Verifiable quantum advantage based on polynomials with planted structures

Markus Bläser, Michael Gullans, Dominik Hangleiter, Yuxuan Liu, Youming Qiao

arXivarxiv/2609.39918Sep 30, 2026quant-phscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2609.39918
curl -X POST /api/v1/records/arxiv/2609.39918/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.39918/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'