pith. machine review for the scientific record. sign in

arxiv: 2604.26900 · v1 · submitted 2026-04-29 · 🪐 quant-ph · cs.CC· cs.DS

Recognition: unknown

Strict Hierarchy for Quantum Channel Certification to Unitary

Kean Chen, Qisheng Wang, Zhicheng Zhang

Authors on Pith no claims yet

Pith reviewed 2026-05-07 10:31 UTC · model grok-4.3

classification 🪐 quant-ph cs.CCcs.DS
keywords quantum channel certificationunitary channelsquery complexitydiamond normincoherent accesscoherent accesssource-code accessquantum algorithms
0
0 comments X

The pith

The query complexity for certifying a quantum channel as a target unitary forms a strict hierarchy across three access models.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper determines the exact number of queries needed to test if an unknown quantum channel matches a given unitary channel or is far from it. In the weakest access model, where each use of the channel is separate, about d over epsilon squared queries are required. With coherent access, allowing joint operations on multiple uses, the number drops to d over epsilon. The strongest model, source-code access, needs only square root of d over epsilon. These bounds are tight and show how more powerful access reduces the testing cost.

Core claim

The authors present optimal quantum algorithms for certifying whether a d-dimensional quantum channel is exactly a target unitary or ε-far from it in diamond norm. For incoherent access we achieve Θ(d/ε²) queries, for coherent access Θ(d/ε), and for source-code access Θ(√d/ε), each matching the corresponding lower bounds from prior work. This establishes a strict hierarchy in the query complexities depending on the power of the access model.

What carries the argument

Optimal algorithms achieving the tight query bounds for diamond-norm certification to unitary channels under incoherent, coherent, and source-code access models.

If this is right

  • Incoherent access requires quadratically more queries than coherent access.
  • Source-code access provides a square-root improvement over coherent access.
  • The query complexities are fully settled with matching upper and lower bounds in each model.
  • The results hold specifically for exact unitary targets under the diamond norm.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • More powerful access models can substantially lower the resources needed for quantum channel testing.
  • Similar strict hierarchies may exist in other quantum property testing problems.
  • The source-code model could be implemented in specific quantum hardware setups.

Load-bearing premise

The results depend on measuring distance with the diamond norm and requiring the channel to be exactly a unitary.

What would settle it

An algorithm achieving the certification task with asymptotically fewer queries than the stated bound in any of the three access models would falsify the optimality claim.

read the original abstract

We consider the problem of quantum channel certification to unitary, where one is given access to an unknown $d$-dimensional channel $\mathcal{E}$, and wants to test whether $\mathcal{E}$ is equal to a target unitary channel or is $\varepsilon$-far from it in the diamond norm. We present optimal quantum algorithms for this problem, settling the query complexities in three access models with increasing power. Specifically, we show that: (i) $\Theta(d/\varepsilon^2)$ queries suffice for incoherent access model, matching the lower bound due to Fawzi, Flammarion, Garivier, and Oufkir (COLT 2023). (ii) $\Theta(d/\varepsilon)$ queries suffice for coherent access model, matching the lower bound due to Regev and Schiff (ICALP 2008). (iii) $\Theta(\sqrt{d}/\varepsilon)$ queries suffice for source-code access model, matching the lower bound due to Jeon and Oh (npj Quantum Inf. 2026). This demonstrates a strict hierarchy of complexities for quantum channel certification to unitary across various access models.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript considers the problem of certifying whether an unknown d-dimensional quantum channel E is exactly equal to a known target unitary channel or is ε-far from it in diamond norm. It presents explicit algorithms achieving query complexities Θ(d/ε²) in the incoherent access model (matching Fawzi et al., COLT 2023), Θ(d/ε) in the coherent access model (matching Regev and Schiff, ICALP 2008), and Θ(√d/ε) in the source-code access model (matching Jeon and Oh, npj Quantum Inf. 2026), thereby establishing a strict hierarchy across these oracles.

Significance. If the constructions and analyses hold, the work is significant because it settles the query complexity of unitary channel certification in each standard access model by supplying matching upper bounds via explicit algorithms. This provides a clean separation of power between the three oracle models and directly complements the cited lower bounds without circularity or parameter fitting. The results use the standard diamond norm and exact unitary target, strengthening the literature on quantum channel testing.

