Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2604.27040

Permutation Invariant Optimization Problems in Quantum Information Theory: A Framework for Channel Fidelity and Beyond

Bjarne Bergh, Marco Parentin

quant-phSubmitted Apr 29, 2026• Announced Apr 30, 2026• 0 citations• Revised May 4, 2026 (v2)
v1 · Apr 29, 2026v2 · May 4, 2026
arXivHTMLPDF

Abstract

Exploiting permutation invariance to reduce the exponential scaling of semidefinite programs in quantum information has emerged as a powerful computational technique. In this work, we develop a systematic framework for using this reduction via Schur-Weyl duality for optimization problems, and establish methods that allow one to work fully inside the permutation invariant subspace while performing operations such as (partially) applying channels and taking (partial) traces, or computing expressions like the quantum relative entropy. We then apply our techniques to the problem of computing efficient lower bounds on the channel fidelity over $n$ parallel uses of a quantum channel. The algorithm, which we call symmetric seesaw method, exploits permutation-invariant codes to yield improved lower bounds on the channel fidelity over $n$ uses of the depolarizing and amplitude-damping channel in the regime of tens of channel uses, and was used in [arxiv:2604.27042] to demonstrate non-asymptotic superactivation of quantum capacity for $n = 17$. An implementation of our methods, aimed at being suitable for various quantum information theoretic optimization problems, is also available as an open-source Python package.

Comments
64 pages, 6 figures. v2: Updated references

Related papers

From Permutation Symmetry to Communication Bounds and Additivity

Zahra Baghali Khanian, Debbie Leung, Graeme Smith

Correlations across channel uses can improve quantum communication rates, making optimization over arbitrarily large blocks a central difficulty in determining quantum capacity. We show how full permutation invariance limits this advantage for every finite-dimensional memoryless channel. The optimized coherent information per use converges to the single-use maximum and consequently attains its supremum at a finite block length. Thus finite-block superadditivity remains possible, while the asymptotic optimization reduces to a single channel use. We also establish a strong converse for pure-source entanglement generation with permutation-invariant inputs: at any fixed rate above the single-use coherent-information maximum, the fidelity tends to zero. Beyond these communication bounds, we identify a common structure underlying completely bounded norms and the sandwiched Rényi channel quantities governing discrimination against a replacer and entanglement-assisted communication. De Finetti reduction and permutation covariance yield systematic alternative proofs of their known multiplicativity and additivity results within a shared variational framework. We further show that, for permutation-invariant inputs, correlations cannot sustain an asymptotic reduction in output entropy per use below the single-use minimum. This entropy limit holds for Rényi orders greater than one and for the von Neumann entropy, extending the role of symmetry from communication bounds to the control of output entropy.

quant-pharXiv:2610.02176•Oct 2, 2026•0 citations

An Efficient Parameterized Algorithm for Computing Quantum Channel Fidelity via Symmetries Exploitation

Yeow Meng Chee, Hoang Ta, Van Khu Vu

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, compared to the$\exp (1/\epsilon, \text {input dimension})$running time required for direct computation.

IEEE Transactions on Information Theory•Jul 16, 2025•0 citations

Enhanced quantum capacity thresholds from symmetry

Avantika Agarwal, Amolak Ratan Kalra, Sungjai Lee +4 more

The quantum capacity captures the value of a quantum channel for transmitting quantum information, establishing the fundamental limits on quantum communication. In spite of its central role in quantum information theory, the quantum capacity of most channels is unknown, with wide gaps between the best upper and lower bounds. Even deciding whether a channel has nonzero capacity -- finding its capacity threshold -- is difficult. In this paper we report significant increases in the capacity thresholds of two prototypical noise models: the depolarizing channel and Pauli channels. In the case of the depolarizing channel, this is the first improvement in 18 years, giving a bigger increase beyond the hashing bound than all previous improvements combined. Our starting point is the representation theoretic framework recently proposed by Bhalerao and Leditzky (2025) to compute coherent information for special permutation invariant states. We generalize their framework to the full symmetric subspace, which allow us to optimize coherent information over rank two states in that space. A representation theoretic calculation shows that exponentially many Kraus operators of the channel annihilate the symmetric space, corresponding to a massive decrease in environment entropy for states on the symmetric space compared to the maximally mixed state. This explains the enhanced coherent information as a manifestation of degeneracy for the resulting codes.

