Computer theorists show the way forward to verify that the classic quantum beats

Quantum supremacy is the term that describes the ability of a quantum computer to solve a computational task that would be extremely difficult for any conventional algorithm. It is considered a crucial step in quantum computing, but as the very nature of quantum activity defies any traditional corroboration, parallel efforts have been made to find a way to prove that quantum supremacy has been performed.

Researchers at the University of California at Berkeley have just contributed to a leading-edge concrete proposal, known as Random Circuit Sampling (RCS), a qualified seal of approval with theoretical proof of weight complexity. Random circuit sampling is the technique put forth by Google to prove whether or not it has achieved quantum supremacy with a 72 qubit chip called Bristlecone, unveiled earlier this year.

Berkeley University's computer theorists published their proof of RCS as a verification method in an article published on Monday, October 29 in the newspaper Physical Nature.

"The need for strong evidence in favor of quantum supremacy is underestimated, but it is important to pin it down," said the study's lead researcher, Umesh Vazirani, professor Roger A. Strauch of Electrical and Electrical Engineering. Computer Science at the University of Berkeley. "In addition to being a milestone on the path to useful quantum computers, quantum supremacy is a new type of physics experiment designed to test quantum mechanics in a new regime." The fundamental question to which a such an experiment must answer is: what confidence can we have the observed behavior is really quantum and could not have been reproduced by conventional means.That is what our results address . "

The other researchers on this paper are Adam Bouland and Bill Fefferman, both postdoctoral fellows, and Chinmay Nirkhe, Ph.D. student, all in Vazirani's theoretical computer science research group.

The investment in the quantum is heating up

The document comes amidst accelerated activity among governments, universities, and industry in quantum information science. Congress reviews National Quantum Initiative Act, and last month, US Department of Energy and National Science Foundation announced nearly $ 250 million in grants to support quantum science and technology research .

At the same time, the national laboratory Lawrence Berkeley and UC Berkeley announced the creation of Berkeley Quantum, a partnership designed to accelerate and develop innovation in the field of quantum computing.

The stakes are high, as international competition in the field of quantum research intensifies and the need for more and more complex calculations increases. With real quantum computing, problems that can not be solved even for the fastest supercomputers to date could be relatively effective. This would change the game in cryptography, in simulations of molecular and chemical interactions and in machine learning.

Quantum computers are not confined by the traditional 0s and 1s of the bits of a traditional computer. Instead, quantum bits, or qubits, can encode 0s, 1s, and any quantum superposition of both to create multiple states simultaneously.

When Google unveiled Bristlecone, he stated that the empirical proof of his quantum supremacy would come from random sampling of circuits, a technique in which the device would use random settings to behave like a random quantum circuit. To be convincing, it would also require strong evidence that there is no conventional algorithm running on a conventional computer and capable of simulating a random quantum circuit, at least within a reasonable time.

Detect quantum accents

The Vazirani team evoked an analogy between the output of the random quantum circuit and a string of random syllables in English: even though syllables do not form coherent sentences or words, they still have an English "accent" and are recognizable by their difference from Greek or Sanskrit.

They showed that it is indeed difficult for a conventional computer to produce a random output with a "quantum emphasis" thanks to a theoretical concept of technical complexity called "worst-case reduction".

The next step was to check that a quantum device actually spoke with a quantum accent. This is based on the Goldilocks principle: a 50-qubit machine is big enough to be powerful, but small enough to be simulated by a conventional supercomputer. If it's possible to check that a 50-qubit machine speaks with a quantum accent, this would provide solid evidence that a 100-qubit machine would make it extremely difficult to simulate classic way, would do it too.

But even if a classical supercomputer was programmed to speak with a quantum accent, would it be able to recognize a native speaker? Berkeley researchers have indicated that the only way to check the speaker's output is to do a statistical test. Google researchers propose to measure the degree of matching with the help of a metric called "cross entropy difference". A cross entropy score of 1 would be an ideal match.

The presumed quantum device can be thought of as behaving like an ideal quantum circuit to which random noise has been added. Fefferman and Bouland claim that the cross entropy score will certify the authenticity of the quantum emphasis, provided that the noise always adds entropy to the output. This is not always the case – for example, if the noise process preferably clears the 0's out of 1, it can actually reduce the entropy.

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

These results echo the work that Vazirani did in 1993 with his student Ethan Bernstein, opening the door to quantum algorithms by presenting accelerations on the part of quantum computers violating a fundamental principle of computer science called the Extended Church-Turing thesis. .

Peter Shor of Bell Labs goes even further by showing that a very important problem, integer factorization, could be exponentially accelerated by a quantum computer.

"This sequence provides a model for the race to build functional quantum computers," Vazirani said. "Quantum supremacy is an experimental violation of the Thesis of the Enlarged-Turing Church, and once that is achieved, the next challenge will be to design quantum computers that can solve practical problems."

Explore further:
First proof of the benefit of the quantum computer

More information:
Adam Bouland et al. On complexity and verification of quantum random circuit sampling, Physical Nature (2018). DOI: 10.1038 / s41567-018-0318-2