Quantum Query Complexity Beyond the Worst Case
Smoothed analysis is a central framework in classical algorithms for explaining the performance of algorithms beyond the worst case, often explaining why algorithms perform well in practice. We initiate a systematic study of its quantum counterpart and show the following results. $(1)$ We show that there is a total function whose smoothed quantum query complexity is exponentially smaller than its classical query complexity. $(2)$ We give near-tight characterizations of smoothed randomized and quantum query complexities for symmetric Boolean functions, unifying the worst-case complexity…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.35580
curl -X POST /api/v1/records/arxiv/2609.35580/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.35580/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'