论文标题
纠缠对于最佳量子属性测试是必需的
Entanglement is Necessary for Optimal Quantum Property Testing
论文作者
论文摘要
近年来，在开发用于实现最佳副本复杂性的量子状态的算法方面，进步趋势激增。不幸的是，它们需要在许多基本状态的许多副本中使用纠缠的测量，因此仍然超出了当前实验可行的范围。一个自然的问题是，是否只能使用独立的 - - 但可能会适应性地选择了这些算法的副本复杂性 - 对单个副本进行了测量。 我们以否定的方式回答了这一点，可以说是最基本的量子测试问题：确定给定的$ d $二维量子状态是否等于或$ε$ -FAR距最大混合状态的微量距离。虽然知道如何使用纠缠测量值实现最佳$ o（d/ε^2）$复制复杂性，但我们表明，即使测量值适应性地选择了测量值，也需要$ω（d^{4/3}/ε^2）$。这解决了赖特的问题。为了获得这种下限，我们开发了几种新技术，包括Paninski的链条样式证明，用于经典统一性测试，这可能具有独立的兴趣。
There has been a surge of progress in recent years in developing algorithms for testing and learning quantum states that achieve optimal copy complexity. Unfortunately, they require the use of entangled measurements across many copies of the underlying state and thus remain outside the realm of what is currently experimentally feasible. A natural question is whether one can match the copy complexity of such algorithms using only independent---but possibly adaptively chosen---measurements on individual copies. We answer this in the negative for arguably the most basic quantum testing problem: deciding whether a given $d$-dimensional quantum state is equal to or $ε$-far in trace distance from the maximally mixed state. While it is known how to achieve optimal $O(d/ε^2)$ copy complexity using entangled measurements, we show that with independent measurements, $Ω(d^{4/3}/ε^2)$ is necessary, even if the measurements are chosen adaptively. This resolves a question of Wright. To obtain this lower bound, we develop several new techniques, including a chain-rule style proof of Paninski's lower bound for classical uniformity testing, which may be of independent interest.
