We give collective tomography protocols for quantum states and channels with known symmetries, using random purification and dilation to reduce learning to pure-state estimation. For states commuting with a compact-group representation with multiplicities $m_λ$, the optimal copy complexity is $Θ((\sum_λm_λ^2+\logη^{-1})/\varepsilon^2)$ for sufficiently small trace-distance error $\varepsilon$ and failure probability $η$ for the nontrivial case $\sum_λm_λ^2>1$. For $G$-covariant channels with finite-dimensional unitary representations of a compact group $G$, parallel $\widetilde{O}(D_G/\varepsilon^2)$ queries achieve a diamond-distance error $\varepsilon $ at fixed success probability $2/3$, where $D_G$ counts the real parameters of covariant Choi operators before imposing trace preservation. For permutation-covariant channels on $k$ qudits of fixed local dimension $d$, at sufficiently small fixed error and fixed success probability $2/3$, we obtain the optimal query scalings $Θ_d(k^{d^4-1})$ for diamond distance and $Θ_d(k^{d^4-d^2})$ for Choi trace distance. Furthermore, we resolve an open problem in quantum tomography of constructing efficient quantum circuits that approximate the Hayashi measurement for optimal pure-state estimation. We encode states in the symmetric subspace into bosonic occupation modes, realize the measurement by heterodyne detection and normalization, and approximate this procedure on qubits using the quantum Hermite transform. Combined with our symmetry-compatible purification and dilation circuits, this yields query-optimal and gate-efficient learners of permutation-covariant states and channels with gate complexity $O_d(\mathrm{poly}(k,\varepsilon^{-1},\logη^{-1}))$.
AI Summary
The paper studies how known compact-group symmetries reduce the collective resources needed for state and channel tomography, and whether the resulting measurements admit efficient quantum circuits. Its approach converts copies of an invariant state into copies of one shared random purification, and parallel channel queries into uses of one shared random covariant Stinespring isometry, then applies pure-state estimation.
For states commuting with a known representation with irrep multiplicities $m_\lambda$, it proves optimal trace-distance copy complexity $\Theta((\sum_\lambda m_\lambda^2+\log(1/\eta))/\varepsilon^2)$ for nontrivial families and sufficiently small error. For covariant channels, it obtains parallel-query complexity $\widetilde O(D_G/\varepsilon^2)$ in diamond distance at constant success probability, where $D_G$ is the covariant Choi parameter count before trace preservation. For permutation-covariant channels on $k$ qudits of fixed local dimension $d$, matching bounds at sufficiently small fixed error give $\Theta_d(k^{d^4-1})$ queries in diamond distance and $\Theta_d(k^{d^4-d^2})$ in Choi trace distance.
The constructions use wreath-product representation theory for symmetry-compatible purification and dilation. An occupation-mode encoding realizes the Hayashi measurement through heterodyne detection and normalization; quantum Hermite transforms yield a qubit approximation costing $O((t+q)\operatorname{polylog}(t,q,\tau^{-1},\zeta^{-1}))$ gates. Combined circuits give polynomial-gate learners for permutation symmetry.
General-channel optimality remains incomplete: diamond-distance bounds match up to logarithms only under a parameter-dimension condition, and general Choi-distance lower bounds remain open. The optimal diamond-distance dependence on variable target error is unresolved even for permutation covariance. Efficient implementation for arbitrary symmetries is not guaranteed.
Little sign of AI-generated textAI use disclosed
The proof of lower bounds is mainly generated by AI under instructions from human authors.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
We give collective tomography protocols for quantum states and channels with known symmetries, using random purification and dilation to reduce learning to pure-state estimation. For states commuting with a compact-group representation with multiplicities mλ, the optimal copy complexity is Θ((∑λmλ2+logη−1)/ε2) for sufficiently small trace-distance error ε and failure probability η for the nontrivial case ∑λmλ2>1. For G-covariant channels with finite-dimensional unitary representations of a compact group G, parallel O(DG/ε2) queries achieve a diamond-distance error ε at fixed success probability 2/3, where DG counts the real parameters of covariant Choi operators before imposing trace preservation. For permutation-covariant channels on k qudits of fixed local dimension d, at sufficiently small fixed error and fixed success probability 2/3, we obtain the optimal query scalings Θd(kd4−1) for diamond distance and Θd(kd4−d2) for Choi trace distance. Furthermore, we resolve an open problem in quantum tomography of constructing efficient quantum circuits that approximate the Hayashi measurement for optimal pure-state estimation. We encode states in the symmetric subspace into bosonic occupation modes, realize the measurement by heterodyne detection and normalization, and approximate this procedure on qubits using the quantum Hermite transform. Combined with our symmetry-compatible purification and dilation circuits, this yields query-optimal and gate-efficient learners of permutation-covariant states and channels with gate complexity Od(poly(k,ε−1,logη−1)).
The paper studies how known compact-group symmetries reduce the collective resources needed for state and channel tomography, and whether the resulting measurements admit efficient quantum circuits. Its approach converts copies of an invariant state into copies of one shared random purification, and parallel channel queries into uses of one shared random covariant Stinespring isometry, then applies pure-state estimation.
For states commuting with a known representation with irrep multiplicities mλ, it proves optimal trace-distance copy complexity Θ((∑λmλ2+log(1/η))/ε2) for nontrivial families and sufficiently small error. For covariant channels, it obtains parallel-query complexity O(DG/ε2) in diamond distance at constant success probability, where DG is the covariant Choi parameter count before trace preservation. For permutation-covariant channels on k qudits of fixed local dimension d, matching bounds at sufficiently small fixed error give Θd(kd4−1) queries in diamond distance and Θd(kd4−d2) in Choi trace distance.
The constructions use wreath-product representation theory for symmetry-compatible purification and dilation. An occupation-mode encoding realizes the Hayashi measurement through heterodyne detection and normalization; quantum Hermite transforms yield a qubit approximation costing O((t+q)polylog(t,q,τ−1,ζ−1)) gates. Combined circuits give polynomial-gate learners for permutation symmetry.
General-channel optimality remains incomplete: diamond-distance bounds match up to logarithms only under a parameter-dimension condition, and general Choi-distance lower bounds remain open. The optimal diamond-distance dependence on variable target error is unresolved even for permutation covariance. Efficient implementation for arbitrary symmetries is not guaranteed.
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.
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 ε.
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 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.
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.
The recently introduced random purification channel, which converts n copies of an arbitrary mixed quantum state into n copies of the same uniformly random purification, has emerged as a powerful tool in quantum information theory. Motivated by this development, we introduce a channel-level analogue, which we call the random Stinespring superchannel. This consists in a procedure to transform n parallel queries of an arbitrary quantum channel into n parallel queries of the same uniformly random Stinespring isometry, via universal encoding and decoding operations that are efficiently implementable. When the channel is promised to have Choi rank at most r, the procedure can be tailored to yield a Stinespring environment of dimension r. We present two applications of the random Stinespring superchannel, one in quantum Shannon theory and one in quantum learning theory. In quantum Shannon theory, we prove a channel-level analogue of Uhlmann's theorem for quantum divergences. In quantum learning theory, our construction shows that tomography of quantum channels reduces to tomography of isometries. This yields a simple channel learning algorithm, based on existing isometry learning protocols, that matches the performance of the two recently proposed channel tomography algorithms. Complementarily, whereas the optimality of these algorithms had previously been established only up to a logarithmic factor in the dimension, we close this gap by removing this logarithmic factor from the lower bound. Taken together, our results fully establish the optimality of these recently introduced channel learning algorithms, showing that the optimal query complexity of learning a quantum channel with input dimension dA, output dimension dB, and Choi rank r is Θ(dAdBr).