Fetching the paper…
Reading the bibliography…
We present several families of total boolean functions which have exact quantum query complexity which is a constant multiple (between 1/2 and 2/3) of their classical query complexity, and show that optimal quantum algorithms for these functions cannot be obtained by simply computing parities of pairs of bits.
Covering radius – survey and recent results
G. Cohen, M. Karpovsky, H. Mattson, Jr., and J. Schatz · 1985
Earlier work this paper cites.
Matrix Analysis
R. A. Horn and C. R. Johnson · 1985
Earlier work this paper cites.
Rapid solution of problems by quantum computation
D. Deutsch and R. Jozsa · 1992
Earlier work this paper cites.
On the degree of Boolean functions as real polynomials
N. Nisan and M. Szegedy · 1994
Earlier work this paper cites.
Quantum complexity theory
E. Bernstein and U. Vazirani · 1997
Earlier work this paper cites.
An exact quantum polynomial-time algorithm for Simon’s problem
G. Brassard and P. Høyer · 1997
Earlier work this paper cites.
On the power of quantum computation
D. R. Simon · 1997
Earlier work this paper cites.
Quantum algorithms revisited
R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca · 1998
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.
A limit on the speed of quantum computation in determining parity
E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser · 1998
Earlier work this paper cites.
Exact learning when irrelevant variables abound
D. Guijarro, V. Lavín, and V. Raghavan · 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.
Complexity measures and decision tree complexity: a survey
H. Buhrman and R. de Wolf · 2002
Cited alongside, same era.
The quantum black-box complexity of majority
T. Hayes, S. Kutin, and D. van Melkebeek · 2002
Cited alongside, same era.
Quantum lower bound for Recursive Fourier Sampling
S. Aaronson · 2003
Cited alongside, same era.
Quantum query complexity and semi-definite programming
H. Barnum, M. Saks, and M. Szegedy · 2003
Cited alongside, same era.
Negative weights make adversaries stronger
P. Høyer, T. Lee, and R. Špalek · 2007
Later among the works it cites.
Quantum query algorithm constructions for computing AND, OR and MAJORITY boolean functions, 2007
Alina Vasilieva · 2007
Later among the works it cites.
Span-program-based quantum algorithm for evaluating formulas
B. Reichardt and R. Špalek · 2008
Later among the works it cites.
Exact quantum query algorithm for error detection code verification, 2009
Alina Vasilieva · 2009
Later among the works it cites.
Nonadaptive quantum query complexity
A. Montanaro · 2010
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
G. Midrijānis · 2004
Cited alongside, same era.
Lower bounds on quantum query complexity
P. Høyer and R. Špalek · 2005
Cited alongside, same era.
Polynomial degree vs. quantum query complexity
A. Ambainis · 2006
Cited alongside, same era.
Computing boolean functions: Exact quantum query algorithms and low degree polynomials, 2006
Alina Dubrovska and Taisija Mischenko-Slatenkova · 2006
Cited alongside, same era.
Source code used to calculate quantum query complexity
A. Montanaro, R. Jozsa, and G. Mitchison
Cited in the paper.
CVX: Matlab software for disciplined convex programming, version 1.21
M. Grant and S. Boyd · 2011
Closest in time.
Reflections for quantum query algorithms
B. Reichardt · 2011
Closest in time.
Superlinear advantage for exact quantum algorithms, 2012
A. Ambainis · 2012
Closest in time.
Exact quantum query complexity of EXACT and THRESHOLD, 2013
A. Ambainis, J. Iraids, and J. Smotrovs · 2013
Closest in time.