In this paper we revisit one of the prototypical tasks for characterizing the
structure of noise in quantum devices, estimating the eigenvalues of an
$n$-qubit Pauli noise channel. Prior work (Chen et al., 2022) established
exponential lower bounds for this task for algorithms with limited quantum
memory. We first improve upon their lower bounds and show:
(1) Any algorithm without quantum memory must make $\Omega(2^n/\epsilon^2)$
measurements to estimate each eigenvalue within error $\epsilon$. This is tight
and implies the randomized benchmarking protocol is optimal, resolving an open
question of (Flammia and Wallman, 2020).
(2) Any algorithm with $\le k$ ancilla qubits of quantum memory must make
$\Omega(2^{(n-k)/3})$ queries to the unknown channel. Crucially, unlike in
(Chen et al., 2022), our bound holds even if arbitrary adaptive control and
channel concatenation are allowed.
In fact these lower bounds, like those of (Chen et al., 2022), hold even for
the easier hypothesis testing problem of determining whether the underlying
channel is completely depolarizing or has exactly one other nontrivial
eigenvalue. Surprisingly, we show that:
(3) With only $k=2$ ancilla qubits of quantum memory, there is an algorithm
that solves this hypothesis testing task with high probability using a single
measurement.
Note that (3) does not contradict (2) as the protocol concatenates
exponentially many queries to the channel before the measurement. This result
suggests a novel mechanism by which channel concatenation and $O(1)$ qubits of
quantum memory could work in tandem to yield striking speedups for quantum
process learning that are not possible for quantum state learning.

在本文中，我们重新思考了用于表征量子设备中噪声结构的典型任务之一，即估计 n 量子比特 Pauli 噪声通道的特征值。我们改进了之前的工作，给出了更好的下界，并且证明了具有限定量子内存的算法在估计每个特征值的误差为 ε 时必须进行 Ω(2^n/ε^2) 个测量。此外，我们还研究了具有 k 个量子内存的算法以及任意自适应控制和通道串联情况下的查询个数下界。此外，我们的下界适用于假设检验问题，并且展示了当只有 2 个辅助比特量子内存时，可以使用单个测量高概率解决这个假设检验任务。这个结果揭示了通道串联和 O (1) 量子内存如何结合以实现量子过程学习的显著加速的新机制。