The weight decision problem, which requires to determine the Hamming weight of a given binary string, is a natural and important problem, with applications in cryptanalysis, coding theory, fault-tolerant circuit design and so on. In particular, both Deutsch-Jozsa problem and Grover search problem can be interpreted as special cases of weight decision problems. In this work, we investigate the exact quantum query complexity of weight decision problems, where the quantum algorithm must always output the correct answer. More specifically we consider a partial Boolean function which distinguishes whether the Hamming weight of the length- $n$ input is $k$ or it is $l$ . Our contribution includes both upper bounds and lower bounds for the precise number of queries. Furthermore, for most choices of $(\frac{k}{n},\frac{l}{n})$ and sufficiently large $n$ , the gap between our upper and lower bounds is no more than one. To get the results, we first build the connection between Chebyshev polynomials and our problem, then determine all the boundary cases of $(\frac{k}{n},\frac{l}{n})$ with matching upper and lower bounds, and finally we generalize to other cases via a new \emph{quantum padding} technique. This quantum padding technique can be of independent interest in designing other quantum algorithms.The weight decision problem, which requires to determine the Hamming weight of a given binary string, is a natural and important problem, with applications in cryptanalysis, coding theory, fault-tolerant circuit design and so on. In particular, both Deutsch-Jozsa problem and Grover search problem can be interpreted as special cases of weight decision problems. In this work, we investigate the exact quantum query complexity of weight decision problems, where the quantum algorithm must always output the correct answer. More specifically we consider a partial Boolean function which distinguishes whether the Hamming weight of the length-$n$ input is $k$ or it is $l$. Our contribution includes both upper bounds and lower bounds for the precise number of queries. Furthermore, for most choices of $(\frac{k}{n},\frac{l}{n})$ and sufficiently large $n$, the gap between our upper and lower bounds is no more than one. To get the results, we first build the connection between Chebyshev polynomials and our problem, then determine all the boundary cases of $(\frac{k}{n},\frac{l}{n})$ with matching upper and lower bounds, and finally we generalize to other cases via a new \emph{quantum padding} technique. This quantum padding technique can be of independent interest in designing other quantum algorithms.

Jan 17, 20183 citations

The quantum query complexity of learning multilinear polynomials

Ashley Montanaro

Information Processing LettersMar 6, 201212 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].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.14682Dec 29, 20211 citation

An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree

Andris Ambainis, Aleksandrs Belovs

Computational ComplexityOct 3, 20250 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.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.02999Leibniz international proceedings in informaticsNov 4, 20218 citations

n

input is

k

or it is

l

. Our contribution includes both upper bounds and lower bounds for the precise number of queries. Furthermore, for most choices of

(\frac{k}{n},\frac{l}{n})

and sufficiently large

n

, the gap between our upper and lower bounds is no more than one. To get the results, we first build the connection between Chebyshev polynomials and our problem, then determine all the boundary cases of

(\frac{k}{n},\frac{l}{n})

with matching upper and lower bounds, and finally we generalize to other cases via a new \emph{quantum padding} technique. This quantum padding technique can be of independent interest in designing other quantum algorithms.

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].

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.