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.

SHARE THIS ARTICLE LinkedIn X Facebook

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.

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

Sign in to like or dislike this research.

SHARE THIS ARTICLE LinkedIn X Facebook
← Back to research archive