Entangling power and quantum circuit complexity

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.

7 pages, 1 figure, typos corrected

References in corpus (8)

• Complexity and Shock Wave Geometries
• Lieb-Robinson bounds and the generation of correlations and topological quantum order
• Quantum Computation as Geometry
• Entropy scaling and simulability by Matrix Product States
• General entanglement scaling laws from time evolution
• Optimal control, geometry, and quantum computing
• On entropy growth and the hardness of simulating time evolution
• Complexity in de Sitter Space

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 ${\mathcal{Z}}_2$ $\mathcal{EEF}\mathcal{T}$
• 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 $COSMOEFT$
• 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