Quantum Search by Local Adiabatic Evolution

Abstract

The adiabatic theorem has been recently used to design quantum algorithms of a new kind, where the quantum computer evolves slowly enough so that it remains near its instantaneous ground state which tends to the solution [Farhi et al., quant-ph/0001106]. We apply this time-dependent Hamiltonian approach to the Grover's problem, i. e., searching a marked item in an unstructured database. We find that, by adjusting the evolution rate of the Hamiltonian so as to keep the evolution adiabatic on each infinitesimal time interval, the total running time is of order $\sqrt{N}$, where $N$ is the number of items in the database. We thus recover the advantage of Grover's standard algorithm as compared to a classical search, scaling as $N$. This is in contrast with the constant-rate adiabatic approach developed by Farhi et al., where the requirement of adiabaticity is expressed only globally, resulting in a time of order $N$.

4 pages RevTex, 2 encapsulated Postscript figures

References in corpus (1)

• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem

Cited by in corpus (360)

• The theory of variational hybrid quantum-classical algorithms
• Adiabatic Quantum Computing
• Quantum Chemistry in the Age of Quantum Computing
• Shortcuts to adiabaticity: concepts, methods, and applications
• Programmable Quantum Simulations of Spin Systems with Trapped Ions
• Spatial search by quantum walk
• Quantum Annealing and Analog Quantum Computation
• Quantum computing for finance: overview and prospects
• Optimal Control at the Quantum Speed Limit
• Robustness of adiabatic quantum computation
• High-fidelity quantum driving
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• On the relationship between continuous- and discrete-time quantum walk
• Mathematical Foundation of Quantum Annealing
• Bounds for the adiabatic approximation with applications to quantum computation
• Solving strongly correlated electron models on a quantum computer
• Scalable Architecture for a Room Temperature Solid-State Quantum Information Processor
• Fast-forward of adiabatic dynamics in quantum mechanics
• Computational Role of Multiqubit Tunneling in a Quantum Annealer
• Fast adiabatic qubit gates using only ${\sigma }_z$ control
• Adiabatic Quantum Simulation of Quantum Chemistry
• Consistency of the Adiabatic Theorem
• A Quantum Adiabatic Algorithm for Factorization and Its Experimental Implementation
• Quantum Adiabatic Brachistochrone
• Decoherence in adiabatic quantum computation
• Quantitative conditions do not guarantee the validity of the adiabatic approximation
• Adiabatic quantum dynamics of a random Ising chain across its quantum critical point
• Adiabatic approximation with exponential accuracy for many-body systems and quantum computation
• Near-optimal quantum circuit for Grover's unstructured search using a transverse field
• Towards quantum simulation with circular Rydberg atoms
• Hybrid quantum-classical algorithms in the noisy intermediate-scale quantum era and beyond
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Quantum annealing with antiferromagnetic fluctuations
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Optimal Protocols in Quantum Annealing and QAOA Problems
• Energy gaps in quantum first-order mean-field-like transitions: The problems that quantum annealing cannot solve
• Quantum adiabatic machine learning
• First Order Quantum Phase Transition in Adiabatic Quantum Computation
• Thermally assisted adiabatic quantum computation
• Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
• Quantum Machine Learning in High Energy Physics
• Understanding Quantum Tunneling through Quantum Monte Carlo Simulations
• Adiabatic quantum algorithm for search engine ranking
• Noise resistance of adiabatic quantum computation using random matrix theory
• Adiabatic Quantum Computing for Random Satisfiability Problems
• Quantum walk approach to search on fractal structures
• Fast quasi-adiabatic dynamics
• Intrinsic geometry of quantum adiabatic evolution and quantum phase transitions
• Decoherence in adiabatic quantum computation
• Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
• SU(2) lattice gauge theory on a quantum annealer
• Scaling and diabatic effects in quantum annealing with a D-Wave device
• Quantum search by measurement
• Tunneling and speedup in quantum optimization for permutation-symmetric problems
• Review: Quantum Metrology and Sensing with Many-Body Systems
• Speeding up critical system dynamics through optimized evolution
• Adiabatic quantum algorithms as quantum phase transitions: first versus second order
• Best-case performance of quantum annealers on native spin-glass benchmarks: How chaos can affect success probabilities
• Universality of Entanglement and Quantum Computation Complexity
• Multivariable Optimization: Quantum Annealing & Computation
• On quantum mean-field models and their quantum annealing
• Experimental Performance of a Quantum Simulator: Optimizing Adiabatic Evolution and Identifying Many-Body Ground States
• Improved Error-Scaling for Adiabatic Quantum State Transfer
• Accuracy vs run time in adiabatic quantum search
• A Review on Quantum Search Algorithms
• Avoiding barren plateaus via transferability of smooth solutions in Hamiltonian Variational Ansatz
• Role of Single Qubit Decoherence Time in Adiabatic Quantum Computation
• Temperature scaling law for quantum annealing optimizers
• Time-dependent unbounded Hamiltonian simulation with vector norm scaling
• General error estimate for adiabatic quantum computing
• Exponential complexity of an adiabatic algorithm for an NP-complete problem
• Reverse quantum annealing of the $p$-spin model with relaxation
• Error suppression and error correction in adiabatic quantum computation I: techniques and challenges
• Unification and limitations of error suppression techniques for adiabatic quantum computing
• Counterdiabatic driving in the quantum annealing of the $p$-spin model: a variational approach
• Dissipation in adiabatic quantum computers: Lessons from an exactly solvable model
• Variationally Learning Grover's Quantum Search Algorithm
• Fast adiabatic evolution by oscillating initial Hamiltonians
• Necessary Condition for the Quantum Adiabatic Approximation
• Adiabatic quantum computation and quantum phase transitions
• Improving quantum annealing of the ferromagnetic $p$-spin model through pausing
• 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
• Nested Quantum Annealing Correction
• Adiabatic Spectroscopy and a Variational Quantum Adiabatic Algorithm
• Quantum pattern recognition with liquid-state nuclear magnetic resonance
• Possible implementation of adiabatic quantum algorithm with superconducting flux qubits
• Quantum optimization via four-body Rydberg gates
• Quantum search with hybrid adiabatic-quantum walk algorithms and realistic noise
• Robustness of the adiabatic quantum search
• Quantum circuit implementation of the Hamiltonian versions of Grover's algorithm
• Error suppression and error correction in adiabatic quantum computation II: non-equilibrium dynamics
• Graph isomorphism and adiabatic quantum computing
• Non-Markovian decoherence in the adiabatic quantum search algorithm
• Algorithmic approach to adiabatic quantum optimization
• Algorithm engineering for a quantum annealing platform
• Quantum Adiabatic Algorithm Design using Reinforcement Learning
• Constant-adiabaticity RF-pulses for generating long-lived singlet spin states in NMR
• The quantum adiabatic search with decoherence in the instantaneous energy eigenbasis
• Scaling of running time of quantum adiabatic algorithm for propositional satisfiability
• Improved Error Bounds for the Adiabatic Approximation
• Lyapunov control-inspired strategies for quantum combinatorial optimization
• An energetic perspective on rapid quenches in quantum annealing
• Quantum Gates with Controlled Adiabatic Evolutions
• Probing Entanglement in Adiabatic Quantum Optimization with Trapped Ions
• Why and when is pausing beneficial in quantum annealing?
• Decoherence in the dynamical quantum phase transition of the transverse Ising chain
• Genetic optimization of quantum annealing
• Effect of Local Minima on Adiabatic Quantum Optimization
• A modified quantum adiabatic evolution for the Deutsch-Jozsa problem
• Exploring adiabatic quantum trajectories via optimal control
• Testing quantum adiabaticity with quench echo
• Energetic cost of superadiabatic quantum computation
• Quantum control of hole spin qubits in double quantum dots
• Relaxation vs. adiabatic quantum steady state preparation: which wins?
• Accelerating adiabatic protocols for entangling two qubits in circuit QED
• High Fidelity Adiabatic Quantum Computation via Dynamical Decoupling
• Eigenstate Tracking in Open Quantum Systems
• The Feynman-Kitaev computer's clock: bias, gaps, idling and pulse tuning
• Optimal quantum annealing: A variational shortcut to adiabaticity approach
• Adiabatic quantum search algorithm for structured problems
• Experimental implementation of local adiabatic evolution algorithms by an NMR quantum information processor
• Schedule path optimization for quantum annealing and adiabatic quantum computing
• Geometric Algebra and Information Geometry for Quantum Computational Software
• What is a quantum computer, and how do we build one?
• Long-range quantum gates using dipolar crystals
• Constant-adiabaticity ultralow magnetic field manipulations of parahydrogen-induced polarization: application to an AA'X spin system
• Direct comparison of quantum and simulated annealing on a fully-connected Ising ferromagnet
• Analog Nature of Quantum Adiabatic Unstructured Search
• On the adiabatic condition and the quantum hitting time of Markov chains
• Hamiltonian engineering for adiabatic quantum computation: Lessons from shortcuts to adiabaticity
• Scaling Advantage in Approximate Optimization with Quantum Annealing
• Optimal suppression of defect generation during a passage across a quantum critical point
• Quantum annealing speedup over simulated annealing on random Ising chains
• Controlled-Controlled-Phase Gates for Superconducting Qubits Mediated by a Shared Tunable Coupler
• Adiabatic quantum search with atoms in a cavity driven by lasers
• Adiabatic preparation without Quantum Phase Transitions
• An Integrated Programming and Development Environment for Adiabatic Quantum Optimization
• Optimal Control for Closed and Open System Quantum Optimization
• Adiabatic Quantum Search in Open Systems
• Analytical solution for nonadiabatic quantum annealing to arbitrary Ising spin Hamiltonian
• Period Finding with Adiabatic Quantum Computation
• Adiabatic Quantum Computation with a 1D projector Hamiltonian
• Shortcuts to adiabaticity: theoretical framework, relations between different methods, and versatile approximations
• Fixed-Point Adiabatic Quantum Search
• Application of Pontryagin's Minimum Principle to Grover's Quantum Search Problem
• A solvable model of quantum random optimization problems
• Resonant shortcuts for adiabatic rapid passage with only $z$-field control
• Faster than Classical Quantum Algorithm for dense Formulas of Exact Satisfiability and Occupation Problems
• Effects of dissipation in an adiabatic quantum search algorithm
• Optimal parametrizations of adiabatic paths
• De-Signing Hamiltonians for Quantum Adiabatic Optimization
• Robust Quantum Control for Adiabatic Quantum Computation
• Adiabatic evolution under quantum control
• Nonadiabatic quantum state engineering driven by fast quench dynamics
• The Travelling Salesman Problem and Adiabatic Quantum Computation: An Algorithm
• On The Power Of Coherently Controlled Quantum Adiabatic Evolutions
• Adiabatic Quantum Optimization for Associative Memory Recall
• Speeding up adiabatic passage with an optimal modified Roland-Cerf protocol
• Optimal Thermometers with Spin Networks
• Error Reduction in Quantum Annealing using Boundary Cancellation: Only the End Matters
• Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm
• Adiabatic Quantum Transistors
• Faster annealing schedules for quantum annealing
• Lower Bounds on Quantum Annealing Times
• Standard quantum annealing outperforms adiabatic reverse annealing with decoherence
• Adiabatic quantum optimization in presence of discrete noise: Reducing the problem dimensionality
• Singularity of Berry Connections Inhibits the Accuracy of Adiabatic Approximation
• Dynamics of the quantum search and quench-induced first-order phase transitions
• A hybrid classical-quantum approach to solve the heat equation using quantum annealers
• Error suppression in adiabatic quantum computing with qubit ensembles
• Practical designs for permutation symmetric problem Hamiltonians on hypercubes
• Improved Bounds for Eigenpath Traversal
• Continuous-Time Quantum Algorithms for Unstructured Problems
• Discretized quantum adiabatic process for free fermions and comparison with the imaginary-time evolution
• Demonstrating Majorana non-Abelian properties using fast adiabatic charge-transfer
• Macroscopic Hyperpolarization Enhanced with Quantum Optimal Control
• Diabatic Quantum Annealing for the Frustrated Ring Model
• Optimal Hamiltonian simulation for time-periodic systems
• Theorem on the existence of a nonzero energy gap in adiabatic quantum computation
• Quantum Computing by Cooling
• Quantum search by partial adiabatic evolution
• Counterdiabatic Reverse Annealing
• Quantum control by effective counterdiabatic driving
• Reservoir-engineering shortcuts to adiabaticity
• Guided quantum walk
• Quantum Sampling Algorithms, Phase Transitions, and Computational Complexity
• Exponentially-enhanced quantum sensing with many-body phase transitions
• Quantum search by parallel eigenvalue adiabatic passage
• A Benchmarking Study of Quantum Algorithms for Combinatorial Optimization
• Customized quantum annealing schedules
• Simulating highly nonlocal Hamiltonians with less nonlocal Hamiltonians
• Irreconcilable Difference Between Quantum Walks and Adiabatic Quantum Computing
• Non adiabatic quantum search algorithms
• Patch-planting spin-glass solution for benchmarking
• Optimizing adiabatic quantum pathways via a learning algorithm
• Diagonal Catalysts in Quantum Adiabatic Optimization
• Deep recurrent networks predicting the gap evolution in adiabatic quantum computing
• Ultrafast critical ground state preparation via bang-bang protocols
• Elementary Proof of QAOA Convergence
• Deep learning optimal quantum annealing schedules for random Ising models
• SchWARMA: A model-based approach for time-correlated noise in quantum circuits
• Dynamical quantum phase transitions
• Symmetry-Protected Quantum Adiabatic Evolution in Spontaneous Symmetry-Breaking Transitions
• How Fast Can Quantum Annealers Count?
• Adiabatic Rotation, Quantum Search and Preparation of Superposition States
• Many-Qudit representation for the Travelling Salesman Problem Optimisation
• Quantum lower and upper speed limits
• A Class of Time-Energy Uncertainty Relations for Time-dependent Hamiltonians
• Optimizing Quantum Adiabatic Algorithm
• Simulations of the adiabatic quantum optimization for the Set Partition Problem
• Non-Hermitian Quantum Annealing in the Ferromagnetic Ising Model
• Quantum search using non-Hermitian adiabatic evolution
• Sensitivity of quantum speedup by quantum annealing to a noisy oracle
• Grover like Operator Using Only Single-Qubit Gates
• Adiabatic Quantum Computing with Phase Modulated Laser Pulses
• How to Compute Using Quantum Walks
• Quantum battery supercharging via counter-diabatic dynamics
• Enhancing quantum annealing performance by a degenerate two-level system
• Robust quantum searching with spontaneously decaying qubits
• Adiabatic quantum computation along quasienergies
• Problem-Size Independent Angles for a Grover-Driven Quantum Approximate Optimization Algorithm
• Trapped-ion Fock state preparation by potential deformation
• Analog Grover search by adiabatic passage in a cavity-laser-atom system
• Measuring adiabaticity in non-equilibrium quantum systems
• Non-Adiabatic Quantum Optimization for Crossing Quantum Phase Transitions
• Fast digital methods for adiabatic state preparation
• Realizable Quantum Adiabatic Search
• Scaling of errors in digitized counterdiabatic driving
• On models of nonlinear evolution paths in adiabatic quantum algorithms
• Theoretical survey of unconventional quantum annealing methods applied to adifficult trial problem
• Decoherence in a dynamical quantum phase transition
• Digital-analog quantum learning on Rydberg atom arrays
• Comparing the hardness of MAX 2-SAT problem instances for quantum and classical algorithms
• Beyond Quantum Annealing: Optimal control solutions to MaxCut problems
• Fast quantum state preparation and bath dynamics using non-Gaussian variational ansatz and quantum optimal control
• Perfect stimulated Raman adiabatic passage with imperfect finite-time pulses
• How Quantum is the Speedup in Adiabatic Unstructured Search?
• The relationship between minimum gap and success probability in adiabatic quantum computing
• Probing nonlinear adiabatic paths with a universal integrator
• Implementation of many-qubit Grover search with trapped ultracold ions
• Robust Preparation of Many-body Ground States in Jaynes-Cummings Lattices
• Why adiabatic quantum annealing is unlikely to yield speed-up
• Bounding first-order quantum phase transitions in adiabatic quantum computing
• The quantum annealing gap and quench dynamics in the exact cover problem
• Robust quantum control by smooth quasi-square pulses
• Resonant Quantum Search with Monitor Qubits
• Adiabatic quantum trajectories in engineered reservoirs
• Counterdiabatic Driving with Performance Guarantees
• Robust Diabatic Quantum Search by Landau-Zener-Stückelberg Oscillations
• Bounds on quantum adiabaticity in driven many-body systems from generalized orthogonality catastrophe and quantum speed limit
• On the efficiency of Hamiltonian-based quantum computation for low-rank matrices
• Quantum Algorithm to Solve Satisfiability Problems
• Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation
• Minimal action control method in quantum critical models
• Quantum search in many-body interacting system with long-range interaction
• Hard instance learning for quantum adiabatic prime factorization
• Quantum thermodynamic advantage in work extraction from steerable quantum correlations
• Solving Satisfiability Problems by the Ground-State Quantum Computer
• Grover Speedup from Many Forms of the Zeno Effect
• Noise-tolerant quantum speedups in quantum annealing without fine tuning
• Information Geometric Aspects of Probability Paths with Minimum Entropy Production for Quantum State Evolution
• A necessary condition for quantum adiabaticity applied to the adiabatic Grover search
• Self-protected adiabatic quantum computation
• Difference between quantum annealing by imaginary-time and real-time Schrödinger equation of Grover's search
• The Detectability Lemma and Quantum Gap Amplification
• Quantum techniques for eigenvalue problems
• Virtual mitigation of coherent non-adiabatic transitions by echo verification
• Lagrangian Duality in Quantum Optimization: Overcoming QUBO Limitations for Constrained Problems
• Speeding up Quantum Annealing with Engineered Dephasing
• Comment on Partial Adiabatic Quantum Search
• Generalized fast quasi-adiabatic population transfer for improved qubit readout, shuttling, and noise mitigation
• Quantum algorithm of a set of quantum 2-sat problem
• The speed of Markovian relaxation towards the ground state
• Performance of Equal Phase-Shift Search for One Iteration
• A relation between fidelity and quantum adiabatic evolution
• Polynomial Time Algorithms for Estimating Spectra of Adiabatic Hamiltonians
• How to experimentally evaluate the adiabatic condition for quantum annealing
• Physical consequences of P$\ne$NP and the DMRG-annealing conjecture
• Homological Description of the Quantum Adiabatic Evolution With a View Toward Quantum Computations
• Hilbert Space Average Method and adiabatic quantum search
• Continuous-time quantum optimisation without the adiabatic principle
• Quantum adiabatic optimization without heuristics
• Lower bounds for adiabatic quantum algorithms by quantum speed limits
• Investigating the potential for a limited quantum speedup on protein lattice problems
• Limitations of some simple adiabatic quantum algorithms
• Coherent population transfer via state-independent quasi-adiabatic dynamics
• Zeno-effect Computation: Opportunities and Challenges
• Quantum Adiabatic Computation and the Travelling Salesman Problem
• Approximating maximum independent set on Rydberg atom arrays using local detunings
• Robust Coherent Superposition of States using Quasiadiabatic Inverse Engineering
• The Short Path Algorithm Applied to a Toy Model
• A thermodynamic approach to optimization in complex quantum systems
• Enhancing the efficiency of adiabatic quantum computations
• Entropy Computing, A Paradigm for Optimization in Open Photonic Systems
• Validating a Two Qubit Non-Stoquastic Hamiltonian in Quantum Annealing
• Error-run-time trade-off in the adiabatic approximation beyond scaling relations
• Can magnetism-assisted quasiperiodic structures in Russell-FeS `bubbles' offer a quantum coherent origin of life?
• Rapid adiabatic gating for capacitively coupled quantum dot hybrid qubits without barrier control
• High-fidelity quantum control via Autler-Townes splitting
• Entanglement and Adiabatic Quantum Computation
• Information-Theoretic Meaning of Quantum Information Flow and Its Applications to Amplitude Amplification Algorithms
• Quantum annealing showing an exponentially small success probability despite a constant energy gap with polynomial energy
• Efficiency of Ground State Quantum Computer
• Quench dynamics in spin crossover induced by high pressure
• Quadratic fermionic interactions yield effective Hamiltonians for adiabatic quantum computing
• Superposition of Macroscopically Distinct States in Adiabatic Quantum Computation
• Inertial geometric quantum logic gates
• Fast-forward of quantum adiabatic dynamics in electro-magnetic field
• The Dynamics of Entanglement in the Adiabatic Search and Deutsch Algorithms
• Tighter Lower Bounds on Quantum Annealing Times
• Accelerating an adiabatic process by nonlinear sweeping
• General conditions for a quantum adiabatic evolution
• Machine-learning-inspired quantum control in many-body dynamics
• Learning-Driven Annealing with Adaptive Hamiltonian Modification for Solving Large-Scale Problems on Quantum Devices
• Analytic approach to the Landau-Zener problem in bounded parameter space
• Adiabatic quantum computing with parameterized quantum circuits
• Structured Adiabatic Quantum Search
• Eigenlevel statistics of the quantum adiabatic algorithm
• Lorentz Quantum Computer
• Unstructured Adiabatic Quantum Optimization: Optimality with Limitations
• Non-classical Role of Potential Energy in Adiabatic Quantum Annealing
• Non-Hermitian Adiabatic Quantum Optimization
• Analytical shortcuts to adiabaticity of weakly driven processes
• Noise Effects on Diabatic Quantum Annealing Protocols
• Pareto-optimality of pulses for robust population transfer in a ladder-type qutrit
• Noise tolerance via reinforcement: Learning a reinforced quantum dynamics
• Hamiltonian and measuring time for analog quantum search
• Optimized adiabatic-impulse protocol preserving Kibble-Zurek scaling with attenuated anti-Kibble-Zurek behavior
• Efficient quantum algorithm for solving structured problems via multi-step quantum computation
• Quantum computing from a mathematical perspective: a description of the quantum circuit model
• Learning adiabatic quantum algorithms for solving optimization problems
• Finite temperature quantum condensations in the space of states: General Proof
• Quantum Mechanical Search and Harmonic Perturbation
• Quasi-adiabatic Grover search via the WKB approximation
• Majorization in Quantum Adiabatic Algorithms
• Tunable Tradeoff between Quantum and Classical Computation via Nonunitary Zeno-like Dynamics
• Quantum Adiabatic Feature Selection
• A Novel AQC Factoring Algorithm
• Universality of the fully connected vertex in Laplacian continuous-time quantum walk problems
• A useful fundamental speed limit for the imaginary-time Schrodinger equation
• Control limit for the quantum state preparation under stochastic control errors
• Lack of a thermodynamic finite-temperature spin-glass phase in the two-dimensional randomly-coupled ferromagnet
• Benincasa-Dowker-Glaser causal set actions by quantum counting
• Combining Learned Representations for Combinatorial Optimization
• Improving adiabatic quantum factorization via chopped random-basis optimization
• Quantum adiabaticity in many-body systems and almost-orthogonality in complementary subspace
• Counterdiabatic driving for random-gap Landau-Zener transitions
• Bounding Run-Times of Local Adiabatic Algorithms
• Quantum annealing and condensed matter physics
• Hybrid Real-Imaginary Time Evolution for Low-Depth Hamiltonian Simulation in Quantum Optimization
• Explicitly Quantum-parallel Computation by Displacements
• Hidden local adiabatic ramp in the modulated time evolution and the quantum approximate optimization algorithm
• Weyl's Relations, Integrable Matrix Models and Quantum Computation
• Programming tools for Analogue Quantum Computing in the High-Performance Computing Context -- A Review
• Reflection-Based Adiabatic State Preparation
• Finite temperature quantum condensations in the space of states: a new perspective for quantum annealing
• Adiabatic Dynamics of Entanglement
• Rate Function Modelling of Quantum Many-Body Adiabaticity
• A universal adiabatic quantum query algorithm
• Superoscillating Quantum Control Induced By Sequential Selections