# A compiler for universal photonic quantum computers

1st Felix Zilk
4thKarl Fürlinger  Christian Doppler Laboratory
for Photonic Quantum Computer
Faculty of Physics
University of Vienna
Vienna, Austria
<EMAIL_ADDRESS>MNM-Team
Ludwig-Maximilians-
Universität (LMU)
Munich, Germany
<EMAIL_ADDRESS>2nd Korbinian Staudacher

5th Dieter Kranzlmüller  MNM-Team
Ludwig-Maximilians-
Universität (LMU)
Munich, Germany
<EMAIL_ADDRESS>MNM-Team
Leibniz Supercomputing
Centre (LRZ)
Garching, Germany
<EMAIL_ADDRESS>3rd Tobias Guggemos
6th Philip Walther  Christian Doppler Laboratory
for Photonic Quantum Computer
Faculty of Physics
University of Vienna
Vienna, Austria
<EMAIL_ADDRESS>Christian Doppler Laboratory
for Photonic Quantum Computer
Faculty of Physics
University of Vienna
Vienna, Austria
<EMAIL_ADDRESS>
###### Abstract

Photons are a natural resource in quantum information, and the last decade
showed significant progress in high-quality single photon generation and
detection. Furthermore, photonic qubits are easy to manipulate and do not
require particularly strongly sealed environments, making them an appealing
platform for quantum computing. With the one-way model, the vision of a
universal and large-scale quantum computer based on photonics becomes
feasible. In one-way computing, the input state is not an initial product
state $\ket{0}^{\otimes n}$, but a so-called cluster state. A series of
measurements on the cluster state’s individual qubits and their temporal
order, together with a feed-forward procedure, determine the quantum circuit
to be executed. We propose a pipeline to convert a QASM circuit into a graph
representation named measurement-graph (m-graph), that can be directly
translated to hardware instructions on an optical one-way quantum computer. In
addition, we optimize the graph using ZX-Calculus before evaluating the
execution on an experimental discrete variable photonic platform.

###### Index Terms:

Quantum Computing, Photonic QC, Measurement Based QC, One-way QC, ZX-Calculus

12341234123412431243123414231234“Linear”$H_{1,3,4}\ket{GHZ}$“Box”“GHZ”$H_{1,4}\ket{\psi}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$LinearGHZgraph
statesgraph states Figure 1: Generation of the 4-qubit Linear and GHZ graph
state from
$\ket{\psi}=\frac{1}{2}(\ket{0000}+\ket{0011}+\ket{1100}-\ket{1111})$ and
$\ket{G\\!H\\!Z}=\frac{1}{\sqrt{2}}(\ket{0000}+\ket{1111})$. The graph states
in each are local complementary (l.c.) with each-other, and can be use as
input states for the one-way-model.

##  I Introduction

Photons are a natural candidate for quantum computing, yet such systems are
not very prevalent in Cloud or High-Performance Computing (HPC) platforms.
However, photonic systems should be considered a valid competitor to other
platforms; recent findings show setups with up to 14 entangled photons [1].

HPC is in an era of specialization, where an increasing number of accelerator
devices are integrated in general-purpose computing machines [2]. Quantum
computers represent an especially powerful type of accelerator, promising
speed-ups for unstructured search and combinatorial optimization problems [3,
4, 5]. As quantum technology matures, it is important to enable integration of
quantum processing units (QPUs) in the HPC ecosystem and to support
heterogeneous programming that integrates classical and quantum aspects, for
example by means of offloading [6, 7, 8, 9, 10, 11]. Here, quantum algorithms
are usually expressed as offloaded computational kernels in a domain-specific
language for the quantum circuit model (e.g., QASM) [12, 8].

Although photons are an attractive platform for QPUs, a direct translation of
the quantum circuit model into photonic components is impractical. Photonic
two-qubit gates are intrinsically probabilistic; hence, an increasing number
of gates comes with an exponential decrease in the circuit’s success
probability. That is why measurement-based schemes [13, 14, 15] are an
appealing alternative, in particular the one-way model of quantum computing
[15, 16, 17, 18]. Here, computation is carried out solely by single-qubit
measurements on highly-entangled multipartite states – so-called cluster
states [19]. The model is equivalent to the circuit model [20], but efficient
methods for translation are still rare [21, 22].

#### Contribution

This paper describes our efforts to develop a compiler for QASM kernels that
targets discrete variable photonic platforms. We propose a pipeline to
translate from QASM to a graph representation, named measurement-graph, or
m-graph. The m-graph is optimized with ZX-Calculus [23] and mapped to hardware
instructions for a photonic one-way processor. This marks a first step towards
accessing photonic QPUs with HPC systems.

##  II Background

The quantum circuit model performs computations by sequentially applying
unitary gates to qubits in a quantum register. Typically, one initializes a
register of $n$ qubits in the product state $\ket{0}^{\otimes n}$ [4].

In contrast to the circuit model, the paradigm of quantum annealing [24] bases
on the unitary evolution of the underlying system Hamiltonian.

###  II-A The measurement-based one-way model

The one-way model, however, bases entirely on adaptive single-qubit
measurements that drive the computation [15, 14, 25]. Here, the initial state
of individual qubits is the $\ket{+}$ state, and they are pairwise coupled via
$CZ$ operations to form a graph state, which serves as the computational
resource. Then, single-qubit measurements on this resource state achieve
universal quantum computation.

A cluster state is a type of graph state in which the underlying graph
structure has the form of a two-dimensional orthogonal grid. Graph states are
highly-entangled multipartite states, and we represent them mathematically as
a graph $G(V,E)$, with vertices $V$ representing physical qubits and edges $E$
indicating entanglement between qubits. An arbitrary graph state $\ket{G}$ of
$V$ qubits and $E$ edges is [26]

$\ket{G}=\left(\prod_{(a,b)\in E}CZ_{a,b}\right)\bigotimes_{v\in
V}\ket{+}_{v}$ (1)

Fig. 1 shows a collection of 4-qubit cluster states, arranged as a two-
dimensional lattice. The states are locally complementary (l.c.) if one can be
transformed into the other with single-qubit transformations and SWAP
operations only.

To carry out computation, we subsequentially measure on connected physical
qubits $j$ in the equatorial basis
$\mathcal{B}_{j}(\alpha)=\\{\ket{\alpha}_{j},\ket{-\alpha}_{j}\\}$, where
$\ket{\pm\alpha}_{j}=1/\sqrt{2}(\ket{0}_{j}\pm e^{i\alpha}\ket{1}_{j})$.
Measurements of physical qubits in the basis $\mathcal{B}_{j}(\alpha)$ induce
the rotation $HR_{z}\left(-\alpha\right)\ket{\psi}$ on encoded logical qubits
up to a Pauli-$X$ correction (cf. Fig. 2). $CZ$ gates are inherently built
into the computational resource state as links between two qubits.

Thus, the native gate set in the one-way model may be defined as
$\mathcal{G}=\\{HR_{z}(-\alpha),CZ\\}$, which is indeed universal.

Unlike the unitary evolution in the gate-based model, the non-unitary action
of measurement is irreversible. As each measurement’s outcome is random, the
desired result only occurs in some cases. Hence, a feed-forward protocol [18]
compensates undesired results by adapting future measurement bases according
to earlier outcomes.

12341234123412431243123414231234“Linear”$H_{1,3,4}\ket{GHZ}$“Box”“GHZ”$H_{1,4}\ket{\psi}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$LinearGHZgraph
statesgraph
states$\ket{\psi}$$R_{z}(-\alpha)$H$\ket{\psi}$$R_{z}(-\alpha)$H$\rightarrow
X^{m}$ $\ket{\psi^{\prime}}$ $\ket{+}$✗One-Way-Model$\rightarrow$
$\ket{\psi^{\prime}}$$\rightarrow m=\\{0,1\\}$ Figure 2: Circuit
representation of the conceptual difference between the circuit model with
unitary transformation and the one-way model. Upper circuit: shows the
transformation of a qubit in state $\ket{\psi}$ with the unitary
$HR_{z}(-\alpha)$ to state $\ket{\psi^{\prime}}$. Lower circuit: shows the
same transformation with the one-way model, where the new state
$\ket{\psi^{\prime}}$ is than teleported to the bottom qubit by measuring the
upper one (up to a Pauli-$X$ correction, that is based on the measurements
output $m$).

As an example, refer to the single-qubit computation in Fig. 2. The result $m$
of the upper wire measurement (red cross mark) influences the Pauli-$X$
correction on the lower output wire. If the outcome is $m=0$, the algorithm
works as expected; however, if $m=1$, a Pauli error is introduced and
corrected before the final measurement. The cascaded execution of this
procedure allows for the implementation of arbitrary single-qubit rotations.
In fact, feed-forward control makes one-way quantum computation deterministic.

Furthermore, any quantum circuit can be converted to a measurement pattern on
a sufficiently large cluster state [15, 14, 25].

TABLE I: Some elementary quantum gates and their respective representation in
a ZX-diagram.

