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:2104.03332 · Physical Review Letters

Entangling Power and Quantum Circuit Complexity

Jens Eisert

Published Jul 7, 2021• 56 citations
arXivHTMLPDF

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 work, 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 twofold: It provides insights into complexity growth for short times. In the context of quantum simulation, it allows us to compare digital and analog quantum simulators. The main technical contribution is a continuous-variable small incremental entangling bound.

DOI
10.1103/physrevlett.127.020501

Related papers

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

Quantifying Entangling Power of Controlled Unitary Gates

Ankur Haldar, Pankaj Agrawal, Prasenjit Deb

Applying controlled unitary gates to generate entanglement between qubits is a routine task in both quantum communication and computation. The existing tools for predicting how much entanglement a given gate can generate require either simulation of the entangling circuit or averaging over a distribution of inputs for a given controlled unitary gate. Here, we introduce a computable quantity $ζ$ that not only determines whether a controlled unitary gate generates entanglement, but also quantifies the entanglement for any specific input without requiring the construction of the output state. For two-qubit controlled unitary gates, we establish the physical conditions corresponding to the extremum values of the proposed quantity. Extending the dimension of control and target registers to arbitrary size through a generalized controlled unitary architecture, we derive a universal upper bound on $ζ$ and identify the conditions for its saturation. Later we establish functional relation between the quantity and other known quantities, such as purity, normalized linear entropy, and von Neumann entropy. Finally, we compare our results with previous research work and show that the quantity proposed in this work achieves the previously known optimal values of entangling power of controlled unitary gates for some specific dimensions of target and control registers.

quant-pharXiv:2608.21105•Aug 24, 2026•0 citations

Models of Quantum Complexity Growth

Fernando G. S. L. Brandão, Wissam A Chemissany, Nicholas Hunter-Jones +2 more

The concept of quantum complexity has far-reaching implications spanning theoretical computer science, quantum many-body physics, and high-energy physics.The quantum complexity of a unitary transformation or quantum state is defined as the size of the shortest quantum computation that executes the unitary or prepares the state.It is reasonable to expect that the complexity of a quantum state governed by a chaotic many-body Hamiltonian grows linearly with time for a time that is exponential in the system size; however, because it is hard to rule out a shortcut that improves the efficiency of a computation, it is notoriously difficult to derive lower bounds on quantum complexity for particular unitaries or states without making additional assumptions.To go further, one may study more generic models of complexity growth.We provide a rigorous connection between complexity growth and unitary k-designs, ensembles that capture the randomness of the unitary group.This connection allows us to leverage existing results about design growth to draw conclusions about the growth of complexity.We prove that local random quantum circuits generate unitary transformations whose complexity grows linearly for a long time, mirroring the behavior one expects in chaotic quantum systems and verifying conjectures by Brown and Susskind.Moreover, our results apply under a strong definition of quantum complexity based on optimal distinguishing measurements.

arXiv:1912.04297•PRX Quantum•Jul 29, 2021•121 citations

One Gate at a Time: Complexity Growth in Random Quantum Circuits

Zhi Li

A random unitary quantum circuit is expected to be incompressible for exponentially long times. We show that the constant-error circuit complexity of a random unitary circuit grows almost linearly with time as $Ω(T/\log T)$. The bound holds for all $2\leq T\leq 4^n$ where $n$ is the system size, and involves no other $n$-dependence. This improves previous lower bounds derived from spectral gaps and unitary designs by a factor of $\mathrm{poly}(n)$. Drawing on insights from stochastic calculus, geometric functional analysis, and randomized linear algebra, our approach exploits the circuit's response to variations of individual gates and requires no control over convergence to high-order unitary designs.

quant-pharXiv:2609.17457•Sep 16, 2026•0 citations

Short Proofs of Linear Growth of Quantum Circuit Complexity

Zhi Li

The complexity of a quantum gate, defined as the minimal number of elementary gates to build it, is an important concept in quantum information and computation. It is shown recently that the complexity of quantum gates built from random quantum circuits almost surely grows linearly with the number of building blocks. In this article, we provide two short proofs of this fact. We also discuss a discrete version of quantum circuit complexity growth.

arXiv:2205.05668•May 11, 2022•2 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•151 citations
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 work, 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 twofold: It provides insights into complexity growth for short times. In the context of quantum simulation, it allows us to compare digital and analog quantum simulators. The main technical contribution is a continuous-variable small incremental entangling bound.
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.
Applying controlled unitary gates to generate entanglement between qubits is a routine task in both quantum communication and computation. The existing tools for predicting how much entanglement a given gate can generate require either simulation of the entangling circuit or averaging over a distribution of inputs for a given controlled unitary gate. Here, we introduce a computable quantity ζζζ that not only determines whether a controlled unitary gate generates entanglement, but also quantifies the entanglement for any specific input without requiring the construction of the output state. For two-qubit controlled unitary gates, we establish the physical conditions corresponding to the extremum values of the proposed quantity. Extending the dimension of control and target registers to arbitrary size through a generalized controlled unitary architecture, we derive a universal upper bound on ζζζ and identify the conditions for its saturation. Later we establish functional relation between the quantity and other known quantities, such as purity, normalized linear entropy, and von Neumann entropy. Finally, we compare our results with previous research work and show that the quantity proposed in this work achieves the previously known optimal values of entangling power of controlled unitary gates for some specific dimensions of target and control registers.
The concept of quantum complexity has far-reaching implications spanning theoretical computer science, quantum many-body physics, and high-energy physics.The quantum complexity of a unitary transformation or quantum state is defined as the size of the shortest quantum computation that executes the unitary or prepares the state.It is reasonable to expect that the complexity of a quantum state governed by a chaotic many-body Hamiltonian grows linearly with time for a time that is exponential in the system size; however, because it is hard to rule out a shortcut that improves the efficiency of a computation, it is notoriously difficult to derive lower bounds on quantum complexity for particular unitaries or states without making additional assumptions.To go further, one may study more generic models of complexity growth.We provide a rigorous connection between complexity growth and unitary k-designs, ensembles that capture the randomness of the unitary group.This connection allows us to leverage existing results about design growth to draw conclusions about the growth of complexity.We prove that local random quantum circuits generate unitary transformations whose complexity grows linearly for a long time, mirroring the behavior one expects in chaotic quantum systems and verifying conjectures by Brown and Susskind.Moreover, our results apply under a strong definition of quantum complexity based on optimal distinguishing measurements.
A random unitary quantum circuit is expected to be incompressible for exponentially long times. We show that the constant-error circuit complexity of a random unitary circuit grows almost linearly with time as Ω(T/log⁡T)Ω(T/\log T)Ω(T/logT). The bound holds for all 2≤T≤4n2\leq T\leq 4^n2≤T≤4n where nnn is the system size, and involves no other nnn-dependence. This improves previous lower bounds derived from spectral gaps and unitary designs by a factor of poly(n)\mathrm{poly}(n)poly(n). Drawing on insights from stochastic calculus, geometric functional analysis, and randomized linear algebra, our approach exploits the circuit's response to variations of individual gates and requires no control over convergence to high-order unitary designs.
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.