Did Google achieve “quantum supremacy” recently, building a computer that “performs a calculation in 200 seconds that would take a conventional computer 10,000 years” (Newsweek)?

If Google could truly use the strangeness of the quantum world to power calculations, it could break the encryption of all non-quantum computers with its relentless swiftness. However, rival IBM engineers dispute the claim, insisting that the feat is “one very specific quantum sampling procedure with no practical applications” (Science). Meanwhile, some suggest that China will launch a quantum surprise by getting ahead of both of them.

Querius wrote to me again, asking what I thought of it all.

But before we get started, here’s a characterization from a physics site of Google’s quantum supremacy as “pudding cup supremacy”:

Isn’t this just an example of creating a system whose output is intractable to calculate, and then “calculating” it by simply observing the output of the system?

It sounds similar to saying:

“If I spill this pudding cup on the floor, the exact pattern it will form is very chaotic, and intractable for any supercomputer to calculate. But I just invented a new special type of computer: this pudding cup. And I’m going to do the calculation by spilling it on the floor and observing the result. I have achieved pudding supremacy.”

which clearly is not impressive at all. In my example, I’m doing a “calculation” that’s intractable for any classical computer, but there’s no obvious way to extrapolate this method towards anything actually useful.

Physics Stack Exchange

Now to our discussion:

Querius: I was interested in knowing if you were aware of Google’s breakthrough on Quantum Computers. They achieved Quantum Supremacy by solving mathematical problem that took a classical computer 10,000 years in 200 seconds.

I noticed Mind Matters News has nothing on quantum computers but I know that it has some tidbits on quantum mechanics and free will. I wanted to know your thoughts on Quantum Computers, whether computers can generate truly random numbers and whether you thought true quantum computers are even possible.

Do you think quantum computers can truly capture quantum physics? If so, what are the implications for an artificial intelligence? 🙂

Eric Holloway: The quantum supremacy claim is pretty fascinating. IBM has a counter claim that the quantum computer has not done anything classically hard, but I don’t know enough to say who is right.

In my opinion the big question is whether human thought is a halting oracle. Everything a quantum computer does can be done with a deterministic Turing machine. So, if human thought is a halting oracle, then even quantum computing will not allow us to replicate human intelligence.

The only way we can possibly know if quantum computers generate truly random numbers is if the human mind is a halting oracle. This is because randomness is undecidable.

Finally, if Google has indeed achieved scalable quantum computation, this doesn’t really improve the state of AI and ML significantly.

Quantum computation can only provide a quadratic speedup over classical computation. However, the tough problems of AI and ML, such as optimizing neural networks and decision trees, and logic minimization, are NP-hard.

In practice, the large scale successful applications of ML use either deep neural networks or extreme gradient boosting (decision trees). To really improve the state of AI and ML, we need a form of computation that provides an exponential speedup, but there is no such candidate.

Scott Aaronson, who helped design the Google quantum supremacy test, claims there is no physical process that can provide such an exponential speedup, since there is no physical process (as far as we know) that can make P=NP.

Aaronson’s paper is here.

And once again, ultimately, since all AI is a form of Solmonoff induction, we really need a halting oracle to get true gains in the field.

So Google’s quantum supremacy claim is certainly fascinating and controversial, but even if true in the grandest and most charitable sense, it ultimately only amounts to an incremental and even inconsequential improvement in the state of AI and ML, due to the need for a halting oracle.

This also leads to my plug for “human in the loop” ML, which I call “imagination sampling.” If the human mind is a halting oracle, then by adding human feedback to ML we can achieve true gains in the field.

Querius: You write, “The only way we can possibly know if quantum computers generate truly random numbers is if the human mind is a halting oracle. This is because randomness is undecidable.”

I found this most interesting. Would you mind clarifying this point further?

Eric Holloway: My claim follows from the uncomputability of Kolmogorov complexity.

Kolmogorov complexity is the length of the shortest program that generates a bitstring. Random bitstrings are uncompressible, meaning that their shortest program is at least the same length as the original bitstring.

So, to know if a bitstring is random, we must compute its Kolmogorov complexity. Alternatively, if there were another way to know if a bitstring is random, we could use that knowledge to compute its Kolmogorov complexity.

Either way, knowing that a bitstring is random means computing its Kolmogorov complexity.

But, as I said, Kolmogorov complexity is not computable. There is a proof from contradiction:

If we could compute the Kolmogorov complexity for every bitstring with some magical program we’ll call MP, then we can run that program on every bitstring, and print out the first bitstring with Kolmogorov complexity larger than the size of MP. This would make the MP the generating program for the bitstring. And because the size of MP is less than the bitstring’s Kolmogorov complexity, this is a contradiction.

Therefore, we cannot compute the Kolmogorov complexity for every bitstring.

And because knowing that a bitstring is random requires computing Kolmogorov complexity, we cannot know that a bitstring is random.

Unless… !

… Unless we have a halting oracle.

With a halting oracle we can compute the Kolmogorov complexity for every bitstring by running just the halting programs until they all halt, and picking the shortest program that generates the bitstring. Thus, we will know which bitstrings are random.

Querius: Also, we often use quantum physics as a hand wavy way of explaining the soul and the mind.

What do you think is the relationship between the human mind and quantum physics? If a quantum computer was truly quantum, then how can deterministic machines run on it? It’s is incorrect for me to say the mind is deterministic, but then it seems wrong to say the mind is quantum because it’s not decidable. What’s been interesting to me is I don’t think the mind is a quantum computer either despite creationists and intelligent design proponents to reach for straws.

Eric Holloway: I don’t really think there is a link between quantum physics and the mind. The reason why people like quantum physics is because it introduces randomness into physics, supposedly allowing exotic things like free will to emerge from woolly-headed thinking.

But quantum physics could make things worse. Deterministic computation is impossible with quantum computers, whereas a deterministic computer can compute anything a quantum computer can compute. So, quantum computers are actually less powerful than good old-fashioned deterministic computers.

However, free will is neither random nor determined nor any combination of the two, so quantum physics adds nothing.

Free will is a third category that scientists have not discovered that is beyond randomness and determinism. So, your intuition is correct.

Note: My other recent dialogues with Querius are linked here, beginning with “Are monkeys with some human genes partly human?

Further reading on computers and the quantum world:

Quantum randomness gives nature free will: Whether or not quantum randomness explains how our brains work, it may help us create unbreakable encryption codes (Robert J. Marks)

More generally:

Things exist that are unknowable. A tutorial on Chaitin’s number (Robert J. Marks)

Futurism doesn’t learn from past experience. Technological success stories cannot be extrapolated into an indefinite future (Analysis)

Could one single machine invent everything? (Eric Holloway)

The mind can’ t be just a computer. Gödel demonstrated that fact and Turing tried to live with it (Analysis)

and

Human intelligence as a halting oracle (Eric Holloway)