Recent experiments have performed quantum computations that seem to be infeasible to reproduce with even the world’s most powerful supercomputers. However, a subtlety of those experiments is that the output of the computations is also computationally hard to verify—for the largest computations, it is not possible to directly show that the results are actually correct. An exciting new research direction is to design tests of quantum computational advantage that are efficiently verifiable by classical computers, while still remaining hard to spoof. 

One of the most promising strategies for moving forward in this direction in to use cryptography to construct protocols with desirable properties. In addition to being hard to spoof and easy to verify, a primary drive is to create protocols which have the smallest possible quantum circuits, and are as tolerant as possible to noise, such that they can be implemented on near-term quantum devices. We have developed a new protocol for the demonstration of quantum advantage [1], whose classical hardness to spoof is provably equivalent to integer factorization, but uses much smaller quantum circuits than Shor’s algorithm. In work with colleagues at the University of Maryland, we have performed a first small-scale demonstration of that protocol [2], using mid-circuit measurements to implement a quantum interactive proof in practice. We also are actively working on optimizing the quantum circuits for implementing these protocols. The core operation behind our protocol is the implementation of the function f(x) = x^2 mod N over a quantum superposition of values x; in optimizing this we have discovered a new, faster method for performing multiplication of quantum superpositions of integers. This new algorithm advances the implementation not only of proofs of quantumness but also of other quantum algorithms such as Shor’s factorization algorithm.

References

1. Kahanamoku-Meyer, G.D., Choi, S., Vazirani, U.V. et al. Classically verifiable quantum advantage from a computational Bell test. Nat. Phys. 18, 918–924 (2022). https://doi.org/10.1038/s41567-022-01643-7
2. Zhu, D., Kahanamoku-Meyer, G.D., Lewis, L. et al. Interactive Proofs of Quantumness via Mid-Circuit Measurements. (2021). https://arxiv.org/pdf/2112.05156.pdf