Quantum Information and Computation

The quantum query complexity of AC0

Paul W. Beame, Widad Machmouchi

Published Jul 1, 2012• 21 citations

Abstract

We show that any quantum algorithm deciding whether an input function $f$ from $[n]$ to $[n]$ is 2-to-1 or almost 2-to-1 requires $\Theta(n)$ queries to $f$. The same lower bound holds for determining whether or not a function $f$ from $[2n-2]$ to $[n]$ is surjective. These results yield a nearly linear $\Omega(n/\log n)$ lower bound on the quantum query complexity of $\cl{AC}^0$. The best previous lower bound known for any $\cl{AC^0}$ function was the $\Omega ((n/\log n)^{2/3})$ bound given by Aaronson and Shi's $\Omega(n^{2/3})$ lower bound for the element distinctness problem.

DOI: 10.26421/qic12.7-8-11

Related papers

The Quantum Query Complexity of AC0

Paul W. Beame, Widad Machmouchi

arXiv:1008.2422Aug 14, 20105 citations

Improved Approximate Degree Bounds For k-distinctness

Nikhil S. Mande, Justin Thaler, Shuchen Zhu

arXiv:2002.08389Leibniz international proceedings in informaticsJan 1, 20204 citations

Adversary Lower Bound for Element Distinctness with Small Range

Ansis Rosmanis

arXiv:1401.3826Jan 16, 20143 citations

Optimal query complexity for fractional quantum evolution

Anthony Yuezhang Liu, Adam Wesołowski, Jayne Thompson +2 more

quant-pharXiv:2610.01940Oct 2, 20260 citations

UNDERSTANDING QUANTUM ALGORITHMS VIA QUERY COMPLEXITY

Andris Ambainis

arXiv:1712.06349International Congress of Mathematicians (ICM)May 1, 201965 citations

A note on the quantum collision and set equality problems

Mark Zhandry

arXiv:1312.1027Quantum Information and ComputationMay 1, 201599 citations

Quantum Information and Computation

The quantum query complexity of AC0

Paul W. Beame, Widad Machmouchi

Published Jul 1, 2012• 21 citations

Publisher

Abstract

We show that any quantum algorithm deciding whether an input function

f

from

[n]

[n]

is 2-to-1 or almost 2-to-1 requires

\Theta(n)

queries to

f

. The same lower bound holds for determining whether or not a function

f

from

[2n-2]

[n]

is surjective. These results yield a nearly linear

\Omega(n/\log n)

lower bound on the quantum query complexity of

\cl{AC}^0

. The best previous lower bound known for any

\cl{AC^0}

function was the

\Omega ((n/\log n)^{2/3})

bound given by Aaronson and Shi's

\Omega(n^{2/3})

lower bound for the element distinctness problem.

DOI: 10.26421/qic12.7-8-11

Related papers

The Quantum Query Complexity of AC0

Paul W. Beame, Widad Machmouchi

We show that any quantum algorithm deciding whether an input function $f$ from $[n]$ to $[n]$ is 2-to-1 or almost 2-to-1 requires $Θ(n)$ queries to $f$ . The same lower bound holds for determining whether or not a function $f$ from $[2n-2]$ to $[n]$ is surjective. These results yield a nearly linear $Ω(n/\log n)$ lower bound on the quantum query complexity of $\cl{AC}^0$. The best previous lower bound known for any $\cl{AC^0}$ function was the $Ω((n/\log n)^{2/3})$ bound given by Aaronson and Shi's $Ω(n^{2/3})$ lower bound for the element distinctness problem.We show that any quantum algorithm deciding whether an input function $f$ from $[n]$ to $[n]$ is 2-to-1 or almost 2-to-1 requires $Θ(n)$ queries to $f$. The same lower bound holds for determining whether or not a function $f$ from $[2n-2]$ to $[n]$ is surjective. These results yield a nearly linear $Ω(n/\log n)$ lower bound on the quantum query complexity of $\cl{AC}^0$. The best previous lower bound known for any $\cl{AC^0}$ function was the $Ω((n/\log n)^{2/3})$ bound given by Aaronson and Shi's $Ω(n^{2/3})$ lower bound for the element distinctness problem.

