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

Realization of some local unitary operations by graph switching

Supriyo Dutta, Bibhas Adhikari, Subhashish Banerjee

Published Jan 1, 2015• 0 citations
Publisher

Abstract

In this work we implement a graph theoretical realization of local unitary transformations, implemented by single qubit Pauli gates, by adapting techniques of graph switching. This leads to the concept of local unitary equivalent graphs. We illustrate our method by a few, well known, local unitary transformations implemented by single qubit Pauli and Hadamard gates.

DOI
10.13140/2.1.5152.5928

Related papers

Polynomial-time local-unitary equivalence of graph states

Yuxuan Zhang

Local-unitary (LU) equivalence asks whether two quantum states differ only by independent changes of basis on their qubits. For graph states, whether this relation can be decided in polynomial time has remained open for over a decade. We give a deterministic algorithm that decides LU equivalence for graphs on $n$ labelled vertices in $\widetilde O(n^{6.38})$ bit operations and constructs exact single-qubit unitaries whenever the states are equivalent. Building on Claudet and Perdrix's quasipolynomial algorithm, we replace the enumeration of vertex subsets by a compact system of constraints generated from pairs and triples. The remaining graph transformation is found by solving linear equations over the binary field. These new steps cost $\widetilde O(n^5)$ bit operations; the inherited graph preprocessing sets the overall bound. We also count the local-Clifford (LC) classes of graph states within any LU class: their number is a power of two, computable within the same bound. For any given graph state, this decides whether single-qubit Clifford gates reach every graph state in its LU class, and supplies a counterexample when they do not. The method also decides LU equivalence of stabilizer codes encoding one logical qubit.

quant-pharXiv:2610.00527•Oct 2, 2026•0 citations

Graph states and local unitary transformations beyond local Clifford operations

Nikoloz Tsimakuridze, Otfried Gühne

Abstract Graph states are quantum states that can be described by a stabilizer formalism and play an important role in quantum information processing. We consider the action of local unitary operations on graph states and hypergraph states. We focus on non-Clifford operations and find for certain transformations a graphical description in terms of weighted hypergraphs. This leads to the indentification of hypergraph states that are locally equivalent to graph states. Moreover, we present a systematic way to construct pairs of graph states which are equivalent under local unitary operations, but not equivalent under local Clifford operations. This generates counterexamples to a conjecture known as LU-LC conjecture. So far, the only counterexamples to this conjecture were found by random search. Our method reproduces the smallest known counterexample as a special case and provides a physical interpretation.

arXiv:1611.06938•Journal of Physics A Mathematical and Theoretical•Mar 20, 2017•38 citations

Graphical description of unitary transformations on hypergraph states

Mariami Gachechiladze, Nikoloz Tsimakuridze, Otfried Gühne

Abstract Hypergraph states form a family of multiparticle quantum states that generalizes cluster states and graph states. We study the action and graphical representation of nonlocal unitary transformations between hypergraph states. This leads to a generalization of local complementation and graphical rules for various gates, such as the CNOT gate and the Toffoli gate. As an application, we show that already for five qubits local Pauli operations are not sufficient to check local equivalence of hypergraph states. Furthermore, we use our rules to construct entanglement witnesses for three-uniform hypergraph states.

arXiv:1612.01447•Journal of Physics A Mathematical and Theoretical•Mar 17, 2017•14 citations

Deciding Local Unitary Equivalence of Graph States in Quasi-Polynomial Time

Nathan Claudet, Simon Perdrix

