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:1801.05717 · Science China Information Sciences

Exact quantum query complexity of weight decision problems via Chebyshev polynomials

Xiaoyu He, Xiaoming Sun, Guang Yang, Pei Yuan

Published Jan 11, 2023• 21 citations
arXivHTMLPDF
DOI
10.1007/s11432-021-3468-x

Related papers

Optimality proofs of quantum weight decision algorithms

Byung-Soo Choi

Quantum Information Processing•Mar 10, 2011•4 citations

Exact quantum query complexity of computing Hamming weight modulo powers of two and three

Arjan Cornelissen, Nikhil S. Mande, Māris Ozols +1 more

We study the problem of computing the Hamming weight of an $n$-bit string modulo $m$, for any positive integer $m \leq n$ whose only prime factors are 2 and 3. We show that the exact quantum query complexity of this problem is $\left\lceil n(1 - 1/m) \right\rceil$. The upper bound is via an iterative query algorithm whose core components are the well-known 1-query quantum algorithm (essentially due to Deutsch) to compute the Hamming weight a 2-bit string mod 2 (i.e., the parity of the input bits), and a new 2-query quantum algorithm to compute the Hamming weight of a 3-bit string mod 3. We show a matching lower bound (in fact for arbitrary moduli $m$) via a variant of the polynomial method [de Wolf, SIAM J. Comput., 32(3), 2003]. This bound is for the weaker task of deciding whether or not a given $n$-bit input has Hamming weight 0 modulo $m$, and it holds even in the stronger non-deterministic quantum query model where an algorithm must have positive acceptance probability iff its input evaluates to 1. For $m>2$ our lower bound exceeds $n/2$, beating the best lower bound provable using the general polynomial method [Theorem 4.3, Beals et al., J. ACM 48(4), 2001].

arXiv:2112.14682•Dec 29, 2021•7 citations

The quantum query complexity of learning multilinear polynomials

Ashley Montanaro

arXiv:1105.3310•Information Processing Letters•Mar 6, 2012•17 citations

Quantum Search-To-Decision Reductions and the State Synthesis Problem

Sandy Irani, Anand Natarajan, Chinmay Nirkhe +2 more

It is a useful fact in classical computer science that many search problems are reducible to decision problems; this has led to decision problems being regarded as the $\textit{de facto}$ computational task to study in complexity theory. In this work, we explore search-to-decision reductions for quantum search problems, wherein a quantum algorithm makes queries to a classical decision oracle to output a desired quantum state. In particular, we focus on search-to-decision reductions for $\mathsf{QMA}$, and show that there exists a quantum polynomial-time algorithm that can generate a witness for a $\mathsf{QMA}$ problem up to inverse polynomial precision by making one query to a $\mathsf{PP}$ decision oracle. We complement this result by showing that $\mathsf{QMA}$-search does $\textit{not}$ reduce to $\mathsf{QMA}$-decision in polynomial-time, relative to a quantum oracle. We also explore the more general $\textit{state synthesis problem}$, in which the goal is to efficiently synthesize a target state by making queries to a classical oracle encoding the state. We prove that there exists a classical oracle with which any quantum state can be synthesized to inverse polynomial precision using only one oracle query and to inverse exponential precision using two oracle queries. This answers an open question of Aaronson from 2016, who presented a state synthesis algorithm that makes $O(n)$ queries to a classical oracle to prepare an $n$-qubit state, and asked if the query complexity could be made sublinear.

arXiv:2111.02999•Leibniz international proceedings in informatics•Nov 4, 2021•31 citations

An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree

Andris Ambainis, Aleksandrs Belovs

arXiv:2301.09218•Computational Complexity•Oct 3, 2025•2 citations

Improved quantum query upper bounds based on classical decision trees

Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro

We consider the following question in query complexity: Given a classical query algorithm in the form of a decision tree, when does there exist a quantum query algorithm with a speed-up (i.e., that makes fewer queries) over the classical one? We provide a general construction based on the structure of the underlying decision tree, and prove that this can give us an up-to-quadratic quantum speed-up in the number of queries. In particular, our results give a bounded-error quantum query algorithm of cost O(√s) to compute a Boolean function (more generally, a relation) that can be computed by a classical (even randomized) decision tree of size s. This recovers an O(√n) algorithm for the Search problem, for example. Lin and Lin [Theory of Computing'16] and Beigi and Taghavi [Quantum'20] showed results of a similar flavor. Their upper bounds are in terms of a quantity which we call the “guessing complexity” of a decision tree. We identify that the guessing complexity of a decision tree equals its rank, a notion introduced by Ehrenfeucht and Haussler [Information and Computation'89] in the context of learning theory. This answers a question posed by Lin and Lin, who asked whether the guessing complexity of a decision tree is related to any measure studied in classical complexity theory. We also show a polynomial separation between rank and its natural randomized analog for the complete binary AND-OR tree. Beigi and Taghavi constructed span programs and dual adversary solutions for Boolean functions given classical decision trees computing them and an assignment of non-negative weights to edges of the tree. We explore the effect of changing these weights on the resulting span program complexity and objective value of the dual adversary bound, and capture the best possible weighting scheme by an optimization program. We exhibit a solution to this program and argue its optimality from first principles. We also exhibit decision trees for which our bounds are strictly stronger than those of Lin and Lin, and Beigi and Taghavi. This answers a question of Beigi and Taghavi, who asked whether different weighting schemes in their construction could yield better upper bounds.

•Dec 14, 2022•0 citations
We study the problem of computing the Hamming weight of an nnn-bit string modulo mmm, for any positive integer m≤nm \leq nm≤n whose only prime factors are 2 and 3. We show that the exact quantum query complexity of this problem is ⌈n(1−1/m)⌉\left\lceil n(1 - 1/m) \right\rceil⌈n(1−1/m)⌉. The upper bound is via an iterative query algorithm whose core components are the well-known 1-query quantum algorithm (essentially due to Deutsch) to compute the Hamming weight a 2-bit string mod 2 (i.e., the parity of the input bits), and a new 2-query quantum algorithm to compute the Hamming weight of a 3-bit string mod 3. We show a matching lower bound (in fact for arbitrary moduli mmm) via a variant of the polynomial method [de Wolf, SIAM J. Comput., 32(3), 2003]. This bound is for the weaker task of deciding whether or not a given nnn-bit input has Hamming weight 0 modulo mmm, and it holds even in the stronger non-deterministic quantum query model where an algorithm must have positive acceptance probability iff its input evaluates to 1. For m>2m>2m>2 our lower bound exceeds n/2n/2n/2, beating the best lower bound provable using the general polynomial method [Theorem 4.3, Beals et al., J. ACM 48(4), 2001].
It is a useful fact in classical computer science that many search problems are reducible to decision problems; this has led to decision problems being regarded as the de facto\textit{de facto}de facto computational task to study in complexity theory. In this work, we explore search-to-decision reductions for quantum search problems, wherein a quantum algorithm makes queries to a classical decision oracle to output a desired quantum state. In particular, we focus on search-to-decision reductions for QMA\mathsf{QMA}QMA, and show that there exists a quantum polynomial-time algorithm that can generate a witness for a QMA\mathsf{QMA}QMA problem up to inverse polynomial precision by making one query to a PP\mathsf{PP}PP decision oracle. We complement this result by showing that QMA\mathsf{QMA}QMA-search does not\textit{not}not reduce to QMA\mathsf{QMA}QMA-decision in polynomial-time, relative to a quantum oracle. We also explore the more general state synthesis problem\textit{state synthesis problem}state synthesis problem, in which the goal is to efficiently synthesize a target state by making queries to a classical oracle encoding the state. We prove that there exists a classical oracle with which any quantum state can be synthesized to inverse polynomial precision using only one oracle query and to inverse exponential precision using two oracle queries. This answers an open question of Aaronson from 2016, who presented a state synthesis algorithm that makes O(n)O(n)O(n) queries to a classical oracle to prepare an nnn-qubit state, and asked if the query complexity could be made sublinear.
We consider the following question in query complexity: Given a classical query algorithm in the form of a decision tree, when does there exist a quantum query algorithm with a speed-up (i.e., that makes fewer queries) over the classical one? We provide a general construction based on the structure of the underlying decision tree, and prove that this can give us an up-to-quadratic quantum speed-up in the number of queries. In particular, our results give a bounded-error quantum query algorithm of cost O(√s) to compute a Boolean function (more generally, a relation) that can be computed by a classical (even randomized) decision tree of size s. This recovers an O(√n) algorithm for the Search problem, for example. Lin and Lin [Theory of Computing'16] and Beigi and Taghavi [Quantum'20] showed results of a similar flavor. Their upper bounds are in terms of a quantity which we call the “guessing complexity” of a decision tree. We identify that the guessing complexity of a decision tree equals its rank, a notion introduced by Ehrenfeucht and Haussler [Information and Computation'89] in the context of learning theory. This answers a question posed by Lin and Lin, who asked whether the guessing complexity of a decision tree is related to any measure studied in classical complexity theory. We also show a polynomial separation between rank and its natural randomized analog for the complete binary AND-OR tree. Beigi and Taghavi constructed span programs and dual adversary solutions for Boolean functions given classical decision trees computing them and an assignment of non-negative weights to edges of the tree. We explore the effect of changing these weights on the resulting span program complexity and objective value of the dual adversary bound, and capture the best possible weighting scheme by an optimization program. We exhibit a solution to this program and argue its optimality from first principles. We also exhibit decision trees for which our bounds are strictly stronger than those of Lin and Lin, and Beigi and Taghavi. This answers a question of Beigi and Taghavi, who asked whether different weighting schemes in their construction could yield better upper bounds.