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.
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.
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.
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.
Stabilizer states form a ubiquitous family of quantum states that can be graphically represented through the graph state formalism. A fundamental property of graph states is that applying a local complementation - a well-known and extensively studied graph transformation - results in a graph that represents the same entanglement as the original. In other words, the corresponding graph states are LU-equivalent. This property served as the cornerstone for capturing non-trivial quantum properties in a simple graphical manner, in the study of quantum entanglement but also for developing protocols and models based on graph states and stabilizer states, such as measurement-based quantum computing, secret sharing, error correction, entanglement distribution... However, local complementation fails short to fully characterise entanglement: there exist pairs of graph states that are LU-equivalent but cannot be transformed one into the other using local complementations. Only few is known about the equivalence of graph states beyond local complementation. We introduce a generalisation of local complementation which graphically characterises the LU-equivalence of graph states. We use this characterisation to show the existence of a strict infinite hierarchy of equivalences of graph states. Our approach is based on minimal local sets, which are subsets of vertices that are known to cover any graph, and to be invariant under local complementation and even LU-equivalence. We use these structures to provide a type to each vertex of a graph, leading to a natural standard form in which the LU-equivalence can be exhibited and captured by means of generalised local complementation.
Circle graph states are a structurally important family of graph states. The family's entanglement is a priori high enough to allow for universal measurement-based quantum computation (MBQC); however, MBQC on circle graph states is actually efficiently classically simulable. In this work, we paint a detailed picture of the local equivalence of circle graph states. First, we consider the class of all graph states that are local unitary (LU)-equivalent to circle graph states. In graph-theoretical terms, this LU-equivalence class is the set of all graphs reachable from the family of circle graphs by applying r-local complementations. We prove that the only graph states that are LU-equivalent to circle graph states are circle graph states themselves: circle graphs are closed under r-local complementation. Second, we show that bipartite circle graph states, i.e., 2-colorable circle graph states, are in one-to-one correspondence with planar code states, on which MBQC is known to be efficiently classically simulable. Leveraging this correspondence, we present alternative, simple proofs that (1) if a planar code state is LU-equivalent to a stabilizer state, they are in fact local Clifford (LC)-equivalent to it and that (2) MBQC on all circle graph states is efficiently classically simulable. Third and finally, we demonstrate that the problem of counting the number of graph states LU-equivalent to a given graph state is #P-hard.
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.
Graph states are widely used in quantum information theory, including entanglement theory, quantum error correction, and one-way quantum computing. Graph states have a nice structure related to a certain graph, which is given by either a stabilizer group or an encoding circuit, both can be directly given by the graph. To generalize graph states, whose stabilizer groups are abelian subgroups of the Pauli group, one approach taken is to study non-abelian stabilizers. In this work, we propose to generalize graph states based on the encoding circuit, which is completely determined by the graph and a Hadamard matrix. We study the entanglement structures of these generalized graph states and show that they are all maximally mixed locally. We also explore the relationship between the equivalence of Hadamard matrices and local equivalence of the corresponding generalized graph states. This leads to a natural generalization of the Pauli (X, Z) pairs, which characterizes the local symmetries of these generalized graph states. Our approach is also naturally generalized to construct graph quantum codes which are beyond stabilizer codes.