We consider the problem of quantum state certification, where we are given
the description of a mixed state $\sigma \in \mathbb{C}^{d \times d}$, $n$
copies of a mixed state $\rho \in \mathbb{C}^{d \times d}$, and $\varepsilon >
0$, and we are asked to determine whether $\rho = \sigma$ or whether $\| \rho -
\sigma \|_1 > \varepsilon$. When $\sigma$ 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 $\rho$
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
$\Omega (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 $\Omega (d^{3/2} / \varepsilon^2)$ copies are necessary, and 2)
we show the instance-optimal bounds for state certification to general $\sigma$
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.

通过研究矩阵鞅的性质，确定了使用不相干测量的混杂性测量和状态认证的副本复杂度，并表明自适应性对这些问题没有帮助。

关于在非相干测量下进行量子状态认证的严格界限

Tight Bounds for Quantum State Certification with Incoherent  Measurements

We show how to perform sparse approximate Gaussian elimination for Laplacian
matrices. We present a simple, nearly linear time algorithm that approximates a
Laplacian by a matrix with a sparse Cholesky factorization, the version of
Gaussian elimination for symmetric matrices. This is the first nearly linear
time solver for Laplacian systems that is based purely on random sampling, and
does not use any graph theoretic constructions such as low-stretch trees,
sparsifiers, or expanders. The crux of our analysis is a novel concentration
bound for matrix martingales where the differences are sums of conditionally
independent variables.

该研究提出了一种新的算法，使用随机采样实现了基于 Cholesky 分解的稀疏高斯消元，并且是第一个基于纯粹的随机采样、不使用任何图论构造（如低伸张树、稀疏器或扩展器）的 Laplacian 系统近线性时间求解器。