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:1906.00324

Ubiquitous Complexity of Entanglement Spectra

Bin Cheng, Man‐Hong Yung

Published Jun 2, 2019• 0 citations
arXivHTMLPDF

Abstract

In recent years, the entanglement spectra of quantum states have been identified to be highly valuable for improving our understanding on many problems in quantum physics, such as classification of topological phases, symmetry-breaking phases, and eigenstate thermalization, etc. However, it remains a major challenge to fully characterize the entanglement spectrum of a given quantum state. An outstanding problem is whether the difficulty is intrinsically technical or fundamental? Here using the tools in computational complexity, we perform a rigorous analysis to pin down the counting complexity of entanglement spectra of (i) states generated by polynomial-time quantum circuits, (ii) ground states of gapped 5-local Hamiltonians, and (iii) projected entangled-pair states (PEPS). We prove that despite the state complexity, the problems of counting the number of sizable elements in the entanglement spectra all belong to the class $\mathsf{\# P}$-complete, which is as hard as calculating the partition functions of Ising models. Our result suggests that the absence of an efficient method for solving the problem is fundamental in nature, from the point of view of computational complexity theory.

DOI
10.48550/arxiv.1906.00324

Related papers

Computational Complexity of Projected Entangled Pair States

Norbert Schuch, Michael M. Wolf, Frank Verstraete +1 more

We determine the computational power of preparing projected entangled pair states (PEPS), as well as the complexity of classically simulating them, and generally the complexity of contracting tensor networks. While creating PEPS allows us to solve PP problems, the latter two tasks are both proven to be #P-complete. We further show how PEPS can be used to approximate ground states of gapped Hamiltonians and that creating them is easier than creating arbitrary PEPS. The main tool for our proofs is a duality between PEPS and postselection which allows us to use existing results from quantum complexity.

arXiv:quant-ph/0611050•Physical Review Letters•Apr 4, 2007•312 citations

Entanglement Spectra as Topological Invariants of C*-Algebras

Revista, Zen, MATH, 10

This paper explores the rigorous formulation of entanglement spectra within the framework of C*-algebras, proposing their utility as robust topological invariants for classifying quantum phases of matter. Entanglement spectra, derived from the eigenvalues of reduced density matrices, have emerged as powerful diagnostic tools for characterizing topological order, often revealing hidden patterns beyond conventional symmetry-breaking paradigms. By embedding quantum systems and their subsystem decompositions into the abstract mathematical structure of C*-algebras, we provide a generalized and mathematically rigorous approach to define and analyze these spectra. This C*-algebraic perspective allows for a unified treatment of finite and infinite quantum systems, including those arising in quantum field theory, and naturally incorporates the algebraic notion of locality and quantum states. We demonstrate how specific features of the entanglement spectrum, such as degeneracy patterns or gaps, can be viewed as invariants under C*-algebraic deformations that preserve the underlying topological order. This framework suggests a deep connection between the algebraic properties of observables, the structure of entanglement, and the classification of topological phases, potentially linking to established mathematical tools like K-theory. The work establishes a theoretical foundation for leveraging entanglement spectra as fundamental topological indicators within a highly abstract yet physically relevant algebraic setting.

•Dec 6, 2025•0 citations

Spectra of Tensor Networks and Entanglement Measures

PAULO SÉRGIO DE ANDRADE

Tensor networks have emerged as a powerful theoretical and computational framework for understanding and simulating quantum many-body systems. Their efficiency in representing quantum states, particularly those satisfying area laws of entanglement, is intimately linked to the structure of their constituent tensors. A fundamental aspect of these networks is their spectral properties, which manifest in various forms, such as the singular values of bond tensors or the eigenvalues of associated transfer matrices. Concurrently, entanglement measures provide quantitative insights into the quantum correlations present within these systems. This paper explores the intricate relationship between the spectra arising from tensor network representations and the different entanglement measures used to characterize quantum states. We delve into how the decay rates of singular values directly impact entanglement entropy, how entanglement spectra derived from Schmidt decompositions can reveal topological order, and how the spectral gaps of transfer matrices are connected to correlation lengths. By analyzing various tensor network architectures, including Matrix Product States (MPS) and Projected Entangled Pair States (PEPS), we elucidate the mechanisms through which their spectral features encode profound information about quantum entanglement. The study highlights how a deeper understanding of these spectral properties can not only guide the construction of more efficient tensor network algorithms but also provide fundamental insights into the nature of quantum phases and phase transitions.

•Nov 23, 2025•0 citations

On the complexity of estimating ground state entanglement and free energy

Sevag Gharibian, Jonas Kamminga

Understanding the entanglement structure of local Hamiltonian ground spaces is a physically motivated problem, with applications ranging from tensor network design to quantum error-correcting codes. To this end, we study the complexity of estimating ground state entanglement, and more generally entropy estimation for low energy states and Gibbs states. We find, in particular, that the classes qq-QAM [Kobayashi, le Gall, Nishimura, SICOMP 2019] (a quantum analogue of public-coin AM) and QMA(2) (QMA with unentangled proofs) play a crucial role for such problems, showing: (1) Detecting a high-entanglement ground state is qq-QAM-complete, (2) computing an additive error approximation to the Helmholtz free energy (equivalently, a multiplicative error approximation to the partition function) is in qq-QAM, (3) detecting a low-entanglement ground state is QMA(2)-hard, and (4) detecting low energy states which are close to product states can range from QMA-complete to QMA(2)-complete. Our results make progress on an open question of [Bravyi, Chowdhury, Gosset and Wocjan, Nature Physics 2022] on free energy, and yield the first QMA(2)-complete Hamiltonian problem using local Hamiltonians (cf. the sparse QMA(2)-complete Hamiltonian problem of [Chailloux, Sattath, CCC 2012]).

arXiv:2510.06796•Oct 8, 2025•0 citations

On the hardness of learning ground state entanglement of geometrically local Hamiltonians

Adam Bouland, Chenyi Zhang, Zixin Zhou

Characterizing the entanglement structure of ground states of local Hamiltonians is a fundamental problem in quantum information. In this work we study the computational complexity of this problem, given the Hamiltonian as input. Our main result is that to show it is cryptographically hard to determine if the ground state of a geometrically local, polynomially gapped Hamiltonian on qudits ($d=O(1)$) has near-area law vs near-volume law entanglement. This improves prior work of Bouland et al. (arXiv:2311.12017) showing this for non-geometrically local Hamiltonians. In particular we show this problem is roughly factoring-hard in 1D, and LWE-hard in 2D. Our proof works by constructing a novel form of public-key pseudo-entanglement which is highly space-efficient, and combining this with a modification of Gottesman and Irani's quantum Turing machine to Hamiltonian construction. Our work suggests that the problem of learning so-called "gapless" quantum phases of matter might be intractable.

arXiv:2411.04353•Nov 7, 2024•1 citation

Computational complexity in entanglement transformations

Eric Chitambar

In physics, systems having three parts are typically much more difficult to analyze than those having just two. Even in classical mechanics, predicting the motion of three interacting celestial bodies remains an insurmountable challenge while the analogous two-body problem has an elementary solution. It is as if just by adding a third party, a fundamental change occurs in the structure of the problem that renders it unsolvable. In this thesis, we demonstrate how such an effect is likewise present in the theory of quantum entanglement. In fact, the complexity differences between two-party and three-party entanglement become quite conspicuous when comparing the difficulty in deciding what state changes are possible for these systems when no additional entanglement is consumed in the transformation process. We examine this entanglement transformation question and its variants in the language of computational complexity theory, a powerful subject that formalizes the concept of problem difficulty. Since deciding feasibility of a specified bipartite transformation is relatively easy, this task belongs to the complexity class P. On the other hand, for tripartite systems, we find the problem to be NP-Hard, meaning that its solution is at least as hard as the solution to some of the most difficult problems humans have encountered. One can then rigorously defend the assertion that a fundamental complexity difference exists between bipartite and tripartite entanglement since unlike the former, the full range of forms realizable by the latter is incalculable (assuming P unequal to NP). However, similar to the three-body celestial problem, when one examines a special subclass of the problem - invertible transformations on systems having at least one qubit subsystem - we prove that the problem can be solved efficiently. As a hybrid of the two questions, we find that the question of tripartite to bipartite transformations can be solved by an efficient randomized algorithm. Our results are obtained by encoding well-studied computational problems such as polynomial identity testing and tensor rank into questions of entanglement transformation. In this way, entanglement theory provides a physical manifestation of some of the most puzzling and abstract classical computation questions.

•Jan 1, 2010•0 citations
In recent years, the entanglement spectra of quantum states have been identified to be highly valuable for improving our understanding on many problems in quantum physics, such as classification of topological phases, symmetry-breaking phases, and eigenstate thermalization, etc. However, it remains a major challenge to fully characterize the entanglement spectrum of a given quantum state. An outstanding problem is whether the difficulty is intrinsically technical or fundamental? Here using the tools in computational complexity, we perform a rigorous analysis to pin down the counting complexity of entanglement spectra of (i) states generated by polynomial-time quantum circuits, (ii) ground states of gapped 5-local Hamiltonians, and (iii) projected entangled-pair states (PEPS). We prove that despite the state complexity, the problems of counting the number of sizable elements in the entanglement spectra all belong to the class #P\mathsf{\# P}#P-complete, which is as hard as calculating the partition functions of Ising models. Our result suggests that the absence of an efficient method for solving the problem is fundamental in nature, from the point of view of computational complexity theory.
We determine the computational power of preparing projected entangled pair states (PEPS), as well as the complexity of classically simulating them, and generally the complexity of contracting tensor networks. While creating PEPS allows us to solve PP problems, the latter two tasks are both proven to be #P-complete. We further show how PEPS can be used to approximate ground states of gapped Hamiltonians and that creating them is easier than creating arbitrary PEPS. The main tool for our proofs is a duality between PEPS and postselection which allows us to use existing results from quantum complexity.
This paper explores the rigorous formulation of entanglement spectra within the framework of C*-algebras, proposing their utility as robust topological invariants for classifying quantum phases of matter. Entanglement spectra, derived from the eigenvalues of reduced density matrices, have emerged as powerful diagnostic tools for characterizing topological order, often revealing hidden patterns beyond conventional symmetry-breaking paradigms. By embedding quantum systems and their subsystem decompositions into the abstract mathematical structure of C*-algebras, we provide a generalized and mathematically rigorous approach to define and analyze these spectra. This C*-algebraic perspective allows for a unified treatment of finite and infinite quantum systems, including those arising in quantum field theory, and naturally incorporates the algebraic notion of locality and quantum states. We demonstrate how specific features of the entanglement spectrum, such as degeneracy patterns or gaps, can be viewed as invariants under C*-algebraic deformations that preserve the underlying topological order. This framework suggests a deep connection between the algebraic properties of observables, the structure of entanglement, and the classification of topological phases, potentially linking to established mathematical tools like K-theory. The work establishes a theoretical foundation for leveraging entanglement spectra as fundamental topological indicators within a highly abstract yet physically relevant algebraic setting.
Tensor networks have emerged as a powerful theoretical and computational framework for understanding and simulating quantum many-body systems. Their efficiency in representing quantum states, particularly those satisfying area laws of entanglement, is intimately linked to the structure of their constituent tensors. A fundamental aspect of these networks is their spectral properties, which manifest in various forms, such as the singular values of bond tensors or the eigenvalues of associated transfer matrices. Concurrently, entanglement measures provide quantitative insights into the quantum correlations present within these systems. This paper explores the intricate relationship between the spectra arising from tensor network representations and the different entanglement measures used to characterize quantum states. We delve into how the decay rates of singular values directly impact entanglement entropy, how entanglement spectra derived from Schmidt decompositions can reveal topological order, and how the spectral gaps of transfer matrices are connected to correlation lengths. By analyzing various tensor network architectures, including Matrix Product States (MPS) and Projected Entangled Pair States (PEPS), we elucidate the mechanisms through which their spectral features encode profound information about quantum entanglement. The study highlights how a deeper understanding of these spectral properties can not only guide the construction of more efficient tensor network algorithms but also provide fundamental insights into the nature of quantum phases and phase transitions.
Understanding the entanglement structure of local Hamiltonian ground spaces is a physically motivated problem, with applications ranging from tensor network design to quantum error-correcting codes. To this end, we study the complexity of estimating ground state entanglement, and more generally entropy estimation for low energy states and Gibbs states. We find, in particular, that the classes qq-QAM [Kobayashi, le Gall, Nishimura, SICOMP 2019] (a quantum analogue of public-coin AM) and QMA(2) (QMA with unentangled proofs) play a crucial role for such problems, showing: (1) Detecting a high-entanglement ground state is qq-QAM-complete, (2) computing an additive error approximation to the Helmholtz free energy (equivalently, a multiplicative error approximation to the partition function) is in qq-QAM, (3) detecting a low-entanglement ground state is QMA(2)-hard, and (4) detecting low energy states which are close to product states can range from QMA-complete to QMA(2)-complete. Our results make progress on an open question of [Bravyi, Chowdhury, Gosset and Wocjan, Nature Physics 2022] on free energy, and yield the first QMA(2)-complete Hamiltonian problem using local Hamiltonians (cf. the sparse QMA(2)-complete Hamiltonian problem of [Chailloux, Sattath, CCC 2012]).
Characterizing the entanglement structure of ground states of local Hamiltonians is a fundamental problem in quantum information. In this work we study the computational complexity of this problem, given the Hamiltonian as input. Our main result is that to show it is cryptographically hard to determine if the ground state of a geometrically local, polynomially gapped Hamiltonian on qudits (d=O(1)d=O(1)d=O(1)) has near-area law vs near-volume law entanglement. This improves prior work of Bouland et al. (arXiv:2311.12017) showing this for non-geometrically local Hamiltonians. In particular we show this problem is roughly factoring-hard in 1D, and LWE-hard in 2D. Our proof works by constructing a novel form of public-key pseudo-entanglement which is highly space-efficient, and combining this with a modification of Gottesman and Irani's quantum Turing machine to Hamiltonian construction. Our work suggests that the problem of learning so-called "gapless" quantum phases of matter might be intractable.
In physics, systems having three parts are typically much more difficult to analyze than those having just two. Even in classical mechanics, predicting the motion of three interacting celestial bodies remains an insurmountable challenge while the analogous two-body problem has an elementary solution. It is as if just by adding a third party, a fundamental change occurs in the structure of the problem that renders it unsolvable. In this thesis, we demonstrate how such an effect is likewise present in the theory of quantum entanglement. In fact, the complexity differences between two-party and three-party entanglement become quite conspicuous when comparing the difficulty in deciding what state changes are possible for these systems when no additional entanglement is consumed in the transformation process. We examine this entanglement transformation question and its variants in the language of computational complexity theory, a powerful subject that formalizes the concept of problem difficulty. Since deciding feasibility of a specified bipartite transformation is relatively easy, this task belongs to the complexity class P. On the other hand, for tripartite systems, we find the problem to be NP-Hard, meaning that its solution is at least as hard as the solution to some of the most difficult problems humans have encountered. One can then rigorously defend the assertion that a fundamental complexity difference exists between bipartite and tripartite entanglement since unlike the former, the full range of forms realizable by the latter is incalculable (assuming P unequal to NP). However, similar to the three-body celestial problem, when one examines a special subclass of the problem - invertible transformations on systems having at least one qubit subsystem - we prove that the problem can be solved efficiently. As a hybrid of the two questions, we find that the question of tripartite to bipartite transformations can be solved by an efficient randomized algorithm. Our results are obtained by encoding well-studied computational problems such as polynomial identity testing and tensor rank into questions of entanglement transformation. In this way, entanglement theory provides a physical manifestation of some of the most puzzling and abstract classical computation questions.