Codes and Graphs

Yuta Kumano, Yoshiyuki Sakamaki, Hironori Uchikawa

Graph codes are constructed from undirected graphs where the code symbols correspond to the edges and component codes are associated with the vertices. We investigate graph codes on multigraphs whereas previous work has mainly studied them on simple graphs. This paper proposes graph codes constructed from complete multipartite graphs as generalizations of block-wise product codes. The graph codes show better error-correcting performance in error-floor region compared with block-wise product codes. This paper also shows an efficient encoding method for the graph codes by employing Richardson and Urbanke's encoding algorithm for LDPC codes.

Toyokazu Hiramatsu, Günter Köhler

Anton Betten, Harald Fripertinger, Adalbert Kerber +2 more

Yongsoo Hwang, Jun Heo

A graph state and a graph code respectively are defined based on a mathematical simple graph. In this work, we examine a relation between a graph state and a graph code both obtained from the same graph, and show that a graph state is a superposition of logical qubits of the related graph code. By using the relation, we first discuss that a local complementation which has been used for a graph state can be useful for searching locally equivalent stabilizer codes, and second provide a method to find a stabilizer group of a graph code.

Masanori Ohya, Igor Vasil'evich Volovich

Salman Beigi, Isaac L. Chuang, Markus Grassl +2 more

Graphs are closely related to quantum error-correcting codes: every stabilizer code is locally equivalent to a graph code and every codeword stabilized code can be described by a graph and a classical code. For the construction of good quantum codes of relatively large block length, concatenated quantum codes and their generalizations play an important role. We develop a systematic method for constructing concatenated quantum codes based on “graph concatenation,” where graphs representing the inner and outer codes are concatenated via a simple graph operation called “generalized local complementation.” Our method applies to both binary and nonbinary concatenated quantum codes as well as their generalizations.