Name | Z | Z-Phase | X | X-Phase | CNOT | CZ
---|---|---|---|---|---|---
Matrix | $\begin{pmatrix}1&0\\\ 0&-1\end{pmatrix}$ |  $\begin{pmatrix}1&0\\\ 0&e^{i\alpha}\end{pmatrix}$ | $\begin{pmatrix}0&1\\\ 1&0\end{pmatrix}$ | $\frac{1}{2}\begin{pmatrix}1+e^{i\alpha}&1-e^{i\alpha}\\\ 1-e^{i\alpha}&1+e^{i\alpha}\end{pmatrix}$ | $\begin{pmatrix}1&0&0&0\\\ 0&1&0&0\\\ 0&0&0&1\\\ 0&0&1&0\end{pmatrix}$ | $\begin{pmatrix}1&0&0&0\\\ 0&1&0&0\\\ 0&0&1&0\\\ 0&0&0&-1\end{pmatrix}$
Gate |  |  |  |  | $\Qcircuit@C=.5em@R=1em$ |
$&$ @C=.5em @R=1em |  1 |  |  |
${\\\ }$ |  12341234123412431243123414231234“Linear”$H_{1,3,4}\ket{GHZ}$“Box”“GHZ”$H_{1,4}\ket{\psi}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$LinearGHZgraph statesgraph states$\ket{\psi}$$R_{z}(-\alpha)$H$\ket{\psi}$$R_{z}(-\alpha)$H$\rightarrow X^{m}$ $\ket{\psi^{\prime}}$ $\ket{+}$✗One-Way-Model$\rightarrow$ $\ket{\psi^{\prime}}$$\rightarrow m=\\{0,1\\}$$\pi$ |  12341234123412431243123414231234“Linear”$H_{1,3,4}\ket{GHZ}$“Box”“GHZ”$H_{1,4}\ket{\psi}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$LinearGHZgraph statesgraph states$\ket{\psi}$$R_{z}(-\alpha)$H$\ket{\psi}$$R_{z}(-\alpha)$H$\rightarrow X^{m}$ $\ket{\psi^{\prime}}$ $\ket{+}$✗One-Way-Model$\rightarrow$ $\ket{\psi^{\prime}}$$\rightarrow m=\\{0,1\\}$$\pi$$\alpha$ |  12341234123412431243123414231234“Linear”$H_{1,3,4}\ket{GHZ}$“Box”“GHZ”$H_{1,4}\ket{\psi}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$LinearGHZgraph statesgraph states$\ket{\psi}$$R_{z}(-\alpha)$H$\ket{\psi}$$R_{z}(-\alpha)$H$\rightarrow X^{m}$ $\ket{\psi^{\prime}}$ $\ket{+}$✗One-Way-Model$\rightarrow$ $\ket{\psi^{\prime}}$$\rightarrow m=\\{0,1\\}$$\pi$$\alpha$$\pi$ |  12341234123412431243123414231234“Linear”$H_{1,3,4}\ket{GHZ}$“Box”“GHZ”$H_{1,4}\ket{\psi}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$LinearGHZgraph statesgraph states$\ket{\psi}$$R_{z}(-\alpha)$H$\ket{\psi}$$R_{z}(-\alpha)$H$\rightarrow X^{m}$ $\ket{\psi^{\prime}}$ $\ket{+}$✗One-Way-Model$\rightarrow$ $\ket{\psi^{\prime}}$$\rightarrow m=\\{0,1\\}$$\pi$$\alpha$$\pi$$\alpha$ | 12341234123412431243123414231234“Linear”$H_{1,3,4}\ket{GHZ}$“Box”“GHZ”$H_{1,4}\ket{\psi}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$LinearGHZgraph statesgraph states$\ket{\psi}$$R_{z}(-\alpha)$H$\ket{\psi}$$R_{z}(-\alpha)$H$\rightarrow X^{m}$ $\ket{\psi^{\prime}}$ $\ket{+}$✗One-Way-Model$\rightarrow$ $\ket{\psi^{\prime}}$$\rightarrow m=\\{0,1\\}$$\pi$$\alpha$$\pi$$\alpha$ | 12341234123412431243123414231234“Linear”$H_{1,3,4}\ket{GHZ}$“Box”“GHZ”$H_{1,4}\ket{\psi}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$LinearGHZgraph statesgraph states$\ket{\psi}$$R_{z}(-\alpha)$H$\ket{\psi}$$R_{z}(-\alpha)$H$\rightarrow X^{m}$ $\ket{\psi^{\prime}}$ $\ket{+}$✗One-Way-Model$\rightarrow$ $\ket{\psi^{\prime}}$$\rightarrow m=\\{0,1\\}$$\pi$$\alpha$$\pi$$\alpha$

###  II-B Implementation with a photonic processor

Photons are excellent candidates for building quantum computers; they are easy
to generate and detect, robust against decoherence, and optical experiments
can realize accurate single-qubit gates easily. However, deterministic
interactions of two photons are experimentally impossible, and photonic two-
qubit gates are of probabilistic nature [15, 16].

In the one-way model, these nondeterministic operations prepare the cluster
state, just before any logical computation takes place [16, 15].

Post-selection techniques ensure successful generation of cluster states, such
that it ignores certain detection events from the results where the cluster
state generation failed [17, 18].

High-precision measurements in an arbitrary basis are achieved, for example,
with phase retarders (wave plates) for qubits encoded in photon polarization.
After successfully generating the multi-photon cluster, the computation
proceeds deterministically by sequential execution of such single-qubit
measurements.

Despite its limitations for implementing a pure circuital model, photonic
qubits are well-suited to the one-way model. Hence, the challenge to realizing
universal photonic quantum computing lies in the efficient creation of
sufficiently large cluster states. Various such protocols have been proposed
and implemented [27, 28, 29, 1]. In fact, smaller clusters can already
implement interestingly large circuits such as the Grover search in Fig. 5.

Fig. 3 shows how a photonic QPU can run a quantum circuit on a cluster state
created from four photons. The input state generation step may be viewed
independently from the computing and measurement steps that executes the
necessary measurements for the post-selection and information processing.

Coupler
---
QWP
---
Detector
---
PBS
---
HWP
---
Free Space
---
Fiber Link
---
a
---
(1)
---
(1)
---
(2)
---
(3)
---
(4)
---
Cluster state
---
Computing &
---
Measurement
---
generation
---
b
---
c
---
d
---
Figure 3: A photonic quantum processing unit (QPU) to execute a graph state of
4 nodes, as in Fig. 1. The input are four single-photons in four fiber links.
Half-wave plates (HWPs) initialize their states to $\ket{D}\equiv\ket{+}$
before they are pairwise entangled by polarizing beam splitters (PBSs) to
create the cluster state. The combination of a quarter-wave plate (QWP) and a
HWP before the detectors allow measurements in arbitrary bases.

###  II-C ZX-Calculus

The ZX-Calculus is a diagrammatic language for quantum computation. A ZX-
diagram consists of spiders and wires, which represent linear maps. Like the
known quantum circuit notation, wires entering the diagram from the left are
called input wires, and wires exiting to the right are called output wires.

Spiders are distinguished into Z (green) and X (red) spiders and can have any
number of input and output wires. In Dirac notation, their linear maps are:

12341234123412431243123414231234“Linear”$H_{1,3,4}\ket{GHZ}$“Box”“GHZ”$H_{1,4}\ket{\psi}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$LinearGHZgraph
statesgraph
states$\ket{\psi}$$R_{z}(-\alpha)$H$\ket{\psi}$$R_{z}(-\alpha)$H$\rightarrow
X^{m}$ $\ket{\psi^{\prime}}$ $\ket{+}$✗One-Way-Model$\rightarrow$
$\ket{\psi^{\prime}}$$\rightarrow
m=\\{0,1\\}$$\pi$$\alpha$$\pi$$\alpha$$\alpha$$\vdots$$\vdots$$\alpha$$\vdots$$\vdots$$:=\ket{0}^{\otimes
m}\\!\bra{0}^{\otimes n}$$+e^{i\alpha}\ket{1}^{\otimes m}\\!\bra{1}^{\otimes
n}$$:=\ket{+}^{\otimes m}\\!\bra{+}^{\otimes n}$$+e^{i\alpha}\ket{-}^{\otimes
m}\\!\bra{-}^{\otimes n}$$m$$n$$m$$n$ (2)

Apart from the normal wire corresponding to $\mathbb{I}_{2}$, it is convenient
to introduce another wire type for representing the Hadamard matrix:

12341234123412431243123414231234“Linear”$H_{1,3,4}\ket{GHZ}$“Box”“GHZ”$H_{1,4}\ket{\psi}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$LinearGHZgraph
statesgraph
states$\ket{\psi}$$R_{z}(-\alpha)$H$\ket{\psi}$$R_{z}(-\alpha)$H$\rightarrow
X^{m}$ $\ket{\psi^{\prime}}$ $\ket{+}$✗One-Way-Model$\rightarrow$
$\ket{\psi^{\prime}}$$\rightarrow
m=\\{0,1\\}$$\pi$$\alpha$$\pi$$\alpha$$\alpha$$\vdots$$\vdots$$\alpha$$\vdots$$\vdots$$:=\ket{0}^{\otimes
m}\\!\bra{0}^{\otimes n}$$+e^{i\alpha}\ket{1}^{\otimes m}\\!\bra{1}^{\otimes
n}$$:=\ket{+}^{\otimes m}\\!\bra{+}^{\otimes n}$$+e^{i\alpha}\ket{-}^{\otimes
m}\\!\bra{-}^{\otimes n}$$m$$n$$m$$n$$:=$$\begin{pmatrix}1&0\\\
0&1\end{pmatrix}$$:=$$\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\\
1&-1\end{pmatrix}$ (3)

Two diagrams can be composed horizontally by joining the output wires of one
diagram to the input wires of the other, or vertically by placing them side by
side. In this way, any quantum circuit can be represented as a ZX-diagram,
moreover, most elementary quantum gates can be directly translated, as shown
in subsection II-A.

12341234123412431243123414231234“Linear”$H_{1,3,4}\ket{GHZ}$“Box”“GHZ”$H_{1,4}\ket{\psi}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$LinearGHZgraph
statesgraph
states$\ket{\psi}$$R_{z}(-\alpha)$H$\ket{\psi}$$R_{z}(-\alpha)$H$\rightarrow
X^{m}$ $\ket{\psi^{\prime}}$ $\ket{+}$✗One-Way-Model$\rightarrow$
$\ket{\psi^{\prime}}$$\rightarrow
m=\\{0,1\\}$$\pi$$\alpha$$\pi$$\alpha$$\alpha$$\vdots$$\vdots$$\alpha$$\vdots$$\vdots$$:=\ket{0}^{\otimes
m}\\!\bra{0}^{\otimes n}$$+e^{i\alpha}\ket{1}^{\otimes m}\\!\bra{1}^{\otimes
n}$$:=\ket{+}^{\otimes m}\\!\bra{+}^{\otimes n}$$+e^{i\alpha}\ket{-}^{\otimes
m}\\!\bra{-}^{\otimes n}$$m$$n$$m$$n$$:=$$\begin{pmatrix}1&0\\\
0&1\end{pmatrix}$$:=$$\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\\
1&-1\end{pmatrix}$$R_{x}(\alpha)$$R_{z}(\beta)$$R_{x}(\gamma)$$=$$=$$\alpha$$\beta$$\gamma$$\alpha$$\beta$$\gamma$
(a)

12341234123412431243123414231234“Linear”$H_{1,3,4}\ket{GHZ}$“Box”“GHZ”$H_{1,4}\ket{\psi}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$LinearGHZgraph
statesgraph
states$\ket{\psi}$$R_{z}(-\alpha)$H$\ket{\psi}$$R_{z}(-\alpha)$H$\rightarrow
X^{m}$ $\ket{\psi^{\prime}}$ $\ket{+}$✗One-Way-Model$\rightarrow$
$\ket{\psi^{\prime}}$$\rightarrow
m=\\{0,1\\}$$\pi$$\alpha$$\pi$$\alpha$$\alpha$$\vdots$$\vdots$$\alpha$$\vdots$$\vdots$$:=\ket{0}^{\otimes
m}\\!\bra{0}^{\otimes n}$$+e^{i\alpha}\ket{1}^{\otimes m}\\!\bra{1}^{\otimes
n}$$:=\ket{+}^{\otimes m}\\!\bra{+}^{\otimes n}$$+e^{i\alpha}\ket{-}^{\otimes
m}\\!\bra{-}^{\otimes n}$$m$$n$$m$$n$$:=$$\begin{pmatrix}1&0\\\
0&1\end{pmatrix}$$:=$$\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\\
1&-1\end{pmatrix}$$R_{x}(\alpha)$$R_{z}(\beta)$$R_{x}(\gamma)$$=$$=$$\alpha$$\beta$$\gamma$$\alpha$$\beta$$\gamma$$\alpha_{1}$$\pm\frac{\pi}{2}$$\alpha_{2}$$\alpha_{3}$$\alpha_{1}\mp\frac{\pi}{2}$$\alpha_{2}\mp\frac{\pi}{2}$$\alpha_{3}\mp\frac{\pi}{2}$$a$$\overset{(lc)}{=}$
(b)

