Graphix: optimizing and simulating measurement-based

quantum computation on local-Clifford decorated graph

Shinichi Sunami1 and Masato Fukushima2,3

1
Clarendon Laboratory, University of Oxford, Oxford OX1 3PU, United Kingdom
2
Department of Physics, Faculty of Science, The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-0033, Japan
3
Fixstars Amplify, 3-1-1 Shibaura, Minato-ku, Tokyo 108-0023, Japan

We introduce an open-source software li- novel approaches in various quantum informa-

brary Graphix, which optimizes and simu- tion theories such as topological error-correction
lates measurement-based quantum compu- codes [3, 4], blind quantum computing [5, 6],
arXiv:2212.11975v1 [quant-ph] 22 Dec 2022

tation (MBQC). By combining the mea- cross-platform verification [7] and quantum
surement calculus with an efficient graph circuit depth reduction [8]. Experimentally,
state simulator, Graphix allows the clas- the MBQC paradigm is particularly suited
sical preprocessing of Pauli measurements to the optical architectures [9–12] with which
in the measurement patterns, significantly large-scale cluster states with thousands of
reducing the number of operations re- modes [13, 14] has already been demonstrated.
quired to perform the quantum computa- Cold-atom and ion trap quantum computers can
tion while maintaining determinism. For also be operated within the framework of MBQC
a measurement pattern translated from a by mid-sequence measurements and feedforward
quantum circuit, this corresponds to the [15–17]. Furthermore, MBQC was demonstrated
preprocessing of all Clifford gates, and this on superconducting-qubit quantum computers
improvement in the one-way model is im- without feedforward capability [18], thus making
portant for efficient operations in quantum it a widely relevant paradigm with a variety of
hardware with limited qubit numbers. In potential advantages, e.g. significantly smaller
addition to the direct translation from gate execution depth compared to circuits [8].
networks, we provide a pattern generation
method based on flow-finding algorithms, In MBQC, an entangled resource state, the
which automatically generates byproduct graph state, is prepared and the computation is
correction sequences to ensure determin- realized by a series of single-qubit measurements
ism. We further implement optimization only [2]. Any gate network has a corresponding
strategies for measurement patterns be- measurement pattern on graph states to realise
yond the standardization procedure and the same Unitary evolution [19, 20], thus making
provide tensor-network backend for clas- MBQC a universal quantum information process-
sically simulating the MBQC. ing method. A remarkable feature of the MBQC
is that all Clifford parts of the gate network can
be parallelized into a depth of one and that they
1 Introduction can be achieved simply by mathematical graph
transformations [2, 21, 22]. This is related to the
Measurement-based quantum computing Gottesman-Knill theorem [23] which states that
(MBQC) performs universal quantum com- the quantum information processing task con-
putation on graph states only by single-qubit sisting of Pauli basis states, Clifford gates and
measurements, and offers an alternative picture Pauli measurements are efficiently simulated in
to the quantum information processing usually classical computers. To our knowledge, concrete
described in networks of single- and multi-qubit strategies to utilize this feature in MBQC for ar-
gates [1, 2]. This has led to the development of bitrary quantum algorithms have not been de-
veloped, which is necessary to perform resource-
Shinichi Sunami: [email protected]
efficient computations.

