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:2408.10323

SDP bounds on quantum codes

Gerard Anglès Munné, Andrew Nemec, Felix Huber

Published Aug 19, 2024• 18 citations
arXivHTMLPDF

Abstract

This paper provides a semidefinite programming hierarchy based on state polynomial optimization to determine the existence of quantum codes with given parameters. The hierarchy is complete, in the sense that a $(\!(n, K, δ)\!)_2$ code exists if and only if every level of the hierarchy is feasible. It is not limited to stabilizer codes and thus is applicable generally. While the machinery is formally dimension-free, we restrict it to qubit codes through quasi-Clifford algebras. We derive the quantum analog of a range of classical results: first, from an intermediate level a Lovász bound for self-dual quantum codes is recovered. Second, a symmetrization of a minor variation of this Lovász bound recovers the quantum Delsarte bound. Third, a symmetry reduction using the Terwilliger algebra leads to semidefinite programming bounds of size $O(n^4)$. With this we give an alternative proof that there is no $(\!(7, 1, 4)\!)_2$ quantum code, and show that $(\!(8, 9, 3)\!)_2$ and $(\!(10, 5, 4)\!)_2$ codes do not exist.

DOI
10.48550/arxiv.2408.10323

Related papers

SDP bounds on quantum codes: rational certificates

Gerard Anglès Munné, Felix Huber

A fundamental problem in quantum coding theory is to determine the maximum size of quantum codes of given block length and distance. A recent work introduced bounds based on semidefinite programming, strengthening the well-known quantum linear programming bounds. However, floating-point inaccuracies prevent the extraction of rigorous non-existence proofs from the numerical methods. Here, we address this by providing rational infeasibility certificates for a range of quantum codes. Using a clustered low-rank solver with heuristic rounding to algebraic expressions, we can improve upon $18$ upper bounds on the maximum size of $n$-qubit codes with $6 \leq n \leq 19$. Our work highlights the practicality and scalability of semidefinite programming for quantum coding bounds.

quant-pharXiv:2603.19901•Mar 23, 2026•5 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.

arXiv:2308.15884•IEEE Transactions on Information Theory•Jul 16, 2025•5 citations

Quantum Bilinear Optimization

Mario Berta, Omar Fawzi, Volkher B. Scholz

We study optimization programs given by a bilinear form over noncommutative variables subject to linear inequalities. Problems of this form include the entangled value of two-prover games, entanglement-assisted coding for classical channels, and quantum-proof randomness extractors. We introduce an asymptotically converging hierarchy of efficiently computable semidefinite programming (SDP) relaxations for this quantum optimization. This allows us to give upper bounds on the quantum advantage for all of these problems. Compared to previous work of Pironio, Navascués, and Acín [SIAM J. Optim., 20 (2010), pp. 2157--2180], our hierarchy has additional constraints. By means of examples, we illustrate the importance of these new constraints both in practice and for analytical properties. Moreover, this allows us to give a hierarchy of SDP outer approximations for the completely positive semidefinite cone introduced by Laurent and Piovesan.

arXiv:1506.08810•SIAM Journal on Optimization•Jan 1, 2016•38 citations

Semidefinite Programming Bounds on the Size of Entanglement-Assisted Codeword Stabilized Quantum Codes

Ching–Yi Lai, Pin-Chieh Tseng, Wei-Hsuan Yu

In this paper, we explore the application of semidefinite programming to the realm of quantum codes, specifically focusing on codeword stabilized (CWS) codes with entanglement assistance. Notably, we utilize the isotropic subgroup of the CWS group and the set of word operators of a CWS-type quantum code to derive an upper bound on the minimum distance. Furthermore, this characterization can be incorporated into the associated distance enumerators, enabling us to construct semidefinite constraints that lead to SDP bounds on the minimum distance or size of CWS-type quantum codes. We illustrate several instances where SDP bounds outperform LP bounds, and there are even cases where LP fails to yield meaningful results, while SDP consistently provides tighter and relevant bounds. Finally, we also provide interpretations of the Shor-Laflamme weight enumerators and shadow enumerators for codeword stabilized codes, enhancing our understanding of quantum codes.

