Answer Partitions and Oracle Access Determine Quantum Query Complexity
Source: arxiv.org/abs/2605.12675
An answer partition specifies which oracle instances share an output, while query complexity also depends on how those instances are accessed. We formulate exact one-query answer-partition resolution as block discrimination of a unitary oracle family. Applied to Deutsch's problem with a controlled response unitary V, the criterion shows that one query suffices if and only if -1 is an eigenvalue of V; cyclic addition in odd response dimension therefore raises the exact quantum cost to two queries, matching the classical cost while preserving the same computational-basis point values. Holding…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.12675
curl -X POST /api/v1/records/arxiv/2605.12675/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.12675/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'