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

A Note on Cyclotomic Cosets, an Algorithm for finding Coset Representatives and Size, and a Theorem on the Quantum evaluation of Weight Enumerators for a Certain Class of Cyclic Codes

Joseph Geraci, Frank Van Bussel

Published Mar 26, 2007• 2 citations
OpenAlex

Abstract

We provide an overview of cyclotomic cosets and discuss applications including how they can be used to speed up the computation of the Weight Enumerator polynomial (which is related to the Potts partition function). We also give an algorithm which returns the coset leaders and the size of each coset from the list $\{0,1,2,...,N-1\}$, whose time complexity is O(N). We also provide a theorem on the quantum computation of the Weight Enumerator polynomial for a certain family of cyclic codes.

Related papers

A theorem on the quantum evaluation of Weight Enumerators for a certain class of Cyclic Codes with a note on Cyclotomic cosets

Joseph Geraci, Frank Van Bussel

This note is a stripped down version of a published paper on the Potts partition function, where we concentrate solely on the linear coding aspect of our approach. It is meant as a resource for people interested in coding theory but who do not know much of the mathematics involved and how quantum computation may provide a speed up in the computation of a very important quantity in coding theory. We provide a theorem on the quantum computation of the Weight Enumerator polynomial for a restricted family of cyclic codes. The complexity of obtaining an exact evaluation is $O(k^{2s}(\log q)^{2})$, where $s$ is a parameter which determines the class of cyclic codes in question, $q$ is the characteristic of the finite field over which the code is defined, and $k$ is the dimension of the code. We also provide an overview of cyclotomic cosets and discuss applications including how they can be used to speed up the computation of the weight enumerator polynomial (which is related to the Potts partition function). We also give an algorithm which returns the coset leaders and the size of each coset from the list $\{0,1,2,...,N-1\}$, whose time complexity is soft-O(N). This algorithm uses standard techniques but we include it as a resource for students. Note that cyclotomic cosets do not improve the asymptotic complexity of the computation of weight enumerators.

arXiv:cs/0703129•Mar 26, 2007•2 citations

Quantum variations of cyclotomic cosets for cyclic stabiliser codes construction

En Chong Yap, Kai Lin Ong

Abstract Cyclotomic cosets are intrinsically linked with the design and construction of classical cyclic codes whose properties can be inferred from the coset structures. This paper proposes some new quantum variations of cyclotomic cosets for cyclic stabiliser construction. These variations are governed by several parameters which are devoted to designing the two essential parts: the error part and the position part of these cosets. Criteria on these cosets in generating additive cyclic stabiliser are extensively studied, followed by actual implementation on stabiliser codes construction of several selected classes of length.

Quantum Information Processing•Jun 17, 2024•2 citations

Cyclotomic cosets and quantum BCH codes

Fangying Xiao, Hanwu Chen

In order to constructing quantum BCH codes from classical BCH codes using CSS constructing method it needs to determine whether the BCH codes contains its dual. Cyclotomic cosets play very important roles in classical error correction theory and quantum error correction theory. This letter presented several properties of cyclotomic cosets and introduced a method to determine whether a non-primitive BCH code over GF (q) contains its dual. The method presented in this paper with polynomial time complexity can also be applied to nonnarrow sense primitive BCH codes.

International Conference on Natural Computation (ICNC)•Aug 1, 2010•2 citations

Families of Cyclic Codes over Finite Chain Rings

Andrew Nemec

A major difficulty in quantum computation and communication is preventing and correcting errors in the quantum bits. Most of the research in this area has focused on stabilizer codes derived from self-orthogonal cyclic error-correcting codes over finite fields. Our goal is to develop a similar theory for self-orthogonal cyclic codes over the class of finite chain rings which have been proven to also produce stabilizer codes. We also will discuss these restrictions on families of cyclic codes, including, but not limited to quadratic residue codes and Bose-Chaudhuri-Hocquenghem codes. Finally, we will extend the concepts of weight enumerators to the class of Frobenius rings and use them to derive bounds for our codes.

