Computational complexity of isometric tensor network states

arXiv:2402.07975 · quant-ph, cs.CC · Submitted 2024-02-12 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: Today's paper: "Computational complexity of isometric tensor network states".

Mira: The gist: Computing local expectation values in isometric tensor network states (isoTNS) is BQP-complete,

Kai: First, who's behind it and why it matters.

Paper summary: Kai: So to summarize this paper, "Computational complexity of isometric tensor network states," they determine that computing local expectation values in isoTNS is BQP-complete when you include those with translation-invariant bulk >

Mira: The central thesis is introducing injective isoTNS, which are defined as the unique ground states of frustration-free Hamiltonians and characterized by an injectivity parameter delta between zero and one over D, where D is the bond dimension >

Kai: They then show that this injectivity adds depolarizing noise to the circuit at a rate η equal to delta squared over D squared >

Mira: The key finding here is that weakly injective isoTNS, those with small delta, are still BQP-complete, but they also find an efficient classical algorithm for computing local expectation values in strongly injective isoTNS when the injectivity parameter is zero point four one or greater >

Lev: So for someone trying to run this on real hardware, that means you can get a speedup for computation if your state has strong enough injectivity >

Kai: It also shows interesting physical properties: weakly injective isoTNS support long-range correlations, and strongly injective isoTNS become approximate Markov states with exponentially decaying correlations >

Mira: That exponential decay in the strongly injective case means the density matrix can be approximated by a sum involving only factorizing density matrices >

Lev: If you can approximate it that way, that simplifies things for any physical modeling or simulation you try to do on top of these states >

Kai: Furthermore, they explore phase transitions where isoTNS move from a hard regime to an easy phase where the monitored circuit can be sampled efficiently >

Mira: In the easy phase, if η is greater than zero point four one, then the equivalent site percolation problem becomes subcritical, meaning the occupied or filled sites don't percolate >

Kai: So they connect this computational complexity result to a physical phenomenon in how correlations spread within the network >

Mira: It shows that computing local observables is hard unless BQP equals BPP for these states, but sampling to multiplicative error is even harder unless postBQP equals postBPP or something similar >

Lev: From an error correction perspective, understanding these phase transitions tells us when the structure of the state allows for efficient measurement rather than requiring a full quantum simulation >

Conclusion: Kai: So, looking at the whole paper, "Computational complexity of isometric tensor network states," it’s about figuring out the computational power inherent in these specific variational states >

Mira: The authors are mapping 2D isoTNS to one plus 1D unitary quantum circuits and showing that computing local expectation values is BQP-complete for the general case > <ref:2402.07975#pg1,mapping 2D isoTNS to 1>

Kai: But the real contribution is introducing injective isoTNS and finding conditions—like strong injectivity above zero point four one—where you can compute those local expectation values efficiently classically >

Mira: This means we have a way to distinguish between states that require a full quantum computer simulation and those that might allow for classical approximation >

Kai: It’s about understanding the physical structure of these states through parameters like delta, and how that structure dictates whether you can sample or compute things easily >

Lev: For practical applications, this tells us which class of quantum states we should focus on if we want to build something that is computationally feasible >

Kai: Ultimately, this work provides a way to characterize these complex tensor network structures by linking their mathematical properties to actual computational hardness results for expectation values and sampling >

Department of Mathematical Sciences, University of Copenhagen · Electrical and Computer Engineering, University of Washington

quant-ph, cs.CC

Submitted: 2024-02-12

Updated: 2025-03-06

Comments: v2, new section VII on physical properties of injective isoTNS; close to published version

Journal ref: PRX Quantum 6, 020310 (2025)

DOI: 10.1103/PRXQuantum.6.020310

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 91/100

The gist: The gist: Computing local expectation values in isometric tensor network states (isoTNS) is BQP-complete, and there exists an efficient classical algorithm to compute them for strongly injective

Key concepts

Isometric Tensor Network States (isoTNS): These are a specific class of tensor network states where the tensors used in the network are isometries. They represent quantum states that can be described efficiently, and they form a variational class for studying quantum computation.
Injectivity Parameter ($\delta$): This parameter quantifies how 'injective' an isoTNS is, ranging from 0 to $1/D$. It determines the level of noise introduced into the circuit. A larger $\delta$ means stronger injectivity and potentially different computational properties for the state.
Strongly Injective States: These are isoTNS with a high injectivity parameter, specifically when $\eta \geq 0.41$. They possess exponentially decaying correlations and satisfy the uniform Markov property, allowing for efficient approximation of the density matrix.
BQP-complete: This complexity class signifies that computing local expectation values in isoTNS is as hard as solving problems solvable by a quantum computer in polynomial time. It establishes the inherent computational difficulty of this task for these states.

Terminology

BQP — 30× in this paper · explained in 2 episodes
Quantum Circuits — 16× in this paper · explained in 2 episodes
BQP-complete — 15× in this paper · explained in 2 episodes
Frustration — 10× in this paper · explained in 2 episodes
Entanglement — 7× in this paper · explained in 3 episodes
Hilbert Space — 6× in this paper · explained in 2 episodes
Phase Transitions — 6× in this paper · explained in 2 episodes
Trace — 3× in this paper · explained in 2 episodes
Ancilla Qubits — 2× in this paper · explained in 1 episode
Post-Selection — 2× in this paper · explained in 2 episodes
Accuracy — 1× in this paper · explained in 1 episode
Ancillary Qubits — 1× in this paper · explained in 1 episode
Area Law — 1× in this paper · explained in 1 episode
Clustering — 1× in this paper · explained in 2 episodes
Consistency — 1× in this paper · explained in 3 episodes
Degeneracy — 1× in this paper · explained in 3 episodes
Embeddings — 1× in this paper · explained in 2 episodes
Generalization — 1× in this paper · explained in 13 episodes
Hubbard Model — 1× in this paper · explained in 3 episodes
Matrix Product States (MPS) — 1× in this paper · explained in 2 episodes
Redundancy — 1× in this paper · explained in 2 episodes
Superradiance — 1× in this paper · explained in 3 episodes
Topological Order — 1× in this paper · explained in 2 episodes
Verification — 1× in this paper · explained in 2 episodes