12341234123412431243123414231234“Linear”$H_{1,3,4}\ket{GHZ}$“Box”“GHZ”$H_{1,4}\ket{\psi}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$LinearGHZgraph
statesgraph
states$\ket{\psi}$$R_{z}(-\alpha)$H$\ket{\psi}$$R_{z}(-\alpha)$H$\rightarrow
X^{m}$ $\ket{\psi^{\prime}}$ $\ket{+}$✗One-Way-Model$\rightarrow$
$\ket{\psi^{\prime}}$$\rightarrow
m=\\{0,1\\}$$\pi$$\alpha$$\pi$$\alpha$$\alpha$$\vdots$$\vdots$$\alpha$$\vdots$$\vdots$$:=\ket{0}^{\otimes
m}\\!\bra{0}^{\otimes n}$$+e^{i\alpha}\ket{1}^{\otimes m}\\!\bra{1}^{\otimes
n}$$:=\ket{+}^{\otimes m}\\!\bra{+}^{\otimes n}$$+e^{i\alpha}\ket{-}^{\otimes
m}\\!\bra{-}^{\otimes n}$$m$$n$$m$$n$$:=$$\begin{pmatrix}1&0\\\
0&1\end{pmatrix}$$:=$$\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\\
1&-1\end{pmatrix}$$R_{x}(\alpha)$$R_{z}(\beta)$$R_{x}(\gamma)$$=$$=$$\alpha$$\beta$$\gamma$$\alpha$$\beta$$\gamma$$\alpha_{1}$$\pm\frac{\pi}{2}$$\alpha_{2}$$\alpha_{3}$$\alpha_{1}\mp\frac{\pi}{2}$$\alpha_{2}\mp\frac{\pi}{2}$$\alpha_{3}\mp\frac{\pi}{2}$$a$$\overset{(lc)}{=}$$\alpha_{2}$$\alpha_{1}$$j\pi$$k\pi$$\gamma_{1}$$\beta_{1}$$\gamma_{2}$$\overset{(p)}{=}$$\alpha_{1}^{\prime}$$\alpha_{2}^{\prime}$$\gamma_{2}^{\prime}$$\beta_{1}^{\prime}$$\gamma_{1}^{\prime}$$u$$v$$\alpha_{i}^{\prime}=\alpha_{i}+k\pi$$\gamma_{i}^{\prime}=\gamma_{i}+j\pi$$\beta_{i}^{\prime}=\beta_{i}+(j+k+1)\pi$
(c)

Figure 4: (a) Transformation of a circuit for arbitrary single-qubit rotations
into an equivalent graph-like diagram. (b) Local complementation (lc) and (c)
Pivoting (p) rule applied on exemplary graph-like ZX-diagrams.

ZX-calculus is equipped with a set of sound and complete rules, allowing the
transformation of ZX-diagrams into equivalent ones wrt. their linear map.
Using those rules, we can transform any ZX-diagram into an equivalent graph-
like diagram, where we allow only Z spiders connected via Hadamard wires [30]
(cf. Fig. 3a).

These are especially useful for the one-way-model. They can be directly
interpreted as measurement patterns where the graph spanned by spiders and
Hadamard wires corresponds to a graph state. The spider’s angles correspond to
measurements in the equatorial basis of the Bloch sphere [31].

Recent research has shown promising results in reducing the complexity of
graph-like diagrams in terms of spiders and wires [30, 32].

This is mainly done by using two graph theoretic rewrite rules named Local
complementation and Pivoting which we can use to eliminate most of the
“Clifford” part in diagrams, i.e., spiders with an angle of $k\pi/2$,
$k\in\mathbb{Z}$. Local complementation applied on a spider with an odd
multiple of $\pi/2$ removes the spider and flips the Hadamard connections
between the neighboring spiders, whereas Pivoting applied on a pair of spiders
with an even multiple of $\pi/2$ removes the pair and flips the connections
between different sets of neighboring spiders (cf. Fig. 3b and 3c). Since
every spider in a graph-like diagram corresponds to a qubit in the one-way
model, we can use those rules to reduce the number of qubits needed for the
computation.

##  III Related Work

Several compiler frameworks and tools are currently available for executing
algorithms on gate-based QPUs or annealing devices [33, 12, 8]. Most high-
level programming tools use sequential execution of basic quantum gates [6, 9,
34, 12, 33].

The one-way quantum computing paradigm is fundamentally different from the
standard quantum circuit model (see Section II). To allow integrating photonic
one-way hardware into current programming frameworks and the HPC ecosystem, we
require translation from the circuit model.

The framework by Zhang Hezi et al. [21] aims particularly at mapping a quantum
circuit to a specific photonic hardware architecture. This hardware
abstraction model relies on a 2D lattice arrangement of resource state
generators (RSGs) that create a 3-qubit graph state in each clock cycle.

For translation, the scheme takes an input circuit and transpiles it to the
universal gate set $\\{J(\alpha),CZ\\}$ where $(J\left(\alpha\right)\equiv
HR_{z}(\alpha))$ and construct an (in general) non-planar graph out of it.
They separate this graph into multiple planar sub-graphs, each of which may
contain high-degree nodes, i.e., nodes with a large number of edges. Further
decomposition results in numerous appropriate low-degree (in their case, the
3-qubit GHZ-states) graph states and additional fusion operations. A clock
cycle marks the execution of one planar graph state mapped to the physical
layer on the considered hardware.

12341234123412431243123414231234“Linear”$H_{1,3,4}\ket{GHZ}$“Box”“GHZ”$H_{1,4}\ket{\psi}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$LinearGHZgraph
statesgraph
states$\ket{\psi}$$R_{z}(-\alpha)$H$\ket{\psi}$$R_{z}(-\alpha)$H$\rightarrow
X^{m}$ $\ket{\psi^{\prime}}$ $\ket{+}$✗One-Way-Model$\rightarrow$
$\ket{\psi^{\prime}}$$\rightarrow
m=\\{0,1\\}$$\pi$$\alpha$$\pi$$\alpha$$\alpha$$\vdots$$\vdots$$\alpha$$\vdots$$\vdots$$:=\ket{0}^{\otimes
m}\\!\bra{0}^{\otimes n}$$+e^{i\alpha}\ket{1}^{\otimes m}\\!\bra{1}^{\otimes
n}$$:=\ket{+}^{\otimes m}\\!\bra{+}^{\otimes n}$$+e^{i\alpha}\ket{-}^{\otimes
m}\\!\bra{-}^{\otimes n}$$m$$n$$m$$n$$:=$$\begin{pmatrix}1&0\\\
0&1\end{pmatrix}$$:=$$\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\\
1&-1\end{pmatrix}$$R_{x}(\alpha)$$R_{z}(\beta)$$R_{x}(\gamma)$$=$$=$$\alpha$$\beta$$\gamma$$\alpha$$\beta$$\gamma$$\alpha_{1}$$\pm\frac{\pi}{2}$$\alpha_{2}$$\alpha_{3}$$\alpha_{1}\mp\frac{\pi}{2}$$\alpha_{2}\mp\frac{\pi}{2}$$\alpha_{3}\mp\frac{\pi}{2}$$a$$\overset{(lc)}{=}$$\alpha_{2}$$\alpha_{1}$$j\pi$$k\pi$$\gamma_{1}$$\beta_{1}$$\gamma_{2}$$\overset{(p)}{=}$$\alpha_{1}^{\prime}$$\alpha_{2}^{\prime}$$\gamma_{2}^{\prime}$$\beta_{1}^{\prime}$$\gamma_{1}^{\prime}$$u$$v$$\alpha_{i}^{\prime}=\alpha_{i}+k\pi$$\gamma_{i}^{\prime}=\gamma_{i}+j\pi$$\beta_{i}^{\prime}=\beta_{i}+(j+k+1)\pi$HH$R_{z}(-\gamma)$$R_{z}(-\delta)$HHXXH+HXXHH$\ket{0}$$\ket{0}$$\gamma$$\delta$$\pi$$\pi$$\pi$$\pi$$\gamma$$\delta$$\pi$$\pi$$\pi$$\pi$
$\gamma^{\prime}$ $\pi$ $\delta^{\prime}$ $\pi$
in1in2out1out2$\gamma\\!+\\!\pi$$\delta\\!+\\!\pi$in1in2$\pi$$\pi$out1out2(2,3)(4.a)(4.b)(5)(1)“Box
Cluster”abdd Figure 5: The “Box” Cluster for four physical qubits (centrally
located) translates into full Grover search for two qubits. Our pipeline takes
the circuit description of this Grover algorithm as an input and translates it
to the m-graph which is then optimized and corresponds to a “Box” Cluster. The
measurement angles $\gamma^{\prime},\delta^{\prime}$ are adapted according to
the hardware.

Vijayan Madhav Krishnan et al. [22] propose a framework using the stabilizer
formalism. It converts a high-level description of a quantum circuit into a
set of instructions for graph state preparation together with local operations
and non-Pauli measurements. The approach is a modification of the
Initialization-CNOT-Measurement (ICM) model, together with the single-qubit
teleportation technique.

First, they decompose the quantum circuit into Clifford and $T$ gate
operations, the latter of which are performed via measurement-induced $T$ and
$T^{\dagger}$ gate teleportation. The resulting intermediate circuit – called
inverse ICM decomposition – consists of a block of Clifford operations, Pauli
corrections, and measurements in bases $\mathcal{B}_{j}(\pm\frac{\pi}{4})$.
Since Clifford operations can be efficiently simulated, a classical computer
calculates the output state of the Clifford block. The resulting stabilizer
state translates to a graph state. With that at hand, the hardware
instructions include the resulting graph state together with single-qubit
unitaries (due to conversion) and non-Pauli measurements.

##  IV Compiler

###  IV-A Compiler pipeline

To execute an arbitrary QASM file on a photonic one-way processor, we perform
the following translation and optimization steps (see also Fig. 5):

#### Step 1

We transpile an arbitrary QASM file as an input in the universal gate set
$\\{R_{x}(\theta),R_{z}(\theta),H,CX,CZ\\}$. Various tools for this were
proposed in the past [34, 35, 36, 37].

#### Step 2

We rewrite the circuit as a sequence of $HR_{z}(\theta)$ and $CZ$ operations
as follows:

$\displaystyle R_{z}(\theta)$ $\displaystyle=[HR_{z}(0)][HR_{z}(\theta)]$ (4)
$\displaystyle H$ $\displaystyle=HR_{z}(0)$ $\displaystyle R_{x}(\theta)$
$\displaystyle=[HR_{z}(\theta)][HR_{z}(0)]$ $\displaystyle CNOT$
$\displaystyle=[\mathbb{I}\otimes H]CZ[\mathbb{I}\otimes H]$

#### Step 3

The m-graph is defined by the sequence of $HR_{z}(\theta)$ and $CZ$: The
number of qubits in the circuit defines the number of rows of the m-graph. A
horizontal edge between two vertices in the m-graph corresponds to a logical
$HR_{z}(-\alpha)$ operation and a physical measurement in the basis
$\mathcal{B}_{j}(\alpha)$ on the next physical qubit to the right. Similarly,
a $CZ$ corresponds to a vertical connection between two qubits [38].

#### Step 4

We interpret this m-graph as a graph-like (4.a) diagram in ZX-calculus and
optimize it (4.b).

#### Step 5

The resulting m-graph defines the required input graph state. Each vertex
shows the angle $(\alpha)$ and its position in the graph defines its order of
execution.

###  IV-B Optimization

