There has been significant interest in understanding how practical
constraints on contemporary quantum devices impact the complexity of quantum
learning. For the classic question of tomography, recent work tightly
characterized the copy complexity for any protocol that can only measure one
copy of the unknown state at a time, showing it is polynomially worse than if
one can make fully-entangled measurements. While we now have a fairly complete
picture of the rates for such tasks in the near-term and fault-tolerant
regimes, it remains poorly understood what the landscape in between looks like.
In this work, we study tomography in the natural setting where one can make
measurements of $t$ copies at a time. For sufficiently small $\epsilon$, we
show that for any $t \le d^2$,
$\widetilde{\Theta}(\frac{d^3}{\sqrt{t}\epsilon^2})$ copies are necessary and
sufficient to learn an unknown $d$-dimensional state $\rho$ to trace distance
$\epsilon$. This gives a smooth and optimal interpolation between the known
rates for single-copy and fully-entangled measurements.
To our knowledge, this is the first smooth entanglement-copy tradeoff known
for any quantum learning task, and for tomography, no intermediate point on
this curve was known, even at $t = 2$. An important obstacle is that unlike the
optimal single-copy protocol, the optimal fully-entangled protocol is
inherently biased and thus precludes naive batching approaches. Instead, we
devise a novel two-stage procedure that uses Keyl's algorithm to refine a crude
estimate for $\rho$ based on single-copy measurements. A key insight is to use
Schur-Weyl sampling not to estimate the spectrum of $\rho$, but to estimate the
deviation of $\rho$ from the maximally mixed state. When $\rho$ is far from the
maximally mixed state, we devise a novel quantum splitting procedure that
reduces to the case where $\rho$ is close to maximally mixed.

基于研究对现代量子设备的实际限制如何影响量子学习的复杂性，通过自然环境中对多个副本进行测量和采用 Schur-Weyl 采样的方式，揭示了量子学习中量子复制与纠缠之间的平滑交换，特别是在拓扑近似条件下的观测联通性以及从最大混合态偏离程度的估计。

关于态重构的量子纠缠性与复制复杂度之间的最佳权衡

An optimal tradeoff between entanglement and copy complexity for state  tomography

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 revisit the basic problem of quantum state certification: given copies of
unknown mixed state $\rho\in\mathbb{C}^{d\times d}$ and the description of a
mixed state $\sigma$, decide whether $\sigma = \rho$ or $\|\sigma -
\rho\|_{\mathsf{tr}} \ge \epsilon$. When $\sigma$ is maximally mixed, this is
mixedness testing, and it is known that $\Omega(d^{\Theta(1)}/\epsilon^2)$
copies are necessary, where the exact exponent depends on the type of
measurements the learner can make [OW15, BCL20], and in many of these settings
there is a matching upper bound [OW15, BOW19, BCL20].
Can one avoid this $d^{\Theta(1)}$ dependence for certain kinds of mixed
states $\sigma$, e.g. ones which are approximately low rank? More ambitiously,
does there exist a simple functional $f:\mathbb{C}^{d\times
d}\to\mathbb{R}_{\ge 0}$ for which one can show that
$\Theta(f(\sigma)/\epsilon^2)$ copies are necessary and sufficient for state
certification with respect to any $\sigma$? Such instance-optimal bounds are
known in the context of classical distribution testing, e.g. [VV17].
Here we give the first bounds of this nature for the quantum setting, showing
(up to log factors) that the copy complexity for state certification using
nonadaptive incoherent measurements is essentially given by the copy complexity
for mixedness testing times the fidelity between $\sigma$ and the maximally
mixed state. Surprisingly, our bound differs substantially from instance
optimal bounds for the classical problem, demonstrating a qualitative
difference between the two settings.

本文主要研究关于量子态证明的基础问题，展示了使用非自适应的非相干测量量子态证明所需的拷贝数目与混合度测量所需的拷贝数目之间存在关联，实现了一个实例优化的上限。

通过不连贯测量实现实例最优状态认证

Toward Instance-Optimal State Certification With Incoherent Measurements

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
$\epsilon$-far in trace distance from the maximally mixed state. While it is
known how to achieve optimal $O(d/\epsilon^2)$ copy complexity using entangled
measurements, we show that with independent measurements,
$\Omega(d^{4/3}/\epsilon^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.

使用自适应独立测量可以匹配使用纠缠测量的算法的复制复杂度，但对于判断量子状态在跟最大混合态之间的距离是否大于 ε 这一基本问题，则在自适应独立测量的情况下，必须达到 Omega (d^(4/3)/ ε^2) 的下限。