1
 Here, we extend the measurement calculus [19, • byproduct correction command Xis , Zis
20] by introducing the local-Clifford commands,
which we refer to as MBQC on local-Clifford dec- • local-Clifford command Cik
orated graphs (LC-MBQC). This is necessary to where subscripts i, j are the node (qubit) indices,
classically preprocess all Pauli measurements in λ specifies the measurement plane (X,Y), (X,Z)
the measurement pattern with an efficient graph or (Y,Z), with the measurement angle α, and
state simulator, since post-measurement states s, t are the signal domains which are the set of
are generally local-Clifford equivalent of graph node indices whose measurement results the cor-
states. The resulting local-Clifford decorations responding operations depend upon [19]. In ad-
only rotate the subsequent non-Pauli measure- dition to the commands introduced in the mea-
ments, thus maintains the concise operational surement calculus, we have added local-Clifford
structure and determinism of the one-way model. commands Cik , where k specifies one of 7 Clif-
Further, we have implemented a tensor- ford decorations used in the graph state simula-
network (TN) backend for MBQC which is capa- tor [21, 27], which are necessary to integrate with
ble of simulating patterns running on thousands efficient stabilizer simulator. As we shall see in
of nodes in modest computing resources, without Section 3, the Clifford commands only change the
the need for approximation which is often nec- measurement angles and do not change the hard-
essary for TN-based circuit simulators. This is ware requirements to execute the one-way model,
thanks to the concise expression of graph states thus none of the advantages of the MBQC are
using matrix product states (MPS) [24, 25], as lost. Any one-way model on a local-Clifford dec-
well as the fact that MBQC completes only with orated graph state is described by series of the
single-qubit operations. above commands. For example, a command se-
We have assembled the proposed LC-MBQC quence realizing Hadamard gate H for an input
model, together with several optimization strate- qubit 1 and output qubit 2 is
gies of measurement patterns and their clas-
sical simulation backends into an open-source, MH = X21 M1
(X,Y ),0
E12 N2 N1 , (1)
python-based software library Graphix [26] which
is showcased in Section 2. In the following Section which should be read from the right. For an in-
3, we describe the LC-MBQC and the procedure put state |ψi1 the operation above is equivalent to
for classical preprocessing of Pauli measurements the tensor product with qubit 2 in +1 eigenstate
in the measurement pattern. Finally, we conclude of Pauli X operator |+i2 , application of CZ-gate,
and provide an outlook in Section 4. measurement in Pauli X basis and byproduct cor-
rection depending on the measurement outcome:

2 Overview H|ψi2 = X2s1 1 h±s1 |CZ12 |+i2 ⊗ |ψi1 , (2)

Here, we first review the MBQC and the mea- where we denote the Pauli X measurement and
surement calculus in Section 2.1 and describe the subsequent trace out of qubit 1 with 1 h±s1 | which
Graphix library in detail in Sections 2.2 and 2.3. depends on the measurement outcome: 1 h+| for
In Section 2.4, we describe the tensor-network s1 = 0 (measurement outcome (−1)s1 = +1)
MBQC simulator backend. and 1 h−| for s1 = 1 (measurement outcome of
(−1)s1 = −1). The byproduct correction opera-
tor X2s1 is applied conditionally, if the measure-
2.1 Introduction ment outcome s1 was 1. For x-rotation of a qubit
In Graphix, we describe MBQC with a sequence with angle ξ, the command sequence is
of commands based on the measurement calculus (X,Y ),−ξ (X,Y ),0
Z3s1 X3s2 s1
[M2 ] M1
E23 E12 N3 N2 N1 .
[19, 20] with additional local-Clifford command,
(3)
In this work, we refer to such a sequence of com-
• node preparation command Ni
mands as a pattern which is central to the soft-
• entanglement command Eij ware implementation of the one-way model.
We further introduce space and depth of a pat-
• measurement command t [Miλ,α ]s tern as follows. The space of the pattern is the

2
 number of qubits present during the execution of 2.2.2 Transpile from a gate network
the pattern. The pattern space is first initialized
with the number of input qubits, and N com- With graphix.Circuit class, one can create a gate
mands increment the space while M commands sequence and transpile into a measurement pat-
decrement the space, since the measurements are tern, with pre-configured byproduct sequences
destructive. The maximum space is the largest that ensure determinism [2, 20], using transpile
space during the execution of a pattern, and is method:
the minimum qubit resource required to run the 1 from graphix import Circuit
pattern with qubit reset and reuse [28]. It is thus 2 import numpy as np
often desirable to reduce the maximum space, for 3 circuit = Circuit (2)
example on classical statevector simulators where 4 circuit . cnot (0 ,1)
5 circuit . rx (0 , np . pi /4)
available memory space bounds the simultaneous 6 circuit . cnot (1 ,0)
qubit count. 7 pattern = circuit . transpile ()
The depth of a pattern is the minimum depth Listing 2: Transpiling a pattern from a gate network.
(the number of measurement rounds) required to
execute the pattern. For example, Pauli mea-
surements can be performed simultaneously with
depth of one [2]. The remaining measurements 2.2.3 Pattern generation with flow or gflow
can be parallelized according to their logical de-
pendence. The reduction of the depth is benefi- Designing the byproduct sequence and ensur-
cial for quantum hardware with limited coherence ing the determinism is the most critical aspect
time. of MBQC programming, however, it is a time-
In the following sections, we describe Graphix consuming process. As such, we implement an
in detail, which consists of generators, modifiers algorithm to find flow [29] or generalized flow
and simulators of patterns. (gflow ) [30] on open graph [31] in the graphix
.gflow module, with which one can automati-
cally generate the command sequence only from
2.2 Pattern generators the measurement angles and shape of the graph,
i.e. this algorithm automatically generates the
At the start of the MBQC programming, we gen- byproduct correction sequence that ensures de-
erate the measurement pattern to be performed terminism. This can be programmed as follows,
on the resource graph state, as described below. where this example generates the pattern to re-
alize the CNOT gate followed by the Hadamard
gate applied to the target qubit:
2.2.1 User-specified command sequence
1 from graphix import generate_from_gra ph
Any MBQC operations can be expressed by a 2 import networkx as nx
sequence of commands as described above. In 3 g = nx . Graph ()
Graphix, it is possible to manually concatenate 4 g . add_nodes_from ([0 ,1 ,2 ,3 ,4])
5 g . add_edges_from ([(0 ,2) ,(1 ,2) ,(1 ,3)
commands using Pattern class, by adding lists ,(2 ,4) ])
specifying each command with add method. Be- 6 angles = {0: 0. , 1: 0. , 2: 0.}
low, we demonstrate the direct programming of 7 pattern = generate_from_graph (g , angles ,
pattern Eq. (1). inputs =[0 ,1] , outputs =[4 ,3])

