We introduce a new framework for quantifying the complexity of quantum channels, grounded in a suitably chosen resource set. This class of convex functions is designed to analyze the complexity of both open and closed quantum systems. By leveraging Lipschitz norms inspired by quantum optimal transport theory, we rigorously establish the fundamental properties of this complexity measure. The flexibility in selecting the resource set allows us to derive effective lower bounds for gate complexities and simulation costs of both Hamiltonian simulations and dynamics of open quantum systems. Additionally, we demonstrate that this complexity measure exhibits linear growth for random quantum circuits and finite-dimensional quantum simulations, up to the Brown-Susskind threshold.
We introduce a new framework for quantifying the complexity of quantum channels, grounded in a suitably chosen resource set. This class of convex functions is designed to analyze the complexity of both open and closed quantum systems. By leveraging Lipschitz norms inspired by quantum optimal transport theory, we rigorously establish the fundamental properties of this complexity measure. The flexibility in selecting the resource set allows us to derive effective lower bounds for gate complexities and simulation costs of both Hamiltonian simulations and dynamics of open quantum systems. Additionally, we demonstrate that this complexity measure exhibits linear growth for random quantum circuits and finite-dimensional quantum simulations, up to the Brown-Susskind threshold.
Abstract Nielsen’s geometric approach to quantum circuit complexity provides a Riemannian framework for quantifying the cost of implementing unitary closed-system dynamics. For open evolutions, the reduced dynamics is described by time-dependent families of quantum channels { Λ t } t ⩾ 0 admitting many inequivalent Stinespring realizations, so any meaningful complexity notion must specify which microscopic resources are counted and which transformations are treated as gauge. We develop a dilation-based geometric complexity framework that distinguishes implementation-dependent complexity, attached to a specific realization, from intrinsic channel complexity obtained by minimizing over a physically admissible class of dilations. The proposed functional is subtractive: it removes purely environmental contributions from the geometric cost of the joint unitary realization. The subtraction is derived from concise structural postulates—closed-system consistency, environment-only neutrality, and invariance under dilation gauge transformations—and admits a natural variational and geometric interpretation. We also define noise complexity as a companion quantity measuring the geometric deviation of a noisy implementation from a prescribed ideal closed-system evolution. In the Hilbert–Schmidt setting, we establish coherence-based lower bounds for unitary and noise complexity, prove linear time scaling under time-homogeneous dilation models, and obtain dissipator-controlled bounds in the Markovian GKSL regime. We illustrate the framework on canonical single-qubit benchmark channels: dephasing, amplitude damping, and Pauli/depolarizing noise.
Nielsen's geometric approach to quantum circuit complexity provides a Riemannian framework for quantifying the cost of implementing unitary closed-system dynamics. For open evolutions, the reduced dynamics is described by time-dependent families of quantum channels {Λt}t≥0 admitting many inequivalent Stinespring realizations, so any meaningful complexity notion must specify which microscopic resources are counted and which transformations are treated as gauge. We develop a dilation-based geometric complexity framework that distinguishes implementation-dependent complexity, attached to a specific realization, from intrinsic channel complexity obtained by minimizing over a physically admissible class of dilations. The proposed functional is subtractive: it removes purely environmental contributions from the geometric cost of the joint unitary realization. The subtraction is derived from concise structural postulates --- closed-system consistency, environment-only neutrality, and invariance under dilation gauge transformations --- and admits a natural variational and geometric interpretation. We also define noise complexity as a companion quantity measuring the geometric deviation of a noisy implementation from a prescribed ideal closed-system evolution. In the Hilbert-Schmidt setting, we establish coherence-based lower bounds for unitary and noise complexity, prove linear time scaling under time-homogeneous dilation models, and obtain dissipator-controlled bounds in the Markovian GKSL regime. We illustrate the framework on canonical single-qubit benchmark channels: dephasing, amplitude damping, and Pauli/depolarizing noise.
Abstract We investigate how the addition of quantum resources changes the statistical complexity of quantum circuits by utilizing the framework of quantum resource theories. Measures of statistical complexity that we consider include the Rademacher complexity and the Gaussian complexity, which are well-known measures in computational learning theory that quantify the richness of classes of real-valued functions. We derive bounds for the statistical complexities of quantum circuits that have limited access to certain resources and apply our results to two special cases: (a) stabilizer circuits that are supplemented with a limited number of T gates and (b) instantaneous quantum polynomial-time Clifford circuits that are supplemented with a limited number of CCZ gates. We show that the increase in the statistical complexity of a quantum circuit when an additional quantum channel is added to it is upper bounded by the free robustness of the added channel. Moreover, as noise in quantum systems is a major obstacle to implementing many quantum algorithms on large quantum circuits, we also study the effects of noise on the Rademacher complexity of quantum circuits. Finally, we derive bounds for the generalization error associated with learning from training data arising from quantum circuits.
Quantum resource theory has sharpened our understanding of the intrinsic complexity of quantum systems, particularly their classical simulability. However, it remains unclear which quantum resource governs the classical learnability of quantum circuits, especially beyond the regime of efficient classical simulation. Here we close this knowledge gap by studying the expectation-value functions of families of tunable quantum circuits, with many applications in digital quantum simulation, quantum metrology, and quantum-system characterization. Specifically, we introduce a new resource measure, the dynamical stabilizer entropy (\DSE), which quantifies how broadly an expectation-value function is distributed across its frequency modes. By relating \DSE to operator stabilizer entropy, we establish a computational phase diagram that compares classical simulators with quantum-data-assisted classical surrogates. We first determine the \DSE-dependent learnability boundary of this diagram by deriving bounds on the sample complexity and runtime of classical surrogates, and by developing a \DSE-guided surrogate. We then complete the diagram by proving, under standard complexity-theoretic assumptions, the existence of circuit families that can be efficiently learned by this surrogate but cannot be efficiently emulated from their circuit descriptions alone. Numerical experiments on random and structured circuits with up to 80 qubits support the predicted \DSE-dependent computational landscape. These results establish a quantitative resource-theoretic framework for delineating the boundary between classical simulation and learning, motivate resource measures linking quantum resources to learnability, and guide the design of learning-based algorithms for scalable quantum systems beyond the reach of direct classical simulation.
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.
Optimal convex approximation of quantum channels based on α-affinity
Determining the minimal distance between a target channel and a convex hull of predefined set of implementable channels is a fundamental problem in quantum resource theory, and provides key guidance for experimental implementations. In this work, we develop a unified analytical framework for optimal convex approximation of quantum channels based on the quantum α-affinity measure. We construct a channel distance metric induced by the α-affinity and the ChoiJamiolkowski isomorphism, which satisfies the required properties of a well-defined channel distance. Subsequently, we present an optimization framework for the convex approximation of quantum channels, and derive analytical solutions for the optimal convex approximation of single-qubit unitary channels over both the SU(2)-covariant and Pauli channel families, obtaining closed-form expressions for the optimal parameters and the minimal approximation distance. This framework is further applied to the amplitude-damping channel, yielding the explicit form of its optimal approximation and the associated minimal α-affinity distance. In contrast to conventional approaches based on the diamond norm, our framework provides a systematic and analytically tractable approach to quantum channel approximation under realistic constraints.