a quantum computer can solve in linear time, problems for which a normal computer requires exponential time. Is chess thus solvable in 'reasonable time' (eg shorter than the expected lifetime of the universe) on a quantum computer ?
It both can and can't solve chess, depends how you look at it.
In my opinion the ultimate result of the game is draw, and I don't think any computer can change my mind.
@jeremyrutman2 said (#1):
> quantum computer can solve in linear time, problems for which a normal computer requires exponential time.
Your premise is already wrong or, lets say, not quite correct. I will try to explain how a quantum computer works with a simple example and i hope the answer to your question will become clear at the end.
Consider one of these old and simple bicycle locks: they had three rings with numbers zero to 9, so 1000 combinations (000-999) were possible. The owner set one of these and then locked it by selecting any random combination. To unlock it again one had to set the correct combination by rotating the rings apropriately.
Now, suppose you want to crack such a lock: since you don't know the combination you will have to try one combination after the other until you are successful. You will start at "000", try to open it and since you are probably unsuccessful you then set it to "001", try to open it, set it to "002" and so on.
This is how a classical computer works. You will need at the worst case (you start at "000" and the combination is "999") one thousand tries to open it but on average you willl need 500 tries or: 500 times the time it takes to open the lock for someone who knows the correct combination (this person will only need one try).
Now, suppose you could try several combinations at once: say, the lock would open if you guess the correct number or you are at most one off. The lock would open when you try "001" and the correct combination would be one of "000", "001" or "002". Because you would only have to try only "001" (covers "000", "001" and "002"), then "004" (covers "003" and "005" as well), then "007", etc. you would save considerable amount of time. You would need only 167 tries on average.
The amount of time you save is because with every try you test not one combination but three at the same time. Now, suppose you could test all combination at the same time: you would only need one try or the same amount of time a person who knows the corect combination would.
Now, this is how a quantum comupter works: for certain operations (ones which are similar to our lock-picking example) it can try "all combinations at once" and get all results at once. Instead of doing it the classical way: try "000", note that it was wrong, then try "001", note that it was wrong, and so on, it tries every combination (or at least a certain amount of them) at once and notes the result of any of these tries. It will not only open the lock with, say, the try "001", testing "000" and "002" as well, but also tell you that the correct combination would have been "002".
So, this is your answer: It may be possible to solve chess *IF* the problem lends itself to what a quantum computer can do. Notice that there are other types of problems, which won't be helped any with a quantum computer. Say, you would have the following problem: you get a number as input. If it is odd, multiply it by seven, if it is even, subtract one. Take the cube root of the result, and give that back as output. For such a problem you will gain absolutely nothing from a quantum computer because for every step you will need the result of the step before and thus it can only be solved in a linear way.
The art of a programmer is to present a problem in a way to the machine so that the computer can make efficient use of all its advantages to solve it. This is what we call "algorithms". Since quantum computers are a very new thing and appropriate algorithms for certain types of problems are only being developed for a short time we cannot say for sure if there is a way to "present chess" to a quantum computer in such a way so that it can make use of its power efficiently. I don't it can't be done, we simply do not know yet.
krasnaya
> quantum computer can solve in linear time, problems for which a normal computer requires exponential time.
Your premise is already wrong or, lets say, not quite correct. I will try to explain how a quantum computer works with a simple example and i hope the answer to your question will become clear at the end.
Consider one of these old and simple bicycle locks: they had three rings with numbers zero to 9, so 1000 combinations (000-999) were possible. The owner set one of these and then locked it by selecting any random combination. To unlock it again one had to set the correct combination by rotating the rings apropriately.
Now, suppose you want to crack such a lock: since you don't know the combination you will have to try one combination after the other until you are successful. You will start at "000", try to open it and since you are probably unsuccessful you then set it to "001", try to open it, set it to "002" and so on.
This is how a classical computer works. You will need at the worst case (you start at "000" and the combination is "999") one thousand tries to open it but on average you willl need 500 tries or: 500 times the time it takes to open the lock for someone who knows the correct combination (this person will only need one try).
Now, suppose you could try several combinations at once: say, the lock would open if you guess the correct number or you are at most one off. The lock would open when you try "001" and the correct combination would be one of "000", "001" or "002". Because you would only have to try only "001" (covers "000", "001" and "002"), then "004" (covers "003" and "005" as well), then "007", etc. you would save considerable amount of time. You would need only 167 tries on average.
The amount of time you save is because with every try you test not one combination but three at the same time. Now, suppose you could test all combination at the same time: you would only need one try or the same amount of time a person who knows the corect combination would.
Now, this is how a quantum comupter works: for certain operations (ones which are similar to our lock-picking example) it can try "all combinations at once" and get all results at once. Instead of doing it the classical way: try "000", note that it was wrong, then try "001", note that it was wrong, and so on, it tries every combination (or at least a certain amount of them) at once and notes the result of any of these tries. It will not only open the lock with, say, the try "001", testing "000" and "002" as well, but also tell you that the correct combination would have been "002".
So, this is your answer: It may be possible to solve chess *IF* the problem lends itself to what a quantum computer can do. Notice that there are other types of problems, which won't be helped any with a quantum computer. Say, you would have the following problem: you get a number as input. If it is odd, multiply it by seven, if it is even, subtract one. Take the cube root of the result, and give that back as output. For such a problem you will gain absolutely nothing from a quantum computer because for every step you will need the result of the step before and thus it can only be solved in a linear way.
The art of a programmer is to present a problem in a way to the machine so that the computer can make efficient use of all its advantages to solve it. This is what we call "algorithms". Since quantum computers are a very new thing and appropriate algorithms for certain types of problems are only being developed for a short time we cannot say for sure if there is a way to "present chess" to a quantum computer in such a way so that it can make use of its power efficiently. I don't it can't be done, we simply do not know yet.
krasnaya
<Comment deleted by user>
I don't think your example is correct; you have a linear speedup and not exponential . This is the crucial qualitative difference between quantum and classical computers and what hints that a solution is conceivable .
It's possible... we don't really yet know what the capabilities of quantum computers will be outside of some particular theoretical examples. A lot of people are betting on using them for optimization problems, of which chess could certainly be considered an example. Probably you wouldn't end up with the game being solved in the sense that with perfect play every position has a deterministic outcome of W/L/D, but something more like AlphaZero which uses a probabilistic algorithm to estimate the chances of a particular move leading to a win.
Working the other way, it's possible that quantum computers may be able to make more significant advances in pushing the endgame tablebases back farther, so that with more pieces on the board an engine could predict an exact winning sequence.
Working the other way, it's possible that quantum computers may be able to make more significant advances in pushing the endgame tablebases back farther, so that with more pieces on the board an engine could predict an exact winning sequence.
@jeremyrutman2 said (#6):
> I don't think your example is correct; you have a linear speedup and not exponential .
Well, first off, if you look at the Landau-symbol of the algorithm i described you see that it scales with 1/log(n) (for n being the number of positions checked simultaneously), which to my untrained eye seems like an exponential function.
Furthermore, the "speedup" as you like to call it can't be purely exponential because qubits (which make up - today still hypothetical - quantum registers are only in a <0|1> superposition. Once measured they collapse to a simple string of 0s and 1s like a classical register. Since quantum processors do not have an infinte amount of infinitely long quantum registers your exponentiationends at some point and will be linear at best from that point on. This is similar to so-called "massively parallel" computers, like the platform AlphaZero ran on (basically a few thousands of IBMs POWER [Performance Optimization With Enhanced RISC] CPUs on Googles OpenPOWER hardware).
But i have to admit i only work in IT for about 40 years and am not that knowledgeable about quantum computers, so: how about you, obviously an accomplished expert in the field, would explain how quantum computers and their algorithms work in detail to us? To be honest i am not that fluent in tensor analysis and when quantum mechanics go about the Dirac notation of quantum systems interacting i become confused quite quickly.
krasnaya
> I don't think your example is correct; you have a linear speedup and not exponential .
Well, first off, if you look at the Landau-symbol of the algorithm i described you see that it scales with 1/log(n) (for n being the number of positions checked simultaneously), which to my untrained eye seems like an exponential function.
Furthermore, the "speedup" as you like to call it can't be purely exponential because qubits (which make up - today still hypothetical - quantum registers are only in a <0|1> superposition. Once measured they collapse to a simple string of 0s and 1s like a classical register. Since quantum processors do not have an infinte amount of infinitely long quantum registers your exponentiationends at some point and will be linear at best from that point on. This is similar to so-called "massively parallel" computers, like the platform AlphaZero ran on (basically a few thousands of IBMs POWER [Performance Optimization With Enhanced RISC] CPUs on Googles OpenPOWER hardware).
But i have to admit i only work in IT for about 40 years and am not that knowledgeable about quantum computers, so: how about you, obviously an accomplished expert in the field, would explain how quantum computers and their algorithms work in detail to us? To be honest i am not that fluent in tensor analysis and when quantum mechanics go about the Dirac notation of quantum systems interacting i become confused quite quickly.
krasnaya
I can see how working with classical computers for 40 yrs would limit one's worldview to classical computing with classical parallelism, and that the crucial qualitative difference allowing for the exponential speedup of quantum computation would be more familiar to a PhD in physics such as myself. Your speedup is a constant factor for a given n, and although you failed to note which Landau symbol you meant, in any case the speedup of your rather irrelevant example is 1/n not 1/log(n). A relevant exponential scaling in this case would be to check exp(t) combinations in time t, such that adding a digit to the combination lock would only 'cost' an extra constant factor in time to crack. . Also Dirac notation is actually pretty simple, maybe give it some time.
Yes, the solution is 5
This topic has been archived and can no longer be replied to.