Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2208.06306 · Journal of Physics A Mathematical and Theoretical

Wasserstein complexity of quantum circuits

Lu Li, Kaifeng Bu, Dax Enshan Koh, Arthur M. Jaffe, Seth Lloyd

Published Jun 10, 2025• 26 citations
arXivHTMLPDF

Abstract

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 paper, 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.

DOI
10.1088/1751-8121/ade381

Related papers

Quantum Wasserstein distance between unitary operations

Xinyu Qiu, Lin Chen, Li-Jun Zhao

Quantifying the effect of noise on unitary operations is an essential task in quantum information processing. We propose the quantum Wasserstein distance between unitary operations, which shows an explanation for quantum circuit complexity and characterizes the local distinguishability of multiqudit operations. We show analytical calculations of the distance between identity and widely used quantum gates including swap, cnot, and other controlled gates. As an application, we estimate the closeness between quantum gates in a circuit and show that the noisy operation simulates the ideal one well when they become close under the distance. Further, we introduce the ${W}_{1}$ error rate by the distance and establish the relation between the ${W}_{1}$ error rate and two practical cost measures of recovery operations in quantum error correction under typical noise scenarios. These applications allow the distance to quantify the effect of noise on unitary operations from the perspective of experiment resources, which cannot be achieved by existing distance.

arXiv:2306.04878•Physical Review A•Jul 1, 2024•2 citations

Coherence and Imaginarity as Resources in Quantum Circuit Complexity

Linlin Ye, Zhaoqi Wu, Nanrun Zhou

Quantum circuit complexity quantifies the minimal number of gates needed to realize a unitary transformation and plays a central role in quantum computation. In this work, we investigate the complexity of quantum circuits through coherence and imaginarity resources. We establish a lower bound on the circuit cost by the Tsallis relative $α$ entropy of cohering power, which is shown to be tighter than the one presented by Bu et al.[\textit{Communications in Mathematical Physics} 405, no. 7 (2024):161] under restrictive conditions. As a consequence, we obtain the relationships between the circuit cost and the coherence generating power via probabilistic average in terms of skew information/relative entropy, and present explicit bounds of the circuit cost for typical quantum gates. Moreover, we derive lower bounds on the circuit cost via the imaginaring power of the circuit, induced by the Tsallis relative $α$ entropy and relative entropy. We demonstrate that imaginarity can yield nontrivial constraints on the circuit cost even when coherence-based lower bounds are zero (e.g., for the $T$ gate), which implies that imaginarity may provide advantages under certain circumstances compared with coherence. Our results may help better understand the connections between quantum resources and circuit complexity.

quant-pharXiv:2604.05660•Advanced Quantum Technologies•Apr 8, 2026•7 citations

Spacetime Quantum Circuit Complexity via Measurements

Du, Zhenyu, Zi-Wen Liu, Xiongfeng Ma

Quantum circuit complexity is a fundamental concept whose importance permeates quantum information, computation, many-body physics and high-energy physics. While extensively studied in closed systems, its characterization and behaviors in the widely important setting where the system is embedded within a larger one -- encompassing measurement-assisted state preparation -- lack systematic understanding. We introduce the notion of embedded complexity that characterizes the complexity of projected states and measurement operators in this general setting incorporating auxiliary systems and measurements. For random circuits and certain strongly interacting time-independent Hamiltonian dynamics, we show that the embedded complexity is lower-bounded by the circuit volume -- the total number of gates acting on both the subsystem and its complement. This strengthens the complexity linear growth theorems, enriches the understanding of deep thermalization, and indicates that measurement-assisted methods generically cannot yield significant advantages in state preparation cost, contrary to expectations. We further demonstrate a spacetime conversion of certain circuit models that concentrates circuit volume onto a subsystem, and showcase applications for random circuit sampling and shadow tomography. Our theory establishes a unified framework for space and time aspects of quantum circuit complexity, yielding profound new insights and applications across quantum information and physics.

arXiv:2408.16602•Aug 29, 2024•7 citations

Quantum Meets the Minimum Circuit Size Problem

Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang +1 more