We describe an algorithm with quasi-polynomial runtime $n^{\log_2(n)+O(1)}$ for deciding local unitary (LU) equivalence of graph states. The algorithm builds on a recent graphical characterisation of LU-equivalence via generalised local complementation. By first transforming the corresponding graphs into a standard form using usual local complementations, LU-equivalence reduces to the existence of a single generalised local complementation that maps one graph to the other. We crucially demonstrate that this reduces to solving a system of quasi-polynomially many linear equations, avoiding an exponential blow-up. As a byproduct, we generalise Bouchet's algorithm for deciding local Clifford (LC) equivalence of graph states by allowing the addition of arbitrary linear constraints. We also improve existing bounds on the size of graph states that are LU- but not LC-equivalent. While the smallest known examples involve 27 qubits, and it is established that no such examples exist for up to 8 qubits, we refine this bound by proving that LU- and LC-equivalence coincide for graph states involving up to 19 qubits.

arXiv:2502.06566•Leibniz international proceedings in informatics•Jan 1, 2025•13 citations

Genuine entanglement and LU-equivalence of graph states in bipartition

Yuting Huang, Lin Chen

Graph states are intuitive representations of quantum states that are useful in quantum computing and quantum information. In this paper, we investigate the role of entanglement and local unitary equivalence in quantum computing through graph states in high-dimensional Hilbert spaces. We introduce bipartitions on the vertices sets and demonstrate separability and local unitary equivalence based on different choices of partitions. By performing the two-qubit controlled phase shift gates on various pairs of multiqubit system, one can generate a genuinely entangled graph state based on simple connected graphs. We extend 2-dimensional Hilbert spaces to higher and mixed dimensions and examine pure quantum states that cannot be separated by any bipartition. In addition, we generalize the analysis on classification of local unitary equivalence beyond the controlled-Z gates to controlled phase gates. By examining graphs constructed from bipartition graphs, we have shown that graphs with identical bipartition subgraph structures are local unitary equivalent.

Modern Physics Letters A•Dec 10, 2025•0 citations

A bonding model of entanglement for N-qubit graph states

Mordecai Waegell

The class of entangled N-qubit states known as graph states, and the corresponding stabilizer groups of N-qubit Pauli observables, have found a wide range of applications in quantum information processing and the foundations of quantum mechanics. A review of the properties of graph states is given and core spaces of graph states are introduced and discussed. A bonding model of entanglement for generalized graph states is then presented, in which the presence or absence of a bond between two qubits unequivocally specifies whether or not they are entangled. A physical interpretation of these bonds is given, along with a characterization of how they can be created or destroyed by entangling unitary operations and how they can be destroyed by local Pauli measurements. It is shown that local unitary operations do not affect the bond structure of a graph state, and therefore that if two graph states have nonisomorphic bond structures, then local unitary operations and/or reordering of qubits cannot change one into the other. Color multigraphs are introduced to depict the bond structures of graph states and to make some of their properties more apparent.

