Quantum Computing

[Jouni]

Despite high hopes for quantum computing, significant progress in hardware, and optimism about future applications, a 2023 Nature spotlight article summarized current quantum computers as being "For now, [good for] absolutely nothing".

[syzygy]

I wonder what Quantum Computing would mean for chess.

Deeper search - link:

"...we find examples of trees for which the classical algorithm requires time exponential in 𝑛, but for which the quantum algorithm succeeds in polynomial time."

I would like to think of a quantum computer as a nondeterministic computer that can make the right choice every time, but it seems nondeterministic computer and quantum computers (or rather NTMs and QTMs) are probably incomparable in the sense that each can efficiently solve some problems that the other cannot solve efficiently.

Still, I suspect that alpha-beta running on a quantum computer would at best be comparable to alpha-beta-with-perfect-move-ordering on a regular comnputer. Current chess engines already come very close to that.

[towforce]

I wonder what Quantum Computing would mean for chess.

Deeper search - link:

"...we find examples of trees for which the classical algorithm requires time exponential in 𝑛, but for which the quantum algorithm succeeds in polynomial time."

I would like to think of a quantum computer as a nondeterministic computer that can make the right choice every time, but it seems nondeterministic computer and quantum computers (or rather NTMs and QTMs) are probably incomparable in the sense that each can efficiently solve some problems that the other cannot solve efficiently.

Still, I suspect that alpha-beta running on a quantum computer would at best be comparable to alpha-beta-with-perfect-move-ordering on a regular computer. Current chess engines already come very close to that.

Why can't a quantum computer have the same quality of move ordering as a normal computer?

[JohnWoe]

Didn't google make some "breakthrough" lately. Their quantum computer made some 10e20 calculations in second. Nobody bothered going into details what kind of BS calculations those were. Why I'm not bothering with news anymore.

I should have stayed in academia. I could tour the world talking nonsense and get paid big bucks doing so.

[towforce]

Didn't google make some "breakthrough" lately. Their quantum computer made some 10e20 calculations in second. Nobody bothered going into details what kind of BS calculations those were. Why I'm not bothering with news anymore.

I should have stayed in academia. I could tour the world talking nonsense and get paid big bucks doing so.

I linked Google's Willow announcement - link.

Their new Willow chip is a breakthrough because it's so good at error correction. However, the example on which it can outperform normal computers is contrived: it can't do anything useful like crack encryption yet.

[syzygy]

I wonder what Quantum Computing would mean for chess.

Deeper search - link:

"...we find examples of trees for which the classical algorithm requires time exponential in 𝑛, but for which the quantum algorithm succeeds in polynomial time."

I would like to think of a quantum computer as a nondeterministic computer that can make the right choice every time, but it seems nondeterministic computer and quantum computers (or rather NTMs and QTMs) are probably incomparable in the sense that each can efficiently solve some problems that the other cannot solve efficiently.

Still, I suspect that alpha-beta running on a quantum computer would at best be comparable to alpha-beta-with-perfect-move-ordering on a regular computer. Current chess engines already come very close to that.

Why can't a quantum computer have the same quality of move ordering as a normal computer?

I did not say it can't?

A nondeterministic computer running alpha-beta would be as fast as a regular computer running alpha-beta with perfect move ordering. It would not be a big improvement over current engines.

Of course AlphaZero and Lc0 have shown that non-alpha-beta approaches are possible, too. So who knows. But I don't think that any of our current algorithms for playing chess could be made to run significantly faster on a quantum computer.

[Chris Formula]

best to run some testing.
https://quantum.ibm.com/services/resources
https://www.youtube.com/watch?v=4MpLnAo2974

[Werewolf]

I wonder if quantum could do a pure brute force search with no mini-max?

[smatovic]

I wonder if quantum could do a pure brute force search with no mini-max?

Mini-Max is the brute force method for computing chess, the whole game tree to the end, with win/draw/loss.

Thus the question would be, how to implement Mini-Max on Quantum Computers based on quantum gates, qubits?

My own estimation says you will need qubits in the range of thousands to implement Mini-Max for TicTacToe, and in the range of billions for the game of Chess.

There are also qudits, which can store decimals, theoretical there are also quinfs, to compute with infinity, a hyper-turing-machine, as mentioned, in theory.

There is also another approach, the von Neumann architecture for quantum computers, to separate memory and computation.

ATM I see no practical value of quantum computers for chess, it is more likely that we will use qubits for inferring neural networks first.

--
Srdja

[towforce]

Good video by a clever German lady on how quantum computer companies are funded (specialist companies, as opposed to IBM and Google, who do quantum computing as research projects):

* their revenue is too lower to cover their costs

* most of the revenue they do get is in the form of grants from governments

* they are initially funded by venture capital

* in order to get their money back, the venture capitalists require these companies to go public

* these companies cannot go public, because in order to list on a stock exchange, they would have to do due diligence

* in order to avoid due diligence, they're listed via SPACs (Special Purpose Acquisition Company)

All explained in the video: