Will quantum computers solve chess?

Question

The theory is that there are more that 10^40 positions, and a computer that works with an atomic scale has to be impossibly large(As in galaxy-scale large), and well beyond our current level of knowledge.

But now, quantum computers will soon be available. This computer can have 2^n, instead of n bytes of space, because of quantum states. With this new large place for tablebases, will chess be solved? Of course, this will take more breakthroughs in the future, but will we see 8 piece databases in the following years?

Many questions on the possibility of solving chess revolve on the fact that we don't have enough computer space to fill them. Will quantum computers change the status quo?

Answer 1

I'm not an expert on quantum computation but my understanding is that quantum computers are not expected to be useful for chess.

Quantum algorithms are very good at finding needles in haystacks: the three big quantum algorithms are Shor's factorization algorithm, Grover's database lookup algorithm and the Deutsch–Jozsa algorithm, which essentially determines whether a long list of numbers is either all zeroes, all ones or half of each. All of these problems can be seen as examples of "I've hidden something: you must find it quickly." In factorization, I've "hidden" the prime factors and you must find them; in database lookup, I've hidden an entry with a given key in a large unsorted table and you must find it; in the problem solved by Deutsch–Jozsa, I might have placed a large number of zeroes in a table of ones but, with a classical algorithm, when you've looked at half the table and seen only ones, you might have just been unlucky and looked at the "wrong" half. Note also that all of these problems could be solved quickly by an unrealistically parallel classical computer: you could try all the factors in parallel, look at all the database entries in parallel and look at all the values in the zero-one table in parallel.

Solving chess isn't even slightly like any of these problems. It's a fundamentally sequential activity. Whether or not my move is any good depends on what you do in response. Whether or not your response is any good depends on what I do in response to that. And so on. You might imagine you can do the first ply of the search by taking a superposition of the possible moves. But then what do you do at the second ply? You can't just take the superposition of all the positions we could be in after two ply because that has forgotten the tree structure. For example, consider this very artificial position, with white to move:

[FEN "1k6/ppp5/5Q2/7q/8/8/PPP5/1K6 w - - 0 2"]

If we forget the tree structure, Black is very happy. He says, "In two ply, the best position I can be in is that I deliver checkmate!" This is true but, of course, White will never allow that, since White's best move is one that prevents Black from checkmating (or doing anything else). Chess isn't about figuring out the best move you can possibly make in N ply: it's about figuring out the best move that your opponent will allow you to play in N ply. Quantum computers don't seem to be good at this back-and-forth, give-and-take reasoning. We don't even know how to solve chess with an unrealistically parallel classical computer.

Answer 2

It should be verbalized what exactly means 'a solution to chess'.
Then we will understand what exactly we may get out from the hypothetical black-box chess solver (BBCS).
We will feed BBCS with the chess board position.
BBCS will spit out an integer number X. 0 means there is no solution for that position (or the position itself is not legit) Another integer number means the least number of moves to transform the original position into a checkmate position in a non-cooperative chess game. The ultimate solution to chess will be just an integer number which means the exact number of moves from the chess starting position to a checkmate position. Is it a task for quantum computer? IDK. As David Richerby lookup - chess is not for QC. But when we must find a single integer number X to declare "mate in X moves" it seems more like to find a needle in haystack... Am I wrong?

Answer 3

Fair warning: This answer contains speculative numbers, and may be off by orders of magnitude.

It's just possible, but unlikely.

The issue isn't necessarily with whether or not quantum computers will be able to "parallelize" to that extent. The problem is one of simple physics, one that even quantum computers can't realistically get around. Put simply, there's a limited number of calculations that can ever be performed. This was answered by Thomas Pornin at Security.SE, and I quote some of his answer here:

Let's look at a more mundane perspective. It seems fair to assume that, with existing technology, each elementary operation must somehow imply the switching of at least one logic gate. The switching power of a single CMOS gate is about C*V² where C is the gate load capacitance, and V is the voltage at which the gate operates. As of 2011, a very high-end gate will be able to run with a voltage of 0.5 V and a load capacitance of a few femtofarads ("femto" meaning "10^-15"). This leads to a minimal energy consumption per operation of no less than, say, 10^-15 J. The current total world energy consumption is around 500 EJ (5*10²⁰ J) per year (or so says this article). Assuming that the total energy production of the Earth is diverted to a single computation for ten years, we get a limit of 5*10³⁶, which is close to 2¹²².

Then you have to take into account technological advances. Given the current trend on ecological concerns and the peak oil, the total energy production should not increase much in the years to come (say no more than a factor of 2 until year 2040 -- already an ecologist's nightmare). On the other hand, there is technological progress in the design of integrated circuits. Moore's law states that you can fit twice as many transistors on a given chip surface every two years. A very optimistic view is that this doubling of the number of transistor can be done at constant energy consumption, which would translate to halving the energy cost of an elementary operation every two years. This would lead to a grand total of 2¹³⁸ in year 2040 -- and this is for a single ten-year-long computation which mobilizes all the resources of the entire planet.

That is the absolute maximum number of elementary operations that can possibly be done. Now let's look at how many chess positions there are...

Let's do some quick numbers. Each of the 64 squares can be empty or hold one of 12 different pieces (R, K, B, Q, K, and P in black and white), so the total number of positions that you could set is at most

13⁶⁴ = 196053476430761073330659760423566015424403280004115787589590963842248961.

That is about 2 x 10⁷¹ different positions. Of course this is a huge overestimate, because most positions are fake (we should eliminate positions with three or more kings, nine or more white pawns, pawns in the eighth rank, quadruple checks, etc). Let's take the square root:

13³² = 442779263776840698304313192148785281,

or about 5 x 10³⁵. By taking the square root we are pretending that for each legal position there is a chess Universe worth of distinct fake positions. This is probably an underestimate, so the true answer must be somewhere in between these two numbers. Now we can confidently say that computers cannot study every legal position in a reasonable time. Even the "tiny" 13³² is too large...

That smallest number ends up being somewhere around 2¹²⁰ or so.

Let's assume that we represent our boards with a 64-byte string. (Practically it would be handled a little differently, but let's go with it for now.) If I'm remembering my math correctly, a quantum computer would be able to represent this with an 8-byte string, or 64 bits. This leaves us with a total of 2¹²⁶ to 2¹³⁰ elementary operations just to store each legal and possible position.

Look at that for a moment. We're not doing anything useful with the information, we're just storing it. And to do so we are mobilizing the resources of the entire planet. Never mind where the storage is physically located. Ignore the whole issue of cooling. Set aside the issue of data transmission. We are diverting enough power to illuminate the Moon just to store the positions.

At the most optimistic of expectations, a quantum computer might be able to solve chess, at the cost of the entire planet's resources. Realistically, that will not happen.