Studying quantum many body systems involves predicting the properties of systems containing several quantum particles, based on the principles of quantum mechanics. In general, the many-body problem describes a large category of physical problems, with fundamental problems described as many-body systems found in quantum chemistry, condensed matter physics, and materials science. In order to simulate many-body systems, one needs to be able to efficiently prepare and evolve certain entangled multipartite states.

One of the most appealing families of multipartite states are Tensor Network States (TNS), a class of variational wave functions, in which the wave function is encoded as a tensor contraction of a network of individual tensors. They are typically used in efficient approximation of the ground states of local Hamiltonians. The best-known class of TNS is that of Matrix Product States (MPS), which corresponds to a one-dimensional geometry of TNS. Higher-dimensional generalizations of these states are known as Projected Entangled Pair States (PEPS). All of these states are characterized by the bond dimension and are the ground state of a local, frustration-free Hamiltonian. This implies that, in case of no degeneracy, one can easily check the successful preparation of the state by merely measuring a set of local observables.

There exist several natural connections between Tensor Network States and quantum computational techniques. In a recent work, related to the paper we treat today, quantum algorithms to generate a wide range of PEPS have already been introduced. However, those algorithms are based on the adiabatic method, which requires a slow adiabatic transition (limited by the size of the minimal spectral gap of the target Hamiltonian) with a computational time scaling exponentially with the number of qubits.

In this work, the authors consider a family of states on arbitrary lattices in order to generate a wide range of PEPS. The objective is to express the computation of the gap as a semidefinite programming problem and to efficiently compute lower bounds on the gap.

The authors present a class of states and their corresponding parent Hamiltonian. These states depend on two positive parameters and by construction, they can be efficiently connected to a product state as shown in this work. Also, a particular adiabatic quantum algorithm (previously proposed by the same group at the Max-Planck-Institute of Quantum Optics) is extended further to continuous time in order to increase the compatibility with analog quantum computers. This generalization ensures that states with positive lower bound values can be prepared in logarithmic time scaling as compared to existing methods, which scale polynomially. For such families of states, it is possible to predict the expectation values of many different observables, beyond those appearing as terms of the parent Hamiltonian. The lower bounds on the gap of the parent Hamiltonian can be found by utilizing a semidefinite program.

Furthermore, the authors propose verification protocols including possible complexity factors. The 3 step verification protocol starts with the verifier sending the prover instructions for preparing the state. This step consists of R rounds where in each round, the verifier sends the prover a set of observables, in return the prover prepares the state, measures the observables, and finally reports the outcome. Lastly, the verifier verifies the preparation of the state by performing certain checks on the accumulated measurement outcomes.

However, there exist certain conditions which limit the protocol from achieving a successful verification process. One possible classical ‘cheating’ strategy would be finding a way to classically sample from the correct distribution, although it is theoretically impossible for the prover to classically sample from the quantum distribution. Also, one cannot find a distribution which yields the correct values for all the expectation values, which makes reproducing impossible. These considerations imply that the proposed protocol can be used for verification in case both prover and verifier have bounded (polynomial) storage space. Moreover, the verifier uses exponential time and the verification procedure can take an exponential number of rounds. Lastly, exponential resources are needed to reproduce expectation values along with maintaining exponential accuracy. All of these limitations suggest that there does not exist a viable cheating strategy that can affect the verification implemented by the proposed protocol.

Regardless of these limitations, the suggested protocol provides great insights to explore the compatibility with analog quantum computation, which is a step beyond prior works. Furthermore, the authors are able to efficiently compute lower bounds on the adiabatic gap by translating it into a semidefinite program, which is a novel perspective. Finally, they prove that states with positive lower bound values can be prepared in logarithmic time scaling in contrast to existing methods that scale polynomially, which is important for future experimentation.