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:1907.04537 · Physical Review A

Heuristic construction of codeword stabilized codes

Alex Rigby, Jan Corne Olivier, Peter Jarvis

Published Dec 2, 2019• 4 citations
arXivHTMLPDF

Abstract

The family of codeword stabilized codes encompasses the stabilizer codes as well as many of the best known nonadditive codes. However, constructing optimal $n$-qubit codeword stabilized codes is made difficult by two main factors. The first of these is the exponential growth with $n$ of the number of graphs on which a code can be based. The second is the NP-hardness of the maximum clique search required to construct a code from a given graph. We address the second of these issues through the use of a heuristic clique finding algorithm. This approach has allowed us to find $((9,97\ensuremath{\le}K\ensuremath{\le}100,2))$ and $((11,387\ensuremath{\le}K\ensuremath{\le}416,2))$ codes, which are larger than any previously known codes. To address the exponential growth of the search space, we demonstrate that graphs that give large codes typically yield clique graphs with a large number of nodes. The number of such nodes can be determined relatively efficiently, and we demonstrate that $n$-node graphs yielding large clique graphs can be found using a genetic algorithm. This algorithm uses a crossover operation based on spectral bisection that we demonstrate to be superior to more standard crossover operations. Using this genetic algorithm approach, we have found ((13, 18, 4)) and ((13, 20, 4)) codes that are larger than any previously known code. We also consider codes for the amplitude damping channel. We demonstrate that for $n\ensuremath{\le}9$, optimal codeword stabilized codes correcting a single amplitude damping error can be found by considering standard form codes that detect one of only three of the ${3}^{n}$ possible equivalent error sets. By combining this error-set selection with the genetic algorithm approach, we have found ((11, 68)) and ((11, 80)) codes capable of correcting a single amplitude damping error and ((11, 4)), ((12, 4)), ((13, 8)), and ((14, 16)) codes capable of correcting two amplitude damping errors.

DOI
10.1103/physreva.100.062303

Related papers

Codeword stabilized quantum codes: Algorithm and structure

Isaac L. Chuang, Andrew W. Cross, Graeme Smith +2 more

The codeword stabilized (CWS) quantum code formalism presents a unifying approach to both additive and nonadditive quantum error-correcting codes [IEEE Trans. Inf. Theory 55, 433 (2009)]. This formalism reduces the problem of constructing such quantum codes to finding a binary classical code correcting an error pattern induced by a graph state. Finding such a classical code can be very difficult. Here, we consider an algorithm which maps the search for CWS codes to a problem of identifying maximum cliques in a graph. While solving this problem is in general very hard, we provide three structure theorems which reduce the search space, specifying certain admissible and optimal ((n,K,d)) additive codes. In particular, we find that the re does not exist any ((7,3,3)) CWS code though the linear programming bound does not rule it out. The complexity of the CWS-search algorithm is compared with the contrasting method introduced by Aggarwal and Calderbank [IEEE Trans. Inf. Theory 54, 1700 (2008)].

arXiv:0803.3232•Journal of Mathematical Physics•Apr 1, 2009•40 citations

Graphical Quantum Error-Correcting Codes

Sixia Yu, Qing Chen, Choo Hiap Oh

We introduce a purely graph-theoretical object, namely the coding clique, to construct quantum errorcorrecting codes. Almost all quantum codes constructed so far are stabilizer (additive) codes and the construction of nonadditive codes, which are potentially more efficient, is not as well understood as that of stabilizer codes. Our graphical approach provides a unified and classical way to construct both stabilizer and nonadditive codes. In particular we have explicitly constructed the optimal ((10,24,3)) code and a family of 1-error detecting nonadditive codes with the highest encoding rate so far. In the case of stabilizer codes a thorough search becomes tangible and we have classified all the extremal stabilizer codes up to 8 qubits.

arXiv:0709.1780•Sep 12, 2007•64 citations

Clustered Error Correction of Codeword-Stabilized Quantum Codes

Yunfan Li, Ilya I. Dumer, Leonid P. Pryadko

Codeword-stabilized codes are a general class of quantum codes that includes stabilizer codes and many families of nonadditive codes with good parameters. For such a nonadditive code correcting all t-qubit errors, we propose an algorithm that employs a single measurement to test all errors located on a given set of t qubits. Compared with exhaustive error screening, this reduces the total number of measurements required for error recovery by a factor of about 3(t).

arXiv:0907.2038•Physical Review Letters•May 10, 2010•9 citations