We optimize the graph-like diagram of ZX-Calculus with phase teleportation
from [39] to eliminate redundant non-Clifford spiders, followed by the
algorithm from [30] to eliminate Clifford spiders. Since both optimization
strategies preserve the graph-like property, we can still interpret the
diagram as m-graph.

##  V Hardware Instructions

###  V-A Cluster state generation

For universal computation, we need an arbitrary connected graph state as an
input. In particular, the photonic setup in Fig. 3 generates
$\ket{G\\!H\\!Z}=\frac{1}{\sqrt{2}}(\ket{0000}+\ket{1111})$ and
$\ket{\psi}=\frac{1}{2}(\ket{0000}+\ket{0011}+\ket{1100}-\ket{1111})$ as input
states [28]. By activating111In an actual hardware setup, activating
corresponds to an angle of $22.5^{\circ}$, while deactivating corresponds to
$0^{\circ}$. For simulation, we can certainly just remove the HWP from the
optical circuit. or deactivating the half-wave plate (HWP) between the two
bottom polarizing beam splitters (PBS), we produce the $\ket{GHZ}$ or
$\ket{\psi}$ states, respectively. With that, we can realize arbitrary
4-photon graph states of Fig. 1 as such:

Linear:

The 4-qubit linear cluster is equivalent to $\ket{\psi}$ up to a local
operation $H_{1}H_{4}$ (see row 1, column 1 in Fig. 1). Up to additional local
(1-qubit + SWAP) operations, it is also equivalent to arbitrary connected
4-qubit clusters (e.g., the “Box”, see row 1 in Fig. 1). The only exceptions
are the GHZ graph and the fully connected graph (see row 2 in Fig. 1)

GHZ:

In the 4-qubit GHZ cluster, all nodes connect towards a single node (see row
2, column 1 in Fig. 6). Up to local (1-qubit) operations, it is equivalent to
the $\ket{G\\!H\\!Z}$ state and to a fully connected 4-qubit graph (see row 2
in Fig. 1)

In theory, the setup allows extension for producing $\ket{G\\!H\\!Z}$ and
$\ket{\psi}$ states for an arbitrary number of qubits, however, for larger
graphs, other setups are more suitable [1]. Please note that for three qubits,
the GHZ and linear cluster states are identical and GHZ with $>4$ qubits does
not fit the definition of a cluster state.

###  V-B Graph state generation with fusion

After the optimization in Step 4, we are left with a m-graph that is not
locally complementary to the GHZ or linear graph state. Hence, we decompose
the m-graph to a set of GHZ- and linear graph states, respectively. The
extraction works as follows:

  1. 1.

Find all nodes that have $>2$ edges and order them with respect to number of
their direct neighbors. Those are the nodes which will become “roots” of a GHZ
graph state.

  2. 2.

Extract all GHZ graph states and remove them from the ZX-graph until no node
with $>2$ neighbors is left.

  3. 3.

All other spiders that have $\leq 2$ neighbors are considered to be part of
linear graph states and are extracted until the graph is empty.

Fig. 6 shows the decomposition of a ZX-graph that was extracted from the
“bell-n4” circuit from QASMBench [40] with four logical qubits and 22 gates
(of which 7 are two-qubit gates). After optimization, we are left with a ZX-
graph of 10 spiders, which is decomposed into 4 graph states that can be
implemented on hardware such as the one in Fig. 3.

12341234123412431243123414231234“Linear”$H_{1,3,4}\ket{GHZ}$“Box”“GHZ”$H_{1,4}\ket{\psi}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$$\overset{l.c.}{=}$LinearGHZgraph
statesgraph
states$\ket{\psi}$$R_{z}(-\alpha)$H$\ket{\psi}$$R_{z}(-\alpha)$H$\rightarrow
X^{m}$ $\ket{\psi^{\prime}}$ $\ket{+}$✗One-Way-Model$\rightarrow$
$\ket{\psi^{\prime}}$$\rightarrow
m=\\{0,1\\}$$\pi$$\alpha$$\pi$$\alpha$$\alpha$$\vdots$$\vdots$$\alpha$$\vdots$$\vdots$$:=\ket{0}^{\otimes
m}\\!\bra{0}^{\otimes n}$$+e^{i\alpha}\ket{1}^{\otimes m}\\!\bra{1}^{\otimes
n}$$:=\ket{+}^{\otimes m}\\!\bra{+}^{\otimes n}$$+e^{i\alpha}\ket{-}^{\otimes
m}\\!\bra{-}^{\otimes n}$$m$$n$$m$$n$$:=$$\begin{pmatrix}1&0\\\
0&1\end{pmatrix}$$:=$$\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\\
1&-1\end{pmatrix}$$R_{x}(\alpha)$$R_{z}(\beta)$$R_{x}(\gamma)$$=$$=$$\alpha$$\beta$$\gamma$$\alpha$$\beta$$\gamma$$\alpha_{1}$$\pm\frac{\pi}{2}$$\alpha_{2}$$\alpha_{3}$$\alpha_{1}\mp\frac{\pi}{2}$$\alpha_{2}\mp\frac{\pi}{2}$$\alpha_{3}\mp\frac{\pi}{2}$$a$$\overset{(lc)}{=}$$\alpha_{2}$$\alpha_{1}$$j\pi$$k\pi$$\gamma_{1}$$\beta_{1}$$\gamma_{2}$$\overset{(p)}{=}$$\alpha_{1}^{\prime}$$\alpha_{2}^{\prime}$$\gamma_{2}^{\prime}$$\beta_{1}^{\prime}$$\gamma_{1}^{\prime}$$u$$v$$\alpha_{i}^{\prime}=\alpha_{i}+k\pi$$\gamma_{i}^{\prime}=\gamma_{i}+j\pi$$\beta_{i}^{\prime}=\beta_{i}+(j+k+1)\pi$HH$R_{z}(-\gamma)$$R_{z}(-\delta)$HHXXH+HXXHH$\ket{0}$$\ket{0}$$\gamma$$\delta$$\pi$$\pi$$\pi$$\pi$$\gamma$$\delta$$\pi$$\pi$$\pi$$\pi$
$\gamma^{\prime}$ $\pi$ $\delta^{\prime}$ $\pi$
in1in2out1out2$\gamma\\!+\\!\pi$$\delta\\!+\\!\pi$in1in2$\pi$$\pi$out1out2(2,3)(4.a)(4.b)(5)(1)“Box
Cluster”abdd$\frac{\pi}{4}$$\frac{\pi}{4}$$\frac{7\pi}{4}$$\frac{7\pi}{4}$$\frac{\pi}{4}$$\frac{\pi}{4}$$\frac{7\pi}{4}$$\frac{\pi}{4}$890125674325790695789$\frac{\pi}{4}$$\frac{7\pi}{4}$0143
Figure 6: Decomposition of an arbitrarily connected ZX-graph to a set of graph
states, the respective measurement angles, and fusion operations (red
connections). This case shows two linear (nodes 0-1-3-4 and 8-9) and two GHZ
graph states (nodes 2-0-5-7-9 and 6-5-7-9). To generate the actual graph
state, the nodes that occur multiple times in different graphs (nodes 0, 5, 7,
9) are fused.

Intersecting nodes between two graph states are connected using fusion gates
[41, 42]. Fig. 6 shows that the photons labeled with “0”, “5”, “7” and “9”
occur in multiple graph states. These labels identify the fusion gates that
must be performed on hardware after the GHZ and linear graph states are
generated. To perform fusion, one (in case of Type-1) or two (in case of
Type-2) photons are measured, and we are left with one photon that connects
two clusters. That way, we can construct arbitrary input states with any
hardware setup that is able to produce GHZ and linear graph states.

###  V-C Measurements basis

The measurement basis of each photon (1-4) on the right of Fig. 3 is defined
by the angle of the corresponding vertex in the m-graph. As an example, node
“a” in the “Box Cluster” in Fig. 5 configures the angles of the QWP/HWP “a” in
Fig. 3.

TABLE II: Results of compiled measurement-patterns for several circuits of the OpenQASM benchmark. The columns are structured as follows: QASM-circuit: name of the circuit in the OpenQASM benchmark, GHZ: Number of GHZ graphs, Linear: Number of linear graphs, Photons: Number of total photons, Comp.: Number of optical components. We compare with the circuital-model translation as built-in function of Perceval | Ours | Perceval
---|---|---
QASM-circuit | GHZ | Linear | Photons | Comp. | Photons | Comp.
adder-n4 | 6 | 4 | 37 | 167 | 46 | 182
bell-n4 | 2 | 2 | 18 | 76 | 34 | 135
cat-state-n4 | 0 | 1 | 6 | 17 | 18 | 42
deutsch-n2 | 0 | 1 | 3 | 8 | 6 | 11
fredkin-n3 | 4 | 3 | 29 | 126 | 36 | 144
grover-n2 | 0 | 1 | 4 | 11 | 10 | 35
hs4-n4 | 1 | 2 | 9 | 31 | 22 | 74
iswap-n2 | 0 | 1 | 3 | 8 | 10 | 32
linearsolver-n3 | 2 | 1 | 11 | 44 | 20 | 72
qft-n4 | 3 | 3 | 34 | 147 | 54 | 236
teleportation-n3 | 0 | 1 | 4 | 11 | 12 | 29
toffoli-n3 | 2 | 2 | 23 | 91 | 28 | 112
wstate-n3 | 3 | 3 | 29 | 122 | 40 | 176
adder-n10 | 25 | 10 | 218 | 1210 | – | –
bv-n14 | 1 | 0 | 15 | 43 | 54 | 119
multiply-n13 | 17 | 9 | 157 | 754 | 106 | 380
multiplier-n15 | 51 | 19 | 767 | 4706 | 474 | 2096
qf21-n15 | 18 | 14 | 299 | 1467 | 260 | 1148
qft-n15 | 14 | 14 | 462 | 2234 | 450 | 2097
qpe-n9 | 11 | 7 | 121 | 568 | 104 | 432
sat-n11 | 68 | 34 | 834 | 4836 | – | –
simon-n6 | 2 | 2 | 15 | 65 | 40 | 140

##  VI Implementation and Evaluation

We implement the presented pipeline with the following libraries:

  * •

Qiskit [37] to transform an arbitrary circuit to the desired gate set (Step
1),

  * •

PyZX [43] to translate the circuit to a graph-like diagram and optimize (Step
2-4), and

  * •

Perceval [44] to create a photonic circuit as in Fig. 3, that simulates the
graph states and fusion operations.

Our software is accessible on GitHub222https://github.com/CDL-Uni-
Vienna/photonq-compiler and includes a simulation of the execution of the
hardware instructions with Perceval. We also include a parser from QASM files
into the basic gate set $\\{HR_{z}(\alpha),CZ\\}$.

We show the differences between our resulting optical circuits and those
provided by the converter package from Perceval. The latter translates Qiskit
quantum circuits into standard optical circuits with probabilistic photonic
gates. However, it should be noted that this evaluation has only limited
expressiveness, as the one-way model and circuital model are conceptually very
different. The strength of the one-way model is not necessarily the reduction
of the number of photons, but the fact that the overall computation can be
performed deterministically.

###  VI-A Simulation

We simulate the photonic architecture depicted in Fig. 3 with Perceval using
standard optical components and extend the setup for $>4$ photons. To connect
two graph states as in Fig. 6, we implement fusion gates using single
polarizing beam splitters and half-wave plates. We choose to work with Type-1
fusion gates, for which one of the fused photons is measured; the fusion is
successful if the detector registers a single photon.

