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

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