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:2302.06305 · Physical review. B./Physical review. B

Complexity growth for one-dimensional free-fermionic lattice models

S. Aravinda, Ranjan Modak

Published Aug 16, 2023• 2 citations
arXivHTMLPDF

Abstract

Complexity plays a very important part in quantum computing and simulation where it acts as a measure of the minimal number of gates that are required to implement a unitary circuit. We study the lower bound of the complexity [Eisert, Phys. Rev. Lett. 127, 020501 (2021)] for the unitary dynamics of the one-dimensional lattice models of noninteracting fermions. We find analytically using quasiparticle formalism, the bound grows linearly in time and is followed by a saturation for short-ranged tight-binding Hamiltonians. We show numerical evidence that for an initial Neel state the bound is maximum for tight-binding Hamiltonians as well as for the long-range hopping models. However, the increase of the bound is sublinear in time for the later, in contrast to the linear growth observed for short-range models. The upper bound of the complexity in noninteracting fermionic lattice models is calculated, which grows linearly in time even beyond the saturation time of the lower bound, and finally, it also saturates.

DOI
10.1103/physrevb.108.064309

Related papers

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•176 citations

Complexity growth in integrable and chaotic models

Vijay Balasubramanian, Matthew P. DeCross, Arjun Kar +2 more

A bstract We use the SYK family of models with N Majorana fermions to study the complexity of time evolution, formulated as the shortest geodesic length on the unitary group manifold between the identity and the time evolution operator, in free, integrable, and chaotic systems. Initially, the shortest geodesic follows the time evolution trajectory, and hence complexity grows linearly in time. We study how this linear growth is eventually truncated by the appearance and accumulation of conjugate points, which signal the presence of shorter geodesics intersecting the time evolution trajectory. By explicitly locating such “shortcuts” through analytical and numerical methods, we demonstrate that: (a) in the free theory, time evolution encounters conjugate points at a polynomial time; consequently complexity growth truncates at O ( $$ \sqrt{N} $$ N ), and we find an explicit operator which “fast-forwards” the free N -fermion time evolution with this complexity, (b) in a class of interacting integrable theories, the complexity is upper bounded by O (poly( N )), and (c) in chaotic theories, we argue that conjugate points do not occur until exponential times O ( e N ), after which it becomes possible to find infinitesimally nearby geodesics which approximate the time evolution operator. Finally, we explore the notion of eigenstate complexity in free, integrable, and chaotic models.

arXiv:2101.02209•Journal of High Energy Physics•Jul 1, 2021•81 citations

Entangling Power and Quantum Circuit Complexity

Jens Eisert

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.

arXiv:2104.03332•Physical Review Letters•Jul 7, 2021•64 citations

Solving free fermion problems on a quantum computer

Maarten Stroeks, Daan Lenterman, Barbara M. Terhal +1 more

Simulating noninteracting fermion systems is a common task in computational many-body physics. In the absence of translational symmetries, modeling free fermions on N modes usually requires poly ( N ) computational resources. While often moderate, these costs can be prohibitive in practice when large systems are considered. We present several free fermion problems that can be solved by a quantum algorithm with substantially reduced computational costs. The memory costs are exponentially improved, poly log ( N ) . The run-time improvement, compared to the best known classical algorithms, is either exponential or significantly polynomial, depending on the geometry of the problem. The simulation of free fermion dynamics belongs to the BQP-hard complexity class (i.e., as hard as any (decision) problem that can be solved on a quantum computer). This implies (under standard assumptions) that our algorithm yields an exponential speedup for classical algorithm at least for some geometries. The key technique in our algorithm is the block encoding of objects such as correlation matrices and Green's functions into a unitary. We demonstrate how such unitaries can be efficiently realized as quantum circuits, in the context of dynamics and thermal states of tight-binding Hamiltonians. The special cases of disordered and inhomogeneous lattices, as well as large nonlattice graphs, are presented in detail. Finally, we show that our simulation algorithm generalizes to other promising targets, including free-boson systems.

arXiv:2409.04550•Physical Review Research•Nov 18, 2025•15 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

Quantum complexity of time evolution with chaotic Hamiltonians

Vijay Balasubramanian, Matthew P. DeCross, Arjun Kar +1 more

A bstract We study the quantum complexity of time evolution in large- N chaotic systems, with the SYK model as our main example. This complexity is expected to increase linearly for exponential time prior to saturating at its maximum value, and is related to the length of minimal geodesics on the manifold of unitary operators that act on Hilbert space. Using the Euler-Arnold formalism, we demonstrate that there is always a geodesic between the identity and the time evolution operator e −iHt whose length grows linearly with time. This geodesic is minimal until there is an obstruction to its minimality, after which it can fail to be a minimum either locally or globally. We identify a criterion — the Eigenstate Complexity Hypothesis (ECH) — which bounds the overlap between off- diagonal energy eigenstate projectors and the k -local operators of the theory, and use it to argue that the linear geodesic will at least be a local minimum for exponential time. We show numerically that the large- N SYK model (which is chaotic) satisfies ECH and thus has no local obstructions to linear growth of complexity for exponential time, as expected from holographic duality. In contrast, we also study the case with N = 2 fermions (which is integrable) and find short-time linear complexity growth followed by oscillations. Our analysis relates complexity to familiar properties of physical theories like their spectra and the structure of energy eigenstates and has implications for the hypothesized computational complexity class separations PSPACE "Image missing" BQP/poly and PSPACE "Image missing" BQSUBEXP/subexp, and the “fast-forwarding” of quantum Hamiltonians.

