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• 6 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•1 citation

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•6 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•0 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•3 citations

Quantum Earth Mover's Distance: A New Approach to Learning Quantum Data

Bobak T. Kiani, Giacomo De Palma, Milad Marvian +2 more

Quantifying how far the output of a learning algorithm is from its target is an essential task in machine learning. However, in quantum settings, the loss landscapes of commonly used distance metrics often produce undesirable outcomes such as poor local minima and exponentially decaying gradients. As a new approach, we consider here the quantum earth mover's (EM) or Wasserstein-1 distance, recently proposed in [De Palma et al., arXiv:2009.04469] as a quantum analog to the classical EM distance. We show that the quantum EM distance possesses unique properties, not found in other commonly used quantum distance metrics, that make quantum learning more stable and efficient. We propose a quantum Wasserstein generative adversarial network (qWGAN) which takes advantage of the quantum EM distance and provides an efficient means of performing learning on quantum data. Our qWGAN requires resources polynomial in the number of qubits, and our numerical experiments demonstrate that it is capable of learning a diverse set of quantum data.

•Jan 8, 2021•4 citations

Quantum Wasserstein Compilation: Unitary Compilation using the Quantum Earth Mover's Distance

Richter, Marvin, Abhishek Y. Dubey, Axel Plinge +3 more

Despite advances in the development of quantum computers, the practical application of quantum algorithms requiring deep circuit depths or high-fidelity transformations remains outside the current range of the so-called noisy intermediate-scale quantum devices. Now and beyond, quantum circuit compilation (QCC) is a crucial component of any quantum algorithm execution. Besides translating a circuit into hardware-specific gates, it can optimize circuit depth and adapt to noise. Variational quantum circuit compilation (VQCC) optimizes the parameters of an ansatz according to the goal of reproducing a given unitary transformation. In this work, we present a VQCC-objective function called the quantum Wasserstein compilation (QWC) cost function based on the quantum Wasserstein distance of order 1. We show that the QWC cost function upper bounds the average infidelity of two circuits. An estimation method based on measurements of local Pauli-observable is utilized in a generative adversarial network to learn a given quantum circuit. We demonstrate the efficacy of the QWC cost function by compiling hardware efficient ansatz (HEA) as both the target and the ansatz and comparing to cost functions such as the Loschmidt echo test (LET) and the Hilbert-Schmidt test (HST). Finally, our experiments demonstrate that QWC as a cost function is the least affected by barren plateaus when compared to LET and HST for deep enough circuits.

arXiv:2409.05849•Sep 9, 2024•0 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.
Quantifying how far the output of a learning algorithm is from its target is an essential task in machine learning. However, in quantum settings, the loss landscapes of commonly used distance metrics often produce undesirable outcomes such as poor local minima and exponentially decaying gradients. As a new approach, we consider here the quantum earth mover's (EM) or Wasserstein-1 distance, recently proposed in [De Palma et al., arXiv:2009.04469] as a quantum analog to the classical EM distance. We show that the quantum EM distance possesses unique properties, not found in other commonly used quantum distance metrics, that make quantum learning more stable and efficient. We propose a quantum Wasserstein generative adversarial network (qWGAN) which takes advantage of the quantum EM distance and provides an efficient means of performing learning on quantum data. Our qWGAN requires resources polynomial in the number of qubits, and our numerical experiments demonstrate that it is capable of learning a diverse set of quantum data.
Despite advances in the development of quantum computers, the practical application of quantum algorithms requiring deep circuit depths or high-fidelity transformations remains outside the current range of the so-called noisy intermediate-scale quantum devices. Now and beyond, quantum circuit compilation (QCC) is a crucial component of any quantum algorithm execution. Besides translating a circuit into hardware-specific gates, it can optimize circuit depth and adapt to noise. Variational quantum circuit compilation (VQCC) optimizes the parameters of an ansatz according to the goal of reproducing a given unitary transformation. In this work, we present a VQCC-objective function called the quantum Wasserstein compilation (QWC) cost function based on the quantum Wasserstein distance of order 1. We show that the QWC cost function upper bounds the average infidelity of two circuits. An estimation method based on measurements of local Pauli-observable is utilized in a generative adversarial network to learn a given quantum circuit. We demonstrate the efficacy of the QWC cost function by compiling hardware efficient ansatz (HEA) as both the target and the ansatz and comparing to cost functions such as the Loschmidt echo test (LET) and the Hilbert-Schmidt test (HST). Finally, our experiments demonstrate that QWC as a cost function is the least affected by barren plateaus when compared to LET and HST for deep enough circuits.