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:1903.06156 · Progress of Theoretical and Experimental Physics

Weighting gates in circuit complexity and holography

Ibrahim Akal

Published Jul 21, 2021• 5 citations
arXivHTMLPDF

Abstract

Abstract Motivated by recent studies of quantum computational complexity in quantum field theory and holography, we discuss how weighting certain classes of gates building up a quantum circuit more heavily than others affects the complexity. Utilizing Nielsen’s geometric approach to circuit complexity, we investigate the effects for a regulated field theory for which the optimal circuit is a representation of $GL(N,\mathbb{R})$. More precisely, we work out how a uniformly chosen weighting factor acting on the entangling gates affects the complexity and, particularly, its divergent behavior. We show that assigning a higher cost to the entangling gates increases the complexity. Employing penalized and unpenalized complexities for the $\mathcal{F}_{\kappa=2}$ cost, we further find an interesting relation between the latter and that based on the unpenalized $\mathcal{F}_{\kappa=1}$ cost. In addition, we exhibit how imposing such penalties modifies the leading-order UV divergence in the complexity. We show that appropriately tuning the gate weighting eliminates the additional logarithmic factor, thus resulting in a simple power-law scaling. We also compare the circuit complexity with holographic predictions, specifically based on the complexity=action conjecture, and relate the weighting factor to certain bulk quantities. Finally, we comment on certain expectations concerning the role of gate penalties in defining complexity in field theory and also speculate on possible implications for holography.

DOI
10.1093/ptep/ptab098

Related papers

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

Reflections on Virasoro circuit complexity and Berry phase

Ibrahim Akal

Recently, the notion of circuit complexity defined in symmetry group manifolds has been related to geometric actions which generally arise in the coadjoint orbit method in representation theory and play an important role in geometric quantization. On the other hand, it is known that there exists a precise relation between geometric actions and Berry phases defined in group representations. Motivated by these connections, we elaborate on a relation between circuit complexity and the group theoretic Berry phase. As the simplest setup relevant for holography, we discuss the case of two dimensional conformal field theories. In the large central charge limit, we identify the computational cost function with the Berry connection in the unitary representation of the Virasoro group. We then use the latter identification to express the Berry phase in terms of the Virasoro circuit complexity. The former can be seen as the holonomy of the Berry connection along the path in the group manifold which defines the protocol. In addition, we derive a proportionality relation between Virasoro circuit complexity and the logarithm of the inner product between a particularly chosen reference state and the prepared target state. In this sense, the logarithmic formula turns out to be approximating the complexity up to some additive constant if the building blocks of the circuit are taken to be the underlying symmetry gates. Predictions based on this formula have recently been shown to coincide with the holographic complexity proposals and the path integral optimization procedure. The found connections may therefore help to better understand such coincidences. We also discuss that our findings, put together with earlier observations, may suggest a connection between the Virasoro Berry phase and the complexity measure in the path integral optimization proposal.

arXiv:1908.08514•Physical review. D/Physical review. D.•Jan 11, 2022•10 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•56 citations

Geometry of quantum complexity

Roberto Auzzi, Stefano Baiguera, G. Bruno De Luca +3 more

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.

arXiv:2011.07601•Physical review. D/Physical review. D.•May 19, 2021•1 citation

Aspects of the first law of complexity

Alice Bernamonti, Federico Galli, Juan Hernandez +3 more

Abstract We investigate the first law of complexity proposed in Bernamonti et al (2019 Phys. Rev. Lett. 123 081601), i.e., the variation of complexity when the target state is perturbed, in more detail. Based on Nielsen’s geometric approach to quantum circuit complexity, we find the variation only depends on the end of the optimal circuit. We apply the first law to gain new insights into the quantum circuits and complexity models underlying holographic complexity. In particular, we examine the variation of the holographic complexity for both the complexity = action and complexity = volume conjectures in perturbing the AdS vacuum with coherent state excitations of a free scalar field. We also examine the variations of circuit complexity produced by the same excitations for the free scalar field theory in a fixed AdS background. In this case, our work extends the existing treatment of Gaussian coherent states to properly include the time dependence of the complexity variation. We comment on the similarities and differences of the holographic and QFT results.

arXiv:2002.05779•Journal of Physics A Mathematical and Theoretical•Apr 29, 2020•52 citations

Subsystem complexity and holography

César A. Agón, Matthew Headrick, Brian G. Swingle

Abstract As a probe of circuit complexity in holographic field theories, we study sub-system analogues based on the entanglement wedge of the bulk quantities appearing in the “complexity = volume” and “complexity = action” conjectures. We calculate these quantities for one exterior region of an eternal static neutral or charged black hole in general dimensions, dual to a thermal state on one boundary with or without chemical potential respectively, as well as for a shock wave geometry. We then define several analogues of circuit complexity for mixed states, and use tensor networks to gain intuition about them. In the action approach, we find two possible cases depending on an ambiguity in the definition of the action associated with a counterterm. In one case, there is a promising qualitative match between the holographic action and what we call the purification complexity, the minimum number of gates required to prepare an arbitrary purification of the given mixed state. In the other case, the match is to what we call the basis complexity, the minimum number of gates required to prepare the given mixed state starting from a minimal complexity state with the same eigenvalue spectrum. One way to fix this ambiguity is to choose an action definition such that UV divergent part is positive, in which case the best match to the action result is the basis complexity. In contrast, the holographic volume does not appear to match any of our definitions of mixed-state complexity.

