Quantum computers can search rapidly by using almost any transformation

Abstract

A quantum computer has a clear advantage over a classical computer for exhaustive search. The quantum mechanical algorithm for exhaustive search was originally derived by using subtle properties of a particular quantum mechanical operation called the Walsh-Hadamard (W-H) transform. This paper shows that this algorithm can be implemented by replacing the W-H transform by almost any quantum mechanical operation. This leads to several new applications where it improves the number of steps by a square-root. It also broadens the scope for implementation since it demonstrates quantum mechanical algorithms that can readily adapt to available technology.

This paper is an adapted version of quant-ph/9711043. It has been modified to make it more readable for physicists. 9 pages, postscript

References in corpus (1)

• Fault-tolerant quantum computation

Cited by in corpus (213)

• Quantum Amplitude Amplification and Estimation
• Grover Algorithm with zero theoretical failure rate
• Amplitude estimation without phase estimation
• Sophisticated quantum search without entanglement
• Quantum computation using electrons trapped by surface acoustic waves
• A different kind of quantum search
• Quantum Computing for High-Energy Physics: State of the Art and Challenges. Summary of the QC4HEP Working Group
• Emerging quantum computing algorithms for quantum chemistry
• The Evolution of Quantum Secure Direct Communication: On the Road to the Qinternet
• Implementation of quantum search algorithm using classical Fourier optics
• Phase matching in quantum searching
• Qibo: a framework for quantum simulation with hardware acceleration
• Entanglement Is Not Necessary for Perfect Discrimination between Unitary Operations
• Grover's Quantum Search Algorithm for an Arbitrary Initial Amplitude Distribution
• Optimized quantum random-walk search algorithms
• Sliding mode control of quantum systems
• Nested quantum search and NP-complete problems
• Efficient implementation of selective recoupling in heteronuclear spin systems using Hadamard matrices
• Three-electron spin qubits
• Approximate Quantum Fourier Transform with $O(n\log (n))$ T gates
• Quantum Search with Two-atom Collisions in Cavity QED
• Phase gate of one superconducting qubit simultaneously controlling n qubits in a cavity
• Quantum logic and entanglement by neutral Rydberg atoms: methods and fidelity
• Analysis of Generalized Grover's Quantum Search Algorithms Using Recursion Equations
• Accuracy vs run time in adiabatic quantum search
• A Review on Quantum Search Algorithms
• Quantum Software Engineering: Roadmap and Challenges Ahead
• Grover search with pairs of trapped ions
• Continuous-Variable Instantaneous Quantum Computing is hard to sample
• Simulation of many-body interactions by conditional geometric phases
• Analysis of Density Matrix reconstruction in NMR Quantum Computing
• Depth optimization of quantum search algorithms beyond Grover's algorithm
• Deterministic Grover search with a restricted oracle
• Near- and long-term quantum algorithmic approaches for vibrational spectroscopy
• The effect of unitary noise on Grover's quantum search algorithm
• Tradeoffs in the Quantum Search Algorithm
• Spin-based quantum information processing with semiconductor quantum dots and cavity QED
• Quantum Walks
• Grover's Quantum Search Algorithm for an Arbitrary Initial Mixed State
• Geometric Strategy for the Optimal Quantum Search
• Characterization of pure quantum states of multiple qubits using the Groverian entanglement measure
• Teleportation implementation of non-deterministic quantum logic operations by using linear optical elements
• Cluster-state preparation and multipartite entanglement analyzer with fermions
• Variational quantum amplitude estimation
• QASMBench: A Low-level QASM Benchmark Suite for NISQ Evaluation and Simulation
• Experimental NMR Realization of A Generalized Quantum Search Algorithm
• Implementation of efficient quantum search algorithms on NISQ computers
• Amplitude estimation via maximum likelihood on noisy quantum computer
• Generalized Quantum Search with Parallelism
• Thermal entanglement and teleportation in a two-qubit Heisenberg chain with Dzyaloshinski-Moriya anisotropic antisymmetric interaction
• Black-box Hamiltonian simulation and unitary implementation
• Coherence number as a discrete quantum resource
• Incoherent Control of Locally Controllable Quantum Systems
• Simple scheme for two-qubit Grover search in cavity QED
• Realization of quantum signal processing on a noisy quantum computer
• Quantum Computer Emulator
• Approximating many-body quantum states with quantum circuits and measurements
• Nonadiabatic holonomic multiqubit controlled gates
• Implementation of three-qubit Grover search in cavity QED
• Quantum Computing for Fusion Energy Science Applications
• Models of quantum computation and quantum programming languages
• FABLE: Fast Approximate Quantum Circuits for Block-Encodings
• Quantum search on graphene lattices
• Noise in Grover's Quantum Search Algorithm
• Delocalization border and onset of chaos in a model of quantum computation
• Fast Quantum Search Algorithms in Protein Sequence Comparison - Quantum Biocomputing
• Quantum algorithm for Feynman loop integrals
• Quantum error correction of systematic errors using a quantum search framework
• Critically damped quantum search
• Quantum learning by measurement and feedback
• Speedup of quantum state transfer by three- qubit interactions: Implementation by nuclear magnetic resonance
• Geometric Algebra and Information Geometry for Quantum Computational Software
• Quantum Searching via Entanglement and Partial Diffusion
• Quantum walks and quantum search on graphene lattices
• What is a quantum computer, and how do we build one?
• Multi-phase matching in the Grover algorithm
• General framework for quantum search algorithms
• Error tolerance in an NMR Implementation of Grover's Fixed-Point Quantum Search Algorithm
• A switchable controlled-NOT gate in a spin-chain NMR quantum computer
• The Limiting Distribution of Decoherent Quantum Random Walks
• Entanglement in a two-qubit Heisenberg XXX chain with x-components of Dzyaloshinskii-Moriya and Kaplan-Shekhtman-Entin-Wohlman-Aharony interactions
• Detected jump-error correcting quantum codes, quantum error designs and quantum computation
• On the role of dealing with quantum coherence in amplitude amplification
• Sudden death, birth and stable entanglement in a two-qubit Heisenberg XY spin chain
• Robust Logic Gates and Realistic Quantum Computation
• Quantum Chaos and Quantum Algorithms
• Modularization of multi-qubit controlled phase gate and its NMR implementation
• A More General Quantum Searching Algorithm And the Precise Formula of the Amplitude and the Non-symmetric Effects of Different Rotating Angles
• Quantum approximate Bayesian computation for NMR model inference
• Quantum algorithm for obtaining the eigenstates of a physical system
• Quantum Error Mitigation Relying on Permutation Filtering
• Effect of system level structure and spectral distribution of the environment on the decoherence rate
• Quantum search on noisy intermediate-scale quantum devices
• Quantum heuristic algorithm for traveling salesman problem
• Realization of generalized quantum searching using nuclear magnetic resonance
• Quantum Signal Processing for simulating cold plasma waves
• Quantum speed-up in solving the maximal clique problem
• Multiplex-controlled phase gate with qubits distributed in a multi-cavity system
• Quantum Bandits
• Simple implementation of a quantum search with trapped ions
• A General SU(2) Formulation for Quantum Searching with Certainty
• Quantum search on structured problems
• Strength and Weakness in Grover's Quantum Search Algorithm
• One-step implementation of a multi-target-qubit controlled-phase gate with photonic qubits encoded via eigenstates of the photon-number parity operator
• Quantum Amplitude Amplification Operators
• Synthesizing NMR analogues of Einstein-Podolsky-Rosen states using generalized Grover's algorithm
• Analysis of Grover's quantum search algorithm as a dynamical system
• Quantum Computing by Cooling
• Fixed-point Quantum Search for Different Phase Shifts
• An Ancilla Based Quantum Simulation Framework for Non-Unitary Matrices
• A Query-based Quantum Eigensolver
• A General Phase Matching Condition for Quantum Searching Algorithm
• The entanglement in one-dimensional random XY spin chain with Dzyaloshinskii-Moriya interaction
• Strongly trapped two-dimensional quantum walks
• Automatic Generation of an Efficient Less-Than Oracle for Quantum Amplitude Amplification
• A quantum phase gate implementation for trapped ions in thermal motion
• Geometric quantum gates via dark paths in Rydberg atoms
• Direct Application of the Phase Estimation Algorithm to Find the Eigenvalues of the Hamiltonians
• Quantum computing with four-particle decoherence-free states in ion trap
• Noisy quantum amplitude estimation without noise estimation
• Quantum associative memory with improved distributed queries
• Quantum phase estimation algorithms with delays: effects of dynamical phases
• Quantum-accessible reinforcement learning beyond strictly epochal environments
• Performance analysis of a hybrid agent for quantum-accessible reinforcement learning
• Quantum Fourier Iterative Amplitude Estimation
• Obtaining A Linear Combination of the Principal Components of a Matrix on Quantum Computers
• Quantum Speedup of the Dispersion and Codebook Design Problems
• One-step implementation of the genuine Fredkin gate in high-$Q$ coupled three-cavity arrays
• Algebraic analysis of quantum search with pure and mixed states
• The Representation of Natural Numbers in Quantum Mechanics
• Faster quantum searching with almost arbitrary operators
• A simple Example of Definitions of Truth, Validity, Consistency, and Completeness in Quantum Mechanics
• Entanglement control in one-dimensional $s=1/2$ random XY spin chain
• Tree Search and Quantum Computation
• Simple realization of a hybrid controlled-controlled-Z gate with photonic control qubits encoded via eigenstates of the photon-number parity operator
• Simulation of Grover's quantum search algorithm in a Ising nuclear spin chain quantum computer with first and second nearest neighbour couplings
• The Precise Formula in a Sine Function Form of the norm of the Amplitude and the Necessary and Sufficient Phase Condition for Any Quantum Algorithm with Arbitrary Phase Rotations
• Effect of qubit losses on Grover's quantum search algorithm
• Applications of the Adversary Method in Quantum Query Algorithms
• Quantum Multiplication Algorithm Based on the Convolution Theorem
• An intuitive Hamiltonian for quantum search
• Error Avoiding Quantum Codes and Dynamical Stabilization of Grover's Algorithm
• Fixed Phase Quantum Search Algorithm
• Two-level Quantum Walkers on Directed Graphs II: An Application to qRAM
• Quantum search degeneration under amplitude noise in queries to the oracle
• Fast quantum state transfer and entanglement for cavity-coupled many qubits via dark pathways
• Comment on 'Grover Search with Pairs of Trapped Ions'
• Quantum computers can search rapidly by using almost any selective transformations
• Solution to Satisfiability problem by a complete Grover search with trapped ions
• A Quantum Implementation Model for Artificial Neural Networks
• A classical limit of Grover's algorithm induced by dephasing: Coherence vs entanglement
• An Adaptive, Fixed-Point Version of Grover's Algorithm
• Decoherence induced by squeezing control errors in optical and ion trap holonomic quantum computations II
• Coherence Fraction in Grover Search Algorithm
• Quantum smoothed particle hydrodynamics algorithm inspired by quantum walks
• Quantum search in many-body interacting system with long-range interaction
• Optimization of probabilistic quantum search algorithm with a priori information
• Decoherence induced by squeezing control errors in optical and ion trap holonomic quantum computations
• Implementation of Grover search algorithm with Josephson charge qubits
• Self-protected adiabatic quantum computation
• Preparation of GHZ states via Grover's quantum searching algorithm
• Performance of Equal Phase-Shift Search for One Iteration
• An Optimized Quantum Maximum or Minimum Searching Algorithm and its Circuits
• Quantum search algorithm tailored to clause satisfaction problems
• A representation of complex rational numbers in quantum mechanics
• Fixed-point quantum continuous search algorithm with optimal query complexity
• Postprocessing can speed up general quantum search algorithms
• QReach: A Reachability Analysis Tool for Quantum Markov Chains
• Complementary-multiphase quantum search for all numbers of target items
• Fast atom-photon entangling gates with a superconducting coplanar waveguide
• Simulation of static and random errors on Grover's search algorithm implemented in a Ising nuclear spin chain quantum computer with few qubits
• Fast nuclear-spin entangling gates compatible with large-scale atomic arrays
• Near-deterministic quantum search algorithm without phase design
• Efficient Implementation and the Product State Representation of Numbers
• Quantum Circuit for Calculating Symmetrized Functions Via Grover-like Algorithm
• Quantum Algorithms with Fixed Points: The Case of Database Search
• Non-unitary Coupled Cluster Enabled by Mid-circuit Measurements on Quantum Computers
• Quantum Circuit for Calculating Mobius-like Transforms Via Grover-like Algorithm
• Voronoi Diagrams for Quantum States and Its Application to a Numerical Estimation of a Quantum Channel Capacity
• Continuous Variable Quantum Advantages and Applications in Quantum Optics
• Constant Time Quantum search Algorithm Over A Datasets: An Experimental Study Using IBM Q Experience
• Amplitude Amplification and Estimation using a Floquet system
• Quantum Realization of the Finite Element Method
• Tight Bounds for Inverting Permutations via Compressed Oracle Arguments
• A lower bound on the quantum query complexity of read-once functions
• Simplify proposal for realizing multiqubit tunable phase gate in circuit QED
• Cavity QED implementation of the multi-qubit refined Deutsch-Jozsa algorithm
• The universal quantum driving force to speed up a quantum computation -- The unitary quantum dynamics
• Deleting a marked item from an unsorted database with a single query
• Quantum Circuit for Calculating Mean Values Via Grover-like Algorithm
• Implementation of quantum algorithms with resonant interactions
• Noisy Grover's search algorithm
• Constant-Time Quantum Algorithm For The Unstructured Search Problem
• Asymptotic bounds on quantum partial search algorithm and its applications to parallel search
• Quantum Search with Prior Knowledge
• An intrinsic limitation on the size of quantum database
• Binary Subdivision for Quantum Search
• Efficient Quantum Algorithms related to Autocorrelation Spectrum
• One-step implementation of the Fredkin gate via quantum Zeno dynamics
• Dressed-state scheme for a fast CNOT gate
• Quantum Multi-object Search Algorithm with the Availability of Partial Information
• Multi-target-qubit unconventional geometric phase gate in a multi-cavity system
• Simultaneous intraportation of many quantum states within the quantum computing network
• A Quantum Genetic Algorithm with application to Cosmological Parameters Estimation
• Exact quantum search based on analytical multiphase matching for known number of target items and the experimental demonstration on IBM Q
• Quantum Computation
• The Signals and Systems Approach to Quantum Computation
• Use of Mathematical Logical Concepts in Quantum Mechanics: An Example
• Quantum Heaviside Eigen Solver
• Quantum reservoir computing for predicting and characterizing chaotic maps
• Grover's Algorithm with Diffusion and Amplitude Steering
• Realizing an $n$-target-qubit controlled phase gate in cavity QED: An approach without classical pulses
• Quantum Algorithms in Cybernetics