arXiv:2609.39918
Verifiable quantum advantage based on polynomials with planted structures
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}$.
AI Summary
Can sampling-based quantum advantage be verified from classical outputs without verification costing as much as classical spoofing? This paper proposes “simulation secrets”: hidden circuit structure that accelerates probability evaluation for XEB verification. Its construction uses cubic Boolean-polynomial IQP circuits with a planted $h$-dimensional independent space, on which the polynomial restricts to degree at most two, hidden by a random invertible linear transformation. Knowing the space permits exact amplitude computation in $O(n^3 2^{n-h})$ time and polynomial space, by summing quadratic-polynomial gaps over complementary variables. Under two fine-grained conjectures—sub-$2^n$ indistinguishability of planted and uniform polynomials for $h\le(1/2-\epsilon)n$, and polynomial-space hardness of achieving XEB at time below $2^{\kappa n}$ for some $\kappa>1/2$—verification takes $\widetilde O(2^{cn})$ while classical spoofing requires $\Omega(2^{\kappa n})$, with $1/2<c<\kappa$. The average ideal XEB is $2+o(1)$; acceptance uses threshold $1$. Supporting results include NP-completeness of finding sufficiently large independent spaces, via slice-rank reductions, and a rank-profile attack recovering planted spaces in $\widetilde O(2^{n-h})$ time when $h\ge(1/2+\epsilon)n$. Moment calculations establish sample-efficient completeness and high output min-entropy. Both verification and the conjectured classical attack cost remain exponential; the gap is polynomial and assumes polynomial-space adversaries. Security rests on new conjectures, not worst-case hardness alone. Certified randomness is treated only through a conditional single-round Shannon-entropy bound without adversarial side information; full security is deferred. Estimated implementation requirements are around 100 logical qubits and logical error rates near $10^{-6}$.
We used generative AI of various generations for assistance in proving lemmas, checking technical correctness, and for feedback on earlier versions of the draft.
Central claim may not hold: The abstract's verification-versus-adversary time-gap claim omits the polynomial-space restriction required by its hardness conjecture and main theorem. The estimate of implementation with 100 logical qubits at logical error rates around 10^-6 is not supported by a resource or noise analysis connecting those parameters to successful XEB verification.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 44 pages, 1 figure. Comments welcome