⚛️ quantum physics

Two exact quantum queries use at most six variables

This paper provides the first unconditional analytic proof that every total Boolean function computable exactly with at most two quantum queries depends on no more than six input variables, a sharp bound established by overcoming interference challenges through a novel rigid support-and-branch decomposition.

Original authors: Yaqiao Li

Published 2026-10-27

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Yaqiao Li

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the realm of computing, there is a fundamental question about how much information a machine needs to solve a problem. Imagine a black box that holds a secret rule for turning a series of switches on and off into a final answer. To find out what that rule is, a computer must peek inside the box, checking the switches one by one. In the world of classical computers, checking these switches is a straightforward, step-by-step process. However, quantum computers operate on a different set of physical laws, allowing them to explore many possibilities at once. This ability, known as superposition, means a quantum computer can sometimes figure out the answer by asking far fewer questions than a classical machine ever could. The field of quantum query complexity studies exactly how many of these questions are necessary to solve a problem with absolute certainty, leaving no room for error.

For decades, researchers have known that if a quantum computer is allowed just one question, it can solve problems involving only two switches. The mystery lay in what happens when the computer is allowed a second question. Previous attempts to answer this relied on massive computer simulations that checked every possible combination of four switches. These simulations suggested that even with two questions, a quantum computer could not possibly solve a problem involving more than six switches. However, because these results depended on numerical calculations rather than a logical proof, a gap remained in the scientific understanding. It was possible, in theory, that a clever, undiscovered algorithm could break this limit.

A new study by Yaqiao Li closes this gap with a direct, logical proof that confirms the six-switch limit is absolute. The researcher demonstrated that any problem that can be solved exactly with two quantum questions must depend on no more than six input variables. This finding is not just a number; it reveals a rigid structural constraint on how quantum information flows. The proof works by showing that if a problem required seven or more variables, the quantum computer would be forced into a logical contradiction. Specifically, the first question would have to focus on a small group of switches, and the second question would have to branch out to handle the rest. The mathematics shows that this branching structure simply cannot accommodate more than six variables without breaking the rules of quantum mechanics.

The paper also clarifies why this proof was so difficult to find. In a single-question scenario, the paths a quantum computer takes are distinct and do not interfere with one another, making the math relatively simple. But with two questions, these paths can overlap and interfere, creating a complex web where the usual counting methods fail. Li overcame this by developing a new way to visualize the process, breaking the algorithm down into a "support" phase where the first question is asked, followed by a "branching" phase where the second question is asked based on the first result. This decomposition revealed that the interference patterns required to handle a seventh variable would destroy the certainty of the answer.

The result is a sharp, definitive boundary. The study confirms that the maximum number of variables for a two-question quantum algorithm is exactly six, matching a known lower bound where a specific six-variable problem was already proven to require two questions. This work removes the reliance on computer simulations and replaces them with a clear, analytical argument. It suggests that as we increase the number of allowed questions, the number of solvable variables grows in a predictable, exponential pattern, though the exact limit for three questions remains an open puzzle. By mapping the precise architecture of these quantum algorithms, the research provides a deeper understanding of the fundamental limits of quantum computation, showing that even with the power of superposition, there are hard walls that cannot be crossed.

Technical Summary: Two Exact Quantum Queries Use at Most Six Variables

Problem Statement
The paper addresses the exact quantum query complexity of total Boolean functions. Let $F: \{+1, -1\}^n \to \{+1, -1\}$ be a total Boolean function. The exact quantum query complexity, denoted $QE(F)$ , is the minimum number of oracle queries required by a quantum algorithm to output $F(x)$ with probability one for every input $x$ . The central question is to determine the maximum number of relevant input variables, $rv(F)$, that a function can depend on given a bound on its query complexity. Specifically, the paper seeks to prove the bound $JE(2) \le 6$ , where $JE(k) = \max \{rv(F) : QE(F) \le k\}$ .

While the polynomial method establishes that $\deg(F) \le 2QE(F)$ , and subsequent bounds relate the number of relevant variables to the degree, these general bounds are insufficient to prove $JE(2) \le 6$ tightly. Previous work on the $k=2$ case relied on numerical classifications of Boolean functions on up to four variables using semidefinite programming (SDP) solvers. A significant gap remained: an unconditional, analytic proof that does not depend on the correctness of numerical SDP results.

