We study tomography for quantum channels with input dimension $d_1$, output dimension $d_2$, and Kraus rank at most $r$, to within diamond norm error $\varepsilon$, using adaptive experiments that retain no quantum memory between channel queries.
- For quantum channels whose non-zero Choi eigenvalues are bounded below by $Ω(d_1/r)$, we establish optimal query upper and lower bounds $Θ(d_1d_2r^2/ε^2)$. The upper bound is achieved by a nonadaptive algorithm that uses the estimator from [Surawy-Stepney et al., Quantum (2022)], together with a new diamond-norm analysis. The lower bound applies to arbitrary adaptive incoherent protocols and follows from a new local family of channels and a uniform one-query Fisher-information bound.
- For general channels, we establish an upper bound $O(d_1d_2r^2\log(2d_1)/ε^2)$, nearly matching the above lower bound $Ω(d_1d_2r^2/\varepsilon^2)$. To achieve this, we generalize the above nonadaptive algorithm by adapting the input state over $O(\log(2d_1))$ rounds with the Matrix Multiplicative Weight Update algorithm.
We study tomography for quantum channels with input dimension d1, output dimension d2, and Kraus rank at most r, to within diamond norm error ε, using adaptive experiments that retain no quantum memory between channel queries.
For quantum channels whose non-zero Choi eigenvalues are bounded below by Ω(d1/r), we establish optimal query upper and lower bounds Θ(d1d2r2/ε2). The upper bound is achieved by a nonadaptive algorithm that uses the estimator from [Surawy-Stepney et al., Quantum (2022)], together with a new diamond-norm analysis. The lower bound applies to arbitrary adaptive incoherent protocols and follows from a new local family of channels and a uniform one-query Fisher-information bound.
For general channels, we establish an upper bound O(d1d2r2log(2d1)/ε2), nearly matching the above lower bound Ω(d1d2r2/ε2). To achieve this, we generalize the above nonadaptive algorithm by adapting the input state over O(log(2d1)) rounds with the Matrix Multiplicative Weight Update algorithm.
Consider quantum channels with input dimension d1, output dimension d2 and Kraus rank at most r. Any such channel must satisfy the constraint rd2≥d1, and the parameter regime rd2=d1 is called the boundary regime. In this paper, we show an optimal query lower bound Ω(rd1d2/ε2) for quantum channel tomography to within diamond norm error ε in the away-from-boundary regime rd2≥2d1, matching the existing upper bound O(rd1d2/ε2). In particular, this lower bound fully settles the query complexity for the commonly studied case of equal input and output dimensions d1=d2=d with r≥2, in sharp contrast to the unitary case r=1 where Heisenberg scaling Θ(d2/ε) is achievable.
Quantum process tomography, the task of estimating an unknown quantum channel, is a central problem in quantum information theory. A long-standing open question is how many uses of an unknown channel are required to learn it in diamond distance, the standard metric for distinguishing quantum processes. While quantum state tomography is well understood, for general channels the problem remained open beyond the unitary case. Here we establish the query complexity of channel tomography with optimal dependence on the dimension parameters, at any fixed constant accuracy. We design an algorithm showing that any channel with input/output dimensions din,dout and Kraus rank at most k can be learned to accuracy ε using O(dindoutk/ε2) channel uses. Conversely, we prove that Ω(dindoutk) uses are necessary at constant accuracy and that, for non-minimal Kraus rank, a separate Ω(1/ε2) contribution is unavoidable. Since channels subsume states, unitaries, isometries, and measurements as special cases, our protocol provides a unified framework for these tomography tasks, yielding new guarantees for isometry and measurement tomography while recovering known optimal scalings for state and unitary tomography. Our algorithm follows the natural strategy of performing optimal tomography on the Choi state. The main technical contribution is to show that this suffices to control the induced diamond-distance error, avoiding the dimension loss incurred by a naive conversion from Choi-state trace distance to channel diamond distance. The protocol uses the channel non-adaptively to prepare Choi-state copies, purifies them in parallel, and performs optimal pure-state tomography on the resulting purifications. Hence, we reduce channel tomography to pure-state tomography.
How many black-box queries to a quantum channel are needed to learn its full classical description? This question lies at the heart of quantum channel tomography (also known as quantum process tomography), a fundamental task in the characterization and validation of quantum hardware. Despite extensive prior work, the optimal query complexity for quantum channel tomography is far from fully understood.
In this paper, we study tomography of an unknown quantum channel with input dimension d1, output dimension d2, and Kraus rank at most r, to within error ε. We identify the dilation rate τ=rd2/d1 (which always satisfies τ≥1 due to the trace preservation of quantum channels) as a key parameter, and establish that the optimal query complexity of channel tomography exhibits distinct scaling laws across three regimes of τ.
- In the boundary regime (τ=1): we show that the query complexity is Θ(rd1d2/ε) for Choi trace norm error ε, and is upper bounded by O(min{rd11.5d2/ε,rd1d2/ε2}) and lower bounded by Ω(rd1d2/ε) for diamond norm error ε.
- In the away-from-boundary regime (τ≥1+Ω(1)): we show that the query complexity is Θ(rd1d2/ε2) for both Choi trace norm and diamond norm errors ε.
Our results uncover a sharp Heisenberg-to-classical phase transition in the query complexity of quantum channel tomography: at τ=1, the optimal query complexity exhibits Heisenberg scaling 1/ε, whereas for τ≥1+Ω(1), it exhibits classical scaling 1/ε2. In addition, we show that in the near-boundary regime (1<τ<1+o(1)), the query complexity exhibits a mixture of Heisenberg and classical scaling behaviors.
Quantum process tomography, the task of learning an unknown quantum channel from black-box access, is a central problem in quantum information. In this setting, protocols with quantum memory can coherently store and jointly process quantum information obtained from multiple channel uses, whereas protocols without quantum memory must measure after each use and retain only a classical transcript of the measurement outcomes. A fundamental open question is whether quantum memory provides a query-complexity advantage even when protocols without quantum memory may adapt their experiments based on all previous outcomes with unbounded classical computational power. In this work, we show that it does. We determine the optimal query complexity of quantum process tomography without quantum memory up to a constant factor to be Θ(din3dout3/ε2), where din and dout are the channel input and output dimensions, respectively, and ε is the target diamond-norm accuracy. More precisely, we prove that any incoherent protocol for this task, including adaptive protocols, requires Ω(din3dout3/ε2) queries, even when each channel use may be assisted by arbitrary fresh ancilla, and we present a non-adaptive, ancilla-free incoherent protocol achieving the matching upper bound O(din3dout3/ε2). Our results thereby generalize the optimal sample-complexity bounds for single-copy state tomography, recovered as the special case din=1. By contrast, coherent protocols with quantum memory achieve query complexity Θ(din2dout2/ε2). Hence, our results establish a rigorous learning separation between quantum process tomography with and without quantum memory.
We study the estimation of an unknown quantum channel E with input dimension d1, output dimension d2 and Kraus rank at most r. We establish a connection between the query complexities in two models: (i) access to E, and (ii) access to a random dilation of E. Specifically, we show that for parallel (possibly coherent) testers, access to dilations does not help. This is proved by constructing a local tester that uses n queries to E yet faithfully simulates the tester with n queries to a random dilation. As application, we show that:
- O(rd1d2/ε2) queries to E suffice for channel tomography to within diamond norm error ε.
Moreover, when rd2=d1, we show that the Heisenberg scaling O(1/ε) can be achieved, even if E is not a unitary channel:
- O(min{d12.5/ε,d12/ε2}) queries to E suffice for channel tomography to within diamond norm error ε, and O(d12/ε) queries suffice for the case of Choi state trace norm error ε.
- O(min{d11.5/ε,d1/ε2}) queries to E suffice for tomography of the mixed state E(∣0⟩⟨0∣) to within trace norm error ε.
We determine the optimal sample complexity of low-rank quantum state tomography when each measurement may act jointly on at most t samples. For sufficiently small ε, estimating an unknown state on Cd of rank at most r to trace norm error ε with constant success probability requires, and is achievable with, Θ(ε2drmax{1,tr}) samples. The lower bound allows the protocol to choose each joint measurement adaptively using all previous classical outcomes; the matching upper bound is nonadaptive. Thus joint measurements on at most t samples improve the complexity of algorithms making single-sample measurements by at most a factor t. Further, measuring order r2 samples jointly is necessary and sufficient to attain the unrestricted collective rate.
For the lower bound, we vary the support of a state with fixed uniform spectrum and bound the Fisher information trace of every joint measurement on t samples. The adaptive Fisher chain rule and the van Trees inequality then give the trace norm lower bound. For the upper bound, we construct and analyze a nonadaptive tomography protocol based on a Gaussian joint measurement. An explicit second moment identity and a conditional Gaussian law outside the state's support give a rank-dependent error analysis, yielding the matching rate.