Recent work has shown that $n$-qubit quantum states output by circuits with
at most $t$ single-qubit non-Clifford gates can be learned to trace distance
$\epsilon$ using $\mathsf{poly}(n,2^t,1/\epsilon)$ time and samples. All prior
algorithms achieving this runtime use entangled measurements across two copies
of the input state. In this work, we give a similarly efficient algorithm that
learns the same class of states using only single-copy measurements.

使用单次测量，以多项式时间和样本量来学习由具有最多 t 个单量子比特非克利福德门的电路输出的 n 量子比特态的得到的跟踪距离为 ε 的最新算法。

少非克利福门单比特态高效学习二：单次测量

Efficient Learning of Quantum States Prepared With Few Non-Clifford  Gates II: Single-Copy Measurements

In this work we make progress in understanding the relationship between
learning models with access to entangled, separable and statistical
measurements in the quantum statistical query (QSQ) model. To this end, we show
the following results.
$\textbf{Entangled versus separable measurements.}$ The goal here is to learn
an unknown $f$ from the concept class $C\subseteq \{f:\{0,1\}^n\rightarrow
[k]\}$ given copies of $\frac{1}{\sqrt{2^n}}\sum_x \vert x,f(x)\rangle$. We
show that, if $T$ copies suffice to learn $f$ using entangled measurements,
then $O(nT^2)$ copies suffice to learn $f$ using just separable measurements.
$\textbf{Entangled versus statistical measurements}$ The goal here is to
learn a function $f \in C$ given access to separable measurements and
statistical measurements. We exhibit a class $C$ that gives an exponential
separation between QSQ learning and quantum learning with entangled
measurements (even in the presence of noise). This proves the "quantum
analogue" of the seminal result of Blum et al. [BKW'03]. that separates
classical SQ and PAC learning with classification noise.
$\textbf{QSQ lower bounds for learning states.}$ We introduce a quantum
statistical query dimension (QSD), which we use to give lower bounds on the QSQ
learning. With this we prove superpolynomial QSQ lower bounds for testing
purity, shadow tomography, Abelian hidden subgroup problem, degree-$2$
functions, planted bi-clique states and output states of Clifford circuits of
depth $\textsf{polylog}(n)$.
$\textbf{Further applications.}$ We give and $\textit{unconditional}$
separation between weak and strong error mitigation and prove lower bounds for
learning distributions in the QSQ model. Prior works by Quek et al. [QFK+'22],
Hinsche et al. [HIN+'22], and Nietner et al. [NIS+'23] proved the analogous
results $\textit{assuming}$ diagonal measurements and our work removes this
assumption.

通过研究量子统计查询（QSQ）模型中具有访问纠缠、可分和统计测量学习模型之间的关系，证明了对于许多问题，使用纠缠测量来确定量子态是不可避免的（即，不可能通过可分测量代替）。

关于纠缠和统计在学习中的作用

On the Role of Entanglement and Statistics in Learning

We show that entangled measurements provide an exponential advantage in
sample complexity for Pauli channel estimation, which is both a fundamental
problem and a practically important subroutine for benchmarking near-term
quantum devices. The specific task we consider is to simultaneously learn all
the eigenvalues of an $n$-qubit Pauli channel to $\pm\varepsilon$ precision. We
give an estimation protocol with an $n$-qubit ancilla that succeeds with high
probability using only $O(n/\varepsilon^{2})$ copies of the Pauli channel,
while prove that any ancilla-free protocol (possibly with adaptive control and
channel concatenation) would need at least $\Omega(2^{n/3})$ rounds of
measurement. We further study the advantages provided by a small number of
ancillas. For the case that a $k$-qubit ancilla ($k\le n$) is available, we
obtain a sample complexity lower bound of $\Omega(2^{(n-k)/3})$ for any
non-concatenating protocol, and a stronger lower bound of $\Omega(n2^{n-k})$
for any non-adaptive, non-concatenating protocol, which is shown to be tight.
We also show how to apply the ancilla-assisted estimation protocol to a
practical quantum benchmarking task in a noise-resilient and sample-efficient
manner, given reasonable noise assumptions. Our results provide a
practically-interesting example for quantum advantages in learning and also
bring new insight for quantum benchmarking.

利用纠缠测量可以在 Pauli 通道估计中提供指数优势，我们提出了一个带有 $n$- 量子比特辅助量子状态的估计协议，仅使用 $O (n/ε^{2})$ 个 Pauli 通道副本即可高概率成功，这为学习中的量子优势提供了实用的例子，也为量子基准测试带来了新的见解。

Pauli 通道估计的量子优势

Quantum advantages for Pauli channel estimation

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) 的下限。