#  Complex Dynamics of the Implicit Maps
Derived from Iteration of Newton and Euler Methods ††thanks: Supported by
Russian Science Foundation, Grant No. 21-12-00121.

Andrei A. Elistratov, Dmitry V. Savin1, Olga B. Isaeva1,2

###### Abstract

Special exotic class of dynamical systems — the implicit maps — is considered.
Such maps, particularly, can appear as a result of using of implicit and semi-
implicit iterative numerical methods. In the present work we propose the
generalization of the well-known Newton-Cayley problem. Newtonian Julia set is
a fractal boundary on the complex plane, which divides areas of convergence to
different roots of cubic nonlinear complex equation when it is solved with
explicit Newton method. We consider similar problem for the relaxed, or
damped, Newton method, and obtain the implicit map, which is non-invertible
both time-forward and time-backward. It is also possible to obtain the same
map in the process of solving of certain nonlinear differential equation via
semi-implicit Euler method. The nontrivial phenomena, appearing in such
implicit maps, can be considered, however, not only as numerical artifacts,
but also independently. From the point of view of theoretical nonlinear
dynamics they seem to be very interesting object for investigation. Earlier it
was shown that implicit maps can combine properties of dissipative non-
invertible and Hamiltonian systems. In the present paper strange invariant
sets and mixed dynamics of the obtained implicit map are analyzed.

keywords: Julia set, Hamiltonian system, implicit map

_Saratov State University
Astrahanskaya 83 Saratov, 410026, Russia_

_Kotel’nikov Institute of Radio-Engineering and Electronics of RAS, Saratov
Branch
Zelenaya 38, Saratov, 410019, Russia_

## Introduction

One of the wide-known examples of fractal sets — Newtonian Julia set (Fig. 1)
— arises as a boundary of areas of convergence to different roots of the cubic
polynomial equation on the complex plane

$\phi(z)=z^{3}+c=0,$ (1)

when it is solved with the Newton method [18]. This problem, first suggested
by Cayley [5], allows generalization, if relaxed, or damped Newton method

$z_{n+1}=z_{n}-h\frac{\phi(z_{n})}{\phi^{\prime}(z_{n})}=z_{n}-h\frac{z_{n}^{3}+c}{2z_{n}^{2}}$
(2)

is used [14, 13]. At the same time the iteration process (2) can be considered
as a trivial discretization of the ordinary differential equation

$\dot{z}=f(z)$ (3)

with the Euler method

$z_{n+1}=z_{n}+hf(z_{n}),$ (4)

where

$f(z)=-\frac{\phi(z)}{\phi^{\prime}(z)}=-\frac{z^{3}+c}{3z^{2}}.$ (5)

Roots of the polynomial equation (1) are the stable nodes of the ODE (3). At
the same time these roots are the attractors of the Newton and Euler iteration
process (2), at least, when the discretization step $h$ is small enough. The
boundary between basins of attraction of the iteration process (2) — the
fractal Newtonian Julia set — corresponds to a separatrix of (3), which should
be smooth when $f(z)$ is defined by (5) (see Fig. 1). Fractalization of the
separatrix occures due to the Euler discretization. This is a numerical
artifact, which can be considered as neglectable for practical applications at
$h\rightarrow 0$ .

Figure 1:  Newtonian Julia set — fractal boundary between white, black and
gray regions, which are the basins of attraction of three roots of the
equation (1) with $c=-1$ (left panel) and Newtonian pie — phase plane of the
flow dynamical system (3) (right panel): three roots of (1) are the stable
nodes of the ODE (3), its basins of attraction are divided by the smooth
separatrix. Euler discretization (4) of (3) results in emergence of fractal
basin boundary, like one on the left panel, which degenerates to the true
smooth linear separatrix at $h\rightarrow 0$.

While in general discretization of flow dynamical systems caused by numerical
time-integration can lead to emergence of solutions which do not represent the
dynamics of the original system and manifest themselves in changes of the
phase space structure, as in example discussed above, or changes in
bifurcation diagrams etc. (see, e.g., [12, 16, 17] and references there), this
problem can be considered from another angle: such discretization of well-
known flow systems can be regarded as a fruitful approach, which is widely
used in modern nonlinear theory and allows to generate new model maps (see,
e.g., [2, 22, 11, 1] and references there). Due to emergence of numerical
artifacts mentioned above dynamical systems generated this way can demonstrate
various nontrivial phenomena. The discretization step $h$ is usually defined
in such models in a wide range — moreover, it can be complex [18]. This
approach can also establich a background for introducing and considering of a
new class of systems, one example from which is proposed in present work.

Simple construction (2), being considered as an abstract dynamical system,
allows a wide spectrum of generalizations and parametrizations. Types of
dynamical behavior and obtained phenomena can also be rather diverse.
Particularly, the implicit dynamics, when every point in the phase space of
the system has both several images and several preimages [4, 3, 15], is also
possible. Such implicit correspondences have wide spectrum of applications
besides implicit numerical schemes of equations solving. Implicit functions
can occur in problems of reconstruction of a multidimensional object (or
system) from its projection [6], in the theory of generalized synchronization
[19], in economics [10, 7], computer graphics [20], chaos control techniques
[8], topology [21].

In the present paper we try to give an example of generalization of the
iteration process (2) and to investigate obtained system from the point of
view of theoretical nonlinear dynamics. In the section 1 we present the
procedure of deriving an implicit map using the modified Euler method. In the
section 2 we analyze the fractalization of both unstable and stable invariant
sets of such exotic system.

##  1 Basic model

Among the numerical recipes of the ODE integration the semi-implicit Euler
method is listed:

$z_{n+1}=z_{n}+h(f(z_{n})+f(z_{n+1}))/2.$ (6)

Let us generalize this scheme by parameterization:

