arXiv:2610.34079v1 Announce Type: new Abstract: We give a direct analytic proof that every total Boolean function computable exactly with at most two quantum queries depends on at most six input variables. This bound is sharp. A previous derivation relied on a numerical classification of Boolean functions on at most four variables; to the best of our knowledge, ours is the first unconditional proof. The main difficulty beyond the one-query case is that query-path vectors need not be mutually orthogonal, so interference prevents the scalar weight-counting argument from applying. We overcome this difficulty by establishing a rigid support-and-branch decomposition: after the coordinates in the first-query support are fixed, the second query induces a family of exact one-query branches.
Quantum Research · 2026-10-27
Two exact quantum queries use at most six variables
arXiv:2610.34079v1 Announce Type: new Abstract: We give a direct analytic proof that every total Boolean function computable exactly with at most two quantum queries depends on at most six input variables. This bound is sharp. A previous derivation relied on a numerical classification of Boolean functions on at most four variables; to the best of our knowledge, ours is the first unconditional proof.
Source and attribution
Original source: arXiv Quantum ↗
This is an attributed editorial digest. For the complete study and original reporting, follow the source link.
Reader feedback
0 likes · 0 dislikes