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

On Connections Between Graphs, Codes, Quantum States, and Boolean Functions

Lars Eirik Danielsen

Published May 28, 2008• 3 citations
OpenAlex

Abstract

We study objects that can be represented as graphs, error-correcting codes, quantum states, or Boolean functions. It is known that self-dual additive codes, which can also be interpreted as quantum states, can be represented as graphs, and that two codes are equivalent when the corresponding graphs are equivalent with respect to local complementation (LC). We give classifications of such codes. Circulant graph codes are introduced, and it is shown that some of these codes have highly regular graph representations. We show that the orbit of a bipartite graph under edge local complementation (ELC) corresponds to the equivalence class of a binary linear code. We classify ELC orbits, give a new method for classifying binary linear codes, and show that the information sets and the minimum distance of a code can be derived from the corresponding ELC orbit. Self-dual additive codes over GF(4) can also be interpreted as quadratic Boolean functions. In this context we define PARIHN, peak-to-average power ratio with respect to the {I, H, N}n transform, and prove that PARIHN equals the size of the maximum independent set over the associated LC orbit of graphs. We define the aperiodic propagation criteria (APC) of a Boolean function, and show that it is related to the minimum distance of a self-dual additive code over GF(4), and to the degree of entanglement in the associated quantum state. We give a generalization to non-quadratic Boolean functions, and relate APC to known cryptographic criteria. Interlace polynomials encode many properties of the LC and ELC orbits of a graph. We enumerate interlace polynomials and circle graphs, show that there exist non-unimodal interlace polynomials, and relate properties of interlace polynomials to properties of codes and quantum states. We define self-dual bent functions, and provide constructions and classifications.

Related papers

On Self-Dual Quantum Codes, Graphs, and Boolean Functions

Lars Eirik Danielsen

A short introduction to quantum error correction is given, and it is shown that zero-dimensional quantum codes can be represented as self-dual additive codes over GF(4) and also as graphs. We show that graphs representing several such codes with high minimum distance can be described as nested regular graphs having minimum regular vertex degree and containing long cycles. Two graphs correspond to equivalent quantum codes if they are related by a sequence of local complementations. We use this operation to generate orbits of graphs, and thus classify all inequivalent self-dual additive codes over GF(4) of length up to 12, where previously only all codes of length up to 9 were known. We show that these codes can be interpreted as quadratic Boolean functions, and we define non-quadratic quantum codes, corresponding to Boolean functions of higher degree. We look at various cryptographic properties of Boolean functions, in particular the propagation criteria. The new aperiodic propagation criterion (APC) and the APC distance are then defined. We show that the distance of a zero-dimensional quantum code is equal to the APC distance of the corresponding Boolean function. Orbits of Boolean functions with respect to the {I,H,N}^n transform set are generated. We also study the peak-to-average power ratio with respect to the {I,H,N}^n transform set (PAR_IHN), and prove that PAR_IHN of a quadratic Boolean function is related to the size of the maximum independent set over the corresponding orbit of graphs. A construction technique for non-quadratic Boolean functions with low PAR_IHN is proposed. It is finally shown that both PAR_IHN and APC distance can be interpreted as partial entanglement measures.

arXiv:quant-ph/0503236•Mar 31, 2005•30 citations

GRAPH-BASED CLASSIFICATION OF SELF-DUAL ADDITIVE CODES OVER FINITE FIELDS

Lars Eirik Danielsen

Abstract. Quantum stabilizer states over Fm can be represented as self-dual additive codes over F m 2. These codes can be represented as weighted graphs, and orbits of graphs under the generalized local complementation operation correspond to equivalence classes of codes. We have previously used this fact to classify self-dual additive codes over F4. In this paper we classify selfdual additive codes over F9, F16, and F25. Assuming that the classical MDS conjecture holds, we are able to classify all self-dual additive MDS codes over F9 by using an extension technique. We prove that the minimum distance of a self-dual additive code is related to the minimum vertex degree in the associated graph orbit. Circulant graph codes are introduced, and a computer search reveals that this set contains many strong codes. We show that some of these codes have highly regular graph representations. 1.

•Jan 1, 2008•15 citations

