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:2011.07601 · Physical review. D/Physical review. D.

Geometry of quantum complexity

Roberto Auzzi, Stefano Baiguera, G. Bruno De Luca, Andrea Legramandi, G. Nardelli, Nicolò Zenoni

Published May 19, 2021• 1 citation
arXivHTMLPDF

Abstract

Computational complexity is a quantum information concept that recently has found applications in the holographic understanding of the black hole interior. We consider quantum computational complexity for $n$ qubits using Nielsen's geometrical approach. In the definition of complexity there is a big amount of arbitrariness due to the choice of the penalty factors, which parametrizes the cost of the elementary computational gates. In order to reproduce desired features in holography, such as ergodicity and exponential maximal complexity for large number of qubits $n$, negative curvatures are required. With the simplest choice of penalties, this is achieved at the price of singular sectional curvatures in the large $n$ limit. We investigate a choice of penalties in which we can obtain negative curvatures in a smooth way. We also analyze the relation between operator and state complexities, framing the discussion with the language of Riemannian submersions. This provides a direct relation between geodesics and curvatures in the unitaries and the states spaces, which we also exploit to give a closed-form expression for the metric on the states in terms of the one for the operators. Finally, we study conjugate points for a large number of qubits in the unitary space and we provide a strong indication that maximal complexity scales exponentially with the number of qubits in a certain regime of the penalties space.

DOI
10.1103/physrevd.103.106021

Related papers

CFT complexity and penalty factors

Stefano Baiguera, Nicolas Chagnet, Shira Chapman +1 more

A bstract Quantum complexity of conformal field theory (CFT) states has recently gained significant attention, both as a diagnostic tool in condensed matter systems and in connection with holographic observables probing black hole interiors. Previous studies have primarily focused on cases where all generators of the conformal group contribute equally to the cost of building a circuit. In this work, we present a general framework for studying the complexity of circuits in generic Lie groups, where penalty factors assign relative weights to different generators. Our approach constructs a metric on the coset space of quantum states, induced from a (pseudo-)Riemannian norm on the space of unitary circuits. The geodesics of this metric are interpreted as optimal circuits. The method builds on the formalism of (pseudo-)Riemannian submersions and connects naturally to other prescriptions in the literature, including cost function minimization along stabilizer directions and constructions based on coadjoint orbits. As a concrete application, we compute state complexity for states in one- and two-dimensional CFTs. For specific choices of penalty factors, our prescription yields a positive-definite metric with a viable interpretation as complexity; in other cases, the resulting metric is indefinite. In the viable regime, we derive analytic results when a specific penalty factor is turned off, develop perturbative expansions for small values of the penalty factors, and provide numerical results in the general case. We comment on the relation of our measure of complexity to holography.

arXiv:2507.22118•Journal of High Energy Physics•Feb 25, 2026•1 citation

The Complexity of Being Entangled

Stefano Baiguera, Shira Chapman, Giuseppe Policastro +1 more

Nielsen's approach to quantum state complexity relates the minimal number of quantum gates required to prepare a state to the length of geodesics computed with a certain norm on the manifold of unitary transformations. For a bipartite system, we investigate binding complexity, which corresponds to norms in which gates acting on a single subsystem are free of cost. We reduce the problem to the study of geodesics on the manifold of Schmidt coefficients, equipped with an appropriate metric. Binding complexity is closely related to other quantities such as distributed computing and quantum communication complexity, and has a proposed holographic dual in the context of AdS/CFT. For finite dimensional systems with a Riemannian norm, we find an exact relation between binding complexity and the minimal Rényi entropy. We also find analytic results for the most commonly used non-Riemannian norm (the so-called F1 norm) and provide lower bounds for the associated notion of state complexity ubiquitous in quantum computation and holography. We argue that our results are valid for a large class of penalty factors assigned to generators acting across the subsystems. We demonstrate that our results can be borrowed to study the usual complexity (not-binding) for a single spin for the case of the F1 norm which was previously lacking from the literature. Finally, we derive bounds for multi-partite binding complexities and the related (continuous) circuit complexity where the circuit contains at most 2 -local interactions.

arXiv:2311.04277•Quantum•Sep 12, 2024•5 citations

Quantum computational complexity from quantum information to black holes and back

