2022/01/05 by Mehdi Soleimanifar, John C. Wright, Soleimanifar, Mehdi +1 · 9 citations
Computer Science · Physics and Astronomy · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Quantum many-body systems
paper · pdf · doi:10.48550/arxiv.2201.01824
openalex publication_date 2022/01/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Devising schemes for testing the amount of entanglement in quantum systems has played a crucial role in quantum computing and information theory. Here, we study the problem of testing whether an unknown state |ψ⟩ is a matrix product state (MPS) in the property testing model. MPS are a class of physically-relevant quantum states which arise in the study of quantum many-body systems. A quantum state |ψ1,...,n⟩ 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. For larger values of r, this yields a more expressive class of quantum states, which are allowed to possess limited amounts of entanglement. In the property testing 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 (FOCS 2010), 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 of Harrow and Montanaro (FOCS 2010) and Montanaro and de Wolf (2016). For the case of r≥ 2, we give an efficient algorithm for testing whether |ψ⟩ is an MPS of bond dimension r using m = O(n r2) 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.