Adiabatic quantum computation and quantum phase transitions

Abstract

We analyze the ground state entanglement in a quantum adiabatic evolution algorithm designed to solve the NP-complete Exact Cover problem. The entropy of entanglement seems to obey linear and universal scaling at the point where the mass gap becomes small, suggesting that the system passes near a quantum phase transition. Such a large scaling of entanglement suggests that the effective connectivity of the system diverges as the number of qubits goes to infinity and that this algorithm cannot be efficiently simulated by classical means. On the other hand, entanglement in Grover's algorithm is bounded by a constant.

5 pages, 4 figures, accepted for publication in PRA

References in corpus (9)

• Entanglement in quantum critical phenomena
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Entropy and Area
• On Geometric Entropy
• Quantum Search by Local Adiabatic Evolution
• Black Hole Entropy and Entropy of Entanglement
• Black hole thermodynamics and information loss in two dimensions
• A Comment on Entropy and Area
• The Majorization Arrow in Quantum Algorithm Design

Cited by in corpus (34)

• Adiabatic Quantum Computing
• Entanglement entropy in the Lipkin-Meshkov-Glick model
• Quantum Adiabatic Brachistochrone
• A short review on entanglement in quantum spin systems
• 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
• Entanglement Scaling in the One-Dimensional Hubbard Model at Criticality
• Entanglement and Entropy in a Spin-Boson Quantum Phase Transition
• Quantum Phase Transition of Ground-state Entanglement in a Heisenberg Spin Chain Simulated in an NMR Quantum Computer
• Counterdiabaticity and the quantum approximate optimization algorithm
• Direct observation of quantum criticality in Ising spin chains
• Intrinsic geometry of quantum adiabatic evolution and quantum phase transitions
• Adiabatic quantum algorithms as quantum phase transitions: first versus second order
• Accuracy vs run time in adiabatic quantum search
• Area law and vacuum reordering in harmonic networks
• Robustness of the adiabatic quantum search
• Entanglement and majorization in (1+1)-dimensional quantum systems
• Simulation of many-qubit quantum computation with matrix product states
• Decoherence in the dynamical quantum phase transition of the transverse Ising chain
• A quantum phase transition in the one-dimensional water chain
• Entanglement and Density Matrix of a Block of Spins in AKLT Model
• Adiabatic preparation without Quantum Phase Transitions
• Dynamical properties across a quantum phase transition in the Lipkin-Meshkov-Glick model
• Universal resources for approximate and stochastic measurement-based quantum computation
• Entanglement, fidelity, and quantum phase transition in antiferromagnetic-ferromagnetic alternating Heisenberg chain
• Dynamical quantum phase transitions
• Quantum Phase Transitions in Anti-ferromagnetic Planar Cubic Lattices
• Decoherence in a dynamical quantum phase transition
• Adiabatic Computation - A Toy Model
• Block Spin Density Matrix of the Inhomogeneous AKLT Model
• Superposition of Macroscopically Distinct States in Adiabatic Quantum Computation
• Eigenlevel statistics of the quantum adiabatic algorithm
• Parent Hamiltonian Reconstruction via Inverse Quantum Annealing
• Entanglement and Quantum Phase Transitions via Adiabatic Quantum Computation