arXiv:1008.2422Aug 14, 20105 citations

Improved Approximate Degree Bounds For k-distinctness

Nikhil S. Mande, Justin Thaler, Shuchen Zhu

An open problem that is widely regarded as one of the most important in quantum query complexity is to resolve the quantum query complexity of the k-distinctness function on inputs of size N. While the case of k=2 (also called Element Distinctness) is well-understood, there is a polynomial gap between the known upper and lower bounds for all constants k>2. Specifically, the best known upper bound is O(N^{(3/4)-1/(2^{k+2}-4)}) (Belovs, FOCS 2012), while the best known lower bound for k >= 2 is Omega(N^{2/3} + N^{(3/4)-1/(2k)}) (Aaronson and Shi, J.~ACM 2004; Bun, Kothari, and Thaler, STOC 2018). For any constant k >= 4, we improve the lower bound to Omega(N^{(3/4)-1/(4k)}). This yields, for example, the first proof that 4-distinctness is strictly harder than Element Distinctness. Our lower bound applies more generally to approximate degree. As a secondary result, we give a simple construction of an approximating polynomial of degree O(N^{3/4}) that applies whenever k <= polylog(N).An open problem that is widely regarded as one of the most important in quantum query complexity is to resolve the quantum query complexity of the k-distinctness function on inputs of size N. While the case of k=2 (also called Element Distinctness) is well-understood, there is a polynomial gap between the known upper and lower bounds for all constants k>2. Specifically, the best known upper bound is O(N^{(3/4)-1/(2^{k+2}-4)}) (Belovs, FOCS 2012), while the best known lower bound for k >= 2 is Omega(N^{2/3} + N^{(3/4)-1/(2k)}) (Aaronson and Shi, J.~ACM 2004; Bun, Kothari, and Thaler, STOC 2018). For any constant k >= 4, we improve the lower bound to Omega(N^{(3/4)-1/(4k)}). This yields, for example, the first proof that 4-distinctness is strictly harder than Element Distinctness. Our lower bound applies more generally to approximate degree. As a secondary result, we give a simple construction of an approximating polynomial of degree O(N^{3/4}) that applies whenever k <= polylog(N).

arXiv:2002.08389Leibniz international proceedings in informaticsJan 1, 20204 citations

Adversary Lower Bound for Element Distinctness with Small Range

Ansis Rosmanis

The Element Distinctness problem is to decide whether each character of an input string is unique. The quantum query complexity of Element Distinctness is known to be $Θ(N^{2/3})$ ; the polynomial method gives a tight lower bound for any input alphabet, while a tight adversary construction was only known for alphabets of size $Ω(N^2)$ . We construct a tight $Ω(N^{2/3})$ adversary lower bound for Element Distinctness with minimal non-trivial alphabet size, which equals the length of the input. This result may help to improve lower bounds for other related query problems.The Element Distinctness problem is to decide whether each character of an input string is unique. The quantum query complexity of Element Distinctness is known to be $Θ(N^{2/3})$; the polynomial method gives a tight lower bound for any input alphabet, while a tight adversary construction was only known for alphabets of size $Ω(N^2)$. We construct a tight $Ω(N^{2/3})$ adversary lower bound for Element Distinctness with minimal non-trivial alphabet size, which equals the length of the input. This result may help to improve lower bounds for other related query problems.

arXiv:1401.3826Jan 16, 20143 citations

Optimal query complexity for fractional quantum evolution

Anthony Yuezhang Liu, Adam Wesołowski, Jayne Thompson +2 more