In this work, we initiate the study of the Minimum Circuit Size Problem (MCSP) in the quantum setting. MCSP is a problem to compute the circuit complexity of Boolean functions. It is a fascinating problem in complexity theory - its hardness is mysterious, and a better understanding of its hardness can have surprising implications to many fields in computer science. We first define and investigate the basic complexity-theoretic properties of minimum quantum circuit size problems for three natural objects: Boolean functions, unitaries, and quantum states. We show that these problems are not trivially in NP but in QCMA (or have QCMA protocols). Next, we explore the relations between the three quantum MCSPs and their variants. We discover that some reductions that are not known for classical MCSP exist for quantum MCSPs for unitaries and states, e.g., search-to-decision reductions and self-reductions. Finally, we systematically generalize results known for classical MCSP to the quantum setting (including quantum cryptography, quantum learning theory, quantum circuit lower bounds, and quantum fine-grained complexity) and also find new connections to tomography and quantum gravity. Due to the fundamental differences between classical and quantum circuits, most of our results require extra care and reveal properties and phenomena unique to the quantum setting. Our findings could be of interest for future studies, and we post several open problems for further exploration along this direction.

arXiv:2108.03171•Leibniz international proceedings in informatics•Aug 6, 2021•13 citations

Linear growth of quantum circuit complexity

Jonas Haferkamp, Philippe Faist, Naga Bhavya Teja Kothakonda +2 more

Abstract The complexity of quantum states has become a key quantity of interest across various subfields of physics, from quantum computing to the theory of black holes. The evolution of generic quantum systems can be modelled by considering a collection of qubits subjected to sequences of random unitary gates. Here we investigate how the complexity of these random quantum circuits increases by considering how to construct a unitary operation from Haar-random two-qubit quantum gates. Implementing the unitary operation exactly requires a minimal number of gates—this is the operation’s exact circuit complexity. We prove a conjecture that this complexity grows linearly, before saturating when the number of applied gates reaches a threshold that grows exponentially with the number of qubits. Our proof overcomes difficulties in establishing lower bounds for the exact circuit complexity by combining differential topology and elementary algebraic geometry with an inductive construction of Clifford circuits.

arXiv:2106.05305•Nature Physics•Mar 28, 2022•197 citations

The Quantum Wasserstein Distance of Order 1

Giacomo De Palma, Milad Marvian, Dario Trevisan +1 more

We propose a generalization of the Wasserstein distance of order 1 to the quantum states of n qudits. The proposal recovers the Hamming distance for the vectors of the canonical basis, and more generally the classical Wasserstein distance for quantum states diagonal in the canonical basis. The proposed distance is invariant with respect to permutations of the qudits and unitary operations acting on one qudit and is additive with respect to the tensor product. Our main result is a continuity bound for the von Neumann entropy with respect to the proposed distance, which significantly strengthens the best continuity bound with respect to the trace distance. We also propose a generalization of the Lipschitz constant to quantum observables. The notion of quantum Lipschitz constant allows us to compute the proposed distance with a semidefinite program. We prove a quantum version of Marton's transportation inequality and a quantum Gaussian concentration inequality for the spectrum of quantum Lipschitz observables. Moreover, we derive bounds on the contraction coefficients of shallow quantum circuits and of the tensor product of one-qudit quantum channels with respect to the proposed distance. We discuss other possible applications in quantum machine learning, quantum Shannon theory, and quantum many-body systems.