Spectral Properties of Boolean Functions, Graphs and Graph States

Constanza Riera

Generalisations of the bent property of a Boolean function are presented, by proposing spectral analysis of the Boolean function with respect to a well-chosen set of local unitary transforms. Quadratic Boolean functions are related to simple graphs and it is shown that the orbit generated by some graph transforms can be found within the spectra of certain unitary transform sets. The flat spectra of a quadratic Boolean function with respect to those transforms are related to modified versions of its associated adjacency matrix. The flat spectra of concrete recursive structures are found using this method. We derive a spectral interpretation of the interlace polynomials (in one or two variables) of a graph and we relate to one of them a quantum measure of entanglement of the associated quantum state. We characterise the values of the spectra of a quadratic Boolean function. We give a formula for the weight hierarchy for a binary linear code in terms of a modified interlace polynomial. We derive as well a spectral interpretation of the pivot operation on a graph and generalise this operation to hypergraphs. We enumerate the number of inequivalent pivot orbits for small numbers of vertices. We also construct a family of Boolean functions of degree higher than two with a large number of flat spectra with respect to the {I,H}n set of transforms, and compute a lower bound on this number. We show how to change the degree of a Boolean function via pivot operation. Finally, we give concrete formulae for the spectra of a wide range of vectors with respect to well-chosen transforms sets.

•Jan 1, 2005•5 citations

Local Equivalences of Graph States

Nathan Claudet

Graph states form a large family of quantum states that are in one-to-one correspondence with mathematical graphs. Graph states are used in many applications, such as measurement-based quantum computation, as multipartite entangled resources. It is thus crucial to understand when two such states have the same entanglement, i.e. when they can be transformed into each other using only local operations. In this case, we say that the graph states are LU-equivalent (local unitary). If the local operations are restricted to the so-called Clifford group, we say that the graph states are LC-equivalent (local Clifford). Interestingly, a simple graph rule called local complementation fully captures LC-equivalence, in the sense that two graph states are LC-equivalent if and only if the underlying graphs are related by a sequence of local complementations. While it was once conjectured that two LU-equivalent graph states are always LC-equivalent, counterexamples do exist and local complementation fails to fully capture the entanglement of graph states. We introduce in this thesis a generalization of local complementation that does fully capture LU-equivalence. Using this characterization, we prove the existence of an infinite strict hierarchy of local equivalences between LC- and LU-equivalence. This also leads to the design of a quasi-polynomial algorithm for deciding whether two graph states are LU-equivalent, and to a proof that two LU-equivalent graph states are LC-equivalent if they are defined on at most 19 qubits. Furthermore, we study graph states that are universal in the sense that any smaller graph state, defined on any small enough set of qubits, can be induced using only local operations. We provide bounds and an optimal, probabilistic construction.

quant-pharXiv:2511.22271•Nov 28, 2025•0 citations

Graph-based classification of self-dual additive codes over finite fields

Lars Eirik Danielsen

Quantum stabilizer states over Fm can be represented as self-dual additive codes over Fm2. These codes can be represented as weighted graphs, and orbits of graphs under the generalized local complementation operationcorrespond to equivalence classes of codes. We have previously used this fact to classify self-dual additive codes over F4. In this paper we classify selfdual additive codes over F9, F16, and F25. Assuming that the classical MDSconjecture holds, we are able to classify all self-dual additive MDS codes over F9 by using an extension technique. We prove that the minimum distanceof a self-dual additive code is related to the minimum vertex degree in theassociated graph orbit. Circulant graph codes are introduced, and a computersearch reveals that this set contains many strong codes. We show that some ofthese codes have highly regular graph representations.

arXiv:0801.3773•Advances in Mathematics of Communications•Jan 1, 2009•16 citations

On the classification of Hermitian self-dual additive codes over GF(9)

Lars Eirik Danielsen

