Limits of quantum computation in solving chess

Update:

Since I have written this post some dramatic new results of large scale quantum coherence exhibited by living organisms came to my attention. It has been demonstrated that microtubules in the brain when excited at certain frequencies show signs of superconductivity ( which is large scale quantum behaviour ). This discovery may turn our knowledge about quantum computing upside down. It seems that what scientists are trying to do at near zero kelvin temperatures with a few quantum bits nature has long since managed to do with billions of bits at room temperature. This is not an isolated case of the brain: it turns out that also in photosynthesis quantum behaviour plays a part. It has been long known that organisms having only one cell and no neurons or nerves can behave very intelligently ( can swin, can find food, avoid obstacles, even have short term memory ). The new discoveries on microtubules can now explain this kind of intelligent information processing as well. If the brain is more than just a network of neurons and can process infromation at quantum level then the number of elementary operations it can perform can be much more than previously expected, on the order of 10^27 operations per second. This means that 1 million human brains in 1 year are capable of performing operations on the order of the number of legal chess positions.

These new discoveries open the way for a new approach toward understanding consciousness as well. They lend experimental credibility to a theory of consciousness that has been around for 20 years now: the Orch-OR ( orchestrated objective reduction ) hypothesis of anaesthesiologist Stuart Hameroff and emeritus professor of mathematics Roger Penrose. It is important to note that Penrose goes further than orthodox quantum mechanics would allow: he assumes that the underlying physics is uncomputable therefore the brain can have qualia ( conscious experience ) and access truths that are not available to the conventional ( Turing ) method of computation ( all classical computers we have today are Turing machines ). However whether Penrose is right or not on this issue does not make any difference for the practical speed of computation: even if the orthodox view that quantum computers in principle can't do anything more than a Turing machine with at most exponential slowdown could do, the sheer speedup offered by room temperature large scale quantum behaviour can be a game changer in computing.

What does it mean to 'solve' chess and can it be done?

First of all 'solving' chess can mean two things. You can solve chess in the weak sense, meaning that the outcome of the game is known and both sides ( in case of a draw ) or the winning side ( in case it is a win for one side ) is equipped with a strategy which is guaranteed to reach this outcome. But having a weak solution the guaranteed strategy is only known if the game starts from the starting position. A weak solution can't tell you what to do in an arbitrary yet legal position. The often cited Checkers has only been solved in the weak sense.

Let us be voracious and demand a strong solution of chess meaning that in possession of such a solution the optimal move ( or moves ) in any arbitrary legal position and the outcome of the game from that position are known exactly. In this sense the Lomonosov 7 men endgame tablebases represent a strong solution for the subset of legal positions in which there are only 7 or less pieces. What we demand for a strong solution is no less than a '32 men endgame tablebase'.

How much effort do we need to obtain such a solution? Since the number of possible games grows exponentially with the number of moves and no better solution is known than to play out every possible game and look at their outcome ( you need to perform an 'exhaustive tree search' ) it appears that solving chess can only be done in 'exponential time' which given the average 35 legal moves per position and the maximum length of the longest possible chess game ( 11797 half moves under the fifty move rule ) means an astronomical number of games. Of course there are shortcuts: there are much more possible games than legal positions so you can store the evaluation of positions which you have already seen during the tree search in a transposition table. Also there are symmetries that can be exploited. However these symmetries are very basic ones and reduce the number of positions at most by one order of magnitude which given the 10^40+ legal positions ( the exact number is not known and is subject to debate ) does not help too much. The only hope is to find some new unexpected symmetry or property of positions which could dramatically reduce the 'search space' but the chances for this are slim. Despite shortcuts, for all practical purposes, chess remains an exponential time problem and amounts to examining 10^40+ positions. We are speaking about a very huge number here: on the order of the number of water molecules in all of Earth's oceans - assuming today's 'classical' technological framework ( even taking into account future advances ) the computational and storage requirements for such a solution simply can not be met. But is there a hope that some radically new approach in computing can still do the job? Can the currently mostly theoretically existing quantum computers solve an exponential time problem in 'polynomial time' ( for our purposes: in a reasonable time )? Or are there ultimate physical limits which prevent us from reaching a solution no matter what? These are the questions I aim to have a closer look at.

To answer the question whether quantum computation can solve chess we need to speak about the place of chess in computational complexity theory since the limits of quantum computers are searched within this theory.

The million dollar question of computational complexity theroy is whether  P = NP ? This question informally asks whether problems the solution of which you can verify quickly can also be solved quickly. The suspected answer is of course ' no ' since otherwise this would imply that if you are able to appreciate some music by Mozart ( 'verify' that it is a masterpiece ) you could also compose such music ( 'solve' the problem of composing ) - meaning we should see a lot of 'Mozarts' around and this is not the case. If you set out to compose a masterpiece having no skills for composing, but only for verifying that the composition is good or bad, the best you could do is to write down notes on a sheet in random order, make an orchestra play from the sheet and listening to it decide whether is is a masterpiece or not. If not ( which is very likely ) you can try again with an other random piece. Since the number of possible random music sheets is astronomical, even the age of the universe would not be enough time for you to compose just one masterpiece with this 'brute force method'.

