论文标题
测试矩阵产品状态
Testing matrix product states
论文作者
论文摘要
设计用于测试量子系统纠缠量的方案在量子计算和信息理论中起着至关重要的作用。在这里，我们研究了测试未知状态$ |ψ\ rangle $是否是属性测试模型中的矩阵乘积状态（MPS）的问题。 MPS是一类与物理相关的量子状态，在量子多体系统的研究中出现。一个量子状态$ |ψ_{1，...，n} \ rangle $由$ n $ qudits组成，据说是债券尺寸$ r $的MPS，如果降低的密度矩阵$ψ_{1，...，k} $的每个$ r $的每个$ r $ in \ in \ in \ in \ in \ {1，...，...，...当$ r = 1 $时，这对应于一组产品状态。对于$ r $的较大值，这会产生更具表现力的量子状态，这些状态被允许拥有有限的纠缠。在属性测试模型中，给出了$ |ψ\ rangle $的$ m $相同副本，目标是确定$ |ψ\ rangle $是债券尺寸$ r $还是$ |ψ\ rangle $是否远离所有此类州。对于产品状态，我们研究了产品测试，这是一项先前由Harrow和Montanaro分析的简单两拷贝测试（FOCS 2010），以及一种关键成分，证明了$ k \ geq 2 $的$ \ Mathsf {QMASF {qMA（2）} = \ Mathsf {qmA}（QMA}（QMA}（QMA）$。我们对产品测试进行了新的更简单的分析，该测试实现了广泛参数的最佳结合，回答了Harrow和Montanaro的开放问题（FOCS 2010）以及Montanaro和De Wolf（2016）。对于$ r \ geq 2 $，我们提供了一种有效的算法来测试$ |ψ\ rangle $是使用$ m = o（n r^2）$ copies $ r $的债券尺寸$（n r^2）$ copies copies copies of qudits的尺寸，而我们表明的$ω（n^{1/2}）$ COPIES是必需的。该下限表明，对Qudits $ n $的数量的依赖性与持续数量副本足够的产品状态形成鲜明对比。
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 $|ψ\rangle$ 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}\rangle$ 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 \in \{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 $|ψ\rangle$, and the goal is to determine whether $|ψ\rangle$ is an MPS of bond dimension $r$ or whether $|ψ\rangle$ 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 $\mathsf{QMA(2)}=\mathsf{QMA}(k)$ for $k \geq 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\geq 2$, we give an efficient algorithm for testing whether $|ψ\rangle$ is an MPS of bond dimension $r$ using $m = O(n r^2)$ copies, independent of the dimensions of the qudits, and we show that $Ω(n^{1/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.
