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.
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.
For the past twenty years, Matrix Product States (MPS) have been widely used in solid state physics to approximate the ground state of one-dimensional spin chains. In this paper, we study homogeneous MPS (hMPS), or MPS constructed via site-independent tensors and a boundary condition. Exploiting a connection with the theory of matrix algebras, we derive two structural properties shared by all hMPS, namely: a) there exist local operators which annihilate all hMPS of a given bond dimension; and b) there exist local operators which, when applied over any hMPS of a given bond dimension, decouple (cut) the particles where they act from the spin chain while at the same time join (glue) the two loose ends back again into a hMPS. Armed with these tools, we show how to systematically derive `bond dimension witnesses', or 2-local operators whose expectation value allows us to lower bound the bond dimension of the underlying hMPS. We extend some of these results to the ansatz of Projected Entangled Pairs States (PEPS). As a bonus, we use our insight on the structure of hMPS to: a) derive some theoretical limitations on the use of hMPS and hPEPS for ground state energy computations; b) show how to decrease the complexity and boost the speed of convergence of the semidefinite programming hierarchies described in [Phys. Rev. Lett. 115, 020501 (2015)] for the characterization of finite-dimensional quantum correlations.
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.
Learning the closest matrix product state (MPS) representation of a quantum state enables useful tools for quantum machine learning and analysis of complex quantum systems. In this work, we study the problem of learning MPS in the following setting: given many copies of an input MPS, the task is to recover a classical description of the state. The best known polynomial-time algorithm, introduced by [LCLP10, CPF+10], requires linear circuit depth and O(n5) samples, and has seen no improvement in over a decade. These costs, neither known to be optimal, renders existing algorithms impractical for near-term quantum devices with limited resources. We introduce parallel disentangling algorithms for MPS learning. For exact MPS learning, our algorithm runs in polynomial time and uses circuit depth O(logn) and sample complexity O(n3), improving both the depth and the dependence on the system size n. The key idea is to exploit the bounded-rank structure of reduced states on middle blocks of an MPS and organize the disentangling operations in a tree structure. We further extend the algorithm to closest MPS learning, improving the sample complexity dependence on n from n9 to n7 and complement the algorithms with an Ω(n) product-state lower bound. We also investigate MPS learning under hardware constraints, including restricted measurements and geometric connectivity. Under the Learning Parity with Noise (LPN) assumption, we show computational hardness for learning an MPS(2) family with non-adaptive single-qubit measurements. Finally, we show that our algorithm can be implemented with depth O(qn1/q) on a q-dimensional hypercubic lattice, giving an asymptotic reduction in depth. Together, our work provides a complete characterization of the quantum resources needed for efficient MPS learning.
Quantum state tomography (QST) remains the gold standard for benchmarking and verification of near-term quantum devices. While QST for a generic quantum many-body state requires an exponentially large amount of resources, most physical quantum states are structured and can often be represented by a much smaller number of parameters, making efficient QST potentially possible. A prominent example is a matrix product state (MPS) or a matrix product density operator (MPDO), which is believed to represent most physical states generated by one-dimensional (1D) quantum devices. We study whether a general MPS/MPDO state can be recovered with bounded errors using only a number of state copies polynomial in the number of qubits, which is necessary for efficient QST. To make this question practically interesting, we assume only local measurements of qubits directly on the target state. By using a local symmetric informationally complete positive operator-valued measurement (SIC-POVM), we provide a positive answer to the above question for a variety of common many-body quantum states, including typical short-range entangled states, random MPS/MPDO states, and thermal states of one-dimensional Hamiltonians. In addition, we also provide an affirmative no answer for certain long-range entangled states such as a family of generalized GHZ states, but with the exception of target states that are known to have real-valued wavefunctions. Our answers are supported by a near-perfect agreement between an efficient calculation of the Cramer-Rao bound that rigorously bounds the sample complexity and numerical optimization results using a machine learning assisted maximal likelihood estimation (MLE) algorithm. This agreement also leads to an optimal QST protocol using local SIC-POVM that can be practically implemented on current quantum hardware and is highly efficient for most 1D physical states.