High Performance Single-Error-Correcting Quantum Codes for Amplitude Damping

Peter W. Shor, Graeme Smith, John A. Smolin +1 more

We construct families of high performance quantum amplitude damping codes. All of our codes are nonadditive and most modestly outperform the best possible additive codes in terms of encoded dimension. One family is built from nonlinear error-correcting codes for classical asymmetric channels, with which we systematically construct quantum amplitude damping codes with parameters better than any prior construction known for any block lengthn≥ 8 exceptn=2r-1. We generalize this construction to employ classical codes overGF(3) with which we numerically obtain better performing codes up to length 14. Because the resulting codes are of the codeword stabilized (CWS) type, conceptually simple (though potentially computationally expensive) encoding and decoding circuits are available.

arXiv:0907.5149•IEEE Transactions on Information Theory•Oct 1, 2011•36 citations

Codeword stabilized quantum codes for asymmetric channels

Tyler Jackson, Markus Grassl, Bei Zeng

In this study we present a method that adapts the codeword stabilized (CWS) quantum code framework to the problem of finding asymmetric quantum codes. Making use of the the corresponding Pauli error models for amplitude and phase-damping models, we focus on codes that correct one or two amplitude-damping errors. As a result, we are able to exhaustively search for all possible codes up to length 9 by applying local Clifford operations on graph states. With a similar method, we also look at codes for the Pauli error models that detect a single amplitude error and detect multiple phase damping errors. Many new codes with good parameters are found, including non-additive codes and degenerate codes.

arXiv:1601.05763•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•9 citations

Codeword Stabilized Quantum Codes and Their Error Correction

Yunfan Li

Quantum decoherence and errors represent some of the major challenges arising in quantum computations. Quantum error correcting codes protect quantum states against these errors and make quantum computing more reliable. One of the main problems of quantum error correction is the design of feasible decoding algorithms that can simplify error-correction for general quantum codes. The dissertation addresses decoding of general Codeword Stabilized (CWS) codes. This class of quantum codes also includes some other important classes such as additive Stabilizer codes and non-additive Union Stabilizer (USt) codes.We first design a generic error-correcting algorithm for CWS codes and analyze the number of decoding measurements and quantum gates. This algorithm performs exhaustive screening of different error patterns, similar to decoding of classical non-linear codes. For an n-qubit quantum code correcting up to t erroneous qubits, this brute-force approach consecutively tests all correctable error patterns and employs a separate n-qubit measurement in each test.The main result is a new error grouping technique that enables simultaneous testing of large groups of errors in a single measurement. To achieve this reduction, we first proceed with a new error-correction algorithm for the USt codes. Secondly, we design an algorithm that converts generic non-linear CWS codes into the simpler quasi-linear USt codes. Each decoding measurement can then either locate the actual error in a given group of errors or entirely eliminate this group. This technique yields a much simpler algorithm that exponentially reduces the number of measurements about 3^t times in any t-error-correcting CWS code.

