Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2407.06872

Quantum Query-Space Lower Bounds Using Branching Programs

Debajyoti Bera, Tharrmashastha Sapv

Published Jul 9, 2024• 0 citations
arXivHTMLPDF

Abstract

Branching programs are quite popular for studying time-space lower bounds. Bera et al. recently introduced the model of generalized quantum branching program aka. GQBP that generalized two earlier models of quantum branching programs. In this work we study a restricted version of GQBP with the motivation of proving bounds on the query-space requirement of quantum-query circuits. We show the first explicit query-space lower bound for our restricted version. We prove that the well-studied OR$_n$ decision problem, given a promise that at most one position of an $n$-sized Boolean array is a 1, satisfies the bound $Q^2 s = Ω(n^2)$, where $Q$ denotes the number of queries and $s$ denotes the width of the GQBP. We then generalize the problem to show that the same bound holds for deciding between two strings with a constant Hamming distance; this gives us query-space lower bounds on problems such as Parity and Majority. Our results produce an alternative proof of the $Ω(\sqrt{n})$-lower bound on the query complexity of any non-constant symmetric Boolean function.

DOI
10.48550/arxiv.2407.06872

Related papers

A Block-Sensitivity Lower Bound for Quantum Testing Hamming Distance

Marcos Villagra

The Gap-Hamming distance problem is the promise problem of deciding if the Hamming distance $h$ between two strings of length $n$ is greater than $a$ or less than $b$, where the gap $g=|a-b|\geq 1$ and $a$ and $b$ could depend on $n$. In this short note, we give a lower bound of $Ω( \sqrt{n/g})$ on the quantum query complexity of computing the Gap-Hamming distance between two given strings of lenght $n$. The proof is a combinatorial argument based on block sensitivity and a reduction from a threshold function.

arXiv:1705.09710•May 26, 2017•0 citations

Quantum Query Advantage Requires Space

Minbo Gao, Zhengfeng Ji, Ziyi Xie

Hao, Huang, and Liu (STOC'26) recently showed that optimal quantum query complexity may require large workspace even for short-output problems, and asked whether a quantum query advantage over classical computation can itself require space. We resolve this question by exhibiting an explicit total Boolean function with quantum query complexity $Q=\widetildeΘ(M)$, and randomized query complexity $R=Θ(M^{21/20})$, whereas, for every fixed $0<η<1/100$ and $S\le O(M^{1/100-η})$, its $S$-space quantum query complexity satisfies $Q_S=ω(M^{21/20})$. Consequently, $$ Q<R<Q_S, $$ so the unrestricted quantum query advantage disappears under sufficiently small workspace. The separation is obtained through a one-bit filtered-parity construction and a space-sensitive quantum lower bound based on compressed-oracle capacity and a new parity-to-capacity inequality, which may be of independent interest.

quant-pharXiv:2609.29497•Sep 7, 2026•1 citation

Quantum query complexity and semi-definite programming

Howard Barnum, Michael Saks, Márió Szegedy

We reformulate quantum query complexity in terms of inequalities and equations for a set of positive semidefinite matrices. Using the new formulation we: 1) show that the workspace of a quantum computer can be limited to at most n+k qubits (where n and k are the number of input and output bits respectively) without reducing the computational power of the model; 2) give an algorithm that on input the truth table of a partial Boolean function and an integer t runs in time polynomial in the size of the truth table and estimates, to any desired accuracy, the minimum probability of error that can be attained by a quantum query algorithm attempts to evaluate f in t queries; 3) use semidefinite programming duality to formulate a dual SDP P/spl circ/(f, t, /spl epsi/) that is feasible if and only if f cannot be evaluated within error /spl epsi/ by a t-step quantum query algorithm. Using this SDP, we derive a general lower bound for quantum query complexity that encompasses a lower bound method of Ambainis and its generalizations; 4) give an interpretation of a generalized form of branching in quantum computation.

IEEE Conference on Computational Complexity (CCC)•Mar 22, 2004•122 citations

Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language

Andris Ambainis, Kaspars Balodis, Jānis Iraids +6 more

We study the quantum query complexity of two problems. First, we consider the problem of determining if a sequence of parentheses is a properly balanced one (a Dyck word), with a depth of at most $k$. We call this the $Dyck_{k,n}$ problem. We prove a lower bound of $Ω(c^k \sqrt{n})$, showing that the complexity of this problem increases exponentially in $k$. Here $n$ is the length of the word. When $k$ is a constant, this is interesting as a representative example of star-free languages for which a surprising $\tilde{O}(\sqrt{n})$ query quantum algorithm was recently constructed by Aaronson et al. Their proof does not give rise to a general algorithm. When $k$ is not a constant, $Dyck_{k,n}$ is not context-free. We give an algorithm with $O\left(\sqrt{n}(\log{n})^{0.5k}\right)$ quantum queries for $Dyck_{k,n}$ for all $k$. This is better than the trival upper bound $n$ for $k=o\left(\frac{\log(n)}{\log\log n}\right)$. Second, we consider connectivity problems on grid graphs in 2 dimensions, if some of the edges of the grid may be missing. By embedding the "balanced parentheses" problem into the grid, we show a lower bound of $Ω(n^{1.5-ε})$ for the directed 2D grid and $Ω(n^{2-ε})$ for the undirected 2D grid. The directed problem is interesting as a black-box model for a class of classical dynamic programming strategies including the one that is usually used for the well-known edit distance problem. We also show a generalization of this result to more than 2 dimensions.

arXiv:2007.03402•Leibniz international proceedings in informatics•Jan 1, 2020•26 citations

Lower bounds on quantum query complexity for symmetric functions

Rajat Mittal, Sanjay S Nair, Sunayana Patro

One of the main reasons for query model's prominence in quantum complexity is the presence of concrete lower bounding techniques: polynomial method and adversary method. There have been considerable efforts to not just give lower bounds using these methods but even to compare and relate them. We explore the value of these bounds on quantum query complexity for the class of symmetric functions, arguably one of the most natural and basic set of Boolean functions. We show (using the recently introduced spectral sensitivity) that both these bounds (positive adversary and approximate degree) give the same value for every total symmetric Boolean function. We also look at the quantum query complexity of Gap Majority, a partial symmetric function. It has gained importance recently in regard to understanding the composition of randomized query complexity. We characterize the quantum query complexity of Gap Majority and show a lower bound on noisy randomized query complexity (Ben-David and Blais, FOCS 2020) in terms of quantum query complexity. In addition, we study how large certificate complexity and block sensitivity can be as compared to sensitivity (even up to constant factors) for symmetric functions. We show tight separations, i.e., give upper bound on possible separations and construct functions achieving the same.

•Oct 25, 2021•0 citations

Beyond the $n/2$ Threshold: Quantum Query Complexity for Computing Hamming Weight and Symmetric Functions

Yuan Deng, Zihan Hao, Honghao Lin +4 more

The oracle-interrogation algorithm [van Dam, FOCS '98] computes every $n$-bit Boolean function with bounded error using $n/2+O(\sqrt n)$ quantum queries. In contrast, parity can be computed exactly using $\lceil n/2\rceil$ queries, but whether an additive overhead beyond $n/2$ is necessary for a single Boolean output has remained open. In this work, we construct an explicit family of symmetric Boolean functions requiring $n/2+Ω(n^{1/3})$ quantum queries at a fixed positive constant error. We also give an algorithm that recovers the exact Hamming weight using $n/2+O(n^{1/3})$ quantum queries with bounded error, and therefore computes every symmetric Boolean function within the same query bound. Together, these results determine the optimal additive order for Hamming weight recovery and for the worst case over symmetric Boolean functions at sufficiently small constant error.

arXiv:2611.09809•Nov 6, 2026•0 citations
Branching programs are quite popular for studying time-space lower bounds. Bera et al. recently introduced the model of generalized quantum branching program aka. GQBP that generalized two earlier models of quantum branching programs. In this work we study a restricted version of GQBP with the motivation of proving bounds on the query-space requirement of quantum-query circuits. We show the first explicit query-space lower bound for our restricted version. We prove that the well-studied ORn_nn​ decision problem, given a promise that at most one position of an nnn-sized Boolean array is a 1, satisfies the bound Q2s=Ω(n2)Q^2 s = Ω(n^2)Q2s=Ω(n2), where QQQ denotes the number of queries and sss denotes the width of the GQBP. We then generalize the problem to show that the same bound holds for deciding between two strings with a constant Hamming distance; this gives us query-space lower bounds on problems such as Parity and Majority. Our results produce an alternative proof of the Ω(n)Ω(\sqrt{n})Ω(n​)-lower bound on the query complexity of any non-constant symmetric Boolean function.
The Gap-Hamming distance problem is the promise problem of deciding if the Hamming distance hhh between two strings of length nnn is greater than aaa or less than bbb, where the gap g=∣a−b∣≥1g=|a-b|\geq 1g=∣a−b∣≥1 and aaa and bbb could depend on nnn. In this short note, we give a lower bound of Ω(n/g)Ω( \sqrt{n/g})Ω(n/g​) on the quantum query complexity of computing the Gap-Hamming distance between two given strings of lenght nnn. The proof is a combinatorial argument based on block sensitivity and a reduction from a threshold function.
Hao, Huang, and Liu (STOC'26) recently showed that optimal quantum query complexity may require large workspace even for short-output problems, and asked whether a quantum query advantage over classical computation can itself require space. We resolve this question by exhibiting an explicit total Boolean function with quantum query complexity Q=Θ~(M)Q=\widetildeΘ(M)Q=Θ(M), and randomized query complexity R=Θ(M21/20)R=Θ(M^{21/20})R=Θ(M21/20), whereas, for every fixed 0<η<1/1000<η<1/1000<η<1/100 and S≤O(M1/100−η)S\le O(M^{1/100-η})S≤O(M1/100−η), its SSS-space quantum query complexity satisfies QS=ω(M21/20)Q_S=ω(M^{21/20})QS​=ω(M21/20). Consequently, Q<R<QS, Q<R<Q_S, Q<R<QS​, so the unrestricted quantum query advantage disappears under sufficiently small workspace. The separation is obtained through a one-bit filtered-parity construction and a space-sensitive quantum lower bound based on compressed-oracle capacity and a new parity-to-capacity inequality, which may be of independent interest.
We reformulate quantum query complexity in terms of inequalities and equations for a set of positive semidefinite matrices. Using the new formulation we: 1) show that the workspace of a quantum computer can be limited to at most n+k qubits (where n and k are the number of input and output bits respectively) without reducing the computational power of the model; 2) give an algorithm that on input the truth table of a partial Boolean function and an integer t runs in time polynomial in the size of the truth table and estimates, to any desired accuracy, the minimum probability of error that can be attained by a quantum query algorithm attempts to evaluate f in t queries; 3) use semidefinite programming duality to formulate a dual SDP P/spl circ/(f, t, /spl epsi/) that is feasible if and only if f cannot be evaluated within error /spl epsi/ by a t-step quantum query algorithm. Using this SDP, we derive a general lower bound for quantum query complexity that encompasses a lower bound method of Ambainis and its generalizations; 4) give an interpretation of a generalized form of branching in quantum computation.
We study the quantum query complexity of two problems. First, we consider the problem of determining if a sequence of parentheses is a properly balanced one (a Dyck word), with a depth of at most kkk. We call this the Dyckk,nDyck_{k,n}Dyckk,n​ problem. We prove a lower bound of Ω(ckn)Ω(c^k \sqrt{n})Ω(ckn​), showing that the complexity of this problem increases exponentially in kkk. Here nnn is the length of the word. When kkk is a constant, this is interesting as a representative example of star-free languages for which a surprising O~(n)\tilde{O}(\sqrt{n})O~(n​) query quantum algorithm was recently constructed by Aaronson et al. Their proof does not give rise to a general algorithm. When kkk is not a constant, Dyckk,nDyck_{k,n}Dyckk,n​ is not context-free. We give an algorithm with O(n(log⁡n)0.5k)O\left(\sqrt{n}(\log{n})^{0.5k}\right)O(n​(logn)0.5k) quantum queries for Dyckk,nDyck_{k,n}Dyckk,n​ for all kkk. This is better than the trival upper bound nnn for k=o(log⁡(n)log⁡log⁡n)k=o\left(\frac{\log(n)}{\log\log n}\right)k=o(loglognlog(n)​). Second, we consider connectivity problems on grid graphs in 2 dimensions, if some of the edges of the grid may be missing. By embedding the "balanced parentheses" problem into the grid, we show a lower bound of Ω(n1.5−ε)Ω(n^{1.5-ε})Ω(n1.5−ε) for the directed 2D grid and Ω(n2−ε)Ω(n^{2-ε})Ω(n2−ε) for the undirected 2D grid. The directed problem is interesting as a black-box model for a class of classical dynamic programming strategies including the one that is usually used for the well-known edit distance problem. We also show a generalization of this result to more than 2 dimensions.
One of the main reasons for query model's prominence in quantum complexity is the presence of concrete lower bounding techniques: polynomial method and adversary method. There have been considerable efforts to not just give lower bounds using these methods but even to compare and relate them. We explore the value of these bounds on quantum query complexity for the class of symmetric functions, arguably one of the most natural and basic set of Boolean functions. We show (using the recently introduced spectral sensitivity) that both these bounds (positive adversary and approximate degree) give the same value for every total symmetric Boolean function. We also look at the quantum query complexity of Gap Majority, a partial symmetric function. It has gained importance recently in regard to understanding the composition of randomized query complexity. We characterize the quantum query complexity of Gap Majority and show a lower bound on noisy randomized query complexity (Ben-David and Blais, FOCS 2020) in terms of quantum query complexity. In addition, we study how large certificate complexity and block sensitivity can be as compared to sensitivity (even up to constant factors) for symmetric functions. We show tight separations, i.e., give upper bound on possible separations and construct functions achieving the same.
Beyond the n/2n/2n/2 Threshold: Quantum Query Complexity for Computing Hamming Weight and Symmetric Functions
The oracle-interrogation algorithm [van Dam, FOCS '98] computes every nnn-bit Boolean function with bounded error using n/2+O(n)n/2+O(\sqrt n)n/2+O(n​) quantum queries. In contrast, parity can be computed exactly using ⌈n/2⌉\lceil n/2\rceil⌈n/2⌉ queries, but whether an additive overhead beyond n/2n/2n/2 is necessary for a single Boolean output has remained open. In this work, we construct an explicit family of symmetric Boolean functions requiring n/2+Ω(n1/3)n/2+Ω(n^{1/3})n/2+Ω(n1/3) quantum queries at a fixed positive constant error. We also give an algorithm that recovers the exact Hamming weight using n/2+O(n1/3)n/2+O(n^{1/3})n/2+O(n1/3) quantum queries with bounded error, and therefore computes every symmetric Boolean function within the same query bound. Together, these results determine the optimal additive order for Hamming weight recovery and for the worst case over symmetric Boolean functions at sufficiently small constant error.