Quantum lower bounds by quantum arguments

Abstract

We propose a new method for proving lower bounds on quantum query algorithms. Instead of a classical adversary that runs the algorithm with one input and then modifies the input, we use a quantum adversary that runs the algorithm with a superposition of inputs. If the algorithm works correctly, its state becomes entangled with the superposition over inputs. We bound the number of queries needed to achieve a sufficient entanglement and this implies a lower bound on the number of queries for the computation. Using this method, we prove two new $\Omega (\sqrt{N})$ lower bounds on computing AND of ORs and inverting a permutation and also provide more uniform proofs for several known lower bounds which have been previously proven via variety of different techniques.

14 pages, to appear at STOC'00

References in corpus (5)

• Strengths and Weaknesses of Quantum Computing
• Quantum Lower Bounds by Polynomials
• Quantum vs. Classical Communication and Computation
• How fast can a quantum computer search?
• Communication Complexity Lower Bounds by Polynomials

Cited by in corpus (9)

• Quantum query complexity of state conversion
• Quantum computation of discrete logarithms in semigroups
• Learning-Graph-Based Quantum Algorithm for k-distinctness
• Quantum Proofs for Classical Theorems
• Variations on Quantum Adversary
• All Quantum Adversary Methods are Equivalent
• Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound
• On the Power of Non-Adaptive Learning Graphs
• A universal adiabatic quantum query algorithm