How to verify the correctness of quantum computing when classical simulations of quantum superiority experiments take tens of thousands of years
Three countries have already demonstrated the superiority of quantum computing, and the classical simulations of these experiments are basically estimated to take more than 10,000 years. But how to verify the correctness of quantum computing, wait for 10,000 years? Of course not! So we need a classical method that can quickly verify the correctness of quantum computing.
Norman Yao
The paper writes that existing experimental demonstrations of the superiority of quantum computing have the limitation that verifying the correctness of quantum devices requires classical computation at an exponential cost. Their protocol relies on a class of cryptographic tools called trapdoor claw-free function (TCF). The protocol eliminates the need for an adaptive hardcore bit (a stringent encryption property), has essentially no overhead in quantum circuits, and makes no additional encryption assumptions.
First, they demonstrate how an idea from the Bell inequality test can achieve the same encryption purpose as the adaptive hardcore bit. Essentially, this interaction protocol is a variant of the CHSH game, where one player is replaced by a cryptographic structure. Usually, in CHSH, two quantum parties are required to produce an association that is not possible with classical devices. If class-space separation is enforced to exclude communication between the two parties, then correlation constitutes a proof of quantumness. In the examples in this paper, the class-space separation is replaced by the computational difficulty of the encryption problem. In particular, the quantum prover (prover) holds a quantum bit whose state depends on the cryptographic secret. From the point of view of Bell's theorem, the protocol can be considered as a "single-detector Bell test" - the encryption task produces the same single-quantum-bit state as the single-quantum-bit state produced by entangling a second quantum bit and measuring it with another detector. Just as in the CHSH game, quantum devices pass the verifier (verifier) test with about 85% probability, but classical devices succeed with at most 75% probability. This limited difference in the probability of success is what makes the quantum advantage a verifiable test.
The figure below shows the complete protocol. The protocol consists of three rounds of interaction between the prover and the verifier (one round is a challenge from the verifier, followed by the response from the prover).
The first round generates a multi-quantum bit superposition on two bit strings, which is cryptographically difficult to compute classically. The second round maps this superposition to the state of an auxiliary quantum bit, preserving enough information to ensure that the final single quantum bit state is also difficult to compute classically. The third round uses this single quantum bit as input to a CHSH-style measurement, allowing the prover to generate a data bit associated with the cryptographic secret in a way that is not possible in the classical case.
Schematic diagram of the interactive quantum superiority protocol
Second, by eliminating the need for an adaptive hardcore bit, they propose two cryptographic structures, the first based on the adjudicative Diffie-Hellman problem (DDH) and the second using the function fN(x) = x2modN, where N is the product of two prime numbers, which forms the backbone of the Rabin cryptosystem. On the one hand, DDH is attractive because the elliptic curve version of the problem is particularly difficult for classical computers. On the other hand, x2modN can be implemented more efficiently with a difficulty equivalent to factorization. The authors hope that these two structures will provide the basis for finding more TCFs with desirable properties (small key size and efficient quantum circuits).
They also propose two independent innovations: an inherent post-selection scheme for increasing the probability of a noisy device passing the test, and another approach that significantly reduces the overhead caused by the reversibility requirements of quantum circuits. The former allows quantum devices to trade a lower quantum fidelity for a proportional increase in overall runtime while still passing the cryptographic test. The latter is a measurement-based uncomputation scheme specific to the protocol structure that converts a classical circuit into a quantum circuit with essentially zero overhead.
They numerically analyze the effectiveness of this post-selection scheme for a specific TCF x2modN. To add redundancy to the output of the function, they mapped this TCF to the function (3ax)2mod(32aN) for the adjustable number a and simulated the circuit under a generic noise model.
For a=0, the circuit implements the original function x2modN, where a total circuit fidelity of about 0.83 is required to achieve quantum superiority without post-selection. As shown below, for a=0, the inherent redundancy in the TCFs makes their post-selection scheme change the superiority threshold to a fidelity of about 0.51. For a = 2, the circuit fidelity with F ≳ 0.1 remains above the quantum superiority threshold, while for a = 3, the required circuit fidelity drops to less than 1%. Performing the post-selection incurs an additional runtime cost, but only 4.7 times the overhead is already able to achieve quantum superiority at 10% of the overall circuit fidelity. Crucially, the runtime increase is mainly due to rerunning the quantum circuit and does not imply the need for longer experimental coherence times.
Performance of the post-selection scheme
Finally, with an eye on TCF x2modN, explicit quantum circuits for near-term quantum devices are provided. They show that verifiable tests of quantum dominance can be achieved with about 103 quantum bits and a gate depth of about 105. A specific implementation of x2modN optimized for a programmable Reedeburg quantum computing platform is then designed one by one. Natural physical interactions corresponding to the Reedeburg blocking mechanism allow for direct implementation of arbitrary phase rotations controlled by multiple quantum bits without the need to decompose such gates into generic two-quantum-bit operations. Access to such native gates immediately reduces the gate depth for achieving quantum dominance by an order of magnitude.
The basic phase circuit of x2modN is implemented. where n is the length of the input register and m = n + O(1) is the length of the output register. The circuit can be modified to reduce the number of gates and quantum bits.
Blueprint for implementing x2modN in Riedberg atoms. a. Schematic diagram of a 3D array of neutral atoms with Riedberg blocking interactions. b. Example: Riedberg atoms can be trapped in an array of optical tweezers. An atom in a Riedberg excited state (red) can change the energy level of a nearby atom (blue). d. Multi-quantum bit-controlled phase rotation via a sequence of π pulses between |0⟩↔|r⟩.
Reference：
[1]https://www.nature.com/articles/s41567-022-01643-7
