Two exact quantum queries use at most six variables

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. This structural description may be of independent interest.

How many input variables can a total Boolean function depend on if it is computable exactly with two quantum queries? This paper gives a direct analytic proof that the maximum is $J_{\mathrm E}(2)=6$. The six-variable lower bound was already known. A previous characterization implied the same upper bound but was conditional on numerical classification results for functions on at most four variables; the proof here removes that numerical premise. The argument uses the structure of exact two-query states rather than only the polynomial-method bound $\deg(F)\leq4$. Let $S$ denote the physical coordinates with nonzero first-query weight. Applying the second oracle again to the exactness identity shows that $\deg(x_jF)\leq3$ for every $j\in S$. Consequently, if $F$ has at least five relevant variables, then $|S|\leq4$. Fixing $S$ leaves exact one-query branches, each computing a constant, a signed literal, or a signed two-variable parity. Orthogonality between branches with different relevant-coordinate sets implies that at most two nonconstant branch types occur. If two occur, their assignment cells are complementary sets specified by a literal or two-variable parity constraint. Factoring the projected states reduces each restriction to a normalized degree-one state, yielding the count $2+2+2=6$. The result concerns total Boolean functions and exact computation with at most two queries. No general higher-query bound of the conjectured form is established: the paper proposes $J_{\mathrm E}(k)=2^{k+1}-2$, matching known constructions, while whether three exact queries imply at most $14$ relevant variables remains open.