Optimal precision dependence of diamond-norm channel tomography
- Field
- Topics
Problem
Does tomography of an arbitrary \(d\)-dimensional quantum channel in diamond norm require and suffice with \(\Theta(d^4/\varepsilon^2)\) channel uses?
Let \(\Lambda:\mathcal L(\mathbb C^d)\to\mathcal L(\mathbb C^d)\) be an unknown completely positive, trace-preserving channel with no Kraus-rank promise. Let \(Q_\diamond(d,\varepsilon)\) be the minimum worst-case number of ordinary channel uses needed to output \(\widehat\Lambda\) such that
The supremum in Eq. (1) is over states on \(\mathbb C^d\otimes\mathbb C^d\). Adaptive inputs, ancillas, quantum memory, and collective measurements are allowed, but no purification of the channel environment is supplied. Is \(Q_\diamond(d,\varepsilon)=\Theta(d^4/\varepsilon^2)\) uniformly in \(d\) and sufficiently small \(\varepsilon\)?
Source
This precise formulation is editor wording based on the unresolved direction and limitations documented in the cited primary literature [Mele25][Chen25]; it is not presented as a verbatim conjecture of those authors.
Progress
Reports do not certify correctness or automatically change the problem's status. Progress policy.
General channels with input dimension \(d_{\mathrm{in}}\), output dimension \(d_{\mathrm{out}}\), and Kraus rank at most \(r\) admit tomography using
\begin{equation} O(d_{\mathrm{in}}d_{\mathrm{out}}r/\varepsilon^2) \tag{2} \end{equation}queries. Substituting \(d_{\mathrm{in}}=d_{\mathrm{out}}=d\) and \(r=d^2\) proves \(Q_\diamond(d,\varepsilon)=O(d^4/\varepsilon^2)\). Mele and Bittel and, independently, Chen, Yu, and Zhang obtain this upper bound. [Mele25][Chen25]
The displayed definitions, constraints, and target bounds are recorded in Eqs. (2).
The dimension dependence at fixed accuracy is settled:
\begin{equation} Q_\diamond(d,\varepsilon)=\Theta(d^4) \qquad\text{for fixed sufficiently small }\varepsilon>0. \tag{3} \end{equation}Theorem IV.25 uses the convention \(\tfrac12\|\widehat\Lambda-\Lambda\|_\diamond\leq\varepsilon\); substituting source accuracy \(\varepsilon/2\) to match the full-norm convention above changes only constants. More quantitatively, specializing Theorem IV.25 of Mele and Bittel’s third version gives
\begin{equation} Q_\diamond(d,\varepsilon) =\Omega\!\left( \frac{d^4}{\varepsilon^{b_d}} +\frac{d\log d}{\varepsilon^2} \right), \qquad b_d:=\frac{d^2}{2(d^2+1)}. \tag{4} \end{equation}Constant-confidence amplification transfers their sufficiently-small-failure-probability statement to the success convention used here. This does not establish the product \(d^4/\varepsilon^2\). [Mele25]
The displayed definitions, constraints, and target bounds are recorded in Eqs. (3), (4).
A separate immediate reduction strengthens the accuracy-dependent obstruction. The preparation channels \(\Lambda_\sigma(X):=\operatorname{Tr}(X)\sigma\), with arbitrary \(d\)-dimensional states \(\sigma\), are a subfamily. Their diamond distance is \(\|\sigma-\tau\|_1\), so the optimal mixed-state tomography lower bound implies
\begin{equation} Q_\diamond(d,\varepsilon)=\Omega(d^2/\varepsilon^2). \tag{5} \end{equation}This is a reduction from the state-tomography bound reviewed in Section I.1, not a claim that the paper states this as its strongest general-channel theorem. [Mele25]
The displayed definitions, constraints, and target bounds are recorded in Eqs. (5).
Section I.5 of Mele and Bittel explicitly leaves the optimal joint dimension–accuracy dependence open; the known lower bounds do not match the general \(O(d^4/\varepsilon^2)\) upper bound. [Mele25][Chen25]
- Reported progress: PR #80.
Comment
The proposed equality is a concrete unrestricted-rank specialization of the published joint-scaling open problem, not a theorem asserted by the papers’ titles. Optimal scaling separately in dimension at constant accuracy and in accuracy at fixed dimension does not prove their multiplicative combination. That uniform two-parameter question remains unresolved.