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:1104.1410 · Physical Review Letters

Preparing Projected Entangled Pair States on a Quantum Computer

Martin Schwarz, Kristan Temme, Frank Verstraete

Published Mar 13, 2012• 49 citations
arXivHTMLPDF

Abstract

We present a quantum algorithm to prepare injective projected entangled pair states (PEPS) on a quantum computer, a class of open tensor networks representing quantum states. The run time of our algorithm scales polynomially with the inverse of the minimum condition number of the PEPS projectors and, essentially, with the inverse of the spectral gap of the PEPS's parent Hamiltonian.

DOI
10.1103/physrevlett.108.110502

Related papers

Preparing topological projected entangled pair states on a quantum computer

Martin Schwarz, Kristan Temme, Frank Verstraete +2 more

Simulating exotic phases of matter that are not amenable to classical techniques is one of the most important potential applications of quantum information processing. We present an efficient algorithm for preparing a large class of topological quantum states, the $G$-injective projected entangled pair states (PEPS), on a quantum computer. Important examples include the resonant valence bond states, conjectured to be topological spin liquids. The runtime of the algorithm scales polynomially with the condition number of the PEPS projectors and inverse polynomially in the spectral gap of the PEPS parent Hamiltonian.

arXiv:1211.4050•Physical Review A•Sep 23, 2013•25 citations

Computational Complexity of Projected Entangled Pair States

Norbert Schuch, Michael M. Wolf, Frank Verstraete +1 more

We determine the computational power of preparing projected entangled pair states (PEPS), as well as the complexity of classically simulating them, and generally the complexity of contracting tensor networks. While creating PEPS allows us to solve PP problems, the latter two tasks are both proven to be #P-complete. We further show how PEPS can be used to approximate ground states of gapped Hamiltonians and that creating them is easier than creating arbitrary PEPS. The main tool for our proofs is a duality between PEPS and postselection which allows us to use existing results from quantum complexity.

arXiv:quant-ph/0611050•Physical Review Letters•Apr 4, 2007•312 citations

Computational complexity of injective projected entangled pair states

Dylan Harley, Freek Witteveen, Daniel Malz

