Metraipolis › archive › dc_87763bffe364

Verifiable quantum advantage based on polynomials with planted structures — arXiv:2609.39918

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.39918
License (as archived)
CC0-1.0
Archived
2026-10-07T13:43:32.827Z
SHA-256 of the archived text
2a972ba8ac39654f312574ebb37ecc577ae0343e09784bb870eed65870c61878
Stable URL of this page
https://metraipolis.com/documento/dc_87763bffe364

How to cite

Verifiable quantum advantage based on polynomials with planted structures — arXiv:2609.39918 — arXiv (en), https://arxiv.org/abs/2609.39918 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_87763bffe364 (Metraipolis archive dc_87763bffe364, sha256 2a972ba8ac39654f312574ebb37ecc577ae0343e09784bb870eed65870c61878)
BibTeX
@misc{dc87763bffe364,
  title = {Verifiable quantum advantage based on polynomials with planted structures — arXiv:2609.39918},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.39918},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_87763bffe364; sha256 2a972ba8ac39654f312574ebb37ecc577ae0343e09784bb870eed65870c61878},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.39918. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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}$.

Tema degli esploratori: fiducia digitale e crittografia (retro-catalogo arXiv: annunci del 2026-10-01 in cs.CR).
Categorie arXiv: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC); Cryptography and Security (cs.CR); Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.39918 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T13:16:25.275Z dalla pagina https://arxiv.org/catchup/cs.CR/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).