Given oracle access to an unknown unitary $U=e^{iH}$ , the fractional query problem asks how many queries are required to implement a noninteger power $U^t=e^{itH}$ , $0<t<1$ , when the spectrum is separated from the branch cut by a gap $δ$ . Quantum singular value transformation gives an upper bound of $O\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$ queries for approximation error $\varepsilon$ . We prove a matching lower bound for arbitrary query algorithms. Our argument reduces any $N$ -query circuit to the approximation of $e^{itθ}$ by a trigonometric polynomial with degree bounded by $O(N)$ , together with Remez inequality. This allows us to establish the lower bound of $Ω_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$ . Consequently, the optimal query complexity for fractional query problem is $Θ_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$ , showing that the known QSVT construction is asymptotically optimal. We also give an alternative lower bound proof based on constructing a linear functional that annihilates the approximant space, yielding a $Ω_τ\!\left(\log\frac{1}{\varepsilon}\right)$ bound uniform to $δ$ .Given oracle access to an unknown unitary $U=e^{iH}$ , the fractional query problem asks how many queries are required to implement a noninteger power $U^t=e^{itH}$, $0<t<1$, when the spectrum is separated from the branch cut by a gap $δ$. Quantum singular value transformation gives an upper bound of $O\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$ queries for approximation error $\varepsilon$. We prove a matching lower bound for arbitrary query algorithms. Our argument reduces any $N$-query circuit to the approximation of $e^{itθ}$ by a trigonometric polynomial with degree bounded by $O(N)$, together with Remez inequality. This allows us to establish the lower bound of $Ω_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$. Consequently, the optimal query complexity for fractional query problem is $Θ_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)$, showing that the known QSVT construction is asymptotically optimal. We also give an alternative lower bound proof based on constructing a linear functional that annihilates the approximant space, yielding a $Ω_τ\!\left(\log\frac{1}{\varepsilon}\right)$ bound uniform to $δ$.

quant-pharXiv:2610.01940Oct 2, 20260 citations

UNDERSTANDING QUANTUM ALGORITHMS VIA QUERY COMPLEXITY

Andris Ambainis

Query complexity is a model of computation in which we have to compute a function $f(x_1, \ldots, x_N)$ of variables $x_i$ which can be accessed via queries. The complexity of an algorithm is measured by the number of queries that it makes. Query complexity is widely used for studying quantum algorithms, for two reasons. First, it includes many of the known quantum algorithms (including Grover's quantum search and a key subroutine of Shor's factoring algorithm). Second, one can prove lower bounds on the query complexity, bounding the possible quantum advantage. In the last few years, there have been major advances on several longstanding problems in the query complexity. In this talk, we survey these results and related work, including: - the biggest quantum-vs-classical gap for partial functions (a problem solvable with 1 query quantumly but requiring $Ω(\sqrt{N})$ queries classically); - the biggest quantum-vs-determistic and quantum-vs-probabilistic gaps for total functions (for example, a problem solvable with $M$ queries quantumly but requiring $\tildeΩ(M^{2.5})$ queries probabilistically); - the biggest probabilistic-vs-deterministic gap for total functions (a problem solvable with $M$ queries probabilistically but requiring $\tildeΩ(M^{2})$ queries deterministically); - the bounds on the gap that can be achieved for subclasses of functions (for example, symmetric functions); - the connections between query algorithms and approximations by low-degree polynomials.Query complexity is a model of computation in which we have to compute a function $f(x_1, \ldots, x_N)$ of variables $x_i$ which can be accessed via queries. The complexity of an algorithm is measured by the number of queries that it makes. Query complexity is widely used for studying quantum algorithms, for two reasons. First, it includes many of the known quantum algorithms (including Grover's quantum search and a key subroutine of Shor's factoring algorithm). Second, one can prove lower bounds on the query complexity, bounding the possible quantum advantage. In the last few years, there have been major advances on several longstanding problems in the query complexity. In this talk, we survey these results and related work, including: - the biggest quantum-vs-classical gap for partial functions (a problem solvable with 1 query quantumly but requiring $Ω(\sqrt{N})$ queries classically); - the biggest quantum-vs-determistic and quantum-vs-probabilistic gaps for total functions (for example, a problem solvable with $M$ queries quantumly but requiring $\tildeΩ(M^{2.5})$ queries probabilistically); - the biggest probabilistic-vs-deterministic gap for total functions (a problem solvable with $M$ queries probabilistically but requiring $\tildeΩ(M^{2})$ queries deterministically); - the bounds on the gap that can be achieved for subclasses of functions (for example, symmetric functions); - the connections between query algorithms and approximations by low-degree polynomials.