1 from graphix import Pattern

Listing 3: flow- or gflow-based pattern generation.
2 # Measurement pattern for Hadamard gate
3 pattern = Pattern ()
4 pattern . add ([ ’N ’ , 0])
5 pattern . add ([ ’N ’ , 1]) 2.3 Pattern modifiers
6 pattern . add ([ ’E ’ , (0 , 1) ])
pattern . add ([ ’M ’ , 0 , ’ XY ’ ,0. , [] , []])
7
Pattern modifiers manipulate the command se-
8 pattern . add ([ ’X ’ , 1 ,[0]])
quences in the Pattern object, and optimize their
Listing 1: User-defined pattern. properties such as command length, space and
depth.

3
2.3.1 Standardization and signal shifting 2.4 Pattern simulator
The standard pattern is the one where the com- The graphix.PatternSimulator class executes the
mands are sorted in the order of N , E, M , fol- pattern using classical simulation backends; we
lowed by the byproduct and Clifford commands have implemented statevector and matrix prod-
X, Z, C which can be in arbitrary order. One uct state (MPS) backends (see Sec. 2.4.1). These
can standardize any command sequence by the can also be called from pattern class by pattern.
commutation relations of individual commands, simulate_pattern().
as described in [19, 20]. Furthermore, the signal Further, it is straightforward to add quantum
shifting procedure reduces the interdependence hardware and hardware emulators as pattern ex-
of measurement commands [19]. These can be ecution backends. This is because the pattern
performed by standardize() and shift_signals() sequence can be run only with standard oper-
methods of Pattern class and the two operations ations such as qubit preparation, CZ-gate and
scale with the number of total commands Nc as single-qubit measurements (and that byproduct
O(Nc5 ) [19]. and Clifford commands can be straightforwardly
When translating a gate network to a pattern, replaced by the rotation of final readout measure-
we can utilize the equivalence to unitary gate se- ment).
quence to simplify the standardization procedure.
This results in a standardized pattern with no t-
2.4.1 Tensor network backend
domain, the same as the one following the signal
shifting. The computation of this process scales It has been known that certain types of quantum
much preferably with O(Ng3 ), where the num- states have an efficient expression by tensor net-
ber of gates Ng is typically much smaller than works (TN) such as matrix product states (MPS)
Nc . We have implemented this in Circuit class as [24, 32–36]. This allows fast simulation of quan-
standardize_and_transpile() method. tum circuits with a limited amount of entangle-
ment [24] and has led to a recent development
2.3.2 Pattern optimization of TN-based quantum circuit simulators [37–40].
However, they are often limited in their applica-
We provide further pattern optimization proce- bility since highly entangled states can no longer
dures. Firstly, Pauli measurements of a pat- be efficiently expressed using MPS without ap-
tern can be classically preprocessed without sim- proximation [32, 41].
ulating the full quantum state thanks to effi- Such a limitation of the circuit MPS simu-
cient graph state simulators, and is thus imple- lation could be mitigated by translating into
mented as a pattern modifier. This is called by MBQC since any quantum algorithm (circuits)
Pattern.perform_pauli_measurements() after which has corresponding measurement patterns running
the length of the pattern sequence is significantly on graph states with only two-body entangle-
reduced while kept deterministic. We describe ments and computation completes by single-qubit
the detailed internal procedure in Section 3. operations. This allows for efficient simulation
We also provide a method for the minimiza- with potentially much wider applicability than
tion of pattern space, by the reordering of N, E standard TN-based circuit simulations. Specifi-
and M commands. Essentially, this is achieved cally, MBQC on tree graphs [33] and graph states
by delaying the preparation of qubits until their with limited Schmidt-rank width [35], were known
immediate neighbors are measured [28]. We re- to be efficiently simulatable using MPS. However,
order measurement commands according to their software libraries for demonstrating and bench-
feedforward dependence structure to further min- marking this idea is not widely available.
imize the maximum space. In Graphix, this can In Graphix, we implement an efficient prepa-
be performed by Pattern.reduce_space(). ration method of graph states on MPS [25, 36]
Another optimization method we provide is the to realize a significant speedup of MBQC pat-
parallelization of commands for reduced execu- tern simulation compared to standard state vec-
tion depth. This is obtained by performing all tor simulator. Further, pattern optimization can
logically independent measurements at once, and be tailored for MPS simulator characteristics, e.g.
can be called with Pattern.parallelize_commands(). by limiting the space of the pattern. As such,

