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.
Related
- Optimal Quantum Junta Testing without Inverse Queries
- Self-similar swirl between contracting porous walls: the GD1998 exact Navier-Stokes solution revisited in the similarity variables of the OpenAI 2026 forced blow-up construction
- Making the most of leftovers: Improved privacy amplification for quantum key distribution
- On the Structure of Quantum Finite-Level Systems: Decoherence-Free Subsystems, Quantum Nondemolition Variables, and Back-Action-Evading Measurements
- Quantum steering in networks: Measurement-device-independent detection, continuous variables, and practical Gaussian schemes
BibTeX
@misc{li2026exact,
title = {{Two exact quantum queries use at most six variables}},
author = {Yaqiao Li},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.34079},
eprint = {2610.34079},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.34079},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Two exact quantum queries use at most six variables
AU - Yaqiao Li
PY - 2026
DA - 2026/10/25
PB - arXiv
DO - 10.48550/arxiv.2610.34079
UR - https://arxiv.org/abs/2610.34079
AB - 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.
ER -