Single quantum querying of a database

Abstract

We present a class of fast quantum algorithms, based on Bernstein and Vazirani's parity problem, that retrieve the entire contents of a quantum database $Y$ in a single query. The class includes binary search problems and coin-weighing problems. Our methods far exceed the efficiency of classical algorithms which are bounded by the classical information-theoretic bound. We show the connection between classical algorithms based on several compression codes and our quantum-mechanical method.

Replaced with expanded version, 6 pages revtex, 12 November 1997. Replaced again to fix small typographical errors, submitted to Phys. Rev. A

References in corpus (2)

• Strengths and Weaknesses of Quantum Computing
• Phase Information in Quantum Oracle Computing

Cited by in corpus (30)

• Quantum computers can search arbitrarily large databases by a single query
• Sophisticated quantum search without entanglement
• Quantum discord and its allies: a review
• Quantum arithmetic with the Quantum Fourier Transform
• Quantum search without entanglement
• Grover's Quantum Search Algorithm for an Arbitrary Initial Amplitude Distribution
• Analysis of Generalized Grover's Quantum Search Algorithms Using Recursion Equations
• Implementation of a quantum algorithm to solve Bernstein-Vazirani's parity problem without entanglement on an ensemble quantum computer
• Optical implementation of Deutsch-Jozsa and Bernstein-Vazirani quantum algorithms in eight dimensions
• The effect of unitary noise on Grover's quantum search algorithm
• Characterization of pure quantum states of multiple qubits using the Groverian entanglement measure
• Configurable sublinear circuits for quantum state preparation
• Quantum Entanglement and the Communication Complexity of the Inner Product Function
• Quantum Oracle Interrogation: Getting all information for almost half the price
• Could Grover's quantum algorithm help in searching an actual database?
• Generalized Grover's algorithm for multiple phase inversion states
• Quantum Counterfeit Coin Problems
• Analysis of Grover's quantum search algorithm as a dynamical system
• An Introduction to Quantum Computing for Non-Physicists
• Optical implementations, oracle equivalence, and the Bernstein-Vazirani algorithm
• Algebraic analysis of quantum search with pure and mixed states
• A Quantum Computational Learning Algorithm
• Speedup of iterated quantum search by parallel performance
• Role of interference and entanglement in quantum neural processing
• Single-Step Quantum Search Using Problem Structure
• Simulation of static and random errors on Grover's search algorithm implemented in a Ising nuclear spin chain quantum computer with few qubits
• A quantum Goldreich-Levin theorem with cryptographic applications
• Measurement of an integral of a classical field with a single quantum particle
• A quantum algorithm for examining oracles
• qSIEVE: Efficient qLDPC Memory via Systolic Movement in Atom Arrays