Summary

The gist: Computing local expectation values in isometric tensor network states (isoTNS) is BQP-complete, and there exists an efficient classical algorithm to compute them for strongly injective isoTNS when the injectivity parameter is sufficiently large.

Computational Complexity of Local Expectation Values

The paper determines the computational power of isoTNS, finding that computing local expectation values in isoTNS (including those with translationinvariant bulk) is BQP-complete We then introduce injective isoTNS, which are those isoTNS that are the unique ground states of frustration-free Hamiltonians, and which are characterized by an injectivity parameter δ ∈ (0, 1/D], where D is the bond dimension of the isoTNS We show that injectivity necessarily adds depolarizing noise to the circuit at a rate η = δ 2/D squared We show that weakly injective isoTNS (small δ) are still BQP-complete, but that there exists an efficient classical algorithm to compute local expectation values in strongly injective isoTNS (η ≥ 0.41)

Properties of Injective and Weakly Injective States

The paper establishes two interesting physical properties of injective isoTNS, depending on their injectivity parameter On the one hand, we show that weakly injective isoTNS support long-range correlations On the other hand, strongly injective isoTNS become approximate Markov states with exponentially decaying correlations Property 1 directly follows from our ability to embed fault-tolerant quantum computation in the virtual space of the isoTNS

Contraction and Phase Transitions

We exhibit a family of isoTNS that undergo a phase transition from a hard regime to an easy phase where the monitored circuit can be sampled efficiently To find a provably efficient classical algorithm to compute a local expectation value ⟨O⟩, we adapt a method due to Aharonov [35] to map contracting the tensor network to percolation In the easy phase, if η ≥ 0.41, then the equivalent site percolation problem is subcritical (i.e. the occupied/filled sites do not percolate) and the typical size of the cluster connected to the site of the local observable is independent of the system size

Complexity of Sampling

Sampling from states to additive error is at least as hard as computing local observables, so the hardness of local expectation values extends to sampling We show that there are families of isoTNS in which sampling maps to monitored quantum circuits, which are known to become easy to simulate under strong monitoring In the easy phase, isoTNS obey a uniform Markov property, which in turns implies that connected correlation functions decay exponentially and that the corresponding ancilla dynamics is rapidly mixing

Hardness to Sample to Multiplicative Precision

We establish that even the most injective isoTNS (i.e., isoTNS with δ = 1/D, which saturate the bound in Eq. (13)), are hard to sample from within a multiplicative error This result closely mirrors earlier results that establish hardness when sampling from low-depth circuits or cluster states

Physical Properties of Strongly Injective States

Strongly injective isoTNS have exponentially decaying correlations We show that strongly injective isoTNS satisfy the uniform Markov property with exponential decay ϵ(l) This allows us to approximate ρAC through a sum involving only factorizing density matrices

Outlook and Future Directions

We have studied the computational complexity of isoTNS, a variational class of tensor network states with the additional constraint that its tensors are isometries We have shown that both computing the local expectation value and sampling from isoTNS have hard and easy phases It remains to test our results, conditions, and the algorithms we provide on isoTNS obtained from numerically optimizing for a ground state

Appendix A: Calculation of δ for Fault Tolerant Construction

The paper calculates the injectivity parameter δ by perturbing the gate tensor to injectivity, finding that δ = σmin(A) = r p k Perturbing restart tensor to injectivity yields σmin(A) = r p k 2

Appendix B: Bulk Translation-Invariant isoTNS Construction

We show that a general quantum computation can be embedded in an isoTNS with a translationally varying boundary, but a translation-invariant bulk tensor This circuit can equivalently be read as an isoTNS with bulk tensor with a translation-invariant bulk and a translationally varying boundary

Appendix A: Calculation of δ for fault tolerant construction (Second part)

The paper shows that the Kraus operators Aα1,α2;β are orthogonal i.e.

Improvements for AI systems

textbf Quantitative Complexity Analysis of State Preparation and Computation in isoTNS: Developed a framework to determine if computing local expectation values is BQP-complete or BPP-complete. This allows for the design of provable algorithms for contracting isoTNS, as shown by the result that strongly injective isoTNS can be contracted efficiently.
textbf Noise Characterization and Phase Transitions in Sampling: Established a link between injectivity and depolarizing noise, showing that injectivity necessarily adds depolarizing noise to the circuit at a rate η = δ2D2/2. This enables the construction of an efficient classical algorithm for strongly injective isoTNS when η ≥ 0.41, corresponding to an easy phase for sampling.
textbf Enhanced Correlation Analysis via Uniform Markov Property: For strongly injective isoTNS, researchers can establish that they obey the uniform Markov property with exponential decay ϵ(l), proving that strongly injective isoTNS have exponentially decaying correlations. This allows AI systems to model long-range correlations in a structured, decaying manner.
textbf Adaptive Sampling Algorithms: Developed Algorithm 1, which uses Monte Carlo sampling with a cluster size cutoff to compute local expectation values in strongly injective isoTNS in time independent of system size and inverse-polynomial in the desired precision. This provides an efficient method for sampling from complex quantum states.
-- Improved AI System Capability -- The resulting system can efficiently determine the complexity class of quantum problems mapped to 2D tensor network states, specifically distinguishing between BQP-complete and classically simulable regimes based on the injectivity parameter δ.