pith. sign in

arxiv: 2308.15884 · v4 · submitted 2023-08-30 · 🪐 quant-ph · cs.DS· cs.IT· math.IT

Efficient Approximation of Quantum Channel Fidelity Exploiting Symmetry

Yeow Meng Chee , Hoang Ta , Van Khu Vu This is my paper

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

classification 🪐 quant-ph cs.DScs.ITmath.IT
keywords quantum channel fidelitysemidefinite programming hierarchysymmetry reductionpolynomial-time approximationquantum information theorySDP dimension reductionfidelity bounds
0
0 comments X

The pith

Symmetries in the SDP hierarchy for quantum channel fidelity allow polynomial-time computation when output dimension is fixed.

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

The paper demonstrates that the symmetries of the semidefinite programs used to bound quantum channel fidelity permit a dimension reduction that leaves the optimal value unchanged. For channels with fixed output dimension this reduction yields programs whose size grows only polynomially with the hierarchy level and the input dimension. The resulting procedure therefore approximates the optimal fidelity to accuracy epsilon in time polynomial in 1/epsilon and input dimension. A reader cares because the original hierarchy scaled exponentially and was therefore limited to very small instances.

Core claim

Exploiting the symmetries present in the SDP formulation of the optimal quantum channel fidelity problem produces a reduced program at each level of the hierarchy whose feasible set and optimal value coincide with those of the original program; when the output dimension is held fixed the size of the reduced program is polynomial in the hierarchy level and the input dimension, directly implying an efficient approximation scheme for the fidelity.

What carries the argument

Symmetry-based dimension reduction of the SDP hierarchy that preserves feasibility and optimal value.

If this is right

  • Each level of the hierarchy can be solved in time polynomial in the level index and input dimension when output dimension is fixed.
  • The optimal fidelity is approximable to accuracy epsilon in time polynomial in 1/epsilon and input dimension.
  • Higher levels of the hierarchy become numerically tractable for moderate input dimensions.
  • The same reduction applies uniformly to any quantum channel whose SDP exhibits the identified symmetry group.

Where Pith is reading between the lines

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

  • The reduction technique may be reusable on other SDP hierarchies arising in quantum information once their symmetry groups are identified.
  • Numerical studies of convergence speed for concrete channels at high hierarchy levels now become feasible.
  • If the output dimension grows slowly with input dimension the same polynomial scaling may still yield practical runtimes.

Load-bearing premise

The symmetries of the SDP formulation permit a dimension reduction that preserves both feasibility and the optimal value of each level of the hierarchy.

What would settle it

An explicit SDP instance from the hierarchy in which the symmetry-reduced program has a different optimal value or different feasibility status from the unreduced program.

read the original abstract

Determining the optimal fidelity for the transmission of quantum information over noisy quantum channels is one of the central problems in quantum information theory. Recently, [Berta-Borderi-Fawzi-Scholz, Mathematical Programming, 2021] introduced an asymptotically converging semidefinite programming hierarchy of outer bounds for this quantity. However, the size of the semidefinite programs (SDPs) grows exponentially with respect to the level of the hierarchy, thus making their computation unscalable. In this work, by exploiting the symmetries in the SDP, we show that, for a fixed output dimension of the quantum channel, we can compute the SDP in time polynomial with respect to the level of the hierarchy and input dimension. As a direct consequence of our result, the optimal fidelity can be approximated with an accuracy of $\epsilon$ in $\mathrm{poly}(1/\epsilon, \text{input dimension})$ time.

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

2 major / 2 minor

Summary. The manuscript develops a symmetry-based dimension reduction for the SDP hierarchy introduced by Berta et al. (2021) that outer-approximates the optimal quantum channel fidelity. For fixed output dimension, the reduced SDPs are claimed to be solvable in time polynomial in the hierarchy level k and input dimension d_in. The abstract states that this reduction directly yields an ε-approximation to the optimal fidelity in poly(1/ε, d_in) time.

Significance. If the claimed polynomial-time per-level solvability and the overall approximation guarantee both hold, the work would make the Berta hierarchy computationally tractable for moderate input dimensions, addressing a key scalability barrier in quantum channel capacity calculations. The symmetry reduction technique itself is standard and, when correctly implemented, preserves feasibility and optimality.