There are some very difficult problems in NP: if you can solve any one of those problems, you can solve all NP problems ( these are called ' NP complete ' problems ). However if the suspected relationship P =/= NP is true, there exist problems which are not easily solvable ( are not in ' P ' ) but solving them would not guarantee that you can solve other NP problems as well ( these are called ' NP intermediate ' problems ). Integer factoring is an NP intermediate problem and we will see the importance of this when speaking of the limits of quantum computation.

It is however suggested that chess is even harder than an NP problem. Not only you can't solve it quickly but having presented a 'solution' ( let's say, that white should make the move 1. e4 or 1. d4 in the starting position ) you can't verify this solution quickly. Even for a verification you need to look at all possible continuations. ( On the other hand a common example of an easily verifiable problem from computational complexity theory would be to check whether some integers add up to zero - you only need to make the additions and there you are - however to find out whether there exists some subset in a random set of integers that sum up to zero is a very hard problem since you having nothing better than to try every possible subset of which there are exponentially many in the function of the size of the set ).

Can quantum computers solve hard problems quickly? The answer is: yes and no. In fact it depends on the problem. In general it can be said that most of the problems that can only be solved using brute force methods ( trying out every possibility ) will remain hard for even a quantum computer. However there are some special problems which are hard for classical computers but theoretically can be quickly solved by quantum computers. A very important and well studied example of such a problem is integer factorization. Integer factorization is important practically because many encription methods rely on the fact that integers having very large factors can only be factored in ridiculously long time using classical computers, making the encription unbreakable. However this problem has a structure which favours a quantum mechanical solution: namely it boils down to finding the period of a function which is 'easy' for quantum mechanics. Quantum mechanics differs from probabilistic classical computation in the sense that not the probabilites add up to one as in the classical case but the squares of the quantum amplitudes. Quantum amplitudes in addition to their absolute value also have a 'phase' ( an angle of rotation ) therefore they are described by a complex number rather than a real number ( as in the classical case ). Here is the catch: quantum amplitudes can cancel each other out or amplify each other depending on in what phase they meat ( this is the explanation for the famous double slit experiment ). So the square of the quantum amplitude ( the probability in the classic sense ) will depend on a very complicated interaction of many quantum amplitudes. It is 'natural' for nature to work with such quantum amplitudes and 'compute' the state of complicated 'entangled' systems of many particles and many quantum states. In this sense the core of integer factorization ( period finding ) turns out to be a very fundamental problem for which nature in order to work properly has to have a solution. But unfortunately chess has nothing do with integer factorization or the simulation of a quantum system. There is nothing fundamental about the rules of chess: its rules were created arbitrarily by humans for the amusement of humans. There is no such natural phenomenon that chess models in an abstract way. It models war fought between humans in an abstract way which is a different story. It is one of the many problems that can only be solved by brute force and this is hard for even quantum computers.

Is there any hope that we can find something better than quantum computing? Here is the point where we bump into something very fundamental: some physical limits that are ubreakable no matter what method we use. Namely that the amount of information that can be stored in a bounded region of space is finite. This non trivial result grew out of the studying of the thermodinamics of black holes. It turns out that the entropy of a black hole only depends only on the surface of its event horizon. Who cares about the information content of black holes you may ask. However unfortunately if you try to pack more and more mass and energy ( ultimately 'information' ) in a limited amount of space at some point the whole thing will collapse into a black hole under its own gravity. So black holes put an ultimate limit on how much information you can pack into a finite amount of space. Interestingly enough it turns out that the amount of information that can be packed into the size of a human brain is cca. 10^42 bits ( on the order of the number of legal chess positions ). This means that you can learn everything about the state of a human brain in 10^42 bits, down to quantum states, down to atoms, electrons, protons, neutrons, quarks, strings, there complex interactions, you name it. This is it: you can't pack in there even one bit more than this. This is a striking result of contemporary physics and while the issue is still not settled it is far from fiction: this view is shared by legitimate scientists the likes of Hawking, 't Hooft, Bekenstein and many others. These results lead many to consider the possibility that the universe is essentially informational ( in fact it is 'made of' information ). In this sense the information content of the whole observable universe is finite. It is always possible to create a problem ( a board game for that matter ) the brute force solution of which requires an arbitrary large number of computational steps ( information processing ). Arbitrarily large means that it can be larger than any particular finite number, so it can exceed than the information processing capability of the entire observable universe ( which is also a finite number ). In that sense it can be said that there are problems that are physically unsolvable no matter how advanced methods one uses. Chess does not belong to this category, solving chess is well within the computatinal capacity of the universe, however whether humans can solve it using the capacity of the Earth is a question that remains a question for the future.