Sharp complexity phase transitions generated by entanglement

Abstract

Entanglement is one of the physical properties of quantum systems responsible for the computational hardness of simulating quantum systems. But while the runtime of specific algorithms, notably tensor network algorithms, explicitly depends on the amount of entanglement in the system, it is unknown whether this connection runs deeper and entanglement can also cause inherent, algorithm-independent complexity. In this work, we quantitatively connect the entanglement present in certain quantum systems to the computational complexity of simulating those systems. Moreover, we completely characterize the entanglement and complexity as a function of a system parameter. Specifically, we consider the task of simulating single-qubit measurements of $k$--regular graph states on $n$ qubits. We show that, as the regularity parameter is increased from $1$ to $n-1$, there is a sharp transition from an easy regime with low entanglement to a hard regime with high entanglement at $k=3$, and a transition back to easy and low entanglement at $k=n-3$. As a key technical result, we prove a duality for the simulation complexity of regular graph states between low and high regularity.

References in corpus (36)

• Efficient classical simulation of slightly entangled quantum computations
• Measurement-based quantum computation with cluster states
• Multi-party entanglement in graph states
• On the Power of One Bit of Quantum Information
• On the role of entanglement in quantum computational speed-up
• Classical simulation of quantum many-body systems with a tree tensor network
• Measuring the scrambling of quantum information
• Simulating quantum computation by contracting tensor networks
• Positive Wigner functions render classical simulation of quantum computation efficient
• Cluster-state quantum computation
• A fault-tolerant one-way quantum computer
• Entanglement and the Power of One Qubit
• Graphical description of the action of local Clifford transformations on graph states
• Improved classical simulation of quantum circuits dominated by Clifford gates
• The computational complexity of PEPS
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Most quantum states are too entangled to be useful as computational resources
• Universal resources for measurement-based quantum computation
• Estimating outcome probabilities of quantum circuits using quasiprobabilities
• Wigner function negativity and contextuality in quantum computation on rebits
• Are random pure states useful for quantum computation?
• Universal quantum computation with little entanglement
• Contextuality and Wigner function negativity in qubit quantum computation
• Quantum Computing Without Entanglement
• Classical simulation versus universality in measurement based quantum computation
• Architectures for quantum simulation showing a quantum speedup
• The one-way quantum computer -- a non-network model of quantum computation
• Phase space simulation method for quantum computation with magic states on qubits
• Entanglement and local information access for graph states
• Quantum Commuting Circuits and Complexity of Ising Partition Functions
• Rank-width: Algorithmic and structural results
• Transforming graph states using single-qubit operations
• Transforming graph states to Bell-pairs is NP-Complete
• Complexity phase diagram for interacting and long-range bosonic Hamiltonians
• Effective gaps are not effective: quasipolynomial classical simulation of obstructed stoquastic Hamiltonians

Cited by in corpus (8)

• Benchmarking highly entangled states on a 60-atom analog quantum simulator
• Error-resilience Phase Transitions in Encoding-Decoding Quantum Circuits
• Compilation of algorithm-specific graph states for quantum circuits
• Achieving the volume-law entropy regime with random-sign Dicke states
• The Foliage Partition: An Easy-to-Compute LC-Invariant for Graph States
• Efficient classical simulation of cluster state quantum circuits with alternative inputs
• Computable and noncomputable in the quantum domain: statements and conjectures
• Quantum Complexity in Rule-Based Constrained Many-Body Models: Scars, Fragmentation, and Chaos