arXiv:1804.01561•Journal of High Energy Physics•Feb 1, 2019•127 citations
Abstract Motivated by recent studies of quantum computational complexity in quantum field theory and holography, we discuss how weighting certain classes of gates building up a quantum circuit more heavily than others affects the complexity. Utilizing Nielsen’s geometric approach to circuit complexity, we investigate the effects for a regulated field theory for which the optimal circuit is a representation of GL(N,R)GL(N,\mathbb{R})GL(N,R). More precisely, we work out how a uniformly chosen weighting factor acting on the entangling gates affects the complexity and, particularly, its divergent behavior. We show that assigning a higher cost to the entangling gates increases the complexity. Employing penalized and unpenalized complexities for the Fκ=2\mathcal{F}_{\kappa=2}Fκ=2​ cost, we further find an interesting relation between the latter and that based on the unpenalized Fκ=1\mathcal{F}_{\kappa=1}Fκ=1​ cost. In addition, we exhibit how imposing such penalties modifies the leading-order UV divergence in the complexity. We show that appropriately tuning the gate weighting eliminates the additional logarithmic factor, thus resulting in a simple power-law scaling. We also compare the circuit complexity with holographic predictions, specifically based on the complexity=action conjecture, and relate the weighting factor to certain bulk quantities. Finally, we comment on certain expectations concerning the role of gate penalties in defining complexity in field theory and also speculate on possible implications for 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.
Recently, the notion of circuit complexity defined in symmetry group manifolds has been related to geometric actions which generally arise in the coadjoint orbit method in representation theory and play an important role in geometric quantization. On the other hand, it is known that there exists a precise relation between geometric actions and Berry phases defined in group representations. Motivated by these connections, we elaborate on a relation between circuit complexity and the group theoretic Berry phase. As the simplest setup relevant for holography, we discuss the case of two dimensional conformal field theories. In the large central charge limit, we identify the computational cost function with the Berry connection in the unitary representation of the Virasoro group. We then use the latter identification to express the Berry phase in terms of the Virasoro circuit complexity. The former can be seen as the holonomy of the Berry connection along the path in the group manifold which defines the protocol. In addition, we derive a proportionality relation between Virasoro circuit complexity and the logarithm of the inner product between a particularly chosen reference state and the prepared target state. In this sense, the logarithmic formula turns out to be approximating the complexity up to some additive constant if the building blocks of the circuit are taken to be the underlying symmetry gates. Predictions based on this formula have recently been shown to coincide with the holographic complexity proposals and the path integral optimization procedure. The found connections may therefore help to better understand such coincidences. We also discuss that our findings, put together with earlier observations, may suggest a connection between the Virasoro Berry phase and the complexity measure in the path integral optimization proposal.
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.
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.
Abstract We investigate the first law of complexity proposed in Bernamonti et al (2019 Phys. Rev. Lett. 123 081601), i.e., the variation of complexity when the target state is perturbed, in more detail. Based on Nielsen’s geometric approach to quantum circuit complexity, we find the variation only depends on the end of the optimal circuit. We apply the first law to gain new insights into the quantum circuits and complexity models underlying holographic complexity. In particular, we examine the variation of the holographic complexity for both the complexity = action and complexity = volume conjectures in perturbing the AdS vacuum with coherent state excitations of a free scalar field. We also examine the variations of circuit complexity produced by the same excitations for the free scalar field theory in a fixed AdS background. In this case, our work extends the existing treatment of Gaussian coherent states to properly include the time dependence of the complexity variation. We comment on the similarities and differences of the holographic and QFT results.
Abstract As a probe of circuit complexity in holographic field theories, we study sub-system analogues based on the entanglement wedge of the bulk quantities appearing in the “complexity = volume” and “complexity = action” conjectures. We calculate these quantities for one exterior region of an eternal static neutral or charged black hole in general dimensions, dual to a thermal state on one boundary with or without chemical potential respectively, as well as for a shock wave geometry. We then define several analogues of circuit complexity for mixed states, and use tensor networks to gain intuition about them. In the action approach, we find two possible cases depending on an ambiguity in the definition of the action associated with a counterterm. In one case, there is a promising qualitative match between the holographic action and what we call the purification complexity, the minimum number of gates required to prepare an arbitrary purification of the given mixed state. In the other case, the match is to what we call the basis complexity, the minimum number of gates required to prepare the given mixed state starting from a minimal complexity state with the same eigenvalue spectrum. One way to fix this ambiguity is to choose an action definition such that UV divergent part is positive, in which case the best match to the action result is the basis complexity. In contrast, the holographic volume does not appear to match any of our definitions of mixed-state complexity.