$z_{n+1}=z_{n}+h((1-\alpha)f(z_{n})+\alpha f(z_{n+1}).$ (7)

In case when $f(z)$ chosen in form (5) this equation can be rewrited as
following:

$(\alpha
h+3)z_{n+1}^{3}z_{n}^{2}+((1-\alpha)h-3)z_{n+1}^{2}z_{n}^{3}+(1-\alpha)hcz_{n+1}^{2}+\alpha
hcz_{n}^{2}=0.$ (8)

This is also some iteration process, but, in contrast to (4), not traditional
for the nonlinear dynamical system theory. This is an implicit map with the
evolution operator looking like

$\Psi(z_{n+1},z_{n})=0.$ (9)

Both forward and backward iterations of this map are defined by multi-valued
functions,

$z_{n+1}=\Psi_{+}(z_{n})$ (10)

and

$z_{n}=\Psi_{-}(z_{n+1})$ (11)

respectively.

Two examples of implicit maps are described in [4, 9]. Below we are trying to
study the implicit dynamics on the new example of such map (8).

##  2 Numerical simulation

###  2.1 Repellers

We will start investigation from studying backward dynamics of the map (8) at
$\alpha=0$. In this case the map is single-valued time-forward and multi-
valued time-backward. We will study structure of its repellers, which form
boundaries of basins of attraction. It is worth mentioning here that since the
map (8) is defined by the cubic polynomial, solutions of the equation (11) can
be found analytically. The repellers of the map (8) at different values of
$|h|\leq 1$ are shown in the Fig. 2. At $h=1$ we obtain the classical
Newtonian Julia set, other positive values of $h$ correspond to
transformations of this fractal (see Fig. 2a,b). Repellers in this case still
define boundaries of areas of convergence of the Newton method (2) to
different roots of (1) — or of the Euler method to different nodes of the ODE
(3). At negative values of $h$ the process of search of repellers of the map
(8) corresponds to solving the ODE (3) with the time reversed with the Euler
method. The result of this process is a fractal set similar to the Sierpińsky
gasket (see Fig. 2d,e). $h=0$ is a degenerate case corresponding transition
between these two situations (see Fig. 2c,f).

The repellers for $h>1$ are shown in the Fig. 3, here $h=3$ (Fig. 3a) is also
a degenerate case — which follows from the structure of function (8), where
one of the terms becomes in this case equal to 0.

Figure 2: The repellers in the phase space of the map (8) with $h=1.0$ (a),
$h=0.5$ (b), $h\rightarrow+0$ (c) and $h=-1.0$ (d), $h=-0.5$ (e),
$h\rightarrow-0$ (f). Parameter $\alpha$ is equal to zero. Parameter $c$ is
not essential, here and further it is fixed being equal to $(1-i)/2$.  Figure
3: The repellers in the phase space of the map (8) with $\alpha=0$ and
different values of $h$: $3$ (a), $5$ (b), $7$ (c).

A useful tool for quantitative analysis of the phase space structure
transformations is a fractal dimension of the basin boundaries. Fig. 4
demonstrates the dependence of the box-counting dimension on the parameter $h$
value. In the vicinity of $h=0$ an abrupt change of the value of dimension
occurs, which indicates a phase transition of the Julia set. In the vicinity
of the degenerate case $h=3$ the fractal dimension value tends to 1 — it
corresponds to degeneration of the Julia set, which looks in this case like a
smooth circle (Fig. 3a). In the region near $h=4$ the value of dimension grows
almost up to $2$, and Julia set almost becomes a fat fractal (Fig. 3b). When
$h\geq 7$, the value of dimension decreases down to values below 1. The
attracting invariant set undergoes here crisis, and basin boundaries
degenerate to the fractal dust.

Figure 4: Box-counting dimension of the repellers of the implicit map (8) with
$\alpha=0.0$ for $|h|\leq 1$ (upper panel) and $1\leq h\leq 10$ (bottom
panel).

###  2.2 Attractors

In general case every point in the phase space of the implicit map (8) has
three images — roots of qubic polynomial equation. Time-forward dynamics of
such map is, as backward dynamics also, not single-valued. To study time-
forward dynamics it seems productive to apply methods which are usually
employed for an analysis of repellers. Particularly, we apply the “chaos game”
algorithm [18] in order to find attracting chaotic trajectories. To find
periodic trajectories we choose the roots of (8) at each iteration according
to a periodic sequence. We construct symbolic codes, consisting of characters
<<1>>, <<2>> and <<3>> — which correspond to the choice of the first, the
second or the third root respectively. The period of dynamical orbit should be
in this case equal or larger than a minimal period of such a sequence.

Let us start from the illustration of the evolution of attractors in special
case $\alpha=0$, which is shown in the Fig. 5. This situation corresponds to
the use of the explicit Euler method, and the forward-time dynamics is in this
case single-valued. Fig. 5a represents three attracting nodes at $h\rightarrow
0$, while an increase of parameter $h$ causes several period doubling
bifurcations (Fig. 5c-e), and the transition to chaos occurs (Fig. 5f).

The bifurcation diagram shown in the Fig. 6 gives more complete picture of the
forward-time behavior of the system (8). Here the real part of the complex
variable $z$ on the attracting invariant set is plotted versus parameter $h$.
At this picture the evolution of one of three attracting fixed points is
demonstrated. It undergoes several period-doubling bifurcations, transition to
chaos and back to the periodic regime, and finally is destroyed via crisis. In
the vicinity of the point $h=4$, where, as we mentioned above, Julia set
almost becomes a fat fractal, time-forward dynamics is chaotic.

Figure 5: Transformation of the attracting invariant sets of the implicit map
(8) with $\alpha=0.0$ and with $h\rightarrow 0$ (a), $h=0.5$ (b), 1.0 (c),
2.15 (d), 2.75 (e), 2.792 (f). Figure 6: The bifurcation diagram for one of
attracting invariant sets of the implicit map (8) with $\alpha=0.0$ (a) and
its enlarged fragment (b).

Next Figure 7 demonstrates the picture of dynamical regimes on the parameter
plane $(h,\alpha)$. When $\alpha\neq 0$, the map (8) becomes an implicit one,
which means that its dynamics is now muti-valued both time-forward and time-
backward.

Figure 7: The charts of dynamical regimes of the implicit map (8) for the
following periodic sequences of time-forward roots choice: $1$ (a), $12$ (b),
$112$ (c), $1112~{}$(d), $11112$ (e), $1(\times 8)2$ (f).

Except the simplest case, when the symbolic sequence has period 1 (Fig. 7a),
charts for different periodic sequences demonstrate similar features. Areas of
periodic dynamics in the quadrant $(h>0,\alpha<0.5)$ have typical “tongue”
shape with spikes in the point $\alpha=0,h=3$, where the map (8) is
degenerate. Another typical feature is partial symmetry of the parameter
plane: borders of areas of aperiodic dynamics are in many cases symmetrical
with respect to the point $(h=0,\alpha=0.5)$ in quadrants $(h>0,\alpha<0.5)$
and $(h<0,\alpha>0.5)$, and points with periodic dynamics are symmetrical to
points with aperiodic dynamic, especially for $|h|\leq 3$. It is a consequence
of specific symmetry of the map (8), which is invariant with respect to the
transformation $h\rightarrow-h,\alpha\rightarrow 1-\alpha,z_{n}\leftrightarrow
z_{n+1}$.

##  3 Conclusion

In this paper we present a short preliminary view on the dynamics of one
example of implicit systems, namely, the map (8). We demonstrate some
approaches for studying of such systems. Advanced investigation of this
implicit map should clarify the structure of its invariant sets. It seems a
promising and very interesting direction of research, since in implicit
systems, in contrast to traditionally studied explicit ones, an infinite
number of trajectories can coexist in forward time, which makes their
attracting invariant sets very complicated. Moreover, complexification of the
parameter $h$ in the map (8) leads to the possibility of a situation, when
$\Psi(z_{n+1},z_{n})=-\Psi^{*}(z_{n},z_{n+1})$. 111Here
$\Psi^{*}(z_{n+1},z_{n})=(\Psi(z^{*}_{n+1},z^{*}_{n}))^{*}$. For the map (8)
this happens at $h=\pm i$, $\alpha=1/2$. This situation, defined in [4, 9] as
generalized unitarity, manifests the emergence of phenomena typical for
Hamiltonian and almost Hamiltonian systems. In this context the implicit maps,
being an artificial construct, can help to describe strong multistability,
mixed dynamics and other complex phenomena of nonlinear dynamics.

## References

  * [1] Adilova, A.B., Kuznetsov, A.P., Savin, A.V.: Complex dynamics in the system of two coupled discrete R’́ossler oscillators. Izvestiya VUZ. Applied Nonlinear Dynamics 21(5), 108–119 (2013), (In Russian)
  * [2] Arrowsmith, D.K., Cartwright, J.H., Lansbury, A.N., Place, C.M.: The Bogdanov map: Bifurcations, mode locking, and chaos in a dissipative system. International Journal of Bifurcation and Chaos 3(04), 803–842 (1993)
  * [3] Bullett, S.R.: Dynamics of quadratic correspondences. Nonlinearity 1(1), 27–50 (1988)
  * [4] Bullett, S.R., Osbaldestin, A.H., Percival, I.C.: An iterated implicit complex map. Physica D: Nonlinear Phenomena 19(2), 290–300 (1986)
  * [5] Cayley, A.: Desiderata and suggestions: no. 3. The Newton-Fourier imaginary problem. American Journal of Mathematics 2(1), 97–97 (1879)
  * [6] DiFranco, D.E., Cham, T.J., Rehg, J.M.: Reconstruction of 3D figure motion from 2D correspondences. In: Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. CVPR 2001. vol. 1, pp. 307–314. IEEE (2001)
  * [7] Gardini, L., Hommes, C., Tramontana, F., De Vilder, R.: Forward and backward dynamics in implicitly defined overlapping generations models. Journal of Economic Behavior & Organization 71(2), 110–129 (2009)
  * [8] Hill, D.: Control of implicit chaotic maps using nonlinear approximations. Chaos: An Interdisciplinary Journal of Nonlinear Science 10(3), 676–681 (2000)
  * [9] Isaeva, O.B., Obychev, M.A., Savin, D.V.: Dynamics of a discrete system with the operator of evolution given by an implicit function: from the Mandelbrot map to a unitary map. Russian Journal of Nonlinear Dynamics 13(3), 331–348 (2017), (In Russian)
  * [10] Kennedy, J.A., Stockman, D.R.: Chaotic equilibria in models with backward dynamics. Journal of Economic Dynamics and Control 32(3), 939–955 (2008)
  * [11] Kuznetsov, A.P., Savin, A.V., Sedova, Y.V.: Bogdanov-Takens bifurcation: from flows to discrete systems. Izvestiya VUZ. Applied Nonlinear Dynamics 17(6), 139–158 (2009), (In Russian)
  * [12] Lóczi, L., Páez Chávez, J.: Preservation of bifurcations under Runge-Kutta methods. International Journal of Qualitative Theory of Differential Equations and Applications 3, 81–98 (2008)
  * [13] Magreñán, Á.A., Gutiérrez, J.M.: Real dynamics for damped Newton’s method applied to cubic polynomials. Journal of Computational and Applied Mathematics 275, 527–538 (2015)
  * [14] McLaughlin, J.: Convergence of a relaxed Newton’s method for cubic equations. Computers & chemical engineering 17(10), 971–983 (1993)
  * [15] Mestel, B.D., Osbaldestin, A.H.: Renormalisation in implicit complex maps. Physica D: Nonlinear Phenomena 39(2-3), 149–162 (1989)
  * [16] Páez Chávez, J.: Discretizing bifurcation diagrams near codimension two singularities. International Journal of Bifurcation and Chaos 20(5), 1391–1403 (2010)
  * [17] Páez Chávez, J.: Discretizing dynamical systems with generalized Hopf bifurcations. Numerische Mathematik 118(2), 229–246 (2011)
  * [18] Peitgen, H.O., Richter, P.H.: The beauty of fractals: images of complex dynamical systems. Springer Science & Business Media (1986)
  * [19] Pikovsky, A., Rosenblum, M., Kurths, J.: Synchronization: A Universal Concept in Nonlinear Sciences. Cambridge Nonlinear Science Series, Cambridge University Press (2001)
  * [20] Sclaroff, S., Pentland, A.: Generalized implicit functions for computer graphics. ACM Siggraph Computer Graphics 25(4), 247–250 (1991)
  * [21] Vlasenko, I.Y.: Internal maps: topological invariants and their applications. Proceedings of Institute of Mathematics of Ukrainian NAS, Institute of Mathematics of Ukrainian NAS (2014), (In Russian)
  * [22] Zaslavsky, G.M.: The physics of chaos in Hamiltonian systems. World Scientific (2007)


# Measurement-based quantum machine learning

Luis Mantilla Calderón1,2<EMAIL_ADDRESS>Polina Feldmann3,4
<EMAIL_ADDRESS>Robert Raussendorf4,5 Dmytro Bondarenko3,4
<EMAIL_ADDRESS>1Department of Computer Science, University of Toronto,
Canada  2Vector Institute for Artificial Intelligence, Toronto, Canada
3Department of Physics & Astronomy, University of British Columbia, Vancouver,
Canada  4Stewart Blusson Quantum Matter Institute, University of British
Columbia, Vancouver, Canada  5Institut für Theoretische Physik, Leibniz
Universität Hannover, Hannover, Germany

###### Abstract

A quantum neural network (QNN) is an object that extends the notion of a
classical neural network to quantum models for quantum data. We can create a
QNN by parametrizing a quantum process and then using it to model unknown
relations between quantum states. In this paper, we explore how to use
measurement-based quantum computation for quantum machine learning problems
and propose a universal QNN in this framework which we call the multiple-
triangle ansatz (MuTA). Using the proposed QNN, we solve several tasks,
including learning a universal set of gates, optimizing measurement with post-
processing, learning a quantum instrument, and the classification of classical
data. Finally, we discuss how to train an ansatz under the hardware
constraints imposed by photonic Gottesman-Kitaev-Preskill qubits. Our work
demonstrates the feasibility of using measurement-based quantum computation as
a framework for quantum machine learning algorithms.

††preprint: APS/123-QED

##  I Introduction

The idea of building a quantum computer has led to the development of several
algorithms that bring significant speedups over their classical counterparts.
Famous examples include Shor’s algorithm, Grover’s algorithm, and quantum
simulation algorithms, which outperform current classical algorithms in the
large-scale limit. However, these algorithms require a large number of qubits
and gates with the addition of quantum error correction to be implemented,
which is a big challenge for current quantum hardware. Thus, it is of interest
to find algorithms that can be implemented with fewer resources and still
bring speedups over classical algorithms.

One approach to save resources in some problems is using measurements with
feedback. This has been shown to bring significant resource savings in several
algorithms, such as implementing Shor’s algorithm with fewer qubits [1],
preparing the ground state of the toric code [2], and preparing matrix product
states (MPS) with exponentially fewer qubits than the counterpart with no
measurement plus feedback [3]. This resource saving is one of the many reasons
why measurement-based quantum computation (MBQC) [4] is of interest to this
field.

Moreover, another idea that has been explored recently is quantum machine
learning (QML) [5]. The primary objective of QML is to use current quantum
hardware, capable of implementing parametrized gates natively, as machine
learning models for performing inference over datasets of interest. One of the
key aims is to find a quantum advantage in these models before reaching fault-
tolerant systems. Current literature, including works like [6, 7, 8, 9, 10],
has shown some evidence of utility in quantum neural networks, but it is still
unclear if they can bring a significant advantage over classical algorithms.
Beyond its potential for a computational advantage over classical approaches,
QML is inherently valuable, offering novel approaches to problem-solving and
potential applications in fields where analysis of quantum data is required.

In this paper, we aim to study a family of models that harness both quantum
and classical resources to process classical and quantum data. Our approach
utilizes measurement-based quantum computation as a framework to define
quantum neural networks. This concept has been previously explored in the
context of the variational quantum eigensolver [11], multi-class
classification [12], and generative modeling [13]. In Section II, we propose a
methodology for creating QML models in MBQC. Additionally, Section III,
introduces a universal quantum neural network architecture that has several
desired properties for a QNN and can be used to solve a wide range of tasks.
We call this QNN architecture the multiple-triangle ansatz (MuTA). In Section
IV we demonstrate the application of MuTA for learning a universal set of
gates, a measurement with classical post-processing, and a quantum instrument.
Unlike earlier QML models in MBQC, MuTA combines features such as a being
universal approximator, having tunable entanglement, being trainable in scale
(with the right restrictions), and having engineerable bias. As discussed
later, these attributes make the MuTA architecture a robust foundation for
developing future QNN models within the MBQC paradigm.

##  II Measurement-based quantum machine learning

MBQC works by preparing an entangled state known as a _resource state_ and
then performing single-qubit measurements that consume this state [14].
Examples of resource states include graph states,

$\ket{G}=\prod_{(i,j)\in E}CZ_{ij}\ket{+}^{\otimes n}.$ (1)

Here, $G=(V,E)$ denotes a graph with vertices $V$ and edges $E$,
$X\ket{+}=\ket{+}$, and $CZ$ is a Controlled-$Z$ gate. $X$, $Y$, and $Z$ are
Pauli operators. To use $\ket{G}$ for MBQC, we define sets of input and output
qubits $I,O\subset V$, respectively, together with single-qubit measurements
$M^{i}$ at each node $i\notin O$. A common choice, which we will assume in
this paper, is $M^{i}_{\alpha}=\cos(\alpha)X_{i}+\sin(\alpha)Y_{i}$,
$\alpha\in(-\pi,\pi]$. However, extended MBQC allows $M^{i}_{\alpha}$ to be in
the $(X,Z)$ and $(Y,Z)$ planes, too [15]. The input of the circuit can be a
quantum state $\ket{\psi}_{\mathrm{in}}$, and in this case we replace the
$\ket{+}$ qubits in $I$ by $\ket{\psi}_{\mathrm{in}}$ before applying the $CZ$
gates in Eq. (1). If the input is classical, we can encode it in an input
quantum state or in the measurement angles $\alpha(i)$ of $M_{\alpha}^{i}$.
The output of the circuit is stored in $O$.

To obtain a deterministic output in spite of the inherent randomness of
quantum measurements, the measurement angles have to be conditioned on
previous measurement outcomes. For MBQC on a graph state, the presence of
_flow_ guarantees a viable conditioning [16]. Let $N_{G}(i)$, $i\in V$ denote
the neighbors of $i$ in $G$. A resource state characterized by $(G,I,O)$ has
flow iff there exists a function $f:V\setminus O\rightarrow V\setminus I$ and
a partial order $<$ such that $\forall i\in V$

  * •

$(i,f(i))\in E$,

  * •

$i<f(i)$,

  * •

$\forall j\in N_{G}(f(i))\setminus\\{i\\}:\quad i<j$.

The flow ensures that we can measure in a time order compatible with $<$ and
compensate a $(-1)$-outcome on $i$ by subsequently applying
$X_{f(i)}\prod_{j\in N_{G}(f(i))\setminus\\{i\\}}Z_{j}$. This compensation,
which ensures determinism, is equivalent to a simple adaptation of measurement
angles. To efficiently find the flow of a graph, we can use the algorithms
presented in Refs. [17, 18]. There is a more general condition known as Pauli
flow [15], which is necessary and sufficient for uniformly deterministic
computation; however, for the sake of simplicity, we consider only graphs with
flow.

Classical (supervised) machine learning aims to learn the underlying
probability distribution of a given dataset. In the typical setup, a machine
learning model $\mathcal{M}$ is trained on a dataset
$\mathcal{D}=\\{(\mathbf{x}_{i},y_{i})\\}_{i=1}^{N}$, where
$\mathbf{x}_{i}\in\mathcal{X}$ represents features and $y_{i}\in\mathcal{Y}$
represents labels. The objective is to learn a function
$f_{\theta}:\mathcal{X}\rightarrow\mathcal{Y}$, parameterized by $\theta$,
that approximates the true relationship between features and labels. This
learning process is driven by a loss function $\ell(\theta;\mathcal{D})$,
which evaluates the difference between predicted and true labels. During
training, $\theta$ is optimized to minimize $\ell(\theta;\mathcal{D})$. The
model’s ability to generalize is tested on unseen data, reflecting its
capabilities in representing the true data distribution.

Integrating the discussed concepts, an MBQC circuit with graph states as a
resource is a tuple $(G,I,O)$ together with a measurement pattern
$\mathcal{P}_{\bm{\theta}}$ which can be carried out deterministically. By
allowing the measurement angles $\bm{\theta}$ to be parameterized, we can
define a QML model (also called ansatz)
$\mathcal{E}_{\bm{\theta}}:\mathcal{H}_{I}\longrightarrow\mathcal{H}_{O}$ as
the quantum channel defined by performing $\mathcal{P}_{\bm{\theta}}$ with
$(G,I,O)$ on an input state $\ket{\psi_{in}}$ [19]. In general, a measurement-
based quantum machine learning (MB-QML) model is a resource state together
with a parametrized measurement pattern $\mathcal{P}_{\bm{\theta}}$ that can
deterministically perform inference on the input states of a given dataset
$\mathcal{D}=\\{(\rho_{j},\sigma_{j})\\}_{j=0}^{N}$ and the parameters
$\bm{\theta}$ can be optimized to minimize a given loss function
$\ell(\bm{\theta},\mathcal{D})$.

##  III The multiple-triangle ansatz

Classical deep neural networks (NNs) have shown an incredible power for
learning to represent functions of real-world data. Several architectures have
been proposed to solve problems with different structure, including multi-
layer perceptrons, convolutional neural networks, transformers, graph neural
networks, and many more. Common features these architectures share are the
capability to (I) _universally approximate_ functions with the desired
structure, have a (II) _tunable message passing_ between different nodes, have
(III) _engineerable bias_ , and (IV) _be trainable_ at scale. Moreover,
underlying all these complex models are a small set of operations that
comprise an _artificial neuron_. A quest for QNN models has driven the
community to propose many ideas for constructing circuits that behave similar
to classical NNs [8, 20, 21].

(a)

(b)

Figure 1: Illustrations of the Multiple-Triangle Ansatz (MuTA) architecture:
(a) A MuTA for three qubits, showing input qubits $I$ on the left, output
qubits $O$ on the right (in blue), with arrows indicating the flow of
$(G,I,O)$; (b) A $(2,0)$-MuTA layer.

Here, we introduce QNNs which are native to MBQC and exhibit a number of
beneficial properties similar to those present in classical NNs. The
centerpiece of our framework is a resource state constructed from simple, yet
universal, building blocks inspired by Ref. [22]. Our _multiple-triangle
ansatz (MuTA)_ consists of 1D cluster states connected by multiple triangles
as shown in Fig. 1. To navigate the qubits of this ansatz, we introduce the
following sets: $Q_{i,k}$ denotes the qubit in row $i$ and column $k$,
$T_{i,j,k}=Q_{i,k}\cup Q_{j,k-1}\cup Q_{j,k}\cup Q_{j,k+1}$ is the set of
qubits in a triangle connecting wires $i$ (tip) and $j$ (base) around column
$k$, and $C_{i,j,k}:=Q_{j,k}\subset T_{i,j,k}$ forms the center of its base.
We denote $C_{i,j,k}$ and $T_{i,j,k}$ by $C_{i,j}$ and $T_{i,j}$ whenever $k$
is unambiguous. To build MuTA layer $(n,i)$, we connect $n$ wires of length
$5$ by a collection of triangles $T_{i,j,1}$ with
$\\{j\\}\subseteq\\{0,\dots,n-1\\}\backslash{\\{i\\}}$ (note that we count
starting from zero). We call a MuTA layer fully connected if
$\\{j\\}=\\{0,\ldots,n-1\\}\setminus\\{i\\}$. A MuTA consists of multiple MuTA
layers. We concatenate two layers $(n,i)$ and $(n,j)$ of equal width $n$ by
identifying the output qubits $O$ of the preceding with the input qubits $I$
of the subsequent layer. When increasing (decreasing) $n$ from one layer to
the next, some of the input qubits of the second layer (output qubits of the
first layer) join the input (output) set of the overall graph state. We show
that this architecture satisfies the following desiderata:

######  Property 1 (Determinism).

Any measurement pattern on MuTA can be performed deterministically.

###### Proof.

MuTA has a flow $f$ defined by $f(Q_{i,k})=Q_{i,k+1}$ for each node $i\in
V\setminus O$. A compatible partial order $<$ is established as follows:
$Q_{i,k}<Q_{i^{\prime},k^{\prime}}$ if either $k=k^{\prime}=4m$, $i\neq
i^{\prime}$ with $f(Q_{i,k})$ a tip qubit; $k=4m$ and $k^{\prime}=k+1$ with
$f(Q_{i,k})$ not a tip qubit; $k=k^{\prime}=4m+1$, $i\neq i^{\prime}$, and
$Q_{i^{\prime},k}$ a tip qubit; $k^{\prime}=k+1$ and $Q_{i,k}$ is a tip qubit;
$k=4m+2$ and $k^{\prime}=k+1$; or $k=4m+3$, $k^{\prime}=k+1$, and
$f(Q_{i^{\prime},k^{\prime}})$ is a tip qubit; additional relations are
defined via transitivity. Thus, for any measurement pattern, Theorem 1 from
Ref. [16] explicitly states how to adapt measurement angles to obtain a
deterministic outcome. ∎

######  Property 2 (Universality).

Given any $n$-qubit unitary operator $V\in U(2^{n})$, there exists a
measurement pattern on a sufficiently deep MuTA that exactly implements $V$.

###### Proof.

The set of single-qubit gates $V^{\prime}\in U(2)$, together with an
entangling gate such as $\text{Ising}XX(\varphi)=\exp(-i\varphi X\otimes
X/2)$, forms a universal set of gates [23, 24], which implies any $V\in
U(2^{n})$ can be decomposed as product of these gates. Both types of gates can
be implemented by MuTA using the measurement patterns shown in Table 1. First,
any single-qubit gate can be implemented by measuring a five-qubit wire with
angles given by the Euler decomposition of
$V^{\prime}=R_{x}(-\lambda)R_{z}(-\phi)R_{x}(-\theta)$, where
$R_{x}(\alpha)=\exp(-i\alpha X/2)$ and $R_{z}(\alpha)=\exp(-i\alpha Z/2)$
[14]. In addition, the $\text{Ising}XX(\varphi)$ gate can be implemented with
a MuTA layer $(2,0)$, which follows from the generator of $C_{i,j}$ (See
Appendix A). Therefore, a MuTA layer of width $n$ consisting of only $n$
disconnected five-qubit wires can implement the former, while one consisting
of $n-2$ disconnected wires and a connected $(2,0)$ block can implement the
latter. Using combinations of these two layers with their corresponding
measurement patterns we define a MuTA that exactly implement $V$.

Gate | Measurement Pattern
---|---
$R_{x}(-\lambda)R_{z}(-\phi)R_{x}(-\theta)\otimes I$ | $M_{0}^{8}M_{\lambda}^{3}M_{0}^{7}M_{\phi}^{2}M_{\theta}^{1}M_{0}^{6}M_{0}^{5}M_{0}^{0}$
$\text{Ising}XX(\varphi)$ | $M_{0}^{8}M_{0}^{3}M_{0}^{7}M_{0}^{2}M_{0}^{1}M_{\varphi}^{6}M_{0}^{5}M_{0}^{0}$
Table 1: Measurement patterns for universal gates in MuTA. Indices are matched
with those from Figure 1b.

∎

######  Property 3 (Tunable Entanglement).

A fully connected MuTA layer $(n,i)$ implements

  1. 1.

a non-entangling gate between wires $i$ and $j\neq i$ if $C_{i,j}$ is measured
at $\alpha\in\\{0,\pi\\}$

  2. 2.

an entangling gate between wires $i$ and $j\neq i$ if $C_{i,j}$ is measured at
$\alpha\notin\\{0,\pi\\}$.

###### Proof.

The first statement follows from noting that the only entangling generators of
MuTA belong to $C_{i,j}$ qubits (see Appendix A), and these generate
entanglement between wires $i$ and $j$.

For the second statement, we recognize that all $C_{i,j}$ in the layer can be
measured simultaneously (since $\forall j,j^{\prime}\ C_{i,j}\nleq
C_{i,j^{\prime}}$). This independence implies that the entanglement property
between wires $i$ and $j$ does not depend on the measurement angle of
$C_{i,j^{\prime}\neq j}$. Consider $G_{i,k}$ to be the operation induced by
measurement $M^{C_{i,k}}_{\alpha}$ on an input state. Then, there exist input
states $\ket{\psi}_{i},\ket{\psi}_{j}$ such that $G_{i,j}$ entangles subsystem
$i$ with $j$ for
$\ket{\psi}_{\text{in}}=\bigotimes_{k=0}^{|I|-1}\ket{\psi}_{k}$. Thus, for the
input state
$\ket{\psi^{\prime}}_{\text{in}}=G_{ij^{\prime}}^{\dagger}\ket{\psi}_{\text{in}}$
the operator $G_{ij}G_{ij^{\prime}}\ket{\psi^{\prime}}_{\text{in}}$ entangles
subsystems $i$ and $j$.

∎

######  Property 4 (Monotonicity of Expressivity).

Adding layers or wires to a given MuTA does not restrict the implementable set
of gates.

###### Proof.

Adding an additional MuTA layer or connecting an additional wire $n$ by
admissible triangles $T_{i,n}$ to existing layers $(n,i)$ does not restrict
the gates that can be expressed by the ansatz. An additional layer can always
be turned into the identity operation by measuring all qubits in the $X$ basis
$(\alpha=0)$. For an additional wire, Property 3 directly implies that it can
be disentangled without restricting the measurements on the other wires. ∎

######  Property 5 (Bias Engineering).

The set of transformations implementable by a given MuTA depends on the chosen
depth (number of layers), connectivity (triangles), preset or restricted
measurement angles (variational parameters), and the width of intermediate
layers (width variations generating auxiliary inputs and outputs).

###### Proof.

Straightforward from previous properties. ∎

######  Property 6 (Scalability).

A fully connected MuTA with $d$ layers of width $n$ has $\leq 4\times d\times
n$ variational parameters.

###### Proof.

MuTA has at most as many variational parameters as qubits, i. e., $4\times
d\times n$. This number does not depend on connectivity. ∎

######  Property 7 (2-Colorable).

The graph of any MuTA is 2-colorable.

###### Proof.

A graph is 2-colorable if and only if it is bipartite. Collecting all even
columns into one subset and all odd columns into the other yields a
bipartition of any MuTA. ∎

These properties show MuTA possesses several features commonly found in
classical NNs. Specifically, Properties 1-2 and 4 align with Feature (I),
Property 3 with Feature (II), Property 5 with Feature (III), and Property 6-7
with Feature (IV). The last comparison is supported by the use of polynomial
number of parameters and the existence of scalable purification protocols for
constructing large MuTA [25]. Despite its advantages over other ansatze with
fixed entanglement structures, such as the cluster state, challenges persist.
Notably, the quantum no-free lunch theorem [26] and the barren plateau
phenomenon [27, 28] necessitate the tailoring of our ansatz to specific tasks
and incorporating prior knowledge, such as the symmetries of the data [29], to
achieve over-average performance and enable training at scale. These
characteristics position MuTA as a promising universal QNN candidate within
the MBQC framework.

##  IV Learning to measure

In this section, we will explore multiple QML tasks and train the measurement
angles from the MuTA (Figure 1b). We perform supervised learning on quantum
data to learn a universal set of gates and study the effect of noise. We also
perform classification of quantum states to distinguish between metrologically
relevant and irrelevant quantum states, and we learn a quantum instrument that
effectively implements teleportation between MuTA wires.

###  IV.1 Universal set of gates

We show that the MuTA is universal by showing the sub-graph in Figure 1b can
learn Haar-random local gates in the first qubit and the entangling gate
$\text{Ising}XX\left(\pi/2\right)$. The dataset used to learn the measurement
angles is $\left\\{\sigma_{i},U\rho_{i}U^{\dagger}\right\\}_{i=1}^{N}$ and the
loss function to minimize is the average infidelity,

$\ell(\bm{\theta})=1-\frac{1}{N}\sum_{i}F(\sigma_{i},U\rho_{i}U^{\dagger}).$
(2)

We use a dataset of size $N_{tr}=7$ for training and $N_{te}=3$ for testing,
and use Haar-random states $\rho_{i}$ for each datapoint. Then, using the Adam
optimizer and average over 20 different random initializations and unitaries,
we can learn this universal set of gates as shown in Figures 2a and 2b.

(a)

(b)

Figure 2: Learning curves for the data sets for (a) single-qubit Haar-random
unitaries in the first qubit and (b) an $\text{Ising}XX\left(\pi/2\right)$
gate. For (a), we average the learning curves obtained for $20$ different
unitaries. The shaded region is the standard deviation of the loss.

###  IV.2 Learning with noise

A criterion for QML to be implementable in practice is robustness to
environmental noise. We perform the same optimization routine made in Figure
2b for two noisy scenarios. First, training the model with noisy data
$\left\\{\sigma_{i},\mathcal{N}\left(U\rho_{i}U^{\dagger}\right)\right\\}_{i=1}^{N}$,
and second, evolving the underlying graph state with a depolarizing channel,
which we discuss in Appendix C.

For the noisy data case, we use a random unitary noise channel, defined as
$\mathcal{N}_{rand}(\rho)=U_{br}^{\dagger}\rho U_{br}$, where $U_{br}$ is the
effect of a random Brownian circuit. This circuit can be constructed by
evolving the system with random hermitian matrices $H_{i}$ for a short amount
of time $U_{br}=\prod_{j=0}^{N}e^{iH_{i}\Delta t}$. We also study the effect
of a bit-flip noise channel at every qubit,
$\mathcal{N}_{bit,j}(\rho)=(1-p)\rho+pX_{j}\rho X_{j}$.

In Figures 3a and 3b, we plot the optimized fidelity as a function of the
noise strength after training for $60$ and $200$ steps, respectively. We
averaged $5$ learning curves that use a dataset of size $N_{tr}=10$ for
training and $N_{te}=10$ for testing. Similar to the noiseless setting, each
learning curve is obtained with a different Haar-random dataset. These figures
show that increasing the noise strength reduces the fidelity of the trained
circuit slowly, similar to that seen in previous QNN proposals. For the bit-
flip noise channel, the model can learn the correct parameters when the
majority of the two-qubit dataset is not bit-flipped – this is, at $p<0.5$ .

(a)

(b)

Figure 3: Stability of QML routine under noise affecting the training dataset.
The testing curves are obtained using noiseless datasets.

###  IV.3 Measurement with classical post-processing

A field of application for QML is quantum sensing and quantum metrology [30,
31, 32, 33, 34]. Techniques in these fields use entangled states to better
estimate an unknown parameter. Here, we train a hybrid quantum-classical model
to distinguish between two-qubit states with high and low quantum Fisher
information (QFI). This quantity is of great importance as it bounds the
precision of any estimator of $\theta$ by the quantum Cramer-Rao bound
$\operatorname{Var}(\hat{\theta})\geq\frac{1}{nF_{Q}(\theta)}$. In this
problem, we deal with pure states $\rho_{\theta}$, and for a given Hermitian
Hamiltonian $\hat{H}$ such that $\rho_{\theta}=e^{-i\theta\hat{H}}\rho
e^{i\theta\hat{H}}$, the quantum Fisher information of a state is given by

$F_{Q}(\rho_{\theta})=4\left(\operatorname{Tr}(\rho\hat{H}^{2})-\operatorname{Tr}(\rho\hat{H})^{2}\right).$

For our example, we set $H=h\otimes\mathbf{1}+\mathbf{1}\otimes h$ with
$h=\alpha_{x}X+\alpha_{y}Y+\alpha_{z}Z$ and
$\alpha_{x}^{2}+\alpha_{y}^{2}+\alpha_{z}^{2}=\frac{1}{4}$ such that the
_standard quantum limit_ (SQL) and the _Heisenberg limit_ (HL) become
$F_{Q}^{(SQL)}=2$ and $F_{Q}^{(HL)}=4$, respectively. We use the value of
$F_{Q}$ to classify the states, which in the ideal case would be $0$ for
$F_{Q}(\rho)\leq 2$, and $1$ otherwise.

We model $F_{Q}(\cdot)$ as a degree two polynomial in two variables
$f_{\beta}(x_{1},x_{2})=\beta_{0}+\beta_{1}x_{1}+\beta_{2}x_{2}+\beta_{3}x_{1}^{2}+\beta_{4}x_{1}x_{2}+\beta_{5}x_{2}^{2}$
(since $F_{Q}$ is quadratic), together with the measurement angles
$\bm{\theta}$ of the MuTA, where $x_{1}$ and $x_{2}$ are the probabilities of
outcomes $(0,0)$ and $(1,1)$ of the output state when measured in the $(Z,Z)$
basis, respectively. Then, we optimize the parameters of the model
$\hat{F}_{\bm{\theta}}(\rho):=f_{\bm{\theta}}(P_{00},P_{11})$ by minimizing a
soft-margin loss function

$\displaystyle\ell(\bm{\theta})=\frac{1}{N}\sum_{i=1}^{N}\bigg{[}y_{i}\max$
$\displaystyle\left\\{0,-\hat{F}_{\bm{\theta}}(\rho_{i})+2+\epsilon\right\\}+$
$\displaystyle(1-y_{i})\max\left\\{0,\hat{F}_{\bm{\theta}}(\rho_{i})-2+\epsilon\right\\}\bigg{]},$

where the parameter $\epsilon$ controls the width of the margin.

The input data used for training this POVM and classical post-processing model
is a set of random states $S=S_{1}\cup S_{2}$ sampled from a 2-parameter
family,

$\displaystyle S_{1}$
$\displaystyle=\left\\{\cos{\theta}\ket{00}+e^{i\phi}\sin{\theta}\ket{11}\mid\phi,\theta\sim\mathcal{U}_{[0,2\pi]}\right\\}$
$\displaystyle S_{2}$
$\displaystyle=\left\\{\cos{\theta}\ket{++}+e^{i\phi}\sin{\theta}\ket{--}\mid\phi,\theta\sim\mathcal{U}_{[0,2\pi]}\right\\},$

where $\mathcal{U}_{[0,2\pi]}$ is the uniform distribution and the target
labels are $0$ or $1$ determined with the ideal classifier dictated by
$F_{Q}$. This family of states is easy to prepare and spans a two-dimensional
surface for every measurement basis.

We train this model using $50$ states in $S_{1}$ and $50$ in $S_{2}$ using the
Adam optimizer and obtain a classifier with an accuracy of $0.9725\pm 0.0042$,
where $0.0149\pm 0.0006$ are false positives, and $0.0125\pm 0.0006$ are false
negatives, whenever we chose to ignore all states that have an estimated QFI
between $1.9$ and $2.1$.

Figure 4: Learned surface to classify states of high and low QFI. The surface
is defined by a degree two polynomial, and the position of each point on the
surface is defined by the measurement pattern.

The quantum Fisher information has a standard measurement protocol, making its
estimation via QML seemingly redundant. But the main takeaway is showcasing
MB-QML’s potential to classify states by metrics that aren’t directly
measurable. This becomes invaluable when we can easily classify a subset of
states using a known metric but struggle to do so for a larger set,
particularly when an analytical expression for the metric is missing.

###  IV.4 Quantum instrument for teleportation

Here we use MuTA with additional conditional measurements to learn a simple
quantum instrument. In general, a quantum instrument is a map
$\mathcal{I}:\operatorname{End}(\mathcal{H}_{1})\rightarrow\operatorname{End}(\mathcal{H}_{2})\otimes\operatorname{End}(\mathbb{C}^{\absolutevalue{X}})$
that measures a state $\rho$ and stores the measurement outcome,

$\mathcal{I}(\rho)=\sum_{x\in X}E_{x}(\rho)\otimes\ket{x}\bra{x},$

where $\left\\{E_{x}\right\\}_{x\in X}$ is a collection of completely positive
maps such that $\operatorname{Tr}\left(\sum_{x\in
X}E_{x}(\rho)\right)=\operatorname{Tr}(\rho)$. The instrument we study is the
teleportation protocol. This protocol consists of creating a maximally
entangled state $\ket{\Phi}$, measuring the state to be teleported
$\ket{\psi}$ together with some subsystem of $\ket{\Phi}$ in an entangled
basis, and finally applying a unitary transformation to the remaining
unmeasured subsystem depending on the measurement outcome. The goal of this
example is not to show that we can do teleportation, as the whole basis of
MBQC is teleportation. The goal is to show that we can learn a quantum
instrument using measurements conditioned to previous measurement outcomes.

Figure 5: Learning curve for learning an instrument that performs
teleportation using the MuTA. We use different datasets of $35$ states for
training and $15$ for testing in each run. We average over $10$ learning
curves. The node colors yellow, grey, purple, and light blue represent
trainable, fixed, controlled, and quantum output nodes, respectively.

We can see in Figure 5 that the model learns the teleportation protocol from
qubits $8$ to $22$ with a perfect fidelity, showing a proof-of-principle for
learning quantum instruments with MB-QML.

###  IV.5 Classification of classical data

Another application of MB-QML is the processing of classical data. Previously,
there has been extensive work on using quantum models to classify classical
datasets, and some examples can be found on [35, 9, 6]. Here, we show how to
use MBQC to create a kernel Support Vector Machine (SVM) classifier and use it
to classify synthetic datasets.

Figure 6: Embedding used for kernel SVM classification of a 2D dataset. Here,
the measurement angle $\theta$ is $\cos(x_{0})\cos(x_{1})$, where $x_{0}$ and
$x_{1}$ are the coordinates of the input data.

We again use MuTA, the universal ansatz we propose, to implement an embedding
$x_{i}\mapsto\ket{\phi(x_{i})}$ of a 2D dataset, shown in Figure 6. This map
is used to construct the kernel which is discussed in more detail in Appendix
D

$K(x_{i},x_{j})=\absolutevalue{\innerproduct{\phi(x_{i})}{\phi(x_{j})}}^{2}.$
(3)

When classifying the different ’toy‘ datasets in Figure 7, we can see this
kernel can be used for data that does not have a strongly non-linear
structure, such as _circles_ and _blobs_ , but not for _moons_. This shows
that there is room for improvement in the design of a quantum kernel using
MBQC, possibly using kernel alignment, that can deal with datasets of higher
dimensions and classify datasets with high degrees of non-linearity.

Figure 7: The classification of three different datasets using the SVM with
the kernel defined in Equations 3 and D. All models were trained with $160$
data points and tested with $40$ data points.

##  V Hardware-Efficient Ansatz

There are some hardware restrictions whenever implementing MBQC with photons.
In particular, if we use the GKP encoding, measuring at arbitrary angles is
complicated, whereas using the dual rail encoding, we can measure at arbitrary
angles, but $CZ$ gates are probabilistic [36, 37]. In terms of implementing a
QML model with these restrictions, we have to learn to either use a discrete
set of angles corresponding to accessible magic states or use a model with an
underlying graph that changes every time. Here, we focus on the former and
propose heuristic algorithms for discrete optimization over measurement
patterns, where the possible angles are
$\theta_{i}\in\left\\{0,\pi/4,\pi/2\right\\}$. In this scenario of photonic
GKP computation, measurements of $0$ and $\pi/2$ can be performed using
homodyne detection on the underlying graph state, while measurement in $\pi/4$
requires injecting a $\ket{T}:=\ket{0}+e^{i\pi/4}\ket{1}$ magic state [38,
39].

Discrete optimization can be NP-hard. However, finding a heuristic for this
hardware-constrained case can be of great practical value. We propose two
different approaches to this problem. The first one is an epsilon-greedy
algorithm that performs a layer-wise search over the measurement angles shown
in Figure 8. The second is finding a pattern via deep Q-learning (DQN), a
reinforcement learning (RL) algorithm, shown in Figure 9. The gate we chose to
learn is $U=(T\otimes\mathbf{1})\ e^{-i\frac{\pi}{8}X\otimes X}$, which
requires $T$-magic states to be implemented [40]. Namely, we must inject
$\ket{T}$ states in nodes $2$ and $6$ of Figure 1b. For the epsilon-greedy
example, we used a dataset of $N=10$, and for the DQN example, we used a
dataset of $N=30$, both with $30\%$ of the data used for testing.

Figure 8: Learning curves of five trials of the greedy algorithm compared to
random search. All examples set $\epsilon=0$ and $L_{max}=4$. Two out of five
runs got stuck in a local minimum until the parameters were reinitialized.

The second approach uses DQN to find the optimal measurement pattern. Here,
the observation of the RL agent consists of the whole measurement pattern plus
an additional node label input. The actions it can take are either measuring
at an angle of $0$, $\pi/2$, or $\pi/4$. Instead of searching for the best
measurement angle at each node, the agent tries to find a balance between
exploration and exploitation. This might lead to getting stuck in a local
minimum, as shown in Figure 9. However, its worth noting that the benefit of
DQN would appear when there needs to be classical processing of partial
information of the quantum state. This means if we measure some part of our
state and extract information from it, DQN could learn how to use this
classical information instead of the simple greedy search, which would naively
suffer from the curse of dimensionality.

Figure 9: Learning curves of five different runs using the DQN algorithm
compared to random search.

##  VI Discussion

In this work, we studied how to use MBQC to do QML. In particular, we proposed
and developed a framework for MB-QML. With this framework, we introduce a
universal quantum neural network (MuTA) and demonstrated how to employ this
ansatz to solve several tasks. MuTA is the first QNN in the MBQC framework
that simultaneously satisfies desired properties mentioned in Section III,
including being a universal approximator, having tunable entangling blocks,
and permitting engineerable inductive bias. We provide numerical evidence for
MuTA with experiments for learning a universal set of gates, a classifier of
quantum states, and a quantum instrument. We also show how to do kernel SVM
classification of classical data using the MuTA to create the kernel matrix
and propose algorithms for optimization of MBQC circuits that are restricted
by the hardware constraints of a photonic GKP qubit encoding.

Several questions arise from this work. An important question to ask is under
which conditions on the data MB-QML performs better than its gate-based
counterpart. It has been previously shown that using measurements with
feedback can allow us to implement specific maps with fewer resources [2, 3,
1]. Thus, to exploit these benefits we would need a more elaborate model with
classical and quantum processing that makes use of an MBQC ansatz. However, it
would be ideal to find general conditions on arbitrary data distributions
under which MB-QML would be better suited than gate-based QML.

Another promising area of research involves applying MB-QML to more complex
datasets, including sequential quantum data. This could mean developing
recurrent MB-QML models akin to those discussed in [41], or constructing
mechanisms similar to attention models using graph states. The key approach
here is to utilize measurements with feedback, as this technique seems to be
crucial for enhancing the efficiency of computations.

###### Acknowledgements.

This work was funded by Canada First Research Excellence Fund and the Quantum
Materials and Future Technologies Program. LM would like to thank helpful
discussions with Paul Herringer, Olivia Di Matteo, Ilan Tzitrin, and Alán
Aspuru-Guzik.

Data availability: All simulations were made in Python, and they can be found
in https://github.com/mentpy/mentpy.

## References

  * Rossi  _et al._ [2021] M. Rossi, L. Asproni, D. Caputo, S. Rossi, A. Cusinato, R. Marini, A. Agosti, and M. Magagnini, Using shor’s algorithm on near term quantum computers: a reduced version (2021), arXiv:2112.12647 [quant-ph] .
  * Raussendorf  _et al._ [2005] R. Raussendorf, S. Bravyi, and J. Harrington, Phys. Rev. A 71, 062313 (2005).
  * Malz  _et al._ [2024] D. Malz, G. Styliaris, Z.-Y. Wei, and J. I. Cirac, Physical Review Letters 132 (2024).
  * Raussendorf  _et al._ [2003] R. Raussendorf, D. E. Browne, and H. J. Briegel, Physical review A 68, 022312 (2003).
  * Biamonte  _et al._ [2017] J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd, Nature 549, 195 (2017).
  * Abbas  _et al._ [2021] A. Abbas, D. Sutter, C. Zoufal, A. Lucchi, A. Figalli, and S. Woerner, Nature Computational Science 1, 403 (2021).
  * Cong  _et al._ [2019] I. Cong, S. Choi, and M. D. Lukin, Nature Physics 15, 1273 (2019).
  * Beer  _et al._ [2020] K. Beer, D. Bondarenko, T. Farrelly, T. J. Osborne, R. Salzmann, D. Scheiermann, and R. Wolf, Nat Commun 11, 808 (2020).
  * Schuld and Killoran [2019] M. Schuld and N. Killoran, Physical review letters 122, 040504 (2019).
  * Tilly  _et al._ [2022] J. Tilly, H. Chen, S. Cao, D. Picozzi, K. Setia, Y. Li, E. Grant, L. Wossnig, I. Rungger, G. H. Booth, _et al._ , Physics Reports 986, 1 (2022).
  * Ferguson  _et al._ [2021] R. R. Ferguson, L. Dellantonio, A. Al Balushi, K. Jansen, W. Dür, and C. A. Muschik, Physical review letters 126, 220501 (2021).
  * Yun  _et al._ [2022] W. J. Yun, H. Baek, and J. Kim, arXiv preprint arXiv:2210.16731 (2022).
  * Majumder  _et al._ [2023] A. Majumder, M. Krumm, T. Radkohl, H. P. Nautrup, S. Jerbi, and H. J. Briegel, Variational measurement-based quantum computation for generative modeling (2023), arXiv:2310.13524 [quant-ph] .
  * Raussendorf and Briegel [2001] R. Raussendorf and H. J. Briegel, Physical review letters 86, 5188 (2001).
  * Browne  _et al._ [2007] D. E. Browne, E. Kashefi, M. Mhalla, and S. Perdrix, New Journal of Physics 9, 250 (2007).
  * Danos and Kashefi [2006] V. Danos and E. Kashefi, Physical Review A 74, 052310 (2006).
  * De Beaudrap [2008] N. De Beaudrap, Physical Review A 77, 022328 (2008).
  * Mhalla and Perdrix [2008] M. Mhalla and S. Perdrix, in  _Automata, Languages and Programming: 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I 35_ (Springer, 2008) pp. 857–868.
  * Mantilla Calderón [2023] L. C. Mantilla Calderón,  _Measurement-based quantum machine learning_ , Master’s thesis, University of British Columbia (2023).
  * da Silva  _et al._ [2016] A. J. da Silva, T. B. Ludermir, and W. R. de Oliveira, Neural Networks 76, 55 (2016).
  * Benedetti  _et al._ [2019] M. Benedetti, E. Lloyd, S. Sack, and M. Fiorentini, Quantum Science and Technology 4, 043001 (2019).
  * Danos  _et al._ [2005] V. Danos, E. Kashefi, and P. Panangaden, Physical Review A 72, 064301 (2005).
  * Nielsen and Chuang [2010] M. A. Nielsen and I. L. Chuang,  _Quantum computation and quantum information_ (Cambridge university press, 2010).
  * Bremner  _et al._ [2002] M. J. Bremner, C. M. Dawson, J. L. Dodd, A. Gilchrist, A. W. Harrow, D. Mortimer, M. A. Nielsen, and T. J. Osborne, Physical review letters 89, 247902 (2002).
  * Goyal  _et al._ [2006] K. Goyal, A. McCauley, and R. Raussendorf, Phys. Rev. A 74, 032318 (2006).
  * Poland  _et al._ [2020] K. Poland, K. Beer, and T. J. Osborne, arXiv preprint arXiv:2003.14103 (2020).
  * McClean  _et al._ [2018] J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven, Nature communications 9, 4812 (2018).
  * Ragone  _et al._ [2023] M. Ragone, B. N. Bakalov, F. Sauvage, A. F. Kemper, C. O. Marrero, M. Larocca, and M. Cerezo, A unified theory of barren plateaus for deep parametrized quantum circuits (2023), arXiv:2309.09342 [quant-ph] .
  * Schatzki  _et al._ [2022] L. Schatzki, M. Larocca, Q. T. Nguyen, F. Sauvage, and M. Cerezo, Theoretical guarantees for permutation-equivariant quantum neural networks (2022), arXiv:2210.09974 [quant-ph] .
  * Degen  _et al._ [2017] C. L. Degen, F. Reinhard, and P. Cappellaro, Reviews of modern physics 89, 035002 (2017).
  * Giovannetti  _et al._ [2011] V. Giovannetti, S. Lloyd, and L. Maccone, Nature photonics 5, 222 (2011).
  * Caro  _et al._ [2023] M. C. Caro, H.-Y. Huang, N. Ezzell, J. Gibbs, A. T. Sornborger, L. Cincio, P. J. Coles, and Z. Holmes, Nature Communications 14, 3751 (2023).
  * Li and Luo [2013] N. Li and S. Luo, Physical Review A 88, 014301 (2013).
  * Feldmann [2021] P. Feldmann,  _Generalized Quantum Phase Transitions for Quantum-State Engineering in Spinor Bose-Einstein Condensates_ , Ph.D. thesis, Gottfried Wilhelm Leibniz Universität Hannover (2021).
  * Havlíček  _et al._ [2019] V. Havlíček, A. D. Córcoles, K. Temme, A. W. Harrow, A. Kandala, J. M. Chow, and J. M. Gambetta, Nature 567, 209 (2019).
  * Knill  _et al._ [2001] E. Knill, R. Laflamme, and G. J. Milburn, Nature 409, 46 (2001).
  * Shadbolt  _et al._ [2012] P. J. Shadbolt, M. R. Verde, A. Peruzzo, A. Politi, A. Laing, M. Lobino, J. C. Matthews, M. G. Thompson, and J. L. O’Brien, Nature Photonics 6, 45 (2012).
  * Knill [2004] E. Knill, Fault-tolerant postselected quantum computation: Schemes (2004), arXiv:quant-ph/0402171 [quant-ph] .
  * Bravyi and Haah [2012] S. Bravyi and J. Haah, Physical Review A 86, 052329 (2012).
  * Danos  _et al._ [2007] V. Danos, E. Kashefi, and P. Panangaden, Journal of the ACM (JACM) 54, 8 (2007).
  * Bondarenko  _et al._ [2023] D. Bondarenko, R. Salzmann, and V.-S. Schmiesing, arXiv preprint arXiv:2301.08167 (2023).
  * Suzuki  _et al._ [2020] Y. Suzuki, H. Yano, Q. Gao, S. Uno, T. Tanaka, M. Akiyama, and N. Yamamoto, Quantum Machine Intelligence 2, 1 (2020).

##  Appendix A Generators of rotations in MBQC

Given a graph state $(G,I,O)$ with flow, we can calculate the generators of
rotations induced by the topology of $G$. By following Theorem 1 from [4], we
can obtain the generators $H$ of an MBQC ansatz, which are a subset of Pauli
group on $n$ qubits, by solving the following set of binary linear equations
at each (trainable) node $j\in O\backslash V$:

$\displaystyle\begin{split}\sum_{i\in G}\omega_{ij}S_{ik}^{(x)}&=0\quad\forall
k\leq j\\\ \sum_{i\in G}\omega_{ij}S_{ik}^{(z)}&=\delta_{kj}\quad\forall
k\end{split}$ (4)

where $\leq$ is the partial order induced by the flow $f$,
$\omega_{ij}\in\\{0,1\\}$, and

$S_{i}=\left[S_{i0}^{(x)}\cdots S_{in}^{(x)}\mid S_{i0}^{(z)}\cdots
S_{in}^{(z)}\right]$

is the binary representation of the stabilizer $K_{i}=Z_{i}\prod_{j\in
N(i)}X_{j}$. Solving for $\omega_{ij}$ in Equations 4, we obtain the
generators by restricting $\\{B_{j}=\sum_{i}\omega_{ij}S_{i}\\}_{j}$ to the
output qubits $O$, this is $H=\\{B_{j}\restriction_{O}\\}_{j}$. Thus, when
restricting measurement to the $(X,Y)$ plane, measuring qubit a qubit $j\in
V\backslash O$. Then, the rotation operator implemented when measuring a qubit
$j\in O\backslash V$ with $M^{j}_{\alpha}$ is $\exp(-i\alpha B_{j}/2)$.

A relevant example where obtaining a generator in needed is that of Property 2
in Section III. By solving Equations 4 for $j=6$ in the graph state of Figure
1b we get $B_{6}=X^{2}X^{4}Z^{6}X^{7}X^{9}$ (Figure 10). Thus, by restricting
$B_{6}$ to $O=\\{4,9\\}$, we conclude that the rotation induced by the
measurement pattern
$M_{0}^{8}M_{0}^{3}M_{0}^{7}M_{0}^{2}M_{0}^{1}M_{\varphi}^{6}M_{0}^{5}M_{0}^{0}$
is $\exp(-i\varphi X\otimes X/2)$.

Figure 10: Stabilizer $B_{6}$ of graph state from Figure 1b.

##  Appendix B Expressivity of MBQC ansatze

A common way of quantifying the expressivity of a QML model is via its Lie
algebra $\mathfrak{g}\subseteq\mathcal{P}_{n}$. This algebra is generated by a
set of generators $H$ which can be obtained as outlined in Appendix A. The set
of gates the model can implement is

$\mathbb{G}=\left\\{\prod_{j}\exp(i\theta_{j}P_{j})\mid\theta_{j}\in\mathbb{R},P_{j}\in\langle
H\rangle_{[\cdot,\cdot]}\right\\},$

where $\langle H\rangle_{[\cdot,\cdot]}$ denotes the Lie closure of $H$. We
can then calculate the Lie algebra $\mathfrak{g}$ by taking the closure of $H$
under the Lie bracket $[\cdot,\cdot]$. This quantity is not only important for
measuring the expressivity of $G_{\theta}$, but also quantify its Barren
plateaus [28]. Namely, if the Lie algebra $\mathfrak{g}$ is simple, then the
variance of the loss function is given by

$\displaystyle\mathrm{Var}[\ell(\bm{\theta})]=O\left(\frac{1}{\dim(\mathfrak{g})}\right)$
(5)

Moreover, using this method, we can easily verify that the Lie algebra of the
(fully connected) MuTA ansatz with $n$ rows, proposed in Section III, is
$\mathfrak{su}\left(2^{n}\right)$.

##  Appendix C Noise in underlying resource state

In MB-QML protocols, we are not limited to dealing with noisy data. The models
themselves can also be susceptible to noise. Here, we study the action of the
depolarizing channel, a common model of quantum noise, on the base resource.
This map is defined by

$\mathcal{N}_{dep}(\rho)=(1-p)\rho+\frac{p}{3}X\rho X+\frac{p}{3}Y\rho
Y+\frac{p}{3}Z\rho Z,$

where $p$ is the noise strength of the channel. We find from numerical
simulations (shown in Figure 11) that the model learns the accurate
measurement angles up to a quite large value of $p$.

Figure 11: Effect of a depolarizing channel over the qubits of the graph state
from Figure 1b.

This robustness presents an interesting use case: one could use two devices, a
less expensive one with a higher noise parameter ($p$) for initial training
phases due to the model’s tolerance to noise, and a more expensive, lower-
noise device for fine-tuning and inference.

##  Appendix D Quantum kernels with MBQC

We can use a graph state to design a quantum kernel. This is done by setting a
measurement pattern for a given datapoint $x$. In Figure 6, we get the map

$\displaystyle\ket{\phi(x_{i})}=R_{z1}(x_{i2})R_{z0}(x_{i1})$ $\displaystyle
e^{-i\cos(x_{i1})\cos(x_{i2})X\otimes X}$ $\displaystyle\times
R_{z1}(x_{i2})R_{z0}(x_{i1})\ket{00}.$ (6)

Experimentally, each entry of $K$ can be obtained using a swap test. This
means that to get $K(x_{i},x_{j})$ we need two graph states to prepare
$\ket{\phi(x_{i})}$ and $\ket{\phi(x_{j})}$, and get enough samples from the
overlap to estimate
$\absolutevalue{\innerproduct{\phi(x_{i})}{\phi(x_{j})}}^{2}$. This kernel is
inspired by a previous embedding studied in [42].

##  Appendix E Hardware efficient training algorithms

In Section V, we used heuristic algorithms to get the optimal measurement
angles from a discrete set of angles. In particular, those accessible in a GKP
encoding with $T$-magic state injection. The first algorithm we use is
Algorithm 1.

Algorithm 1 Layer-wise greedy search algorithm for discrete optimization of
measurement patterns.

1:function
GreedyOpt($\ell,\varepsilon,A,\text{layers},n_{\text{reset}},L_{\max},\delta$)

2: for $reset=0$ to $n_{\text{reset}}$-1 do

3: for $m=1$ to $L_{max}$ do

4: $A=\text{LayerOpt}(\ell,A,\text{layers},m,\varepsilon)$

5: if $\ell(A)<\delta$ then

6: return True, $A$

7: else

8: $A=\text{randomAngles()}$

9: return False, $A$

10:function LayerOpt($\ell,A,\text{layers},n,\varepsilon$)

11: for $i=0$ to $\text{len(layers)}-n$ do

12: $\text{merged\\_layers}=\text{concatenate(layers[i:i+n])}$

13: $A_{\text{best}}=A$

14: $\ell_{\text{best}}=\ell(A)$

15: for all $A^{\prime}\in\\{0,\pi/4,\pi/2\\}^{\text{merged\\_layers})}$ do

16: $\ell_{\text{current}}=\ell(A^{\prime})$

17: if $\ell_{\text{current}}<\ell_{\text{best}}$ or
$\text{random}(0,1)<\varepsilon$ then

18: $A_{\text{best}}=A^{\prime}$

19: $\ell_{\text{best}}=\ell_{\text{current}}$

20: return $A_{\text{best}}$

The second algorithm we used was DQN, a popular reinforcement learning
algorithm suitable for discrete state and action spaces. In this context, the
state space (or observation) includes the entire measurement pattern, along
with a node label $j$ indicating which node the agent will modify next. The
action space consists of selecting a measurement angle at $j$ from the set
${0,\pi/2,\pi/4}$. This approach helps balance exploration and exploitation,
and depending on the model’s hyperparameters, it may converge to a global or
local minimum of the loss.


# tinygarden - A java package for testing properties of spanning trees

Manuel Dubinsky<EMAIL_ADDRESS>César Massri  Gabriel Taubin
Ingeniería en Informática, Departamento de Tecnología y Administración,
Universidad Nacional de Avellaneda, Argentina  Departamento de Computación,
Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires,
Argentina  Departamento de Matemática, Universidad de CAECE, CABA, Argentina
School of Engineering, Brown University, Providence, RI, USA

###### Abstract

Spanning trees are fundamental objects in graph theory. The spanning tree set
size of an arbitrary graph can be very large. This limitation discourages its
analysis. However interesting patterns can emerge in small cases. In this
article we introduce _tinygarden_ , a java package for validating hypothesis,
testing properties and discovering patterns from the spanning tree set of an
arbitrary graph.

###### keywords:

Graphs; Spanning trees; Fundamental cycle bases

††journal: Software Impacts

##  1 Introduction

Graph theory is a longstanding and well-established area of discrete
mathematics. Graphs are abstract models of pairwise relations between entities
in some domain. A graph $G=(V,E)$ is composed of $V$ -a set of _vertices_ (or
_nodes_)- and $E$ -a set of _edges_ -. Each node is a point representing an
entity and each edge is a line connecting two nodes. For example we can model
friendship relationships in a social network by associating a node to each
person and connecting two nodes with an edge if the corresponding people are
friends.

Let $G=(V,E)$ be the following graph

Figure 1: Example of a Graph

A _subgraph_ $G^{\prime}=(V^{\prime},E^{\prime})$ is a graph such that
$V^{\prime}\subseteq V$, $E^{\prime}\subseteq E$ and such that $V^{\prime}$
contains all endpoints of the edges in $E^{\prime}$. A _path_
$p=(e_{1},\dots,e_{k})$ is a sequence of consecutive edges of $G$.

Figure 2: Example of a Path

A _cycle_ in $G$ is a non-empty path in which the only repeated nodes are the
first and last.

Figure 3: Example of a Cycle

We say that G is _connected_ if there is at least one path between each pair
of nodes. A _tree_ is a connected graph without cycles. And finally, a
_spanning tree_ $T\subseteq G$ is a tree that contains all the nodes of $G$.

Figure 4: Example of a Spanning Tree

Spanning trees are important in optimization [1], network design [2], VLSI
interconnection [3], clustering [4], complexity theory [5], graph invariants
[6], fundamental cycle bases [7] and in many more areas of applied and
theoretical sciences.

The spanning tree set of an arbitrary graph can be very large [8]. This limit
prevents the entire set from being explored. However, there are algorithms to
generate all spanning trees of a graph ([9], [10], [11]) that are suitable in
the case of small instances.

##  2 Software description

The _tinygarden_ package is a self-contained group of _java_ classes that
enables the exploration of the set of spanning trees of a given graph. It
implements _Matsui algorithm_ [11] to generate it.

The architecture is simple. The class _SpanningTreesMatsui_ organizes the
whole process. Custom descendants of two class hierarchies: _Collectors_ and
_Processors_ are invoked sequentially to process each spanning tree.
_Collectors_ are useful for global analysis of the entire set, for example,
count the number of spanning trees with a certain property. Processors, on the
other hand, are useful for local tasks, such as generating a pretty-print
version of a specific spanning tree.

The package also implements helper classes, such as _Graph_ , _SparseMatrix_ ,
_UnionFind_ , etc. Since a _Graph_ can be built based on a text file
containing its incidence matrix, it works well together with _nauty_ [12], the
well-known graph software.

##  3 Limitations and improvements

The scope of the _tinygarden_ package is restricted to specific graph theory
problems. The most important limitation is the size of the instances that can
be processed; it was conceived to explore the spanning tree set of all non-
isomorphic graphs of at most 9 nodes. Consequently, two important improvements
would be:

  * 1.

A distributed implementation of Matsui algorithm: in order to process larger
graphs.

  * 2.

Compute the spanning tree set size [13]: to process graphs with smaller size
compared to a prescribed threshold.

The first version of the package was recently made public. At the moment is
only being used by the authors.

Figure 5: Distribution of the Min FCB of the graphs of 8 nodes (left).
Aggregated relation of the Min FCB with respect to the number of edges (right)

##  4 Impact

The _tinygarden_ package is a tool for validating hypothesis, testing
properties, and discovering patterns from the spanning tree set of an
arbitrary graph. To the best of our knowledge this is the only tool with these
features.

In [14] we introduced the _mstci problem_ , the _tinygarden_ package proved to
be effective in finding a pattern related to the _intersection number_ of
complete graphs which led to its main result, and to set a solid basis for the
conjecture posed in it. It was an important tool to evaluate a metaheuristic
algorithm for graph integration [15]. We are currently using it to test an
algorithm in order to find a good solution to the _mstci problem_.