minor comments (2)
  1. [Abstract] Abstract: the three access models are named but not briefly defined or contrasted; adding one sentence per model would improve accessibility for readers outside the immediate subfield.
  2. The paper cites lower bounds from 2023, 2008, and 2026; confirm that the 2026 reference is correctly formatted and that all cited works are properly referenced in the bibliography.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, recognition of the significance of establishing matching upper bounds that settle the query complexities in each access model, and recommendation to accept the manuscript.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper establishes upper bounds via explicit algorithm constructions for the three access models (incoherent, coherent, source-code), which are independent of the external lower-bound citations (Fawzi et al. COLT 2023, Regev and Schiff ICALP 2008, Jeon and Oh npj Quantum Inf. 2026). These citations provide matching lower bounds but do not form a self-citation chain or load-bearing premise; the central claim of a strict hierarchy rests on the differing oracle powers and standard diamond-norm analysis, with no reduction of any prediction or result to a fitted parameter, self-definition, or ansatz smuggled via prior author work. The derivation is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, axioms beyond standard quantum mechanics, or invented entities are introduced; the work operates entirely within the established framework of quantum query complexity and diamond-norm distance.

pith-pipeline@v0.9.0 · 5498 in / 1138 out tokens · 40209 ms · 2026-05-07T10:31:03.929645+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

