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

arXiv:1704.06504 · Quantum

Universal MBQC with generalised parity-phase interactions and Pauli measurements

Aleks Kissinger, John van de Wetering

Published Apr 26, 2019• 43 citations
arXivHTMLPDF

Abstract

We introduce a new family of models for measurement-based quantum computation which are deterministic and approximately universal. The resource states which play the role of graph states are prepared via 2-qubit gates of the form exp⁡(−iπ2nZ⊗Z) . When n=2 , these are equivalent, up to local Clifford unitaries, to graph states. However, when n>2 , their behaviour diverges in two important ways. First, multiple applications of the entangling gate to a single pair of qubits produces non-trivial entanglement, and hence multiple parallel edges between nodes play an important role in these generalised graph states. Second, such a state can be used to realise deterministic, approximately universal computation using only Pauli Z and X measurements and feed-forward. Even though, for n>2 , the relevant resource states are no longer stabiliser states, they admit a straightforward, graphical representation using the ZX-calculus. Using this representation, we are able to provide a simple, graphical proof of universality. We furthermore show that for every n>2 this family is capable of producing all Clifford gates and all diagonal gates in the n -th level of the Clifford hierarchy.

DOI
10.22331/q-2019-04-26-134

Related papers

Fermionic Insights into Measurement-Based Quantum Computation: Circle Graph States Are Not Universal Resources

Brent Harrison, Vishnu Iyer, Ojas Parekh +2 more

Measurement-based quantum computation (MBQC) is a strong contender for realizing quantum computers. A critical question for MBQC is the identification of resource graph states that can enable universal quantum computation. Any such universal family must have unbounded entanglement width, which is equivalent to the ability to produce any circle graph state from the states in the family using only local Clifford operations, local Pauli measurements, and classical communication. Yet, it was not previously known whether or not circle graph states themselves are a universal resource. We show that, in spite of their expressivity, circle graph states are not efficiently universal for MBQC (i.e., assuming $\mathsf{BQP} \neq \mathsf{BPP}$). We prove this by articulating a precise graph-theoretic correspondence between circle graph states and a certain subset of fermionic Gaussian states. This is accomplished by synthesizing a variety of techniques that allow us to handle both stabilizer states and fermionic Gaussian states at the same time. As such, we anticipate that our developments may have broader applications beyond the domain of MBQC as well.

arXiv:2510.05557•Oct 7, 2025•4 citations

The Structure of Circle Graph States

Frederik Hahn, Rose McCarty, Hendrik Poulsen Nautrup +1 more

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 $\#\mathsf{P}$-hard.

quant-pharXiv:2603.08847•Mar 11, 2026•5 citations

Efficient Preparation of Resource States for Hamiltonian Simulation and Universal Quantum Computation

Thierry N. Kaldenbach, Isaac D. Smith, Hendrik Poulsen Nautrup +2 more

The direct compilation of algorithm-specific graph states in measurement-based quantum computation (MBQC) can lead to resource reductions in terms of circuit depth, entangling gates, and even the number of physical qubits. In this work, we extend previous studies on algorithm-tailored graph states to periodic sequences of generalized Pauli rotations, which commonly appear in, e.g., Trotterized Hamiltonian simulation. We first implement an enhanced simulated-annealing-based algorithm to find optimal periodic graph states within local-Clifford equivalent MBQC resources. In addition, we derive a novel scheme for the preparation of resource states based on a graph state and a ladder of CNOT gates, which we term anticommutation-based MBQC, since it uncovers a direct relationship between the graph state and the anticommutation matrix for the set of Hamiltonians generating the computation. We also deploy our two approaches to derive universal resource states from minimal universal sets of generating Hamiltonians. Finally, we demonstrate and compare both of our methods based on various examples from condensed matter physics and universal quantum computation.

arXiv:2509.05404•Sep 5, 2025•7 citations

Graphix: optimizing and simulating measurement-based quantum computation on local-Clifford decorated graph

Shinichi Sunami, Fukushima, Masato

We introduce an open-source software library Graphix, which optimizes and simulates measurement-based quantum computation (MBQC). By combining the measurement calculus with an efficient graph state simulator, Graphix allows the classical preprocessing of Pauli measurements in the measurement patterns, significantly reducing the number of operations required to perform the quantum computation while maintaining determinism. For a measurement pattern translated from a quantum circuit, this corresponds to the preprocessing of all Clifford gates, and this improvement in the one-way model is important for efficient operations in quantum hardware with limited qubit numbers. In addition to the direct translation from gate networks, we provide a pattern generation method based on flow-finding algorithms, which automatically generates byproduct correction sequences to ensure determinism. We further implement optimization strategies for measurement patterns beyond the standardization procedure and provide tensor-network backend for classically simulating the MBQC.

