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

Quantum Information Processing

Classes of quantum codes derived from self-dual orientable embeddings of complete multipartite graphs

Avaz Naghipour, M. A. Jafarizadeh

Published Oct 27, 2017• 0 citations
Publisher
DOI
10.1007/s11128-017-1753-1

Related papers

Topological quantum codes from self-complementary self-dual graphs

Avaz Naghipour, M. A. Jafarizadeh, S. Shahmorad

Quantum Information Processing•Sep 3, 2015•6 citations

Construction of quantum codes from new embeddings of graphs on compact surfaces

Avaz Naghipour

Optical and Quantum Electronics•Dec 17, 2019•2 citations

Construction of quantum codes based on self-dual orientable embeddings of complete multipartite graphs complete multipartite graphs

Avaz Naghipour, M. A. Jafarizadeh, S. Shahmorad

This paper presents four new classes of binary quantum codes with minimum dis- tance 3 and 4, namely Class-I, Class-II, Class-III and Class-IV. The classes Class-I and Class-II are constructed based on self-dual orientable embeddings of the com- plete graphs K4r+1 and K4s and by current graphs and rotation schemes. and s are both divisible by 4.

arXiv:1507.01536•Jul 6, 2015•0 citations

Metric Self-Dual Completion and Optimal Additive Hardness for Quantum and Graph-State Distance

Rafail Ostrovsky

We prove that the quantum code distance is NP-hard to approximate within an additive error of $c N$, for some constant $c >0$, where $N$ is the number of qubits. Our reductions are deterministic. This improves the previous square-root additive gap to $Ω(N)$ and resolves the explicitly stated linear-gap question of Kapshikar and Kundu. Our result holds for CSS codes with identical $X$- and $Z$-check spaces, and with a constant rate and constant relative distance. For every fixed $λ>1$, there is a constant $c>0$ such that hardness still holds even when every nonidentity stabilizer has weight greater than $λ$ times the quantum distance. We also improve the hardness gap of graph state distance on $N$ vertices of Grigorescu, Jha, and Samperton from cube-root to $Ω(N)$, resolving their explicitly stated open question. Both hardness results are asymptotically optimal since both distances are at most $N$. Our graph state distance hardness result holds for balanced bipartite graphs with a binary adjacency matrix that is its own inverse (mod 2). Our main technique for both hardness bounds above is classical: we show how to convert any code $C$ of length $m$ into a self-dual code $A(C)$ of length $N=Θ(m)$ while exactly doubling the original coset metric. The conversion is deterministic and efficient. We call it the metric self-dual completion of $C$. It comes with a linear embedding $τ: \mathbb F_2^m \hookrightarrow \mathbb F_2^N$. The embedding doubles all Hamming distances between vectors in $\mathbb F_2^m$ and all pairwise distances between corresponding cosets. The embedding also guarantees that all codewords of $A(C)$ of weight at most $2m$ are exactly $τ(C)$.

quant-pharXiv:2609.22669•Sep 22, 2026•0 citations

New classes of TQC associated with self-dual, quasi self-dual and denser tessellations

Clarice Dias de Albuquerque, Reginaldo Palazzo, Eduardo Brandani da Silva

In this paper we present six classes of topological quantum codes (TQC) on compact surfaces with genus $g\ge 2$. These codes are derived from self-dual, quasi self-dual and denser tessellations associated with embeddings of self-dual complete graphs and complete bipartite graphs on the corresponding compact surfaces. The majority of the new classes has the self-dual tessellations as their algebraic and geometric supporting mathematical structures. Every code achieves minimum distance 3 and its encoding rate is such that $\frac{k}{n} \rightarrow 1$ as $n \rightarrow \infty$, except for the one case where $\frac{k}{n} \rightarrow \frac{1}{3}$ as $n \rightarrow \infty$.

Quantum Information and Computation•Nov 1, 2010•9 citations

Topological quantum codes from self-complementary self-dual graphs

Avaz Naghipour, M. A. Jafarizadeh, S. Shahmorad

In this paper we present two new classes of binary quantum codes with minimum distance of at least three, by self-complementary self-dual orientable embeddings of voltage graphs and Paley graphs in the Galois field GF(pr), where p is a prime number and r is a positive integer. The parameters of two new classes of quantum codes are [[(2k+2)(8k+ 7); 2(8k^2+7k); d]] and [[(2k+2)(8k+9); 2(8k^2+9k+1); d]] respectively, where d>=3. For these quantum codes, the code rate approaches 1 as k goes to infinity.

arXiv:1503.05710•Mar 19, 2015•0 citations
We prove that the quantum code distance is NP-hard to approximate within an additive error of cNc NcN, for some constant c>0c >0c>0, where NNN is the number of qubits. Our reductions are deterministic. This improves the previous square-root additive gap to Ω(N)Ω(N)Ω(N) and resolves the explicitly stated linear-gap question of Kapshikar and Kundu. Our result holds for CSS codes with identical XXX- and ZZZ-check spaces, and with a constant rate and constant relative distance. For every fixed λ>1λ>1λ>1, there is a constant c>0c>0c>0 such that hardness still holds even when every nonidentity stabilizer has weight greater than λλλ times the quantum distance. We also improve the hardness gap of graph state distance on NNN vertices of Grigorescu, Jha, and Samperton from cube-root to Ω(N)Ω(N)Ω(N), resolving their explicitly stated open question. Both hardness results are asymptotically optimal since both distances are at most NNN. Our graph state distance hardness result holds for balanced bipartite graphs with a binary adjacency matrix that is its own inverse (mod 2). Our main technique for both hardness bounds above is classical: we show how to convert any code CCC of length mmm into a self-dual code A(C)A(C)A(C) of length N=Θ(m)N=Θ(m)N=Θ(m) while exactly doubling the original coset metric. The conversion is deterministic and efficient. We call it the metric self-dual completion of CCC. It comes with a linear embedding τ:F2m↪F2Nτ: \mathbb F_2^m \hookrightarrow \mathbb F_2^Nτ:F2m​↪F2N​. The embedding doubles all Hamming distances between vectors in F2m\mathbb F_2^mF2m​ and all pairwise distances between corresponding cosets. The embedding also guarantees that all codewords of A(C)A(C)A(C) of weight at most 2m2m2m are exactly τ(C)τ(C)τ(C).
In this paper we present six classes of topological quantum codes (TQC) on compact surfaces with genus g≥2g\ge 2g≥2. These codes are derived from self-dual, quasi self-dual and denser tessellations associated with embeddings of self-dual complete graphs and complete bipartite graphs on the corresponding compact surfaces. The majority of the new classes has the self-dual tessellations as their algebraic and geometric supporting mathematical structures. Every code achieves minimum distance 3 and its encoding rate is such that kn→1\frac{k}{n} \rightarrow 1nk​→1 as n→∞n \rightarrow \inftyn→∞, except for the one case where kn→13\frac{k}{n} \rightarrow \frac{1}{3}nk​→31​ as n→∞n \rightarrow \inftyn→∞.
In this paper we present two new classes of binary quantum codes with minimum distance of at least three, by self-complementary self-dual orientable embeddings of voltage graphs and Paley graphs in the Galois field GF(pr), where p is a prime number and r is a positive integer. The parameters of two new classes of quantum codes are [[(2k+2)(8k+ 7); 2(8k^2+7k); d]] and [[(2k+2)(8k+9); 2(8k^2+9k+1); d]] respectively, where d>=3. For these quantum codes, the code rate approaches 1 as k goes to infinity.