Optimal learning of quantum channels in diamond distance

MainIn this work we study the task of learning an accurate classical description of an unknown quantum channel from black-box access, using as few channel invocations as possible. This is the problem of quantum process tomography1,2,3, also referred to as quantum channel tomography or learning. Process tomography is a central primitive for calibrating, validating and debugging noisy quantum devices, and has been implemented across a range of platforms, including trapped ions, superconducting qubits and photonic architectures4,5,6. In its most general form, a tomography protocol is given N uses of an unknown channel, may probe it with arbitrary input states, may interleave these uses with adaptive quantum operations and may finally perform a joint measurement on all output and auxiliary systems to produce a classical description of the channel. To make such learning guarantees precise, one must choose a metric for the space of quantum channels. Among the available choices, the diamond distance is widely regarded as the standard metric due to its operational meaning7,8,9,10,11: it captures the worst-case distinguishability between two quantum processes, optimized over arbitrary input states, auxiliary systems and measurements. Learning in this metric therefore asks for a classical surrogate of an unknown open-system dynamics that can replace the true process in any future experiment, up to a prescribed worst-case error. The central question is how many times the process must be used before such a surrogate can be guaranteed.For comparison, the analogous problem of quantum state tomography—learning an unknown state in trace distance, the standard operational metric for states—is now well understood12,13,14,15. In particular, the optimal dependence on dimension and accuracy for mixed-state tomography has been known for roughly a decade13,14 (with the full resolution in all relevant parameters, including fixed rank and failure probability, obtained only very recently15,16). By contrast, the corresponding question for general quantum channels has remained open beyond special cases, most notably unitary channels17.In particular, for states on the complex Hilbert space \({{\mathbb{C}}}^{d}\), where \({\mathbb{C}}\) denotes the complex numbers and d is the Hilbert-space dimension, the optimal number of copies required for tomography to fixed trace-distance accuracy scales with the number of degrees of freedom of the density matrix, namely Θ(d2) for full-rank states. By analogy, one might expect the number of channel uses required for quantum process tomography to scale with the number of parameters describing a general channel. However, once one insists on diamond-distance guarantees, the best previously known tomography schemes for arbitrary d-dimensional channels required \(\widetilde{O}({d}^{6})\) channel uses18,19,20, larger than the Θ(d4) number of independent parameters that are needed to describe a general channel. The gap between this and the best known information-theoretic lower bounds, which scale as \({\tilde{\varOmega}}({d}^{4})\) for constant accuracy21, is substantial (see Table 1). This raises a basic and conceptually clean question: How many uses of an unknown quantum channel are needed to learn it to constant accuracy in diamond distance? More specifically, is this number governed by the number of independent parameters needed to describe a general channel? Table 1 Query complexity for tomography of quantum states and quantum channels to accuracy ε in the corresponding operational metricFull size tableIn this work, we answer this question affirmatively. We show that a number of channel uses scaling with the degrees of freedom of the unknown channel is both sufficient and necessary to achieve any fixed constant diamond-distance accuracy. In particular, channels with input and output dimensions din and dout and Kraus rank of at most k admit a Θ(dindoutk)-parameter description, and we present a channel-tomography algorithm that achieves this query-complexity scaling and prove a matching lower bound, showing that process-tomography procedures cannot asymptotically improve on this parameter-count dependence. More generally, our main theorem can be stated as follows: Theorem 1 Let \(\varLambda :{\mathcal{L}}({{\mathbb{C}}}^{{d}_{{\rm{in}}}})\to {\mathcal{L}}({{\mathbb{C}}}^{{d}_{{\rm{out}}}})\) be an unknown quantum channel with Kraus rank of at most k. Then, for any ε ∈ (0, 1) and any desired constant success probability, there exists a quantum process-tomography algorithm that uses$$N=O\left(\dfrac{{d}_{{\rm{in}}}{d}_{{\rm{out}}}k}{{\varepsilon }^{2}}\right)$$ (1) invocations of Λ and outputs a classical description of a channel \({\hat{\varLambda}}\) satisfying \(\parallel {\hat{\varLambda}}-\varLambda {\parallel }_{\diamond}\le \varepsilon\), where ∥ ⋅ ∥⋄ denotes the diamond norm. Conversely, any process-tomography algorithm that achieves diamond-norm accuracy ε must use N = Ω(dindoutk) channel invocations. Moreover, if the allowed Kraus rank is non-minimal, namely if k > ⌈din/dout⌉, then any such algorithm must also incur an Ω(1/ε2) lower-bound contribution. Thus, Theorem 1 establishes that the query complexity of channel tomography at constant accuracy in diamond distance is Θ(dindoutk). It also records a separate accuracy-dependent lower bound: for channels with Kraus rank larger than the minimum allowed by the input and output dimensions, an Ω(ε−2) contribution to the query complexity is unavoidable. This contrasts with the minimal Kraus rank case, which includes unitary channels, for which Heisenberg scaling O(ε−1) is known to be achievable17. We point out that, for readability, Theorem 1 suppresses the explicit dependence on the failure probability in the upper bound and gives only the most relevant consequences of the lower-bound results proved later in the text.If no Kraus rank assumption is imposed, then one may take k = dindout, and the upper bound becomes \(O({d}_{{\rm{in}}}^{2}{d}_{{\rm{out}}}^{2}/{\varepsilon }^{2})\). For channels acting on \({{\mathbb{C}}}^{d}\) (that is, when din = dout = d), this gives O(d4/ε2).The algorithm that achieves this scaling is conceptually simple (Fig. 1). We first prepare many copies of the Choi state of the unknown channel in parallel. We then apply the recently introduced random purification channel22 to these Choi states, producing multiple copies of a purification15,22,23. Finally, we run a sample-optimal pure-state tomography procedure on the resulting purifications12,15,24, obtain an estimate of the purification and reconstruct from it an estimate of the unknown channel, regularizing the estimate by a semi-definite program (SDP) projection onto the set of completely positive and trace-preserving (CPTP) maps.Fig. 1: Protocol for learning quantum channels.Full size imageParallel invocations of the unknown channel Λ, applied to halves of maximally entangled states |Ω〉, prepare copies of its normalized Choi state Φc = J(Λ), where J denotes the map assigning a channel its normalized Choi state. The green boxes represent invocations of the unknown channel Λ. A purification channel then maps these Choi-state copies to copies of a random purification |Φc〉, which are learned using a sample-optimal pure-state tomography scheme. The notation |J(Λ)〉 used in the figure denotes the purification |Φc〉. Finally, a classical post-processing step, formulated as an SDP projecting onto the set of CPTP maps, returns a channel estimate \({\hat{\varLambda}}\) satisfying \(\parallel {\hat{\varLambda}}-\varLambda {\parallel }_{\diamond }\le \varepsilon\) with high probability.In this sense, the protocol can essentially be viewed as applying the sample-optimal mixed-state tomography strategy recently introduced in ref. 15 to the Choi state of the unknown channel. This is a conceptual strength of our result: we show that the most natural strategy, namely Choi-state tomography, in fact suffices for achieving such diamond-distance guarantees, even though it might a priori seem too crude. The apparent obstruction is that state tomography controls the Choi state in trace distance, whereas the operational metric for channels is the diamond distance, and a naive worst-case conversion from Choi-state trace distance to channel diamond distance incurs a dimension-dependent loss, which would destroy the desired scaling.One of our main technical contributions is an analysis showing that, for the estimator produced by the protocol, converting the purified Choi-state estimation error to diamond-distance error incurs only a constant factor, with no dimension-dependent overhead. A key feature of the analysis is that we evaluated the estimator directly in diamond distance, using a convenient SDP characterization10,25. A second key ingredient is that the residual state-estimation error after pure-state tomography can, without loss of generality, be modelled as Haar-random. This allows us to control the induced diamond-distance error of the reconstructed channel using concentration properties of random quantum states26. In particular, we prove that to guarantee a diamond-distance error of at most ε, it suffices to learn the purified Choi state, and hence the Choi state, to trace-distance accuracy O(ε), with essentially no additional dimension-dependent overhead.Thus, our analysis shows that learning a quantum process in diamond distance can be reduced, without losing the optimal scaling in dimension, to pure-state tomography. This generalizes the mixed-to-pure-state tomography reduction of ref. 15 from mixed states to quantum channels, a strict generalization as quantum states can be viewed as channels with one-dimensional input.Two structural features of our scheme are worth highlighting. First, the protocol is entirely non-adaptive at the level of channel uses: all invocations of the unknown channel occur in a single parallel block, and all subsequent operations act only on the resulting Choi-state copies. In particular, this also shows that adaptivity offers no asymptotic advantage for achieving the dimension-optimal scaling at fixed constant diamond-distance accuracy. Second, coherence across Choi-state copies remains provably useful in this non-adaptive setting. Indeed, ref. 19 showed that any non-adaptive scheme restricted to incoherent measurements on individual channel outputs requires asymptotically more channel invocations to reach a given diamond-distance accuracy. In our protocol, this coherence is confined to the purification stage. Once purifications of the Choi state are available, the remaining tomography step can be carried out using any sample-optimal pure-state tomography procedure, including single-copy schemes24.We next briefly explain the converse direction. The lower bounds stated in Theorem 1 are proved by two different reductions. The dimension-dependent lower bound Ω(dindoutk) follows from a packing argument: we construct many Kraus-rank-k channels separated in diamond distance and reduce tomography to identifying which channel was given, following ideas used previously for unitary channels17,27. The Ω(1/ε2) lower bound for channels with non-minimal Kraus rank follows from embedding the task of estimating the biases of multiple classical coins into channel tomography, so that the standard ε−2 lower bound for coin-bias estimation carries over.Beyond Theorem 1, our framework recovers and unifies several previously known query-optimal tomography results13,14,15,16,17, and yields additional guarantees for other basic tomography tasks in the strong metrics considered here28,29.On the ‘known results’ side, specializing to channels with din = 1 recovers the optimal Θ(kd/ε2) scaling for trace-distance tomography of rank-k states, matching the information-theoretic lower bounds16 and the upper bounds achieved by sample-optimal state tomography schemes13,14,15. For unitary channels, corresponding to din = dout = d and k = 1, our Choi-state-based protocol recovers the optimal Θ(d2) dimension dependence. Moreover, using our unitary-learning protocol as a black-box subroutine in the adaptive boosting scheme of ref. 17, one can upgrade the 1/ε2 dependence to Heisenberg scaling 1/ε, obtaining the optimal query complexity Θ(d2/ε). Thus, our method provides an alternative route to query-optimal unitary tomography based on the natural Choi-state tomography approach, complementary to ref. 17, which achieves the same optimal scaling through a protocol that is not based on Choi-state learning.On the ‘additional consequences’ side, for Kraus-rank-one channels our result gives an algorithm for learning arbitrary isometries in diamond distance with query complexity O(dindout/ε2). In sharp contrast with the unitary case, lower bounds rule out Heisenberg scaling 1/ε for general isometries29 and show that this scaling is optimal up to logarithmic factors. Finally, we show that binary positive operator-valued measures (POVMs) can be learned in operator norm with O(d2/ε2) uses of the unknown measurement device. We show that this scaling is optimal in the dimension at constant accuracy, and establish a separate Ω(1/ε2) lower bound.It is also important to clarify the practical scope of our result. The present result should primarily be seen as an information-theoretic achievability theorem, rather than as a practically scalable tomography protocol. Although the query complexity is dimension-optimal, the protocol requires a coherent purification step acting jointly across many Choi-state copies, which is demanding in realistic multi-qubit regimes. In addition, the final CPTP regularization is formulated as an SDP whose size is polynomial in the Hilbert-space dimension, and hence generally not scalable in the number of qubits. By contrast, the Kraus-rank-one case is substantially more feasible in practice. In this case the Choi state is already pure, so the purification step is unnecessary, and the task reduces directly to pure-state tomography on independent Choi-state copies24. This also has a practically appealing feature compared with earlier optimal unitary-learning schemes17: one repeatedly prepares and measures the same state, rather than cycling through many different input settings. In this sense, our protocol identifies the dimension-optimal query complexity of channel tomography in the strongest operational metric, whereas more practical incoherent schemes trade this query optimality for implementability19,20,28.ApplicationsQuantum channels provide a common framework that includes, as special cases, quantum states (via din = 1), isometries (via k = 1), in particular unitaries (via din = dout and k = 1), and POVMs (for instance, binary POVMs via dout = 2 and enforcing diagonal output states). Accordingly, Theorem 2 and its consequences simultaneously capture and extend several tomography results for these primitives. In this subsection we summarize the resulting guarantees (detailed formulations are provided in Supplementary Information). For any fixed constant success probability, specializing Theorem 2 to each of these settings implies the following. States. When din = 1, a channel is a state-preparation map and the diamond norm reduces to the trace distance. In this case we recover the optimal scaling N = Θ(dk/ε2) for trace-distance tomography of a rank-k state in dimension d. Isometries and unitaries. For Kraus-rank-one channels Λ(ρ) = VρV† with \(V:{{\mathbb{C}}}^{{d}_{{\rm{in}}}}\to {{\mathbb{C}}}^{{d}_{{\rm{out}}}}\) an isometry, we obtain an explicit tomography scheme with query-complexity guarantees N = O(dindout/ε2) for learning arbitrary isometries in diamond distance. Here ρ is the input density operator, and the superscript dagger denotes the Hermitian adjoint. A recent work29 proves a lower bound \({\tilde{\varOmega}}({d}_{{\rm{in}}}{d}_{{\rm{out}}}/{\varepsilon }^{2})\) for generic isometries, so our obtained scaling is tight up to logarithmic factors. For unitary channels (din = dout = d), combining our Choi-state-based learner with the boosting scheme of ref. 17 further yields N = Θ(d2/ε), achieving Heisenberg scaling in the accuracy parameter while preserving the optimal d2 dimensional dependence. We also remark that in the isometric/unitary case the Choi state is already pure, so the purification step in our general construction is not needed; one can instead apply directly a sample-optimal pure-state tomography algorithm such as the projected least-squares scheme of ref. 24, which uses only single-copy measurements. In particular, no coherent operations between Choi-state copies are required in this setting—the Choi states can be prepared and measured sequentially. Measurements. If we restrict attention to channels with dout = 2 whose outputs are classical (that is, diagonal in a fixed basis), we recover exactly the channels induced by binary POVMs: each such channel is determined by a single POVM element E via the map \(\rho \mapsto {\sum }_{b\in \{0,1\}}\,\text{tr}\,({M}_{b}\rho )\left\vert b\right\rangle \left\langle b\right\vert\), where b ∈ {0,1} labels the two measurement outcomes and Mb are the corresponding positive operator-valued measure elements, satisfying M0 = E and \({M}_{1}={\mathbb{I}}-E\), with \({\mathbb{I}}\) the identity operator. In this setting, the diamond distance between two such channels coincides (up to a factor of two) with the operator-norm distance between the corresponding POVM elements, so diamond-norm tomography of the channel is equivalent to operator-norm learning of the POVM elements. For binary POVMs on \({{\mathbb{C}}}^{d}\), we obtain N = O(d2/ε2) samples for ε-accurate operator-norm learning. Thus, our results place previously separate guarantees for states13,14,15, isometries29, unitaries17 and measurements20,28 within a single unified channel-based framework.Discussion and open problemsIn this work we studied a tomography scheme for learning unknown quantum channels with rigorous recovery guarantees in diamond distance. Our main result shows that any channel with input dimension din, output dimension dout and Kraus rank of at most k can be learned to diamond-distance accuracy ε using N = O(dindoutk/ε2) queries. We also prove two complementary lower bounds: a matching Ω(dindoutk) lower bound at constant accuracy and a separate Ω(1/ε2) lower-bound contribution for channels with non-minimal Kraus rank. Thus, as summarized in Table 1, our results close the dimensional query-complexity gap for quantum process tomography in diamond distance.Operationally, this identifies the experimental query cost of reconstructing open-system dynamics in the strongest sense: after N uses of the unknown process, the learner outputs a classical surrogate that can replace the true channel in any future experiment, up to error ε. Our query-complexity bound shows that, at constant accuracy, this cost is set by the intrinsic number of channel degrees of freedom. Thus the result provides an information-theoretic reference point for how costly it is to learn general noisy quantum dynamics, independently of any particular experimental platform or reconstruction heuristic.Our analysis also has implications for the role of adaptivity and coherence in quantum channel learning19,21,30,31. We show that adaptivity does not improve the asymptotic query complexity for process tomography at fixed constant diamond-distance accuracy: all uses of the unknown channel in our protocol occur in a single parallel block. At the same time, coherence across channel uses is provably helpful in this non-adaptive setting: ref. 19 shows that any fully incoherent, non-adaptive strategy necessarily incurs an asymptotically larger query complexity. Our scheme sits precisely at this intermediate point, being non-adaptive but coherent: it prepares many copies of the Choi state, applies a coherent random purification map15,22 and finally reduces the problem to sample-optimal pure-state tomography on independent copies of a fixed purification.Conceptually, our results show that the Choi-state representation suffices for channel tomography with optimal dependence on the input and output dimensions and Kraus rank at fixed constant accuracy in diamond distance. While the Choi–Jamiołkowski isomorphism guarantees that a quantum channel is uniquely determined by its Choi state, this equivalence does not automatically translate into an efficient learning strategy. Indeed, for several channel-learning tasks (including tasks beyond tomography), it has been argued that approaches based on preparing Choi states and then applying a direct analogue of the corresponding state-estimation procedure can be suboptimal compared with channel-tailored approaches18,21,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47. Our results show that this concern does not apply to diamond-distance channel tomography: Choi-state estimation suffices to achieve dimension-optimal learning guarantees in diamond distance.Finally, by specializing our protocol to the corresponding settings, we recover the optimal Θ(dk/ε2) sample-complexity scaling for trace-distance tomography of rank-k states and the optimal Θ(d2/ε) query-complexity scaling for diamond-distance learning of unitary channels. Beyond these cases, our general bounds also yield additional guarantees: for Kraus-rank-one channels, we obtain a diamond-norm tomography scheme for arbitrary isometries with query complexity O(dindout/ε2), with the additional practical experimental advantage that it does not require the random purification channel and therefore reduces to single-copy measurements on the Choi state; and for tomography of quantum measurements, we derive the dimension-optimal upper bound O(d2/ε2) for diamond-norm learning of binary measurement channels.Our results suggest several natural directions for further work. A first challenge would be to close the remaining gap between the upper and lower bounds for learning channels in diamond distance. The bounds match in their dependence on (din, dout, k), and in a broad parameter regime also in their dependence on the failure probability δ, but they do not yet match in the target accuracy ε. For fixed input and output dimensions, the optimal ε scaling depends sensitively on the admissible Kraus rank: once k exceeds the minimal value kmin, our reduction already enforces an Ω(1/ε2) contribution, whereas at the minimal Kraus rank the class contains unitary channels, for which Heisenberg scaling Θ(1/ε) is achievable and a uniform Ω(1/ε2) lower bound cannot hold in general. Characterizing the optimal joint dependence on (ε, din, dout, k)—specifically, determining the sharp ε-exponent β in equation (19)—remains an appealing open problem. We expect that sharpening the lower bound in this direction would establish the full optimality of our protocol in broad Kraus-rank regimes.A second direction would be to better understand the role of coherence in channel tomography. In particular, it would be interesting to determine the optimal query complexity under explicit restrictions on coherent processing across channel uses—for example, when one is limited to a number t of adaptive and coherent queries to the unknown channel interleaved with arbitrary quantum operations, including collective measurements across the t uses. For state tomography, such trade-offs between the number of copies and the available quantum memory (coherent versus incoherent measurements) have been analysed in refs. 48,49; developing an analogous theory for diamond-distance channel learning remains a largely open problem. One natural possibility is to study blockwise versions of our protocol, in which the coherent part is applied only within blocks of at most t Choi-state copies, while different blocks are processed independently and combined only through classical post-processing, in the spirit of limited-entanglement measurement schemes for state tomography15,50.MethodsOur learning scheme and upper boundIn this subsection we summarize our channel-learning protocol and its main guarantee, and sketch the key proof ideas. Full technical details are provided in Supplementary Information. Throughout, we fix an unknown quantum channel \(\varLambda :{\mathcal{L}}({{\mathcal{H}}}_{{\rm{in}}})\to {\mathcal{L}}({{\mathcal{H}}}_{{\rm{out}}})\) with input and output dimensions \({d}_{{\rm{in}}}:= \dim ({{\mathcal{H}}}_{{\rm{in}}})\) and \({d}_{{\rm{out}}}:= \dim ({{\mathcal{H}}}_{{\rm{out}}})\) and Kraus rank of at most k. Our objective is to learn Λ up to accuracy ε in diamond distance, while using as few calls to the black-box channel as possible.Our protocol (Algorithm 1) is formulated in terms of the Choi state of the channel. Let Φc = J(Λ) denote the normalized Choi state of Λ, defined by$${\varPhi }_{\mathrm{c}}:= J(\varLambda )=(\varLambda \otimes {{\rm{id}}}_{{{\mathcal{H}}}_{{\rm{in}}}})(\varOmega )\in {\mathcal{L}}({{\mathcal{H}}}_{{\rm{out}}}\otimes {{\mathcal{H}}}_{{\rm{in}}}),$$ (2) where \(\varOmega =\left\vert {\bf{\Omega}} \right\rangle \left\langle {\bf{\Omega}} \right\vert\) is the maximally entangled state on \({{\mathcal{H}}}_{{\rm{in}}}\otimes {{\mathcal{H}}}_{{\rm{in}}}\). Given that Λ has Kraus rank of at most k, the rank of Φc is at most k, and hence any purification of Φc lives in a Hilbert space of total dimension$${d}_{{\rm{tot}}}:= {d}_{{\rm{in}}}{d}_{{\rm{out}}}k.$$ (3) The central idea is to reduce diamond-distance learning of Λ to trace-distance pure-state tomography of such a purification of Φc of dimension dtot. Algorithm 1 Diamond-distance tomography for Kraus-rank-k channels Require: Access to \(\varLambda :{\mathcal{L}}({{\mathcal{H}}}_{{\rm{in}}})\to {\mathcal{L}}({{\mathcal{H}}}_{{\rm{out}}})\) with Kraus rank ≤ k; target accuracy ε ∈ (0, 1); failure probability δ ∈ (0, 1). 1: Choose N as prescribed by the complete theorem in Supplementary Information (to obtain ε-accuracy in diamond distance). 2: (Choi-state preparation) Using N parallel calls to Λ, prepare N copies of the normalized Choi state Φc = J(Λ) by feeding half of a maximally entangled state into each use of Λ. 3: (Purification) Apply the random purification channel15,22 described in Supplementary Information to \({\varPhi }_{\mathrm{c}}^{\otimes N}\) to obtain N copies of a random purification |Φc〉 of Φc. 4: (Pure-state tomography) Run a sample-optimal pure-state tomography scheme \({\mathcal{A}}\) on \({\left\vert {\mathbf{\Phi }}_{\mathrm{c}}\right\rangle }^{\otimes N}\) to obtain an estimate \(\left\vert {\hat{{\mathbf\Phi }}}_{\mathrm{c}}\right\rangle\). 5: (Choi reconstruction) Form the (normalized) Choi operator estimate$${\hat{\varPhi }}_{\mathrm{c}}:= {\text{tr}}_{E}\left(\left\vert {\hat{\mathbf{\Phi }}}_{\mathrm{c}}\right\rangle \left\langle {\hat{\mathbf{\Phi }}}_{\mathrm{c}}\right\vert \right),$$ (4) and let Λest be the completely positive map whose normalized Choi state is \({\hat{\varPhi }}_{\mathrm{c}}\). 6: (CPTP regularization) Compute a CPTP map \(\hat{\varLambda }\) by solving (as detailed in Supplementary Information) the SDP$$\hat{\varLambda }\in \arg {\mathop{\min }\limits_{\varPhi \in {\mathsf{CPTP}}}}\parallel \varPhi -{\varLambda }^{{\rm{est}}}{\parallel }_{\diamond }.$$ (5) Ensure: For N as above, the final estimator \(\hat{\varLambda }\) satisfies \(\frac{1}{2}\parallel\hat{\varLambda}-\varLambda{\parallel}_{\diamond}\le \varepsilon\) with a probability of at least 1 − δ. Our protocol (Algorithm 1) has three main steps: Parallel, non-adaptive Choi-state preparation. Given N uses of Λ, we prepare the Choi-state copies \({\varPhi }_{\mathrm{c}}^{\otimes N}\) by applying Λ⊗N in parallel to maximally entangled input states Ω⊗N on \({({{\mathcal{H}}}_{{\rm{in}}}\otimes {{\mathcal{H}}}_{{\rm{in}}})}^{\otimes N}\). All calls to the unknown channel occur in a single parallel block, and no adaptivity is required at the level of channel uses. Purification via the random purification channel. On the prepared Choi-state copies \({\varPhi }_{\mathrm{c}}^{\otimes N}\), we apply the random purification channel of ref. 22$${{\mathcal{P}}}^{(N)}:{\mathcal{D}}\left({({{\mathcal{H}}}_{{\rm{out}}}\otimes {{\mathcal{H}}}_{{\rm{in}}})}^{\otimes N}\right)\to {\mathcal{D}}\left({({{\mathcal{H}}}_{{\rm{out}}}\otimes {{\mathcal{H}}}_{{\rm{in}}}\otimes {{\mathcal{H}}}_{E})}^{\otimes N}\right),$$ (6) where \({{\mathcal{H}}}_{E}\simeq {{\mathbb{C}}}^{k}\) is an environment register, so that \({{\mathcal{H}}}_{{\rm{out}}}\otimes {{\mathcal{H}}}_{{\rm{in}}}\otimes {{\mathcal{H}}}_{E}\simeq {{\mathbb{C}}}^{{d}_{{\rm{tot}}}}\). This channel maps the mixed-state \({\varPhi }_{\mathrm{c}}^{\otimes N}\) to N copies of a random purification \(\left\vert {\mathbf{\Phi }}_{\mathrm{c}}\right\rangle \in {{\mathbb{C}}}^{{d}_{{\rm{tot}}}}\simeq {{\mathcal{H}}}_{{\rm{out}}}\otimes {{\mathcal{H}}}_{{\rm{in}}}\otimes {{\mathcal{H}}}_{E}\), in the sense that$${{\mathcal{P}}}^{(N)}\left({\varPhi }_{\mathrm{c}}^{\otimes N}\right)={{\mathbb{E}}}_{\left\vert {\varPhi }_{\mathrm{c}}^{{\prime} }\right\rangle }\left[\left\vert {\mathbf{\Phi }}_{\mathrm{c}}^{{\prime} }\right\rangle {\left\langle {\mathbf{\Phi }}_{\mathrm{c}}^{{\prime} }\right\vert }^{\otimes N}\right],$$ (7) where the expectation is over purifications \(\left\vert {\mathbf{\Phi }}_{\mathrm{c}}^{{\prime} }\right\rangle\) drawn from the unitarily invariant (Haar) measure on the environment. This is the only stage that really requires coherent (entangled) operations across different Choi-state copies, and it does not involve any further calls to the unknown channel. For Kraus-rank-one channels, the Choi state is already pure, so this purification step is unnecessary. Pure-state tomography and CPTP regularization. We perform pure-state tomography on \({\left\vert {\mathbf{\Phi }}_{\mathrm{c}}\right\rangle }^{\otimes N}\) using a covariant, sample-optimal pure-state tomography algorithm \({\mathcal{A}}\) (for example, refs. 12,24) on \({{\mathbb{C}}}^{{d}_{{\rm{tot}}}}\), obtaining a purified estimate \(\left\vert {\hat{\mathbf{\Phi }}}_{\mathrm{c}}\right\rangle\). Here ‘covariant’ means that rotating the unknown state by a unitary simply rotates the output estimate by the same unitary, without changing its error distribution; a formal definition is given in Supplementary Information. Tracing out the purifying register yields an intermediate CP map Λest with Choi operator$$J({\varLambda }^{{\rm{est}}})={{\rm{tr}}}_{E}\left(\left\vert {\hat{\mathbf{\Phi }}}_{\mathrm{c}}\right\rangle \left\langle {\hat{\mathbf{\Phi }}}_{\mathrm{c}}\right\vert \right).\,$$ (8) As a final step, we regularize this intermediate estimate by projecting it (via an SDP) onto the convex set of CPTP maps in diamond norm, namely$$\hat{\varLambda}\in \arg {\mathop{\min }\limits_{\varPhi\in{\mathsf{CPTP}}}}\parallel \varPhi-{\varLambda}^{{\rm{est}}}{\parallel}_{\diamond }.\,$$ (9) The pure-state tomography algorithm \({\mathcal{A}}\) can be any covariant scheme on \({{\mathbb{C}}}^{{d}_{{\rm{tot}}}}\) with trace-distance accuracy guarantees. Let εpure = εpure(N, δ, dtot) denote its worst-case trace-distance accuracy parameter, in the sense that when \({\mathcal{A}}\) is run on N copies of any pure state in \({{\mathbb{C}}}^{{d}_{{\rm{tot}}}}\), it outputs an estimated pure state with a trace distance accuracy of at most εpure with a probability of at least 1 − δ. The restriction to covariant schemes is without a loss of generality for worst-case pure-state tomography: with the covariance lemma in Supplementary Information, any pure-state tomography scheme can be converted into a covariant one by applying a Haar-random unitary to the unknown state and undoing the same unitary on the output estimate, without worsening its worst-case performance. This covariance property is useful because it makes the error direction isotropic, which is the key input for modelling the relevant error component as Haar-random.Our main structural result, the complete theorem in Supplementary Information, relates the performance of such a pure-state scheme to the resulting channel estimator \(\hat{\varLambda }\) produced by Algorithm 1. It shows that$$\dfrac{1}{2}\parallel \hat{\varLambda }-\varLambda {\parallel }_{\diamond }\le \left(2+\sqrt{\dfrac{1}{k{d}_{{\rm{out}}}}\log \dfrac{4}{\delta }}\,\right)\left[4+{S}_{\delta }({d}_{{\rm{tot}}})\right]\,{\varepsilon }_{{\rm{pure}}},$$ (10) with a probability of at least 1 − δ, where Sδ(dtot) is an explicit subleading function in the total dimension and failure probability analysed in the proof. In particular, the diamond-distance error of channel tomography essentially scales linearly with the underlying trace-distance error of pure-state tomography.One convenient choice for \({\mathcal{A}}\) is a projected least-squares scheme based on single-copy measurements24, or Hayashi’s covariant coherent scheme12. Both are sample-optimal, in the sense that achieving trace-distance error εpure with a failure probability of at most δ requires$$N=\varTheta \left(\dfrac{{d}_{{\rm{tot}}}+\log ({\delta }^{-1})}{{\varepsilon }_{{\rm{pure}}}^{2}}\right),$$ (11) which is optimal in its dependence on dtot, εpure and δ (see, for example, ref. 15). Inverting this relation for εpure and substituting into equation (10), together with dtot = dindoutk, yields our main upper bound on the query complexity of diamond-distance channel learning.In the regime where the target failure probability is not extremely small compared with the total dimension, that is, δ > 4exp(−dtot), we show that Sδ(dtot) remains uniformly bounded and the prefactor in equation (10) can be simplified, leading to the following statement. Theorem 2 (Main theorem) Let Λ be a channel with input dimension din, output dimension dout and Kraus rank of at most k. Fix ε ∈ (0, 1) and δ ∈ (0, 1) satisfying δ > 4exp(−dindoutk). Then there exists a non-adaptive tomography protocol (Algorithm 1) that uses$$N=O\left(\dfrac{{d}_{{\rm{in}}}{d}_{{\rm{out}}}k+{d}_{{\rm{in}}}\log (1/\delta )}{{\varepsilon }^{2}}\right)$$ (12) queries to Λ and outputs a classical description of a quantum channel \({\hat{\varLambda}}\) satisfying \(\parallel {\hat{\varLambda}}-\varLambda {\parallel }_{\diamond }\le \varepsilon\) with a probability of at least 1 − δ. For example, if \({\mathcal{A}}\) is instantiated with Hayashi’s optimal covariant pure-state scheme12, the bound with leading constant explicit becomes N = 256dindoutk/ε2 + O(dinlog(1/δ)/ε2).If one prefers a statement with no restriction on the failure probability, δ, a standard boosting argument (see the boosting argument in Supplementary Information) yields a clean bound, valid for all δ ∈ (0, 1), namely N = O(dindoutklog(1/δ)/ε2). In particular, for any fixed constant failure probability, this reduces to exactly the scaling claimed in Theorem 1.Before giving the proof sketch, it is useful to isolate the standard obstruction that makes a naive Choi-state tomography approach seem insufficient for achieving the desired dimension scaling in diamond-norm channel tomography. If \(\widehat{J}\) is an estimate of the Choi state J(Λ) satisfying \(\parallel \widehat{J}-J(\Lambda ){\parallel }_{1}\le \varepsilon\), then the standard worst-case Choi-to-diamond conversion gives only$$\parallel {\hat{\Lambda}}-\Lambda {\parallel }_{\diamond }\le {d}_{{\rm{in}}}\parallel \widehat{J}-J(\Lambda ){\parallel }_{1}\le {d}_{{\rm{in}}}\varepsilon .$$ (13) Thus, a Choi trace-norm error ε may translate into a diamond-norm error larger by a factor of din, producing an unwanted dimension overhead in the query complexity. The proof sketch below explains why our estimator is not governed by this worst-case conversion: the pure-state tomography error direction is effectively Haar-random, and the resulting concentration cancels the din factor in the induced diamond-norm error. Proof Proof sketch of the upper bound. A formal statement and full proof are given in Supplementary Information; here we only summarize the main mechanism. Conditioned on achieving a trace-distance error of at most εpure in the pure-state tomography step, the estimated Choi-state purification can be written as$$\left\vert {\hat{\mathbf{\Phi }}}_{\mathrm{c}}\right\rangle =\sqrt{1-{\varepsilon }_{{\rm{pure}}}^{2}}\,\left\vert {\mathbf{\Phi }}_{\mathrm{c}}\right\rangle +{\varepsilon }_{{\rm{pure}}}\,\left\vert {\pmb{\uppsi}}_{{\rm{err}}}\right\rangle ,$$ (14) where, thanks to the covariance of the pure-state tomography algorithm (as established in Supplementary Information), |ψerr〉 is a Haar-random unit vector on the subspace orthogonal to the Choi-state purification |Φc〉. Intuitively, covariance forces the error direction to be isotropic; up to the subleading corrections, we may therefore treat |ψerr〉 as Haar-random in \({{\mathbb{C}}}^{{d}_{{\rm{tot}}}}\). We now translate this decomposition into a statement about channels. Let \(\hat{J}={\text{tr}}_{E}(\left\vert {\hat{\mathbf{\Phi }}}_{c}\right\rangle \left\langle {\hat{\mathbf{\Phi }}}_{c}\right\vert )\) be the estimated normalized Choi operator and let \(J(\varLambda )={\text{tr}}_{E}(\left\vert {\mathbf{\Phi }}_{c}\right\rangle \left\langle {\mathbf{\Phi }}_{c}\right\vert )\) be the true one. Expanding \(\hat{J}-J(\varLambda )\) using the decomposition above gives a true-channel block, an error block \({\text{tr}}_{E}(\left\vert \mathbf{\uppsi }_{{\rm{err}}}\right\rangle \left\langle \mathbf{\uppsi }_{{\rm{err}}}\right\vert )\) and two off-diagonal cross terms. We apply the triangle inequality to this decomposition. The true-channel block has diamond norm 1, as it is the Choi operator of a valid channel, and the off-diagonal terms are controlled by the diamond Cauchy–Schwarz inequality proved in Supplementary Information in terms of the true-channel block and the Haar-error block. Thus the diamond-norm error is reduced to the diamond norm of the Haar-error block. More precisely, writing ∥X∥⋄ for the diamond norm of the map with normalized Choi operator X, we obtain$$\parallel \!{\varLambda }^{{\rm{est}}}-\varLambda {\parallel }_{\diamond }=\parallel \hat{J}-J(\varLambda ){\parallel }_{\diamond }\le O({\varepsilon }_{{\rm{pure}}})\left(1+{\left\Vert {\text{tr}}_{E}\left(\left\vert \mathbf{\uppsi }_{{\rm{err}}}\right\rangle \left\langle \mathbf{\uppsi }_{{\rm{err}}}\right\vert \right)\right\Vert }_{\diamond }\right).$$ (15) It remains to show that this last diamond norm is O(1). As \({\text{tr}}_{E}(\left\vert \mathbf{\uppsi }_{{\rm{err}}}\right\rangle \left\langle \mathbf{\uppsi }_{{\rm{err}}}\right\vert )\) is a positive Choi operator, the SDP characterization of the diamond norm for positive Choi operators, proved in Supplementary Information, shows that the diamond norm reduces to the operator norm of the input marginal$${\left\Vert {\text{tr}}_{E}\left(\left\vert \mathbf{\uppsi }_{{\rm{err}}}\right\rangle \left\langle \mathbf{\uppsi }_{{\rm{err}}}\right\vert \right)\right\Vert }_{\diamond }={d}_{{\rm{in}}}{\left\Vert {\text{tr}}_{{\rm{out}},E}\left(\left\vert \mathbf{\uppsi }_{{\rm{err}}}\right\rangle \left\langle \mathbf{\uppsi }_{{\rm{err}}}\right\vert \right)\right\Vert }_{\infty }={d}_{{\rm{in}}}\times O\left(\dfrac{1}{{d}_{{\rm{in}}}}\right)=O(1),$$ (16) where in the second step we used the concentration of reduced states of Haar-random vectors (see Supplementary Information) with high probability. This is the essential cancellation: the din factor from the diamond-norm SDP characterization is compensated by the O(1/din) operator-norm scaling of a Haar-random reduced state. Substituting this into the previous bound yields \(\parallel \!{\varLambda }^{{\rm{est}}}-\varLambda {\parallel }_{\diamond }=O({\varepsilon }_{{\rm{pure}}})\). The final CPTP regularization changes the error by at most a constant factor. Finally, sample-optimal pure-state tomography gives \({\varepsilon }_{{\rm{pure}}}=O(\sqrt{{d}_{{\rm{tot}}}/N})\). Since dtot = dindoutk, choosing N = O(dindoutk/ε2) gives the claimed query-complexity scaling. This proof sketch also clarifies why the result does not follow directly from mixed-state tomography alone. The known ingredients that we import are the random purification channel15,22,23 and pure-state tomography12,15, while our technical contribution comes from directly controlling the diamond distance of the specific Choi-state estimator produced by these subroutines.Lower bounds for channel tomographyWe now turn to the lower bounds; the fully explicit statements, proofs and additional discussion are presented in Supplementary Information. Recall that the Kraus rank of a channel must satisfy kmin ≤ k ≤ dindout, where \({k}_{\min }:= \lceil {d}_{{\rm{in}}}/{d}_{{\rm{out}}}\rceil\). Theorem 3 (Query lower bounds for channel tomography) Any tomography protocol that, for every channel \(\varLambda :{\mathcal{L}}({{\mathbb{C}}}^{{d}_{{\rm{in}}}})\to {\mathcal{L}}({{\mathbb{C}}}^{{d}_{{\rm{out}}}})\) of Kraus rank at most k, uses N queries to Λ and outputs an estimator \({\hat{\varLambda}}\) satisfying$$\parallel {\hat{\varLambda}}-\varLambda {\parallel }_{\diamond }\le \varepsilon$$ (17) with a probability of at least 1 − δ, must obey$$N=\varOmega \left(\dfrac{{d}_{{\rm{in}}}{d}_{{\rm{out}}}k}{{\varepsilon }^{\beta }}+\dfrac{m}{{\varepsilon }^{2}}\log \dfrac{m}{\delta }\right),$$ (18) where β = β(din, dout, k)≤1 and m = m(din, dout, k) ∈ [0, din] are given explicitly in Supplementary Information. In particular, m = 0 at minimal Kraus rank k = kmin, m > 0 whenever k > kmin and m = din whenever k ≥ 2din. In particular, the first term gives the dimension-dependent lower bound Ω(dindoutk) at fixed constant accuracy. The second term gives a \(\varOmega \left(\frac{1}{{\varepsilon }^{2}}\log \frac{1}{\delta }\right)\) contribution whenever the Kraus rank is non-minimal. At the minimal Kraus rank k = kmin, this Ω(ε−2)-contribution vanishes (that is, m = 0), which is consistent with the fact that the class of Kraus-rank-kmin channels contains unitary channels, for which Heisenberg scaling N = O(1/ε) is achievable in diamond distance; see, for example, ref. 17. Moreover, when k ≥ 2din we have m = din and equation (18) reduces to$$N=\varOmega \left(\dfrac{{d}_{{\rm{in}}}{d}_{{\rm{out}}}k}{{\varepsilon }^{\beta }}+\dfrac{{d}_{{\rm{in}}}}{{\varepsilon }^{2}}\log \dfrac{{d}_{{\rm{in}}}}{\delta }\right).$$ (19) Theorem 3 matches the dimension dependence of our upper bound, and in the regime δ > 4 exp(−dindoutk) and k ≥ 2din it also matches its dependence on δ. Indeed, in this regime our upper bound (Theorem 2) can be written as$$N=O\left(\dfrac{{d}_{{\rm{in}}}{d}_{{\rm{out}}}k}{{\varepsilon }^{2}}+\dfrac{{d}_{{\rm{in}}}}{{\varepsilon }^{2}}\log \dfrac{{d}_{{\rm{in}}}}{\delta }\right).$$ (20) However, the exponent β governing the ε dependence in the first term of equation (19) is not tight in general. As the proof sketch below indicates, this exponent is tied to the particular proof strategy based on the packing construction and channel-identification bound used. We expect that refined lower-bound constructions may improve the exponent β, plausibly matching our upper bound in broader parameter regimes; we leave this to future work.For fixed constant accuracy and constant success probability, Theorem 3 implies the matching lower bound N = Ω(dindoutk). Moreover, we show in Supplementary Information that this dimension lower bound remains valid even if the protocol is granted purified access to a fixed Stinespring dilation of Λ, with the environment register retained, and no definite causal order is imposed among the N uses.We now sketch the proof. Full details are given in Supplementary Information. Proof (Proof sketch) The two terms in equation (18) come from two independent reductions. We first prove the dimension-dependent term by reducing tomography to channel identification. Let \({\{{\varLambda }_{x}\}}_{x = 1}^{M}\) be a family of Kraus-rank-k channels satisfying ∥Λx − Λy∥⋄ > 2ε for all x ≠ y; that is, a packing net of channels. Any tomography protocol that outputs an ε-accurate estimate can then be used to identify which channel Λx was given. Thus tomography is at least as hard as identifying an element of a large diamond-distance packing. For this identification task, we prove that any N-query protocol trying to identify one of the M channels chosen uniformly at random has a success probability that satisfies$$\begin{array}{l}{p}_{{\rm{succ}}}:= \dfrac{1}{M}\mathop{\sum }\limits_{x=1}^{M}\,\text{Pr}\,[\,\text{the}\,\,\,\text{protocol}\,\,\,\text{outputs}\,x| {\varLambda }_{x}]\\\qquad\quad\;\le \dfrac{1}{M}\left(\begin{array}{l}N+D-1\\ D-1\end{array}\right),\qquad D:= {d}_{{\rm{in}}}{d}_{{\rm{out}}}k.\end{array}$$ (21) Intuitively, the binomial factor is the effective symmetric-subspace dimension accessible from N uses of a Kraus-rank-k channel, even allowing fully general quantum strategies. Hence constant success probability forces \(M\lesssim \left(\begin{array}{l}N+D-1\\ D-1\end{array}\right)\). Using the standard estimate \(\left(\begin{array}{l}N+D-1\\ D-1\end{array}\right)\lesssim {(1+N/(D-1))}^{D-1}\), this implies that N ≳ (D − 1)M1/(D−1). It remains to construct a sufficiently large packing, which will fix M. We do this by packing Stinespring isometries and treating as equivalent Stinespring isometries that differ only by a unitary transformation on the environment, as environment-unitarily equivalent Stinespring isometries define the same channel. The Stinespring-isometry manifold has real dimension \(2{d}_{{\rm{in}}}{d}_{{\rm{out}}}k-{d}_{{\rm{in}}}^{2}\), and passing to these equivalence classes removes k2 redundant real parameters. Thus the effective dimension is \(2{d}_{{\rm{in}}}{d}_{{\rm{out}}}k-{d}_{{\rm{in}}}^{2}-{k}^{2}.\) Accounting for the relation between the Stinespring distance and diamond distance gives a packing of size \(M\gtrsim {(1/\sqrt{\varepsilon })}^{2{d}_{{\rm{in}}}{d}_{{\rm{out}}}k-{d}_{{\rm{in}}}^{2}-{k}^{2}}\). Combining this with the identification bound yields$$N=\varOmega \left(\dfrac{D}{{\varepsilon }^{\beta }}\right),\qquad \beta =\dfrac{2{d}_{{\rm{in}}}{d}_{{\rm{out}}}k-{d}_{{\rm{in}}}^{2}-{k}^{2}}{2(D-1)},$$ (22) where D = dindoutk. This gives the first term in equation (18); in particular, at fixed constant accuracy it gives N = Ω(dindoutk). This ε-dependent exponent should not be interpreted as sharp. It is a by-product of the particular packing route used here: the argument first separates Stinespring isometries and then transfers this separation to channels in diamond distance. This is well suited to capturing the dimension of the channel family at constant accuracy, but not necessarily the optimal local scaling in ε. The second term has a different, statistical origin. We restrict it to a subfamily of Kraus-rank-k channels that encodes the biases of m independent classical coins. Learning such a channel to diamond-distance accuracy ε allows one to estimate these coin biases to accuracy O(ε). Standard coin-bias lower bounds therefore imply that N = Ω((m/ε2)log(m/δ)). Here m = 0 at minimal Kraus rank, m > 0 as soon as the Kraus rank is non-minimal and m = din when k ≥ 2din, as in that regime there is enough Kraus-rank slack to encode one independent coin bias for each input basis state. Given that a tomography protocol must succeed uniformly over all channels with Kraus rank of at most k, both reductions apply. Combining them gives equation (18). Although for general Kraus-rank-k channels our proof method captures the optimal dependence on (din, dout, k), it does not do so for the target accuracy ε. However, for important special cases—notably pure-state tomography in trace distance and unitary-channel tomography in diamond norm—we can show that the same framework combined with the corresponding packing bounds recovers the optimal scaling in both the dimension parameters and ε.Finally, we use the same approach to obtain a dimension-matching lower bound for learning binary measurement channels in diamond distance (equivalently for learning the associated POVM element in operator norm), showing that our Θ(d2) query-complexity scaling is necessary and sufficient at constant accuracy. Similarly to above, we also prove a separate accuracy- and failure probability-dependent lower bound of Ω(dε−2log(d/δ)) for learning binary measurements.