arXiv:2212.11975•Dec 22, 2022•15 citations

Preservation of determinism in MBQC under ZX-calculus rewrites

McElvanney, Tommy

The ZX-calculus is a powerful graphical language for reasoning about and optimizing quantum computations, being able to represent and rewrite both quantum circuits and measurement-based quantum computations (MBQCs) in a natural way, along with acting as a tool to translate between the two aforementioned types of quantum computation. Finding a circuit that is equivalent to a ZX-diagram can be #P hard [11] - it is therefore important to look at the classes of ZX-diagrams that we have efficient circuit extraction algorithms for. The most general of these classes are ZX-diagrams with a property known as Pauli flow - this is a property from measurement-based quantum computing which ensures that computations remain deterministic despite quantum measurements being inherently probabilistic. The standard ZX-calculus rules are not particularly well suited to measurement-based quantum computing as they often do not preserve the existence of Pauli flow nor preserve the MBQC structure itself. Thus by developing our understanding of ZX-calculus rewrite rules which preserve the existence of Pauli flow, we can better understand which ZX diagrams we are able to efficiently extract a circuit from as well as which Measurement-based computations we can perform deterministically. In this thesis, I introduce new ZX-calculus rewrite rules and prove that these rules preserve the existence of Pauli flow. These rules have a variety of applications across many areas of quantum computation which will also be explored - to start, I show that these rules give us a procedure for rewriting any measurement-based quantum computation with arbitrary planar measurements along with X, Y and Z Pauli measurements into a diagram containing only XY -planar measurements and X and Y Pauli measurements (that is, only containing green spiders in the ZX-calculus). I then show that when we restrict to the stabilizer fragment of quantum computing - where we only have Pauli-measurements in measurement-based quantum computations - we are able to find a complete set of rewrite rules which preserve the existence of Pauli flow. To do this, I introduce a procedure for rewriting any stabilizer ZX-diagram into a unique normal form using only flow-preserving rewrite rules. Finally, I examine the flow preservation of the "neighbour unfusion" rule of [60]. This rule was used in an optimization procedure for reducing 2-qubit gate count but the authors did not know in what cases this rule preserved gflow which was important for their algorithm to function. Neighbour unfusion is a special case of one of the rules which I proved to preserve Pauli flow and so it also preserves Pauli flow, but it is not as simple in the case of gflow. I find a condition that is both sufficient and necessary for neighbour unfusion to preserve the existence of gflow, along with providing less strict conditions for gflow to be preserved that can function as useful heuristics in their algorithm.

