Unitary process tomography is the act of learning how an unknown unitary gate acts on a quantum system. It is an essential procedure for realizing a functioning quantum computer. As quantum technologies develop, it is important to understand the computational resources needed to conduct unitary process tomography using a variety of types of circuits. In particular, when measuring error in diamond distance, it is known how to achieve optimal query complexity using a sequential circuit architecture, but it had not been known whether a parallel circuit architecture could achieve the same optimal query complexity. In this work, we prove that unitary process tomography with near-optimal query complexity is indeed possible using a parallel circuit by introducing an explicit, novel parallel procedure. This closes the gap between sequential and parallel circuits up to a logarithmic factor, showing that parallel and sequential strategies are nearly equally capable for this task.
AI Summary
The paper asks whether fully parallel queries suffice for unitary process tomography with the query complexity achievable sequentially when error is measured in diamond distance. For an unknown $U\in\mathrm{U}(d)$, the task is to output a classical description of a unitary estimate within diamond distance $\epsilon$, with constant success probability. The known lower bound and sequential upper bound are $\Theta(d^2/\epsilon)$; previous parallel upper bounds scale as $O(d^{5/2}/\epsilon)$.
It constructs a family of parallel protocols using $O(r d^{2+1/(2r)}/\epsilon)$ queries for every positive integer $r$, with success probability at least $2/3$. Choosing $r=\Theta(\log d)$ gives $O(d^2\log d/\epsilon)$ queries. Independent parallel repetitions extend the guarantee to failure probability $\eta$ with an additional $O(\log(1/\eta))$ factor.
The construction adapts an existing covariant estimation framework: an entangled probe is specified through Schur–Weyl sectors, followed by a collective covariant POVM. The new probe uses separated Young-diagram row lengths and sine-power amplitudes. The analysis applies the Weyl integral formula to express estimation error through eigenangles, then uses Fourier transforms and finite-difference bounds to control high moments of eigenvalue separations. This yields a mean-square diamond-error bound, converted into the success guarantee by Markov’s inequality.
The result concerns query complexity rather than an implementation-cost guarantee and retains a logarithmic gap to the lower bound. A note added reports concurrent independent work achieving the exact optimal parallel scaling $O(d^2/\epsilon)$.
No sign of AI-generated text
Error found: The formula defining λ₀ makes its total size N−1 boxes too small and invalidates the appendix's stated affine parametrization, but changing its last row to (d−1)(N−1) repairs the proof without changing the protocol or query bound.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
Unitary process tomography is the act of learning how an unknown unitary gate acts on a quantum system. It is an essential procedure for realizing a functioning quantum computer. As quantum technologies develop, it is important to understand the computational resources needed to conduct unitary process tomography using a variety of types of circuits. In particular, when measuring error in diamond distance, it is known how to achieve optimal query complexity using a sequential circuit architecture, but it had not been known whether a parallel circuit architecture could achieve the same optimal query complexity. In this work, we prove that unitary process tomography with near-optimal query complexity is indeed possible using a parallel circuit by introducing an explicit, novel parallel procedure. This closes the gap between sequential and parallel circuits up to a logarithmic factor, showing that parallel and sequential strategies are nearly equally capable for this task.
The paper asks whether fully parallel queries suffice for unitary process tomography with the query complexity achievable sequentially when error is measured in diamond distance. For an unknown U∈U(d), the task is to output a classical description of a unitary estimate within diamond distance ϵ, with constant success probability. The known lower bound and sequential upper bound are Θ(d2/ϵ); previous parallel upper bounds scale as O(d5/2/ϵ).
It constructs a family of parallel protocols using O(rd2+1/(2r)/ϵ) queries for every positive integer r, with success probability at least 2/3. Choosing r=Θ(logd) gives O(d2logd/ϵ) queries. Independent parallel repetitions extend the guarantee to failure probability η with an additional O(log(1/η)) factor.
The construction adapts an existing covariant estimation framework: an entangled probe is specified through Schur–Weyl sectors, followed by a collective covariant POVM. The new probe uses separated Young-diagram row lengths and sine-power amplitudes. The analysis applies the Weyl integral formula to express estimation error through eigenangles, then uses Fourier transforms and finite-difference bounds to control high moments of eigenvalue separations. This yields a mean-square diamond-error bound, converted into the success guarantee by Markov’s inequality.
The result concerns query complexity rather than an implementation-cost guarantee and retains a logarithmic gap to the lower bound. A note added reports concurrent independent work achieving the exact optimal parallel scaling O(d2/ϵ).
In the study of quantum process tomography, it has remained open how to learn a unitary channel in diamond distance with strictly parallel queries as efficiently as with sequential queries. Sequential queries allow one to exploit adaptivity to refine the estimate and adjust the learning strategy accordingly, whereas such adjustments are impossible for parallel queries. From the perspective of higher-order quantum operations, any parallel learning strategy can be simulated by a sequential one, whereas the converse does not hold in general, suggesting that sequential learning strategies are potentially more powerful. Contrary to this intuition, we present a new protocol for learning an unknown d-dimensional unitary channel to within ε in diamond distance using O(d2/ε) parallel queries, matching the lower bound presented in [Haah, Kothari, O'Donnell, and Tang, FOCS '23]. Our protocol thus closes the gap between parallel and sequential strategies for unitary channel tomography. As applications, it achieves optimal query complexity for boundary-regime quantum channel tomography and improves the query efficiency of the best-known protocol for tomography of fermionic linear optics.
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.
Quantum channel tomography (also known as quantum process tomography) is a fundamental task in quantum information and quantum computing, aiming to learn the full description of an unknown quantum channel from black-box queries. For channels with input dimension d1, output dimension d2, and Kraus rank at most r, [CGO+26] identifies the dilation rate τ=rd2/d1≥1 as a key parameter governing a Heisenberg-to-classical transition in query complexity. While the optimal bounds in the boundary regime (τ=1) and the away-from-boundary regime (τ≥1+Ω(1)) are now known, the precise behavior in the near-boundary regime (1<τ<1+o(1)) has remained unresolved.
In this paper, we close this gap, thereby fully settling the query complexity of quantum channel tomography. Specifically, we show that the query complexity is
- Ω(rd1d2/ε2) for diamond norm error ε, matching the upper bound by [MB26, CGO+26],
- Θ(d12/ε+min{(τ−1)d12,(τ−1)2d12d22}/ε2) for Choi trace norm error ε.
Our results reveal two qualitatively different forms of the Heisenberg-to-classical transition. For diamond norm tomography, the Heisenberg scaling disappears suddenly as soon as τ leaves the boundary regime. In contrast, Choi trace norm tomography exhibits a gradual transition from Heisenberg to classical scaling as τ moves from the boundary regime to the away-from-boundary regime.
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 consider process tomography for unitary quantum channels. Given access to an unknown unitary channel acting on a d-dimensional qudit, we aim to output a classical description of a unitary that is ε-close to the unknown unitary in diamond norm. We design an algorithm achieving error ε using O(d2/ε) applications of the unknown channel and only one qudit. This improves over prior results, which use O(d3/ε2) [via standard process tomography] or O(d2.5/ε) [Yang, Renner, and Chiribella, PRL 2020] applications. To show this result, we introduce a simple technique to “bootstrap” an algorithm that can produce constant-error estimates to one that can produce ε-error estimates with the Heisenberg scaling. Finally, we prove a complementary lower bound showing that estimation requires Ω(d2/ε) applications, even with access to the inverse or controlled versions of the unknown unitary. This shows that our algorithm has both optimal query complexity and optimal space complexity.
The diamond distance between two quantum channels determines the optimal probability of distinguishing them from a single use. We give a quantum algorithm that estimates the diamond distance between two unknown d-dimensional unitary channels to within additive error ε, using O(d/ε) queries to the unitary channels and their inverses. The query complexity is optimal, as it matches the lower bound due to Jeon and Oh (npj Quantum Inf. 2026).