Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
Will it be possible to use quantum computing to one day solve the game of chess? If so, any estimate as to how many qubits it would require?
The game of checkers has already been solved through back in 2007 after years of number crunching. But they don't expect that chess will be able to be solved the same way because the problem is an order of magnitude more difficult. There are an estimated $10^{40}$ legal chess positions and about $10^{120}$ possible games.
As an initial matter, let's ask "what is the classical computational complexity of solving 'mate-in-$n$' type games?" For example, is it even in $\mathcal{NP}$ to know, given a certain chess position, that white can mate in $10$ or fewer moves?
It's been known for a while that we can consider such questions as a "quantified boolean formula" (QBF) question. Let's rephrase our question as:
$$\exists w_1\forall b_1\exists w_2\forall b_2\cdots\exists w_n:\phi(w_1,b_1,w_2,b_2,\cdots,w_n)?$$
This "mate-in-$n$" statement can be read as "given a state of the board $\phi$ encoding the rules of chess, does there exist a move by white such that for moves by black, there is a countermove by white such that... the moves applied to the board $\phi$ will lead to a mate by white?"
This "mate-in-$n$" is precisely a way to think about the polynomial hierarchy $\mathcal{PH}$. The mate-in-$10$ is at the $10^{th}$ level of the hierarchy (or maybe it's the $20^{th}$) because there are $20$ iterations of for-alls and there-exists. $\phi$ is easy to evaluate (polynomial evaluation of whether there's a mate or not). The number of qubits would be polynomial in $n$ I think (high thousands?).
Letting $n$ vary polynomialy distinguishes $\mathcal{PH}$ from $\mathcal{PSPACE}$. Magically, although we know that $\mathcal{BQP}\subseteq\mathcal{PSPACE}$, it's likely that $\mathcal{BQP}$ and $\mathcal{PH}$ are incomparable. I think the implication is that certain well-framed QBF-style questions can be answered faster than classical algorithms.
For chess proper, most games can be completed in about $50$ moves or less. So we can say "is there a mate-in-$50$ for white, given the starting position?"
Chess has a lot of asymmetry that may make it difficult to frame in the right way. Weichi (Go) may be a better candidate for pondering. I suspect a toy game, based on forrelation, can be built where a quantum computer can outperform a classical computer.
EDIT
To think about how to utilize such an algorithm, let's take the QBF a little bit more. The output of the QBF is either a "YES" (a forced mate is possible) or "NO" (a forced mate is not possible).
Say we are white, and we have a quantum QBF-solver that can be fed a given board position with black to move, and will spit out whether there's a winning strategy for black (i.e. YES or NO). It is our turn to move.
We can cycle through all of the available moves for white by making a putative move, and ask our quantum QBF-solver whether black has a winning response. If we find a move where black doesn't have a winning response we can take that line.
In the comments, you suggest that chess isn't likely played out in $50$ moves starting from the initial board, and that $6000$ moves is more likely.
Nonetheless even accepting $6000$ is the better estimate, I maintain that the number of qubits is polynomial in the depth of the tree you are willing to review, otherwise you haven't got a practical algorithm.
Speculatively expanding on previous answer
Quantum computers tend to outperform classical computers in determining global properties of functions. Further, the properties tend to be some measure of global symmetry. Based on the global symmetry, the probability amplitudes can constructively (and destructively) interfere, in ways that a classical computer could not.
Let's look at chess for a moment.
Deciding a winning position in chess, e.g. a mate, seems very much a local property of the board. There may be many pieces left on a board, but many of the pieces are irrelevant to the mating position. Of course pawn structure is a global property in a way, but pawns and many pieces (knights/kings/bad-color bishops) only have a local influence.
Chess by its nature is very asymmetric. Castling of course is a very asymmetric move, but I also mean, for example, that a bishop behaves significantly differently than a knight or a queen. A pawn captures differently than it moves.
Let's compare chess to wei-chi/go/paduk.
Wei-chi has much more of a global feel to it than chess. Each stone can have both a long-range and a short-range impact. Life and death may hinge on being able to connect to a far-away island.
The rules of wei-chi are much more symmetric, in a sense that "all stones are born equal." There are some asymmetries, of course, such as the ko rule. The edge-of-the-board is different than the center, which is a bit of asymmetry; however, there's nothing quite like the dramatic difference in strength between a queen and a knight or a pawn.
Ignoring such ko-rule asymmetries for now, let's let black be $0$, white be $1$, let $x\in\{0,1,blank\}$, and $f(x_1^1,x_1^2,\cdots,x_1^{19},\cdots,x_{19}^{19})$ be a function that takes a $19\times 19$ wei-chi board (e.g., a board after two consecutive passes), and returns whether white or black or neither has more claimed territory. I'm pretty sure $f$ is not that difficult to calculate, at least to a first level. Once black places the first stone, we can ask the same about the new board position with a new function $f^1$, and so on. Here $f^1$ is just like $f$ but one of the values of one of the $x^i_j$ has been fixed to $0$.
Speculatively, a quantum computer may be able to answer such a global property of $f$ as "is there a move for black, such that for all moves by white, there's a countermove by black, such that... black ends up with more territory?" With the placement of each of the stones, it feels like maybe there's constructive/destructive interference at work.
Speculating very much even more, perhaps we can construct a toy "battleship-style" or "Kiregspiel" style wei-chi game, where white $f$ and black $g$ take turns placing stones secretly on their respective board, and the value of the board is determined by a measure of the correlation between $f$ and the Fourier transform of $g$. We know a quantum computer is likely to outperform a classical computer for such a "forrelation" game; working backwards to create rules for such a game may be possible.
