pith. sign in

arxiv: 2606.08784 · v1 · pith:IZ3GT5OPnew · submitted 2026-06-07 · 🪐 quant-ph

Randomized simulation of quantum channels using small ancilla

Marcin Kotowski , Micha{\l} Kotowski This is my paper

Pith reviewed 2026-06-27 18:13 UTC · model grok-4.3

classification 🪐 quant-ph
keywords quantum channelsancilla simulationunital channelsrandomized protocolsmatrix concentration inequalitiesquantum information theorynoncommutative Khintchine inequalities
0
0 comments X

The pith

Any unital quantum channel on d dimensions admits exact simulation with ancilla dimension k at success probability Omega(k / log d).

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

The paper shows that every unital channel, which leaves the maximally mixed state invariant, can be realized exactly by a probabilistic protocol that draws on a k-dimensional ancilla, succeeds with probability at least a constant times k over log d, and otherwise flags failure. For an n-qubit system this means any such channel can be simulated at constant success rate with only O(log n) ancillary qubits. The same scaling is shown to be necessary for some families of channels. Channels whose Kraus operators are highly noncommutative, including generic random channels, can be handled at constant success probability with a single ancillary qubit.

Core claim

Any unital channel on a d-dimensional system can be simulated with ancilla dimension k and success probability Omega(k / log d). Equivalently, every unital channel on n qubits can be simulated with constant success probability using only O(log n) ancillary qubits. The tradeoff is optimal: there exist channels for which no protocol achieves better than O(k / log d) success probability. Highly noncommutative channels admit constant-success simulation with a single ancillary qubit. The model necessarily fails for strongly non-unital channels.

What carries the argument

A non-adaptive partition-based protocol that uses classical randomization over partitions of the ancilla space together with postselection on a success flag, implemented via matrix concentration inequalities including refined noncommutative Khintchine bounds.

If this is right

  • Constant-success simulation of any n-qubit unital channel requires only O(log n) ancillary qubits.
  • A family of unital channels exists whose simulation success probability is bounded above by O(k / log d) for every protocol.
  • Highly noncommutative channels, including random channels, admit constant-success simulation with one ancillary qubit.
  • The simulation model cannot succeed for strongly non-unital channels without further modifications such as adaptivity.

Where Pith is reading between the lines

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

  • The amount of ancilla needed is governed by the degree of noncommutativity among the channel's Kraus operators rather than by the dimension alone.
  • Adaptive protocols that allow measurement outcomes to select later operations might extend the method to a larger class of channels.
  • Resource estimates for fault-tolerant quantum computation that rely on channel simulation can replace large ancilla overheads with logarithmic ones when the target operations are unital.

Load-bearing premise

The target channel must preserve the maximally mixed state and the protocol must remain non-adaptive with only classical randomness and postselection.

What would settle it

A single unital channel on d dimensions for which every non-adaptive protocol with ancilla k succeeds with probability o(k / log d), or a strongly non-unital channel that admits constant-success simulation under the same protocol.

read the original abstract

We study the problem of implementing a quantum channel using a small ancilla with classical randomization and postselection on an output failure flag. The simulation is probabilistic, but exact conditioned on success. We prove that any unital channel on a $d$-dimensional system can be simulated with ancilla dimension $k$ and success probability $\Omega(\frac{k}{\log d})$. Equivalently, every unital channel on $n$ qubits can be simulated with constant success probability using only $O(\log n)$ ancillary qubits. We show that this tradeoff is best possible by constructing a family of channels which cannot be simulated with success probability better than $O(\frac{k}{\log d})$. We also show that the class of \textit{highly noncommutative} channels, which includes random channels, admits constant-success simulation with just a single ancillary qubit. We further show that this model of simulation necessarily fails for strongly non-unital channels and discuss possible extensions involving adaptivity. On the technical side we rely on a partition-based protocol and matrix concentration inequalities, including the recent refinement of noncommutative Khintchine inequalities due to Bandeira, Boedihardjo and van Handel.

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 / 3 minor

Summary. The paper claims that any unital quantum channel on a d-dimensional system can be exactly simulated (conditioned on success) via a non-adaptive partition-based protocol with classical randomization and postselection, achieving success probability Ω(k / log d) for ancilla dimension k. Equivalently, n-qubit unital channels admit constant-success simulation with O(log n) ancilla qubits. The bound is shown to be tight by an explicit family of channels achieving at most O(k / log d). Highly noncommutative channels (including random ones) admit constant-success simulation with a single ancilla qubit. The model necessarily fails for strongly non-unital channels. Proofs rely on a partition protocol combined with matrix concentration inequalities, specifically the Bandeira–Boedihardjo–van Handel refinement of the noncommutative Khintchine inequality.

