Computational complexity of isometric tensor network states

summary

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

In short

The paper investigates the computational complexity of computing local expectation values in isometric tensor network states (isoTNS), finding it to be BQP-complete. It introduces strongly injective isoTNS, which possess efficient classical algorithms for expectation values when the injectivity parameter is high enough. These states exhibit interesting physical properties like long-range correlations or approximate Markov behavior depending on their injectivity level.

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 used across episodes

Reinforcement Learning (RL) — explained in 25 episodes
Retrieval-Augmented Generation (RAG) — explained in 16 episodes
Interpretability — explained in 15 episodes
Sample Complexity — explained in 15 episodes
Federated Learning — explained in 14 episodes
Generalization — explained in 13 episodes

This episode discusses

The paper

Computational complexity of isometric tensor network states · Read on arXiv

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

DOI: 10.1103/PRXQuantum.6.020310

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 >

More episodes

← Home