An official website of the United States government
Ground-state entanglement governs various properties of quantum many-body systems at low temperatures and is the key to understanding gapped quantum phases of matter. Here we identify a structural property of entanglement in the ground state of gapped local Hamiltonians. This property is captured using a quantum information quantity known as the entanglement spread, which measures the difference between Rényi entanglement entropies. Our main result shows that gapped ground states possess limited entanglement spread across any partition of the system, exhibiting an area-law scaling. Our result applies to systems with interactions described by any graph, but we obtain an improved bound for the special case of lattices. These interaction graphs include cases where entanglement entropy is known not to satisfy an area law. We achieve our results first by connecting the ground-state entanglement to the communication complexity of testing bipartite entangled states and then devising a communication scheme for testing ground states using recently developed quantum algorithms for Hamiltonian simulation.
more »
« less
Complexity Phase Transitions Generated by Entanglement
Entanglement is one of the physical properties of quantum systems responsible for the computational hardness of simulating quantum systems. But while the runtime of specific algorithms, notably tensor network algorithms, explicitly depends on the amount of entanglement in the system, it is unknown whether this connection runs deeper and entanglement can also cause inherent, algorithm-independent complexity. In this Letter, we quantitatively connect the entanglement present in certain quantum systems to the computational complexity of simulating those systems. Moreover, we completely characterize the entanglement and complexity as a function of a system parameter. Specifically, we consider the task of simulating single-qubit measurements of k-regular graph states on n qubits. We show that, as the regularity parameter is increased from 1 to n−1, there is a sharp transition from an easy regime with low entanglement to a hard regime with high entanglement at k = 3, and a transition back to easy and low entanglement at k = n−3. As a key technical result, we prove a duality for the simulation complexity of regular graph states between low and high regularity.
more »
« less
- Award ID(s):
- 2120757
- PAR ID:
- 10505870
- Publisher / Repository:
- American Physical Society
- Date Published:
- Journal Name:
- Physical Review Letters
- Volume:
- 131
- Issue:
- 3
- ISSN:
- 0031-9007
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Saraf, Shubhangi (Ed.)We initiate a study of the classification of approximation complexity of the eight-vertex model defined over 4-regular graphs. The eight-vertex model, together with its special case the six-vertex model, is one of the most extensively studied models in statistical physics, and can be stated as a problem of counting weighted orientations in graph theory. Our result concerns the approximability of the partition function on all 4-regular graphs, classified according to the parameters of the model. Our complexity results conform to the phase transition phenomenon from physics. We introduce a quantum decomposition of the eight-vertex model and prove a set of closure properties in various regions of the parameter space. Furthermore, we show that there are extra closure properties on 4-regular planar graphs. These regions of the parameter space are concordant with the phase transition threshold. Using these closure properties, we derive polynomial time approximation algorithms via Markov chain Monte Carlo. We also show that the eight-vertex model is NP-hard to approximate on the other side of the phase transition threshold.more » « less
-
Entanglement is essential for quantum information processing, but is limited by noise. We address this by developing high-yield entanglement distillation protocols with several advancements. (1) We extend the 2-to-1 recurrence entanglement distillation protocol to higher-rate n-to-(n−1) protocols that can correct any single-qubit errors. These protocols are evaluated through numerical simulations focusing on fidelity and yield. We also outline a method to adapt any classical error-correcting code for entanglement distillation, where the code can correct both bit-flip and phase-flip errors by incorporating Hadamard gates. (2) We propose a constant-depth decoder for stabilizer codes that transforms logical states into physical ones using single-qubit measurements. This decoder is applied to entanglement distillation protocols, reducing circuit depth and enabling protocols derived from high-performance quantum error-correcting codes. We demonstrate this by evaluating the circuit complexity for entanglement distillation protocols based on surface codes and quantum convolutional codes. (3) Our stabilizer entanglement distillation techniques advance quantum computing. We propose a fault-tolerant protocol for constant-depth encoding and decoding of arbitrary states in surface codes, with potential extensions to more general quantum low-density parity-check codes. This protocol is feasible with state-of-the-art reconfigurable atom arrays and surpasses the limits of conventional logarithmic depth encoders. Overall, our study integrates stabilizer formalism, measurement-based quantum computing, and entanglement distillation, advancing both quantum communication and computing.more » « less
-
Abstract Quantum systems have entered a competitive regime in which classical computers must make approximations to represent highly entangled quantum states1,2. However, in this beyond-classically-exact regime, fidelity comparisons between quantum and classical systems have so far been limited to digital quantum devices2–5, and it remains unsolved how to estimate the actual entanglement content of experiments6. Here, we perform fidelity benchmarking and mixed-state entanglement estimation with a 60-atom analogue Rydberg quantum simulator, reaching a high-entanglement entropy regime in which exact classical simulation becomes impractical. Our benchmarking protocol involves extrapolation from comparisons against an approximate classical algorithm, introduced here, with varying entanglement limits. We then develop and demonstrate an estimator of the experimental mixed-state entanglement6, finding our experiment is competitive with state-of-the-art digital quantum devices performing random circuit evolution2–5. Finally, we compare the experimental fidelity against that achieved by various approximate classical algorithms, and find that only the algorithm we introduce is able to keep pace with the experiment on the classical hardware we use. Our results enable a new model for evaluating the ability of both analogue and digital quantum devices to generate entanglement in the beyond-classically-exact regime, and highlight the evolving divide between quantum and classical systems.more » « less
-
A spanner of a graph is a subgraph that preserves lengths of shortest paths up to a multiplicative distortion. For every k, a spanner with size O(n^{1+1/k}) and stretch (2k+1) can be constructed by a simple centralized greedy algorithm, and this is tight assuming Erdős girth conjecture. In this paper we study the problem of constructing spanners in a local manner, specifically in the Local Computation Model proposed by Rubinfeld et al. (ICS 2011). We provide a randomized Local Computation Agorithm (LCA) for constructing (2r-1)-spanners with Õ(n^{1+1/r}) edges and probe complexity of Õ(n^{1-1/r}) for r ∈ {2,3}, where n denotes the number of vertices in the input graph. Up to polylogarithmic factors, in both cases, the stretch factor is optimal (for the respective number of edges). In addition, our probe complexity for r = 2, i.e., for constructing a 3-spanner, is optimal up to polylogarithmic factors. Our result improves over the probe complexity of Parter et al. (ITCS 2019) that is Õ(n^{1-1/2r}) for r ∈ {2,3}. Both our algorithms and the algorithms of Parter et al. use a combination of neighbor-probes and pair-probes in the above-mentioned LCAs. For general k ≥ 1, we provide an LCA for constructing O(k²)-spanners with Õ(n^{1+1/k}) edges using O(n^{2/3}Δ²) neighbor-probes, improving over the Õ(n^{2/3}Δ⁴) algorithm of Parter et al. By developing a new randomized LCA for graph decomposition, we further improve the probe complexity of the latter task to be O(n^{2/3-(1.5-α)/k}Δ²), for any constant α > 0. This latter LCA may be of independent interest.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1103/PhysRevLett.131.030601