Projected entangled pair states (PEPS) constitute a variational family of quantum states with area-law entanglement. PEPS are particularly relevant and successful for studying ground states of spatially local Hamiltonians. However, computing local expectation values in these states is known to be \postBQP-hard. Injective PEPS, where all constituent tensors fulfil an injectivity constraint, are generally believed to be better behaved, because they are unique ground states of spatially local Hamiltonians. In this work, we therefore examine how the computational hardness of contraction depends on the injectivity. We establish that below a constant positive injectivity threshold, evaluating local observables remains \postBQP-complete, while above a different constant nontrivial threshold there exists an efficient classical algorithm for the task, resolving an open question from (Anshu et al., STOC `24). We do this by proving that noisy postselected quantum computation can be made fault-tolerant.

arXiv:2509.19963•Sep 24, 2025•0 citations

Conversion of projected entangled pair states into a canonical form

Reza Haghshenas, Matthew J. O'Rourke, Garnet Kin-Lic Chan

Projected entangled pair states (PEPS) are a class of tensor networks that are believed to represent a wide variety of two-dimensional physical quantum states. However, unlike their well-known one-dimensional counterparts, the matrix product states (MPS), numerical simulations with PEPS suffer from instabilities that can be traced back to the lack of a canonical form. The authors describe how to convert a PEPS into a canonical form analogous to the one for an MPS. It is expected that this canonical form will make possible improved analytical and numerical approaches for PEPS.

arXiv:1903.03843•Physical review. B./Physical review. B•Aug 5, 2019•39 citations

Efficient 2D Tensor Network Simulation of Quantum Systems

Yuchen Pang, Tianyi Hao, Annika Dugad +2 more

Simulation of quantum systems is challenging due to the exponential size of the state space. Tensor networks provide a systematically improvable approximation for quantum states. 2D tensor networks such as Projected Entangled Pair States (PEPS) are well-suited for key classes of physical systems and quantum circuits. However, direct contraction of PEPS networks has exponential cost, while approximate algorithms require computations with large tensors. We propose new scalable algorithms and software abstractions for PEPS-based methods, accelerating the bottleneck operation of contraction and refactorization of a tensor subnetwork. We employ randomized SVD with an implicit matrix to reduce cost and memory footprint asymptotically. Further, we develop a distributed-memory PEPS library and study accuracy and efficiency of alternative algorithms for PEPS contraction and evolution on the Stampede2 supercomputer. We also simulate a popular near-term quantum algorithm, the Variational Quantum Eigensolver (VQE), and benchmark Imaginary Time Evolution (ITE), which compute ground states of Hamiltonians.

arXiv:2006.15234•International Conference for High Performance Computing, Networking, Storage and Analysis (SC)•Nov 1, 2020•17 citations

Algorithmic Locality of Quantum Tensor Network Belief Propagation

Siddhant Midha, Yifan F. Zhang, Daniel Malz +2 more

Belief propagation has recently emerged as a powerful framework for evaluating tensor networks in higher dimensions, combining computational efficiency with provable analytical guarantees. In this work, we develop the first end-to-end theory of tensor network belief propagation for a class of projected entangled pair states satisfying \emph{strong injectivity}. We show that when the injectivity parameter exceeds a constant threshold, BP fixed points can be found efficiently, and a cluster-corrected BP algorithm computes physical quantities to $1/\mathrm{poly}(N)$ error in $\mathrm{poly}(N)$ time for an $N$ qubit system. We further identify a striking phenomenon we term \emph{algorithmic locality}: local perturbations of the tensor network affect the BP fixed point with an influence decaying rapidly with distance. Moreover, through the cluster expansion, this locality extends to observables, implying that local expectation values can be approximated from local data with controlled accuracy. We exhibit three regimes admitting strong injectivity: random Gaussian PEPS with large physical dimension, high-temperature Gibbs states of commuting two-body Hamiltonians, and fixed-depth quantum circuits subject to sufficiently strong depolarizing noise. Our bounds are worst-case sufficient conditions and do not identify sharp algorithmic transitions.

quant-pharXiv:2604.21919•Apr 24, 2026•0 citations
We present a quantum algorithm to prepare injective projected entangled pair states (PEPS) on a quantum computer, a class of open tensor networks representing quantum states. The run time of our algorithm scales polynomially with the inverse of the minimum condition number of the PEPS projectors and, essentially, with the inverse of the spectral gap of the PEPS's parent Hamiltonian.
Simulating exotic phases of matter that are not amenable to classical techniques is one of the most important potential applications of quantum information processing. We present an efficient algorithm for preparing a large class of topological quantum states, the GGG-injective projected entangled pair states (PEPS), on a quantum computer. Important examples include the resonant valence bond states, conjectured to be topological spin liquids. The runtime of the algorithm scales polynomially with the condition number of the PEPS projectors and inverse polynomially in the spectral gap of the PEPS parent Hamiltonian.
We determine the computational power of preparing projected entangled pair states (PEPS), as well as the complexity of classically simulating them, and generally the complexity of contracting tensor networks. While creating PEPS allows us to solve PP problems, the latter two tasks are both proven to be #P-complete. We further show how PEPS can be used to approximate ground states of gapped Hamiltonians and that creating them is easier than creating arbitrary PEPS. The main tool for our proofs is a duality between PEPS and postselection which allows us to use existing results from quantum complexity.
Projected entangled pair states (PEPS) constitute a variational family of quantum states with area-law entanglement. PEPS are particularly relevant and successful for studying ground states of spatially local Hamiltonians. However, computing local expectation values in these states is known to be \postBQP-hard. Injective PEPS, where all constituent tensors fulfil an injectivity constraint, are generally believed to be better behaved, because they are unique ground states of spatially local Hamiltonians. In this work, we therefore examine how the computational hardness of contraction depends on the injectivity. We establish that below a constant positive injectivity threshold, evaluating local observables remains \postBQP-complete, while above a different constant nontrivial threshold there exists an efficient classical algorithm for the task, resolving an open question from (Anshu et al., STOC `24). We do this by proving that noisy postselected quantum computation can be made fault-tolerant.
Projected entangled pair states (PEPS) are a class of tensor networks that are believed to represent a wide variety of two-dimensional physical quantum states. However, unlike their well-known one-dimensional counterparts, the matrix product states (MPS), numerical simulations with PEPS suffer from instabilities that can be traced back to the lack of a canonical form. The authors describe how to convert a PEPS into a canonical form analogous to the one for an MPS. It is expected that this canonical form will make possible improved analytical and numerical approaches for PEPS.
Simulation of quantum systems is challenging due to the exponential size of the state space. Tensor networks provide a systematically improvable approximation for quantum states. 2D tensor networks such as Projected Entangled Pair States (PEPS) are well-suited for key classes of physical systems and quantum circuits. However, direct contraction of PEPS networks has exponential cost, while approximate algorithms require computations with large tensors. We propose new scalable algorithms and software abstractions for PEPS-based methods, accelerating the bottleneck operation of contraction and refactorization of a tensor subnetwork. We employ randomized SVD with an implicit matrix to reduce cost and memory footprint asymptotically. Further, we develop a distributed-memory PEPS library and study accuracy and efficiency of alternative algorithms for PEPS contraction and evolution on the Stampede2 supercomputer. We also simulate a popular near-term quantum algorithm, the Variational Quantum Eigensolver (VQE), and benchmark Imaginary Time Evolution (ITE), which compute ground states of Hamiltonians.
Belief propagation has recently emerged as a powerful framework for evaluating tensor networks in higher dimensions, combining computational efficiency with provable analytical guarantees. In this work, we develop the first end-to-end theory of tensor network belief propagation for a class of projected entangled pair states satisfying \emph{strong injectivity}. We show that when the injectivity parameter exceeds a constant threshold, BP fixed points can be found efficiently, and a cluster-corrected BP algorithm computes physical quantities to 1/poly(N)1/\mathrm{poly}(N)1/poly(N) error in poly(N)\mathrm{poly}(N)poly(N) time for an NNN qubit system. We further identify a striking phenomenon we term \emph{algorithmic locality}: local perturbations of the tensor network affect the BP fixed point with an influence decaying rapidly with distance. Moreover, through the cluster expansion, this locality extends to observables, implying that local expectation values can be approximated from local data with controlled accuracy. We exhibit three regimes admitting strong injectivity: random Gaussian PEPS with large physical dimension, high-temperature Gibbs states of commuting two-body Hamiltonians, and fixed-depth quantum circuits subject to sufficiently strong depolarizing noise. Our bounds are worst-case sufficient conditions and do not identify sharp algorithmic transitions.