quant-pharXiv:2605.09138•May 12, 2026•0 citations

Quantum Time Lower Bounds by Permutation Invariance

Qisheng Wang

Tight bounds on quantum sample complexity and quantum query complexity have been known for various computational problems in the literature, whereas tight bounds on quantum time complexity (i.e., the size of quantum circuits) remain unresolved. In this paper, we provide a framework to establish lower bounds on the quantum time complexity for testing permutation-invariant properties of quantum states, via a reduction from quantum sample complexity. As an application, we obtain a series of matching lower bounds when given sample access to the input quantum states, including: 1. The SWAP test due to Buhrman, Cleve, Watrous, and de Wolf (Phys. Rev. Lett. 2001) is time-optimal to estimate the purity $\operatorname{tr}(ρ^2)$ and the inner product $\operatorname{tr}(ρσ)$. 2. The Shift test due to Ekert, Alves, Oi, Horodecki, Horodecki, and Kwek (Phys. Rev. Lett. 2002) is time-optimal to estimate the high-order functionals $\operatorname{tr}(ρ^k)$. 3. The productness tester for multipartite pure states due to Harrow and Montanaro (J. ACM 2013) is time-optimal. 4. The LMR protocol due to Lloyd, Mohseni, and Rebentrost (Nat. Phys. 2014) is time-optimal to implement the reflection operator about a pure state. 5. The samplizer due to Wang and Zhang (IEEE Trans. Inf. Theory 2025) is time-optimal for pure states. 6. The estimator for pure-state trace distance and fidelity due to Wang and Zhang (ICALP 2026) is time-optimal. To the best of our knowledge, this is the first method that allows us to systematically establish tight lower bounds on quantum time complexity.

quant-pharXiv:2606.05099•Jun 4, 2026•0 citations

Universal quantum coding

Jacopo Rizzo, Filippo Girardi, Ludovico Lami +2 more

Entanglement distillation from noisy bipartite states and reliable quantum communication over noisy channels are fundamental tasks in quantum information theory. Yet existing coding schemes typically require prior knowledge of the underlying state or channel, or assume independent or weakly correlated quantum information sources. Here, using Schur-Weyl duality, we establish a universal quantum error-correction principle that overcomes these limitations. We show that the irreducible permutation spaces arising from the local Schur-Weyl decomposition of multiple copies of an unknown bipartite mixed state form maximally entangled quantum code spaces whose error structure is governed entirely by representation theory. Correcting these symmetry-resolved errors yields protocols for entanglement distillation and quantum communication that achieve coherent-information rates with exponentially vanishing error and optimal second-order corrections, even in the case of almost i.i.d. resources. Our approach also provides sharp finite-copy guarantees that are worst-case optimal at every finite block length, including in the sample-efficient regime, where the number of copies scales only polynomially with the number of qubits. Together, these results establish Schur-Weyl duality as a general mechanism for universal, robust, and optimal quantum coding, unifying entanglement distillation, quantum error correction, and quantum communication within a common representation-theoretic framework.

quant-pharXiv:2609.38038•Sep 30, 2026•0 citations

Classification and implementation of unitary-equivariant and permutation-invariant quantum channels

Laura Mančinska, Elias Theil