4
Graphix serves as a comprehensive platform to mented in Graphix the decorated graph state sim-
test the boundary of applicability for the MBQC- ulation proposed in [27, 48] to efficiently perform
MPS simulation method. An intriguing advan- the Pauli measurements of graph states. This im-
tage in comparison to the circuit-based TN tech- plementation also allows us to toggle through the
nique is that the bond dimension [32] of two is set of equivalent graphs, a set of different local-
sufficient to exactly describe the resource state, Clifford-decorated graph states representing ex-
as well as that only single-qubit (single-tensor) actly the same stabilizer state, and this procedure
operations are performed after graph state prepa- can be used to minimize the connectivities of the
ration for which MPS runs efficiently. With our graph and thus optimize subsequent MBQC op-
current implementation, MBQC on graphs with erations.
thousands of nodes can be simulated with mod- ZX-calculus [49] is a graphical tool for circuit
est computing resources, on which only up to ∼20 optimizations, which also has application in opti-
qubits can be prepared at once as a statevector. mizing MBQC [50] while preserving the existence
Further, we are developing an optimized MBQC- of the flow. While our method of Pauli measure-
MPS simulator to run on a GPU cluster, all of ment elimination in Sec. 3.1 does not necessar-
which will be described and benchmarked in de- ily preserve the flow, it does preserve the deter-
tail in our separate work [42]. minism by considering the measurements on the
graph state simulator as part of the pattern ex-
2.5 Relation to previous works ecution and this reduces a much larger number
of measurement commands (i.e. the size of the
The possibility of eliminating Pauli measure- graph state). For users to be able to evaluate ZX-
ments in one-way quantum computing was calculus for MBQC pattern sequence generated
pointed out in the initial work by Raussendorf [2] with Graphix, we provide a method to export
based on the correspondence to stabilizer code, from a measurement pattern to openQASM [51],
however, the concrete strategy to integrate this which can be loaded into python library PyZX
idea into the computational model of MBQC has [52].
not been developed so far, to our knowledge. Re-
cent work by Houshmand et al [28] showed only
the minimum number of qubits required in the 3 Measurement calculus with local-
most general case and suggested the presence of Clifford command Cik
determinism using the notion of gflow [30] for a
single example. Another recent work by Fergu- In this section, we introduce the measurement
son et. al [43] optimize only a few variational al- calculus [20] with local Clifford commands, which
gorithms, without devising the methodology for is essential to incorporate the fast graph state
general quantum algorithms. simulator into the one-way model to preprocess
Other simulators for the measurement-based all Pauli measurements.
model, Paddle Quantum [44] and MCBeth [45]
were recently developed to implement the mea-
surement calculus. The Graphix package offers a 3.1 Classical preprocessing of Pauli measure-
significantly advanced capability by incorporat- ments
ing the stabilizer simulator with LC command, To perform Pauli measurements of a pattern us-
novel pattern optimization methods and tensor- ing a graph state simulator, and to obtain a pat-
network backend. tern with significantly reduced command length,
We note that the measurement calculus also the following procedure is used:
naturally describes other measurement-based
models [20] such as the teleportation-based model 1. Perform standardization of the pattern.
[46]. Thus Graphix will flexibly accommodate a
wide range of measurement-based architectures. 2. Perform signal shifting to eliminate the de-
There are numerous stabilizer simulators that pendence of Pauli measurements on non-
perform fast Clifford operations to stabilizer Pauli measurements, and bring Pauli mea-
states with a large number of qubits, such as surements to the front (just after entangle-
graph-state [21] and stim [47]. We have imple- ment commands).