arXiv:2009.04469•IEEE Transactions on Information Theory•May 3, 2021•119 citations
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 paper, 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.
Quantifying the effect of noise on unitary operations is an essential task in quantum information processing. We propose the quantum Wasserstein distance between unitary operations, which shows an explanation for quantum circuit complexity and characterizes the local distinguishability of multiqudit operations. We show analytical calculations of the distance between identity and widely used quantum gates including swap, cnot, and other controlled gates. As an application, we estimate the closeness between quantum gates in a circuit and show that the noisy operation simulates the ideal one well when they become close under the distance. Further, we introduce the W1{W}_{1}W1​ error rate by the distance and establish the relation between the W1{W}_{1}W1​ error rate and two practical cost measures of recovery operations in quantum error correction under typical noise scenarios. These applications allow the distance to quantify the effect of noise on unitary operations from the perspective of experiment resources, which cannot be achieved by existing distance.
Quantum circuit complexity quantifies the minimal number of gates needed to realize a unitary transformation and plays a central role in quantum computation. In this work, we investigate the complexity of quantum circuits through coherence and imaginarity resources. We establish a lower bound on the circuit cost by the Tsallis relative ααα entropy of cohering power, which is shown to be tighter than the one presented by Bu et al.[\textit{Communications in Mathematical Physics} 405, no. 7 (2024):161] under restrictive conditions. As a consequence, we obtain the relationships between the circuit cost and the coherence generating power via probabilistic average in terms of skew information/relative entropy, and present explicit bounds of the circuit cost for typical quantum gates. Moreover, we derive lower bounds on the circuit cost via the imaginaring power of the circuit, induced by the Tsallis relative ααα entropy and relative entropy. We demonstrate that imaginarity can yield nontrivial constraints on the circuit cost even when coherence-based lower bounds are zero (e.g., for the TTT gate), which implies that imaginarity may provide advantages under certain circumstances compared with coherence. Our results may help better understand the connections between quantum resources and circuit complexity.
Quantum circuit complexity is a fundamental concept whose importance permeates quantum information, computation, many-body physics and high-energy physics. While extensively studied in closed systems, its characterization and behaviors in the widely important setting where the system is embedded within a larger one -- encompassing measurement-assisted state preparation -- lack systematic understanding. We introduce the notion of embedded complexity that characterizes the complexity of projected states and measurement operators in this general setting incorporating auxiliary systems and measurements. For random circuits and certain strongly interacting time-independent Hamiltonian dynamics, we show that the embedded complexity is lower-bounded by the circuit volume -- the total number of gates acting on both the subsystem and its complement. This strengthens the complexity linear growth theorems, enriches the understanding of deep thermalization, and indicates that measurement-assisted methods generically cannot yield significant advantages in state preparation cost, contrary to expectations. We further demonstrate a spacetime conversion of certain circuit models that concentrates circuit volume onto a subsystem, and showcase applications for random circuit sampling and shadow tomography. Our theory establishes a unified framework for space and time aspects of quantum circuit complexity, yielding profound new insights and applications across quantum information and physics.
In this work, we initiate the study of the Minimum Circuit Size Problem (MCSP) in the quantum setting. MCSP is a problem to compute the circuit complexity of Boolean functions. It is a fascinating problem in complexity theory - its hardness is mysterious, and a better understanding of its hardness can have surprising implications to many fields in computer science. We first define and investigate the basic complexity-theoretic properties of minimum quantum circuit size problems for three natural objects: Boolean functions, unitaries, and quantum states. We show that these problems are not trivially in NP but in QCMA (or have QCMA protocols). Next, we explore the relations between the three quantum MCSPs and their variants. We discover that some reductions that are not known for classical MCSP exist for quantum MCSPs for unitaries and states, e.g., search-to-decision reductions and self-reductions. Finally, we systematically generalize results known for classical MCSP to the quantum setting (including quantum cryptography, quantum learning theory, quantum circuit lower bounds, and quantum fine-grained complexity) and also find new connections to tomography and quantum gravity. Due to the fundamental differences between classical and quantum circuits, most of our results require extra care and reveal properties and phenomena unique to the quantum setting. Our findings could be of interest for future studies, and we post several open problems for further exploration along this direction.
Abstract The complexity of quantum states has become a key quantity of interest across various subfields of physics, from quantum computing to the theory of black holes. The evolution of generic quantum systems can be modelled by considering a collection of qubits subjected to sequences of random unitary gates. Here we investigate how the complexity of these random quantum circuits increases by considering how to construct a unitary operation from Haar-random two-qubit quantum gates. Implementing the unitary operation exactly requires a minimal number of gates—this is the operation’s exact circuit complexity. We prove a conjecture that this complexity grows linearly, before saturating when the number of applied gates reaches a threshold that grows exponentially with the number of qubits. Our proof overcomes difficulties in establishing lower bounds for the exact circuit complexity by combining differential topology and elementary algebraic geometry with an inductive construction of Clifford circuits.
We propose a generalization of the Wasserstein distance of order 1 to the quantum states of n qudits. The proposal recovers the Hamming distance for the vectors of the canonical basis, and more generally the classical Wasserstein distance for quantum states diagonal in the canonical basis. The proposed distance is invariant with respect to permutations of the qudits and unitary operations acting on one qudit and is additive with respect to the tensor product. Our main result is a continuity bound for the von Neumann entropy with respect to the proposed distance, which significantly strengthens the best continuity bound with respect to the trace distance. We also propose a generalization of the Lipschitz constant to quantum observables. The notion of quantum Lipschitz constant allows us to compute the proposed distance with a semidefinite program. We prove a quantum version of Marton's transportation inequality and a quantum Gaussian concentration inequality for the spectrum of quantum Lipschitz observables. Moreover, we derive bounds on the contraction coefficients of shallow quantum circuits and of the tensor product of one-qudit quantum channels with respect to the proposed distance. We discuss other possible applications in quantum machine learning, quantum Shannon theory, and quantum many-body systems.