A Limit on the Speed of Quantum Computation in Determining Parity

Abstract

Consider a function f which is defined on the integers from 1 to N and takes the values -1 and +1. The parity of f is the product over all x from 1 to N of f(x). With no further information about f, to classically determine the parity of f requires N calls of the function f. We show that any quantum algorithm capable of determining the parity of f contains at least N/2 applications of the unitary operator which evaluates f. Thus for this problem, quantum computers cannot outperform classical computers.

9 pages, latex

References in corpus (3)

• Quantum Mechanics helps in searching for a needle in a haystack
• Strengths and Weaknesses of Quantum Computing
• Quantum Algorithms Revisited

Cited by in corpus (65)

• Quantum algorithm for solving linear systems of equations
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Information and Computation: Classical and Quantum Aspects
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Exponential improvement in precision for simulating sparse Hamiltonians
• Quantum Lower Bounds by Polynomials
• Quantum Computers and Quantum Coherence
• Quantum Computing at the Frontiers of Biological Sciences
• An Introduction to Quantum Complexity Theory
• Improved Bounds on Quantum Learning Algorithms
• Improved Quantum Communication Complexity Bounds for Disjointness and Equality
• Local copying and local discrimination as a study for non-locality of a set
• Quantum Computation Beyond the Circuit Model
• On exact quantum query complexity
• Superdiffusive quantum stochastic walk definable of arbitrary directed graph
• Efficient simulation of sparse Markovian quantum dynamics
• Quantum complexities of ordered searching, sorting, and element distinctness
• Fragmented imaginary-time evolution for early-stage quantum signal processors
• Geometric quantum computation using fictitious spin- 1/2 subspaces of strongly dipolar coupled nuclear spins
• Quantum Hocus Pocus
• The quantum query complexity of read-many formulas
• Exact quantum query complexity of EXACT and THRESHOLD
• Quantum Database Search can do without Sorting
• Local Hamiltonians in Quantum Computation
• Characterization of exact one-query quantum algorithms
• Nondeterministic Quantum Query and Quantum Communication Complexities
• Quantum Computers Speed Up Classical with Probability Zero
• A Limit on the Speed of Quantum Computation for Insertion into an Ordered List
• The quantum query complexity of approximating the median and related statistics
• Information processing using three-qubit and qubit-qutrit encodings of noncomposite quantum systems
• Limitations on the simulation of non-sparse Hamiltonians
• Unbounded Error Quantum Query Complexity
• Characterizations of symmetrically partial Boolean functions with exact quantum query complexity
• Quantum and classical query complexities of functions of matrices
• Complexity of Digital Quantum Simulation in the Low-Energy Subspace: Applications and a Lower Bound
• Quantum algorithms for powering stable Hermitian matrices
• Optimal parallel quantum query algorithms
• Speedup of iterated quantum search by parallel performance
• The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver
• Optimal quantum algorithm for polynomial interpolation
• Exact quantum query complexity of ${\mathrm{EXACT}}_{\mathrm{k},\mathrm{l}}^{\mathrm{n}}$
• Efficient Quantum Algorithms for Analyzing Large Sparse Electrical Networks
• Solving the quantum search problem in polynomial time on an NMR quantum computer
• Quantum Oracle Classification - The Case of Group Structure
• Universal construction for the unsorted quantum search algorithms
• Optimal quantum query bounds for almost all Boolean functions
• On the solution of trivalent decision problems by quantum state identification
• Exact quantum algorithms have advantage for almost all Boolean functions
• Orthogonal vector computations
• Quantum queries associated with equi-partitioning of states and multipartite relational encoding across space-time
• Quantum Lower Bounds by Sample-to-Query Lifting
• Comparative Computational Strength of Quantum Oracles
• Quantum Communication-Query Tradeoffs
• Quantum speed limits in dephasing dynamics of a qubit system coupled to thermal environments
• Vector computation
• Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case
• Quantum algorithms for search with wildcards and combinatorial group testing
• On the uselessness of quantum queries
• A note on quantum black-box complexity of almost all Boolean functions
• Quantum advantage by relational queries about physically realizable equivalence classes
• A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs
• Quantum Computation
• Quantum Advantage in Identifying the Parity of Permutations with Certainty
• Physics and metaphysics looks at computation
• Nonadaptive quantum query complexity