Answers.Body: <p>It should be verbalized what exactly means 'a solution to chess'.<br>
  Then we will understand what exactly we may get out from the hypothetical black-box chess solver (BBCS).<br>
  We will feed BBCS with the chess board position.<br>
  BBCS will spit out an integer number X.
  0 means there is no solution for that position (or the position itself is not legit)
  Another integer number means the least number of moves to transform the original position into a checkmate position in a non-cooperative chess game.
  The ultimate solution to chess will be just an integer number which means the exact number of moves from the chess starting position to a checkmate position.
  Is it a task for quantum computer? IDK.
  As David Richerby lookup - chess is not for QC.
  But when we must find a single integer number X to declare "mate in X moves" it seems more like to find a needle in haystack...
  Am I wrong?</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-09-04T13:10:58.243Z
Answers.LastActivityDate: 2018-09-04T20:22:18.150Z
Answers.LastEditDate: 2018-09-04T20:22:18.150Z
Answers.UserDisplayName: user21914
Answers.Body: <p><em>Fair warning: This answer contains speculative numbers, and may be off by orders of magnitude.</em></p>
  <p>It's just possible, but unlikely.</p>
  <p>The issue isn't necessarily with whether or not quantum computers will be able to &quot;parallelize&quot; to that extent. The problem is one of simple physics, one that even quantum computers can't realistically get around. Put simply, there's a limited number of calculations that can ever be performed. This was <a href="https://security.stackexchange.com/a/6149/13239">answered by Thomas Pornin</a> at Security.SE, and I quote some of his answer here:</p>
  <blockquote>
  <p>Let's look at a more mundane perspective. It seems fair to assume that, with existing technology, each elementary operation must somehow imply the switching of at least one logic gate. The switching power of a single <a href="https://en.wikipedia.org/wiki/CMOS" rel="nofollow noreferrer">CMOS</a> gate is about <em>C*V<sup>2</sup></em> where <em>C</em> is the gate load capacitance, and <em>V</em> is the voltage at which the gate operates. As of 2011, a very high-end gate will be able to run with a voltage of 0.5 V and a load capacitance of a few femtofarads (&quot;femto&quot; meaning &quot;10<sup>-15</sup>&quot;). This leads to a minimal energy consumption per operation of no less than, say, 10<sup>-15</sup> J. The current total world energy consumption is around 500 EJ (5*10<sup>20</sup> J) per year (or so says <a href="https://en.wikipedia.org/wiki/World_energy_consumption" rel="nofollow noreferrer">this article</a>). Assuming that the total energy production of the Earth is diverted to a single computation for ten years, we get a limit of 5*10<sup>36</sup>, which is close to 2<sup>122</sup>.</p>
  <p>Then you have to take into account technological advances. Given the current trend on ecological concerns and the <a href="https://en.wikipedia.org/wiki/Peak_oil" rel="nofollow noreferrer">peak oil</a>, the total energy production should not increase much in the years to come (say no more than a factor of 2 until year 2040 -- already an ecologist's nightmare). On the other hand, there is technological progress in the design of integrated circuits. <a href="https://en.wikipedia.org/wiki/Moore%27s_Law" rel="nofollow noreferrer">Moore's law</a> states that you can fit twice as many transistors on a given chip surface every two years. A <em>very</em> optimistic view is that this doubling of the number of transistor can be done at constant energy consumption, which would translate to halving the energy cost of an elementary operation every two years. This would lead to a grand total of <strong>2<sup>138</sup> in year 2040</strong> -- and this is for a single ten-year-long computation which mobilizes <em>all</em> the resources of the entire planet.</p>
  </blockquote>
  <p>That is the absolute maximum number of elementary operations that can <em>possibly</em> be done. Now let's <a href="https://chess.stackexchange.com/a/2781/652">look at how many chess positions there are...</a></p>
  <blockquote>
  <p>Let's do some quick numbers. Each of the 64 squares can be empty or hold one of 12 different pieces (R, K, B, Q, K, and P in black and white), so the total number of positions that you could set is at most</p>
  <p>13<sup>64</sup> = 196053476430761073330659760423566015424403280004115787589590963842248961.</p>
  <p>That is about 2 x 10<sup>71</sup> different positions. Of course this is a huge overestimate, because most positions are fake (we should eliminate positions with three or more kings, nine or more white pawns, pawns in the eighth rank, quadruple checks, etc). Let's take the square root:</p>
  <p>13<sup>32</sup> = 442779263776840698304313192148785281,</p>
  <p>or about 5 x 10<sup>35</sup>. By taking the square root we are pretending that for each legal position there is a chess Universe worth of distinct fake positions. This is probably an underestimate, so the true answer must be somewhere in between these two numbers. Now we can confidently say that computers cannot study every legal position in a reasonable time. Even the &quot;tiny&quot; 13<sup>32</sup> is too large...</p>
  </blockquote>
  <p>That smallest number ends up being somewhere around 2<sup>120</sup> or so.</p>
  <p>Let's assume that we represent our boards with a 64-byte string. (Practically it would be handled a little differently, but let's go with it for now.) If I'm remembering my math correctly, a quantum computer would be able to represent this with an 8-byte string, or 64 bits. This leaves us with a total of 2<sup>126</sup> to 2<sup>130</sup> elementary operations <em>just to store each legal and possible position</em>.</p>
  <p>Look at that for a moment. We're not doing anything useful with the information, we're <em>just</em> storing it. And to do so we are mobilizing the resources of the entire <em>planet</em>. Never mind where the storage is physically located. Ignore the whole issue of cooling. Set aside the issue of data transmission. We are diverting enough power to <a href="http://what-if.xkcd.com/13/" rel="nofollow noreferrer">illuminate the Moon</a> just to store the positions.</p>
  <p><strong>At the most optimistic of expectations, a quantum computer <i>might</i> be able to solve chess, at the cost of the entire planet's resources. Realistically, that will not happen.</strong></p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-08-21T20:43:34.877Z
