Quantum search by measurement

Abstract

We propose a quantum algorithm for solving combinatorial search problems that uses only a sequence of measurements. The algorithm is similar in spirit to quantum computation by adiabatic evolution, in that the goal is to remain in the ground state of a time-varying Hamiltonian. Indeed, we show that the running times of the two algorithms are closely related. We also show how to achieve the quadratic speedup for Grover's unstructured search problem with only two measurements. Finally, we discuss some similarities and differences between the adiabatic and measurement algorithms.

8 pages, 2 figures

References in corpus (13)

• Quantum Mechanics helps in searching for a needle in a haystack
• Strengths and Weaknesses of Quantum Computing
• Quantum Algorithms Revisited
• A quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors
• Quantum Search by Local Adiabatic Evolution
• Robustness of adiabatic quantum computation
• Efficient Simulation of Quantum Systems by Quantum Computers
• Simulations of Many-Body Quantum Systems by a Quantum Computer
• Quantum Adiabatic Evolution Algorithms versus Simulated Annealing
• Quantum computing via measurements only
• Two-qubit Projective Measurements are Universal for Quantum Computation
• Universal quantum computation with two- and three-qubit projective measurements
• Phase estimation as a quantum nondemolition measurement

Cited by in corpus (56)

• Spatial search by quantum walk
• Quantum Simulations of Classical Annealing Processes
• Near-optimal ground state preparation
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Simulation of quantum random walks using interference of classical field
• Preparing thermal states of quantum systems by dimension reduction
• A quantum algorithm to solve nonlinear differential equations
• Quantum Computing in Plato's Cave
• Quantum Walks
• Non-ergodic delocalized states for efficient population transfer within a narrow band of the energy landscape
• Zeno physics in ultrastrong circuit QED
• Quantum search with hybrid adiabatic-quantum walk algorithms and realistic noise
• Spectral Gap Amplification
• Constrained Optimization via Quantum Zeno Dynamics
• An energetic perspective on rapid quenches in quantum annealing
• Teleportation on a quantum dot array
• Decoherence in the dynamical quantum phase transition of the transverse Ising chain
• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
• Necessary and sufficient condition for quantum adiabatic evolution by unitary control fields
• Several natural BQP-Complete problems
• Measurement induced quantum walks on an IBM Quantum Computer
• Optimal parametrizations of adiabatic paths
• Continuous Time Quantum Walks in finite Dimensions
• Diagrammatic Approach to Quantum Search
• Analog quantum algorithms for the mixing of Markov chains
• Dynamics of dissipative Bose-Einstein condensation
• Non-Abelian Phases from a Quantum Zeno Dynamics
• Guided quantum walk
• Fast quantum algorithms for traversing paths of eigenstates
• Efficient population transfer via non-ergodic extended states in quantum spin glass
• Real-Time Simulation of Large Open Quantum Spin Systems driven by Measurements
• Robustness of controlled Hamiltonian approaches to unitary quantum gates
• Decoherence in a dynamical quantum phase transition
• Entangling quantum measurement and its properties
• Real-time simulation of non-equilibrium transport of magnetization in large open quantum spin systems driven by dissipation
• Quantum advantage from energy measurements of many-body quantum systems
• Quantum search in many-body interacting system with long-range interaction
• Grover Speedup from Many Forms of the Zeno Effect
• Fractal states in quantum information processing
• Postprocessing can speed up general quantum search algorithms
• Real-Time Evolution of Strongly Coupled Fermions driven by Dissipation
• Decoherence-assisted quantum driving
• A thermodynamic approach to optimization in complex quantum systems
• Depth scaling of unstructured search via quantum approximate optimization
• Optimal quantum transport on a ring via locally monitored chiral quantum walks
• Nonlinear Quantum Search
• Measurement-driven quantum computing: Performance of a 3-SAT solver
• A measurement driven analog of adiabatic quantum computation for frustration-free Hamiltonians
• Quantum Algorithms and Covering Spaces
• Optimization of the damped quantum search
• Tunable Tradeoff between Quantum and Classical Computation via Nonunitary Zeno-like Dynamics
• Quantum search in structured database using local adiabatic evolution and spectral methods
• Efficient quantum algorithm for solving structured problems via multi-step quantum computation
• Generalized quantum measurements. Part I: Information properties of soft quantum measurements
• Saving resources through repeat-until-success positive-operator-valued-measure measurements in quantum computation
• Monte Carlo Quantum Computing