Wasserstein Complexity of Quantum Circuits
arXiv:2208.06306 · doi:10.1088/1751-8121/ade381
Abstract
Given a unitary transformation, what is the size of the smallest quantum circuit that implements it? This quantity, known as the quantum circuit complexity, is a fundamental property of quantum evolutions that has widespread applications in many fields, including quantum computation, quantum field theory, and black hole physics. In this letter, we obtain a new lower bound for the quantum circuit complexity in terms of a novel complexity measure that we propose for quantum circuits, which we call the quantum Wasserstein complexity. Our proposed measure is based on the quantum Wasserstein distance of order one (also called the quantum earth mover's distance), a metric on the space of quantum states. We also prove several fundamental and important properties of our new complexity measure, which stand to be of independent interest. Finally, we show that our new measure also provides a lower bound for the experimental cost of implementing quantum circuits, which implies a quantum limit on converting quantum resources to computational resources. Our results provide novel applications of the quantum Wasserstein distance and pave the way for a deeper understanding of the resources needed to implement a quantum computation.
arXiv comment7+7 pages
References in corpus (40)
- Quantum Computing in the NISQ era and beyond
- Noisy intermediate-scale quantum (NISQ) algorithms
- Quantum Computational Supremacy
- Complexity and Shock Wave Geometries
- Quantum Computation as Geometry
- Generalized Limits for Single-Parameter Quantum Estimation
- Application of a resource theory for magic states to fault-tolerant quantum computing
- Trading classical and quantum computational resources
- The Second Law of Quantum Complexity
- Simulation of quantum circuits by low-rank stabilizer decompositions
- Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning
- Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus
- Linear growth of quantum circuit complexity
- Optimal control, geometry, and quantum computing
- Quantifying the magic of quantum channels
- Geometrical Bounds of the Irreversibility in Markovian Systems
- Quantifying quantum speedups: improved classical simulation from tighter magic monotones
- Quantifying magic for multi-qubit operations
- The Quantum Wasserstein Distance of Order 1
- Renormalized Circuit Complexity
- Geometric quantum speed limits: a case for Wigner phase space
- Quantum circuit optimization with deep reinforcement learning
- How many qubits are needed for quantum computational supremacy?
- Learning quantum data with the quantum Earth Mover's distance
- Non-commutative calculus, optimal transport and functional inequalities in dissipative quantum systems
- Entangling power and quantum circuit complexity
- Efficient classical simulation of Clifford circuits with nonstabilizer input states
- T-count optimization and Reed-Muller codes
- Quantum advantage of unitary Clifford circuits with magic state inputs
- T-count and T-depth of any multi-qubit unitary
- A polynomial time and space heuristic algorithm for T-count
- Resource theory of quantum uncomplexity
- Further extensions of Clifford circuits and their classical simulation complexities
- Reducing the CNOT count for Clifford+T circuits on NISQ architectures
- Quantum concentration inequalities
- Complexity of quantum circuits via sensitivity, magic, and coherence
- Classical simulation of quantum circuits by half Gauss sums
- Computing quopit Clifford circuit amplitudes by the sum-over-paths technique
- Quantifying the difference between many-body quantum states
- Lower bound for simulation cost of open quantum systems: Lipschitz continuity approach