Significance. If the central claims hold, the work establishes matching upper and lower bounds on the ancilla-success tradeoff for probabilistic exact simulation of unital channels, providing a quantitative resource characterization with direct relevance to quantum algorithm compilation and circuit design. The explicit tightness construction and the separation for highly noncommutative channels are notable. Credit is due for the machine-checked-style reliance on a recent, sharp matrix concentration result rather than looser bounds.

minor comments (3)
  1. [Introduction] §1 (Introduction) and the statement of Theorem 1: the precise definition of the partition-based protocol (including how the failure flag is implemented and how postselection is performed) should be stated formally before the main theorem, rather than deferred to the proof section, to improve readability for readers outside the immediate subfield.
  2. The lower-bound construction (the family of channels witnessing the O(k / log d) upper limit on success probability) is described at a high level in the abstract; a short self-contained paragraph summarizing the key properties of this family (e.g., how unitality is preserved while forcing the concentration failure) would help readers assess the tightness argument without immediately consulting the full proof.
  3. [Preliminaries] Notation: the symbol for the success probability p_succ is used interchangeably with Ω(k / log d) in several places; a single consistent definition (perhaps as a function of d and k) in the preliminaries would eliminate minor ambiguity.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, including recognition of the matching upper and lower bounds, the tightness construction, the separation for highly noncommutative channels, and the use of the Bandeira–Boedihardjo–van Handel matrix concentration result. The recommendation for minor revision is noted.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The central upper bound is obtained by combining an explicit partition-based protocol with external matrix concentration inequalities (Bandeira–Boedihardjo–van Handel refinement of noncommutative Khintchine), while the matching lower bound is witnessed by an explicit family of unital channels. Neither step reduces to a fitted parameter, self-definition, or self-citation chain; the cited concentration tools are independent of the present authors and the construction is direct rather than renamed or smuggled. The restriction to unital channels is stated explicitly as a model limitation, not derived internally. This is a standard non-circular derivation from first-principles tools and constructions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard mathematical tools (matrix concentration inequalities) and domain assumptions about quantum channels; no free parameters are fitted, and no new entities are postulated.

axioms (2)
  • standard math Matrix concentration inequalities, including the recent refinement of noncommutative Khintchine inequalities due to Bandeira, Boedihardjo and van Handel, hold and can be applied to the partition-based protocol.
    Invoked in the abstract as the technical foundation for the upper bound proof.
  • domain assumption The target channel is unital (preserves the maximally mixed state).
    Central to the simulation bounds; the paper explicitly states the model fails for strongly non-unital channels.

pith-pipeline@v0.9.1-grok · 5733 in / 1651 out tokens · 25105 ms · 2026-06-27T18:13:28.734343+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