5
 a)
|+ Rx( 1)
|+ Rz( 1) Rx( 2)
|+ Rz( 2) Rz( 4) Rx( 3)
|+ Rz( 3) Rz( 5) Rz( 6) Rx( 4)

b) c)

Figure 1: The quantum approximate optimization algorithm (QAOA) circuit and the resource state for MBQC
implementation before and after the graph transformation. a) One layer of QAOA circuit for a fully-connected graph
with four vertices. b) The graph state to perform the QAOA with the one-way model. Four leftmost nodes (qubits) are
the input and four rightmost nodes are the output qubits. The nodes to be measured in Pauli bases are indicated by
black circles while the ones with non-Pauli measurements are in white. Output qubits are in gray. c) The graph state
required to execute the pattern generated using Pattern.perform_pauli_measurements(), following the procedure
3.1. This is the minimal resource state that performs the same deterministic quantum computation as the graph
state shown in b). The number of nodes reduces from 48 to 14 and the minimum depth of measurement rounds,
obtained by pattern.parallelize_commands(), reduces from 3 to 2 as a result of the node elimination procedure.

3. Extract the N and E commands of the pat- ment calculus, with rotated measurement angles.
tern to initialize a graph state simulator.
Perform Pauli measurements on the graph 3.2 Local-Clifford command
state simulator and remove corresponding
commands from the measurement pattern. Here, we describe the effect of local-Clifford dec-
Choose the measurement results si = 0 orations (commands) on the subsequent MBQC
where possible (except for isolated nodes operations (rotation of measurement angles, in-
with 100% chance of being measured in |−i cluding that of final readout measurements).
state of the corresponding measurement ba- Single-qubit Clifford operators OC map a Pauli
sis). operator Op ∈ {X, Y, Z} to an element in P =
{±} × {X, Y, Z} under conjugation with OC , i.e.
4. From the resulting local-Clifford decorated
graph state in the graph state simulator, in- †
OC Op OC ∈ P. (4)
sert N , E and C commands to the front of
the pattern. For a single-qubit projection operator Pr = (I +
r1 X + r2 Y + r3 Z)/2 in an arbitrary projection
The resulting command sequence is runnable angle specified by a vector with unit length r =
and deterministic, since the measurement results (r1 , r2 , r3 ), the following holds:
are known and can be used for subsequent feed-
forward operations where necessary. As we de- †
OC Pr OC = Pr0 , (5)
scribe below, the local-Clifford commands C only
rotate the subsequent measurements, and there with a rotated vector r 0 (see Appendix 1 for the
is no need to prepare local-Clifford decorated list of transformation rules for each Oc used in
graphs quantum mechanically; the pattern runs Graphix). Thus, the local Clifford commands ro-
exactly the same way as the standard measure- tate the measurement angles and the following

6
 rules apply to the local-Clifford commands: 104
Standard MBQC
LC-MBQC

resource state size

0 0
Cik [Miλ,α ] = [Miλ ,α ], 103

Cik [Mjλ,α ] = [Mjλ,α ]Cik , i 6= j (6)