•Sep 29, 2015•0 citations

QUANTUM CODES CONSTRUCTED FROM BINARY CYCLIC CODES

Ruihu Li, Xueliang Li

In this paper, we use 2-cyclotomic cosets of modulo n and generator polynomials to describe binary cyclic codes of length N=2αn with n odd. We discuss the conditions under which two cyclic codes [Formula: see text] and [Formula: see text] can be used to construct quantum codes by CSS construction or Steane's construction. Using the results of Chen, Promhouse and Tavares, and Castagnoli et al., we study the quantum codes that can be constructed from binary cyclic codes of length N=2αn with n odd and n≤99, and α≤2. We find that except the quantum codes constructed by Steane, there are also some very interesting quantum codes constructed from repeated-root cyclic codes, and some of the quantum codes constructed by Steane can be improved.

International Journal of Quantum Information•Jun 1, 2004•27 citations

On the relation between quantum computation and classical statistical mechanics

Joseph Geraci

We provide a quantum algorithm for the exact evaluation of the Potts partition function for a certain class of restricted instances of graphs that correspond to irreducible cyclic codes. We use the same approach to demonstrate that quantum computers can provide an exponential speed up over the best classical algorithms for the exact evaluation of the weight enumerator polynomial for a family of classical cyclic codes. In addition to this we also provide an efficient quantum approximation algorithm for a function (signed-Euler generating function) closely related to the Ising partition function and demonstrate that this problem is BQP-complete. \n\nWe accomplish the above for the Potts partition function by using a series of links between Gauss sums, classical coding theory, graph theory and the partition function. We exploit the fact that there exists an efficient approximation algorithm for Gauss sums and the fact that this problem is equivalent in complexity to evaluating discrete log. A theorem of McEliece allows one to turn the Gauss sum approximation into an exact evaluation of the Potts partition function. Stripping the physics from this result leaves one with the result for the weight enumerator polynomial. \n\nThe result for the approximation of the signed-Euler generating function was accomplished by fashioning a new mapping between quantum circuits and graphs. The mapping provided us with a way of relating the cycle structure of graphs with quantum circuits. Using a slight variant of this mapping, we present the final result of this thesis which presents a way of testing families of quantum circuits for their classical simulatability. We thus provide an efficient way of deciding whether a quantum circuit provides any additional computational power over classical computation and this is achieved by exploiting the fact that planar instances of the Ising partition function (with no external magnetic field) can be efficiently classically computed.

