Answer Partitions and Oracle Access Determine Quantum Query Complexity
arXiv:2605.12675
Abstract
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 the standard Boolean point oracle fixed, we further show that balanced answer partitions with equal-sized cells can have different exact classical and quantum query complexities. A complete exact classification is given for all 35 balanced three-bit partitions, while the unresolved four-bit cases are reported explicitly as numerical candidates. These results separate the combinatorial specification of an answer from the oracle-dependent distinguishability that determines query complexity.
5 pages, mayor revision