arXiv:1712.06349International Congress of Mathematicians (ICM)May 1, 201965 citations

A note on the quantum collision and set equality problems

Mark Zhandry

A collision for a function $f$ is two distinct inputs $x_1\neq x_2$ such that $f$ outputs the same value on both inputs: $f(x_1)=f(x_2)$ . The quantum query complexity of finding collisions has been shown~\cite{BHT1997,AS2004, Ambainis05, Kutin05} in some settings to be $\Theta(N^{1/3})$ ; however, these results do not apply to random functions. The issues are two-fold. First, the $\Omega(N^{1/3})$ lower bound only applies when the domain is no larger than the co-domain, which precludes many of the cryptographically interesting applications. Second, most of the results in the literature only apply to $r$ -to-1 functions, which are quite different from random functions. Understanding the collision problem for random functions is of great importance to cryptography, and we seek to fill the gaps of knowledge for this problem. To that end, we prove that, as expected, a quantum query complexity of $\Theta(N^{1/3})$ holds for all interesting domain and co-domain sizes. Our proofs are simple, and combine existing techniques with several novel tricks to obtain the desired results. Using our techniques, we also give an optimal $\Omega(M^{1/3})$ lower bound for the set equality problem. This lower bound can be used to improve the relationship between classical randomized query complexity and quantum query complexity for so-called permutation-symmetric functions.A collision for a function $f$ is two distinct inputs $x_1\neq x_2$ such that $f$ outputs the same value on both inputs: $f(x_1)=f(x_2)$. The quantum query complexity of finding collisions has been shown~\cite{BHT1997,AS2004, Ambainis05, Kutin05} in some settings to be $\Theta(N^{1/3})$; however, these results do not apply to random functions. The issues are two-fold. First, the $\Omega(N^{1/3})$ lower bound only applies when the domain is no larger than the co-domain, which precludes many of the cryptographically interesting applications. Second, most of the results in the literature only apply to $r$-to-1 functions, which are quite different from random functions. Understanding the collision problem for random functions is of great importance to cryptography, and we seek to fill the gaps of knowledge for this problem. To that end, we prove that, as expected, a quantum query complexity of $\Theta(N^{1/3})$ holds for all interesting domain and co-domain sizes. Our proofs are simple, and combine existing techniques with several novel tricks to obtain the desired results. Using our techniques, we also give an optimal $\Omega(M^{1/3})$ lower bound for the set equality problem. This lower bound can be used to improve the relationship between classical randomized query complexity and quantum query complexity for so-called permutation-symmetric functions.

arXiv:1312.1027Quantum Information and ComputationMay 1, 201599 citations

We show that any quantum algorithm deciding whether an input function

f

from

[n]

[n]

is 2-to-1 or almost 2-to-1 requires

\Theta(n)

queries to

f

. The same lower bound holds for determining whether or not a function

f

from

[2n-2]

[n]

is surjective. These results yield a nearly linear

\Omega(n/\log n)

lower bound on the quantum query complexity of

\cl{AC}^0

. The best previous lower bound known for any

\cl{AC^0}

function was the

\Omega ((n/\log n)^{2/3})

bound given by Aaronson and Shi's

\Omega(n^{2/3})

lower bound for the element distinctness problem.

We show that any quantum algorithm deciding whether an input function

f

from

[n]

[n]

is 2-to-1 or almost 2-to-1 requires

Θ(n)

queries to

f

. The same lower bound holds for determining whether or not a function

f

from

[2n-2]

[n]

is surjective. These results yield a nearly linear

Ω(n/\log n)

lower bound on the quantum query complexity of $\cl{AC}^0$. The best previous lower bound known for any $\cl{AC^0}$ function was the

Ω((n/\log n)^{2/3})