•Jan 1, 2008•0 citations
We provide an overview of cyclotomic cosets and discuss applications
including how they can be used to speed up the computation of the Weight
Enumerator polynomial (which is related to the Potts partition function). We
also give an algorithm which returns the coset leaders and the size of each
coset from the list {0,1,2,...,N−1}\{0,1,2,...,N-1\}{0,1,2,...,N−1}, whose time complexity is O(N). We also
provide a theorem on the quantum computation of the Weight Enumerator
polynomial for a certain family of cyclic codes.
This note is a stripped down version of a published paper on the Potts partition function, where we concentrate solely on the linear coding aspect of our approach. It is meant as a resource for people interested in coding theory but who do not know much of the mathematics involved and how quantum computation may provide a speed up in the computation of a very important quantity in coding theory. We provide a theorem on the quantum computation of the Weight Enumerator polynomial for a restricted family of cyclic codes. The complexity of obtaining an exact evaluation is O(k2s(log⁡q)2)O(k^{2s}(\log q)^{2})O(k2s(logq)2), where sss is a parameter which determines the class of cyclic codes in question, qqq is the characteristic of the finite field over which the code is defined, and kkk is the dimension of the code. We also provide an overview of cyclotomic cosets and discuss applications including how they can be used to speed up the computation of the weight enumerator polynomial (which is related to the Potts partition function). We also give an algorithm which returns the coset leaders and the size of each coset from the list {0,1,2,...,N−1}\{0,1,2,...,N-1\}{0,1,2,...,N−1}, whose time complexity is soft-O(N). This algorithm uses standard techniques but we include it as a resource for students. Note that cyclotomic cosets do not improve the asymptotic complexity of the computation of weight enumerators.
Abstract Cyclotomic cosets are intrinsically linked with the design and construction of classical cyclic codes whose properties can be inferred from the coset structures. This paper proposes some new quantum variations of cyclotomic cosets for cyclic stabiliser construction. These variations are governed by several parameters which are devoted to designing the two essential parts: the error part and the position part of these cosets. Criteria on these cosets in generating additive cyclic stabiliser are extensively studied, followed by actual implementation on stabiliser codes construction of several selected classes of length.
In order to constructing quantum BCH codes from classical BCH codes using CSS constructing method it needs to determine whether the BCH codes contains its dual. Cyclotomic cosets play very important roles in classical error correction theory and quantum error correction theory. This letter presented several properties of cyclotomic cosets and introduced a method to determine whether a non-primitive BCH code over GF (q) contains its dual. The method presented in this paper with polynomial time complexity can also be applied to nonnarrow sense primitive BCH codes.
A major difficulty in quantum computation and communication is preventing and correcting errors in the quantum bits. Most of the research in this area has focused on stabilizer codes derived from self-orthogonal cyclic error-correcting codes over finite fields. Our goal is to develop a similar theory for self-orthogonal cyclic codes over the class of finite chain rings which have been proven to also produce stabilizer codes. We also will discuss these restrictions on families of cyclic codes, including, but not limited to quadratic residue codes and Bose-Chaudhuri-Hocquenghem codes. Finally, we will extend the concepts of weight enumerators to the class of Frobenius rings and use them to derive bounds for our codes.
In this paper, we use 2-cyclotomic cosets of modulo n and generator polynomials to describe binary cyclic codes of length N=2αn with n odd. We discuss the conditions under which two cyclic codes [Formula: see text] and [Formula: see text] can be used to construct quantum codes by CSS construction or Steane's construction. Using the results of Chen, Promhouse and Tavares, and Castagnoli et al., we study the quantum codes that can be constructed from binary cyclic codes of length N=2αn with n odd and n≤99, and α≤2. We find that except the quantum codes constructed by Steane, there are also some very interesting quantum codes constructed from repeated-root cyclic codes, and some of the quantum codes constructed by Steane can be improved.
We provide a quantum algorithm for the exact evaluation of the Potts partition function for a certain class of restricted instances of graphs that correspond to irreducible cyclic codes. We use the same approach to demonstrate that quantum computers can provide an exponential speed up over the best classical algorithms for the exact evaluation of the weight enumerator polynomial for a family of classical cyclic codes. In addition to this we also provide an efficient quantum approximation algorithm for a function (signed-Euler generating function) closely related to the Ising partition function and demonstrate that this problem is BQP-complete. \n\nWe accomplish the above for the Potts partition function by using a series of links between Gauss sums, classical coding theory, graph theory and the partition function. We exploit the fact that there exists an efficient approximation algorithm for Gauss sums and the fact that this problem is equivalent in complexity to evaluating discrete log. A theorem of McEliece allows one to turn the Gauss sum approximation into an exact evaluation of the Potts partition function. Stripping the physics from this result leaves one with the result for the weight enumerator polynomial. \n\nThe result for the approximation of the signed-Euler generating function was accomplished by fashioning a new mapping between quantum circuits and graphs. The mapping provided us with a way of relating the cycle structure of graphs with quantum circuits. Using a slight variant of this mapping, we present the final result of this thesis which presents a way of testing families of quantum circuits for their classical simulatability. We thus provide an efficient way of deciding whether a quantum circuit provides any additional computational power over classical computation and this is achieved by exploiting the fact that planar instances of the Ising partition function (with no external magnetic field) can be efficiently classically computed.