Quantum channel tomography: optimal bounds and a Heisenberg-to-classical phase transition

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 d₁, output dimension d₂, and Kraus rank at most r, to within error varepsilon. We identify the dilation rate τ= r d₂ / d₁ which always satisfies $τgeq 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 Θ\(r d₁ d₂/varepsilon\) for Choi trace norm error varepsilon, and is upper bounded by O\(min\{r d₁^1.5 d₂/varepsilon, r d₁ d₂/varepsilon²\}\) and lower bounded by Ω\(r d₁ d₂/varepsilon\) for diamond norm error varepsilon. - In the away-from-boundary regime $τgeq 1+Ω(1): we show that the query complexity isΘr d₁ d₂/varepsilon²for both Choi trace norm and diamond norm errors\varepsilon. 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 scaling1/\varepsilon, whereas forτ\geq 1+Ω(1), it exhibits classical scaling1/\varepsilon^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.