Methodology
The author provides a direct analytic proof using a "rigid support-and-branch decomposition." The proof proceeds by contradiction, assuming a function $F$ exists with $QE(F) \le 2$ and $rv(F) \ge 7$ . The argument is structured in two main steps:

Bounding the First-Query Support:
The author analyzes the structure of a two-query algorithm in the direct form $|\phi_2(x)\rangle = O^P_x O^Q_x |\phi\rangle$ , where $O^P_x$ and $O^Q_x$ are phase oracles acting on orthogonal decompositions of the Hilbert space. They define the "first-query support" $S$ as the set of physical coordinates $j$ for which the query-path weight $q_j = \|Q_j|\phi\rangle\|^2$ is positive.
Using a degree-reduction argument, they show that for any coordinate $j \in S$ , the degree of the toggled function $x_j F(x)$ is at most 3. This leads to the conclusion that if $rv(F) \ge 5$ , the size of the first-query support is bounded by $|S| \le 4$ . Consequently, if $rv(F) \ge 7$ , there must be at least three relevant coordinates lying outside the first-query support ( $Z = \text{Rel}(F) \setminus S$ , with $|Z| \ge 3$ ).
Structural Analysis of One-Query Branches:
The author fixes the assignment of the coordinates in $S$ to create "branches" of the algorithm. For a fixed assignment $\epsilon$ to $S$ , the remaining algorithm acts as an exact one-query algorithm on the remaining variables $y$ .
- Branch Types: Each branch computes a restricted function $F_\epsilon(y)$ . By Lemma 3.1, any exact one-query function depends on at most two variables. The set of these variables is called the "type" $T_\epsilon$ .
- Orthogonality Constraints: A critical difficulty in the two-query case is that query-path vectors need not be mutually orthogonal, preventing simple scalar weight-counting arguments. The author overcomes this by establishing that if two branches have different types ( $T_\epsilon \neq T_{\epsilon'}$ ), their corresponding final states are orthogonal for all inputs.
- Cell Decomposition: The author defines "type cells" $C_T = \{\epsilon : T_\epsilon = T\}$ . They prove that any occurring nonconstant type must have a cell of density at least $1/2$ in the space of assignments to $S$ . Furthermore, if two distinct nonconstant types occur, their cells must be complementary "short halfcubes" (sets defined by a single linear constraint or a parity of two variables).
- Degree Reduction: By projecting the state onto the subspaces corresponding to these cells, the author shows that the function restricted to each cell can be computed by an exact one-query algorithm on the full cube of the remaining variables. This implies the number of relevant variables in each branch is at most 2.

Key Contributions and Results

Theorem 1.1: The paper proves that $JE(2) \le 6$ . Combined with the known lower bound construction by Mukherjee and Maitra (which achieves $rv(F) = 6$ for $QE(F)=2$ ), this establishes $JE(2) = 6$ .
Unconditional Proof: Unlike previous derivations that relied on numerical SDP classifications for $n \le 4$ , this proof is purely analytic and unconditional.
Structural Decomposition: The paper introduces a "support-and-branch" decomposition for two-query algorithms. It demonstrates that fixing the first-query support reduces the problem to a family of exact one-query branches, where the interaction between branches is governed by strict orthogonality conditions on their types.
Handling Interference: The work explicitly addresses the difficulty that query-path vectors in two-query algorithms are not necessarily mutually orthogonal. It resolves this by showing that the interference is constrained such that distinct types force the support of the algorithm to decompose into complementary short halfcubes.

Significance and Claims
The paper claims to provide the first unconditional proof that every total Boolean function computable exactly with at most two quantum queries depends on at most six input variables. The author notes that the bound is sharp, as demonstrated by the function $G_2(x_1, \dots, x_6) = \frac{1+x_1x_2}{2}x_3x_4 + \frac{1-x_1x_2}{2}x_5x_6$ , which has exact query complexity 2 and 6 relevant variables.

The structural description of two-query algorithms—specifically the rigid decomposition into branches with complementary short halfcube supports—is presented as a result of independent interest. The author suggests that this structural understanding may be necessary for extending these results to higher query complexities, noting that the case $k=3$ (whether $QE(F) \le 3$ implies $rv(F) \le 14$ ) remains open. The paper concludes by proposing Conjecture 1.2: $JE(k) = 2^{k+1} - 2$ for all positive integers $k$ .

More like this