Classical Computers Have a Hard Time Understanding 'Quantum Accents'

Estimated reading time: 5 minutes

Vazirani's team referred to an analogy between the output of the random quantum circuit and a string of random syllables in English: even if the syllables don't form coherent sentences or words, they will still possess an English "accent" and will be recognizably different from Greek or Sanskrit.

They showed that producing a random output with a "quantum accent" is indeed hard for a classical computer through a technical complexity theoretic construct called "worst-to-average-case reduction."

The next step was to verify that a quantum device was actually speaking with a quantum accent. This relies on the Goldilocks principle -- a 50-qubit machine is large enough to be powerful, but small enough to be simulated by a classical supercomputer. If it's possible to verify that a 50-qubit machine speaks with a quantum accent, then that would provide strong evidence that a 100-qubit machine, which would be prohibitively hard to simulate classically, would do so, as well.

But even if a classical supercomputer were programmed to speak with a quantum accent, would it be able to recognize a native speaker? The only way to verify the output of the speaker is by a statistical test, said the Berkeley researchers. Google researchers are proposing to measure the degree of matching by a metric called "cross-entropy difference." A cross-entropy score of 1 would be an ideal match.

The alleged quantum device may be regarded as behaving like an ideal quantum circuit with random noise added. Fefferman and Bouland say the cross-entropy score will certify the authenticity of the quantum accent provided the noise always adds entropy to the output. This is not always the case - for example if the noise process preferentially erases 0s over 1s, it can actually reduce the entropy.

"If Google's random circuits are generated by a process that allows such erasures, then the cross-entropy would not be a valid measure of quantum supremacy," said Bouland. "That's partly why it will be very important for Google to pin down how its device deviates from a real random quantum circuit."

These results are an echo of work that Vazirani did in 1993 with his student Ethan Bernstein when they presented the first formal evidence that quantum computers would exponentially speed up certain computations. This opened the door to quantum algorithms by showing that quantum computers violate the Extended Church-Turing thesis, a foundational principle in computer science.

Peter Shor of Bell Labs took their work one step further by showing that a very important practical problem, integer factorization, could be exponentially sped up by a quantum computer.

"This sequence provides a template for the race to build working quantum computers," said Vazirani. "Quantum supremacy is an experimental violation of the Extended Church-Turing thesis. Once that is achieved, the next challenge will be to design quantum computers that can solve practically useful problems."

• < Previous Page