Fetching the paper…

Reading the bibliography…

2009

Nonadaptive quantum query complexity

Montanaro, Ashley

Original
PDF
Post on X

Understand

We study the power of nonadaptive quantum query algorithms, which are algorithms whose queries to the input do not depend on the result of previous queries.

First, we show that any bounded-error nonadaptive quantum query algorithm that computes some total boolean function depending on n variables must make Omega(n) queries to the input in total.
Second, we show that, if there exists a quantum algorithm that uses k nonadaptive oracle queries to learn which one of a set of m boolean functions it has been given, there exists a nonadaptive classical algorithm using O(k log m) queries to solve the same problem.
Thus, in the nonadaptive setting, quantum algorithms can achieve at most a very limited speed-up over classical query algorithms.

Nonadaptive quantum query complexity · Around

Built on

Queries and concept learning
D. Angluin · 1988
Earlier work this paper cites.
Quantum complexity theory
E. Bernstein and U. Vazirani · 1997
Earlier work this paper cites.
Quantum mechanics helps in searching for a needle in a haystack
L. Grover · 1997
Earlier work this paper cites.
On the power of quantum computation
D. R. Simon · 1997
Earlier work this paper cites.
Quantum oracle interrogation: Getting all information for almost half the price
W. van Dam · 1998
Earlier work this paper cites.

Similar

A limit on the speed of quantum computation in determining parity
E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser · 1998
Cited alongside, same era.
Grover’s quantum searching algorithm is optimal
C. Zalka · 1999
Cited alongside, same era.
Quantum lower bounds by polynomials
R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf · 2001
Cited alongside, same era.
Quantum versus classical learnability
R. Servedio and S. Gortler · 2001
Cited alongside, same era.
Complexity measures and decision tree complexity: a survey
H. Buhrman and R. de Wolf · 2002
Cited alongside, same era.

Then

Quantum identification of Boolean oracles
A. Ambainis, K. Iwama, A. Kawachi, H. Masuda, R. Putra, and S. Yamashita · 2004
Later among the works it cites.
An algorithmic argument for nonadaptive query complexity lower bounds on advised quantum computation
H. Nishimura and T. Yamakami · 2004
Later among the works it cites.
Lower bounds on quantum query complexity
P. Høyer and R. Špalek · 2005
Later among the works it cites.
Polynomial degree vs. quantum query complexity
A. Ambainis · 2006
Later among the works it cites.
Adversary lower bounds for nonadaptive quantum algorithms
Original
P. Koiran, J. Landes, N. Portier, and P. Yao · 2008
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…