Fetching the paper…

Reading the bibliography…

2011

Quantum Adversary (Upper) Bound

Kimmel, Shelby

Original
PDF
Post on X

Understand

We describe a method to upper bound the quantum query complexity of Boolean formula evaluation problems, using fundamental theorems about the general adversary bound.

This nonconstructive method can give an upper bound on query complexity without producing an algorithm.
For example, we describe an oracle problem which we prove (non-constructively) can be solved in $O(1)$ queries, where the previous best quantum algorithm uses a polylogarithmic number of queries.
We then give an explicit $O(1)$-query algorithm for this problem based on span programs.

Quantum Adversary (Upper) Bound · Around

Built on

Probabilistic boolean decision trees and the complexity of evaluating game trees
Michael Saks and Avi Wigderson · 1986
Earlier work this paper cites.
Quantum lower bounds by quantum arguments
Andris Ambainis · 2000
Earlier work this paper cites.
Polynomial degree vs. quantum query complexity
Andris Ambainis · 2006
Earlier work this paper cites.
Negative weights make adversaries stronger
Peter Høyer, Troy Lee, and Robert S̆palek · 2007
Earlier work this paper cites.
A quantum algorithm for the hamiltonian nand tree
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann · 2008
Earlier work this paper cites.

Similar

Quantum complexities of ordered searching, sorting, and element distinctness
Peter Høyer, Jan Neerbek, and Yaoyun Shi · 2008
Cited alongside, same era.
Span-program-based quantum algorithm for evaluating formulas
Ben W. Reichardt and Robert S̆palek · 2008
Cited alongside, same era.
Discrete-query quantum algorithm for NAND trees
Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David Yeung · 2009
Cited alongside, same era.
Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function
Ben W. Reichardt · 2009
Cited alongside, same era.

Then

Symmetry-assisted adversaries for quantum state generation
Andris Ambainis, Loïck Magnin, Martin Roetteler, and Jérémie Roland · 2011
Closest in time.
Quantum query complexity of state conversion
Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert S̆palek, and Mario Szegedy · 2011
Closest in time.
Reflections for quantum query algorithms
Ben W. Reichardt · 2011
Closest in time.
Super-polynomial quantum speed-ups for boolean evaluation trees with hidden structure
Original
Bohua Zhan, Shelby Kimmel, and Avinatan Hassidim · 2012
Closest in time.

Beyond the bibliography

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

Open on alphaXiv

alphaXiv is searching for related work…