major comments (2)
  1. [Abstract] Abstract: the assertion that the symmetry reduction yields an ε-approximation in poly(1/ε, d_in) time is presented as a direct consequence of the per-level polynomial runtime. However, the Berta et al. (2021) hierarchy is only known to converge asymptotically (k → ∞); no polynomial convergence rate (error ≤ C/k^α) is established or cited. Without such a rate, choosing k = poly(1/ε) does not guarantee ε-accuracy, so the overall runtime claim is unsupported.
  2. [§3 or §4 (symmetry reduction)] Section describing the symmetry reduction (likely §3 or §4): the manuscript must explicitly verify that the fixed-point subspace projection (or representation-theoretic reduction) preserves both the feasible set and the optimal value of each level of the original SDP. If the reduction is only shown to produce a smaller SDP without proving equivalence of the optimum, the polynomial-time claim does not apply to the original fidelity bounds.
minor comments (2)
  1. Notation for the reduced SDP variables and the group action should be introduced with a short table or explicit mapping from the original variables.
  2. The complexity analysis should state the precise polynomial degree in k and d_in (or at least the dominant terms) rather than the generic phrase 'polynomial time'.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments. We address each major point below and agree that revisions are needed for the abstract claim.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the assertion that the symmetry reduction yields an ε-approximation in poly(1/ε, d_in) time is presented as a direct consequence of the per-level polynomial runtime. However, the Berta et al. (2021) hierarchy is only known to converge asymptotically (k → ∞); no polynomial convergence rate (error ≤ C/k^α) is established or cited. Without such a rate, choosing k = poly(1/ε) does not guarantee ε-accuracy, so the overall runtime claim is unsupported.

    Authors: We agree with the referee. The Berta et al. hierarchy converges only asymptotically with no known polynomial rate, so the abstract's claim of an ε-approximation in poly(1/ε, d_in) time is unsupported. We will revise the abstract to remove this assertion and instead state only that each reduced SDP level is solvable in time polynomial in k and d_in (for fixed output dimension). revision: yes

  2. Referee: [§3 or §4 (symmetry reduction)] Section describing the symmetry reduction (likely §3 or §4): the manuscript must explicitly verify that the fixed-point subspace projection (or representation-theoretic reduction) preserves both the feasible set and the optimal value of each level of the original SDP. If the reduction is only shown to produce a smaller SDP without proving equivalence of the optimum, the polynomial-time claim does not apply to the original fidelity bounds.

    Authors: The reduction is obtained by projecting the SDP variables onto the fixed-point subspace of the symmetric group action, which is invariant. This preserves optimality because the objective and constraints are group-invariant, so the symmetrized solution remains feasible with the same value. To address the request for explicit verification, we will insert a new proposition in the symmetry reduction section that formally proves equivalence of feasible sets and optimal values between the original and reduced SDPs. revision: yes

Circularity Check

0 steps flagged

No circularity; symmetry reduction is an independent algorithmic contribution

full rationale

The paper's core claim is a new symmetry-based dimension reduction (via representation theory or fixed-point subspaces) that makes each level of the Berta et al. (2021) SDP hierarchy solvable in time polynomial in the hierarchy level k and input dimension (for fixed output dimension). This reduction is derived from the structure of the SDP and is not defined in terms of the final approximation result. The poly(1/ε) runtime is presented as a direct consequence of the per-level cost plus the cited asymptotic convergence of the hierarchy; no fitted parameters, self-definitional equations, or load-bearing self-citations appear in the derivation chain. The argument is therefore self-contained against external benchmarks and receives the default non-circularity finding.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review performed on abstract only; therefore the ledger is necessarily incomplete. The sole explicit background assumption is the asymptotic convergence of the cited SDP hierarchy.

axioms (1)
  • domain assumption The SDP hierarchy introduced in Berta-Borderi-Fawzi-Scholz (Mathematical Programming, 2021) converges asymptotically to the optimal quantum channel fidelity.
    Abstract states that the hierarchy provides outer bounds and that the new result yields a direct consequence for approximation accuracy.