arXiv:1905.05765•Journal of High Energy Physics•Jan 21, 2020•140 citations
Complexity plays a very important part in quantum computing and simulation where it acts as a measure of the minimal number of gates that are required to implement a unitary circuit. We study the lower bound of the complexity [Eisert, Phys. Rev. Lett. 127, 020501 (2021)] for the unitary dynamics of the one-dimensional lattice models of noninteracting fermions. We find analytically using quasiparticle formalism, the bound grows linearly in time and is followed by a saturation for short-ranged tight-binding Hamiltonians. We show numerical evidence that for an initial Neel state the bound is maximum for tight-binding Hamiltonians as well as for the long-range hopping models. However, the increase of the bound is sublinear in time for the later, in contrast to the linear growth observed for short-range models. The upper bound of the complexity in noninteracting fermionic lattice models is calculated, which grows linearly in time even beyond the saturation time of the lower bound, and finally, it also saturates.
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 bstract We use the SYK family of models with N Majorana fermions to study the complexity of time evolution, formulated as the shortest geodesic length on the unitary group manifold between the identity and the time evolution operator, in free, integrable, and chaotic systems. Initially, the shortest geodesic follows the time evolution trajectory, and hence complexity grows linearly in time. We study how this linear growth is eventually truncated by the appearance and accumulation of conjugate points, which signal the presence of shorter geodesics intersecting the time evolution trajectory. By explicitly locating such “shortcuts” through analytical and numerical methods, we demonstrate that: (a) in the free theory, time evolution encounters conjugate points at a polynomial time; consequently complexity growth truncates at O ( N \sqrt{N} N​ N ), and we find an explicit operator which “fast-forwards” the free N -fermion time evolution with this complexity, (b) in a class of interacting integrable theories, the complexity is upper bounded by O (poly( N )), and (c) in chaotic theories, we argue that conjugate points do not occur until exponential times O ( e N ), after which it becomes possible to find infinitesimally nearby geodesics which approximate the time evolution operator. Finally, we explore the notion of eigenstate complexity in free, integrable, and chaotic models.
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.
Simulating noninteracting fermion systems is a common task in computational many-body physics. In the absence of translational symmetries, modeling free fermions on N modes usually requires poly ( N ) computational resources. While often moderate, these costs can be prohibitive in practice when large systems are considered. We present several free fermion problems that can be solved by a quantum algorithm with substantially reduced computational costs. The memory costs are exponentially improved, poly log ( N ) . The run-time improvement, compared to the best known classical algorithms, is either exponential or significantly polynomial, depending on the geometry of the problem. The simulation of free fermion dynamics belongs to the BQP-hard complexity class (i.e., as hard as any (decision) problem that can be solved on a quantum computer). This implies (under standard assumptions) that our algorithm yields an exponential speedup for classical algorithm at least for some geometries. The key technique in our algorithm is the block encoding of objects such as correlation matrices and Green's functions into a unitary. We demonstrate how such unitaries can be efficiently realized as quantum circuits, in the context of dynamics and thermal states of tight-binding Hamiltonians. The special cases of disordered and inhomogeneous lattices, as well as large nonlattice graphs, are presented in detail. Finally, we show that our simulation algorithm generalizes to other promising targets, including free-boson systems.
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.
A bstract We study the quantum complexity of time evolution in large- N chaotic systems, with the SYK model as our main example. This complexity is expected to increase linearly for exponential time prior to saturating at its maximum value, and is related to the length of minimal geodesics on the manifold of unitary operators that act on Hilbert space. Using the Euler-Arnold formalism, we demonstrate that there is always a geodesic between the identity and the time evolution operator e −iHt whose length grows linearly with time. This geodesic is minimal until there is an obstruction to its minimality, after which it can fail to be a minimum either locally or globally. We identify a criterion — the Eigenstate Complexity Hypothesis (ECH) — which bounds the overlap between off- diagonal energy eigenstate projectors and the k -local operators of the theory, and use it to argue that the linear geodesic will at least be a local minimum for exponential time. We show numerically that the large- N SYK model (which is chaotic) satisfies ECH and thus has no local obstructions to linear growth of complexity for exponential time, as expected from holographic duality. In contrast, we also study the case with N = 2 fermions (which is integrable) and find short-time linear complexity growth followed by oscillations. Our analysis relates complexity to familiar properties of physical theories like their spectra and the structure of energy eigenstates and has implications for the hypothesized computational complexity class separations PSPACE "Image missing" BQP/poly and PSPACE "Image missing" BQSUBEXP/subexp, and the “fast-forwarding” of quantum Hamiltonians.