###  VI-B Evaluation

We apply our compiler to extract m-graphs from circuits given by the QASMBench
[40] project to demonstrate the validity of our pipeline and implementation.
We execute these m-graphs on a simulation of our photonic setups, such as that
shown in Fig. 3 in the case of four photons. Table II shows the number of
required GHZ and linear graph states, together with the number of photons and
optical elements – the latter are counted with Perceval.

First and foremost, it shows that we were able to decompose all circuits from
this project and translate them to a photonic setup – which is not true for
the converter provided by Perceval [45].

Second, we compare the number of required photons and optical elements against
the quantum circuit conversion provided by Perceval. For some cases (e.g.
grover-n2, hs4-n4 or bv-n14), Table II shows the full strength of the one-way
model, where a single input graph state can perform rather complex
calculations. However, especially larger circuits with complex calculation
show the excessive use of photons in the one-way model.

##  VII Conclusion

Photons are well-known candidates for quantum computing, but they are
currently underrepresented in publicly available environments, such as HPC
centers. The well-established quantum circuit model, however, is impracticable
for photonic hardware. Hence, measurement-based quantum computing (MBQC) is
the only feasible alternative for large-scale photonic quantum computing. The
quantum circuit model and the measurement-based one-way model of quantum
computation are known to be computationally equivalent. Still, compilers that
translate circuits into the one-way model are not established yet [21, 22].

In this paper, we describe a pipeline for a compiler that converts an
arbitrary quantum circuit to an optimized instruction set for a one-way QPU.
We demonstrate the translation to a discrete variable photonic platform, but
the concept should be applicable to other quantum computing technologies that
implement the one-way model, e.g., superconducting qubits or trapped ion
qubits [46, 47].

Our implementation constructs a measurement graph from the QASM input by using
simple transformation rules and optimizes it with the built-in methods of ZX-
Calculus. We find that ZX-Calculus is ideally suited to extract specific
hardware instructions from graph-like diagrams.

This work is only a first demonstration of the power of a ZX-Calculus-based
compiler for photonic QPUs. We plan to further investigate the optimization
for specific hardware architectures and other platforms, such as the recent
proposal where 14-photon GHZ and 12-photon linear states were experimentally
realized [1].

## Acknowledgment

The authors would like to thank Francesco Giorgino for the fruitful
discussions and the patient help with some of the theory.

This work is partially funded from the Austrian Federal Ministry for Digital
and Economic Affairs, the National Foundation for Research, Technology and
Development and the Christian Doppler Research Association. This work is
additionally partially supported by the German Federal Ministry of Education
and Research (BMBF) under the funding program Quantum Technologies - From
Basic Research to Market under contract number 13N16077.

## References

  * [1] P. Thomas, L. Ruscio, O. Morin, and G. Rempe, “Efficient generation of entangled multiphoton graph states from a single atom,” _Nature_ , vol. 608, no. 7924, pp. 677–681, 2022.
  * [2] J. Shalf, “Hpc interconnects at the end of moore’s law,” in _Optical Fiber Communication Conference_. Optical Society of America, 2019, pp. Th3A–1.
  * [3] M. Cerezo, A. Arrasmith _et al._ , “Variational quantum algorithms,” _Nature Reviews Physics_ , vol. 3, no. 9, pp. 625–644, 2021.
  * [4] M. A. Nielsen and I. L. Chuang, _Quantum Computation and Quantum Information: 10th Anniversary Edition_ , 10th ed. USA: Cambridge University Press, 2011.
  * [5] K. Bharti, A. Cervera-Lierta _et al._ , “Noisy intermediate-scale quantum algorithms,” _Rev. Mod. Phys._ , vol. 94, p. 015004, Feb 2022. [Online]. Available: https://link.aps.org/doi/10.1103/RevModPhys.94.015004
  * [6] A. D. Córcoles, A. Kandala _et al._ , “Challenges and opportunities of near-term quantum computing systems,” _Proceedings of the IEEE_ , vol. 108, no. 8, pp. 1338–1352, 2020.
  * [7] A. J. McCaskey, D. I. Lyakh, E. F. Dumitrescu, S. S. Powers, and T. S. Humble, “Xacc: a system-level software infrastructure for heterogeneous quantum–classical computing,” _Quantum Science and Technology_ , vol. 5, no. 2, p. 024002, 2020.
  * [8] S. Sivarajah, S. Dilkes, A. Cowtan, W. Simmons, A. Edgington, and R. Duncan, “t$\ket{\text{ket}}$: a retargetable compiler for NISQ devices,” _Quantum Science and Technology_ , vol. 6, no. 1, p. 014003, 2020.
  * [9] A. W. Cross, L. S. Bishop, J. A. Smolin, and J. M. Gambetta, “Open quantum assembly language,” 2017. [Online]. Available: https://arxiv.org/abs/1707.03429
  * [10] F. Leymann, J. Barzen, M. Falkenthal, D. Vietz, B. Weder, and K. Wild, “Quantum in the cloud: Application potentials and research opportunities,” 2020\.
  * [11] P. J. Karalekas, N. A. Tezak, E. C. Peterson, C. A. Ryan, M. P. da Silva, and R. S. Smith, “A quantum-classical cloud platform optimized for variational hybrid algorithms,” _Quantum Science and Technology_ , vol. 5, p. 024003, 2020.
  * [12] R. LaRose, “Overview and Comparison of Gate Level Quantum Software Platforms,” _Quantum_ , vol. 3, p. 130, Mar. 2019. [Online]. Available: https://doi.org/10.22331/q-2019-03-25-130
  * [13] W.-B. Gao, X.-C. Yao _et al._ , “Experimental measurement-based quantum computing beyond the cluster-state model,” _Nature Photonics_ , vol. 5, no. 2, pp. 117–123, Jan. 2011. [Online]. Available: https://doi.org/10.1038/nphoton.2010.283
  * [14] H. J. Briegel, D. E. Browne, W. Dür, R. Raussendorf, and M. V. den Nest, “Measurement-based quantum computation,” _Nature Physics_ , vol. 5, no. 1, pp. 19–26, Jan. 2009. [Online]. Available: https://doi.org/10.1038/nphys1157
  * [15] S. Barz, “Quantum computing with photons: introduction to the circuit model, the one-way quantum computer, and the fundamental principles of photonic experiments,” _Journal of Physics B: Atomic, Molecular and Optical Physics_ , vol. 48, no. 8, p. 083001, mar 2015. [Online]. Available: https://doi.org/10.1088/0953-4075/48/8/083001
  * [16] S. Slussarenko and G. J. Pryde, “Photonic quantum information processing: A concise review,” _Applied Physics Reviews_ , vol. 6, no. 4, p. 041303, 2019\. [Online]. Available: https://doi.org/10.1063/1.5115814
  * [17] P. Walther, K. Resch _et al._ , “Experimental one-way quantum computing,” _Nature_ , vol. 434, pp. 169–76, 04 2005.
  * [18] R. Prevedel, P. Walther _et al._ , “High-speed linear optics quantum computing using active feed-forward,” _Nature_ , vol. 445, pp. 65–9, 02 2007\.
  * [19] R. Raussendorf and H. J. Briegel, “A one-way quantum computer,” _Physical Review Letters_ , vol. 86, no. 22, p. 5188, 2001.
  * [20] ——, “Computational model for the one-way quantum computer: Concepts and summary,” 2002. [Online]. Available: https://arxiv.org/abs/quant-ph/0207183
  * [21] H. Zhang, A. Wu _et al._ , “A compilation framework for photonic one-way quantum computation,” 2022. [Online]. Available: https://arxiv.org/abs/2209.01545
  * [22] M. K. Vijayan, A. Paler, J. Gavriel, C. R. Myers, P. P. Rohde, and S. J. Devitt, “Compilation of algorithm-specific graph states for quantum circuits,” 2022. [Online]. Available: https://arxiv.org/abs/2209.07345
  * [23] B. Coecke and A. Kissinger, “Picturing quantum processes,” in _International Conference on Theory and Application of Diagrams_. Springer, 2018, pp. 28–31.
  * [24] P. Hauke, H. G. Katzgraber, W. Lechner, H. Nishimori, and W. D. Oliver, “Perspectives of quantum annealing: methods and implementations,” _Reports on Progress in Physics_ , vol. 83, no. 5, p. 054401, may 2020. [Online]. Available: https://doi.org/10.1088/1361-6633/ab85b8
  * [25] T.-C. Wei, “Measurement-based quantum computation,” _Oxford Research Encyclopedia of Physics_ , 2021.
  * [26] A. Russo, E. Barnes, and S. E. Economou, “Generation of arbitrary all-photonic graph states from quantum emitters,” _New Journal of Physics_ , vol. 21, no. 5, p. 055002, may 2019. [Online]. Available: https://doi.org/10.1088/1367-2630/ab193d
  * [27] D. Istrati, Y. Pilnyak _et al._ , “Sequential generation of linear cluster states from a single photon emitter,” vol. 11, no. 1, 2020. [Online]. Available: https://doi.org/10.1038/s41467-020-19341-4
  * [28] J.-P. Li, J. Qin _et al._ , “Multiphoton graph states from a solid-state single-photon source,” _ACS Photonics_ , vol. 7, no. 7, pp. 1603–1610, 2020\. [Online]. Available: https://doi.org/10.1021/acsphotonics.0c00192
  * [29] S. Bartolucci, P. M. Birchall _et al._ , “Creation of entangled photonic states using linear optics,” 2021. [Online]. Available: https://arxiv.org/abs/2106.13825
  * [30] R. Duncan, A. Kissinger, S. Perdrix, and J. Van De Wetering, “Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus,” _Quantum_ , vol. 4, p. 279, 2020.
  * [31] M. Backens, H. Miller-Bakewell, G. de Felice, L. Lobski, and J. van de Wetering, “There and back again: A circuit extraction tale,” _Quantum_ , vol. 5, p. 421, 2021.
  * [32] K. Staudacher, T. Guggemos, S. Grundner-Culemann, and W. Gehrke, “Reducing 2-qubit gate count for zx-calculus based quantum circuit optimization,” in _Proceedings 19th International Conference on Quantum Physics and Logic, Oxford, 27 June – 1 July 2022_ , ser. Electronic Proceedings in Theoretical Computer Science, S. Gogioso and M. Hoban, Eds., 2022.
  * [33] M. Fingerhuth, T. Babej, and P. Wittek, “Open source software in quantum computing,” _PLOS ONE_ , vol. 13, pp. 1–28, 2018.
  * [34] Microsoft, “qsharp-language,” https://github.com/microsoft/qsharp-language.
  * [35] F. Chong, D. Franklin, and M. Martonosi, “Programming languages and compiler design for realistic quantum hardware,” _Nature_ , vol. 549, pp. 180–187, 09 2017.
  * [36] A. S. Green, P. L. Lumsdaine, N. J. Ross, P. Selinger, and B. Valiron, “Quipper: a scalable quantum programming language,” in _Proceedings of the 34th ACM SIGPLAN conference on Programming language design and implementation_ , 2013, pp. 333–342.
  * [37] M. S. ANIS, Abby-Mitchell _et al._ , “Qiskit: An open-source framework for quantum computing,” 2021.
  * [38] C. Greganti, T. Demarie _et al._ , “Cross-verification of independent quantum devices,” _Physical Review X_ , vol. 11, no. 3, Sep. 2021. [Online]. Available: https://doi.org/10.1103/physrevx.11.031049
  * [39] A. Kissinger and J. van de Wetering, “Reducing the number of non-clifford gates in quantum circuits,” _Physical Review A_ , vol. 102, no. 2, p. 022406, 2020.
  * [40] A. Li, S. Stein, S. Krishnamoorthy, and J. Ang, “QASMBench: A Low-level QASM Benchmark Suite for NISQ Evaluation and Simulation,” _arXiv preprint arXiv:2005.13018_ , 2021.
  * [41] D. E. Browne and T. Rudolph, “Resource-efficient linear optical quantum computation,” _Phys. Rev. Lett._ , vol. 95, p. 010501, Jun 2005. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.95.010501
  * [42] S. Bartolucci, P. Birchall _et al._ , “Fusion-based quantum computation,” 2021\. [Online]. Available: https://arxiv.org/abs/2101.09310
  * [43] A. Kissinger and J. van de Wetering, “PyZX: Large Scale Automated Diagrammatic Reasoning,” in _Proceedings 16th International Conference on Quantum Physics and Logic, Chapman University, Orange, CA, USA., 10-14 June 2019_, ser. Electronic Proceedings in Theoretical Computer Science, B. Coecke and M. Leifer, Eds., vol. 318. Open Publishing Association, 2020, pp. 229–241.
  * [44] N. Heurtel, A. Fyrillas _et al._ , “Perceval: A Software Platform for Discrete Variable Photonic Quantum Computing,” 2022. [Online]. Available: https://arxiv.org/abs/2204.00602
  * [45] “Convertors.” [Online]. Available: https://perceval.quandela.net/docs/convertors.html
  * [46] S. N. Shah, “Realizations of measurement based quantum computing,” 2021. [Online]. Available: https://arxiv.org/abs/2112.11601
  * [47] B. P. Lanyon, P. Jurcevic _et al._ , “Measurement-based quantum computation with trapped ions,” _Phys. Rev. Lett._ , vol. 111, p. 210501, Nov 2013. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.111.210501