Shira Chapman, Giuseppe Policastro

Abstract Quantum computational complexity estimates the difficulty of constructing quantum states from elementary operations, a problem of prime importance for quantum computation. Surprisingly, this quantity can also serve to study a completely different physical problem – that of information processing inside black holes. Quantum computational complexity was suggested as a new entry in the holographic dictionary, which extends the connection between geometry and information and resolves the puzzle of why black hole interiors keep growing for a very long time. In this pedagogical review, we present the geometric approach to complexity advocated by Nielsen and show how it can be used to define complexity for generic quantum systems; in particular, we focus on Gaussian states in QFT, both pure and mixed, and on certain classes of CFT states. We then present the conjectured relation to gravitational quantities within the holographic correspondence and discuss several examples in which different versions of the conjectures have been tested. We highlight the relation between complexity, chaos and scrambling in chaotic systems. We conclude with a discussion of open problems and future directions. This article was written for the special issue of EPJ-C Frontiers in Holographic Duality.

arXiv:2110.14672•The European Physical Journal C•Feb 1, 2022•127 citations

The Geometry of Quantum Complexity in Open Systems

Ezra Acalapati, Kausik Ghosh, Giuseppe Policastro

We extend Nielsen's geometric approach for quantum complexity from closed to open quantum systems, whose dynamics is governed by Lindbladian evolution. In this framework, complexity is defined through an optimal-control problem on the space of mixed states, with a cost assigned to both unitary and non-unitary generators. We show that the resulting geometric structure differs fundamentally from the Riemannian geometry that emerges in the case of unitary evolution. In the open-system setting, the natural geometry is typically sub-Finslerian. Dissipation makes the geodesics non-reversible, while the admissible tangent directions are restricted by the physically allowed controls. We analyze several physically motivated examples, including a single qubit subject to depolarizing and amplitude-damping channels, as well as the damped harmonic oscillator. We show that, similarly to the unitary case, varying the penalty factors in the cost functional modifies the geometric properties through changes in the flag curvature, the Finslerian analog of sectional curvature. Our results provide a geometric framework for quantifying the abstract notion of complexity in dissipative quantum systems, with potential connections to experimentally realizable setups.

quant-pharXiv:2607.08411•Jul 10, 2026•0 citations

The geometry of quantum computation

Mark R. Dowling, Michael A. Nielsen

Determining the quantum circuit complexity of a unitary operation is closely related to the problem of finding minimal length paths in a particular curved geometry [Nielsen et al, Science 311, 1133-1135 (2006)]. This paper investigates many of the basic geometric objects associated to this space, including the Levi-Civita connection, the geodesic equation, the curvature, and the Jacobi equation. We show that the optimal Hamiltonian evolution for synthesis of a desired unitary necessarily obeys a simple universal geodesic equation. As a consequence, once the initial value of the Hamiltonian is set, subsequent changes to the Hamiltonian are completely determined by the geodesic equation. We develop many analytic solutions to the geodesic equation, and a set of invariants that completely determine the geodesics. We investigate the problem of finding minimal geodesics through a desired unitary, U, and develop a procedure which allows us to deform the (known) geodesics of a simple and well understood metric to the geodesics of the metric of interest in quantum computation. This deformation procedure is illustrated using some three-qubit numerical examples. We study the computational complexity of evaluating distances on Riemmanian manifolds, and show that no efficient classical algorithm for this problem exists, subject to the assumption that good pseudorandom generators exist. Finally, we develop a canonical extension procedure for unitary operations which allows ancilla qubits to be incorporated into the geometric approach to quantum computing.

arXiv:quant-ph/0701004•Dec 31, 2006•7 citations

The geometry of quantum computation

Mark R. Dowling, Michael A. Nielsen

