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:quant-ph/0311017 · Physical Review A

Universality of entanglement and quantum-computation complexity

Román Orús, José Ignacio Latorre

Published May 12, 2004• 76 citations
arXivHTMLPDF

Abstract

We study the universality of scaling of entanglement in Shor's factoring algorithm and in adiabatic quantum algorithms across a quantum phase transition for both the $NP$-complete exact cover problem as well as Grover's problem. The analytic result for Shor's algorithm shows a linear scaling of the entropy in terms of the number of qubits, therefore making it hard to generate an efficient classical simulation protocol. A similar result is obtained numerically for the quantum adiabatic evolution exact cover algorithm, which also shows universality of the quantum phase transition near which the system evolves. On the other hand, entanglement in Grover's adiabatic algorithm remains a bounded quantity even at the critical point. The classification of scaling of entanglement appears as a natural grading of the computational complexity of simulating quantum phase transitions.

DOI
10.1103/physreva.69.052308

Related papers

Adiabatic quantum computation and quantum phase transitions

José Ignacio Latorre, Román Orús

We analyze the ground-state entanglement in a quantum adiabatic evolution algorithm designed to solve the $NP$-complete Exact Cover problem. The entropy of entanglement seems to obey linear and universal scaling at the point where the energy gap becomes small, suggesting that the system passes near a quantum phase transition. Such a large scaling of entanglement suggests that the effective connectivity of the system diverges as the number of qubits goes to infinity and that this algorithm cannot be efficiently simulated by classical means. On the other hand, entanglement in Grover's algorithm is bounded by a constant.

arXiv:quant-ph/0308042•Physical Review A•Jun 2, 2004•57 citations

Entanglement Entropy Scaling and Entropic Computational Capacity in Quantum Many Body Systems

Bannishikha Banerjee

Abstract Entanglement entropy governs the classical simulability of quantum many-body states, yet its role as an operational computational resource has lacked a unified, dimensionless quantification. Here we introduce the Entropic Computational Capacity (ECC) — defined as the ratio of the ground-state von Neumann entropy of a subsystem to the theoretical Page maximum — and map it across the critical-to-gapped quantum phase diagram of the spin-½ XXZ chain using exact diagonalization (N ≤ 10 sites, PBC). At critical points, ECC obeys universal logarithmic scaling governed by the CFT central charge c, with c = 1.0825 ± 0.0073 (XX model) and c = 1.1037 ± 0.0085 (Heisenberg), consistent with the exact value c = 1. Deep in the gapped Néel phase, ECC falls by a factor of ~ 1.39×. We prove three theorems: (i) universal ECC scaling at CFT critical points; (ii) polynomial ECC suppression by Hastings’ area law; (iii) Hölder continuity of ECC under local perturbations. A fourth result (Proposition 1) shows ECC lower-bounds the MPS bond dimension, directly quantifying classical simulation hardness. Eigenstate ECC spectra reveal a sharp transition from area-law ground states (ECC = 0.1648) to near-volume-law excited states (ECC = 0.6989), consistent with ETH. Disorder-averaged ECC variance peaks at the predicted MBL crossover, establishing ECC as a disorder diagnostic. Six simulation figures with full numerical data are presented.

•May 20, 2026•0 citations

Entanglement, quantum phase transitions and quantum algorithms

Román Orús

The work that we present in this thesis tries to be at the crossover of quantum information science, quantum many-body physics, and quantum field theory. We use tools from these three fields to analyze problems that arise in the interdisciplinary intersection. More concretely, in Chapter 1 we consider the irreversibility of renormalization group flows from a quantum information perspective by using majorization theory and conformal field theory. In Chapter 2 we compute the entanglement of a single copy of a bipartite quantum system for a variety of models by using techniques from conformal field theory and Toeplitz matrices. The entanglement entropy of the so-called Lipkin-Meshkov-Glick model is computed in Chapter 3, showing analogies with that of (1+1)-dimensional quantum systems. In Chapter 4 we apply the ideas of scaling of quantum correlations in quantum phase transitions to the study of quantum algorithms, focusing on Shor's factorization algorithm and quantum algorithms by adiabatic evolution solving an NP-complete and the searching problems. Also, in Chapter 5 we use techniques originally inspired by condensed-matter physics to develop classical simulations, using the so-called matrix product states, of an adiabatic quantum algorithm. Finally, in Chapter 6 we consider the behavior of some families of quantum algorithms from the perspective of majorization theory. The structure within each Chapter is such that the last section always summarizes the basic results. Some general conclusions and possible future directions are briefly discussed in Chapter 7. Appendix A, Appendix B and Appendix C respectively deal with some basic notions on majorization theory, conformal field theory, and classical complexity theory.