arXiv:2311.07111•IEEE Transactions on Information Theory•Jul 25, 2024•2 citations

Quantum query complexity and semi-definite programming

Howard Barnum, Michael Saks, Márió Szegedy

We reformulate quantum query complexity in terms of inequalities and equations for a set of positive semidefinite matrices. Using the new formulation we: 1) show that the workspace of a quantum computer can be limited to at most n+k qubits (where n and k are the number of input and output bits respectively) without reducing the computational power of the model; 2) give an algorithm that on input the truth table of a partial Boolean function and an integer t runs in time polynomial in the size of the truth table and estimates, to any desired accuracy, the minimum probability of error that can be attained by a quantum query algorithm attempts to evaluate f in t queries; 3) use semidefinite programming duality to formulate a dual SDP P/spl circ/(f, t, /spl epsi/) that is feasible if and only if f cannot be evaluated within error /spl epsi/ by a t-step quantum query algorithm. Using this SDP, we derive a general lower bound for quantum query complexity that encompasses a lower bound method of Ambainis and its generalizations; 4) give an interpretation of a generalized form of branching in quantum computation.

IEEE Conference on Computational Complexity (CCC)•Mar 22, 2004•122 citations

Characterizing finite-dimensional quantum behavior

Miguel Navascués, Adrien Feix, Mateus Araújo +1 more

We study and extend the semidefinite programming (SDP) hierarchies introduced in Navascu\'es and V\'ertesi [Phys. Rev. Lett. 115, 020501 (2015)] for the characterization of the statistical correlations arising from finite-dimensional quantum systems. First, we introduce the dimension-constrained noncommutative polynomial optimization (NPO) paradigm, where a number of polynomial inequalities are defined and optimization is conducted over all feasible operator representations of bounded dimensionality. Important problems in device-independent and semi-device-independent quantum information science can be formulated (or almost formulated) in this framework. We present effective SDP hierarchies to attack the general dimension-constrained NPO problem (and related ones) and prove their asymptotic convergence. To illustrate the power of these relaxations, we use them to derive a number of dimension witnesses for temporal and Bell-type correlation scenarios, and also to bound the probability of success of quantum random access codes.

