Near-optimal incoherent tomography of low-rank quantum channels

Technical Summary: Near-optimal incoherent tomography of low-rank quantum channels

Problem Statement
This work addresses the query complexity of quantum channel tomography under the incoherent model. The objective is to reconstruct an unknown quantum channel $\mathcal{E}: \mathcal{L}(\mathbb{C}^{d_1}) \to \mathcal{L}(\mathbb{C}^{d_2})$ with Kraus rank at most $r$ to within a diamond-norm error $\epsilon$. The learning algorithm operates in the incoherent setting, meaning it possesses no quantum memory between channel queries; it must measure the output state after each use of the channel, though subsequent inputs and measurements may depend adaptively on the classical transcript of previous outcomes. The accuracy is measured in the diamond norm, which quantifies the worst-case distinguishability of channels.

The central question is determining the number of channel queries required to achieve this reconstruction. While coherent protocols (utilizing entangled inputs and joint measurements) are known to achieve query complexity $\Theta(d_1 d_2 r / \epsilon^2)$ in the "away-from-boundary" regime, the incoherent complexity for general low-rank channels ($1 < r < d_1 d_2$) was previously uncharacterized beyond the trivial cases of $r=1$ and full rank.

Methodology
The paper establishes both upper and lower bounds on the query complexity using distinct technical approaches for different regimes of the channel spectrum.

1. Upper Bounds (Gapped Case):
   For channels where the non-zero eigenvalues of the Choi operator are bounded below by $\Omega(d_1/r)$, the authors utilize a non-adaptive protocol based on the ancilla-assisted projected least squares estimator from [SSKKG22]. The protocol involves preparing a fixed maximally entangled input state, applying the channel, and measuring the output in Haar-random bases.

   • Key Technical Innovation: The authors develop a new analysis to bound the diamond-norm error. They decompose the estimation error $\Delta$ into blocks relative to the support of the Choi operator. A critical component is the parameter $\kappa(\mathcal{E}) = d_1 \| \text{tr}_B P_E \|_\infty$, where $P_E$ is the projection onto the Choi support. For gapped channels, $\kappa(\mathcal{E}) = O(r)$. The analysis leverages the invariance of the error distribution under unitary conjugation on the orthogonal complement of the support to "flatten" the input marginal, allowing for tight control of the diamond distance via scalar Bernstein inequalities and covering net arguments.

2. Upper Bounds (General Case):
   For arbitrary channels where the spectrum may not be gapped (i.e., $\kappa(\mathcal{E})$ can be large), the authors propose an adaptive algorithm.

   • Key Technical Innovation: The algorithm employs the Matrix Multiplicative Weight Update (Matrix Exponentiated Gradient) method to iteratively select input states. The core difficulty is that the quantity controlling the error, $\kappa(\sigma_{in})$, depends discontinuously on the input state. To overcome this, the authors introduce a regularization filter $f_s(X) = X(X+sI)^{-1}$ and a corresponding "regularized input-sensitivity operator" $H_s(\sigma_{in})$. They construct a two-batch estimator to obtain a multiplicative estimate of $H_s(\sigma_{in}) + rI$. The weight update rule increases the weight of input directions where $H_s$ is large, converging to an input state $\bar{\sigma}$ such that $\|H_s(\bar{\sigma})\|_\infty = O(r)$ within $O(\log d_1)$ iterations. This allows the algorithm to achieve near-optimal complexity with only a logarithmic overhead.

3. Lower Bounds:
   The lower bound is derived using a standard information-theoretic strategy involving the construction of a "hard family" of channels and applying Fano's inequality.

   • Key Technical Innovation: The authors construct a new family of hard channels by perturbing the Kraus operators of a base channel. This family is designed such that every non-zero Choi eigenvalue lies within a specific range $[d_1/(4r), 4d_1/r]$. The proof bounds the mutual information between the channel parameter and the algorithm's transcript. Crucially, they utilize the tester representation of single-query experiments to show that the trace of the one-query Fisher information matrix is uniformly bounded by $O(d_1 d_2 / r)$. By applying Gaussian log-Sobolev inequalities to the prior distribution over the channel parameters, they translate this Fisher information bound into a mutual information bound, establishing the necessity of $\Omega(d_1 d_2 r^2 / \epsilon^2)$ queries even for adaptive incoherent protocols.

Key Contributions and Results
The paper provides a near-complete characterization of the query complexity for incoherent low-rank quantum channel tomography:

• Gapped Channels: For channels with $\Omega(d_1/r)$-gapped Choi spectra, the authors prove an optimal query complexity of $\Theta(d_1 d_2 r^2 / \epsilon^2)$. This is achieved by a non-adaptive algorithm using a fixed maximally entangled input.
• General Channels: For arbitrary low-rank channels, the authors establish an upper bound of $O(d_1 d_2 r^2 \log(2d_1) / \epsilon^2)$ via an adaptive algorithm. This nearly matches the lower bound, differing only by a logarithmic factor in the input dimension.
• Lower Bound: The paper proves a universal lower bound of $\Omega(d_1 d_2 r^2 / \epsilon^2)$ for any adaptive incoherent protocol learning channels of Kraus rank $r$. This bound holds across the entire feasible parameter regime, including the boundary regime where the dilation rate $\tau = rd_2/d_1 = 1$.

Significance
The paper answers the open question regarding the query complexity of incoherent low-rank channel tomography. Its primary significance lies in quantifying the cost of lacking quantum memory:

• Compared to coherent protocols, which achieve $\Theta(d_1 d_2 r / \epsilon^2)$ in the away-from-boundary regime, the incoherent setting incurs a multiplicative overhead of roughly $O(r)$.
• Unlike the coherent setting, where the boundary regime ($\tau=1$) exhibits Heisenberg scaling of $\Theta(d_1 d_2 r / \epsilon)$, the incoherent lower bound maintains the $1/\epsilon^2$ scaling throughout the feasible parameter space.
• The results generalize previous findings for minimal rank ($r=1$) and full rank ($r=d_1 d_2$) to arbitrary intermediate ranks, unifying the understanding of incoherent tomography across the spectrum of channel ranks.

The authors note that their upper-bound algorithms are ancilla-assisted and rely on exact Haar-random bases, leaving open the question of whether ancilla-free algorithms or approximate unitary designs can achieve comparable complexities.