arXiv:quant-ph/0608013•Aug 1, 2006•2 citations

Macroscopic entanglement in Quantum Computation

Akihisa Ukena, Shimizu, Akira

We investigate macroscopic entanglement of quantum states in quantum computers, where we say a quantum state is entangled macroscopically if the state has superposition of macroscopically distinct states. The index $p$ of the macroscopic entanglement is calculated as a function of the step of the computation, for Grover's quantum search algorithm and Shor's factoring algorithm. It is found that whether macroscopically entangled states are used or not depends on the numbers and properties of the solutions to the problem to be solved. When the solutions are such that the problem becomes hard in the sense that classical algorithms take more than polynomial steps to find a solution, macroscopically entangled states are always used in Grover's algorithm and almost always used in Shor's algorithm. Since they are representative algorithms for unstructured and structured problems, respectively, our results support strongly the conjecture that quantum computers utilize macroscopically entangled states when they solve hard problems much faster than any classical algorithms.

arXiv:quant-ph/0505057•May 9, 2005•4 citations

ENTANGLEMENT IN ADIABATIC QUANTUM SEARCHING ALGORITHMS

Wen Jiayan, Daowen Qiu

Quantum entanglement is widely considered as one of the key resources for quantum-computational power. However, present interpretations of entanglement in speeding up of quantum algorithms remain far from complete. We analyze and compare the behaviors of entanglement during the adiabatic evolution of Grover's quantum search algorithms with complexity [Formula: see text] and O(1), respectively. Our results show that entanglement has a significant impact on the computational efficiency of both algorithms. That is, the greater the entanglement, the higher is the quantum computation, and vice versa. Furthermore, the correlations between entanglement and energy are discussed. It is observed that for the algorithm with complexity O(1), its entanglement degree becomes larger when the energy input into the quantum system increases, thus making the algorithm more efficient.

International Journal of Quantum Information•Oct 1, 2008•9 citations

New Dynamical Scaling Universality for Quantum Networks Across Adiabatic Quantum Phase Transitions

Oscar L. Acevedo, Luis Quiroga, Ferney J. Rodríguez +1 more

We reveal universal dynamical scaling behavior across adiabatic quantum phase transitions in networks ranging from traditional spatial systems (Ising model) to fully connected ones (Dicke and Lipkin-Meshkov-Glick models). Our findings, which lie beyond traditional critical exponent analysis and adiabatic perturbation approximations, are applicable even where excitations have not yet stabilized and, hence, provide a time-resolved understanding of quantum phase transitions encompassing a wide range of adiabatic regimes. We show explicitly that even though two systems may traditionally belong to the same universality class, they can have very different adiabatic evolutions. This implies that more stringent conditions need to be imposed than at present, both for quantum simulations where one system is used to simulate the other and for adiabatic quantum computing schemes.