Additive codes over GF(9) that are self-dual with respect to the Hermitian trace inner product have a natural application in quantum information theory, where they correspond to ternary quantum error-correcting codes. However, these codes have so far received far less interest from coding theorists than self-dual additive codes over GF(4), which correspond to binary quantum codes. Self-dual additive codes over GF(9) have been classified up to length 8, and in this paper we extend the complete classification to codes of length 9 and 10. The classification is obtained by using a new algorithm that combines two graph representations of self-dual additive codes. The search space is first reduced by the fact that every code can be mapped to a weighted graph, and a different graph is then introduced that transforms the problem of code equivalence into a problem of graph isomorphism. By an extension technique, we are able to classify all optimal codes of length 11 and 12. There are 56,005,876 (11,3^11,5) codes and 6493 (12,3^12,6) codes. We also find the smallest codes with trivial automorphism group.

arXiv:1106.2428•Jun 13, 2011•0 citations
We study objects that can be represented as graphs, error-correcting codes, quantum states, or Boolean functions. It is known that self-dual additive codes, which can also be interpreted as quantum states, can be represented as graphs, and that two codes are equivalent when the corresponding graphs are equivalent with respect to local complementation (LC). We give classifications of such codes. Circulant graph codes are introduced, and it is shown that some of these codes have highly regular graph representations. We show that the orbit of a bipartite graph under edge local complementation (ELC) corresponds to the equivalence class of a binary linear code. We classify ELC orbits, give a new method for classifying binary linear codes, and show that the information sets and the minimum distance of a code can be derived from the corresponding ELC orbit. Self-dual additive codes over GF(4) can also be interpreted as quadratic Boolean functions. In this context we define PARIHN, peak-to-average power ratio with respect to the {I, H, N}n transform, and prove that PARIHN equals the size of the maximum independent set over the associated LC orbit of graphs. We define the aperiodic propagation criteria (APC) of a Boolean function, and show that it is related to the minimum distance of a self-dual additive code over GF(4), and to the degree of entanglement in the associated quantum state. We give a generalization to non-quadratic Boolean functions, and relate APC to known cryptographic criteria. Interlace polynomials encode many properties of the LC and ELC orbits of a graph. We enumerate interlace polynomials and circle graphs, show that there exist non-unimodal interlace polynomials, and relate properties of interlace polynomials to properties of codes and quantum states. We define self-dual bent functions, and provide constructions and classifications.
A short introduction to quantum error correction is given, and it is shown that zero-dimensional quantum codes can be represented as self-dual additive codes over GF(4) and also as graphs. We show that graphs representing several such codes with high minimum distance can be described as nested regular graphs having minimum regular vertex degree and containing long cycles. Two graphs correspond to equivalent quantum codes if they are related by a sequence of local complementations. We use this operation to generate orbits of graphs, and thus classify all inequivalent self-dual additive codes over GF(4) of length up to 12, where previously only all codes of length up to 9 were known. We show that these codes can be interpreted as quadratic Boolean functions, and we define non-quadratic quantum codes, corresponding to Boolean functions of higher degree. We look at various cryptographic properties of Boolean functions, in particular the propagation criteria. The new aperiodic propagation criterion (APC) and the APC distance are then defined. We show that the distance of a zero-dimensional quantum code is equal to the APC distance of the corresponding Boolean function. Orbits of Boolean functions with respect to the {I,H,N}^n transform set are generated. We also study the peak-to-average power ratio with respect to the {I,H,N}^n transform set (PAR_IHN), and prove that PAR_IHN of a quadratic Boolean function is related to the size of the maximum independent set over the corresponding orbit of graphs. A construction technique for non-quadratic Boolean functions with low PAR_IHN is proposed. It is finally shown that both PAR_IHN and APC distance can be interpreted as partial entanglement measures.
Abstract. Quantum stabilizer states over Fm can be represented as self-dual additive codes over F m 2. These codes can be represented as weighted graphs, and orbits of graphs under the generalized local complementation operation correspond to equivalence classes of codes. We have previously used this fact to classify self-dual additive codes over F4. In this paper we classify selfdual additive codes over F9, F16, and F25. Assuming that the classical MDS conjecture holds, we are able to classify all self-dual additive MDS codes over F9 by using an extension technique. We prove that the minimum distance of a self-dual additive code is related to the minimum vertex degree in the associated graph orbit. Circulant graph codes are introduced, and a computer search reveals that this set contains many strong codes. We show that some of these codes have highly regular graph representations. 1.
Generalisations of the bent property of a Boolean function are presented, by proposing spectral analysis of the Boolean function with respect to a well-chosen set of local unitary transforms. Quadratic Boolean functions are related to simple graphs and it is shown that the orbit generated by some graph transforms can be found within the spectra of certain unitary transform sets. The flat spectra of a quadratic Boolean function with respect to those transforms are related to modified versions of its associated adjacency matrix. The flat spectra of concrete recursive structures are found using this method. We derive a spectral interpretation of the interlace polynomials (in one or two variables) of a graph and we relate to one of them a quantum measure of entanglement of the associated quantum state. We characterise the values of the spectra of a quadratic Boolean function. We give a formula for the weight hierarchy for a binary linear code in terms of a modified interlace polynomial. We derive as well a spectral interpretation of the pivot operation on a graph and generalise this operation to hypergraphs. We enumerate the number of inequivalent pivot orbits for small numbers of vertices. We also construct a family of Boolean functions of degree higher than two with a large number of flat spectra with respect to the {I,H}n set of transforms, and compute a lower bound on this number. We show how to change the degree of a Boolean function via pivot operation. Finally, we give concrete formulae for the spectra of a wide range of vectors with respect to well-chosen transforms sets.
Graph states form a large family of quantum states that are in one-to-one correspondence with mathematical graphs. Graph states are used in many applications, such as measurement-based quantum computation, as multipartite entangled resources. It is thus crucial to understand when two such states have the same entanglement, i.e. when they can be transformed into each other using only local operations. In this case, we say that the graph states are LU-equivalent (local unitary). If the local operations are restricted to the so-called Clifford group, we say that the graph states are LC-equivalent (local Clifford). Interestingly, a simple graph rule called local complementation fully captures LC-equivalence, in the sense that two graph states are LC-equivalent if and only if the underlying graphs are related by a sequence of local complementations. While it was once conjectured that two LU-equivalent graph states are always LC-equivalent, counterexamples do exist and local complementation fails to fully capture the entanglement of graph states. We introduce in this thesis a generalization of local complementation that does fully capture LU-equivalence. Using this characterization, we prove the existence of an infinite strict hierarchy of local equivalences between LC- and LU-equivalence. This also leads to the design of a quasi-polynomial algorithm for deciding whether two graph states are LU-equivalent, and to a proof that two LU-equivalent graph states are LC-equivalent if they are defined on at most 19 qubits. Furthermore, we study graph states that are universal in the sense that any smaller graph state, defined on any small enough set of qubits, can be induced using only local operations. We provide bounds and an optimal, probabilistic construction.
Quantum stabilizer states over Fm can be represented as self-dual additive codes over Fm2. These codes can be represented as weighted graphs, and orbits of graphs under the generalized local complementation operationcorrespond to equivalence classes of codes. We have previously used this fact to classify self-dual additive codes over F4. In this paper we classify selfdual additive codes over F9, F16, and F25. Assuming that the classical MDSconjecture holds, we are able to classify all self-dual additive MDS codes over F9 by using an extension technique. We prove that the minimum distanceof a self-dual additive code is related to the minimum vertex degree in theassociated graph orbit. Circulant graph codes are introduced, and a computersearch reveals that this set contains many strong codes. We show that some ofthese codes have highly regular graph representations.
Additive codes over GF(9) that are self-dual with respect to the Hermitian trace inner product have a natural application in quantum information theory, where they correspond to ternary quantum error-correcting codes. However, these codes have so far received far less interest from coding theorists than self-dual additive codes over GF(4), which correspond to binary quantum codes. Self-dual additive codes over GF(9) have been classified up to length 8, and in this paper we extend the complete classification to codes of length 9 and 10. The classification is obtained by using a new algorithm that combines two graph representations of self-dual additive codes. The search space is first reduced by the fact that every code can be mapped to a weighted graph, and a different graph is then introduced that transforms the problem of code equivalence into a problem of graph isomorphism. By an extension technique, we are able to classify all optimal codes of length 11 and 12. There are 56,005,876 (11,3^11,5) codes and 6493 (12,3^12,6) codes. We also find the smallest codes with trivial automorphism group.