# A Conceptual Model for End-to-End Causal Discovery in Knowledge Tracing

Nischal Ashok Kumar, Wanyong Feng, Jaewook Lee, Hunter McNichols,
Aritra Ghosh, Andrew Lan

University of Massachusetts Amherst
<EMAIL_ADDRESS>
###### Abstract

In this paper, we take a preliminary step towards solving the problem of
causal discovery in knowledge tracing, i.e., finding the underlying causal
relationship among different skills from real-world student response data.
This problem is important since it can potentially help us understand the
causal relationship between different skills without extensive A/B testing,
which can potentially help educators to design better curricula according to
skill prerequisite information. Specifically, we propose a conceptual
solution, a novel causal gated recurrent unit (GRU) module in a modified deep
knowledge tracing model, which uses i) a learnable permutation matrix for
causal ordering among skills and ii) an optionally learnable lower-triangular
matrix for causal structure among skills. We also detail how to learn the
model parameters in an end-to-end, differentiable way. Our solution placed
among the top entries in Task 3 of the NeurIPS 2022 Challenge on Causal
Insights for Learning Paths in Education. We detail preliminary experiments as
evaluated on the challenge’s public leaderboard since the ground truth causal
structure has not been publicly released, making detailed local evaluation
impossible.

###### keywords:

Causal Discovery, Knowledge Tracing, Response Data

##  1 Introduction

Knowledge Tracing (KT) [1] refers to the problem of estimating a student’s
understanding or mastery of certain skills, concepts, or knowledge components
through their responses to questions and using these estimates to predict
future performance. KT methods are frequently utilized in modern online
education platforms to determine the knowledge levels of many students to
enable the platform to provide personalized feedback and recommendations,
ultimately leading to better learning results [19]. KT methods are limited in
how they represent the relationship between skills; One key limitation is that
most do not model the causal relationships between skills. Most KT methods
simply treat human expert-provided skill tags as a flat structure (with a few
exceptions, such as [27], that organize skills hierarchically as trees). As a
result, these models are not capable of providing meaningful pedagogical
insights, i.e., predicting future student performance if a particular
instructional plan is applied instead of the actual plan applied.

Causal analysis tools are a perfect fit to address these limitations in KT.
The task of _causal discovery_ , i.e., learning causal relationships among
different skills from observational data, is especially important. First, it
helps educators learn prerequisite relationships among skills. This can guide
educators in ordering topics within their curriculum and can guide students to
review prerequisite information when they are stuck on a question [2]. Second,
causal relationships among skills helps us with the task of _causal inference_
, i.e., estimating the effect of a particular pedagogical treatment or
intervention. Traditionally, these tasks are addressed through randomized
controlled trials which are difficult to scale. Therefore, incorporating
causal discovery into KT methods has the potential to become a scalable
alternative since it can be done solely from observational student response
data. Performing causal discovery directly from observational student response
data is challenging since it is not straightforward to estimate treatment
effects from observational data with incomplete or no knowledge of the causal
relationship between skills. This problem is referred to as the _end-to-end
causal inference_ problem, where we discover the causal graph and estimate
treatment effects together.

###  1.1 Contributions

In this paper, we take a preliminary step towards learning causal ordering
among skills from student response data. This task is proposed in the NeurIPS
2022 Challenge on Causal Insights for Learning Paths in
Education111https://eedi.com/projects/neurips-2022. Our proposed conceptual
solution is, to the best of our knowledge, the first KT method to learn the
causal structure among human expert-provided skill tags directly from
observational data in an _end-to-end_ manner. Specifically, our contributions
in this paper are as follows:

  * •

First, we propose an interpretable _causal structure_ model that characterizes
both i) the dependency among skills using a lower-triangular matrix and ii)
their prerequisite ordering using a permutation matrix. We hypothesize that
this module can be combined with any existing KT method that rely on human
expert-provided skill tags.

  * •

Second, as a (among the top) solution222The code for our solution can be found
at: https://github.com/umass-ml4ed/Neurips-Challenge-22 to Task 3 in the
NeurIPS 2022 Challenge, we apply our causal structure module to a variant of
deep knowledge tracing (DKT) [17], with a _causal_ gated recurrent unit (GRU)
module at its core, due to i) the simple nature of DKT and ii) its good
empirical performance in our experiments.

  * •

Third, we detail our experimental results based on the public leaderboard of
the NeurIPS 2022 Challenge. We are honest up front that our evaluation is
limited since i) the ground-truth causal structure data is not publicly
released and ii) the nature of this brand new task means that there are no
baselines to compare against.

##  2 Related Work

###  2.1 KT methods

Existing KT methods can be classified along several different axes, the first
of which is how they represent the student knowledge representation variable
$h$. Classic Bayesian KT methods, such as those in [9, 15, 28], treat student
knowledge as a latent binary variable. Recent methods like deep learning-based
KT methods, such as [4, 14, 17, 22, 29], treat student knowledge as hidden
states in neural networks. This setup results in models that excel at
predicting future performance but have limited interpretability [3]. Another
major axis is how KT methods represent responses, questions, skills, and time
steps. To represent student responses, most existing KT methods treat them as
binary-valued indicating response correctness. However, a few methods, such as
option tracing [5] and predict partial analysis [26], have characterized
student responses as non-binary-valued by analyzing the specific options
selected on multiple-choice questions. Another exception is [11], which uses
large language models to predict open-ended student responses in a generative
way. To represent questions and skills, most existing KT methods one-hot
encode them based on question IDs or skill tags [24], except [11, 12]. To
represent time steps, most existing KT methods treat each question as a
discrete time step, with a few exceptions such as [25], which considers the
exact, continuous time elapsed between responses.

###  2.2 Causal Analysis Methods

In the field of education, there exist very few works on causality and
especially few in the context of KT. [8] is closely related to our work, where
the authors study the relationship between courses in higher educational
institutions using historical student performance data. They use matching
methods and regression to determine the average treatment effect (ATE). Along
similar lines, [20] and [21] developed theory and methods for analyzing A/B
testing data and presented studied data collected from real-world randomized
controlled trials. These works focus on causal inference, i.e., assuming that
the structure is given and the focus is on estimating the treatment effect.
However, the data we use from Eedi contains fine-grained skills, defined as
the smallest elements of learning among primary/middle school students.
Therefore, our work is different from these works in terms of both the goal
and the educational context. The only existing works that study causal
discovery in the context of KT are [10] and [13]. The former uses a special
model structure that has some similarity to ours to model knowledge state
transitions among uninterpretable latent skills. The authors showed that their
method, while simple, is highly accurate in predicting unobserved student
responses, but do not evaluate on whether the identified causal structure is
valid. Our proposed method to learn latent causal structure is closely based
on the structural equation model (SEM) [16]. SEM enables us to estimate the
relationships between observed and latent variables, offering valuable
insights into their underlying relationships. The hypothesized causal
relationship among variables is represented as a directed acylic graph (DAG).
In this work, our goal is to learn the causal structure graph $\mathcal{G}$.

##  3 Methodology

We now detail our conceptual causal KT method.

###  3.1 Basic Setup

The basic KT model contains two components:

$\displaystyle\mathbf{h}_{j,t}\sim f(\mathbf{h}_{j,t-1},\mathbf{x}_{j,t}).$
(1) $\displaystyle p(Y_{j,t}\>|\>\mathbf{h}_{j,t},{i}_{j,t}).$ (2)

For a student $j$ at time step $t$, The knowledge estimation component in Eq.
(1) estimates the current knowledge state $\mathbf{h}_{j,t}$ given the
previous knowledge state $\mathbf{h}_{j,t-1}$ and the student’s performance on
the problem $\mathbf{x}_{j,t}$ as inputs. The response prediction component in
Eq. (2) outputs the prediction of the student’s likelihood of answering the
next question ${Y}_{j,t}$ correctly given the current knowledge state
$\mathbf{h}_{j,t}$ and the next question index ${i}_{j,t}$ as input. During
the learning process, the KT model needs to maximize the predicted likelihood
across responses of all students, i.e., $\sum_{j}\sum_{t}\log
p(Y_{j,t}\>|\>Y_{j,1},\ldots,Y_{j,t-1}).$

We adopt the DKT setup detailed in [18] for consistency. Since incorporating
causal learning into the base KT model introduces additional parameters, we
use the gated recurrent unit (GRU) as the transition model instead of long
short-term memory (LSTM) for computational efficiency. For response
prediction, we simply use a single linear layer over the hidden states of the
GRU. For causal discovery, i.e., learning the causal structure among skills,
we use the causal GRU module detailed below.

Figure 1: The implementation of a causal GRU cell. All the GRU weight
matrices, $\mathbf{W}_{z}$, $\mathbf{W}_{r}$, and $\mathbf{W}$ are multiplied
by the causal mask $\mathbf{M}=\mathbf{P}\mathbf{L}\mathbf{P}^{T}$, resulting
in $\mathbf{W}_{z}^{\prime}$, $\mathbf{W}_{r}^{\prime}$, and
$\mathbf{W}^{\prime}$.

###  3.2 Causal GRU