Answers.Text: Quantum computers don't have any problems with the capacity. The 2^n vs n thing, so 2^120 positions in a 64 byte string, is 2^126 positions, or 2^129. a quantum computer needs only 129 quanta particles for that(theoretically). Since we will have the technology for quantum computing until then, probably the computation won't take all planetarian resources, or all planetarian space. THe computer that can do this will probably be no larger than a big room.
Answers.UserDisplayName: MikhailTal
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-08-21T20:45:09.420Z
Answers.Text: This seems like it might be a misunderstanding of how quantum computers work.  As I understand it, qbits represent a superposition of all states, where a single computation (read gate transition) operates on all states simultaneously, returning a result probabilistically.  The argument above applies to more traditional CMOS paradigms.
Answers.UserDisplayName: tbischel
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-08-21T20:51:44.433Z
Answers.Text: I think the real question is can graph searching fit into a quantum computing paradigm... I've heard that there are good results solving the traveling salesman problem with quantum computers, so maybe there is an approach
Answers.UserDisplayName: tbischel
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-08-21T20:57:48.067Z
Answers.Text: At that point, why not just ask "When will quantum computing be practical?" Given those definitions, it's not a question of "whether". I'll have to do some reading this weekend.
Answers.UserDisplayName: Jonathan Garber
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-08-21T21:00:10.197Z
Answers.Text: Quantum Computing is like Fusion power... perpetually 50 years out ;)
Answers.UserDisplayName: tbischel
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-08-21T21:57:39.850Z
Answers.Text: @JonathanGarber How do you get 2^126 or 2^130? And I don't understand how CMOS gates are related to estimating the power requirements of a quantum computer.
Answers.UserDisplayName: JiK
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-08-21T22:51:07.700Z
Answers.Text: This answer is fundamentally wrong because it's entirely about classical computers and the question is about quantum computers.
Answers.UserDisplayName: David Richerby
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-08-21T20:01:36.323Z
Answers.LastActivityDate: 2014-08-21T20:18:46.060Z
Answers.LastEditDate: 2020-06-17T09:59:59.497Z
Answers.UserDisplayName: Jonathan Garber
Answers.Body: <p>I'm not an expert on quantum computation but my understanding is that quantum computers are <em>not</em> expected to be useful for chess.</p>
  
  <p>Quantum algorithms are very good at finding needles in haystacks: the three big quantum algorithms are <a href="https://en.wikipedia.org/wiki/Shor%27s_algorithm" rel="noreferrer">Shor's factorization algorithm</a>, <a href="https://en.wikipedia.org/wiki/Grover%27s_algorithm" rel="noreferrer">Grover's database lookup algorithm</a> and the <a href="https://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm" rel="noreferrer">Deutsch&ndash;Jozsa algorithm</a>, which essentially determines whether a long list of numbers is either all zeroes, all ones or half of each.
  All of these problems can be seen as examples of "I've hidden something: you must find it quickly." In factorization, I've "hidden" the prime factors and you must find them; in database lookup, I've hidden an entry with a given key in a large unsorted table and you must find it; in the problem solved by Deutsch&ndash;Jozsa, I might have placed a large number of zeroes in a table of ones but, with a classical algorithm, when you've looked at half the table and seen only ones, you might have just been unlucky and looked at the "wrong" half.  Note also that all of these problems could be solved quickly by an unrealistically parallel classical computer: you could try all the factors in parallel, look at all the database entries in parallel and look at all the values in the zero-one table in parallel.</p>
  
  <p>Solving chess isn't even slightly like any of these problems. It's a fundamentally sequential activity. Whether or not my move is any good depends on what you do in response. Whether or not your response is any good depends on what I do in response to that. And so on.  You might imagine you can do the first ply of the search by taking a superposition of the possible moves.  But then what do you do at the second ply? You can't just take the superposition of all the positions we could be in after two ply because that has forgotten the tree structure. For example, consider this very artificial position, with white to move:</p>
  
  <pre><code>[FEN "1k6/ppp5/5Q2/7q/8/8/PPP5/1K6 w - - 0 2"]
  </code></pre>
  
  <p>If we forget the tree structure, Black is very happy. He says, "In two ply, the best position I can be in is that I deliver checkmate!"  This is true but, of course, White will never allow that, since White's best move is one that prevents Black from checkmating (or doing anything else).  Chess isn't about figuring out the best move you can possibly make in N ply: it's about figuring out the best move that your opponent will allow you to play in N ply. Quantum computers don't seem to be good at this back-and-forth, give-and-take reasoning. We don't even know how to solve chess with an unrealistically parallel classical computer.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-08-23T06:49:12.507Z
