Solving chess with a quantum computer

Question

Given that the game-tree complexity of the game of chess is at least 10¹²³ and quantum computers may eventually become millions of times faster than a classical computer; will it be possible for a quantum algorithm to process each possible combination of moves within a lifetime?

Answer 1

Maybe, but whats the point - it would need to somehow store allready examined move-paths and given the huge amount of possible paths it would be impossible (remember that there are a lot more paths than there are atoms in the known universe)

Answer 2

This is my understanding of using quantum machine to solve a NP problem:

The efficiency of using a quantum machine depends on your implementation of the cost function - the modelling of your problem.

I would like to define a cost function - a polynomial includes all the possible combinations of the moves - and pass to the quantum machine. And each move is a boolean variable.

There are several requirements (constrains) of using a quantum machine to solve a NP Complete or NP hard problem:

1. Number of variables in your problem is smaller than or equal to number of qubit (quantum bit) in a Quantum Machine chip
2. The polynomial has to be QUBO problem(Quadratic unconstrained binary optimization) - by applying force to 2 quantum bits (base on current quantum machine technology, hopefully HOBO (Higher order binary optimization - this PAPER) polynomial will be acceptable by quantum chip in future)

If those constrains are satisfied, than we can convert the complexity of a NP problem to a lower degree. (for example from O(N^3) to O(N^2))

The current quantum machine has up to 512 qubit (D-Wave Two System), it could solve up to 2^512 complexity problem.