SDP bounds on quantum codes: rational certificates

• URL: http://arxiv.org/abs/2603.19901v1
• Date: Fri, 20 Mar 2026 12:33:38 GMT
• Title: SDP bounds on quantum codes: rational certificates
• Abstract summary: A fundamental problem in quantum coding theory is to determine the maximum size of quantum codes of given block length and distance.<n>Recent work introduced bounds based on semidefinite programming, strengthening the well-known quantum linear programming bounds.<n>We provide rational infeasibility certificates for a range of quantum codes.
• Score: 1.7188280334580195
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Tight inapproximability of max-LINSAT and implications for decoded quantum interferometry [0.0]
  We prove by a direct reduction from Hstad's theorem that no-time algorithm can exceed the randomassignment ratio $r/q$ by any constant.<n>This threshold coincides with the $ell/m to 0$ limit of the semicircle law governing decoded quantum interferometry.
  arXiv  Detail & Related papers  (2026-03-04T19:26:26Z)
• Fine-Grained Unambiguous Measurements [2.5782420501870296]
  We introduce the notion of fine-grained unambiguous measurements.<n>We show that determining the maximal number of parities that a measurement can output can be formulated as a linear program.<n>We discuss the implications of these findings for the Quantum Decoding Problem.
  arXiv  Detail & Related papers  (2025-10-08T17:53:08Z)
• Quantum Hypothesis Testing Lemma for Deterministic Identification over Quantum Channels [49.126395046088014]
  This work shows that the existence of a DI code in the quantum setting follows from a suitable packing in a modified space of output quantum states.<n>This result enables us to tighten the capacity lower bound for DI over quantum channels beyond the simultaneous decoding approach.
  arXiv  Detail & Related papers  (2025-04-29T17:57:36Z)
• SDP bounds on quantum codes [3.441021278275805]
  We show that there is no $(!(8, 9, 3)!)$ quantum code, and show that $(!(10, 5, 5)!)$ codes do not exist.<n>The hierarchy is complete, in the sense that a $(!(n, K, delta)!)$ code exists if and only if every level of the hierarchy is feasible.
  arXiv  Detail & Related papers  (2024-08-19T18:00:07Z)
• Approximate quantum error correcting codes from conformal field theory [0.0]
  We consider generic 1+1D CFT codes under extensive local dephasing channels. We show that a CFT code with continuous symmetry saturates a bound on the recovery fidelity for covariant codes.
  arXiv  Detail & Related papers  (2024-06-13T19:40:36Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
  arXiv  Detail & Related papers  (2023-03-02T14:18:17Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Connectivity constrains quantum codes [0.06091702876917279]
  We study the limitations of quantum LDPC codes associated with local graphs in $D$-dimensional hyperbolic space. We find that unless the connectivity graph contains an expander, the code is severely limited. As an application, we present novel bounds on quantum LDPC codes associated with local graphs in $D$-dimensional hyperbolic space.
  arXiv  Detail & Related papers  (2021-06-01T20:03:16Z)
• Entropic proofs of Singleton bounds for quantum error-correcting codes [0.5156484100374058]
  We show that a relatively simple reasoning using von Neumann entropy inequalities yields a robust proof of the quantum Singleton bound for quantum error-correcting codes (QECC) We also prove information-theoretically tight bounds on the entanglement-communication tradeoff for EAQECC.
  arXiv  Detail & Related papers  (2020-10-15T17:28:36Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.