Verifiable quantum advantage based on polynomials with planted structures
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.
Related
- Verifiable Quantum Advantage and Computation via Quantum Circuit Obfuscation
- Verifiable quantum advantage in extremely low depth
- Towards verifiable quantum advantage with random circuits: Observables that survive concentration
- Planted Cliques and Quantum Symmetry-Adapted Measurements
- Verifiable Sampling for Delegated Generative Quantum Machine Learning
BibTeX
@misc{blaser2026verifiable,
title = {{Verifiable quantum advantage based on polynomials with planted structures}},
author = {Markus Bläser and Michael Gullans and Dominik Hangleiter and Yuxuan Liu and Youming Qiao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.39918},
eprint = {2609.39918},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.39918},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Verifiable quantum advantage based on polynomials with planted structures
AU - Markus Bläser
AU - Michael Gullans
AU - Dominik Hangleiter
AU - Yuxuan Liu
AU - Youming Qiao
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.39918
UR - https://arxiv.org/abs/2609.39918
AB - 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.
ER -