•Jul 15, 2025•0 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•4 citations
We introduce a new family of models for measurement-based quantum computation which are deterministic and approximately universal. The resource states which play the role of graph states are prepared via 2-qubit gates of the form exp⁡(−iπ2nZ⊗Z) . When n=2 , these are equivalent, up to local Clifford unitaries, to graph states. However, when n>2 , their behaviour diverges in two important ways. First, multiple applications of the entangling gate to a single pair of qubits produces non-trivial entanglement, and hence multiple parallel edges between nodes play an important role in these generalised graph states. Second, such a state can be used to realise deterministic, approximately universal computation using only Pauli Z and X measurements and feed-forward. Even though, for n>2 , the relevant resource states are no longer stabiliser states, they admit a straightforward, graphical representation using the ZX-calculus. Using this representation, we are able to provide a simple, graphical proof of universality. We furthermore show that for every n>2 this family is capable of producing all Clifford gates and all diagonal gates in the n -th level of the Clifford hierarchy.
Measurement-based quantum computation (MBQC) is a strong contender for realizing quantum computers. A critical question for MBQC is the identification of resource graph states that can enable universal quantum computation. Any such universal family must have unbounded entanglement width, which is equivalent to the ability to produce any circle graph state from the states in the family using only local Clifford operations, local Pauli measurements, and classical communication. Yet, it was not previously known whether or not circle graph states themselves are a universal resource. We show that, in spite of their expressivity, circle graph states are not efficiently universal for MBQC (i.e., assuming BQP≠BPP\mathsf{BQP} \neq \mathsf{BPP}BQP=BPP). We prove this by articulating a precise graph-theoretic correspondence between circle graph states and a certain subset of fermionic Gaussian states. This is accomplished by synthesizing a variety of techniques that allow us to handle both stabilizer states and fermionic Gaussian states at the same time. As such, we anticipate that our developments may have broader applications beyond the domain of MBQC as well.
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 rrr-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 rrr-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\#\mathsf{P}#P-hard.
The direct compilation of algorithm-specific graph states in measurement-based quantum computation (MBQC) can lead to resource reductions in terms of circuit depth, entangling gates, and even the number of physical qubits. In this work, we extend previous studies on algorithm-tailored graph states to periodic sequences of generalized Pauli rotations, which commonly appear in, e.g., Trotterized Hamiltonian simulation. We first implement an enhanced simulated-annealing-based algorithm to find optimal periodic graph states within local-Clifford equivalent MBQC resources. In addition, we derive a novel scheme for the preparation of resource states based on a graph state and a ladder of CNOT gates, which we term anticommutation-based MBQC, since it uncovers a direct relationship between the graph state and the anticommutation matrix for the set of Hamiltonians generating the computation. We also deploy our two approaches to derive universal resource states from minimal universal sets of generating Hamiltonians. Finally, we demonstrate and compare both of our methods based on various examples from condensed matter physics and universal quantum computation.
We introduce an open-source software library Graphix, which optimizes and simulates measurement-based quantum computation (MBQC). By combining the measurement calculus with an efficient graph state simulator, Graphix allows the classical preprocessing of Pauli measurements in the measurement patterns, significantly reducing the number of operations required to perform the quantum computation while maintaining determinism. For a measurement pattern translated from a quantum circuit, this corresponds to the preprocessing of all Clifford gates, and this improvement in the one-way model is important for efficient operations in quantum hardware with limited qubit numbers. In addition to the direct translation from gate networks, we provide a pattern generation method based on flow-finding algorithms, which automatically generates byproduct correction sequences to ensure determinism. We further implement optimization strategies for measurement patterns beyond the standardization procedure and provide tensor-network backend for classically simulating the MBQC.
The ZX-calculus is a powerful graphical language for reasoning about and optimizing quantum computations, being able to represent and rewrite both quantum circuits and measurement-based quantum computations (MBQCs) in a natural way, along with acting as a tool to translate between the two aforementioned types of quantum computation. Finding a circuit that is equivalent to a ZX-diagram can be #P hard [11] - it is therefore important to look at the classes of ZX-diagrams that we have efficient circuit extraction algorithms for. The most general of these classes are ZX-diagrams with a property known as Pauli flow - this is a property from measurement-based quantum computing which ensures that computations remain deterministic despite quantum measurements being inherently probabilistic. The standard ZX-calculus rules are not particularly well suited to measurement-based quantum computing as they often do not preserve the existence of Pauli flow nor preserve the MBQC structure itself. Thus by developing our understanding of ZX-calculus rewrite rules which preserve the existence of Pauli flow, we can better understand which ZX diagrams we are able to efficiently extract a circuit from as well as which Measurement-based computations we can perform deterministically. In this thesis, I introduce new ZX-calculus rewrite rules and prove that these rules preserve the existence of Pauli flow. These rules have a variety of applications across many areas of quantum computation which will also be explored - to start, I show that these rules give us a procedure for rewriting any measurement-based quantum computation with arbitrary planar measurements along with X, Y and Z Pauli measurements into a diagram containing only XY -planar measurements and X and Y Pauli measurements (that is, only containing green spiders in the ZX-calculus). I then show that when we restrict to the stabilizer fragment of quantum computing - where we only have Pauli-measurements in measurement-based quantum computations - we are able to find a complete set of rewrite rules which preserve the existence of Pauli flow. To do this, I introduce a procedure for rewriting any stabilizer ZX-diagram into a unique normal form using only flow-preserving rewrite rules. Finally, I examine the flow preservation of the "neighbour unfusion" rule of [60]. This rule was used in an optimization procedure for reducing 2-qubit gate count but the authors did not know in what cases this rule preserved gflow which was important for their algorithm to function. Neighbour unfusion is a special case of one of the rules which I proved to preserve Pauli flow and so it also preserves Pauli flow, but it is not as simple in the case of gflow. I find a condition that is both sufficient and necessary for neighbour unfusion to preserve the existence of gflow, along with providing less strict conditions for gflow to be preserved that can function as useful heuristics in their algorithm.
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.