102
6
where the relationships between (λ, α) and
(λ0 , α0 ) follow from Table 1 in Appendix A. If the 101 4
local Clifford command operates on the output 2
100 0 10 20
nodes, it is applied to the final output states or 1 2 5 10 20
rotate the final readout measurement basis. # logical qubits
Figure 2: The number of nodes in the resource state
3.3 Example: Variational quantum algorithm to perform the three-layer QAOA circuit for the max-
cut problem of fully-connected graphs, before (Standard
We demonstrate the procedure 3.1 with quantum MBQC) and after (LC-MBQC) the node elimination pro-
approximate optimization algorithm (QAOA), cedure shown in Sec.3.1. The inset shows the ratio of
which is a heuristic variational algorithm for op- the graph state size before and after the procedure.
timization problems such as max-cut [53]. We
show in Fig.1 a) the typical circuit to perform an
evaluation of variational parameters ξ and θ for QAOA circuits for max-cut problems of com-
the max-cut problem of a fully-connected graph plete graphs with different sizes (number of log-
with four nodes. We transpile this circuit into a ical qubits). The resource state size required to
measurement pattern using graphix.Circuit class perform MBQC is significantly reduced by up to
as described in Section 2.2.2, which results in the a factor of 6. Generally, this method preprocesses
command sequence that requires the total graph all Pauli measurement corresponding to Clifford
state shown in Fig. 1 b). Using the procedure in gates in the original gate network, and thus its
Section, 3.1, the length of the command sequence effect is more significant for quantum algorithms
reduces from 156 to 50, which requires a much involving a large number of Clifford gates.
smaller graph state shown in Fig. 1 c). This can
be performed by the following python code:
4 Conclusion and Outlook
1 from graphix import Circuit
import networkx as nx
We have introduced LC-MBQC, a measurement
2
3 import numpy as np
4 n = 4 calculus formulation of MBQC with local Clifford
5 xi = np . random . rand (6) commands. With this, we have naturally inte-
6 theta = np . random . rand (4) grated an efficient graph state simulator as an
g = nx . complete_graph ( n )
7
MBQC pattern sequence preprocessing routine
8
9 circuit = Circuit ( n ) which allows the significant reduction of the size
10 for i , (u , v ) in enumerate ( g . edges ) : of the resource state required to execute universal
11 circuit . cnot (u , v ) quantum computations by single-qubit measure-
12 circuit . rz (v , xi [ i ])
ments only. We have implemented further opti-
13 circuit . cnot (u , v )
14 for v in g . nodes : mization strategies for pattern sequence, such as
15 circuit . rx (v , theta [ v ]) faster standardization and algorithms to reduce
16 the pattern space or the execution depth. We
17 pattern = circuit . transpile () further provide an MPS simulator backend, which
18 pattern . standardize ()
19 pattern . shift_signals () improves the classical simulation of MBQC.
20 pattern . p e r f o r m _ p a u l i _ m e a s u r e m e n t s () A natural extension of Graphix is the imple-
21 out_state = pattern . simulate_pattern () mentation of noise models for specific hardware
Listing 4: Optimizing single-layer QAOA pattern. implementations such as CV photonic architec-
tures with Bosonic codes. With this, we plan to
In Fig.2, we plot the number of nodes in integrate error correction algorithms for the one-
the resource state before and after pattern way model, such as topological error correction
.perform_pauli_measurements(), translated from [3], into the measurement pattern architecture.

7
Furthermore, it is possible to express and simu- B. Q. Baragiola, S. Guha, G. Dauphinais,
late unique approaches in the one-way model such K. K. Sabapathy, N. C. Menicucci, and
as blind quantum computations [8, 36] and dis- I. Dhand, Quantum 5, 392 (2021).
tributed MBQC [19, 54] thanks to the flexibility [12] S. Takeda and A. Furusawa, APL Photonics
of the pattern-based construction, thus making 4, 060902 (2019).
Graphix a suitable platform for further research [13] M. V. Larsen, X. Guo, C. R. Breum, J. S.
into the measurement-based model. Neergaard-Nielsen, and U. L. Andersen, Sci-
ence 366, 369 (2019).
Acknowledgement [14] W. Asavanant, Y. Shiozawa, S. Yokoyama,
B. Charoensombutamon, H. Emura, R. N.
S.S. is supported by EPSRC Grant Reference Alexander, S. Takeda, J. ichi Yoshikawa,
EP/S013105/1. Authors thank Christopher Foot N. C. Menicucci, H. Yonezawa, and A. Fu-
for reading the manuscript, Suguru Endo, Takuji rusawa, Science 366, 373 (2019).
Hiraoka and Yoshiki Matsuda for insightful dis- [15] T. M. Graham, Y. Song, J. Scott, C. Poole,
cussions and Ryosuke Suda for contribution to L. Phuttitarn, K. Jooya, P. Eichler, X. Jiang,
the library. A. Marra, B. Grinkemeyer, M. Kwon,
M. Ebert, J. Cherek, M. T. Lichtman,
References M. Gillette, J. Gilbert, D. Bowman, T. Bal-
lance, C. Campbell, E. D. Dahl, O. Craw-
[1] R. Raussendorf and H. J. Briegel, Phys. Rev. ford, N. S. Blunt, B. Rogers, T. Noel, and
Lett. 86, 5188 (2001). M. Saffman, Nature 604, 457 (2022).
[2] R. Raussendorf, D. E. Browne, and H. J. [16] D. Bluvstein, H. Levine, G. Semeghini,
Briegel, Phys. Rev. A 68, 022312 (2003). T. T. Wang, S. Ebadi, M. Kalinowski,
[3] R. Raussendorf, J. Harrington, and A. Keesling, N. Maskara, H. Pichler,
K. Goyal, New Journal of Physics 9, M. Greiner, V. Vuletić, and M. D. Lukin,
199 (2007). Nature 604, 451 (2022).
[4] K. Fujii, Quantum Computation with Topo- [17] M. DeCross, E. Chertkov, M. Kohagen, and
logical Codes (Springer Nature, 2015). M. Foss-Feig, Qubit-reuse compilation with
[5] A. Broadbent, J. Fitzsimons, and E. Kashefi, mid-circuit measurement and reset (2022),
50th Annual IEEE Symposium on Founda- arXiv:2210.08039 [physics.quant-ph] .
tions of Computer Science , 517 (2009). [18] Z.-P. Yang, H.-Y. Ku, A. Baishya, Y.-R.
[6] T. Morimae and K. Fujii, Nature Communi- Zhang, A. F. Kockum, Y.-N. Chen, F.-L. Li,
cations 3, 1036 (2012). J.-S. Tsai, and F. Nori, Phys. Rev. A 105,
[7] C. Greganti, T. F. Demarie, M. Ringbauer, 042610 (2022).
J. A. Jones, V. Saggio, I. A. Calafell, L. A. [19] V. Danos, E. Kashefi, and P. Panangaden, J.
Rozema, A. Erhard, M. Meth, L. Postler, ACM 54, 8 (2007).
R. Stricker, P. Schindler, R. Blatt, T. Monz,
[20] V. Danos, E. Kashefi, P. Panangaden, and
P. Walther, and J. F. Fitzsimons, Phys. Rev.
S. Perdrix, Semantic Techniques in Quan-
X 11, 031049 (2021).
tum Computation, edited by S. Gay and
[8] A. Broadbent and E. Kashefi, Theoretical
I. Mackie (Cambridge University Press,
Computer Science 410, 2489 (2009).
2009) p. 235–310.
[9] M. V. Larsen, C. Chamberland, K. Noh,
[21] S. Anders and H. J. Briegel, Phys. Rev. A
J. S. Neergaard-Nielsen, and U. L. Ander-
73, 022334 (2006).
sen, PRX Quantum 2, 030325 (2021).
[10] W. Asavanant, B. Charoensombutamon, [22] S. Aaronson and D. Gottesman, Phys. Rev.
S. Yokoyama, T. Ebihara, T. Nakamura, A 70, 052328 (2004).
R. N. Alexander, M. Endo, J.-i. Yoshikawa, [23] M. A. Nielsen and I. L. Chuang, Quan-
N. C. Menicucci, H. Yonezawa, and A. Furu- tum Computation and Quantum Informa-
sawa, Phys. Rev. Applied 16, 034005 (2021). tion: 10th Anniversary Edition (Cambridge
[11] J. E. Bourassa, R. N. Alexander, M. Vas- University Press, 2010).
mer, A. Patil, I. Tzitrin, T. Matsuura, D. Su, [24] G. Vidal, Phys. Rev. Lett. 91, 147902 (2003).

8
[25] D. Gross, J. Eisert, N. Schuch, and D. Perez- [42] M. Fukushima, Y. Matsuda and S. Sunami,
Garcia, Phys. Rev. A 76, 052315 (2007). in preparation.
[26] Graphix, https://github.com/ [43] R. R. Ferguson, L. Dellantonio, A. A.
TeamGraphix/graphix (2022). Balushi, K. Jansen, W. Dür, and C. A.
[27] M. B. Elliott, B. Eastin, and C. M. Caves, Muschik, Phys. Rev. Lett. 126, 220501
Phys. Rev. A 77, 042307 (2008). (2021).
[28] M. Houshmand, M. Houshmand, and J. F. [44] Paddle Quantum, https://github.com/
Fitzsimons, Phys. Rev. A 98, 012318 (2018). PaddlePaddle/Quantum (2020).
[29] V. Danos and E. Kashefi, Phys. Rev. A 74, [45] A. Evans, S. Omonije, R. Soulé, and
052310 (2006). R. Rand, Mcbeth: A measurement based
[30] D. E. Browne, E. Kashefi, M. Mhalla, and quantum programming language (2022),
S. Perdrix, New Journal of Physics 9, 250 arXiv:2204.10784 .
(2007). [46] M. A. Nielsen, Physics Letters A 308, 96
[31] M. Mhalla and S. Perdrix, in Automata, (2003).
Languages and Programming, edited by [47] C. Gidney, Quantum 5, 497 (2021).
L. Aceto, I. Damgård, L. A. Goldberg, [48] M. B. Elliott, B. Eastin, and C. M. Caves,
M. M. Halldórsson, A. Ingólfsdóttir, and Journal of Physics A: Mathematical and
I. Walukiewicz (Springer Berlin Heidelberg, Theoretical 43, 025301 (2009).
Berlin, Heidelberg, 2008) pp. 857–868. [49] B. Coecke and R. Duncan, New Journal of
[32] U. Schollwöck, Annals of Physics 326, 96 Physics 13, 043016 (2011).
(2011), january 2011 Special Issue. [50] T. McElvanney and M. Backens, Com-
[33] Y.-Y. Shi, L.-M. Duan, and G. Vidal, Phys. plete flow-preserving rewrite rules for mbqc
Rev. A 74, 022320 (2006). patterns with pauli measurements (2022),
[34] I. L. Markov and Y. Shi, SIAM Journal on arXiv:2205.02009 .
Computing 38, 963 (2008). [51] A. W. Cross, L. S. Bishop, J. A. Smolin,
[35] M. Van den Nest, W. Dür, G. Vidal, and and J. M. Gambetta, Open quantum as-
H. J. Briegel, Phys. Rev. A 75, 012337 sembly language (2017), arXiv:1707.03429
(2007). [physics.quant-ph] .
[36] T. Morimae, Phys. Rev. A 85, 062328 (2012). [52] A. Kissinger and J. van de Wetering, in Pro-
[37] L. Fang, ahehn-nv, hhbayraktar, and sam- ceedings 16th International Conference on
stanwyck, Nvidia/cuquantum: cuquantum Quantum Physics and Logic, Electronic Pro-
v22.11.0 (2022). ceedings in Theoretical Computer Science,
[38] T. Vincent, L. J. O’Riordan, M. Andrenkov, Vol. 318, edited by B. Coecke and M. Leifer
J. Brown, N. Killoran, H. Qi, and I. Dhand, (Open Publishing Association, 2020) pp.
Quantum 6, 709 (2022). 229–241.
[39] C. Roberts, A. Milsted, M. Ganahl, A. Zal- [53] E. Farhi, J. Goldstone, and S. Gutmann,
cman, B. Fontaine, Y. Zou, J. Hidary, G. Vi- A quantum approximate optimization algo-
dal, and S. Leichenauer, Tensornetwork: A rithm (2014), arXiv:1411.4028 .
library for physics and machine learning [54] E. D’Hondt and Y. Vandriessche, Unconven-
(2019), arXiv:1905.01330 . tional Computation, Lecture Notes in Com-
[40] Y. A. Liu, X. L. Liu, F. N. Li, H. Fu, puter Science 5715, 110 (2009).
Y. Yang, J. Song, P. Zhao, Z. Wang,
D. Peng, H. Chen, C. Guo, H. Huang,
W. Wu, and D. Chen, in Proceedings of the
International Conference for High Perfor- A Clifford commands
mance Computing, Networking, Storage and
Analysis (Association for Computing Ma- Pauli measurements of a graph state performed
chinery, New York, NY, USA, 2021). in the graph state simulator [27] result in a graph
[41] Y. Zhou, E. M. Stoudenmire, and X. Wain- state with local-Clifford decorations up to one
tal, Phys. Rev. X 10, 041038 (2020). H, S and Z gates on each nodes i.e. the post-

9
measurement state is [48]

CZl,m |+i⊗n ,
Y Y Y Y
|gi = Hi Sj Zk
i∈Hg j∈Sg k∈Zg (l,m)∈Eg
(7)
where Hg , Sg and Zg are the sets of nodes with
decorations with each Clifford gates, Eg is the set
of edges and n is the number of nodes in the
graph. There are 7 unique Clifford commands to
be used in the procedure described in Section 3.1
for which we list their effect on Pauli X, Y and
Z gates as follows. The rotation of measurement
angle (6) follows from Table 1 for any k, λ and α.
† † †
cmd OC OC XOC OC Y OC OC ZOC
C0 H Z −Y X
C1 S −Y X Z
C2 Z −X −Y Z
C3 HS Z −X −Y
C4 HZ Z Y −X
C5 SZ Y −X Z
C6 HSZ Z X Y

Table 1: Effect of single-qubit Clifford operators on

Pauli operators.

10