论文标题
与不连贯测量的量子状态认证的紧密界限
Tight Bounds for Quantum State Certification with Incoherent Measurements
论文作者
论文摘要
我们考虑量子状态认证的问题，在其中给予了混合状态$σ\的描述。 $ \ | ρ-σ\ | _1> \ varepsilon $。当$σ$是最大混合状态$ \ frac {1} {d} i_d $时，这被称为混合度测试。我们专注于使用不连贯测量的算法，即一次仅测量一个$ρ$的副本。与使用纠缠的多复制测量值的人不同，可以在没有持续的量子内存的情况下实现这些测量，因此代表了可以在当前或近期设备上运行的大量协议。 对于混合度测试，有一种民间文学算法，它使用不连贯的测量值，并且只需要$ o（d^{3/2} / \ varepsilon^2）$ copies。该算法是非自适应的，即其测量值提前固定，并且已知对于非自适应算法是最佳的。但是，当该算法可以进行任意不相干的测量值时，最著名的下限仅为$ω（d^{4/3} / \ varepsilon^2）$ [bubeck-chen-li '20]，这是一个出色的开放问题，可以缩小这一多元性差距。在这项工作中，1）我们确定了混合性测试的复制复杂性，并表明$ω（d^{3/2} / \ varepsilon^2）$ copies是必要的，2）我们显示了实例 - 最佳限制的状态认证，用于一般$σ$ in [chen-li-o'd od''''''''''''''''21]不一致的测量。 从定性上讲，我们的结果表明，适应性对这些问题根本无济于事。我们的结果基于新技术，使我们能够减少问题来理解某些矩阵martingales，我们认为这可能具有独立的兴趣。
We consider the problem of quantum state certification, where we are given the description of a mixed state $σ\in \mathbb{C}^{d \times d}$, $n$ copies of a mixed state $ρ\in \mathbb{C}^{d \times d}$, and $\varepsilon > 0$, and we are asked to determine whether $ρ= σ$ or whether $\| ρ- σ\|_1 > \varepsilon$. When $σ$ is the maximally mixed state $\frac{1}{d} I_d$, this is known as mixedness testing. We focus on algorithms which use incoherent measurements, i.e. which only measure one copy of $ρ$ at a time. Unlike those that use entangled, multi-copy measurements, these can be implemented without persistent quantum memory and thus represent a large class of protocols that can be run on current or near-term devices. For mixedness testing, there is a folklore algorithm which uses incoherent measurements and only needs $O(d^{3/2} / \varepsilon^2)$ copies. The algorithm is non-adaptive, that is, its measurements are fixed ahead of time, and is known to be optimal for non-adaptive algorithms. However, when the algorithm can make arbitrary incoherent measurements, the best known lower bound is only $Ω(d^{4/3} / \varepsilon^2)$ [Bubeck-Chen-Li '20], and it has been an outstanding open problem to close this polynomial gap. In this work, 1) we settle the copy complexity of mixedness testing with incoherent measurements and show that $Ω(d^{3/2} / \varepsilon^2)$ copies are necessary, and 2) we show the instance-optimal bounds for state certification to general $σ$ first derived by [Chen-Li-O'Donnell '21] for non-adaptive measurements also hold for arbitrary incoherent measurements. Qualitatively, our results say that adaptivity does not help at all for these problems. Our results are based on new techniques that allow us to reduce the problem to understanding certain matrix martingales, which we believe may be of independent interest.