We now detail the structure of the Causal GRU. From now on, we drop the
student index $j$ for notation simplicity. We define a permuted causal mask
$\mathbf{M}$ that represents the causal ordering and structure between skills.
The $\mathbf{L}$ matrix represents the _causal structure/skill dependency_ ,
and the $\mathbf{P}$ matrix represents the _causal ordering_. The permuted
causal mask $\mathbf{M}$ is calculated in Eq. (3) as first multiplying
$\mathbf{P}$ by $\mathbf{L}$ to obtain the updated causal structure and
multiplying by $\mathbf{P}^{T}$ to transform the causal structure into the
original space.

The parameters in the Causal GRU are masked, i.e., element-wise multiplied by
the permuted causal mask $\mathbf{M}$ in Eq. (4). By masking out some
parameters, we zero out parameters that do not satisfy the causal graph. This
step ensures that there is no relationship between the hidden states of the
non-causally dependent skills in latent student knowledge states. The latest
student knowledge state estimation $\mathbf{h}_{t}$ is calculated in Eq. (5).
The input $\mathbf{x}_{t}$ is represented as a one-hot vector with the
dimension size equals to the number of skills $C$. The entry of value $\pm 1$
represents whether the student can correctly answer the question corresponding
to the skill. The input $\mathbf{h}_{t-1}$ is the previous student knowledge
state estimation. The implementation detail of a Causal GRU cell can be found
in Fig. 1.

$\displaystyle\mathbf{M}=\mathbf{P}\mathbf{L}\mathbf{P}^{T},$ (3)
$\displaystyle\mathbf{W}^{{}^{\prime}}=\mathbf{M}\odot\mathbf{W},$ (4)
$\displaystyle\mathbf{h}_{t}=GRU_{c}(\mathbf{h}_{t-1},\mathbf{x}_{t}).$ (5)

Figure 2: The intuition behind causal GRU. Here,
$\mathbf{M}=\mathbf{P}\mathbf{L}\mathbf{P}^{T}$. $M_{i,j}=1$ if and only if
$[\mathbf{h}_{t-1}]_{j}$ influences $[\mathbf{h}_{t}]_{i}$ where
$\mathbf{h}_{t}$ is the student’s knowledge state at time-step $t$.

####  3.2.1 Causal Ordering

One important element of the causal GRU is the _causal ordering_ matrix
$\mathbf{P}$, which we set to be a permutation matrix. By definition, a
permutation matrix has exactly one entry of 1 in each row and each column and
0s elsewhere. Since multiplying a matrix by a permutation matrix permutes the
order of the columns/rows of that matrix, the permutation matrix is naturally
capable of sorting skills into order based on prerequisite relationships.
However, the binary and discrete nature of the permutation matrix makes the
learning process non-differentiable. To solve this problem, we introduce a
relaxed version of the problem by approximating a permutation matrix with a
doubly stochastic matrix, i.e., one where all entries are non-negative and the
summation of each column/row is equal to 1, i.e.,
$P_{i,k}\in[0,1],\>\sum_{k}P_{i,k}=1\>\forall i\>,\>\sum_{i}P_{i,k}=1\>\forall
k\>$. Instead of learning a doubly stochastic matrix directly, which is very
difficult, we learn a matrix of free parameters $\bar{\mathbf{P}}$, from which
we can obtain $\mathbf{P}$ after applying the _Sinkhorn_ operator [23]
$\mathbf{P}=\text{Sinkhorn}(\bar{\mathbf{P}})$.

The _Sinkhorn_ operator works as follows: First, starting with the base matrix
$\bar{\mathbf{P}}$, we subtract the largest entry of the matrix from each
entry, multiply each entry with the temperature hyper-parameter, and pass it
through an exponential function. Second, we apply a series of row and column
normalizations by dividing each entry of the column/row by the summation of
all the entries in the column/row. In our implementation of the _Sinkhorn_
operator, there are two hyper-parameters: _temperature_ and _unroll_. The
temperature hyper-parameter specifies the extent of the continuous relaxation:
the larger the temperature hyper-parameter, the closer $\mathbf{P}$’s entries
are to either $0$ or $1$. The unroll hyper-parameter specifies the number of
times row/column normalization is carried out: the more times the
normalization is applied, the closer $\mathbf{P}$ is to satisfying the
row/column normalization constraints.

####  3.2.2 Causal Structure

The other important element of the causal GRU is the _causal structure/ skill
dependency_ matrix $\mathbf{L}$, which we set to be lower triangular. By
definition, a lower triangular matrix is one in which all the elements above
the principal diagonal of the matrix are 0. This matrix is important since it
specifies the causal structure among the skills. Once the skills are ordered
using the _causal ordering_ matrix $\mathbf{P}$, we apply the _causal
structure_ matrix $\mathbf{L}$ to regularize student knowledge state
transitions across time steps. Due to its lower-diagonal structure, an entry
$L_{i,k}>0$ with $i>k$ implies that skill $k$ is a prerequisite of skill $i$.
Therefore, since the causal GRU weight matrices are masked by the
$\mathbf{PLP^{T}}$ matrix, at the next time step $t$, the entry in the latent
student knowledge vector that corresponds to skill $i$,
$[\mathbf{h}_{t}]_{i}$, depends only on the entries in the previous knowledge
state that correspond to prerequisites of skill $i$, i.e.,
$[\mathbf{h}_{t-1}]_{k}\,\forall k$ s.t. $L_{i,k}>0$.

The L matrix being lower diagonal ensures that the resulting causal structure
is a DAG. This means that if skill $C_{1}$ depends on $C_{2}$ then $C_{2}$
cannot depend on $C_{1}$. As a concrete example, Fig. 2 visualizes the effect
of applying a mask $\mathbf{M}=\mathbf{P}\mathbf{L}\mathbf{P}^{T}$ on the
skill matrix $C$. The skill matrix $C$ represents 5 skills where each skill is
represented as a one-hot vector. The causal ordering matrix $\mathbf{P}$ is
applied to the skill matrix to give a skill ordering of $C_{3}$, $C_{2}$,
$C_{1}$, $C_{5}$, $C_{4}$ which is in the order of decreasing pre-requisites
($C_{3}$ being the most pre-requisite of all skills). We further apply the
$\mathbf{L}$ matrix (in this case a lower diagonal matrix with all ones) that
specifies that every subsequent skill depends on the preceding one. For
example, it specifies that $C_{4}$ depends on all of $C_{1}$, $C_{2}$,
$C_{3}$, and $C_{5}$; $C_{5}$ depends on $C_{1}$, $C_{2}$, and $C_{3}$ and so
on.

One easy choice for $\mathbf{L}$ is to set its lower-diagonal part to be all
ones; this setting means that every subsequent skill causally depends on all
the previous skills. However, in practice, causal dependencies among skills
nay not be this dense; most skills will only be causally related to a few
other skills. To resolve this problem, we can make the $\mathbf{L}$ matrix
learnable by restricting the lower diagonal elements to be either 0 or 1. We
do this by learning a matrix of free parameters $\bar{\mathbf{L}}$, from which
we can obtain $\mathbf{L}$ after applying the element-wise sigmoid operator
$\mathbf{L}=\text{sigmoid}(\alpha\bar{\mathbf{L}})$. A large value of the
temperature parameter $\alpha>0$ will push entries to be close to either 0 or
1 but not in between.

####  3.2.3 Skill Embeddings

We use a learnable dense embedding to represent each skill and alter both the
input and the output layers of the causal GRU. We learn an embedding matrix
$\mathbf{E}$ where each column $\mathbf{e}_{c}$ represents the embedding of
skill $c$. We treat the dimension of $\mathbf{e}_{c}$ as a hyperparameter. For
the input layer, we use another learnable embedding $\mathbf{d}$, which is
either added or subtracted from the skill embedding depending on the
correctness of the previous answer. We then learn the input to the causal GRU
using $NN(\mathbf{e}_{c}\pm\mathbf{d})$ where $NN$ is a single-layer neural
network. For the output, we use $p(Y_{t})\sim
NN_{o}([\mathbf{e}_{c}^{T},\tilde{\mathbf{h}}_{t}^{T}]^{T})$, where
$\tilde{\mathbf{h}}_{t}$ is a masked version of $\mathbf{h}_{t}$ with the only
non-zero entry being the one that corresponds to the skill of the next
question that we are predicting. Here $NN_{o}$ is a single-layer neural
network that predicts the probability of the correct answer.

##  4 Experiments

###  4.1 Data and Challenge Description

We participated in Task 3 of the NeurIPS Challenge co-hosted by Eedi,
Microsoft Research, and Rice University [6]. The goal of this task is to
discover the causal relationships between different skills, or _constructs_
(as defined by Eedi, which means the smallest unit of learning; for example,
“mental addition and subtraction” is a construct within the main topic
“math”), and evaluate the effect of learning one _skill_ on another. Questions
in this dataset are multiple-choice, with a single correct option and three
distractors that are designed to assess a single skill. The challenge
hypothesis is that it is possible to discover the hidden relationship behind
different skills through analyzing the responses to a large number of
diagnostic questions. The challenge uses an $F_{1}$ score-based metric which
calculates the similarity between the predicted adjacency matrix $\hat{A}$ and
the true adjacency matrix $A$.

Table 1: Results on different model variants. | Model
---
Variant
| Leaderboard
---
$F_{1}$ Score
| No Embedding
---
No Adaptive
0.11
| No Embedding
---
Adapative
0.17
| Embedding (300D)
---
Adaptive
0.33
| Embedding (300D)
---
Adaptive
Learnable L
0.43

###  4.2 Model Learning and Hyperparameters

The dataset consists of 1855 skills and 6468 students. We set the default
skill embedding dimension to 300. We use an adaptive strategy and start with
small values of the temperature and unroll and linearly increase their values
over a set of epochs. We set the initial temperature and unroll to 2 and 5
respectively and linearly increase the values with a factor of 2 and 5
respectively for every 10 epochs. We train the model for 50 epochs with a
batch size of 64, and a learning rate of 5e-4 using four Nvidia Tesla 2080
GPUs with a GPU memory of 12GB each which takes about 6 hours. After training,
to obtain the final _causal structure_ matrix $\mathbf{L}$ we apply a post-
processing step. We define a hyperparameter _$\kappa$_ such that all values of
the $\mathbf{L}$ matrix less than _$\kappa$_ are set to 0 and all values
greater than or equal to _$\kappa$_ are set to 1.

###  4.3 Results and Discussion

In Table 1, we show the results of different model variants. We report the
leaderboard $F_{1}$ score obtained in our experiments. We see that the $F_{1}$
score is 0.11 for the case where we are not using the skill embeddings. Using
an adaptive strategy increases the $F_{1}$ score by 0.06, which suggests that
the adaptive strategy is helpful during model training. We also report the
results corresponding to the skill embeddings and the learnable $\mathbf{L}$.
We see that using an embedding dimension of 300 almost doubles the $F_{1}$
score. This observation confirms our hypothesis that using skill embeddings
increases the representational capacity of the neural network model and hence
performs better. When the causal structure matrix $\mathbf{L}$ is learnable,
we see that we get a further 0.1 increase in the $F_{1}$ score. The increase
in the $F_{1}$ score on using the learnable $\mathbf{L}$ configuration of the
model shows that it is better to learn the explicit causal dependence of
skills instead of assuming a dense representation where each skill depends on
all the skills preceding it.

##  5 Conclusions and Future Work

In this work, we proposed a conceptual method for learning causal structure
among skills from student response data, as a part of our solution to the
NeurIPS 2022 Challenge on Causal Insights for Learning Paths in Education. Our
method is a novel causal knowledge tracing method that enables us to learn the
causal structure in an end-to-end manner while performing knowledge tracing.
Unfortunately, due to space limitations, we cannot show a qualitative example
of the learned causal structure among skills. We believe that our work should
inspire future works in the direction of building causal knowledge tracing
methods on observational student response data. First, it is important to
evaluate the accuracy of the learned causal structure between skills, either
against human domain experts or via A/B testing. Second, it is important to
apply our causal module to more flexible knowledge tracing methods, such as
attention-based methods, to see whether it is applicable and effective. Third,
it is important to develop ways to leverage both the opinion of human experts
and our data-driven causal discovery model, in a human-in-the-loop manner. The
former may be less accurate but the latter requires extensive training data; a
hybrid human-AI collaboration may be able to take the best from both sides.

##  6 Acknowledgements

The authors thank the NSF (under grants 1917713, 2118706, 2202506, 2215193)
for partially supporting this work. We also thank the organizers of the 2022
NeurIPS Challenge on Causal Insights for Learning Paths in Education for
proposing a new and meaningful task.

## References

  * [1] A. Corbett and J. Anderson.  Knowledge tracing: Modeling the acquisition of procedural knowledge.  User Model. User-adapted Interact., 4(4):253–278, Dec. 1994.
  * [2] M. C. Desmarais.  Mapping question items to skills with non-negative matrix factorization.  ACM SIGKDD Explorations Newsletter, 13(2):30–36, 2012.
  * [3] T. Gervet, K. Koedinger, J. Schneider, T. Mitchell, et al.  When is deep learning the best approach to knowledge tracing?  Journal of Educational Data Mining, 12(3):31–54, 2020.
  * [4] A. Ghosh, N. Heffernan, and A. S. Lan.  Context-aware attentive knowledge tracing.  In Proc. ACM SIGKDD, pages 2330–2339, 2020.
  * [5] A. Ghosh, J. Raspat, and A. Lan.  Option tracing: Beyond correctness analysis in knowledge tracing.  In Int. Conf. Artif. Intell. Educ., pages 137–149. Springer, 2021\.
  * [6] W. Gong, D. Smith, Z. Wang, C. Barton, S. Woodhead, N. Pawlowski, J. Jennings, and C. Zhang.  Instructions and guide: Causal insights for learning paths in education.  arXiv preprint arXiv:2208.12610, 2022.
  * [7] A. Hyvärinen, K. Zhang, S. Shimizu, and P. O. Hoyer.  Estimation of a structural vector autoregression model using non-gaussianity.  Journal of Machine Learning Research, 11(5), 2010.
  * [8] P. Kaur, A. Polyzou, and G. Karypis.  Causal inference in higher education: Building better curriculums.  In Proceedings of the Sixth (2019) ACM Conference on Learning@ Scale, pages 1–4, 2019.
  * [9] M. Khajah, Y. Huang, J. González-Brenes, M. Mozer, and P. Brusilovsky.  Integrating knowledge tracing and item response theory: A tale of two frameworks.  In Proc. Int. Workshop Personalization Approaches Learn. Environ., volume 1181, pages 7–15, 2014.
  * [10] A. S. Lan, C. Studer, and R. G. Baraniuk.  Time-varying learning and content analytics via sparse factor analysis.  In Proc. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 452–461, Aug. 2014.
  * [11] N. Liu, Z. Wang, R. Baraniuk, and A. Lan.  Open-ended knowledge tracing for computer science education.  In Conference on Empirical Methods in Natural Language Processing, pages 3849–3862, 2022.
  * [12] Q. Liu, Z. Huang, Y. Yin, E. Chen, H. Xiong, Y. Su, and G. Hu.  Ekt: Exercise-aware knowledge tracing for student performance prediction.  IEEE Trans. Knowl. Data Eng., 33(1):100–115, 2019.
  * [13] S. Minn, J.-J. Vie, K. Takeuchi, H. Kashima, and F. Zhu.  Interpretable knowledge tracing: Simple and efficient student modeling with causal relations.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 12810–12818, 2022.
  * [14] S. Pandey and J. Srivastava.  Rkt: Relation-aware self-attention for knowledge tracing.  arXiv preprint arXiv:2008.12736, 2020.
  * [15] Z. A. Pardos and N. T. Heffernan.  Modeling individualization in a Bayesian networks implementation of knowledge tracing.  In Proc. Int. Conf. User Model. Adaptation Personalization, pages 255–266, 2010.
  * [16] J. Pearl.  Causal inference in statistics: An overview.  Statistics surveys, 3:96–146, 2009.
  * [17] C. Piech, J. Bassen, J. Huang, S. Ganguli, M. Sahami, L. J. Guibas, and J. Sohl-Dickstein.  Deep knowledge tracing.  In Proc. NeurIPS, pages 505–513, 2015.
  * [18] C. Piech, J. Bassen, J. Huang, S. Ganguli, M. Sahami, L. J. Guibas, and J. Sohl-Dickstein.  Deep knowledge tracing.  Advances in neural information processing systems, 28, 2015.
  * [19] S. Ritter, J. R. Anderson, K. R. Koedinger, and A. Corbett.  Cognitive tutor: Applied research in mathematics education.  Psychonomic Bulletin & Review, 14(2):249–255, 2007.
  * [20] A. Sales, A. Botelho, T. Patikorn, and N. T. Heffernan.  Using big data to sharpen design-based inference in a/b tests.  In Proceedings of the Eleventh International Conference on Educational Data Mining, 2018.
  * [21] A. C. Sales and J. F. Pane.  Student log-data from a randomized evaluation of educational technology: A causal case study.  Journal of Research on Educational Effectiveness, 14(1):241–269, 2021.
  * [22] D. Shin, Y. Shim, H. Yu, S. Lee, B. Kim, and Y. Choi.  Saint+: Integrating temporal features for ednet correctness prediction.  In 11th Int. Learn. Analytics Knowl. Conf., pages 490–496, 2021\.
  * [23] R. Sinkhorn.  A relationship between arbitrary positive matrices and doubly stochastic matrices.  The annals of mathematical statistics, 35(2):876–879, 1964.
  * [24] S. Sonkar, A. E. Waters, A. S. Lan, P. J. Grimaldi, and R. G. Baraniuk.  qdkt: Question-centric deep knowledge tracing.  In Proceedings of the International Conference on Educational Data Mining, 2020.
  * [25] C. Wang, W. Ma, M. Zhang, C. Lv, F. Wan, H. Lin, T. Tang, Y. Liu, and S. Ma.  Temporal cross-effects in knowledge tracing.  In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, pages 517–525, 2021.
  * [26] Y. Wang and N. Heffernan.  Extending knowledge tracing to allow partial credit: Using continuous versus binary nodes.  In Int. conf. artif. intell. educ., pages 181–188. Springer, 2013\.
  * [27] Y. Yang, J. Shen, Y. Qu, Y. Liu, K. Wang, Y. Zhu, W. Zhang, and Y. Yu.  Gikt: A graph-based interaction model for knowledge tracing.  In Proc. Joint Eur. Conf. Mach. Learn. Knowl. Discovery Databases, 2020.
  * [28] M. V. Yudelson, K. R. Koedinger, and G. J. Gordon.  Individualized bayesian knowledge tracing models.  In Int. Conf. artif. intell. educ., pages 171–180. Springer, 2013\.
  * [29] J. Zhang, X. Shi, I. King, and D.-Y. Yeung.  Dynamic key-value memory networks for knowledge tracing.  In Proc. Int. Conf. World Wide Web, pages 765–774, Apr. 2017.

##  Appendix A Structural Equation Modeling

In SEM, given a collection of random variables
$\mathbf{x}=(x_{1},\cdots,x_{D})$ and a causal directed acyclic graph (DAG)
$\mathcal{G}$, each variable $x_{i}$ is generated using its parents
$Pa(i;\mathcal{G})$ in the DAG and an exogenous noise variable $\epsilon_{i}$:
$x_{i}=f_{i}(\\{x_{j}\\}_{j\in Pa(i;\mathcal{G})})+\epsilon_{i}$. The
structural vector autoregression (SVAR) model extends SEM to random variables
that form a time series $\mathbf{x}_{t}=(x_{1,t},\cdots,x_{D,t})$ for time
steps $t\in\\{1,\cdots,T\\}$ [7]. The influence of one variable on others can
be instantaneous or lagged behind for a few time steps. The SEM model is given
by

$\displaystyle x_{i,t}=\sum_{\tau=0}^{k}f_{i,\tau}(\\{x_{j,t-\tau}\\}_{j\in
Pa(i,t,\tau;\mathcal{G})})+\epsilon_{i,t},$

where ${Pa(i,t,\tau;\mathcal{G})}$ are random variables from time step
$t-\tau$ that influence random variable $x_{i,t}$. One can also use a single
latent state $\mathbf{h}{\cdot,t}$ to model the influence of past random
variables. The SEM becomes

$\displaystyle\mathbf{h}_{i,t}=f_{i}(\\{h_{j,t-1}\\}_{j\in
Pa(i;\mathcal{G})})+\epsilon_{i}.$

##  Appendix B Sinkhorn Operation

Figure 3: The _Sinkhorn_ operator is a smooth operator that outputs an
approximate permutation matrix.

Fig. 3 shows the working of the Sinkhorn operator.

##  Appendix C Additional Results

Table 2: Results on varying the cutoff for the $\mathbf{L}$ matrix, $\kappa$. $\kappa$ |  $F_{1}$ Score
---|---
0.42 | 0.43
0.45 | 0.43
0.435 | 0.43
0.48 | 0.43
0.495 | 0.43
0.51 | 0.33
0.525 | 0.18

We report the results obtained using different hyperparameters of the
learnable $\mathbf{L}$ model configuration. In Table 2, we show the results
across different _$\kappa$_ values. We vary the values from 0.42 to 0.525 and
observe that using any values out of this range gives a leaderboard $F_{1}$
score of 0. Among the experimented values for _$\kappa$_ we see that we obtain
a maximum $F_{1}$ score of 0.43 for all values in the range of 0.42 to 0.495.
The maximum $F_{1}$ score for _$\kappa$_ values in the range of 0.42 to 0.495
means that using very large or very less values of _$\kappa$_ does not give
the optimal skill dependency.

Figure 4: An example of learned causal ordering among skills in actual student
response data.

We perform a qualitative analysis of our proposed method. Fig. 4 shows an
example from the DAG obtained from the learned adjacency matrix for causal
relations. Here, we represent the constructs based on their subject names, and
an arrow from subject $i$ to subject $j$ implies that subject $i$ is a pre-
requisite of subject $j$. Here, in the figure, we can see that “Counting” is
the most pre-requisite skill. The subsequent skills in fractions depend on
“Counting”. Calculating areas of simple figures depends on fraction
multiplication. In the same way, calculating the volume depends on calculating
the area. Hence, from this, we can see that we are able to learn a meaningful
DAG using our methodology.