Speedup of the Quantum Adiabatic Algorithm using Delocalization Catalysis

Abstract

We propose a method to speed up the quantum adiabatic algorithm using catalysis by many-body delocalization. This is applied to random-field antiferromagnetic Ising spin models. The algorithm is catalyzed in such a way that the evolution approximates a Heisenberg model in the middle of its course, and the model is in a delocalized phase. We show numerically that we can speed up the standard algorithm for finding the ground state of the random-field Ising model using this idea. We also demonstrate that the speedup is due to gap amplification, even though the underlying model is not frustration-free. The crossover to speedup occurs at roughly the value of the interaction which is known to be the critical one for the delocalization transition. We also calculate the participation ratio and entanglement entropy as a function of time: their time dependencies indicate that the system is exploring more states and that they are more entangled than when there is no catalyst. Together, all these pieces of evidence demonstrate that the speedup is related to delocalization. Even though only relatively small systems can be investigated, the evidence suggests that the scaling of the method with system size is favorable. Our method is illustrated by experimental results from a small online IBM quantum computer, showing how to verify the method in future as such machines improve. The cost of the catalytic method compared to the standard algorithm is only a constant factor.

arXiv commentPublished version

References in corpus (26)

• Many body localization and thermalization in quantum statistical mechanics
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Metal-insulator transition in a weakly interacting many-electron system with localized single-particle states
• Adiabatic Quantum Computing
• The many-body localization phase transition
• Many-body localization edge in the random-field Heisenberg chain
• Exploring the many-body localization transition in two dimensions
• Interacting electrons in disordered wires: Anderson localization and low-temperature transport
• On Many-Body Localization for Quantum Spin Chains
• Optimal Quantum Circuits for General Two-Qubit Gates
• Coupling Identical 1D Many-Body Localized Systems
• Simulating quantum many-body dynamics on a current digital quantum computer
• Anderson localization casts clouds over adiabatic quantum optimization
• Many-body Localization and Symmetry Protected Topological Order
• Spectral features of a many-body localized system weakly coupled to a heat bath
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Quantum Simulations of Classical Annealing Processes
• Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
• Nonstoquastic Hamiltonians and Quantum Annealing of an Ising Spin Glass
• Decoherence in a scalable adiabatic quantum computer
• Role of Non-stoquastic Catalysts in Quantum Adiabatic Optimization
• Spectral Gap Amplification
• Steering random spin systems to speed up the quantum adiabatic algorithm
• Elimination of Perturbative Crossings in Adiabatic Quantum Optimization
• Response of a quantum disordered spin system to a local periodic drive
• Energy Level Statistics of Quantum Dots

Cited by in corpus (10)

• Noise-Assisted Quantum Autoencoder
• Fermionic Quantum Approximate Optimization Algorithm
• Many-body localization enables iterative quantum optimization
• Solution of SAT Problems with the Adaptive-Bias Quantum Approximate Optimization Algorithm
• Qutrit Circuits and Algebraic Relations: A Pathway to Efficient Spin-1 Hamiltonian Simulation
• Cyclic Quantum Annealing: Searching for Deep Low-Energy States in 5000-Qubit Spin Glass
• Comparison of encoding schemes for quantum computing of $S>1/2$ spin chains
• Computational complexity of three-dimensional Ising spin glass: Lessons from D-Wave annealer
• Fighting Exponentially Small Gaps by Counterdiabatic Driving
• Exploiting many-body localization for scalable variational quantum simulation