Our learning scheme and upper bound<\/p>\n
In 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<\/a>. 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 \u039b up to accuracy \u03b5 in diamond distance, while using as few calls to the black-box channel as possible.<\/p>\n Our protocol (Algorithm 1) is formulated in terms of the Choi state of the channel. Let \u03a6c = J(\u039b) denote the normalized Choi state of \u039b, defined by<\/p>\n $${\\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}}}),$$<\/p>\n \n (2)\n <\/p>\n 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 \u039b has Kraus rank of at most k, the rank of \u03a6c is at most k, and hence any purification of \u03a6c lives in a Hilbert space of total dimension<\/p>\n $${d}_{{\\rm{tot}}}:= {d}_{{\\rm{in}}}{d}_{{\\rm{out}}}k.$$<\/p>\n \n (3)\n <\/p>\n The central idea is to reduce diamond-distance learning of \u039b to trace-distance pure-state tomography of such a purification of \u03a6c of dimension dtot.<\/p>\n Algorithm 1<\/p>\n Diamond-distance tomography for Kraus-rank-k channels<\/p>\n Require: Access to \\(\\varLambda :{\\mathcal{L}}({{\\mathcal{H}}}_{{\\rm{in}}})\\to {\\mathcal{L}}({{\\mathcal{H}}}_{{\\rm{out}}})\\) with Kraus rank\u2009\u2264\u2009k; target accuracy \u03b5\u2009\u2208\u2009(0,\u20091); failure probability \u03b4\u2009\u2208\u2009(0,\u20091).<\/p>\n 1: Choose N as prescribed by the complete theorem in Supplementary Information<\/a> (to obtain \u03b5-accuracy in diamond distance).<\/p>\n 2: (Choi-state preparation) Using N parallel calls to \u039b, prepare N copies of the normalized Choi state \u03a6c = J(\u039b) by feeding half of a maximally entangled state into each use of \u039b.<\/p>\n 3: (Purification) Apply the random purification channel15<\/a>,22<\/a> described in Supplementary Information<\/a> to \\({\\varPhi }_{\\mathrm{c}}^{\\otimes N}\\) to obtain N copies of a random purification |\u03a6c\u3009 of \u03a6c.<\/p>\n 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\\).<\/p>\n 5: (Choi reconstruction) Form the (normalized) Choi operator estimate<\/p>\n $${\\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),$$<\/p>\n \n (4)\n <\/p>\n and let \u039best be the completely positive map whose normalized Choi state is \\({\\hat{\\varPhi }}_{\\mathrm{c}}\\).<\/p>\n 6: (CPTP regularization) Compute a CPTP map \\(\\hat{\\varLambda }\\) by solving (as detailed in Supplementary Information<\/a>) the SDP<\/p>\n $$\\hat{\\varLambda }\\in \\arg {\\mathop{\\min }\\limits_{\\varPhi \\in {\\mathsf{CPTP}}}}\\parallel \\varPhi -{\\varLambda }^{{\\rm{est}}}{\\parallel }_{\\diamond }.$$<\/p>\n \n (5)\n <\/p>\n 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\u2009\u2212\u2009\u03b4.<\/p>\n Our protocol (Algorithm 1) has three main steps:<\/p>\n Parallel, non-adaptive Choi-state preparation. Given N uses of \u039b, we prepare the Choi-state copies \\({\\varPhi }_{\\mathrm{c}}^{\\otimes N}\\) by applying \u039b\u2297N in parallel to maximally entangled input states \u03a9\u2297N 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.<\/p>\n 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<\/a><\/p>\n $${{\\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),$$<\/p>\n \n (6)\n <\/p>\n 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<\/p>\n $${{\\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],$$<\/p>\n \n (7)\n <\/p>\n 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.<\/p>\n 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.\u200912<\/a>,24<\/a>) on \\({{\\mathbb{C}}}^{{d}_{{\\rm{tot}}}}\\), obtaining a purified estimate \\(\\left\\vert {\\hat{\\mathbf{\\Phi }}}_{\\mathrm{c}}\\right\\rangle\\). Here \u2018covariant\u2019 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<\/a>. Tracing out the purifying register yields an intermediate CP map \u039best with Choi operator<\/p>\n $$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).\\,$$<\/p>\n \n (8)\n <\/p>\n 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<\/p>\n $$\\hat{\\varLambda}\\in \\arg {\\mathop{\\min }\\limits_{\\varPhi\\in{\\mathsf{CPTP}}}}\\parallel \\varPhi-{\\varLambda}^{{\\rm{est}}}{\\parallel}_{\\diamond }.\\,$$<\/p>\n \n (9)\n <\/p>\n The pure-state tomography algorithm \\({\\mathcal{A}}\\) can be any covariant scheme on \\({{\\mathbb{C}}}^{{d}_{{\\rm{tot}}}}\\) with trace-distance accuracy guarantees. Let \u03b5pure\u2009=\u2009\u03b5pure(N,\u2009\u03b4,\u2009dtot) 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 \u03b5pure with a probability of at least 1\u2009\u2212\u2009\u03b4. The restriction to covariant schemes is without a loss of generality for worst-case pure-state tomography: with the covariance lemma in Supplementary Information<\/a>, 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.<\/p>\n Our main structural result, the complete theorem in Supplementary Information<\/a>, relates the performance of such a pure-state scheme to the resulting channel estimator \\(\\hat{\\varLambda }\\) produced by Algorithm 1. It shows that<\/p>\n $$\\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}}},$$<\/p>\n \n (10)\n <\/p>\n with a probability of at least 1\u2009\u2212\u2009\u03b4, where S\u03b4(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.<\/p>\n One convenient choice for \\({\\mathcal{A}}\\) is a projected least-squares scheme based on single-copy measurements24<\/a>, or Hayashi\u2019s covariant coherent scheme12<\/a>. Both are sample-optimal, in the sense that achieving trace-distance error \u03b5pure with a failure probability of at most \u03b4 requires<\/p>\n $$N=\\varTheta \\left(\\dfrac{{d}_{{\\rm{tot}}}+\\log ({\\delta }^{-1})}{{\\varepsilon }_{{\\rm{pure}}}^{2}}\\right),$$<\/p>\n \n (11)\n <\/p>\n which is optimal in its dependence on dtot, \u03b5pure and \u03b4 (see, for example, ref.\u200915<\/a>). Inverting this relation for \u03b5pure and substituting into equation (10<\/a>), together with dtot\u2009=\u2009dindoutk, yields our main upper bound on the query complexity of diamond-distance channel learning.<\/p>\n In the regime where the target failure probability is not extremely small compared with the total dimension, that is, \u03b4\u2009>\u20094exp(\u2212dtot), we show that S\u03b4(dtot) remains uniformly bounded and the prefactor in equation (10<\/a>) can be simplified, leading to the following statement.<\/p>\n Theorem 2<\/p>\n (Main theorem) Let \u039b be a channel with input dimension din, output dimension dout and Kraus rank of at most k. Fix \u03b5\u2009\u2208\u2009(0,\u20091) and \u03b4\u2009\u2208\u2009(0,\u20091) satisfying \u03b4\u2009>\u20094exp(\u2212dindoutk). Then there exists a non-adaptive tomography protocol (Algorithm 1) that uses<\/p>\n $$N=O\\left(\\dfrac{{d}_{{\\rm{in}}}{d}_{{\\rm{out}}}k+{d}_{{\\rm{in}}}\\log (1\/\\delta )}{{\\varepsilon }^{2}}\\right)$$<\/p>\n \n (12)\n <\/p>\n queries to \u039b 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\u2009\u2212\u2009\u03b4.<\/p>\n For example, if \\({\\mathcal{A}}\\) is instantiated with Hayashi\u2019s optimal covariant pure-state scheme12<\/a>, the bound with leading constant explicit becomes N\u2009=\u2009256dindoutk\/\u03b52\u2009+\u2009O(dinlog(1\/\u03b4)\/\u03b52).<\/p>\n If one prefers a statement with no restriction on the failure probability, \u03b4, a standard boosting argument (see the boosting argument in Supplementary Information<\/a>) yields a clean bound, valid for all \u03b4\u2009\u2208\u2009(0,\u20091), namely N\u2009=\u2009O(dindoutklog(1\/\u03b4)\/\u03b52). In particular, for any fixed constant failure probability, this reduces to exactly the scaling claimed in Theorem 1.<\/p>\n 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(\u039b) satisfying \\(\\parallel \\widehat{J}-J(\\Lambda ){\\parallel }_{1}\\le \\varepsilon\\), then the standard worst-case Choi-to-diamond conversion gives only<\/p>\n $$\\parallel {\\hat{\\Lambda}}-\\Lambda {\\parallel }_{\\diamond }\\le {d}_{{\\rm{in}}}\\parallel \\widehat{J}-J(\\Lambda ){\\parallel }_{1}\\le {d}_{{\\rm{in}}}\\varepsilon .$$<\/p>\n \n (13)\n <\/p>\n Thus, a Choi trace-norm error \u03b5 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.<\/p>\n Proof<\/p>\n Proof sketch of the upper bound. A formal statement and full proof are given in Supplementary Information<\/a>; here we only summarize the main mechanism. Conditioned on achieving a trace-distance error of at most \u03b5pure in the pure-state tomography step, the estimated Choi-state purification can be written as<\/p>\n $$\\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 ,$$<\/p>\n \n (14)\n <\/p>\n where, thanks to the covariance of the pure-state tomography algorithm (as established in Supplementary Information<\/a>), |\u03c8err\u3009 is a Haar-random unit vector on the subspace orthogonal to the Choi-state purification |\u03a6c\u3009. Intuitively, covariance forces the error direction to be isotropic; up to the subleading corrections, we may therefore treat |\u03c8err\u3009 as Haar-random in \\({{\\mathbb{C}}}^{{d}_{{\\rm{tot}}}}\\).<\/p>\n 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\u2013Schwarz inequality proved in Supplementary Information<\/a> 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 \u2225X\u2225\u22c4 for the diamond norm of the map with normalized Choi operator X, we obtain<\/p>\n $$\\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).$$<\/p>\n \n (15)\n <\/p>\n 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<\/a>, shows that the diamond norm reduces to the operator norm of the input marginal<\/p>\n $${\\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),$$<\/p>\n \n (16)\n <\/p>\n where in the second step we used the concentration of reduced states of Haar-random vectors (see Supplementary Information<\/a>) 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\/\u03b52) gives the claimed query-complexity scaling.<\/p>\n 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<\/a>,22<\/a>,23<\/a> and pure-state tomography12<\/a>,15<\/a>, while our technical contribution comes from directly controlling the diamond distance of the specific Choi-state estimator produced by these subroutines.<\/p>\n Lower bounds for channel tomography<\/p>\n We now turn to the lower bounds; the fully explicit statements, proofs and additional discussion are presented in Supplementary Information<\/a>. Recall that the Kraus rank of a channel must satisfy kmin\u2009\u2264\u2009k\u2009\u2264\u2009dindout, where \\({k}_{\\min }:= \\lceil {d}_{{\\rm{in}}}\/{d}_{{\\rm{out}}}\\rceil\\).<\/p>\n Theorem 3<\/p>\n (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 \u039b and outputs an estimator \\({\\hat{\\varLambda}}\\) satisfying<\/p>\n $$\\parallel {\\hat{\\varLambda}}-\\varLambda {\\parallel }_{\\diamond }\\le \\varepsilon$$<\/p>\n \n (17)\n <\/p>\n with a probability of at least 1\u2009\u2212\u2009\u03b4, must obey<\/p>\n $$N=\\varOmega \\left(\\dfrac{{d}_{{\\rm{in}}}{d}_{{\\rm{out}}}k}{{\\varepsilon }^{\\beta }}+\\dfrac{m}{{\\varepsilon }^{2}}\\log \\dfrac{m}{\\delta }\\right),$$<\/p>\n \n (18)\n <\/p>\n where \u03b2\u2009=\u2009\u03b2(din,\u2009dout,\u2009k)\u22641 and m\u2009=\u2009m(din,\u2009dout,\u2009k)\u2009\u2208\u2009[0,\u2009din] are given explicitly in Supplementary Information<\/a>. In particular, m\u2009=\u20090 at minimal Kraus rank k\u2009=\u2009kmin, m\u2009>\u20090 whenever k\u2009>\u2009kmin and m\u2009=\u2009din whenever k\u2009\u2265\u20092din.<\/p>\n In particular, the first term gives the dimension-dependent lower bound \u03a9(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\u2009=\u2009kmin, this \u03a9(\u03b5\u22122)-contribution vanishes (that is, m\u2009=\u20090), which is consistent with the fact that the class of Kraus-rank-kmin channels contains unitary channels, for which Heisenberg scaling N\u2009=\u2009O(1\/\u03b5) is achievable in diamond distance; see, for example, ref.\u200917<\/a>. Moreover, when k\u2009\u2265\u20092din we have m\u2009=\u2009din and equation (18<\/a>) reduces to<\/p>\n $$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).$$<\/p>\n \n (19)\n <\/p>\n Theorem 3 matches the dimension dependence of our upper bound, and in the regime \u03b4\u2009>\u20094 exp(\u2212dindoutk) and k\u2009\u2265\u20092din it also matches its dependence on \u03b4. Indeed, in this regime our upper bound (Theorem 2) can be written as<\/p>\n $$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).$$<\/p>\n \n (20)\n <\/p>\n However, the exponent \u03b2 governing the \u03b5 dependence in the first term of equation (19<\/a>) 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 \u03b2, plausibly matching our upper bound in broader parameter regimes; we leave this to future work.<\/p>\n For fixed constant accuracy and constant success probability, Theorem 3 implies the matching lower bound N\u2009=\u2009\u03a9(dindoutk). Moreover, we show in Supplementary Information<\/a> that this dimension lower bound remains valid even if the protocol is granted purified access to a fixed Stinespring dilation of \u039b, with the environment register retained, and no definite causal order is imposed among the N uses.<\/p>\n We now sketch the proof. Full details are given in Supplementary Information<\/a>.<\/p>\n Proof<\/p>\n (Proof sketch) The two terms in equation (18<\/a>) come from two independent reductions.<\/p>\n 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 \u2225\u039bx\u2009\u2212\u2009\u039by\u2225\u22c4\u2009>\u20092\u03b5 for all x\u2009\u2260\u2009y; that is, a packing net of channels. Any tomography protocol that outputs an \u03b5-accurate estimate can then be used to identify which channel \u039bx 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<\/p>\n $$\\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}$$<\/p>\n \n (21)\n <\/p>\n 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\u2009\u2273\u2009(D\u2009\u2212\u20091)M1\/(D\u22121).<\/p>\n 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<\/p>\n $$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)},$$<\/p>\n \n (22)\n <\/p>\n