Quantum channel tomography: optimal bounds and a Heisenberg-to-classical phase transition
Kean Chen, Filippo Girardi, Aadil Oufkir, Nengkun Yu, Zhicheng Zhang
Abstract
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 , output dimension , and Kraus rank at most , to within error . We identify the dilation rate (which always satisfies 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 (): we show that the query complexity is for Choi trace norm error , and is upper bounded by and lower bounded by for diamond norm error . - In the away-from-boundary regime (): we show that the query complexity is 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 , the optimal query complexity exhibits Heisenberg scaling , whereas for , it exhibits classical scaling . In addition, we show that in the near-boundary regime (), the query complexity exhibits a mixture of Heisenberg and classical scaling behaviors.
AI Impact Assessments
(3 models)Scientific Impact Assessment
Core Contribution
This paper resolves a fundamental open question in quantum channel tomography: when does the optimal query complexity exhibit Heisenberg scaling (1/ε) versus classical scaling (1/ε²)? The authors identify the dilation rate τ = rd₂/d₁ as the key parameter governing this transition and establish three distinct regimes:
1. Boundary regime (τ = 1): Θ(rd₁d₂/ε) for Choi trace norm, with near-matching bounds for diamond norm.
2. Away-from-boundary regime (τ ≥ 1 + Ω(1)): Θ(rd₁d₂/ε²) for both norms — tight in all parameters.
3. Near-boundary regime (1 < τ < 1 + o(1)): Mixed scaling with new upper and lower bounds.
The phase transition is sharp: Heisenberg scaling is achievable only when τ = 1 (corresponding to unitary channels when d₁ = d₂), and even an infinitesimal departure from τ = 1 (independent of ε) forces classical scaling. This cleanly answers Question 1.1 posed in the paper.
Methodological Rigor
Upper bounds: The key technical contribution is Theorem 3.1 ("local test for quantum channels"), which shows that any parallel tester querying a Stinespring dilation can be simulated by a parallel tester querying the channel itself. This is proved using representation-theoretic tools (Schur-Weyl duality on bipartite systems) combined with the quantum comb formalism. The construction (Equations 9-10) is explicit and the proof is detailed. This reduces general channel tomography to isometry tomography, enabling reuse of existing algorithms (Yang-Renner-Chiribella, Haah-Kothari-O'Donnell-Tang, Yoshida-Miyazaki-Murao).
Lower bounds: The two-stage proof strategy is sophisticated and novel. First, carefully constructed packing nets of quantum channels are built via perturbative constructions around a center map V₀ + ε∆ (Figure 2). The critical insight is that in the non-boundary regime, V₀ and ∆ have orthogonal images, enabling classical-scaling lower bounds, while at the boundary, this orthogonality is impossible, yielding only Heisenberg-scaling bounds. Second, hardness of discriminating structured isometry families is established via the quantum comb framework, using a universal upper bound on |V⟩⟩⟨⟨V|^⊗n through Haar averaging. The cardinality of packing nets is established through concentration of measure arguments, and the proofs carefully track all dimension-dependent constants.
The paper handles multiple sub-cases (Sections 5.1-5.4) based on parameter relationships, which is technically demanding but necessary for completeness. The constants throughout are explicit, though large.
Potential Impact
1. Practical relevance: Quantum process tomography is essential for characterizing quantum hardware. Knowing the exact query complexity tells experimentalists the fundamental cost of channel characterization and when Heisenberg-limited precision is achievable.
2. Conceptual significance: The identification of τ as the governing parameter and the sharp phase transition provides deep structural insight. The result that *any* departure from τ = 1 destroys Heisenberg scaling is a fundamental no-go result.
3. Unifying framework: As special cases, the results recover optimal bounds for quantum state tomography (d₁ = 1, recovering [SSW25]), unitary channel tomography (d₁ = d₂, r = 1, recovering [HKOT23]), and provide the complete characterization for d-dimensional channels (Corollary 1.3).
4. Technical tools with broader applicability: The "dilation does not help" theorem (Theorem 1.5) partially answers a conjecture by Tang-Wright-Zhandry and could find applications in other quantum learning tasks. The local test technique and packing net constructions are reusable methodological contributions.
Timeliness & Relevance
This work addresses a central open problem at the intersection of quantum information theory and quantum learning theory, an area of intense current activity. It subsumes and significantly extends three prior preprints by subsets of the authors, providing a unified and comprehensive treatment. The concurrent independent work of Mele-Bittel [MB25] obtained the same O(rd₁d₂/ε²) upper bound but through different methods and with weaker lower bounds, underscoring the timeliness.
Strengths
Limitations
Overall Assessment
This is a major contribution to quantum information theory that resolves a fundamental open question about the query complexity of quantum channel tomography. The identification of a sharp Heisenberg-to-classical phase transition, the near-complete characterization across parameter regimes, and the novel technical machinery make this a landmark paper in quantum learning theory.
Generated Apr 21, 2026
Comparison History (31)
Paper 2 resolves a fundamental open question in quantum channel tomography by establishing optimal query complexity bounds and discovering a sharp Heisenberg-to-classical phase transition governed by the dilation rate parameter. This result has broad implications across quantum information theory, quantum computing validation, and quantum metrology. The identification of distinct scaling regimes and phase transitions provides deep theoretical insight applicable to practical quantum hardware characterization. Paper 1 makes a solid incremental contribution to hybrid CV-DV error correction but addresses a more specialized problem with narrower impact.
Paper 1 addresses a fundamental question in quantum information theory—optimal query complexity for quantum channel tomography—and establishes tight bounds revealing a novel Heisenberg-to-classical phase transition. This provides deep theoretical insight with broad implications for quantum computing, error characterization, and benchmarking. The mathematical rigor and completeness of the results (matching upper/lower bounds across multiple regimes) represent a major advance. Paper 2 presents an interesting but more niche contribution—a quantum graph embedding method—that is largely empirical and incremental, with practical limitations tied to current hardware constraints.
Paper 1 provides fundamental bounds and identifies a novel phase transition in quantum channel tomography, directly impacting the practical characterization and validation of near-term quantum hardware. In contrast, Paper 2 explores experimental signatures in relativistic Bohmian mechanics that imply superluminal signaling, which remains highly speculative and outside mainstream physics consensus. Thus, Paper 1 offers significantly higher practical application, methodological rigor, and relevance to the rapidly growing field of quantum computing.
Paper 2 establishes fundamental optimal bounds for quantum channel tomography and discovers a sharp Heisenberg-to-classical phase transition in query complexity, which is a deep theoretical result with broad implications across quantum information science, quantum computing validation, and complexity theory. The identification of the dilation rate as a key parameter and the tight bounds across multiple regimes represent a significant advance in a foundational problem. Paper 1, while solid, is more incremental—studying random state generation in a specific platform (Rydberg arrays) with primarily numerical results. Paper 2's results are more general, mathematically rigorous, and likely to influence a wider range of future research.
Paper 1 provides fundamental theoretical bounds and uncovers a novel phase transition in quantum channel tomography, a core task in quantum hardware validation. Its rigorous mathematical approach and discovery of Heisenberg-to-classical scaling transitions offer deeper, broader foundational impact across quantum information science compared to the more specialized, application-focused VQE resource scaling study in Paper 2.
Paper 2 establishes fundamental, optimal complexity bounds for quantum channel tomography—a core task in quantum computing characterization—and discovers a novel Heisenberg-to-classical phase transition governed by the dilation rate. This result has broad implications across quantum information theory, quantum computing benchmarking, and complexity theory. Its mathematical rigor (tight bounds across multiple regimes) and conceptual novelty (identifying the phase transition) give it high impact. Paper 1 proposes designs for quantum interconnects, which is valuable but more incremental and narrower in scope, addressing an engineering challenge rather than uncovering a fundamental theoretical insight.
Paper 2 likely has higher scientific impact due to its broadly applicable, near-fundamental characterization of optimal query complexity for quantum channel tomography, including a clear phase transition (Heisenberg 1/ε to classical 1/ε²) across regimes. This directly informs experimental design, benchmarking, and resource estimates for quantum hardware validation, affecting multiple subfields (tomography, metrology, complexity, quantum information). Paper 1 is highly novel and important for quantum circuit complexity, but its impact is more specialized and contingent on resolving major open problems (e.g., PARITY in QAC0) rather than providing immediately actionable optimal bounds.
Paper 1 extends the highly influential classical shadow framework, which is critical for efficient quantum state characterization. By providing a unified theory for arbitrary group representations, it opens doors to novel, optimized measurement protocols with direct applications in near-term quantum hardware. While Paper 2 offers deep fundamental insights into quantum channel tomography, Paper 1's methodology is likely to see broader and more immediate adoption across both theoretical and experimental quantum computing.
Paper 1 addresses a fundamental bottleneck in quantum computing—quantum channel tomography—by establishing optimal query complexity bounds and discovering a novel Heisenberg-to-classical phase transition. Its foundational theoretical results have broad implications for quantum hardware characterization across various platforms. Paper 2 presents valuable theoretical work on phonon lasing for trapped ions with strong sensing applications, but its impact is more narrowly focused on a specific experimental platform compared to the foundational and broadly applicable complexity bounds established in Paper 1.
Paper 2 has higher likely impact: it delivers broadly applicable, near-fundamental bounds on the optimal query complexity of quantum channel tomography, identifies a unifying parameter (dilation rate τ), and uncovers a sharp Heisenberg-to-classical phase transition with regime-dependent optimal scalings. These results are methodologically rigorous (information-theoretic upper/lower bounds) and immediately relevant to benchmarking and validating quantum hardware across platforms. Paper 1 is innovative but more niche, numerically demonstrated only up to 6 qubits, and its scalability limits temper near-term breadth and impact.
Paper 2 likely has higher impact: it resolves core optimality questions in quantum channel/process tomography with sharp query-complexity bounds across regimes, identifying a new “dilation rate” parameter and a Heisenberg-to-classical phase transition. This is methodologically rigorous (matching upper/lower bounds), timely for near-term quantum hardware validation, and broadly relevant to quantum information, algorithms, metrology, and experimental characterization. Paper 1 is conceptually novel for classical–quantum dynamics and gravity-motivated interpretations, but its real-world applicability and breadth are narrower and more interpretational, with impact contingent on future experimental contexts.
Paper 1 demonstrates a surprising and fundamental result—that Hamiltonian dynamics can emerge from pure dissipation—with broad implications spanning quantum complexity theory (BQP-completeness), quantum simulation, the quantum Zeno effect, and foundational understanding of open vs. closed quantum systems. Its multiple corollaries touch diverse subfields. Paper 2 provides important optimal bounds for channel tomography with an elegant phase transition, but addresses a more specific technical question. Paper 1's conceptual novelty and breadth of implications give it higher potential impact.
Paper 1 combines novel machine learning techniques (differentiable physics) with quantum state engineering to solve a longstanding clinical challenge in neuroimaging. Its immediate real-world medical applications and potential to revolutionize clinical diagnostics give it broader and more immediate cross-disciplinary impact compared to the strictly theoretical quantum complexity bounds in Paper 2.
Paper 2 likely has higher impact due to its direct implications for scalable fault-tolerant quantum computing: it co-designs ultra-high-rate QLDPC codes with a concrete, timely hardware platform (reconfigurable neutral-atom arrays), provides implementability constraints, and reports strong circuit-level performance approaching teraquop targets at realistic physical error rates. This combination of theory, architecture-aware design, and performance evidence suggests near-term applicability and broad relevance to quantum hardware and error-correction communities. Paper 1 is highly rigorous and novel in complexity theory for tomography, but its applications are more indirect and narrower.
Paper 1 makes fundamental contributions to quantum information theory by establishing optimal query complexity bounds for quantum channel tomography and discovering a sharp Heisenberg-to-classical phase transition. This addresses a core open problem with rigorous mathematical proofs and has broad implications for quantum hardware characterization. Paper 2 proposes a quantum SAT solver with an O(1) expected complexity claim over random Boolean functions, but this result is less impactful since random instances are typically easy anyway; the worst case remains exponential, limiting practical significance. Paper 1's methodological depth and foundational nature give it substantially higher impact.
Paper 1 presents novel theoretical results establishing optimal query complexity bounds for quantum channel tomography and discovers a previously unknown Heisenberg-to-classical phase transition. This is a fundamental contribution to quantum information science with implications for quantum hardware characterization. Paper 2 is a review article summarizing existing work on single-photon detectors using low-dimensional platforms. While useful, reviews synthesize known knowledge rather than generating new findings. Paper 1's rigorous mathematical results and discovery of a sharp phase transition represent a more significant original scientific contribution with broad theoretical impact.
Paper 2 establishes fundamental, optimal complexity bounds for quantum channel tomography—a core primitive in quantum information science—and discovers a novel Heisenberg-to-classical phase transition governed by the dilation rate. This result is broadly impactful across quantum computing, information theory, and complexity theory, providing tight theoretical limits relevant to all quantum hardware characterization. Paper 1 makes solid engineering contributions to quantum repeater design using GKP codes, but its impact is more narrowly focused on quantum communication protocols. Paper 2's identification of a sharp phase transition and optimal bounds represents a deeper theoretical advance with wider applicability.
Paper 2 likely has higher scientific impact due to clearer near-term real-world applicability: it targets chemically accurate quantum chemistry via QPE with concrete end-to-end resource estimates on a modern FTQC architecture and proposes an optimization (unitary weight concentration) that could materially reduce costs. Its results are timely for early fault-tolerant roadmaps and relevant to chemistry, materials, and quantum computing. Paper 1 is highly novel and rigorous in quantum information theory, but its impact is more foundational and narrower to tomography/query-complexity theory with less immediate application pull.
Paper 1 establishes fundamental theoretical bounds and uncovers a novel phase transition in quantum channel tomography, a core problem in quantum information. Its rigorous mathematical results provide deep insights into the ultimate limits of quantum hardware characterization, offering broader and more lasting foundational impact than the heuristic algorithmic improvements for specific mappings presented in Paper 2.
Paper 1 is more likely to have higher scientific impact: it delivers near-optimal query-complexity bounds and identifies a sharp Heisenberg-to-classical scaling phase transition, a fundamental theoretical advance with clear relevance to benchmarking and validating quantum hardware. The results are broadly applicable across quantum information, learning theory, and metrology, and are timely given rapid growth in quantum devices. Paper 2 is a useful cross-disciplinary methodological transfer (recurrence analysis) with potential for data-driven diagnostics, but it is demonstrated on a canonical model and may be viewed as less foundational and less broadly transformative than tight complexity-theoretic limits.