It has been proved that almost all n-bit Boolean functions have exact classical query complexity n. However, the situation seemed to be very different when we deal with exact quantum query complexity. In this paper, we prove that almost all n-bit Boolean functions can be computed by an exact quantum algorithm with less than n queries. More exactly, we prove that ANDn is the only n-bit Boolean function, up to isomorphism, that requires n queries.

arXiv:1404.1684Quantum Information and ComputationApr 1, 201518 citations

arXiv:1211.0721

Superlinear advantage for exact quantum algorithms

Andris Ambainis

Published Nov 4, 2012• 2 citations

arXiv HTML PDF

Abstract

N

queries classically but can be computed with N/2 queries by an exact quantum algorithm. We present the first example of a Boolean function f(x_1, ..., x_N) for which exact quantum algorithms have superlinear advantage over the deterministic algorithms. Any deterministic algorithm that computes our function must use N queries but an exact quantum algorithm can compute it with O(N^{0.8675...}) queries.

DOI: 10.48550/arxiv.1211.0721

Related papers

Superlinear advantage for exact quantum algorithms

Andris Ambainis

A quantum algorithm is exact if, on any input data, it outputs the correct answer with certainty (probability 1). A key question is: how big is the advantage of exact quantum algorithms over their classical counterparts: deterministic algorithms. For total Boolean functions in the query model, the biggest known gap was just a factor of 2: PARITY of N input bits requires N queries classically but can be computed with N/2 queries by an exact quantum algorithm. We present the first example of a Boolean function f(x1, ..., xN) for which exact quantum algorithms have superlinear advantage over deterministic algorithms. Any deterministic algorithm that computes our function must use N queries but an exact quantum algorithm can compute it with O(N0.8675...) queries. A modification of our function gives a similar result for communication complexity: there is a function f which can be computed by an exact quantum protocol that communicates O(N^{0.8675...}) quantum bits but requires Omega(N) bits of communication for classical protocols.A quantum algorithm is exact if, on any input data, it outputs the correct answer with certainty (probability 1). A key question is: how big is the advantage of exact quantum algorithms over their classical counterparts: deterministic algorithms. For total Boolean functions in the query model, the biggest known gap was just a factor of 2: PARITY of N input bits requires N queries classically but can be computed with N/2 queries by an exact quantum algorithm. We present the first example of a Boolean function f(x1, ..., xN) for which exact quantum algorithms have superlinear advantage over deterministic algorithms. Any deterministic algorithm that computes our function must use N queries but an exact quantum algorithm can compute it with O(N0.8675...) queries. A modification of our function gives a similar result for communication complexity: there is a function f which can be computed by an exact quantum protocol that communicates O(N^{0.8675...}) quantum bits but requires Omega(N) bits of communication for classical protocols.

ACM Symposium on Theory of Computing (STOC)May 28, 201328 citations

Superlinear Advantage for Exact Quantum Algorithms

Andris Ambainis

A quantum algorithm is exact if, on any input data, it outputs the correct answer with certainty (probability 1). A key question is, how big is the advantage of exact quantum algorithms over their classical counterparts: deterministic algorithms? We present the first example of a total Boolean function $f(x_1,\ldots, x_N)$ for which exact quantum algorithms have superlinear advantage over deterministic algorithms. Any deterministic algorithm that computes our function must use $N$ queries but an exact quantum algorithm can compute it with $O(N^{0.8675\ldots})$ queries. A modification of our function gives a similar result for communication complexity: there is a function $f$ which can be computed by an exact quantum protocol that communicates $O(N^{0.8675\ldots}\log N)$ quantum bits but requires $\Omega(N)$ bits of communication for classical protocols.A quantum algorithm is exact if, on any input data, it outputs the correct answer with certainty (probability 1). A key question is, how big is the advantage of exact quantum algorithms over their classical counterparts: deterministic algorithms? We present the first example of a total Boolean function $f(x_1,\ldots, x_N)$ for which exact quantum algorithms have superlinear advantage over deterministic algorithms. Any deterministic algorithm that computes our function must use $N$ queries but an exact quantum algorithm can compute it with $O(N^{0.8675\ldots})$ queries. A modification of our function gives a similar result for communication complexity: there is a function $f$ which can be computed by an exact quantum protocol that communicates $O(N^{0.8675\ldots}\log N)$ quantum bits but requires $\Omega(N)$ bits of communication for classical protocols.

SIAM Journal on ComputingJan 1, 201622 citations

Characterization of exact one-query quantum algorithms (ii): for partial functions

Zekun Ye, Lvzhou Li