arXiv:1406.0206•International Journal of Quantum Information•Sep 1, 2014•4 citations
In this work we implement a graph theoretical realization of local unitary transformations, implemented by single qubit Pauli gates, by adapting techniques of graph switching. This leads to the concept of local unitary equivalent graphs. We illustrate our method by a few, well known, local unitary transformations implemented by single qubit Pauli and Hadamard gates.
Local-unitary (LU) equivalence asks whether two quantum states differ only by independent changes of basis on their qubits. For graph states, whether this relation can be decided in polynomial time has remained open for over a decade. We give a deterministic algorithm that decides LU equivalence for graphs on nnn labelled vertices in O~(n6.38)\widetilde O(n^{6.38})O(n6.38) bit operations and constructs exact single-qubit unitaries whenever the states are equivalent. Building on Claudet and Perdrix's quasipolynomial algorithm, we replace the enumeration of vertex subsets by a compact system of constraints generated from pairs and triples. The remaining graph transformation is found by solving linear equations over the binary field. These new steps cost O~(n5)\widetilde O(n^5)O(n5) bit operations; the inherited graph preprocessing sets the overall bound. We also count the local-Clifford (LC) classes of graph states within any LU class: their number is a power of two, computable within the same bound. For any given graph state, this decides whether single-qubit Clifford gates reach every graph state in its LU class, and supplies a counterexample when they do not. The method also decides LU equivalence of stabilizer codes encoding one logical qubit.
Abstract Graph states are quantum states that can be described by a stabilizer formalism and play an important role in quantum information processing. We consider the action of local unitary operations on graph states and hypergraph states. We focus on non-Clifford operations and find for certain transformations a graphical description in terms of weighted hypergraphs. This leads to the indentification of hypergraph states that are locally equivalent to graph states. Moreover, we present a systematic way to construct pairs of graph states which are equivalent under local unitary operations, but not equivalent under local Clifford operations. This generates counterexamples to a conjecture known as LU-LC conjecture. So far, the only counterexamples to this conjecture were found by random search. Our method reproduces the smallest known counterexample as a special case and provides a physical interpretation.
Abstract Hypergraph states form a family of multiparticle quantum states that generalizes cluster states and graph states. We study the action and graphical representation of nonlocal unitary transformations between hypergraph states. This leads to a generalization of local complementation and graphical rules for various gates, such as the CNOT gate and the Toffoli gate. As an application, we show that already for five qubits local Pauli operations are not sufficient to check local equivalence of hypergraph states. Furthermore, we use our rules to construct entanglement witnesses for three-uniform hypergraph states.
We describe an algorithm with quasi-polynomial runtime nlog⁡2(n)+O(1)n^{\log_2(n)+O(1)}nlog2​(n)+O(1) for deciding local unitary (LU) equivalence of graph states. The algorithm builds on a recent graphical characterisation of LU-equivalence via generalised local complementation. By first transforming the corresponding graphs into a standard form using usual local complementations, LU-equivalence reduces to the existence of a single generalised local complementation that maps one graph to the other. We crucially demonstrate that this reduces to solving a system of quasi-polynomially many linear equations, avoiding an exponential blow-up. As a byproduct, we generalise Bouchet's algorithm for deciding local Clifford (LC) equivalence of graph states by allowing the addition of arbitrary linear constraints. We also improve existing bounds on the size of graph states that are LU- but not LC-equivalent. While the smallest known examples involve 27 qubits, and it is established that no such examples exist for up to 8 qubits, we refine this bound by proving that LU- and LC-equivalence coincide for graph states involving up to 19 qubits.
Graph states are intuitive representations of quantum states that are useful in quantum computing and quantum information. In this paper, we investigate the role of entanglement and local unitary equivalence in quantum computing through graph states in high-dimensional Hilbert spaces. We introduce bipartitions on the vertices sets and demonstrate separability and local unitary equivalence based on different choices of partitions. By performing the two-qubit controlled phase shift gates on various pairs of multiqubit system, one can generate a genuinely entangled graph state based on simple connected graphs. We extend 2-dimensional Hilbert spaces to higher and mixed dimensions and examine pure quantum states that cannot be separated by any bipartition. In addition, we generalize the analysis on classification of local unitary equivalence beyond the controlled-Z gates to controlled phase gates. By examining graphs constructed from bipartition graphs, we have shown that graphs with identical bipartition subgraph structures are local unitary equivalent.
The class of entangled N-qubit states known as graph states, and the corresponding stabilizer groups of N-qubit Pauli observables, have found a wide range of applications in quantum information processing and the foundations of quantum mechanics. A review of the properties of graph states is given and core spaces of graph states are introduced and discussed. A bonding model of entanglement for generalized graph states is then presented, in which the presence or absence of a bond between two qubits unequivocally specifies whether or not they are entangled. A physical interpretation of these bonds is given, along with a characterization of how they can be created or destroyed by entangling unitary operations and how they can be destroyed by local Pauli measurements. It is shown that local unitary operations do not affect the bond structure of a graph state, and therefore that if two graph states have nonisomorphic bond structures, then local unitary operations and/or reordering of qubits cannot change one into the other. Color multigraphs are introduced to depict the bond structures of graph states and to make some of their properties more apparent.