pith-pipeline@v0.9.0 · 5689 in / 1323 out tokens · 31900 ms · 2026-05-24T07:05:50.898205+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

44 extracted references · 44 canonical work pages · 2 internal anchors

  1. [1]

    Semidefinite programming hierarchies for constrained bilinear optimization

    Mario Berta, Francesco Borderi, Omar Fawzi, and Volkher B Scholz. Semidefinite programming hierarchies for constrained bilinear optimization. Mathematical Programming , pages 1--49, 2021

    work page 2021

  2. [2]

    Exploiting group symmetry in truss topology optimization

    Yanqin Bai, Etienne de Klerk, Dmitrii Pasechnik, and Renata Sotirov. Exploiting group symmetry in truss topology optimization. Optimization and Engineering , 10:331--349, 2009

    work page 2009

  3. [3]

    Algorithmic aspects of optimal channel coding

    Siddharth Barman and Omar Fawzi. Algorithmic aspects of optimal channel coding. IEEE Transactions on Information Theory , 64(2):1038--1045, 2017

    work page 2017

  4. [4]

    Tight approximation bounds for maximum multi-coverage

    Siddharth Barman, Omar Fawzi, Suprovat Ghoshal, and Emirhan G \"u rp nar. Tight approximation bounds for maximum multi-coverage. In International Conference on Integer Programming and Combinatorial Optimization , pages 66--77. Springer, 2020

    work page 2020

  5. [5]

    Quantum bilinear optimization

    Mario Berta, Omar Fawzi, and Volkher B Scholz. Quantum bilinear optimization. SIAM Journal on Optimization , 26(3):1529--1564, 2016

    work page 2016

  6. [6]

    Optimizing hypergraph-based polynomials modeling job-occupancy in queuing with redundancy scheduling

    Daniel Brosch, Monique Laurent, and Andries Steenkamp. Optimizing hypergraph-based polynomials modeling job-occupancy in queuing with redundancy scheduling. SIAM Journal on Optimization , 31(3):2227--2254, 2021

    work page 2021

  7. [7]

    New lower bounds on crossing numbers of k\_ \ m, n \ from permutation modules and semidefinite programming

    Daniel Brosch and Sven Polak. New lower bounds on crossing numbers of k\_ \ m, n \ from permutation modules and semidefinite programming. arXiv preprint arXiv:2206.02755 , 2022

    work page arXiv 2022

  8. [8]

    Exploiting special structure in semidefinite programming: A survey of theory and applications

    Etienne De Klerk. Exploiting special structure in semidefinite programming: A survey of theory and applications. European Journal of Operational Research , 201(1):1--10, 2010

    work page 2010

  9. [9]

    Reduction of symmetric semidefinite programs using the regular-representation

    Etienne De Klerk, Dmitrii V Pasechnik, and Alexander Schrijver. Reduction of symmetric semidefinite programs using the regular-representation. Mathematical programming , 109(2-3):613--624, 2007

    work page 2007

  10. [10]

    Representation theory: a first course , volume 129

    William Fulton and Joe Harris. Representation theory: a first course , volume 129. Springer Science & Business Media, 2013

    work page 2013

  11. [11]

    Approximation algorithms for classical-quantum channel coding

    Omar Fawzi, Johanna Seif, and D \'a niel Szil \'a gyi. Approximation algorithms for classical-quantum channel coding. In 2019 IEEE International Symposium on Information Theory (ISIT) , pages 2569--2573. IEEE, 2019

    work page 2019

  12. [12]

    A hierarchy of efficient bounds on quantum capacities exploiting symmetry

    Omar Fawzi, Ala Shayeghi, and Hoang Ta. A hierarchy of efficient bounds on quantum capacities exploiting symmetry. IEEE Transactions on Information Theory , 68(11):7346--7360, 2022

    work page 2022

  13. [13]

    Optimum quantum error recovery using semidefinite programming

    Andrew S Fletcher, Peter W Shor, and Moe Z Win. Optimum quantum error recovery using semidefinite programming. Physical Review A , 75(1):012338, 2007

    work page 2007

  14. [14]

    Block diagonalization for algebra's associated with block codes

    Dion Gijswijt. Block diagonalization for algebra's associated with block codes. arXiv preprint arXiv:0910.4515 , 2009

    work page internal anchor Pith review Pith/arXiv arXiv 2009

  15. [15]

    Computing the and semidefinite programming bounds for the chromatic number

    N Gvozdenovic and M Laurent. Computing the and semidefinite programming bounds for the chromatic number. Optimization Online, February , 2007

    work page 2007

  16. [16]

    Symmetry groups, semidefinite programs, and sums of squares

    Karin Gatermann and Pablo A Parrilo. Symmetry groups, semidefinite programs, and sums of squares. Journal of Pure and Applied Algebra , 192(1-3):95--128, 2004

    work page 2004

  17. [17]

    Mutually unbiased bases: polynomial optimization and symmetry

    Sander Gribling and Sven Polak. Mutually unbiased bases: polynomial optimization and symmetry. arXiv preprint arXiv:2111.05698 , 2021

    work page arXiv 2021

  18. [18]

    New upper bounds for nonbinary codes based on the terwilliger algebra and semidefinite programming

    Dion Gijswijt, Alexander Schrijver, and Hajime Tanaka. New upper bounds for nonbinary codes based on the terwilliger algebra and semidefinite programming. Journal of Combinatorial Theory, Series A , 113(8):1719--1731, 2006

    work page 2006

  19. [19]

    Information spectrum approach to second-order coding rate in channel coding

    Masahito Hayashi. Information spectrum approach to second-order coding rate in channel coding. IEEE Transactions on Information Theory , 55(11):4947--4966, 2009

    work page 2009

  20. [20]

    QVECTOR: an algorithm for device-tailored quantum error correction

    Peter D Johnson, Jonathan Romero, Jonathan Olson, Yudong Cao, and Al \'a n Aspuru-Guzik. Qvector: an algorithm for device-tailored quantum error correction. arXiv preprint arXiv:1711.02249 , 2017

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  21. [21]

    Extendibility limits the performance of quantum processors

    Eneet Kaur, Siddhartha Das, Mark M Wilde, and Andreas Winter. Extendibility limits the performance of quantum processors. Physical review letters , 123(7):070502, 2019

    work page 2019

  22. [22]

    Reduction of symmetric semidefinite programs using the regular * -representation

    Etienne Klerk, Dmitrii Pasechnik, and Alexander Schrijver. Reduction of symmetric semidefinite programs using the regular * -representation. Math. Program. , 109:613--624, March 2007. https://doi.org/10.1007/s10107-006-0039-7 doi:10.1007/s10107-006-0039-7

    work page doi:10.1007/s10107-006-0039-7 2007

  23. [23]

    Strengthened semidefinite programming bounds for codes

    Monique Laurent. Strengthened semidefinite programming bounds for codes. Mathematical programming , 109(2-3):239--261, 2007

    work page 2007

  24. [24]

    Semidefinite bounds for mixed binary/ternary codes

    Bart Litjens. Semidefinite bounds for mixed binary/ternary codes. Discrete mathematics , 341(6):1740--1748, 2018

    work page 2018

  25. [25]

    Jean-Bernard Lasserre and Anjos F. Miguel. Handbook on Semidefinite, Conic and Polynomial Optimization . International Series in Operations Research & Management Science. Springer , November 2011. URL: https://hal.archives-ouvertes.fr/hal-00697757

    work page 2011

  26. [26]

    On the power of ppt-preserving and non-signalling codes

    Debbie Leung and William Matthews. On the power of ppt-preserving and non-signalling codes. IEEE Transactions on Information Theory , 61(8):4486--4499, 2015

    work page 2015

  27. [27]

    Semidefinite bounds for nonbinary codes based on quadruples

    Bart Litjens, Sven Polak, and Alexander Schrijver. Semidefinite bounds for nonbinary codes based on quadruples. Designs, Codes and Cryptography , 84(1):87--100, 2017

    work page 2017

  28. [28]

    Semidefinite programming bounds for constant-weight codes

    Sven C Polak. Semidefinite programming bounds for constant-weight codes. IEEE Transactions on Information Theory , 65(1):28--38, 2018

    work page 2018

  29. [29]

    Semidefinite programming bounds for lee codes

    Sven C Polak. Semidefinite programming bounds for lee codes. Discrete Mathematics , 342(9):2579--2589, 2019

    work page 2019

  30. [30]

    New methods in coding theory : Error-correcting codes and the Shannon capacity

    Sven Carel Polak. New methods in coding theory : Error-correcting codes and the Shannon capacity . PhD thesis, University of Amsterdam, 2019

    work page 2019

  31. [31]

    New methods in coding theory: Error-correcting codes and the shannon capacity

    Sven Polak. New methods in coding theory: Error-correcting codes and the shannon capacity. arXiv preprint arXiv:2005.02945 , 2020

    work page arXiv 2005

  32. [32]

    Symmetry reduction to optimize a graph-based polynomial from queueing theory

    Sven C Polak. Symmetry reduction to optimize a graph-based polynomial from queueing theory. SIAM Journal on Applied Algebra and Geometry , 6(2):243--266, 2022

    work page 2022

  33. [33]

    Channel coding rate in the finite blocklength regime

    Yury Polyanskiy, H Vincent Poor, and Sergio Verd \'u . Channel coding rate in the finite blocklength regime. IEEE Transactions on Information Theory , 56(5):2307--2359, 2010

    work page 2010

  34. [34]

    Lie groups

    Claudio Procesi. Lie groups. an approach through invariants and representations. Bull. Amer. Math. Soc , 2007

    work page 2007

  35. [35]

    Exploiting symmetries in sdp-relaxations for polynomial optimization

    Cordian Riener, Thorsten Theobald, Lina Jansson Andr \'e n, and Jean B Lasserre. Exploiting symmetries in sdp-relaxations for polynomial optimization. Mathematics of Operations Research , 38(1):122--141, 2013

    work page 2013

  36. [36]

    Iterative optimization of quantum error correcting codes

    Michael Reimpell and Reinhard F Werner. Iterative optimization of quantum error correcting codes. Physical review letters , 94(8):080501, 2005

    work page 2005

  37. [37]

    New code upper bounds from the terwilliger algebra and semidefinite programming

    Alexander Schrijver. New code upper bounds from the terwilliger algebra and semidefinite programming. IEEE Transactions on Information Theory , 51(8):2859--2866, 2005

    work page 2005

  38. [38]

    Linear Representations of Finite Groups

    Jean-Pierre Serre. Linear Representations of Finite Groups . Cambridge University Press, 1977

    work page 1977

  39. [39]

    A mathematical theory of communication

    Claude Elwood Shannon. A mathematical theory of communication. The Bell system technical journal , 27(3):379--423, 1948

    work page 1948

  40. [40]

    Quantum coding with finite resources

    Marco Tomamichel, Mario Berta, and Joseph M Renes. Quantum coding with finite resources. Nature communications , 7(1):11419, 2016

    work page 2016

  41. [41]

    Channel-optimized quantum error correction

    Soraya Taghavi, Robert L Kosut, and Daniel A Lidar. Channel-optimized quantum error correction. IEEE Transactions on Information Theory , 56(3):1461--1473, 2010

    work page 2010

  42. [42]

    Symmetry in semidefinite programs

    Frank Vallentin. Symmetry in semidefinite programs. Linear Algebra and its Applications , 430(1):360--369, 2009

    work page 2009

  43. [43]

    A semidefinite programming upper bound of quantum capacity

    Xin Wang and Runyao Duan. A semidefinite programming upper bound of quantum capacity. In 2016 IEEE International Symposium on Information Theory (ISIT) , pages 1690--1694. IEEE, 2016

    work page 2016

  44. [44]

    Semidefinite programming converse bounds for quantum communication

    Xin Wang, Kun Fang, and Runyao Duan. Semidefinite programming converse bounds for quantum communication. IEEE Transactions on Information Theory , 65(4):2583--2592, 2018

    work page 2018