35 extracted references · 32 canonical work pages · 3 internal anchors

  1. [1]

    Quantum algorithmic measurement

    Dorit Aharonov, Jordan Cotler, and Xiao-Liang Qi. Quantum algorithmic measurement. Nature Communications , 13(1):887, 2022. https://doi.org/10.1038/s41467-021-27922-0 doi:10.1038/s41467-021-27922-0

    work page doi:10.1038/s41467-021-27922-0 2022

  2. [2]

    Entanglement is necessary for optimal quantum property testing

    Sebastien Bubeck, Sitan Chen, and Jerry Li. Entanglement is necessary for optimal quantum property testing. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages 692--703. IEEE, 2020. https://doi.org/10.1109/FOCS46700.2020.00070 doi:10.1109/FOCS46700.2020.00070

    work page doi:10.1109/focs46700.2020.00070 2020

  3. [3]

    In: Samuel J

    Gilles Brassard, Peter H yer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. In Samuel J. Lomonaco, Jr. and Howard E. Brandt, editors, Quantum Computation and Information , volume 305 of Contemporary Mathematics , pages 53--74. AMS, 2002. https://doi.org/10.1090/conm/305/05215 doi:10.1090/conm/305/05215

    work page doi:10.1090/conm/305/05215 2002

  4. [4]

    VC dimension and distribution-free sample-based testing

    Costin B a descu and Ryan O'Donnell. Improved quantum data analysis. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages 1398--1411, 2021. https://doi.org/10.1145/3406325.3451109 doi:10.1145/3406325.3451109

    work page doi:10.1145/3406325.3451109 2021

  5. [5]

    Quantum state certification

    Costin B a descu, Ryan O'Donnell, and John Wright. Quantum state certification. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages 503--514, 2019. https://doi.org/10.1145/3313276.3316344 doi:10.1145/3313276.3316344

    work page doi:10.1145/3313276.3316344 2019

  6. [6]

    The hardest explicit construction

    Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li. Exponential separations between learning with and without quantum memory. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) , pages 574--585. IEEE, 2022. https://doi.org/10.1109/FOCS52979.2021.00063 doi:10.1109/FOCS52979.2021.00063

    work page doi:10.1109/focs52979.2021.00063 2021

  7. [7]

    Polylogarithmic-time deterministic net- work decomposition and distributed derandomization

    Sitan Chen, Jerry Li, Brice Huang, and Allen Liu. Tight bounds for quantum state certification with incoherent measurements. In Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science , pages 1205--1213, 2022. https://doi.org/10.1109/FOCS54457.2022.00118 doi:10.1109/FOCS54457.2022.00118

    work page doi:10.1109/focs54457.2022.00118 2022

  8. [8]

    Toward instance-optimal state certification with incoherent measurements

    Sitan Chen, Jerry Li, and Ryan O'Donnell. Toward instance-optimal state certification with incoherent measurements. In Conference on Learning Theory , pages 2541--2596. PMLR, 2022. URL: https://proceedings.mlr.press/v178/chen22b.html

    2022

  9. [9]

    Unitarity estimation for quantum channels

    Kean Chen, Qisheng Wang, Peixun Long, and Mingsheng Ying. Unitarity estimation for quantum channels. IEEE Transactions on Information Theory , 69(8):5116--5134, 2023. https://doi.org/10.1109/TIT.2023.3263645 doi:10.1109/TIT.2023.3263645

    work page doi:10.1109/tit.2023.3263645 2023

  10. [10]

    Local test for unitarily invariant properties of bipartite quantum states

    Kean Chen, Qisheng Wang, and Zhicheng Zhang. Local test for unitarily invariant properties of bipartite quantum states. ArXiv e-prints, 2024. https://arxiv.org/abs/2404.04599 arXiv:2404.04599

    work page arXiv 2024

  11. [11]

    Quantum channel tomography and estimation by local test

    Kean Chen, Nengkun Yu, and Zhicheng Zhang. Quantum channel tomography and estimation by local test. ArXiv e-prints, 2025. https://arxiv.org/abs/2512.13614 arXiv:2512.13614

    work page arXiv 2025

  12. [12]

    Quantum channel certification with incoherent measurements

    Omar Fawzi, Nicolas Flammarion, Aur \' e lien Garivier, and Aadil Oufkir. Quantum channel certification with incoherent measurements. In Proceedings of the 36th Conference on Learning Theory , pages 1822--1884, 2023. URL: https://proceedings.mlr.press/v195/fawzi23a.html

    2023

  13. [13]

    Quantum Hamiltonian certification

    Minbo Gao, Zhengfeng Ji, Qisheng Wang, Wenjun Yu, and Qi Zhao. Quantum Hamiltonian certification. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1424--1467, 2026. https://doi.org/10.1137/1.9781611978971.53 doi:10.1137/1.9781611978971.53

    work page doi:10.1137/1.9781611978971.53 2026

  14. [14]

    de Rezende, Aaron Potechin, and Kilian Risse

    Jeongwan Haah, Robin Kothari, Ryan O'Donnell, and Ewin Tang. Query-optimal estimation of unitary channels in diamond distance. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages 363--390. IEEE, 2023. https://doi.org/10.1109/FOCS57990.2023.00028 doi:10.1109/FOCS57990.2023.00028

    work page doi:10.1109/focs57990.2023.00028 2023

  15. [15]

    Huang, R

    Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. Nature Physics , 16(10):1050--1057, 2020. https://doi.org/10.1038/s41567-020-0932-7 doi:10.1038/s41567-020-0932-7

    work page doi:10.1038/s41567-020-0932-7 2020

  16. [16]

    Information-theoretic bounds on quantum advantage in machine learning

    Hsin-Yuan Huang, Richard Kueng, and John Preskill. Information-theoretic bounds on quantum advantage in machine learning. Physical Review Letters , 126(19):190505, 2021. https://doi.org/10.1103/PhysRevLett.126.190505 doi:10.1103/PhysRevLett.126.190505

    work page doi:10.1103/physrevlett.126.190505 2021

  17. [17]

    On the query complexity of unitary channel certification

    Sangwoo Jeon and Changhun Oh. On the query complexity of unitary channel certification. npj Quantum Information , 12:2, 2026. https://doi.org/10.1038/s41534-025-01135-5 doi:10.1038/s41534-025-01135-5

    work page doi:10.1038/s41534-025-01135-5 2026

  18. [18]

    Mean estimation when you have the source code; or, quantum Monte Carlo methods

    Robin Kothari and Ryan O'Donnell. Mean estimation when you have the source code; or, quantum Monte Carlo methods. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1186--1215. SIAM, 2023. https://doi.org/10.1137/1.9781611977554.ch44 doi:10.1137/1.9781611977554.ch44

    work page doi:10.1137/1.9781611977554.ch44 2023

  19. [19]

    Dennis Kretschmann, Dirk Schlingemann, and Reinhard F. Werner. The information-disturbance tradeoff and the continuity of Stinespring's representation. IEEE Transactions on Information Theory , 54(4):1708--1717, 2008. https://doi.org/10.1109/TIT.2008.917696 doi:10.1109/TIT.2008.917696

    work page doi:10.1109/tit.2008.917696 2008

  20. [20]

    Optimal certification of constant-local hamiltonians.arXiv:2512.09778, 2025

    Junseo Lee and Myeongjin Shin. Optimal certification of constant-local Hamiltonians . ArXiv e-prints, 2025. https://arxiv.org/abs/2512.09778 arXiv:2512.09778

    work page arXiv 2025

  21. [21]

    Optimal learning of quantum channels in diamond distance

    Antonio Anna Mele and Lennart Bittel. Optimal learning of quantum channels in diamond distance. ArXiv e-prints, 2025. https://arxiv.org/abs/2512.10214 arXiv:2512.10214

    work page arXiv 2025

  22. [22]

    A Survey of Quantum Property Testing , year =

    Ashley Montanaro and Ronald de Wolf. A survey of quantum property testing. In Theory of Computing Library , number 7 in Graduate Surveys, pages 1--81. University of Chicago, 2016. https://doi.org/10.4086/toc.gs.2016.007 doi:10.4086/toc.gs.2016.007

    work page doi:10.4086/toc.gs.2016.007 2016

  23. [23]

    Michael A. Nielsen. A simple formula for the average gate fidelity of a quantum dynamical operation. Physics Letters A , 303(4):249--252, 2002. https://doi.org/10.1016/S0375-9601(02)01272-0 doi:10.1016/S0375-9601(02)01272-0

    work page doi:10.1016/s0375-9601(02)01272-0 2002

  24. [24]

    On Adaptivity in Classical and Quantum Learning

    Aadil Oufkir. On Adaptivity in Classical and Quantum Learning . PhD thesis, Ecole normale sup \'e rieure de lyon-ENS LYON, 2023. URL: https://theses.hal.science/tel-04210763/

    2023

  25. [25]

    Sample-optimal quantum process tomography with non-adaptive incoherent measurements

    Aadil Oufkir. Sample-optimal quantum process tomography with non-adaptive incoherent measurements. In 2023 IEEE International Symposium on Information Theory (ISIT) , pages 1919--1924, June 2023. https://doi.org/10.1109/ISIT54713.2023.10206538 doi:10.1109/ISIT54713.2023.10206538

    work page doi:10.1109/isit54713.2023.10206538 2023

  26. [26]

    Quantum spectrum testing

    Ryan O'Donnell and John Wright. Quantum spectrum testing. Communications in Mathematical Physics , 387(1):1--75, 2021. https://doi.org/10.1007/s00220-021-04180-1 doi:10.1007/s00220-021-04180-1

    work page doi:10.1007/s00220-021-04180-1 2021

  27. [27]

    A fidelity measure for quantum channels

    Maxim Raginsky. A fidelity measure for quantum channels. Physics Letters A , 290(1-2):11--18, 2001. https://doi.org/10.1016/S0375-9601(01)00640-5 doi:10.1016/S0375-9601(01)00640-5

    work page doi:10.1016/s0375-9601(01)00640-5 2001

  28. [28]

    Quantum channel testing in average-case distance

    Gregory Rosenthal, Hugo Aaronson, Sathyawageeswar Subramanian, Animesh Datta, and Tom Gur. Quantum channel testing in average-case distance. ArXiv e-prints, 2024. https://arxiv.org/abs/2409.12566 arXiv:2409.12566

    work page arXiv 2024

  29. [29]

    Impossibility of a quantum speed-up with a faulty oracle

    Oded Regev and Liron Schiff. Impossibility of a quantum speed-up with a faulty oracle. In Proceedings of 35th International Colloquium on Automata, Languages and Programming , pages 773--781, 2008. https://doi.org/10.1007/978-3-540-70575-8_63 doi:10.1007/978-3-540-70575-8_63

    work page doi:10.1007/978-3-540-70575-8_63 2008

  30. [30]

    Projected least-squares quantum process tomography

    Trystan Surawy-Stepney, Jonas Kahn, Richard Kueng, and Madalin Guta. Projected least-squares quantum process tomography. Quantum , 6:844, 2022. https://doi.org/10.22331/q-2022-10-20-844 doi:10.22331/q-2022-10-20-844

    work page doi:10.22331/q-2022-10-20-844 2022

  31. [31]

    Amplitude amplification and estimation require inverses

    Ewin Tang and John Wright. Amplitude amplification and estimation require inverses. ArXiv e-prints, 2025. https://arxiv.org/abs/2507.23787 arXiv:2507.23787

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  32. [32]

    Conjugate queries can help

    Ewin Tang, John Wright, and Mark Zhandry. Conjugate queries can help. ArXiv e-prints, 2025. https://arxiv.org/abs/2510.07622 arXiv:2510.07622

    work page internal anchor Pith review arXiv 2025

  33. [33]

    Optimal trace distance and fidelity estimations for pure quantum states

    Qisheng Wang. Optimal trace distance and fidelity estimations for pure quantum states. IEEE Transactions on Information Theory , 70(12):8791--8805, 2024. https://doi.org/10.1109/TIT.2024.3447915 doi:10.1109/TIT.2024.3447915

    work page doi:10.1109/tit.2024.3447915 2024

  34. [34]

    Watrous.The Theory of Quantum Information

    John Watrous. The Theory of Quantum Information . Cambridge University Press, 2018. https://doi.org/10.1017/9781316848142 doi:10.1017/9781316848142

    work page doi:10.1017/9781316848142 2018

  35. [35]

    Quantum Advantage in Storage and Retrieval of Isometry Channels

    Satoshi Yoshida, Jisho Miyazaki, and Mio Murao. Quantum advantage in storage and retrieval of isometry channels. ArXiv e-prints, 2025. https://arxiv.org/abs/2507.10784 arXiv:2507.10784

    work page internal anchor Pith review Pith/arXiv arXiv 2025