Tight Quantum Lower Bound for k-Distinctness
In this paper, we introduce a new quantum query lower bound framework. It is inspired by Zhandry's compressed oracle technique, but it also subsumes the polynomial method as a special case. Compared to Zhandry's technique, our approach has two key differences. First, we do not use any oracles (except for the standard input oracle), and define ``knowledge'' directly through the expansion of the state of the algorithm in the Fourier basis. Second, we allow arbitrary probability distributions of inputs. We show how this framework behaves on the problem of finding equal elements in the input…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.05133
curl -X POST /api/v1/records/arxiv/2604.05133/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.05133/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'