Universality of Entanglement and Quantum Computation Complexity

Abstract

We study the universality of scaling of entanglement in Shor's factoring algorithm and in adiabatic quantum algorithms across a quantum phase transition for both the NP-complete Exact Cover problem as well as the Grover's problem. The analytic result for Shor's algorithm shows a linear scaling of the entropy in terms of the number of qubits, therefore difficulting the possibility of an efficient classical simulation protocol. A similar result is obtained numerically for the quantum adiabatic evolution Exact Cover algorithm, which also shows universality of the quantum phase transition the system evolves nearby. On the other hand, entanglement in Grover's adiabatic algorithm remains a bounded quantity even at the critical point. A classification of scaling of entanglement appears as a natural grading of the computational complexity of simulating quantum phase transitions.

30 pages, 17 figures, accepted for publication in PRA

References in corpus (17)

• Entanglement in quantum critical phenomena
• Efficient classical simulation of slightly entangled quantum computations
• Persistent entanglement in arrays of interacting particles
• Scaling of Entanglement close to a Quantum Phase Transitions
• Entropy and Area
• Average Entropy of a Subsystem
• Quantum Algorithms Revisited
• On Geometric Entropy
• Quantum Search by Local Adiabatic Evolution
• Information and Computation: Classical and Quantum Aspects
• Black Hole Entropy and Entropy of Entanglement
• Black hole thermodynamics and information loss in two dimensions
• Average Entropy of a Subsystem
• A Comment on Entropy and Area
• Typical entanglement in multi-qubit systems
• The Majorization Arrow in Quantum Algorithm Design
• Entanglement Simulations of Shor's Algorithm

Cited by in corpus (50)

• Quantum entanglement
• Ultracold atomic gases in optical lattices: mimicking condensed matter physics and beyond
• Adiabatic Quantum Computing
• Entanglement in XY Spin Chain
• Macroscopic quantum states: measures, fragility and implementations
• Entanglement entropy in the Lipkin-Meshkov-Glick model
• Entanglement in a Valence-Bond-Solid State
• Universal quantum computation with little entanglement
• Correlations in Grover search
• Symmetry resolved entanglement: Exact results in 1D and beyond
• Adiabatic quantum algorithms as quantum phase transitions: first versus second order
• Entanglement Across a Transition to Quantum Chaos
• Shortcuts to adiabaticity for quantum annealing
• 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
• Optimising Matrix Product State Simulations of Shor's Algorithm
• Scale invariance of entanglement dynamics in Grover's quantum search algorithm
• Energetic cost of superadiabatic quantum computation
• Entanglement and Density Matrix of a Block of Spins in AKLT Model
• Adiabatic preparation without Quantum Phase Transitions
• Ultracold atomic Bose and Fermi spinor gases in optical lattices
• Dynamical properties across a quantum phase transition in the Lipkin-Meshkov-Glick model
• Entanglement in Valence-Bond-Solid States
• A tree tensor network approach to simulating Shor's algorithm
• Coherence Depletion in Quantum Algorithms
• Quantum Entanglement involved in Grover's and Shor's algorithms: the four-qubit case
• Four-tangle for pure states
• Entanglement of Periodic States, the Quantum Fourier Transform and Shor's Factoring Algorithm
• Quantum Phase Transitions in Anti-ferromagnetic Planar Cubic Lattices
• On the quantum spin glass transition on the Bethe lattice
• Entanglement bounds on the performance of quantum computing architectures
• Necessity of Superposition of Macroscopically Distinct States for Quantum Computational Speedup
• Genuine Multipartite Entanglement in Quantum Optimization
• Entanglement Scaling in Quantum Advantage Benchmarks
• Adiabatic Computation - A Toy Model
• Physical consequences of P$\ne$NP and the DMRG-annealing conjecture
• Entanglement of Valence-Bond-Solid on an Arbitrary Graph
• Block Spin Density Matrix of the Inhomogeneous AKLT Model
• Entanglement and its Role in Shor's Algorithm
• The Fisher-Hartwig Formula and Generalized Entropies in XY Spin Chain
• Boosting quantum annealing performance through direct polynomial unconstrained binary optimization
• Superposition of Macroscopically Distinct States in Adiabatic Quantum Computation
• Eigenlevel statistics of the quantum adiabatic algorithm
• The Dynamics of Entanglement in the Adiabatic Search and Deutsch Algorithms
• Entanglement and Quantum Phase Transitions via Adiabatic Quantum Computation
• Unique entanglement time evolution of two-qubit product separable and extended Werner-like states in a discrete qubit environment
• Entanglement Trajectory and its Boundary
• Boosting Gaussian Boson Sampling using Optical Parametric Amplification Networks