Entangling power and quantum circuit complexity
arXiv:2104.03332 · doi:10.1103/PhysRevLett.127.020501
Abstract
Notions of circuit complexity and cost play a key role in quantum computing and simulation where they capture the (weighted) minimal number of gates that is required to implement a unitary. Similar notions also become increasingly prominent in high energy physics in the study of holography. While notions of entanglement have in general little implications for the quantum circuit complexity and the cost of a unitary, in this note, we discuss a simple such relationship when both the entanglement of a state and the cost of a unitary take small values, building on ideas on how values of entangling power of quantum gates add up. This bound implies that if entanglement entropies grow linearly in time, so does the cost. The implications are two-fold: It provides insights into complexity growth for short times. In the context of quantum simulation, it allows to compare digital and analog quantum simulators. The main technical contribution is a continuous-variable small incremental entangling bound.
arXiv comment7 pages, 1 figure, typos corrected
References in corpus (27)
- Gaussian Quantum Information
- Area laws for the entanglement entropy - a review
- Nonequilibrium dynamics of closed interacting quantum systems
- Quantum many-body systems out of equilibrium
- Equilibration, thermalisation, and the emergence of statistical mechanics in closed quantum systems
- Complexity Equals Action
- Complexity and Shock Wave Geometries
- Lieb-Robinson bounds and the generation of correlations and topological quantum order
- Spectral Gap and Exponential Decay of Correlations
- Quantum Computation as Geometry
- Entropy scaling and simulability by Matrix Product States
- On the Entangling Power of Quantum Evolutions
- Optimal local implementation of non-local quantum gates
- Circuit complexity in quantum field theory
- Towards Complexity for Quantum Field Theory States
- The Second Law of Quantum Complexity
- Complexity of Formation in Holography
- Entangling operations and their implementation using a small amount of entanglement
- Complexity and entanglement for thermofield double states
- General entanglement scaling laws from time evolution
- The non-local content of quantum operations
- Optimal control, geometry, and quantum computing
- On entropy growth and the hardness of simulating time evolution
- Divergences in Holographic Complexity
- Entanglement rates and area laws
- Complexity in de Sitter Space
- Binding Complexity and Multiparty Entanglement
Cited by in corpus (38)
- Linear growth of quantum circuit complexity
- Quantum complexity in gravity, quantum field theory, and quantum information science
- Circuit Complexity as a novel probe of Quantum Entanglement: A study with Black Hole Gas in arbitrary dimensions
- Entanglement entropy production in deep inelastic scattering
- Resource theory of quantum uncomplexity
- Complexity of quantum circuits via sensitivity, magic, and coherence
- Quantum state preparation via engineered ancilla resetting
- Circuit complexity of quantum access models for encoding classical data
- Primordial Gravitational Wave Circuit Complexity
- Circuit Complexity in
- Circuit Complexity in an interacting quenched Quantum Field Theory
- Complexity-constrained quantum thermodynamics
- Entanglement in interacting quenched two-body coupled oscillator system
- Dual unitaries as maximizers of the distance to local product gates
- Introduction to quantum entanglement in many-body systems
- Saturation and recurrence of quantum complexity in random local quantum dynamics
- Measuring out quasi-local integrals of motion from entanglement
- Characterizing randomness in parameterized quantum circuits through expressibility and average entanglement
- Quantum complexity phase transitions in monitored random circuits
- Quantum Tensor Product Decomposition from Choi State Tomography
- Thermalization and hydrodynamics in an interacting integrable system: the case of hard rods
- Wavefunction branching: when you can't tell pure states from mixed states
- Classically Replaceable Operations
- Coherence and Imaginarity as Resources in Quantum Circuit Complexity
- The Complexity of Being Entangled
- Kolmogorov complexity as intrinsic entropy of a pure state: Perspective from entanglement in free fermion systems
- Causality Constraint on Circuit Complexity from
- Unifying non-Markovian characterisation with an efficient and self-consistent framework
- Wasserstein Complexity of Quantum Circuits
- Limitations of Noisy Quantum Devices in Computational and Entangling Power
- Quantum circuit complexity and unsupervised machine learning of topological order
- Conserved densities of hard rods: microscopic to hydrodynamic solutions
- Expressibility, entangling power and quantum average causal effect for causally indefinite circuits
- Non-stabilizerness and entanglement from cat-state injection
- Hamiltonian quantum gates -- energetic advantage from entangleability
- Estimating time in quantum chaotic systems and black holes
- Fast suppression of classification error in variational quantum circuits
- Extremal jumps of circuit complexity of unitary evolutions generated by random Hamiltonians