Many quantum information tasks use inputs of the form $ρ^{\otimes m}$, which naturally induce permutation and unitary symmetries. We classify all quantum channels that respect both symmetries - i.e. unitary-equivariant and permutation-invariant quantum channels from $(\mathbb{C}^{d})^{\otimes m}$ to $(\mathbb{C}^{d})^{\otimes n}$ - via their extremal points. Operationally, each extremal quantum channel factors as unitary Schur sampling $\rightarrow$ an irrep-level unitary-equivariant quantum channel $\rightarrow$ the adjoint unitary Schur sampling. We give a streaming implementation ansatz that uses an efficient streaming implementation of unitary Schur sampling together with a resource-state primitive, and we apply it to state symmetrization, symmetric cloning, and purity amplification. In these applications we obtain polynomial-time algorithms with exponential memory improvements in $m,n$. Further, for symmetric cloning we present, to our knowledge, the first efficient (polynomial-time) algorithm with explicit memory and gate bounds.

arXiv:2510.08154•Oct 9, 2025•0 citations
Exploiting permutation invariance to reduce the exponential scaling of semidefinite programs in quantum information has emerged as a powerful computational technique. In this work, we develop a systematic framework for using this reduction via Schur-Weyl duality for optimization problems, and establish methods that allow one to work fully inside the permutation invariant subspace while performing operations such as (partially) applying channels and taking (partial) traces, or computing expressions like the quantum relative entropy. We then apply our techniques to the problem of computing efficient lower bounds on the channel fidelity over nnn parallel uses of a quantum channel. The algorithm, which we call symmetric seesaw method, exploits permutation-invariant codes to yield improved lower bounds on the channel fidelity over nnn uses of the depolarizing and amplitude-damping channel in the regime of tens of channel uses, and was used in [arxiv:2604.27042] to demonstrate non-asymptotic superactivation of quantum capacity for n=17n = 17n=17. An implementation of our methods, aimed at being suitable for various quantum information theoretic optimization problems, is also available as an open-source Python package.
Correlations across channel uses can improve quantum communication rates, making optimization over arbitrarily large blocks a central difficulty in determining quantum capacity. We show how full permutation invariance limits this advantage for every finite-dimensional memoryless channel. The optimized coherent information per use converges to the single-use maximum and consequently attains its supremum at a finite block length. Thus finite-block superadditivity remains possible, while the asymptotic optimization reduces to a single channel use. We also establish a strong converse for pure-source entanglement generation with permutation-invariant inputs: at any fixed rate above the single-use coherent-information maximum, the fidelity tends to zero. Beyond these communication bounds, we identify a common structure underlying completely bounded norms and the sandwiched Rényi channel quantities governing discrimination against a replacer and entanglement-assisted communication. De Finetti reduction and permutation covariance yield systematic alternative proofs of their known multiplicativity and additivity results within a shared variational framework. We further show that, for permutation-invariant inputs, correlations cannot sustain an asymptotic reduction in output entropy per use below the single-use minimum. This entropy limit holds for Rényi orders greater than one and for the von Neumann entropy, extending the role of symmetry from communication bounds to the control of output entropy.
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 ininin\mathrm {poly}(1/\epsilon, \text {input dimension})time,comparedtothetime, compared to thetime,comparedtothe\exp (1/\epsilon, \text {input dimension})$running time required for direct computation.
The quantum capacity captures the value of a quantum channel for transmitting quantum information, establishing the fundamental limits on quantum communication. In spite of its central role in quantum information theory, the quantum capacity of most channels is unknown, with wide gaps between the best upper and lower bounds. Even deciding whether a channel has nonzero capacity -- finding its capacity threshold -- is difficult. In this paper we report significant increases in the capacity thresholds of two prototypical noise models: the depolarizing channel and Pauli channels. In the case of the depolarizing channel, this is the first improvement in 18 years, giving a bigger increase beyond the hashing bound than all previous improvements combined. Our starting point is the representation theoretic framework recently proposed by Bhalerao and Leditzky (2025) to compute coherent information for special permutation invariant states. We generalize their framework to the full symmetric subspace, which allow us to optimize coherent information over rank two states in that space. A representation theoretic calculation shows that exponentially many Kraus operators of the channel annihilate the symmetric space, corresponding to a massive decrease in environment entropy for states on the symmetric space compared to the maximally mixed state. This explains the enhanced coherent information as a manifestation of degeneracy for the resulting codes.
Tight bounds on quantum sample complexity and quantum query complexity have been known for various computational problems in the literature, whereas tight bounds on quantum time complexity (i.e., the size of quantum circuits) remain unresolved. In this paper, we provide a framework to establish lower bounds on the quantum time complexity for testing permutation-invariant properties of quantum states, via a reduction from quantum sample complexity. As an application, we obtain a series of matching lower bounds when given sample access to the input quantum states, including: 1. The SWAP test due to Buhrman, Cleve, Watrous, and de Wolf (Phys. Rev. Lett. 2001) is time-optimal to estimate the purity tr⁡(ρ2)\operatorname{tr}(ρ^2)tr(ρ2) and the inner product tr⁡(ρσ)\operatorname{tr}(ρσ)tr(ρσ). 2. The Shift test due to Ekert, Alves, Oi, Horodecki, Horodecki, and Kwek (Phys. Rev. Lett. 2002) is time-optimal to estimate the high-order functionals tr⁡(ρk)\operatorname{tr}(ρ^k)tr(ρk). 3. The productness tester for multipartite pure states due to Harrow and Montanaro (J. ACM 2013) is time-optimal. 4. The LMR protocol due to Lloyd, Mohseni, and Rebentrost (Nat. Phys. 2014) is time-optimal to implement the reflection operator about a pure state. 5. The samplizer due to Wang and Zhang (IEEE Trans. Inf. Theory 2025) is time-optimal for pure states. 6. The estimator for pure-state trace distance and fidelity due to Wang and Zhang (ICALP 2026) is time-optimal. To the best of our knowledge, this is the first method that allows us to systematically establish tight lower bounds on quantum time complexity.
Entanglement distillation from noisy bipartite states and reliable quantum communication over noisy channels are fundamental tasks in quantum information theory. Yet existing coding schemes typically require prior knowledge of the underlying state or channel, or assume independent or weakly correlated quantum information sources. Here, using Schur-Weyl duality, we establish a universal quantum error-correction principle that overcomes these limitations. We show that the irreducible permutation spaces arising from the local Schur-Weyl decomposition of multiple copies of an unknown bipartite mixed state form maximally entangled quantum code spaces whose error structure is governed entirely by representation theory. Correcting these symmetry-resolved errors yields protocols for entanglement distillation and quantum communication that achieve coherent-information rates with exponentially vanishing error and optimal second-order corrections, even in the case of almost i.i.d. resources. Our approach also provides sharp finite-copy guarantees that are worst-case optimal at every finite block length, including in the sample-efficient regime, where the number of copies scales only polynomially with the number of qubits. Together, these results establish Schur-Weyl duality as a general mechanism for universal, robust, and optimal quantum coding, unifying entanglement distillation, quantum error correction, and quantum communication within a common representation-theoretic framework.
Many quantum information tasks use inputs of the form ρ⊗mρ^{\otimes m}ρ⊗m, which naturally induce permutation and unitary symmetries. We classify all quantum channels that respect both symmetries - i.e. unitary-equivariant and permutation-invariant quantum channels from (Cd)⊗m(\mathbb{C}^{d})^{\otimes m}(Cd)⊗m to (Cd)⊗n(\mathbb{C}^{d})^{\otimes n}(Cd)⊗n - via their extremal points. Operationally, each extremal quantum channel factors as unitary Schur sampling →\rightarrow→ an irrep-level unitary-equivariant quantum channel →\rightarrow→ the adjoint unitary Schur sampling. We give a streaming implementation ansatz that uses an efficient streaming implementation of unitary Schur sampling together with a resource-state primitive, and we apply it to state symmetrization, symmetric cloning, and purity amplification. In these applications we obtain polynomial-time algorithms with exponential memory improvements in m,nm,nm,n. Further, for symmetric cloning we present, to our knowledge, the first efficient (polynomial-time) algorithm with explicit memory and gate bounds.