37 extracted references · 27 canonical work pages · 2 internal anchors

  1. [2]

    and Xu, Z

    Xu, Z. and Xu, Z. and Zhu, Z. , year =. Improved bounds in Weaver's KS conjecture for high rank \ positive semidefinite matrices , volume =. doi:10.1016/j.jfa.2023.109978 , journal =

    work page doi:10.1016/j.jfa.2023.109978 2023

  2. [4]

    Large Deviations of the Maximum Eigenvalue for Wishart and Gaussian Random Matrices , author =. Phys. Rev. Lett. , volume =. 2009 , month =. doi:10.1103/PhysRevLett.102.060601 , url =

    work page doi:10.1103/physrevlett.102.060601 2009

  3. [5]

    Approximation of Haar distributed matrices and limiting distributions of eigenvalues of Jacobi ensembles , volume =

    Jiang, Tiefeng , year =. Approximation of Haar distributed matrices and limiting distributions of eigenvalues of Jacobi ensembles , volume =. Probability Theory and Related Fields , doi =

  4. [6]

    Tropp , title =

    Tropp, Joel A. , title=. Foundations of Computational Mathematics , year=. doi:10.1007/s10208-011-9099-z , url=

    work page doi:10.1007/s10208-011-9099-z

  5. [7]

    , title =

    Tropp, Joel A. , title =. Found. Trends Mach. Learn. , month = may, pages =. 2015 , issue_date =. doi:10.1561/2200000048 , abstract =

    work page doi:10.1561/2200000048 2015

  6. [8]

    and Boedihardjo, March T

    Bandeira, Afonso S. and Boedihardjo, March T. and van Handel, Ramon , title=. Inventiones mathematicae , year=. doi:10.1007/s00222-023-01204-6 , url=

    work page doi:10.1007/s00222-023-01204-6

  7. [9]

    Journal of Mathematical Physics , volume =

    Kukulski, Ryszard and Nechita, Ion and Pawela, Łukasz and Puchała, Zbigniew and Życzkowski, Karol , title =. Journal of Mathematical Physics , volume =. 2021 , month =. doi:10.1063/5.0038838 , url =

    work page doi:10.1063/5.0038838 2021

  8. [10]

    Implementation of quantum measurements using classical resources and only a single ancillary qubit , volume =

    Singal, Tanmay and Maciejewski, Filip and Oszmaniec, Michał , year =. Implementation of quantum measurements using classical resources and only a single ancillary qubit , volume =. npj Quantum Information , doi =

  9. [11]

    2018 , isbn =

    Watrous, John , title =. 2018 , isbn =

    2018

  10. [12]

    Engineering quantum dynamics , volume =

    Lloyd, Seth and Viola, Lorenza , year =. Engineering quantum dynamics , volume =. Phys. Rev. A , doi =

  11. [13]

    Binary search trees for generalized measurement , volume =

    Andersson, Erika and Oi, Daniel , year =. Binary search trees for generalized measurement , volume =. Phys. Rev. A , doi =

  12. [14]

    Detecting mixed-unitary quantum channels is

    Lee, Colin Do-Yan and Watrous, John , journal =. Detecting mixed-unitary quantum channels is. doi:10.22331/q-2020-04-16-253 , url =

    work page doi:10.22331/q-2020-04-16-253 2020

  13. [15]

    High-Dimensional Probability: An Introduction with Applications in Data Science , publisher=

    Vershynin, Roman , year=. High-Dimensional Probability: An Introduction with Applications in Data Science , publisher=

  14. [16]

    General Resource Theories in Quantum Mechanics and Beyond: Operational Characterization via Discrimination Tasks , author =. Phys. Rev. X , volume =. 2019 , month =. doi:10.1103/PhysRevX.9.031053 , url =

    work page doi:10.1103/physrevx.9.031053 2019

  15. [17]

    The Church of the Symmetric Subspace

    The Church of the Symmetric Subspace. arXiv e-prints , keywords =. doi:10.48550/arXiv.1308.6595 , archivePrefix =. 1308.6595 , primaryClass =

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.1308.6595

  16. [18]

    arXiv e-prints , keywords =

    Norm of matrix-valued polynomials in random unitaries and permutations. arXiv e-prints , keywords =. doi:10.48550/arXiv.2304.05714 , archivePrefix =. 2304.05714 , primaryClass =

    work page doi:10.48550/arxiv.2304.05714

  17. [19]

    Tropp, Joel A. , year=. User-friendly Tail Bounds for Matrix Martingales , DOI=. ACM Report 2011-01, California Inst. Tech., Pasadena, CA , publisher=

    2011

  18. [20]

    arXiv e-prints , keywords =

    Haar random codes attain the quantum Hamming bound, approximately. arXiv e-prints , keywords =. doi:10.48550/arXiv.2510.07158 , archivePrefix =. 2510.07158 , primaryClass =

    work page doi:10.48550/arxiv.2510.07158

  19. [21]

    Letters in Mathematical Physics , volume=

    A note on quantum expanders , author=. Letters in Mathematical Physics , volume=. 2025 , publisher=

    2025

  20. [22]

    arXiv e-prints , keywords =

    Pauli Measurements Are Near-Optimal for Single-Qubit Tomography. arXiv e-prints , keywords =. doi:10.48550/arXiv.2507.22001 , archivePrefix =. 2507.22001 , primaryClass =

    work page doi:10.48550/arxiv.2507.22001

  21. [23]

    International Mathematics Research Notices , volume =

    Lancien, Cécilia , title =. International Mathematics Research Notices , volume =. 2026 , month =. doi:10.1093/imrn/rnaf383 , url =

    work page doi:10.1093/imrn/rnaf383 2026

  22. [24]

    arXiv e-prints , keywords =

    On the injective norm of random fermionic states and skew-symmetric tensors. arXiv e-prints , keywords =. doi:10.48550/arXiv.2510.25474 , archivePrefix =. 2510.25474 , primaryClass =

    work page doi:10.48550/arxiv.2510.25474

  23. [25]

    Pretty Good Simulation of All Quantum Measurements by Projective Measurements , year=

    Kotowski, Michał and Oszmaniec, Michał , journal=. Pretty Good Simulation of All Quantum Measurements by Projective Measurements , year=

  24. [26]

    Almost all quantum channels are equidistant , journal =

    Nechita, Ion and Pucha. Almost all quantum channels are equidistant , journal =. 2018 , month =. doi:10.1063/1.5019322 , url =

    work page doi:10.1063/1.5019322 2018

  25. [27]

    Quantum channel construction with circuit quantum electrodynamics , author =. Phys. Rev. B , volume =. 2017 , month =. doi:10.1103/PhysRevB.95.134501 , url =

    work page doi:10.1103/physrevb.95.134501 2017

  26. [28]

    Approximating quantum channels by completely positive maps with small

    Lancien, C. Approximating quantum channels by completely positive maps with small. doi:10.22331/q-2024-04-30-1320 , url =

    work page doi:10.22331/q-2024-04-30-1320 2024

  27. [29]

    Quantum circuits for quantum channels , author =. Phys. Rev. A , volume =. 2017 , month =. doi:10.1103/PhysRevA.95.052316 , url =

    work page doi:10.1103/physreva.95.052316 2017

  28. [30]

    Simulating Positive-Operator-Valued Measures with Projective Measurements , author =. Phys. Rev. Lett. , volume =. 2017 , month =. doi:10.1103/PhysRevLett.119.190501 , url =

    work page doi:10.1103/physrevlett.119.190501 2017

  29. [31]

    Simulating all quantum measurements using only projective measurements and postselection , author =. Phys. Rev. A , volume =. 2019 , month =. doi:10.1103/PhysRevA.100.012351 , url =

    work page doi:10.1103/physreva.100.012351 2019

  30. [32]

    Simulating Quantum Instruments with Projective Measurements and Quantum Postprocessing , author =. Phys. Rev. Lett. , volume =. 2025 , month =. doi:10.1103/bhr5-g71p , url =

    work page doi:10.1103/bhr5-g71p 2025

  31. [33]

    B. Phys. Rev. Lett. , volume =. 2010 , month = mar, publisher =. doi:10.1103/PhysRevLett.104.120501 , eprint =

    work page doi:10.1103/physrevlett.104.120501 2010

  32. [34]

    Efficient Quantum Algorithms for Simulating Lindblad Evolution

    Cleve, Richard and Wang, Chunhao , title =. 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) , series =. 2017 , editor =. doi:10.4230/LIPIcs.ICALP.2017.17 , isbn =. 1612.09512 , archivePrefix =

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.4230/lipics.icalp.2017.17 2017

  33. [35]

    and Cirac, J

    Verstraete, Frank and Wolf, Michael M. and Cirac, J. Ignacio , title =. Nature Physics , volume =. 2009 , month = sep, doi =. 0803.1447 , archivePrefix =

    Pith/arXiv arXiv 2009

  34. [36]

    Kraus, B. and B. Phys. Rev. A , volume =. 2008 , month = oct, publisher =. doi:10.1103/PhysRevA.78.042307 , eprint =

    work page doi:10.1103/physreva.78.042307 2008

  35. [37]

    Communications in Mathematical Physics , volume=

    Unital quantum channels--convex structure and revivals of Birkhoff's theorem , author=. Communications in Mathematical Physics , volume=. 2009 , publisher=. doi:10.1007/s00220-009-0824-2 , eprint=

    work page doi:10.1007/s00220-009-0824-2 2009

  36. [38]

    Strongly Interacting Fermions Are Nontrivial yet Nonglassy , author =. Phys. Rev. Lett. , volume =. 2025 , month =. doi:10.1103/cbqf-d24r , url =

    work page doi:10.1103/cbqf-d24r 2025

  37. [39]

    and Anschuetz, Eric R

    Ding, Matthew and King, Robbie and Kiani, Bobak T. and Anschuetz, Eric R. , journal =. Optimizing. doi:10.22331/q-2026-03-16-2029 , url =

    work page doi:10.22331/q-2026-03-16-2029 2026