Determining the quantum circuit complexity of a unitary operation is closely related to the problem of finding minimal length paths in a particular curved geometry [Nielsen et al, Science 311, 1133-1135 (2006)]. This paper investigates many of the basic geometric objects associated to this space, including the Levi-Civita connection, the geodesic equation, the curvature, and the Jacobi equation. We show that the optimal Hamiltonian evolution for synthesis of a desired unitary necessarily obeys a simple universal geodesic equation. As a consequence, once the initial value of the Hamiltonian is set, subsequent changes to the Hamiltonian are completely determined by the geodesic equation. We develop many analytic solutions to the geodesic equation, and a set of invariants that completely determine the geodesics. We investigate the problem of finding minimal geodesics through a desired unitary, U, and develop a procedure which allows us to deform the (known) geodesics of a simple and well understood metric to the geodesics of the metric of interest in quantum computation. This deformation procedure is illustrated using some three-qubit numerical examples. We study the computational complexity of evaluating distances on Riemmanian manifolds, and show that no efficient classical algorithm for this problem exists, subject to the assumption that good pseudorandom generators exist. Finally, we develop a canonical extension procedure for unitary operations which allows ancilla qubits to be incorporated into the geometric approach to quantum computing.

Quantum Information and Computation•Nov 1, 2008•94 citations
Computational complexity is a quantum information concept that recently has found applications in the holographic understanding of the black hole interior. We consider quantum computational complexity for nnn qubits using Nielsen's geometrical approach. In the definition of complexity there is a big amount of arbitrariness due to the choice of the penalty factors, which parametrizes the cost of the elementary computational gates. In order to reproduce desired features in holography, such as ergodicity and exponential maximal complexity for large number of qubits nnn, negative curvatures are required. With the simplest choice of penalties, this is achieved at the price of singular sectional curvatures in the large nnn limit. We investigate a choice of penalties in which we can obtain negative curvatures in a smooth way. We also analyze the relation between operator and state complexities, framing the discussion with the language of Riemannian submersions. This provides a direct relation between geodesics and curvatures in the unitaries and the states spaces, which we also exploit to give a closed-form expression for the metric on the states in terms of the one for the operators. Finally, we study conjugate points for a large number of qubits in the unitary space and we provide a strong indication that maximal complexity scales exponentially with the number of qubits in a certain regime of the penalties space.
A bstract Quantum complexity of conformal field theory (CFT) states has recently gained significant attention, both as a diagnostic tool in condensed matter systems and in connection with holographic observables probing black hole interiors. Previous studies have primarily focused on cases where all generators of the conformal group contribute equally to the cost of building a circuit. In this work, we present a general framework for studying the complexity of circuits in generic Lie groups, where penalty factors assign relative weights to different generators. Our approach constructs a metric on the coset space of quantum states, induced from a (pseudo-)Riemannian norm on the space of unitary circuits. The geodesics of this metric are interpreted as optimal circuits. The method builds on the formalism of (pseudo-)Riemannian submersions and connects naturally to other prescriptions in the literature, including cost function minimization along stabilizer directions and constructions based on coadjoint orbits. As a concrete application, we compute state complexity for states in one- and two-dimensional CFTs. For specific choices of penalty factors, our prescription yields a positive-definite metric with a viable interpretation as complexity; in other cases, the resulting metric is indefinite. In the viable regime, we derive analytic results when a specific penalty factor is turned off, develop perturbative expansions for small values of the penalty factors, and provide numerical results in the general case. We comment on the relation of our measure of complexity to holography.
Nielsen's approach to quantum state complexity relates the minimal number of quantum gates required to prepare a state to the length of geodesics computed with a certain norm on the manifold of unitary transformations. For a bipartite system, we investigate binding complexity, which corresponds to norms in which gates acting on a single subsystem are free of cost. We reduce the problem to the study of geodesics on the manifold of Schmidt coefficients, equipped with an appropriate metric. Binding complexity is closely related to other quantities such as distributed computing and quantum communication complexity, and has a proposed holographic dual in the context of AdS/CFT. For finite dimensional systems with a Riemannian norm, we find an exact relation between binding complexity and the minimal Rényi entropy. We also find analytic results for the most commonly used non-Riemannian norm (the so-called F1 norm) and provide lower bounds for the associated notion of state complexity ubiquitous in quantum computation and holography. We argue that our results are valid for a large class of penalty factors assigned to generators acting across the subsystems. We demonstrate that our results can be borrowed to study the usual complexity (not-binding) for a single spin for the case of the F1 norm which was previously lacking from the literature. Finally, we derive bounds for multi-partite binding complexities and the related (continuous) circuit complexity where the circuit contains at most 2 -local interactions.
Abstract Quantum computational complexity estimates the difficulty of constructing quantum states from elementary operations, a problem of prime importance for quantum computation. Surprisingly, this quantity can also serve to study a completely different physical problem – that of information processing inside black holes. Quantum computational complexity was suggested as a new entry in the holographic dictionary, which extends the connection between geometry and information and resolves the puzzle of why black hole interiors keep growing for a very long time. In this pedagogical review, we present the geometric approach to complexity advocated by Nielsen and show how it can be used to define complexity for generic quantum systems; in particular, we focus on Gaussian states in QFT, both pure and mixed, and on certain classes of CFT states. We then present the conjectured relation to gravitational quantities within the holographic correspondence and discuss several examples in which different versions of the conjectures have been tested. We highlight the relation between complexity, chaos and scrambling in chaotic systems. We conclude with a discussion of open problems and future directions. This article was written for the special issue of EPJ-C Frontiers in Holographic Duality.
We extend Nielsen's geometric approach for quantum complexity from closed to open quantum systems, whose dynamics is governed by Lindbladian evolution. In this framework, complexity is defined through an optimal-control problem on the space of mixed states, with a cost assigned to both unitary and non-unitary generators. We show that the resulting geometric structure differs fundamentally from the Riemannian geometry that emerges in the case of unitary evolution. In the open-system setting, the natural geometry is typically sub-Finslerian. Dissipation makes the geodesics non-reversible, while the admissible tangent directions are restricted by the physically allowed controls. We analyze several physically motivated examples, including a single qubit subject to depolarizing and amplitude-damping channels, as well as the damped harmonic oscillator. We show that, similarly to the unitary case, varying the penalty factors in the cost functional modifies the geometric properties through changes in the flag curvature, the Finslerian analog of sectional curvature. Our results provide a geometric framework for quantifying the abstract notion of complexity in dissipative quantum systems, with potential connections to experimentally realizable setups.
Determining the quantum circuit complexity of a unitary operation is closely related to the problem of finding minimal length paths in a particular curved geometry [Nielsen et al, Science 311, 1133-1135 (2006)]. This paper investigates many of the basic geometric objects associated to this space, including the Levi-Civita connection, the geodesic equation, the curvature, and the Jacobi equation. We show that the optimal Hamiltonian evolution for synthesis of a desired unitary necessarily obeys a simple universal geodesic equation. As a consequence, once the initial value of the Hamiltonian is set, subsequent changes to the Hamiltonian are completely determined by the geodesic equation. We develop many analytic solutions to the geodesic equation, and a set of invariants that completely determine the geodesics. We investigate the problem of finding minimal geodesics through a desired unitary, U, and develop a procedure which allows us to deform the (known) geodesics of a simple and well understood metric to the geodesics of the metric of interest in quantum computation. This deformation procedure is illustrated using some three-qubit numerical examples. We study the computational complexity of evaluating distances on Riemmanian manifolds, and show that no efficient classical algorithm for this problem exists, subject to the assumption that good pseudorandom generators exist. Finally, we develop a canonical extension procedure for unitary operations which allows ancilla qubits to be incorporated into the geometric approach to quantum computing.
Determining the quantum circuit complexity of a unitary operation is closely related to the problem of finding minimal length paths in a particular curved geometry [Nielsen et al, Science 311, 1133-1135 (2006)]. This paper investigates many of the basic geometric objects associated to this space, including the Levi-Civita connection, the geodesic equation, the curvature, and the Jacobi equation. We show that the optimal Hamiltonian evolution for synthesis of a desired unitary necessarily obeys a simple universal geodesic equation. As a consequence, once the initial value of the Hamiltonian is set, subsequent changes to the Hamiltonian are completely determined by the geodesic equation. We develop many analytic solutions to the geodesic equation, and a set of invariants that completely determine the geodesics. We investigate the problem of finding minimal geodesics through a desired unitary, U, and develop a procedure which allows us to deform the (known) geodesics of a simple and well understood metric to the geodesics of the metric of interest in quantum computation. This deformation procedure is illustrated using some three-qubit numerical examples. We study the computational complexity of evaluating distances on Riemmanian manifolds, and show that no efficient classical algorithm for this problem exists, subject to the assumption that good pseudorandom generators exist. Finally, we develop a canonical extension procedure for unitary operations which allows ancilla qubits to be incorporated into the geometric approach to quantum computing.