bound given by Aaronson and Shi's

Ω(n^{2/3})

lower bound for the element distinctness problem.

The Element Distinctness problem is to decide whether each character of an input string is unique. The quantum query complexity of Element Distinctness is known to be

Θ(N^{2/3})

; the polynomial method gives a tight lower bound for any input alphabet, while a tight adversary construction was only known for alphabets of size

Ω(N^2)

. We construct a tight

Ω(N^{2/3})

adversary lower bound for Element Distinctness with minimal non-trivial alphabet size, which equals the length of the input. This result may help to improve lower bounds for other related query problems.

Given oracle access to an unknown unitary

U=e^{iH}

, the fractional query problem asks how many queries are required to implement a noninteger power

U^t=e^{itH}

0<t<1

, when the spectrum is separated from the branch cut by a gap

δ

. Quantum singular value transformation gives an upper bound of

O\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)

queries for approximation error

\varepsilon

. We prove a matching lower bound for arbitrary query algorithms. Our argument reduces any

N

-query circuit to the approximation of

e^{itθ}

by a trigonometric polynomial with degree bounded by

O(N)

, together with Remez inequality. This allows us to establish the lower bound of

Ω_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)

. Consequently, the optimal query complexity for fractional query problem is

Θ_τ\!\left(\frac{1}δ\log\frac{1}{\varepsilon}\right)

, showing that the known QSVT construction is asymptotically optimal. We also give an alternative lower bound proof based on constructing a linear functional that annihilates the approximant space, yielding a

Ω_τ\!\left(\log\frac{1}{\varepsilon}\right)

bound uniform to

δ

Query complexity is a model of computation in which we have to compute a function

f(x_1, \ldots, x_N)

of variables

x_i

which can be accessed via queries. The complexity of an algorithm is measured by the number of queries that it makes. Query complexity is widely used for studying quantum algorithms, for two reasons. First, it includes many of the known quantum algorithms (including Grover's quantum search and a key subroutine of Shor's factoring algorithm). Second, one can prove lower bounds on the query complexity, bounding the possible quantum advantage. In the last few years, there have been major advances on several longstanding problems in the query complexity. In this talk, we survey these results and related work, including: - the biggest quantum-vs-classical gap for partial functions (a problem solvable with 1 query quantumly but requiring

Ω(\sqrt{N})

queries classically); - the biggest quantum-vs-determistic and quantum-vs-probabilistic gaps for total functions (for example, a problem solvable with

M

queries quantumly but requiring

\tildeΩ(M^{2.5})

queries probabilistically); - the biggest probabilistic-vs-deterministic gap for total functions (a problem solvable with

M

queries probabilistically but requiring

\tildeΩ(M^{2})

queries deterministically); - the bounds on the gap that can be achieved for subclasses of functions (for example, symmetric functions); - the connections between query algorithms and approximations by low-degree polynomials.

A collision for a function

f

is two distinct inputs

x_1\neq x_2

such that

f

outputs the same value on both inputs:

f(x_1)=f(x_2)

. The quantum query complexity of finding collisions has been shown~\cite{BHT1997,AS2004, Ambainis05, Kutin05} in some settings to be

\Theta(N^{1/3})

; however, these results do not apply to random functions. The issues are two-fold. First, the

\Omega(N^{1/3})

lower bound only applies when the domain is no larger than the co-domain, which precludes many of the cryptographically interesting applications. Second, most of the results in the literature only apply to

r

-to-1 functions, which are quite different from random functions. Understanding the collision problem for random functions is of great importance to cryptography, and we seek to fill the gaps of knowledge for this problem. To that end, we prove that, as expected, a quantum query complexity of

\Theta(N^{1/3})

holds for all interesting domain and co-domain sizes. Our proofs are simple, and combine existing techniques with several novel tricks to obtain the desired results. Using our techniques, we also give an optimal

\Omega(M^{1/3})

lower bound for the set equality problem. This lower bound can be used to improve the relationship between classical randomized query complexity and quantum query complexity for so-called permutation-symmetric functions.