Bounds for Small-Error and Zero-Error Quantum Algorithms

Abstract

We present a number of results related to quantum algorithms with small error probability and quantum algorithms that are zero-error. First, we give a tight analysis of the trade-offs between the number of queries of quantum search algorithms, their error probability, the size of the search space, and the number of solutions in this space. Using this, we deduce new lower and upper bounds for quantum versions of amplification problems. Next, we establish nearly optimal quantum-classical separations for the query complexity of monotone functions in the zero-error model (where our quantum zero-error model is defined so as to be robust when the quantum gates are noisy). Also, we present a communication complexity problem related to a total function for which there is a quantum-classical communication complexity gap in the zero-error model. Finally, we prove separations for monotone graph properties in the zero-error and other error models which imply that the evasiveness conjecture for such properties does not hold for quantum computers.

11 pages, LaTeX. New title and some sections are rewritten. This version to appear in IEEE FOCS'99

References in corpus (4)

• Quantum Algorithms Revisited
• An Exact Quantum Polynomial-Time Algorithm for Simon's Problem
• Quantum Lower Bounds by Polynomials
• Complexity limitations on quantum computation

Cited by in corpus (16)

• An area law for 2D frustration-free spin systems
• Quantum Communication Complexity
• The Computational Complexity of Linear Optics
• An Investigation on Support Vector Clustering for Big Data in Quantum Paradigm
• Quantum Algorithms for the Triangle Problem
• Potential of quantum finite automata with exact acceptance
• Communication Complexity Lower Bounds by Polynomials
• The quantum query complexity of certification
• Span-program-based quantum algorithm for evaluating unbalanced formulas
• Circuit lower bounds for low-energy states of quantum code Hamiltonians
• A note on quantum algorithms and the minimal degree of epsilon-error polynomials for symmetric functions
• Adversary Lower Bound for the Orthogonal Array Problem
• What Can be Observed Locally? Round-based Models for Quantum Distributed Computing
• Quantum search of partially ordered sets
• Query complexity in expectation
• Query Complexity: Worst-Case Quantum Versus Average-Case Classical