Verifiable quantum advantage using special polynomials in circuits
Verifiable quantum advantage based on polynomials with planted structures
Computational ComplexityCryptography and SecurityData Structures and Algorithms
Summary
Showing clear proof that quantum computers can outperform classical ones is a big challenge. This paper suggests a way to do that by hiding secret structures in certain mathematical polynomials used in quantum circuits. These secrets let a verifier quickly check if a quantum computer’s output is genuine, while classical computers would struggle to fake it. The authors believe this method could help create trustworthy quantum-generated randomness and could be tested with around 100 qubits.
What this means in practice
- •For quantum cryptography teams: Produce classically verifiable random numbers from quantum circuits with hidden polynomial structures to improve security guarantees.
- •For quantum hardware developers: Design quantum processors with about 100 logical qubits and low error rates to implement verifiable quantum advantage schemes based on planted polynomials.
A theory result. No direct application yet.
Authors
Markus Bläser, Michael Gullans, Dominik Hangleiter, Yuxuan Liu, Youming Qiao
Abstract
A central question in the theory of quantum advantage is whether there are quantum advantage protocols with similar resource requirements as random circuit sampling that are also verifiable just from the classical outputs of the quantum computation. Here, we develop the idea of simulation secrets for verifiable advantage. A verifier can use a simulation secret to evaluate a cross-entropy test faster than it would take a classical adversary to pass the test. We instantiate this idea using IQP circuits described by cubic polynomials with planted independent spaces. These correspond to the largest independent set in the orbit of a polynomial under the general linear group and yield a low-rank stabilizer decomposition of the corresponding state. We conjecture that large independent spaces are invisible to a computationally bounded adversary, and therefore they cannot exploit them to pass the protocol. A second conjecture regards the fine-grained complexity of producing samples that pass the cross-entropy test for uniformly random polynomials. Under these conjectures, our scheme results in a polynomial gap between the verification time and the time a classical adversary would need to pass the protocol---both are exponential. It has a potential application to generating classically certifiable randomness, since the output distributions have high min-entropy. We estimate that the planted polynomial scheme is implementable using 100 logical qubits at logical error rates around $10^{-6}$.