arXiv:1312.5288•Physical Review Letters•Jan 22, 2014•53 citations
We study the universality of scaling of entanglement in Shor's factoring algorithm and in adiabatic quantum algorithms across a quantum phase transition for both the NPNPNP-complete exact cover problem as well as Grover's problem. The analytic result for Shor's algorithm shows a linear scaling of the entropy in terms of the number of qubits, therefore making it hard to generate an efficient classical simulation protocol. A similar result is obtained numerically for the quantum adiabatic evolution exact cover algorithm, which also shows universality of the quantum phase transition near which the system evolves. On the other hand, entanglement in Grover's adiabatic algorithm remains a bounded quantity even at the critical point. The classification of scaling of entanglement appears as a natural grading of the computational complexity of simulating quantum phase transitions.
We analyze the ground-state entanglement in a quantum adiabatic evolution algorithm designed to solve the NPNPNP-complete Exact Cover problem. The entropy of entanglement seems to obey linear and universal scaling at the point where the energy gap becomes small, suggesting that the system passes near a quantum phase transition. Such a large scaling of entanglement suggests that the effective connectivity of the system diverges as the number of qubits goes to infinity and that this algorithm cannot be efficiently simulated by classical means. On the other hand, entanglement in Grover's algorithm is bounded by a constant.
Abstract Entanglement entropy governs the classical simulability of quantum many-body states, yet its role as an operational computational resource has lacked a unified, dimensionless quantification. Here we introduce the Entropic Computational Capacity (ECC) — defined as the ratio of the ground-state von Neumann entropy of a subsystem to the theoretical Page maximum — and map it across the critical-to-gapped quantum phase diagram of the spin-½ XXZ chain using exact diagonalization (N ≤ 10 sites, PBC). At critical points, ECC obeys universal logarithmic scaling governed by the CFT central charge c, with c = 1.0825 ± 0.0073 (XX model) and c = 1.1037 ± 0.0085 (Heisenberg), consistent with the exact value c = 1. Deep in the gapped Néel phase, ECC falls by a factor of ~ 1.39×. We prove three theorems: (i) universal ECC scaling at CFT critical points; (ii) polynomial ECC suppression by Hastings’ area law; (iii) Hölder continuity of ECC under local perturbations. A fourth result (Proposition 1) shows ECC lower-bounds the MPS bond dimension, directly quantifying classical simulation hardness. Eigenstate ECC spectra reveal a sharp transition from area-law ground states (ECC = 0.1648) to near-volume-law excited states (ECC = 0.6989), consistent with ETH. Disorder-averaged ECC variance peaks at the predicted MBL crossover, establishing ECC as a disorder diagnostic. Six simulation figures with full numerical data are presented.
The work that we present in this thesis tries to be at the crossover of quantum information science, quantum many-body physics, and quantum field theory. We use tools from these three fields to analyze problems that arise in the interdisciplinary intersection. More concretely, in Chapter 1 we consider the irreversibility of renormalization group flows from a quantum information perspective by using majorization theory and conformal field theory. In Chapter 2 we compute the entanglement of a single copy of a bipartite quantum system for a variety of models by using techniques from conformal field theory and Toeplitz matrices. The entanglement entropy of the so-called Lipkin-Meshkov-Glick model is computed in Chapter 3, showing analogies with that of (1+1)-dimensional quantum systems. In Chapter 4 we apply the ideas of scaling of quantum correlations in quantum phase transitions to the study of quantum algorithms, focusing on Shor's factorization algorithm and quantum algorithms by adiabatic evolution solving an NP-complete and the searching problems. Also, in Chapter 5 we use techniques originally inspired by condensed-matter physics to develop classical simulations, using the so-called matrix product states, of an adiabatic quantum algorithm. Finally, in Chapter 6 we consider the behavior of some families of quantum algorithms from the perspective of majorization theory. The structure within each Chapter is such that the last section always summarizes the basic results. Some general conclusions and possible future directions are briefly discussed in Chapter 7. Appendix A, Appendix B and Appendix C respectively deal with some basic notions on majorization theory, conformal field theory, and classical complexity theory.
We investigate macroscopic entanglement of quantum states in quantum computers, where we say a quantum state is entangled macroscopically if the state has superposition of macroscopically distinct states. The index ppp of the macroscopic entanglement is calculated as a function of the step of the computation, for Grover's quantum search algorithm and Shor's factoring algorithm. It is found that whether macroscopically entangled states are used or not depends on the numbers and properties of the solutions to the problem to be solved. When the solutions are such that the problem becomes hard in the sense that classical algorithms take more than polynomial steps to find a solution, macroscopically entangled states are always used in Grover's algorithm and almost always used in Shor's algorithm. Since they are representative algorithms for unstructured and structured problems, respectively, our results support strongly the conjecture that quantum computers utilize macroscopically entangled states when they solve hard problems much faster than any classical algorithms.
Quantum entanglement is widely considered as one of the key resources for quantum-computational power. However, present interpretations of entanglement in speeding up of quantum algorithms remain far from complete. We analyze and compare the behaviors of entanglement during the adiabatic evolution of Grover's quantum search algorithms with complexity [Formula: see text] and O(1), respectively. Our results show that entanglement has a significant impact on the computational efficiency of both algorithms. That is, the greater the entanglement, the higher is the quantum computation, and vice versa. Furthermore, the correlations between entanglement and energy are discussed. It is observed that for the algorithm with complexity O(1), its entanglement degree becomes larger when the energy input into the quantum system increases, thus making the algorithm more efficient.
We reveal universal dynamical scaling behavior across adiabatic quantum phase transitions in networks ranging from traditional spatial systems (Ising model) to fully connected ones (Dicke and Lipkin-Meshkov-Glick models). Our findings, which lie beyond traditional critical exponent analysis and adiabatic perturbation approximations, are applicable even where excitations have not yet stabilized and, hence, provide a time-resolved understanding of quantum phase transitions encompassing a wide range of adiabatic regimes. We show explicitly that even though two systems may traditionally belong to the same universality class, they can have very different adiabatic evolutions. This implies that more stringent conditions need to be imposed than at present, both for quantum simulations where one system is used to simulate the other and for adiabatic quantum computing schemes.