The package can be used to analyze general questions, i.e.: list the spanning
trees with minimum diameter of a graph, as well as to carry out statistical
analysis, i.e.: calculate the distribution of the graphs of a fixed number of
nodes with respect to the spanning tree with shortest total path length [5].

Based on our package, several NP-hard problems can be analyzed from a
statistical perspective, for example Fig. 5 shows the distribution of the
_Minimum Fundamental Cycle Basis_ (or _Min FCB_)[16] of 8 node graphs. This
information can be used to implement approximate or heuristic algorithms in
order to find good solutions for these problems.

## Declaration of competing interest

The authors declare that they have no known competing financial interests or
personal relationships that could have appeared to influence the work reported
in this paper.

## Acknowledgements

Prof. Massri was supported by Instituto de Investigaciones Matemáticas “Luis
A. Santaló”, UBA, CONICET, CABA, Argentina.

Prof. Taubin was partially supported by the National Science Foundation grant
number IIS-1717355.

## References

## References

  * [1] B. Wu, K. Chao, Spanning Trees and Optimization Problems, Discrete Mathematics and Its Applications, CRC Press, 2004\.
URL https://books.google.com.ar/books?id=SI82UzzyVN8C

  * [2] D. Eppstein, Chapter 9 - spanning trees and spanners, in: J.-R. Sack, J. Urrutia (Eds.), Handbook of Computational Geometry, North-Holland, Amsterdam, 2000, pp. 425–461.  doi:https://doi.org/10.1016/B978-044482537-7/50010-3.
