Can quantum computer become perfect chess player?
Can it determine whether (when both players are perfect) win white or black? (or is it dead heat?)
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityCan quantum computer become perfect chess player?
Can it determine whether (when both players are perfect) win white or black? (or is it dead heat?)
I've already answered essentially this question, on Chess Stack Exchange. The executive summary is that chess doesn't seem particularly well-suited to quantum computation's strengths so there's no particular reason to believe that a quantum computer would be any better at it than a classical one.
Quantum computers can evaluate game trees asymptotically faster than classical computers, but this advantage is not sufficient to solve chess.
Wikipedia gives an estimate of $10^{123}$ for the game tree complexity of chess. The best known classical algorithm can solve a randomized NAND tree of size $N$ in $O(N^{0.793})$ steps. The quantum algorithm mentioned in the blog post I linked to can do it in roughly $O(N^{0.5})$ steps. Ignoring constant factors and other important things, this roughly means the quantum algorithm can explore and solve the chess game tree in $\sqrt{10^{123}} \approx 10^{62}$ steps instead of $10^{92}$ steps.
Unfortunately, $10^{62}$ is still obscenely gigantic. It is "consume all the entropy in the galaxy just to run the computation" levels of absurd. Maybe there's a tractable algorithm out there that can play chess perfectly, by relying on the fact that its game tree has more structure than an arbitrary NAND tree, but just switching from classical to quantum isn't enough.