Quantum Computing

Could a quantum computer be able to brute-force go and play a strong game? Maybe even solve it?

Surely it is within possibility to represent all the possible board combinations at the same time on a quantum computer, unlike with classical computers. Since the number of combinations given N qubits goes as 2^N, we will only need about 500 qubits to store the 3^361 possible boards.

But still it is some way from here to reducing the wavefunction to one good move, that can be read out.

Can anybody come up with a sensible algorithm, or prove that it will take unrealistically long time? I´m working on it myself.

Is there even anyone else out there who knows about both quantum information theory, and Go?

Symplicity: I'm no expert, just a layman who has done a bit of reading on complexity theory and the limits of quantum computing, but I highly doubt that a quantum computer could solve Go. Even assuming that someone can construct a quantum computer beyond the several-qubit scale with no decoherence problems at all and coax a few hundred qubits to represent a Go board, the problem would be much more than representing the board. The reason why a few problems like factoring (Shor's Algorithm) can be done efficiently on a quantum computer is because there are some extraordinary underlying mathematical properties (the periodicity of modular exponentiation relating to the factors) that a quantum computer can exploit and attack "in parallel". The game tree of any arbitrary game, such as Go, would most likely lack any such nice properties. From a mathematical perspective, there is nothing nice or neatly tractable about the definition of territory, the patterns of liberties and capture, the ko rule, etc.

Moreover, it is certain Go in general would still be intractable, even with only very modest increases in board size. Go is EXPTIME-complete, meaning that it takes exponential time to decide the best move in general, whereas quantum computers are not even known to be efficient for the tremendously easier NP-complete problems. Performing any form of minimax search on a quantum computer in better than exponential time is ridiculously unlikely, and one would expect at most a modest (polynomial) speedup compared to now. This much is already proved by the existing literature. Even if 19x19 Go were somehow solvable by a quantum computer (very very unlikely), because Go is still in exponential time, even a small increase in board size (say, to 23x23) would probably make it intractable all over again.

As for achieving a strong level of play, perhaps even professional strength, that seems to be in the range of possibility already, with the way that current technologies are developing. Pro-level play is absolutely absurdly easier than solving the game, in computational terms. I wouldn't be surprised at all if mid-upper dan-level play were achieved, even long before a commerical quantum computer becomes available. The current top (UCT) programs are already several dan on 9x9, and mid-low kyu on 19x19. If the future produces a strong Go program, it won't be from a quantum computer, but future algorithmic innovations and breakthroughs, probably with heavy levels of pruning and heuristics, combined with the current rate of increasing computer power.

zsoujiro: I don't have a deep knowledge about complexity concepts applied to quantum computing, but I do think quantum processing and AI will achieve a lot of success when used together. Moreover, the advance is not just technological; AI itself, as the science it is, is advancing. Quantum computing might allow research in innovative machine-learning models or complex learning algorithms.. I think my base point is: yes, AI-Go will be breeding stronger players all the time.

However, the expression "solving go", as if we were doing sudoku, is wrong. It's like saying you could solve art, or solve mathematics (googleFor:Göedel). Simply, there are things you can not compute. Anyone who's played enough Go knows that this isn't a game a about mere calculations, there is a lot of right brain hemisphere activity going on as well. There are a lot of factors involved in a Go match, and understanding another person's intentions is no easy task for machines. It's a human capacity known as "empathy"; I just don't think machines might get right-hemisphere-type artificial intelligence someday, creative tasks and abstract reasoning, aesthetics perception, intuition, imaginative process.. result => does not compute, I think.

As a last observation: although AI will be making stronger players, there will also exist stronger human players everytime. Human knowledge evolves, intelligence evolves, and of course, Go is constantly evolving itself.

MrMormon: Go is finite: solvable. Creativity is a heuristic until that is possible. Then we increase the size of the board (tee hee hee).