arXiv:1507.07521•Physical Review A•Oct 21, 2015•55 citations
This paper provides a semidefinite programming hierarchy based on state polynomial optimization to determine the existence of quantum codes with given parameters. The hierarchy is complete, in the sense that a ( ⁣(n,K,δ) ⁣)2(\!(n, K, δ)\!)_2((n,K,δ))2​ code exists if and only if every level of the hierarchy is feasible. It is not limited to stabilizer codes and thus is applicable generally. While the machinery is formally dimension-free, we restrict it to qubit codes through quasi-Clifford algebras. We derive the quantum analog of a range of classical results: first, from an intermediate level a Lovász bound for self-dual quantum codes is recovered. Second, a symmetrization of a minor variation of this Lovász bound recovers the quantum Delsarte bound. Third, a symmetry reduction using the Terwilliger algebra leads to semidefinite programming bounds of size O(n4)O(n^4)O(n4). With this we give an alternative proof that there is no ( ⁣(7,1,4) ⁣)2(\!(7, 1, 4)\!)_2((7,1,4))2​ quantum code, and show that ( ⁣(8,9,3) ⁣)2(\!(8, 9, 3)\!)_2((8,9,3))2​ and ( ⁣(10,5,4) ⁣)2(\!(10, 5, 4)\!)_2((10,5,4))2​ codes do not exist.
A fundamental problem in quantum coding theory is to determine the maximum size of quantum codes of given block length and distance. A recent work introduced bounds based on semidefinite programming, strengthening the well-known quantum linear programming bounds. However, floating-point inaccuracies prevent the extraction of rigorous non-existence proofs from the numerical methods. Here, we address this by providing rational infeasibility certificates for a range of quantum codes. Using a clustered low-rank solver with heuristic rounding to algebraic expressions, we can improve upon 181818 upper bounds on the maximum size of nnn-qubit codes with 6≤n≤196 \leq n \leq 196≤n≤19. Our work highlights the practicality and scalability of semidefinite programming for quantum coding bounds.
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.
We study optimization programs given by a bilinear form over noncommutative variables subject to linear inequalities. Problems of this form include the entangled value of two-prover games, entanglement-assisted coding for classical channels, and quantum-proof randomness extractors. We introduce an asymptotically converging hierarchy of efficiently computable semidefinite programming (SDP) relaxations for this quantum optimization. This allows us to give upper bounds on the quantum advantage for all of these problems. Compared to previous work of Pironio, Navascués, and Acín [SIAM J. Optim., 20 (2010), pp. 2157--2180], our hierarchy has additional constraints. By means of examples, we illustrate the importance of these new constraints both in practice and for analytical properties. Moreover, this allows us to give a hierarchy of SDP outer approximations for the completely positive semidefinite cone introduced by Laurent and Piovesan.
In this paper, we explore the application of semidefinite programming to the realm of quantum codes, specifically focusing on codeword stabilized (CWS) codes with entanglement assistance. Notably, we utilize the isotropic subgroup of the CWS group and the set of word operators of a CWS-type quantum code to derive an upper bound on the minimum distance. Furthermore, this characterization can be incorporated into the associated distance enumerators, enabling us to construct semidefinite constraints that lead to SDP bounds on the minimum distance or size of CWS-type quantum codes. We illustrate several instances where SDP bounds outperform LP bounds, and there are even cases where LP fails to yield meaningful results, while SDP consistently provides tighter and relevant bounds. Finally, we also provide interpretations of the Shor-Laflamme weight enumerators and shadow enumerators for codeword stabilized codes, enhancing our understanding of quantum codes.
We reformulate quantum query complexity in terms of inequalities and equations for a set of positive semidefinite matrices. Using the new formulation we: 1) show that the workspace of a quantum computer can be limited to at most n+k qubits (where n and k are the number of input and output bits respectively) without reducing the computational power of the model; 2) give an algorithm that on input the truth table of a partial Boolean function and an integer t runs in time polynomial in the size of the truth table and estimates, to any desired accuracy, the minimum probability of error that can be attained by a quantum query algorithm attempts to evaluate f in t queries; 3) use semidefinite programming duality to formulate a dual SDP P/spl circ/(f, t, /spl epsi/) that is feasible if and only if f cannot be evaluated within error /spl epsi/ by a t-step quantum query algorithm. Using this SDP, we derive a general lower bound for quantum query complexity that encompasses a lower bound method of Ambainis and its generalizations; 4) give an interpretation of a generalized form of branching in quantum computation.
We study and extend the semidefinite programming (SDP) hierarchies introduced in Navascu\'es and V\'ertesi [Phys. Rev. Lett. 115, 020501 (2015)] for the characterization of the statistical correlations arising from finite-dimensional quantum systems. First, we introduce the dimension-constrained noncommutative polynomial optimization (NPO) paradigm, where a number of polynomial inequalities are defined and optimization is conducted over all feasible operator representations of bounded dimensionality. Important problems in device-independent and semi-device-independent quantum information science can be formulated (or almost formulated) in this framework. We present effective SDP hierarchies to attack the general dimension-constrained NPO problem (and related ones) and prove their asymptotic convergence. To illustrate the power of these relaxations, we use them to derive a number of dimension witnesses for temporal and Bell-type correlation scenarios, and also to bound the probability of success of quantum random access codes.