Adiabatic quantum algorithms as quantum phase transitions: first versus second order

Abstract

In the continuum limit (large number of qubits), adiabatic quantum algorithms display a remarkable similarity to sweeps through quantum phase transitions. We find that transitions of second or higher order are advantageous in comparison to those of first order. With this insight, we propose a novel adiabatic quantum algorithm for the solution of 3-satisfiability (3-SAT) problems (exact cover), which is significantly faster than previous proposals according to numerical simulations (up to 20 qubits). These findings suggest that adiabatic quantum algorithms can solve NP-complete problems such as 3-SAT much faster than the Grover search routine (yielding a quadratic enhancement), possibly even with an exponential speed-up. PACS: 03.67.-a, 03.67.Lx, 73.43.Nq, 64.70.-p.

4 pages, 4 figures

Cited by in corpus (45)

• Quantum Quench of an Atomic Mott Insulator
• Quantum Adiabatic Brachistochrone
• Adiabatic approximation with exponential accuracy for many-body systems and quantum computation
• Quantum annealing with antiferromagnetic fluctuations
• Preservation of Positivity by Dynamical Coarse-Graining
• Excited-state quantum phase transitions
• Thermally assisted adiabatic quantum computation
• Direct observation of quantum criticality in Ising spin chains
• The quantum adiabatic algorithm and scaling of gaps at first order quantum phase transitions
• Accuracy vs run time in adiabatic quantum search
• Phase transitions and adiabatic preparation of a fractional Chern insulator in a boson cold atom model
• New dynamical scaling universality for quantum networks across adiabatic quantum phase transitions
• Continuous Preparation of a Fractional Chern Insulator
• Controllable exchange coupling between two singlet-triplet qubits
• Non-Markovian decoherence in the adiabatic quantum search algorithm
• Effect of Local Minima on Adiabatic Quantum Optimization
• Decoherence in the dynamical quantum phase transition of the transverse Ising chain
• High Fidelity Adiabatic Quantum Computation via Dynamical Decoupling
• A quantum phase transition in the one-dimensional water chain
• Designing Quantum Annealing Schedules using Bayesian Optimization
• Analog Nature of Quantum Adiabatic Unstructured Search
• Adiabatic preparation without Quantum Phase Transitions
• Theorem on the existence of a nonzero energy gap in adiabatic quantum computation
• Dynamical quantum phase transitions
• Quantum Hysteresis in Coupled Light-Matter Systems
• Classical and Quantum Annealing in the Median of Three Satisfiability
• Adiabatic quantum computation along quasienergies
• Pulsed Generation of Quantum Coherences and Non-classicality in Light-Matter Systems
• Decoherence in a dynamical quantum phase transition
• Why adiabatic quantum annealing is unlikely to yield speed-up
• Probing nonlinear adiabatic paths with a universal integrator
• Implementation of many-qubit Grover search with trapped ultracold ions
• Solution to Satisfiability problem by a complete Grover search with trapped ions
• Quantum algorithms for powering stable Hermitian matrices
• Statistical Mechanics of the Quantum K-Satisfiability problem
• The speed of Markovian relaxation towards the ground state
• Search for optimal driving in finite quantum systems with precursors of criticality
• Continuous Transition between Bosonic Fractional Chern Insulator and Superfluid
• Decoherence-assisted quantum driving
• Quadratic fermionic interactions yield effective Hamiltonians for adiabatic quantum computing
• Learning-Driven Annealing with Adaptive Hamiltonian Modification for Solving Large-Scale Problems on Quantum Devices
• Entanglement and Quantum Phase Transitions via Adiabatic Quantum Computation
• Energy Spectrum and Exact Cover in an Extended Quantum Ising Model
• Improving adiabatic quantum factorization via chopped random-basis optimization
• Anomalous Dynamical Scaling at Topological Quantum Criticality