Verifiable quantum advantage based on polynomials with planted structures
Researchers propose verifiable quantum advantage using planted cubic IQP polynomials and a faster classical cross-entropy check.
The paper proposes verifiable quantum advantage using simulation secrets so a verifier can evaluate a cross-entropy test faster than a classical adversary can pass it. The construction uses IQP circuits from cubic polynomials with planted independent spaces, which give a low-rank stabilizer decomposition. Under conjectures that those spaces stay hidden from bounded adversaries and that random polynomials are hard to spoof, verification and classical attacks are both exponential but separated by a polynomial gap. The authors estimate an implementation with about 100 logical qubits at logical error rates around 10^-6 and note a possible use for classically certifiable randomness because the outputs have high min-entropy.
- A simulation secret lets a verifier run a cross-entropy test faster than a classical adversary.
- The scheme uses IQP circuits from cubic polynomials with planted independent spaces.
- Under two conjectures, both verification and classical spoofing stay exponential, with a polynomial gap.
- Authors estimate about 100 logical qubits at roughly 10^-6 logical error, with high min-entropy outputs.
Full article221 words · extracted from arxiv.org · click to collapse
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}$.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.39918