URL https://www.sciencedirect.com/science/article/pii/B9780444825377500103

  * [3] J. Cong, L. He, C.-K. Koh, P. H. Madden, Performance optimization of VLSI interconnect layout, Integration 21 (1-2) (1996) 1–94.  doi:10.1016/s0167-9260(96)00008-9.
URL https://doi.org/10.1016/s0167-9260(96)00008-9

  * [4] L. Rokach, A survey of clustering algorithms, in: Data Mining and Knowledge Discovery Handbook, Springer US, 2009, pp. 269–298.  doi:10.1007/978-0-387-09823-4_14.
URL https://doi.org/10.1007/978-0-387-09823-4_14

  * [5] M. Garey, D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Macmillan, New York, 1979.
  * [6] W. T. Tutte, A contribution to the theory of chromatic polynomials, Canadian Journal of Mathematics 6 (1954) 80–91.  doi:10.4153/cjm-1954-010-9.
URL https://doi.org/10.4153/cjm-1954-010-9

  * [7] T. Kavitha, C. Liebchen, K. Mehlhorn, D. Michail, R. Rizzi, T. Ueckerdt, K. A. Zweig, Cycle bases in graphs characterization, algorithms, complexity, and applications, Computer Science Review 3 (4) (2009) 199–243.  doi:10.1016/j.cosrev.2009.08.001.
URL https://doi.org/10.1016/j.cosrev.2009.08.001

  * [8] A. Cayley, A theorem on trees, Quarterly Journal of Pure and Applied Mathematics 23 (1889) 376–378.
  * [9] R. C. Read, R. E. Tarjan, Bounds on backtrack algorithms for listing cycles, paths, and spanning trees, Networks 5 (3) (1975) 237–252.  doi:10.1002/net.1975.5.3.237.
URL https://doi.org/10.1002/net.1975.5.3.237

  * [10] H. N. Gabow, E. W. Myers, Finding all spanning trees of directed and undirected graphs, SIAM Journal on Computing 7 (3) (1978) 280–287.  doi:10.1137/0207024.
URL https://doi.org/10.1137/0207024

  * [11] T. Matsui, Algorithms for finding all the spanning trees in undirected graphs, Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo (1993) (1993).
URL https://www.keisu.t.u-tokyo.ac.jp/data/1993/METR93-08.pdf

  * [12] B. D. McKay, A. Piperno, Practical graph isomorphism, II, Journal of Symbolic Computation 60 (2014) 94–112.  doi:10.1016/j.jsc.2013.09.003.
URL https://doi.org/10.1016/j.jsc.2013.09.003

  * [13] G. Kirchhoff, Ueber die auflösung der gleichungen, auf welche man bei der untersuchung der linearen vertheilung galvanischer ströme geführt wird, Annalen der Physik und Chemie 148 (12) (1847) 497–508.  doi:10.1002/andp.18471481202.
URL https://doi.org/10.1002/andp.18471481202

  * [14] M. Dubinsky, C. Massri, G. Taubin, Minimum spanning tree cycle intersection problem, Discrete Applied Mathematics 294 (2021) 152–166.  doi:10.1016/j.dam.2021.01.031.
URL https://doi.org/10.1016/j.dam.2021.01.031

  * [15] Una metaheurística GRASP para integración en grafos, XV Simposio Argentino de Investigación Operativa (SIO) - JAIIO 46 (Córdoba, 2017), 2017, in Spanish.
URL http://sedici.unlp.edu.ar/handle/10915/66445

  * [16] G. P. Narsingh Deo, M. S. Krishnomoorthy, Algorithms for generating fundamental cycles in a graph, ACM Trans. Math. Software 8 (1) (1982) 26–42.

## Current code version

Nr. |  Code metadata description |  Please fill in this column
---|---|---
C1 |  Current code version |  1.0
C2 |  Permanent link to code/repository used for this code version |  https://github.com/manudubinsky/tinygarden
C3 |  Permanent link to Reproducible Capsule |  https://codeocean.com/capsule/9539109/tree/v1
C4 |  Legal Code License |  MIT
C5 |  Code versioning system used |  git
C6 |  Software code languages, tools, and services used |  java
C7 |  Compilation requirements, operating environments & dependencies |  jdk
C8 |  If available Link to developer documentation/manual |  https://github.com/manudubinsky/tinygarden/wiki
C9 |  Support email for questions |<EMAIL_ADDRESS>
Table 1: Code metadata (mandatory)