Answers.Text: I wouldn't put it past quantum computing... we've seen major progress in other graph search type problems, like using quantum annealing to solve the traveling salesman problem.  Maybe some clever person can figure out how to do something similar in chess?  http://www.gizmag.com/d-wave-quantum-computer-supercomputer-ranking/27476/
Answers.UserDisplayName: tbischel
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-08-23T08:11:35.087Z
Answers.Text: @tbischel But chess, an adversarial tree search, doesn't look at all like TSP, which is another needle-in-a-haystack problem. Also, note that DWave's claims are, shall we say, [quite controversial](http://www.scottaaronson.com/blog/?p=1400). There are at least two groups who have written quantum annealing simulations that outperform DWave when run on an ordinary laptop, for example.
Answers.UserDisplayName: David Richerby
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2014-08-23T16:45:32.680Z
Answers.Text: I don't deny that there currently doesn't exist a quantum equivalent to say alpha beta search... but given that quantum computing algorithms are still in their infancy, that doesn't mean they never will be.  For example: http://web.ist.utl.pt/luis.tarrataca/publications/treeSearchAndQuantumComputation.pdf
  As for DWave, I recognize the controversy exists since their model for quantum computing is different than standard models... I would approach them cautiously, although they do have customers like Google, NASA, and the NSA.
Answers.UserDisplayName: tbischel
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-11T03:08:27.760Z
Answers.Text: Wouldn't quantum annealing solve chess?
Answers.UserDisplayName: Behrang Saeedzadeh
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2014-08-21T23:30:13.573Z
Answers.LastActivityDate: 2018-07-09T09:14:01.730Z
Answers.LastEditDate: 2018-07-09T09:14:01.730Z
Answers.UserDisplayName: David Richerby
Body: <p>The theory is that there are more that 10^40 positions, and a computer that works with an atomic scale has to be impossibly large(As in galaxy-scale large), and well beyond our current level of knowledge.</p>
  
  <p>But now, quantum computers will soon be available. This computer can have 2^n, instead of n bytes of space, because of quantum states. With this new large place for tablebases, will chess  be solved? Of course, this will take more breakthroughs in the future, but will we see 8 piece databases in the following years?</p>
  
  <p>Many questions on the possibility of solving chess revolve on the fact that we don't have enough computer space to fill them. Will quantum computers change the status quo? </p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2014-08-21T13:09:01.977Z
Comments.Text: "But now, quantum computers will soon be available" Source on this?
Comments.UserDisplayName: Cleveland
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2014-08-21T13:24:41.840Z
Comments.Text: Microsoft is developing a technology atm that will come out in 2015. A friend of mine showed me an article.
Comments.UserDisplayName: MikhailTal
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2014-08-21T14:36:43.903Z
Comments.Text: As a physics student, let me assure you *quantum computers will not be used to play chess anytime soon*.
Comments.UserDisplayName: Danu
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2014-08-21T14:42:07.240Z
Comments.Text: @Danu that is quite a silly argument from 'authority'
Comments.UserDisplayName: Spork
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2014-08-21T14:44:21.837Z
Comments.Text: @Spork Sure, but it's easily backed up. Quantum computation is still in the very early stages, research is still focused on much more basic things such as simple mathematics problems (such as factoring small prime numbers).
Comments.UserDisplayName: Danu
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2014-08-21T14:44:58.843Z
Comments.Text: We are discussing here what would happen if they existed. Microsoft might fail in its endeavour, or some tiny company in the slums of Hong Kong can succeed before them. The point is that it is theoretically possible, and what will the impact be?
Comments.UserDisplayName: MikhailTal
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2014-08-21T14:48:45.590Z
Comments.Text: @Spork you could say the same about "A friend of mine showed me an article"
Comments.UserDisplayName: Cleveland
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2014-08-21T14:51:29.387Z
Comments.Text: @Cleveland We are discussing theoretically here. I saw that it could become possible, so what if it became possible?
Comments.UserDisplayName: MikhailTal
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2014-08-21T14:52:59.000Z
Comments.Text: @Cleveland that one is so obvious I doubt many people would put a lot of faith in it. The friend was probably talking about 2015 Xbox games anyway http://www.neowin.net/news/microsoft-confirms-quantum-break-coming-in-2015-to-xbox-one
Comments.UserDisplayName: Spork
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2014-08-21T14:54:42.847Z
Comments.Text: Nope not that. Quantum computing, not Xbox One games. I am sure of it.
Comments.UserDisplayName: MikhailTal
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2014-08-21T21:59:28.803Z
Comments.Text: A quantum computer does not work by storing classical information worth of 2^n bits in n qubits and using that like a classical computer would.
Comments.UserDisplayName: JiK
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2014-08-21T22:03:11.583Z
Comments.Text: By solving do you mean (a) knowing the result with optimal play, (b) knowning the optimal play for both players in positions where the player having the move has played optimally in all of his previous moves, or (c) knowing the optimal play in each legal position?
Comments.UserDisplayName: JiK
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2014-08-23T10:43:05.737Z
Comments.Text: He's probably even talking about strong probable primes.
Comments.UserDisplayName: chaosflaws
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-07-09T15:10:01.187Z
Comments.Text: As a physicist, every single sentence in the question is plain wrong and false.
Comments.UserDisplayName: gented
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-07-11T01:01:59.900Z
Comments.Text: The fact that you think having "2^n" bytes on a quantum computer really shows your lack of understanding about how they even work. Why is this question in chess stack exchange section?
Comments.UserDisplayName: Matthew Liu
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2018-07-11T09:02:22.780Z
Comments.Text: Quantum computers only have n bits of memory, but to describe a quantum state of n bits, you need $2^n$ numbers. Someone may be able to come up with a exponentially faster quantum algorithm for alpha-beta pruning then there is a tiny chance it can solve chess, however this is terribly unlikely
Comments.UserDisplayName: Ariana
Tags: <engines><tablebases><computer-chess>
Title: Will quantum computers solve chess?
ThreadText: # Will quantum computers solve chess?
  
  (Asked by: username_0 on 2014-08-21)
  
  The theory is that there are more that 10^40 positions, and a computer that works with an atomic scale has to be impossibly large(As in galaxy-scale large), and well beyond our current level of knowledge.
  
  But now, quantum computers will soon be available. This computer can have 2^n, instead of n bytes of space, because of quantum states. With this new large place for tablebases, will chess be solved? Of course, this will take more breakthroughs in the future, but will we see 8 piece databases in the following years?
  
  Many questions on the possibility of solving chess revolve on the fact that we don't have enough computer space to fill them. Will quantum computers change the status quo?
  
  **Tags:** engines, tablebases, computer-chess
  
  > **Comments:**
  > **username_1**: "But now, quantum computers will soon be available" Source on this?  
  > **username_0**: Microsoft is developing a technology atm that will come out in 2015. A friend of mine showed me an article.  
  > **username_2**: As a physics student, let me assure you *quantum computers will not be used to play chess anytime soon*.  
  > **username_3**: @username_2 that is quite a silly argument from 'authority'  
  > **username_2**: @username_3 Sure, but it's easily backed up. Quantum computation is still in the very early stages, research is still focused on much more basic things such as simple mathematics problems (such as factoring small prime numbers).  
  > **username_0**: We are discussing here what would happen if they existed. Microsoft might fail in its endeavour, or some tiny company in the slums of Hong Kong can succeed before them. The point is that it is theoretically possible, and what will the impact be?  
  > **username_1**: @username_3 you could say the same about "A friend of mine showed me an article"  
  > **username_0**: @username_1 We are discussing theoretically here. I saw that it could become possible, so what if it became possible?  
  > **username_3**: @username_1 that one is so obvious I doubt many people would put a lot of faith in it. The friend was probably talking about 2015 Xbox games anyway http://www.neowin.net/news/microsoft-confirms-quantum-break-coming-in-2015-to-xbox-one  
  > **username_0**: Nope not that. Quantum computing, not Xbox One games. I am sure of it.  
  > **username_4**: A quantum computer does not work by storing classical information worth of 2^n bits in n qubits and using that like a classical computer would.  
  > **username_4**: By solving do you mean (a) knowing the result with optimal play, (b) knowning the optimal play for both players in positions where the player having the move has played optimally in all of his previous moves, or (c) knowing the optimal play in each legal position?  
  > **username_5**: He's probably even talking about strong probable primes.  
  > **username_6**: As a physicist, every single sentence in the question is plain wrong and false.  
  > **username_7**: The fact that you think having "2^n" bytes on a quantum computer really shows your lack of understanding about how they even work. Why is this question in chess stack exchange section?  
  > **username_8**: Quantum computers only have n bits of memory, but to describe a quantum state of n bits, you need $2^n$ numbers. Someone may be able to come up with a exponentially faster quantum algorithm for alpha-beta pruning then there is a tiny chance it can solve chess, however this is terribly unlikely  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_12 on 2014-08-21. Score: 26 | Accepted answer
  
  I'm not an expert on quantum computation but my understanding is that quantum computers are not expected to be useful for chess.
  Quantum algorithms are very good at finding needles in haystacks: the three big quantum algorithms are Shor's factorization algorithm, Grover's database lookup algorithm and the Deutsch–Jozsa algorithm, which essentially determines whether a long list of numbers is either all zeroes, all ones or half of each.
  All of these problems can be seen as examples of "I've hidden something: you must find it quickly." In factorization, I've "hidden" the prime factors and you must find them; in database lookup, I've hidden an entry with a given key in a large unsorted table and you must find it; in the problem solved by Deutsch–Jozsa, I might have placed a large number of zeroes in a table of ones but, with a classical algorithm, when you've looked at half the table and seen only ones, you might have just been unlucky and looked at the "wrong" half.  Note also that all of these problems could be solved quickly by an unrealistically parallel classical computer: you could try all the factors in parallel, look at all the database entries in parallel and look at all the values in the zero-one table in parallel.
  Solving chess isn't even slightly like any of these problems. It's a fundamentally sequential activity. Whether or not my move is any good depends on what you do in response. Whether or not your response is any good depends on what I do in response to that. And so on.  You might imagine you can do the first ply of the search by taking a superposition of the possible moves.  But then what do you do at the second ply? You can't just take the superposition of all the positions we could be in after two ply because that has forgotten the tree structure. For example, consider this very artificial position, with white to move:
  [FEN "1k6/ppp5/5Q2/7q/8/8/PPP5/1K6 w - - 0 2"]
  
  If we forget the tree structure, Black is very happy. He says, "In two ply, the best position I can be in is that I deliver checkmate!"  This is true but, of course, White will never allow that, since White's best move is one that prevents Black from checkmating (or doing anything else).  Chess isn't about figuring out the best move you can possibly make in N ply: it's about figuring out the best move that your opponent will allow you to play in N ply. Quantum computers don't seem to be good at this back-and-forth, give-and-take reasoning. We don't even know how to solve chess with an unrealistically parallel classical computer.
  
  > **Comments:**
  > **username_11**: I wouldn't put it past quantum computing... we've seen major progress in other graph search type problems, like using quantum annealing to solve the traveling salesman problem.  Maybe some clever person can figure out how to do something similar in chess?  http://www.gizmag.com/d-wave-quantum-computer-supercomputer-ranking/27476/  
  > **username_12**: @username_11 But chess, an adversarial tree search, doesn't look at all like TSP, which is another needle-in-a-haystack problem. Also, note that DWave's claims are, shall we say, [quite controversial](http://www.scottaaronson.com/blog/?p=1400). There are at least two groups who have written quantum annealing simulations that outperform DWave when run on an ordinary laptop, for example.  
  > **username_11**: I don't deny that there currently doesn't exist a quantum equivalent to say alpha beta search... but given that quantum computing algorithms are still in their infancy, that doesn't mean they never will be.  For example: http://web.ist.utl.pt/luis.tarrataca/publications/treeSearchAndQuantumComputation.pdf As for DWave, I recognize the controversy exists since their model for quantum computing is different than standard models... I would approach them cautiously, although they do have customers like Google, NASA, and the NSA.  
  > **username_13**: Wouldn't quantum annealing solve chess?  
  
  ---
  
  ### Answer by username_9 on 2018-09-04. Score: -1
  
  It should be verbalized what exactly means 'a solution to chess'.  
  Then we will understand what exactly we may get out from the hypothetical black-box chess solver (BBCS).  
  We will feed BBCS with the chess board position.  
  BBCS will spit out an integer number X.
  0 means there is no solution for that position (or the position itself is not legit)
  Another integer number means the least number of moves to transform the original position into a checkmate position in a non-cooperative chess game.
  The ultimate solution to chess will be just an integer number which means the exact number of moves from the chess starting position to a checkmate position.
  Is it a task for quantum computer? IDK.
  As username_12 lookup - chess is not for QC.
  But when we must find a single integer number X to declare "mate in X moves" it seems more like to find a needle in haystack...
  Am I wrong?
  
  
  ---
  
  ### Answer by username_10 on 2014-08-21. Score: -3
  
  *Fair warning: This answer contains speculative numbers, and may be off by orders of magnitude.*
  
  It's just possible, but unlikely.
  
  The issue isn't necessarily with whether or not quantum computers will be able to "parallelize" to that extent. The problem is one of simple physics, one that even quantum computers can't realistically get around. Put simply, there's a limited number of calculations that can ever be performed. This was [answered by Thomas Pornin](https://security.stackexchange.com/a/6149/13239) at Security.SE, and I quote some of his answer here:
  
  > Let's look at a more mundane perspective. It seems fair to assume that, with existing technology, each elementary operation must somehow imply the switching of at least one logic gate. The switching power of a single [CMOS](https://en.wikipedia.org/wiki/CMOS) gate is about *C\*V2* where *C* is the gate load capacitance, and *V* is the voltage at which the gate operates. As of 2011, a very high-end gate will be able to run with a voltage of 0.5 V and a load capacitance of a few femtofarads ("femto" meaning "10-15"). This leads to a minimal energy consumption per operation of no less than, say, 10-15 J. The current total world energy consumption is around 500 EJ (5\*1020 J) per year (or so says [this article](https://en.wikipedia.org/wiki/World_energy_consumption)). Assuming that the total energy production of the Earth is diverted to a single computation for ten years, we get a limit of 5\*1036, which is close to 2122.
  >
  > Then you have to take into account technological advances. Given the current trend on ecological concerns and the [peak oil](https://en.wikipedia.org/wiki/Peak_oil), the total energy production should not increase much in the years to come (say no more than a factor of 2 until year 2040 -- already an ecologist's nightmare). On the other hand, there is technological progress in the design of integrated circuits. [Moore's law](https://en.wikipedia.org/wiki/Moore%27s_Law) states that you can fit twice as many transistors on a given chip surface every two years. A *very* optimistic view is that this doubling of the number of transistor can be done at constant energy consumption, which would translate to halving the energy cost of an elementary operation every two years. This would lead to a grand total of **2138 in year 2040** -- and this is for a single ten-year-long computation which mobilizes *all* the resources of the entire planet.
  
  That is the absolute maximum number of elementary operations that can *possibly* be done. Now let's [look at how many chess positions there are...](https://chess.stackexchange.com/a/2781/652)
  
  > Let's do some quick numbers. Each of the 64 squares can be empty or hold one of 12 different pieces (R, K, B, Q, K, and P in black and white), so the total number of positions that you could set is at most
  >
  > 1364 = 196053476430761073330659760423566015424403280004115787589590963842248961.
  >
  > That is about 2 x 1071 different positions. Of course this is a huge overestimate, because most positions are fake (we should eliminate positions with three or more kings, nine or more white pawns, pawns in the eighth rank, quadruple checks, etc). Let's take the square root:
  >
  > 1332 = 442779263776840698304313192148785281,
  >
  > or about 5 x 1035. By taking the square root we are pretending that for each legal position there is a chess Universe worth of distinct fake positions. This is probably an underestimate, so the true answer must be somewhere in between these two numbers. Now we can confidently say that computers cannot study every legal position in a reasonable time. Even the "tiny" 1332 is too large...
  
  That smallest number ends up being somewhere around 2120 or so.
  
  Let's assume that we represent our boards with a 64-byte string. (Practically it would be handled a little differently, but let's go with it for now.) If I'm remembering my math correctly, a quantum computer would be able to represent this with an 8-byte string, or 64 bits. This leaves us with a total of 2126 to 2130 elementary operations *just to store each legal and possible position*.
  
  Look at that for a moment. We're not doing anything useful with the information, we're *just* storing it. And to do so we are mobilizing the resources of the entire *planet*. Never mind where the storage is physically located. Ignore the whole issue of cooling. Set aside the issue of data transmission. We are diverting enough power to [illuminate the Moon](http://what-if.xkcd.com/13/) just to store the positions.
  
  **At the most optimistic of expectations, a quantum computer *might* be able to solve chess, at the cost of the entire planet's resources. Realistically, that will not happen.**
  
  > **Comments:**
  > **username_0**: Quantum computers don't have any problems with the capacity. The 2^n vs n thing, so 2^120 positions in a 64 byte string, is 2^126 positions, or 2^129. a quantum computer needs only 129 quanta particles for that(theoretically). Since we will have the technology for quantum computing until then, probably the computation won't take all planetarian resources, or all planetarian space. THe computer that can do this will probably be no larger than a big room.  
  > **username_11**: This seems like it might be a misunderstanding of how quantum computers work.  As I understand it, qbits represent a superposition of all states, where a single computation (read gate transition) operates on all states simultaneously, returning a result probabilistically.  The argument above applies to more traditional CMOS paradigms.  
  > **username_11**: I think the real question is can graph searching fit into a quantum computing paradigm... I've heard that there are good results solving the traveling salesman problem with quantum computers, so maybe there is an approach  
  > **username_10**: At that point, why not just ask "When will quantum computing be practical?" Given those definitions, it's not a question of "whether". I'll have to do some reading this weekend.  
  > **username_11**: Quantum Computing is like Fusion power... perpetually 50 years out ;)  
  > **username_4**: @JonathanGarber How do you get 2^126 or 2^130? And I don't understand how CMOS gates are related to estimating the power requirements of a quantum computer.  
  > **username_12**: This answer is fundamentally wrong because it's entirely about classical computers and the question is about quantum computers.  
  
  ---
  
  