{"id":"arxiv/2605.12675","url":"https://arxiv.org/abs/2605.12675","tags":["quant-ph"],"score":0,"title":"Answer Partitions and Oracle Access Determine Quantum Query Complexity","domain":"quant-ph","source":"arxiv","authors":["Karl Svozil"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-05-12","reactions":{}}