Distributional Variants of the Aaronson-Ambainis Conjecture

Uma Girish, Kunal Mittal, Barak Nehoran, Ran Raz

arXivarxiv/2609.35327Sep 28, 2026quant-phscore 0

A longstanding conjecture in quantum complexity theory asserts that, under the uniform input distribution, quantum query algorithms can be polynomially simulated by classical query algorithms. More precisely, the acceptance probability of any quantum query algorithm can be approximated, on average over uniformly random inputs, by a classical query algorithm, with only polynomial query overhead. The conjecture is central to understanding whether exponential quantum advantages for decision problems necessarily rely on additional structure. We study analogues of this conjecture under other…

SourceJSON

Comments and reviews

No comments yet.

API

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