quantum computer. will it hurt chess theory?

A quantum computer works differently, but it is faster.
https://www.nature.com/articles/d41586-020-03434-7

The quantum computer in 200 seconds solved a problem that would take 2.5 billion years on a supercomputer.
It is possible to re-write a chess program in a quantum programming language. If it is written in a smart way, then it can take advantage of the higher speed achievable by parallel instead of sequential calculation.

Quantum computers/ engines wont be faster than traditional cpu in chess. 

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.

( copy from someone' answer)

#25
The lockpicking is a nice analogy.
"a quantum computer can solve in linear time, problems for which a normal computer requires exponential time"
Chess is a such a problem that requires exponential time.
A chess engine does
look at all white moves one by one
    for each white move look at all black moves one by one
        for each black move look at all white moves one by one
                 and so on and so forth like 20 ply deep or more
if there are m possible moves per ply, then looking p ply deep requires m^p calculations, clearly exponential.

A quantum computer offers the possibility to perform those calculations in parallel instead of sequential.

So all that is needed is some smart programmer who translates a chess program like Stockfish which has open source code into a quantum programming language like SQL in a clever way that takes advantage of the parallel processing possibility with appropriate qubit registers and then run it on a quantum computer like the one IBM makes available for cloud computing.

 

Only specific cases? Don't they  figure out the possibilities faster? What are these cases (if there are some specific)

Oh I didn't know this. Where can i learn the basics of relativity? Any sources

There are principles in  chess which are always true. To give an example king and rook always  beat a lone king unless the position is already in stalemate. These principles did not change when when chess engines became stronger over time.

There are also "situations"  which very usually ring true.  These "situations" would be called "principles" except they are very specific.  For example a very strong human chess player knows

when the sacrifice of a knight with Nxg7 vs the 0-0 position should work or should not work.

These "principles/situations" remain the same if a human is playing or a chess engine is playing. 

There are many thousands of such "principles" A very strong human knows many.

In correspondence chess over many years and using the best chess engines certain openings have been analyzed to a draw. Example the Ruy Lopez-- 1. e4  e5  2, Nf3  Nc6  3. Bb5. Another example is 1. e4  e5  2. Nf3   Nf6.   So fewer and fewer strong correspondence players will play say the Ruy Lopez as White

The use of chess engines has over time-leveled the playing field in top correspondence chess.

Quite a few correspondence players never lose and also play with no mistakes.

The era where one  player dominates all other players  in correspondence chess is over. 

Am friends with several

 of the top correspondence players. One lamented to me the other day "another draw--another few rating points lost."

In the 30th World Correspondence Championship all players  were rated in the 2500s except one rated 2606. [he ended with all draws.,]  12 players ended with a bunch of draws and no loses.

The very top players know it is not worth their efforts to play in some top tournaments. Clearly

perfect play with no errors has affected top levels of correspondence chess

Engines have changed a lot. A few examples:
Endgames: In the pre engine era, it was unsure if KQg vs. KQ was won or not.
Middle game: AlphaZero showed that the opportunistic h2-h4-h5-h6 is good.
Openings: AlphaZero has re-invented Berlin and Grünfeld with no prior knowledge. Dutch, Chigorin, King's Gambit are found unsound.

There is plenty of material on the internet. Much of it very bad, of course. Don Lincoln of Fermilab makes lots of science popularization videos, and usually gets it right.

The bolded statement above is flat out false .

What is true is that often compiled and interpreted languages run in their own "sandbox", and so you can easily port applications to lots of platforms and computers regardless of the processors' underlying instruction sets...but if you do this with quantum computers, creating the "sandbox" effectively removes all the speed benefit you were touting in the first place.

Your argument is kind of like saying you can win a 72 hour off road rally/race in the desert using a Formula one racecar.  Maybe you could , but after adding the offroad suspension, tires, changing out to regular gas, removing the front scoop, etc. your Formula One racecar is no better than the other entrants, really, and probably much worse.

How much do you actually know about processors and instruction sets, and how quantum computer instruction sets will differ?  Because if you are are some Ruby on Rails developer or something, you have no idea what you are talking about.

If you read this article, the person being interviewed has a very apt description of quantum computing's current state, likening it to the first plane flight at Kittyhawk...did it prove flight is possible?  Yes.  Did people pack their bags to fly across the Atlantic?  No.  Quantum computers have yet to achieve anything practical.

#32

The bolded statement above if flatout right and is one of the fundamentals of computer theory.
Any program can run on any computer.
To take full advantage of a certain hardware the programmer needs to be clever.
Quantum computing is not yet fully mature, but IBM already sells quantum cloud computing and there are quantum desktop computers for sale.

To get back to the lockpicking example:
Picking a lock:
for dial = 1 to p
    for position = 1 to m
          is lock open?

Chess:

for ply = 1 to 11797
    for move = 1 to m(ply)
           is position won?

So chess lends itself for quantum computing.

If one has access to a quantum computer e.g. from IBM and a quantum program that takes advantage of the inherent speed advantage, then that player is likely to win TCEC or the ICCF World Championship.
 

- I don't know who is teaching you "computer theory", but you should get a refund.

- Your example is pretty funny since looping is one of the things quantum computers are *not* good at.  Quantum computers are good at matrix computations.  

- "is position won?" is a not a simple binary state to be checked, it requires cross checking against all previous results as you are calculating each new tablebase layer...something else that quantum computers are not particularly good at.  Certainly it is in no way comparable to "is lock open?"...

- To create constructs that allow for looping (or many other higher-level language functions) is inefficient for a quantum computer, and so loses the "inherent speed advantage"

- If a $5,000 IBM quantum computer in the cloud wins TCEC, I'm sure we'll all hear about it .

These are some of the people who should be really impressed with quantum computing in the near future:

- Your local weatherman

- Your linear algebra teacher

- The NSA agent reading your encrypted Whats App messages

- The microbiologist working on your next vaccine variant

This is obviously wrong.

In the lockpicking model, the calculation for dial positions Y does NOT depend on you already having the completed result of the calculation for dial positions X. They are order-independant, and can be calculated in parallel.

Not so for the chess example, where the calculation for ply Y depends on having already completed the calculation for ply X.

I might mention, just in passing, that my first job with room-sized mainframe computers was in 1975 (nearly 50 years ago), and that my most recent computer-related job was as a computer systems analyst at a secure military installation (the Tactics School).

So when I give an opinion on the capabilities of computers, I'm not just repeating what some guy on Youtube said.

Just sayin'.

#35

In chess, the calculation for 1 e4 c5 does NOT depend on you already having the completed result of the calculation for 1 e4 e5. They are order-independant, and can be calculated in parallel.
Most high performance chess engines use more than one processor, thus work in parallel. A quantum computer can push this further.

The calculation for ply Y depends on having already completed the calculation for ply X. That is right, but the calculation for possible move Z does not depend on having already completed the calculation for possible move T.

When I give an opinion on the capabilities of computers, I'm not just repeating what some guy on Youtube said either. I also had college education on computer architecture.

Just sayin'.

No you cant!

Average possible moves in chess is 30. For analysis at depth 30, 

If you just do parallel computing (brute forces), you need 30^30= 2x 10^40. (impossible with resources on earth) 

Average branching factor of stockfish search is <2, so Stockfish just need 2^30= 1 billion nodes.

Quantum computers are not gazillions  times more powerful than traditional computers. 

#37
Yes, you can!

https://www.nature.com/articles/d41586-020-03434-7 

The quantum computer solved in 200 seconds a problem that would take 2.5 billion years on a supercomputer. This is from 'Nature' not some blog.

Deep blue used 36 processors in parallel. A quantum computer say "Deep Q" of 128 qubit would be equivalent to 1000 billion processors.

The hardware exists and will become more performant and more affordable in years to come. You can already buy a quantum computer or buy cloud computing time on it from IBM, open source chess programs exist, quantum programming languages exist, the only missing is a programmer who reprograms the chess program in a quantum programming language that takes advantage of the inherent speed advantage.

Even if their claims are applicable on chess (although it is not true due to branching nature of chess) , you still need 10^20 times faster quantum computer to reach the depth 30 .

There is still massive difference between 10^40  vs 10^ 20 . 

except, chess and numberlocks aren't the same thing

It would/will be interesting  to see what a quantum computer can or cannot do regarding chess?

However regarding the forum question the very strong chess computers we have now and the very strong chess entities we have now have already greatly affected chess theory in several different ways. 

This affect at the very top will only continue--quantum computers or not.?

99% of current players are not aware of the several changes which have already happened. 

However these changes do not so much affect the practical players with a chess ability under grandmaster. 

So  the answer to the forum question is "No, quantum computers will have little affect on    chess theory for players with less than grandmaster skills."

Players and chess entities who/which are already grandmaster strength are already greatly affected regardless of what quantum computers can or cannot do or might do? 

Sesse used 48 processors 2 GHz Skylake-SP and 18 processors 2.2 GHz Broadwell-EP to reach 49,582,886 nodes per second.

A 128 qbit quantum computer is equivalent to 1000 billion processors and hence would go much deeper in the same time.
Hardware is commercially available e.g. from IBM
Quantum programming languages are available e.g. QCL or Silq
Open source chess engines are available e.g. Stockfish
A translation of an open source chess engine into a quantum programming language is not yet available (StoQfish ?)

Referring to the earlier analogy to airplanes quantum computing is past the 1903 Kitty Hawk stage and rather in the 1927 Pan Am stage.