•Jan 1, 2010•0 citations
The family of codeword stabilized codes encompasses the stabilizer codes as well as many of the best known nonadditive codes. However, constructing optimal nnn-qubit codeword stabilized codes is made difficult by two main factors. The first of these is the exponential growth with nnn of the number of graphs on which a code can be based. The second is the NP-hardness of the maximum clique search required to construct a code from a given graph. We address the second of these issues through the use of a heuristic clique finding algorithm. This approach has allowed us to find ((9,97\ensuremath≤K\ensuremath≤100,2))((9,97\ensuremath{\le}K\ensuremath{\le}100,2))((9,97\ensuremath≤K\ensuremath≤100,2)) and ((11,387\ensuremath≤K\ensuremath≤416,2))((11,387\ensuremath{\le}K\ensuremath{\le}416,2))((11,387\ensuremath≤K\ensuremath≤416,2)) codes, which are larger than any previously known codes. To address the exponential growth of the search space, we demonstrate that graphs that give large codes typically yield clique graphs with a large number of nodes. The number of such nodes can be determined relatively efficiently, and we demonstrate that nnn-node graphs yielding large clique graphs can be found using a genetic algorithm. This algorithm uses a crossover operation based on spectral bisection that we demonstrate to be superior to more standard crossover operations. Using this genetic algorithm approach, we have found ((13, 18, 4)) and ((13, 20, 4)) codes that are larger than any previously known code. We also consider codes for the amplitude damping channel. We demonstrate that for n\ensuremath≤9n\ensuremath{\le}9n\ensuremath≤9, optimal codeword stabilized codes correcting a single amplitude damping error can be found by considering standard form codes that detect one of only three of the 3n{3}^{n}3n possible equivalent error sets. By combining this error-set selection with the genetic algorithm approach, we have found ((11, 68)) and ((11, 80)) codes capable of correcting a single amplitude damping error and ((11, 4)), ((12, 4)), ((13, 8)), and ((14, 16)) codes capable of correcting two amplitude damping errors.
The codeword stabilized (CWS) quantum code formalism presents a unifying approach to both additive and nonadditive quantum error-correcting codes [IEEE Trans. Inf. Theory 55, 433 (2009)]. This formalism reduces the problem of constructing such quantum codes to finding a binary classical code correcting an error pattern induced by a graph state. Finding such a classical code can be very difficult. Here, we consider an algorithm which maps the search for CWS codes to a problem of identifying maximum cliques in a graph. While solving this problem is in general very hard, we provide three structure theorems which reduce the search space, specifying certain admissible and optimal ((n,K,d)) additive codes. In particular, we find that the re does not exist any ((7,3,3)) CWS code though the linear programming bound does not rule it out. The complexity of the CWS-search algorithm is compared with the contrasting method introduced by Aggarwal and Calderbank [IEEE Trans. Inf. Theory 54, 1700 (2008)].
We introduce a purely graph-theoretical object, namely the coding clique, to construct quantum errorcorrecting codes. Almost all quantum codes constructed so far are stabilizer (additive) codes and the construction of nonadditive codes, which are potentially more efficient, is not as well understood as that of stabilizer codes. Our graphical approach provides a unified and classical way to construct both stabilizer and nonadditive codes. In particular we have explicitly constructed the optimal ((10,24,3)) code and a family of 1-error detecting nonadditive codes with the highest encoding rate so far. In the case of stabilizer codes a thorough search becomes tangible and we have classified all the extremal stabilizer codes up to 8 qubits.
We construct families of high performance quantum amplitude damping codes. All of our codes are nonadditive and most modestly outperform the best possible additive codes in terms of encoded dimension. One family is built from nonlinear error-correcting codes for classical asymmetric channels, with which we systematically construct quantum amplitude damping codes with parameters better than any prior construction known for any block lengthn≥ 8 exceptn=2r-1. We generalize this construction to employ classical codes overGF(3) with which we numerically obtain better performing codes up to length 14. Because the resulting codes are of the codeword stabilized (CWS) type, conceptually simple (though potentially computationally expensive) encoding and decoding circuits are available.
In this study we present a method that adapts the codeword stabilized (CWS) quantum code framework to the problem of finding asymmetric quantum codes. Making use of the the corresponding Pauli error models for amplitude and phase-damping models, we focus on codes that correct one or two amplitude-damping errors. As a result, we are able to exhaustively search for all possible codes up to length 9 by applying local Clifford operations on graph states. With a similar method, we also look at codes for the Pauli error models that detect a single amplitude error and detect multiple phase damping errors. Many new codes with good parameters are found, including non-additive codes and degenerate codes.
Quantum decoherence and errors represent some of the major challenges arising in quantum computations. Quantum error correcting codes protect quantum states against these errors and make quantum computing more reliable. One of the main problems of quantum error correction is the design of feasible decoding algorithms that can simplify error-correction for general quantum codes. The dissertation addresses decoding of general Codeword Stabilized (CWS) codes. This class of quantum codes also includes some other important classes such as additive Stabilizer codes and non-additive Union Stabilizer (USt) codes.We first design a generic error-correcting algorithm for CWS codes and analyze the number of decoding measurements and quantum gates. This algorithm performs exhaustive screening of different error patterns, similar to decoding of classical non-linear codes. For an n-qubit quantum code correcting up to t erroneous qubits, this brute-force approach consecutively tests all correctable error patterns and employs a separate n-qubit measurement in each test.The main result is a new error grouping technique that enables simultaneous testing of large groups of errors in a single measurement. To achieve this reduction, we first proceed with a new error-correction algorithm for the USt codes. Secondly, we design an algorithm that converts generic non-linear CWS codes into the simpler quasi-linear USt codes. Each decoding measurement can then either locate the actual error in a given group of errors or entirely eliminate this group. This technique yields a much simpler algorithm that exponentially reduces the number of measurements about 3^t times in any t-error-correcting CWS code.