The query model (or black-box model) has attracted much attention from the communities of both classical and quantum computing. Usually, quantum advantages are revealed by presenting a quantum algorithm that has a better query complexity than its classical counterpart. For example, the well-known quantum algorithms including Deutsch-Jozsa algorithm, Simon algorithm and Grover algorithm all show a considerable advantage of quantum computing from the viewpoint of query complexity. Recently we have considered in (Phys. Rev. A. {\bf 101}, 02232 (2020)) the problem: what functions can be computed by an exact one-query quantum algorithm? This problem has been addressed for total Boolean functions but still open for partial Boolean functions. Thus, in this paper we continue to characterize the computational power of exact one-query quantum algorithms for partial Boolean functions by giving several necessary and sufficient conditions. By these conditions, we construct some new functions that can be computed exactly by one-query quantum algorithms but have essential difference from the already known ones. Note that before our work, the known functions that can be computed by exact one-query quantum algorithms are all symmetric functions, whereas the ones constructed in this papers are generally asymmetric.The query model (or black-box model) has attracted much attention from the communities of both classical and quantum computing. Usually, quantum advantages are revealed by presenting a quantum algorithm that has a better query complexity than its classical counterpart. For example, the well-known quantum algorithms including Deutsch-Jozsa algorithm, Simon algorithm and Grover algorithm all show a considerable advantage of quantum computing from the viewpoint of query complexity. Recently we have considered in (Phys. Rev. A. {\bf 101}, 02232 (2020)) the problem: what functions can be computed by an exact one-query quantum algorithm? This problem has been addressed for total Boolean functions but still open for partial Boolean functions. Thus, in this paper we continue to characterize the computational power of exact one-query quantum algorithms for partial Boolean functions by giving several necessary and sufficient conditions. By these conditions, we construct some new functions that can be computed exactly by one-query quantum algorithms but have essential difference from the already known ones. Note that before our work, the known functions that can be computed by exact one-query quantum algorithms are all symmetric functions, whereas the ones constructed in this papers are generally asymmetric.

arXiv:2008.11998Aug 27, 20201 citation

Properties and application of nondeterministic quantum query algorithms

Alina Dubrovska

Many quantum algorithms can be analyzed in a query model to compute Boolean functions where input is given by a black box. As in the classical version of decision trees, different kinds of quantum query algorithms are possible: exact, with bounded error and even nondeterministic. In this paper, we study the latter class of algorithms. We introduce a new notion in addition to already studied nondeterministic algorithms and introduce dual nondeterministic quantum query algorithms. We examine properties of such algorithms and prove relations with exact and nondeterministic quantum query algorithm complexity. As a result and as an example of the application of discovered properties, we demonstrate a gap of n vs. 2 between classical deterministic and dual nondeterministic quantum query complexity for a specific Boolean function. Finally, we show an approach how to construct examples where quantum nondeterministic complexity of an algorithm is O(1), however classical deterministic algorithm for the same function would require O(n) queries.Many quantum algorithms can be analyzed in a query model to compute Boolean functions where input is given by a black box. As in the classical version of decision trees, different kinds of quantum query algorithms are possible: exact, with bounded error and even nondeterministic. In this paper, we study the latter class of algorithms. We introduce a new notion in addition to already studied nondeterministic algorithms and introduce dual nondeterministic quantum query algorithms. We examine properties of such algorithms and prove relations with exact and nondeterministic quantum query algorithm complexity. As a result and as an example of the application of discovered properties, we demonstrate a gap of n vs. 2 between classical deterministic and dual nondeterministic quantum query complexity for a specific Boolean function. Finally, we show an approach how to construct examples where quantum nondeterministic complexity of an algorithm is O(1), however classical deterministic algorithm for the same function would require O(n) queries.

arXiv:quant-ph/0606248Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIEApr 27, 20073 citations

An improved quantum query algorithm for computing AND Boolean function

Alina Vasilieva, Taisia Mischenko-Slatenkova

We consider the quantum query model for computing Boolean functions. The definition of the function is known, but a black box contains the input X = (x1, x2, ..., xn). Black box can be accessed by querying xivalues. The goal is to develop an algorithm, which would compute the function value for arbitrary input using as few queries to the black box as possible. We present two different quantum query algorithms for computing the basic Boolean function - logical AND of two bits. Both algorithms use only one query to determine the function value. Correct answer probability for the first algorithm is 80%, but for the second algorithm it is 90%. To compute this function with the same probability in the classical model, two queries are necessary. We analyze algorithms implementation differences and propose a way to extend the first algorithm to compute AND of two functions.We consider the quantum query model for computing Boolean functions. The definition of the function is known, but a black box contains the input X = (x1, x2, ..., xn). Black box can be accessed by querying xivalues. The goal is to develop an algorithm, which would compute the function value for arbitrary input using as few queries to the black box as possible. We present two different quantum query algorithms for computing the basic Boolean function - logical AND of two bits. Both algorithms use only one query to determine the function value. Correct answer probability for the first algorithm is 80%, but for the second algorithm it is 90%. To compute this function with the same probability in the classical model, two queries are necessary. We analyze algorithms implementation differences and propose a way to extend the first algorithm to compute AND of two functions.

IEEE Congress on Evolutionary Computation (CEC)Jul 1, 20100 citations

Exact quantum algorithms have advantage for almost all Boolean functions

Andris Ambainis, Jozef Gruska, Shenggen Zheng

arXiv:1404.1684Quantum Information and ComputationApr 1, 201518 citations

N

f(x_1,\ldots, x_N)

for which exact quantum algorithms have superlinear advantage over deterministic algorithms. Any deterministic algorithm that computes our function must use

N

queries but an exact quantum algorithm can compute it with

O(N^{0.8675\ldots})

queries. A modification of our function gives a similar result for communication complexity: there is a function

f

which can be computed by an exact quantum protocol that communicates

O(N^{0.8675\ldots}\log N)

quantum bits but requires

\Omega(N)

bits of communication for classical protocols.