Computational complexity of isometric tensor network states
- URL: http://arxiv.org/abs/2402.07975v1
- Date: Mon, 12 Feb 2024 19:00:00 GMT
- Title: Computational complexity of isometric tensor network states
- Authors: Daniel Malz and Rahul Trivedi
- Abstract summary: We map 2D isoTNS to 1+1D unitary quantum circuits.
We find an efficient classical algorithm to compute local expectation values in strongly injective isoTNS.
Our results can be used to design provable algorithms to contract isoTNS.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We determine the computational power of isometric tensor network states
(isoTNS), a variational ansatz originally developed to numerically find and
compute properties of gapped ground states and topological states in two
dimensions. By mapping 2D isoTNS to 1+1D unitary quantum circuits, we find that
computing local expectation values in isoTNS is $\textsf{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 $\delta\in(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 $\eta=\delta^2D^2$. We show that weakly injective isoTNS
(small $\delta$) are still $\textsf{BQP}$-complete, but that there exists an
efficient classical algorithm to compute local expectation values in strongly
injective isoTNS ($\eta\geq0.41$). Sampling from isoTNS corresponds to
monitored quantum dynamics and 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. Our results can be used to design provable
algorithms to contract isoTNS. Our mapping between ground states of certain
frustration-free Hamiltonians to open circuit dynamics in one dimension fewer
may be of independent interest.
Related papers
- Predicting Ground State Properties: Constant Sample Complexity and Deep Learning Algorithms [48.869199703062606]
A fundamental problem in quantum many-body physics is that of finding ground states of local Hamiltonians.
We introduce two approaches that achieve a constant sample complexity, independent of system size $n$, for learning ground state properties.
arXiv Detail & Related papers (2024-05-28T18:00:32Z) - Neural Pfaffians: Solving Many Many-Electron Schrödinger Equations [58.130170155147205]
Neural wave functions accomplished unprecedented accuracies in approximating the ground state of many-electron systems, though at a high computational cost.
Recent works proposed amortizing the cost by learning generalized wave functions across different structures and compounds instead of solving each problem independently.
This work tackles the problem by defining overparametrized, fully learnable neural wave functions suitable for generalization across molecules.
arXiv Detail & Related papers (2024-05-23T16:30:51Z) - Spin coupling is all you need: Encoding strong electron correlation on quantum computers [0.0]
We show that quantum computers can efficiently simulate strongly correlated molecular systems by directly encoding the dominant entanglement structure in the form of spin-coupled initial states.
Our work paves the way towards scalable quantum simulation of electronic structure for classically challenging systems.
arXiv Detail & Related papers (2024-04-29T17:14:21Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks.
In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
arXiv Detail & Related papers (2024-04-29T15:04:07Z) - Isometric tensor network optimization for extensive Hamiltonians is free
of barren plateaus [0.0]
We show that there are no barren plateaus in the energy optimization of isometric tensor network states (TNS)
TNS are a promising route for an efficient quantum-computation-based investigation of strongly-correlated quantum matter.
arXiv Detail & Related papers (2023-04-27T16:45:57Z) - Two Dimensional Isometric Tensor Networks on an Infinite Strip [1.2569180784533303]
We introduce the class ofisoTNS (isoTNS) for efficient simulation of 2D systems on finite square lattices.
We iteratively transform an infinite MPS representation of a 2D quantum state into a strip isoTNS and investigate the entanglement properties of the resulting state.
Finally, we introduce an infinite time-evolving block decimation algorithm (iTEBDsuperscript2) and use it to approximate the ground state of the 2D transverse field Ising model on lattices of infinite strip geometry.
arXiv Detail & Related papers (2022-11-25T19:00:06Z) - Quantum-Inspired Tempering for Ground State Approximation using
Artificial Neural Networks [0.0]
We propose a parallel tempering method that facilitates escape from local minima.
We show that augmenting the training with quantum parallel tempering becomes useful to finding good approximations to the ground states of problem instances.
arXiv Detail & Related papers (2022-10-20T16:50:32Z) - A quantum algorithm for training wide and deep classical neural networks [72.2614468437919]
We show that conditions amenable to classical trainability via gradient descent coincide with those necessary for efficiently solving quantum linear systems.
We numerically demonstrate that the MNIST image dataset satisfies such conditions.
We provide empirical evidence for $O(log n)$ training of a convolutional neural network with pooling.
arXiv Detail & Related papers (2021-07-19T23:41:03Z) - SiMaN: Sign-to-Magnitude Network Binarization [165.5630656849309]
We show that our weight binarization provides an analytical solution by encoding high-magnitude weights into +1s, and 0s otherwise.
We prove that the learned weights of binarized networks roughly follow a Laplacian distribution that does not allow entropy.
Our method, dubbed sign-to- neural network binarization (SiMaN), is evaluated on CIFAR-10 and ImageNet.
arXiv Detail & Related papers (2021-02-16T07:03:51Z) - Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
We give scalable, explicit digital quantum algorithms to simulate the lattice Schwinger model in both NISQ and fault-tolerant settings.
In lattice units, we find a Schwinger model on $N/2$ physical sites with coupling constant $x-1/2$ and electric field cutoff $x-1/2Lambda$.
We estimate observables which we cost in both the NISQ and fault-tolerant settings by assuming a simple target observable---the mean pair density.
arXiv Detail & Related papers (2020-02-25T19:18:36Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.