Matrix product states (MPS) are a class of physically-relevant quantum states which arise in the study of quantum many-body systems. A quantum state comprised of n qudits is said to be an MPS of bond dimension r if the reduced density matrix ψ1, …, k has rank r for each k ∊ {1, …, n}. When r = 1, this corresponds to the set of product states, i.e. states of the form |ψ1〉 ⊗ ⃛ ⊗ |ψn), which possess no entanglement. For larger values of r, this yields a more expressive class of quantum states, which are allowed to possess limited amounts of entanglement. Devising schemes for testing the amount of entanglement in quantum systems has played a crucial role in quantum computing and information theory. In this work, we study the problem of testing whether an unknown state |ψ〉 is an MPS in the property testing model. In this model, one is given m identical copies of |ψ〉, and the goal is to determine whether |ψ〉 is an MPS of bond dimension r or whether |ψ〉 is far from all such states. For the case of product states, we study the product test, a simple two-copy test previously analyzed by Harrow and Montanaro [17], and a key ingredient in their proof that QMA(2) = QMA(k) for k ≥ 2. We give a new and simpler analysis of the product test which achieves an optimal bound for a wide range of parameters, answering open problems in [17] and [23]. For the case of r ≥ 2, we give an efficient algorithm for testing whether |ψ〉 is an MPS of bond dimension r using m = O(nr2) copies, independent of the dimensions of the qudits, and we show that Ω(n1/2) copies are necessary for this task. This lower bound shows that a dependence on the number of qudits n is necessary, in sharp contrast to the case of product states where a constant number of copies suffices.
Matrix product states (MPS) are a class of physically-relevant quantum states which arise in the study of quantum many-body systems. A quantum state comprised of n qudits is said to be an MPS of bond dimension r if the reduced density matrix ψ1, …, k has rank r for each k ∊ {1, …, n}. When r = 1, this corresponds to the set of product states, i.e. states of the form |ψ1〉 ⊗ ⃛ ⊗ |ψn), which possess no entanglement. For larger values of r, this yields a more expressive class of quantum states, which are allowed to possess limited amounts of entanglement. Devising schemes for testing the amount of entanglement in quantum systems has played a crucial role in quantum computing and information theory. In this work, we study the problem of testing whether an unknown state |ψ〉 is an MPS in the property testing model. In this model, one is given m identical copies of |ψ〉, and the goal is to determine whether |ψ〉 is an MPS of bond dimension r or whether |ψ〉 is far from all such states. For the case of product states, we study the product test, a simple two-copy test previously analyzed by Harrow and Montanaro [17], and a key ingredient in their proof that QMA(2) = QMA(k) for k ≥ 2. We give a new and simpler analysis of the product test which achieves an optimal bound for a wide range of parameters, answering open problems in [17] and [23]. For the case of r ≥ 2, we give an efficient algorithm for testing whether |ψ〉 is an MPS of bond dimension r using m = O(nr2) copies, independent of the dimensions of the qudits, and we show that Ω(n1/2) copies are necessary for this task. This lower bound shows that a dependence on the number of qudits n is necessary, in sharp contrast to the case of product states where a constant number of copies suffices.
Product testing, i.e., deciding whether a pure multipartite quantum state is fully unentangled across a specified tensor decomposition, serves as a bridge between quantum property testing, unentangled quantum proof systems, and tensor optimization. Despite being a fundamental property testing task and having many applications, the product test's exact (worst-case) acceptance probability curve has yet to be fully determined. In this work, we determine this curve exactly. Let ω be the maximum squared overlap of the input with a product state, and let PTn(ω) be the largest possible acceptance probability of the product test over all n-partite pure states with product overlap ω, allowing arbitrary finite local dimensions. We prove that, for every $n\ge 2 $ and every $ω\in(0,1] $, PTn(ω)=21(1+mω2+(1−mω)2), where $m=\lfloor1/ω\rfloor $. The formula recovers the previously known tight section of the curve for $ω\ge 1/2 $, resolves all low-overlap regimes $ω<1/2 $, and implies $\mathrm{PT}_n(ω)\to 1/2 $ as ω→0 answering an open problem in [Soleimanifar and Wright, SODA 2022]. As a complexity-theoretic application, our results improve the one-shot soundness parameter in the Harrow-Montanaro reduction from QMA(k) to QMA(2). Our techniques, built upon those of Soleimanifar and Wright, allow us to resolve these open questions while remaining surprisingly elementary.
Tree tensor network states (TTNS) generalize the notion of having low Schmidt-rank to multipartite quantum states, through a parameter known as the bond dimension. This leads to succinct representations of quantum many-body systems with a tree-like entanglement structure. In this work, we study the task of testing whether an unknown pure state is a TTNS onnqudits with bond dimension at mostr, or is far in trace distance from any such state. We first establish that, independent of the dimension of the state,O(nr2) copies suffice to accomplish this task with onesided error. We then prove that Ω(nr2/ logn) copies are necessary for any test with one-sided error wheneverr≥ 2 + logn. In particular, this closes a roughly quadratic gap in the previous bounds for testing matrix product states in this setting. On the other hand, whenr= 2 we show that Θ(√n) copies are both necessary and sufficient for the related task of testing whether a state is a product ofnbipartite states having Schmidt-rank at mostr, for some choice of the qudit dimensions. We also study the performance of tests using measurements performed on a small number of copies at a time. Here, we obtain new bounds for testing rank, Schmidt-rank, and TTNS when the tester is restricted to making measurements onr+ 1 copies of the state.
We give a test that can distinguish efficiently between product states of n quantum systems and states that are far from product. If applied to a state | ψ 〉 whose maximum overlap with a product state is 1 − ε , the test passes with probability 1 − Θ ( ε ), regardless of n or the local dimensions of the individual systems. The test uses two copies of | ψ 〉. We prove correctness of this test as a special case of a more general result regarding stability of maximum output purity of the depolarizing channel. A key application of the test is to quantum Merlin-Arthur games with multiple Merlins, where we obtain several structural results that had been previously conjectured, including the fact that efficient soundness amplification is possible and that two Merlins can simulate many Merlins: QMA( k ) = QMA(2) for k ≥ 2. Building on a previous result of Aaronson et al., this implies that there is an efficient quantum algorithm to verify 3-SAT with constant soundness, given two unentangled proofs of Õ (√ n ) qubits. We also show how QMA(2) with log-sized proofs is equivalent to a large number of problems, some related to quantum information (such as testing separability of mixed states) as well as problems without any apparent connection to quantum mechanics (such as computing injective tensor norms of 3-index tensors). As a consequence, we obtain many hardness-of-approximation results, as well as potential algorithmic applications of methods for approximating QMA(2) acceptance probabilities. Finally, our test can also be used to construct an efficient test for determining whether a unitary operator is a tensor product, which is a generalization of classical linearity testing.
We present a new wavefunction ansatz that combines the technique of spin projection with the language of matrix product states (MPS) and matrix product operators (MPO) as used in the density matrix renormalization group (DMRG). Specifically, spin-projected matrix product states (SP-MPS) are constructed as |Ψ^(N,S,M)_SP−MPS⟩=P_S|Ψ(N,M)_MPS⟩, where P_S is the spin projector for total spin S and |Ψ(N,M)MPS⟩ is an MPS wavefunction with a given particle number N and spin projection M. This new ansatz possesses several attractive features: (1) It provides a much simpler route to achieve spin-adaptation (i.e. to create eigenfunctions of Ŝ^2) compared to explicitly incorporating the non-Abelian SU(2) symmetry into the MPS. In particular, since the underlying state |Ψ(N,M)MPS⟩ in the SP-MPS uses only Abelian symmetries, one does not need the singlet embedding scheme for non-singlet states, as normally employed in spin-adapted DMRG, to achieve a single consistent variationally optimized state. (2) SP-MPS are closely connected to broken symmetry mean-field states. This allows to straightforwardly generate the large number of broken symmetry guesses needed to explore complex electronic landscapes in magnetic systems. Further, this connection can be exploited in the future development of quantum embedding theories for open-shell systems. (3) The sum of MPOs representation for the Hamiltonian and spin projector P_S naturally leads to an embarrassingly parallel algorithm for computing expectation values and optimizing SP-MPS. (4) Optimizing SP-MPS belongs to the variation-after-projection (VAP) class of spin projected theories. Unlike usual spin projected theories based on determinants, the SP-MPS ansatz can be made essentially exact simply by increasing the bond dimensions in |Ψ(N,M)MPS⟩. Computing excited states is also simple by imposing orthogonality constraints, which are simple to implement with MPS. To illustrate the versatility of SP-MPS, we formulate algorithms for the optimization of ground and excited states, develop perturbation theory based on SP-MPS, and describe how to evaluate spin-independent and spin-dependent properties such as the reduced density matrices. We demonstrate the numerical performance of SP-MPS with applications to several models typical of strong correlation, including the Hubbard model, and [2Fe-2S] and [4Fe-4S] model complexes.
Preparing matrix product states (MPS) on a quantum device is a key subroutine in many quantum algorithms. The most competitive methods, based on the renormalisation group, prepare translationally invariant MPS of size L and bond dimension χ, up to an error ε, in circuit depth O~(χ4log(L/ε)) or O~(χ6loglog(L/ε)). We improve multiple aspects of these methods. First, using block-encoded correction maps, whose post-selection succeeds with constant probability, we render the preparation exact without sacrificing the scaling in L. Second, through a generalisation of oblivious amplitude amplification to isometries, we reduce the bond-dimension dependence, improving the depth to O~(χ2logL+χ4) or O~(χ2loglogL+χ4), and even to O~(χ3logL) for incoherent preparations. Finally, we extend the framework to non-translationally invariant MPS and prove logarithmic-depth exact preparation for independent and identically distributed random tensor sequences. Confirmed by numerical studies, these results constitute, to the best of our knowledge, the most efficient exact MPS preparation protocols in the relevant parameter regimes.
The term Tensor Network States (TNS) refers to a number of families of states that represent different ansätze for the efficient description of the state of a quantum many-body system.Matrix Product States (MPS) are one particular case of TNS, and have become the most precise tool for the numerical study of one dimensional quantum many-body systems, as the basis of the Density Matrix Renormalization Group method.Lattice Gauge Theories (LGT), in their Hamiltonian version, offer a challenging scenario for these techniques.While the dimensions and sizes of the systems amenable to TNS studies are still far from those achievable by 4-dimensional LGT tools, Tensor Networks can be readily used for problems which more standard techniques, such as Markov chain Monte Carlo simulations, cannot easily tackle.Examples of such problems are the presence of a chemical potential or out-of-equilibrium dynamics.We have explored the performance of Matrix Product States in the case of the Schwinger model, as a widely used testbench for lattice techniques.Using finite-size, open boundary MPS, we are able to determine the low energy states of the model in a fully non-perturbative manner.The precision achieved by the method allows for accurate finite size and continuum limit extrapolations of the ground state energy, but also of the chiral condensate and the mass gaps, thus showing the feasibility of these techniques for gauge theory problems.