Quantum computers can search arbitrarily large databases by a single query

Abstract

This paper shows that a quantum mechanical algorithm that can query information relating to multiple items of the database, can search a database in a single query (a query is defined as any question to the database to which the database has to return a (YES/NO) answer). A classical algorithm will be limited to the information theoretic bound of at least O(log N) queries (which it would achieve by using a binary search).

Several enhancements to the original paper

References in corpus (3)

• Quantum Mechanics helps in searching for a needle in a haystack
• Strengths and Weaknesses of Quantum Computing
• Single quantum querying of a database

Cited by in corpus (109)

• Quantum Computing in Molecular Magnets
• Quantum Teleportation is a Universal Computational Primitive
• Decoherence Free Subspaces for Quantum Computation
• Experimental realization of a quantum algorithm
• Benchmarking an 11-qubit quantum computer
• Quantum Communication through Spin Chain Dynamics: an Introductory Overview
• t$|$ket$⟩$ : A Retargetable Compiler for NISQ Devices
• Fundamentals of Quantum Information Theory
• Experimental Implementation of Discrete Time Quantum Random Walk on an NMR Quantum Information Processor
• Sophisticated quantum search without entanglement
• Quantum computation using electrons trapped by surface acoustic waves
• Quantum Adiabatic Brachistochrone
• Implementation of quantum search algorithm using classical Fourier optics
• Phase matching in quantum searching
• Quantum search without entanglement
• Quantum information processing and multiatom entanglement engineering with a thermal cavity
• Grover's Quantum Search Algorithm for an Arbitrary Initial Amplitude Distribution
• Calculating the Thermal Rate Constant with Exponential Speed-Up on a Quantum Computer
• A Self Assembled Nanoelectronic Quantum Computer Based on the Rashba Effect in Quantum Dots
• Implementation of a three-quantum-bit search algorithm
• Quantum Computation
• A Quantum Algorithm for Solving Linear Differential Equations: Theory and Experiment
• Quantum Search with Two-atom Collisions in Cavity QED
• Quantum walk-based search and centrality
• Virtual-photon-induced quantum phase gates for two distant atoms trapped in separate cavities
• Parallel Quantum Computing in a Single Ensemble Quantum Computer
• Effects of Noisy Oracle on Search Algorithm Complexity
• Quantum phase retrieval of a Rydberg wave packet using a half-cycle pulse
• Grover search with pairs of trapped ions
• Unconventional Rydberg pumping and applications in quantum information processing
• The manipulation of massive ro-vibronic superpositions using time-frequency-resolved coherent anti-Stokes Raman scattering (TFRCARS): from quantum control to quantum computing
• Quantum information processing with large nuclear spins in GaAs semiconductors
• The effect of unitary noise on Grover's quantum search algorithm
• Realization of logically labeled effective pure states for bulk quantum computation
• Spin-based quantum information processing with semiconductor quantum dots and cavity QED
• Characterization of pure quantum states of multiple qubits using the Groverian entanglement measure
• The Grover algorithm with large nuclear spins in semiconductors
• Quantum computing of molecular magnet Mn${}_{12}$
• Cluster-state preparation and multipartite entanglement analyzer with fermions
• Femtosecond data storage, processing and search using collective excitations of a macroscopic quantum state
• Engineering Entanglement between two cavity modes
• Simple scheme for two-qubit Grover search in cavity QED
• Unconventional strengthening of a bipartite entanglement of a mixed spin-(1/2,1) Heisenberg dimer achieved through Zeeman splitting
• Probabilistic quantum cloning via Greenberger-Horne-Zeilinger states
• Quantum Computer Emulator
• Entanglement between external degrees of freedom of atoms via Bragg deflection
• Quantum Algorithms for Solving Ordinary Differential Equations via Classical Integration Methods
• Quantum Computing for Fusion Energy Science Applications
• Quantum Oracle Interrogation: Getting all information for almost half the price
• Experimental and theoretical challenges for the trapped electron quantum computer
• One-way quantum computation with two-photon multiqubit cluster states
• Symmetry breaking/symmetry preserving circuits and symmetry restoration on quantum computers: A quantum many-body perspective
• FPGA-based electronic system for the control and readout of superconducting quantum processors
• Quantum Computing in a Macroscopic Dark Period
• Fault-Tolerant Code Switching Protocols for Near-Term Quantum Processors
• Experimental Realization of Nonadiabatic Holonomic Single-Qubit Quantum Gates with Two Dark Paths in a Trapped Ion
• Entangled biphoton generation in myelin sheath
• Multi-phase matching in the Grover algorithm
• Certainty and Uncertainty in Quantum Information Processing
• Spin systems dynamics and faults detection in threshold networks
• On the role of dealing with quantum coherence in amplitude amplification
• A More General Quantum Searching Algorithm And the Precise Formula of the Amplitude and the Non-symmetric Effects of Different Rotating Angles
• A Quick Glance at Quantum Cryptography
• Quantum forgery attacks on COPA,AES-COPA and marble authenticated encryption algorithms
• Realization of generalized quantum searching using nuclear magnetic resonance
• Quantum Entanglement involved in Grover's and Shor's algorithms: the four-qubit case
• Pulse-engineered Controlled-V gate and its applications on superconducting quantum device
• Quantum speed-up in solving the maximal clique problem
• Three-qubit Thermal Entanglement via Entanglement Swapping on Two-qubit Heisenberg XY chains
• Analysis of Grover's quantum search algorithm as a dynamical system
• Thermal quantum coherence of two-qutrit Heisenberg XXZ model with Herring-Flicker coupling and Dzyaloshinskii-Moriya interaction under magnetic field
• An algorithm for minimization of quantum cost
• Quantum computing with four-particle decoherence-free states in ion trap
• Algebraic analysis of quantum search with pure and mixed states
• Time and frequency domain solutions in an optical analogue of Grover's search algorithm
• Number Partitioning on a Quantum Computer
• Scalable quantum computing model in the circuit-QED lattice with circulator function
• Effect of qubit losses on Grover's quantum search algorithm
• Continuous-Time Quantum Walks on Directed Bipartite Graphs
• Using continuous measurement to protect a universal set of quantum gates within a perturbed decoherence-free subspace
• Quantum search degeneration under amplitude noise in queries to the oracle
• Enhancement of nonclassical properties of two qubits via deformed operators
• Solution to Satisfiability problem by a complete Grover search with trapped ions
• No-relationship between impossibility of faster-than-light quantum communication and distinction of ensembles with the same density matrix
• Implementing conventional and unconventional nonadiabatic geometric quantum gates via SU(2) transformations
• Implementation of Grover search algorithm with Josephson charge qubits
• Investigation of entanglement measures across the magnetization process of a highly frustrated spin-1/2 Heisenberg octahedral chain as a new paradigm of the localized-magnon approach
• Single-Step Quantum Search Using Problem Structure
• Optimized surface ion trap design for tight confinement and separation of ion chains
• Scalable quantum computation architecture using always-on Ising interactions via quantum feedforward
• How big is a quantum computer?
• Deep Reinforcement Learning with Quantum-inspired Experience Replay
• Hybrid entanglement caused by depletion of pump on output of spontaneous parametric down converter
• Blindly Factorizing 21 Quantumly
• Quantum forgery attacks against OTR structures based on Simon's algorithm
• Experimental protection of the coherence of a molecular qubit exceeding a millisecond
• Pure State Tomography with Fourier Transformation
• A class of non-classicality and non-Gaussianity of photon added three-mode GHZ-type entangled coherent states
• An Efficient Gradient Sensitive Alternate Framework for VQE with Variable Ansatz
• Discrete Fourier Transform in Nanostructures using Scattering
• Quantum Probes Reduce Measurements: Application to Distributed Grover Algorithm
• Implementation of quantum algorithms with resonant interactions
• Equations, States, and Lattices of Infinite-Dimensional Hilbert Spaces
• Error analysis of quantum operators written as a linear combination of permutations
• Phase-sensitive superposition of quantum states
• Quantum Algorithms in Cybernetics
• Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms
• Non-adiabatic Arbitary Geometric Gates in 2-qubit NMR Model
• Approaching unstructured search from function bilateral symmetry detection - A quantum algorithm