# Sub-universal variational circuits for combinatorial optimization problems

Gal Weitz  These two authors contributed equally.  Department of Physics,
University of Colorado Boulder, Boulder, CO 80309, USA  Lirandë Pira  These
two authors contributed equally.  University of Technology Sydney, Centre for
Quantum Software and Information, Ultimo NSW 2007, Australia  Chris Ferrie
University of Technology Sydney, Centre for Quantum Software and Information,
Ultimo NSW 2007, Australia  Joshua Combes  Department of Electrical, Computer
and Energy Engineering, University of Colorado Boulder, Boulder, Colorado
80309, USA

###### Abstract

Quantum variational circuits have gained significant attention due to their
applications in the quantum approximate optimization algorithm and quantum
machine learning research. This work introduces a novel class of classical
probabilistic circuits designed for generating approximate solutions to
combinatorial optimization problems constructed using two-bit stochastic
matrices. Through a numerical study, we investigate the performance of our
proposed variational circuits in solving the Max-Cut problem on various graphs
of increasing sizes. Our classical algorithm demonstrates improved performance
for several graph types to the quantum approximate optimization algorithm. Our
findings suggest that evaluating the performance of quantum variational
circuits against variational circuits with sub-universal gate sets is a
valuable benchmark for identifying areas where quantum variational circuits
can excel.

##  I Introduction

There is much interest in constructing parameterized quantum circuits as
variational ansatzes to solve mathematical problems [1]. Such circuits can
find applications in quantum chemistry, for example, using variational quantum
eigensolvers [2] or quantum machine learning [3]. This class of circuits also
includes the quantum approximate optimization algorithm (QAOA) of Farhi  _et
al._ [4], which has received significant attention. Its purpose is to
efficiently approximate the global optima of constraint satisfaction problems
(CSP) in combinatorial optimization.

A popular constraint satisfaction problem that is relevant in physics is
called Max-Cut. The solution to Max-Cut can be used to find the minimum energy
of the Ising Hamiltonian [5]. The Max-Cut problem is defined on a graph as
follows. If the vertices of a graph can take one of two labels, the objective
of Max-Cut is to maximize the number of edges with opposing labels. The
constraint comes from the topology of the graph. If we have $n$ vertices, the
optimum assignment is somewhere among the $2^{n}$ combinations. Finding the
exact minimum (or maximum) of Max-Cut is considered an NP-complete problem see
e.g. Appendix A2.2 of [6]. While there are no current algorithms (beyond brute
force searching) that guarantee an exact solution to Max-Cut, there are
classical and quantum approximation techniques that produce “good-enough”
solutions in polynomial time.

Figure 1: Perspective on the relationship between three model classes
considered in this work. Parameterized quantum circuits (PQCs) are the
paradigm that represents the largest class of parameterized quantum
algorithms. QAOA (Farhi et al. [4]) is a popular example. PAOA represents a
class of probabilistic methods that are entirely classical. The “distance”
between classical and quantum methods we consider to be in the practical sense
— i.e., do they achieve comparable performance in practice where near-term
quantum computers are expected to be used.

The simplest solution is random guessing, which would “cut” half of the edges
in the graph, on average. The fraction of the number of cut edges to the
optimal solution is known as the approximation ratio. The gold standard of
classical techniques is the Goemans-Williamson algorithm, which guarantees a
ratio of 0.8785 [7].

On the quantum side, Farhi et al. [4] proved that for a depth one ($p=1$)
quantum circuit on 3-regular, triangle-free graphs, QAOA guarantees a solution
with an approximation ratio of 0.6924. It was also shown that as
$p\rightarrow\infty$, the QAOA will always find the true optimal solution.
Recent experiments have implemented QAOA on larger numbers of qubits (see,
e.g. Refs. [8, 9, 10, 11]). However, these demonstrations solve Max-Cut on
small graphs, and the time to solution is slow relative to real-world
applications. Furthermore, the Goemans-Williamson algorithm has an almost
optimal approximation ratio and, with small modifications, can efficiently
solve problems on sparse graphs with 20 million vertices on a laptop [12].
Given these factors, one might question the relevance of using QAOA. Some
possible responses are (i) variational approaches like QAOA might process
broader applicability than the SDP relaxation, (ii) QAOA could outperform the
Goemans-Williamson algorithm on extremely large problems as it is a hardware-
based solution. This raises the question of what is the appropriate classical
protocol to compare to.

In this article, we introduce PAOA (probabilistic approximate optimization
algorithm), a classical probabilistic variational circuit inspired by QAOA,
that could be implemented as a hardware-based solution. In numerical
experiments, we have found that PAOA can achieve performance comparable, and
in some cases superior, to QAOA. The protocol we suggest provides a fairer
comparison to classical techniques than the typical approach of comparing to
random guessing. This provides a way to benchmark QAOA’s performance in a way
closer in spirit than the bound provided by the Goemans-Williamson algorithm
and other excellent approaches like that of Refs. [13, 14]. This paper intends
not to compete with the Goemans-Williamson algorithm but to provide a
compelling alternative to quantum solutions.

At the core of the PAOA protocol lies probabilistic bits or “p-bits.” These
are intermediate between standard classical bits and qubits. While qubits can
be prepared in a superposition state of “0” and “1”, p-bits can only be
prepared in classical mixtures of 0 and 1. Interestingly, p-bits can be
physically implemented using modern technology [15, 16, 17]. If these
p-circuits (probabilistic circuits) can be implemented using current
technology, yet yield similar results to that achieved using current quantum
circuits, is there a real quantum advantage? The envisioned relationship
between these classes is illustrated in Figure 1.

In Section II, we briefly review constraint satisfaction problems and Max-Cut.
In Section III, we summarize QAOA. In Section IV, we introduce a class of
classical variational circuits that can solve some constraint satisfaction
problems. We compare QAOA to our classical variational circuits numerically in
Section V. Our numerics indicate that a low-depth classical variational
algorithm has comparable performance to a quantum algorithm. We conclude with
a summary and discussion of some open questions in Section VI.

##  II Constraint satisfaction problems and Max-Cut

A constraint satisfaction problem is specified by a set of items $\\{z\\}$,
and $m$ constraints. Each constraint involves a subset of the items. The
computational task is to find a combination of items that maximize the number
of satisfied constraints. For each constraint $a\in[m]$ and each string in a
given CSP, we define,

$C_{a}(z)=\begin{cases}1&\text{if $z$ satisfies constraint a},\\\
0&\text{otherwise}\\\ \end{cases}.$ (1)

Hence, the goal is to maximize the cost function $C(z)$ over the set
$\\{z\\}$, where,

$C(z)=\sum_{a=1}^{m}C_{a}(z).$ (2)

Max-Cut is a CSP defined on a graph $G(z,E)$. We represent the set of vertices
as $n$-bit strings, i.e., $z=z_{n}z_{n-1}...z_{2}z_{1}$, and the set of edges
$\langle ij\rangle\in E$. We will consider a simple graph $G(z,E)$, and denote
the number of edges $|E|$. For each vertex $i$ we assign a label, denoted as
$z_{i}\in\\{0,1\\}$. Consequently, the $n$-bit string $z$ becomes a string of
ones and zeros of length $n$, denoted as $z\in\\{0,1\\}^{n}$. Thus there are
$2^{n}$ distinct states spanning the set $\\{0,1\\}^{n}$, each representing a
unique assignment of the vertices. The goal of Max-Cut is to find the maximum
number of edges whose vertices on each end have different labels, over the set
$\\{0,1\\}^{n}$. Equivalently we find the string $z$ that maximizes,

$C(z)=\sum_{\left\langle ij\right\rangle\in E}C_{\left\langle
ij\right\rangle}(z),$ (3)

where,

$C_{\left\langle
ij\right\rangle}(z)=\frac{1}{2}\big{(}1-(-1)^{z_{i}}(-1)^{z_{j}}\big{)}.$ (4)

###  II.1 Quantum reformulation of Max-Cut objective

The maximization of $C(z)$ corresponds to finding the maximum energy of a
Hamiltonian $C$, an operator in the $2^{n}\times 2^{n}$ dimensional Hilbert
space with basis vectors $\ket{z}\in\mathbb{C}^{n}$, defined by the following
eigenvalue equation

$C\ket{z}=C(z)\ket{z},$ (5)

where $C(z)$ is defined in Eq. 3. For a simple graph $G(z,E)$, each vertex $i$
is associated with a spin state $\ket{z_{i}}$, where $z_{i}\in\\{0,1\\}$ and
$Z_{i}\ket{z_{i}}=(-1)^{z_{i}}\ket{z_{i}}$. The state associated with the
entire graph is $\ket{z}=\otimes^{n}_{i=1}\ket{z_{i}}$ and
$Z_{i}\ket{z}=(-1)^{z_{i}}\ket{z}$ where $Z_{i}$ is identity on all spins
except the $i^{th}$ spin. The quantum representation of the cost operator of
Max-Cut is

$C=\sum_{\left\langle ij\right\rangle\in E}C_{\left\langle
ij\right\rangle},\,\,\,{\rm where}\quad C_{\left\langle
ij\right\rangle}=-\frac{1}{2}(I-Z_{i}Z_{j}).$ (6)

##  III Quantum Approximate Optimization Algorithm

Here we summarize QAOA, following Farhi  _et al._ [4] presentation. The
objective of QAOA is to find an $n$-bit string $z$ that approximately
minimizes the cost $C$. Using $C$ from Eq. (6), we define the unitary cost
operator $U(C,\gamma)$,

$U(C,\gamma)=e^{-i\gamma C}=\prod_{\left\langle jk\right\rangle\in
E}e^{-i\frac{\gamma}{2}(Z_{j}Z_{k}-I)},$ (7)

where $\gamma\in[0,2\pi)$ applies a phase to pairs of bits according to the
cost function. Now we also define the operator $B$,

$B=\sum_{k=1}^{n}X_{k},$ (8)

with $X_{k}$ being the single qubit Pauli $X$ operator operating on the qubit
corresponding to the $k^{th}$ bit in $z$. We define the “mixer” unitary
operator with $\beta\in[0,\pi)$,

$U(B,\beta)=e^{-i\beta B}=\prod_{k=1}^{n}e^{-i\beta X_{k}}.$ (9)

This unitary operator drives transitions between bit-strings within a
superimposed state [10].

QAOA involves a sequential application of $U(C,\gamma)$ and $U(B,\beta)$ to an
initially uniform superposition of computational basis states. Let
$\ket{+_{n}}:=H^{\otimes n}\ket{z}$ denote the uniform superposition of all
possible states, where $H$ is the Hadamard gate. The depth number of the
circuit, $p$, is an integer number that counts sequential applications of the
two unitaries,

$U(\boldsymbol{\gamma},\boldsymbol{\beta})=\prod_{k=1}^{p}U(B,\beta_{k})U(C,\gamma_{k}),$
(10)

with a total of $2p$ angles defined via
$\boldsymbol{\gamma}:=(\gamma_{1},...,\gamma_{p})$ and
$\boldsymbol{\beta}:=(\beta_{1},...,\beta_{p})$. Thus the state after one
application of the circuit is

$\ket{\boldsymbol{\gamma},\boldsymbol{\beta}}=U(\boldsymbol{\gamma},\boldsymbol{\beta})\ket{+_{n}},$
(11)

and the expectation of the cost operator in the final state is

$\langle
C\rangle=\bra{\boldsymbol{\gamma},\boldsymbol{\beta}}C\ket{\boldsymbol{\gamma},\boldsymbol{\beta}}.$
(12)

It is the vector of parameters $\boldsymbol{\gamma},\boldsymbol{\beta}$ that
we will optimize over.

With an initial set of parameters, we conduct a repeated measurement of the
state in Eq. (11). Each measurement will have the superposition state collapse
to one of the basis states with probability

$\Pr(z)=|\langle z|\boldsymbol{\gamma},\boldsymbol{\beta}\rangle|^{2}.$ (13)

Given the binary string $z$, we can efficiently compute the cut and record the
corresponding cost $C(z)$. Repeating this process many times we collect a
sample of costs $\\{C(z)\\}$, from which can get estimates for the expectation
in Eq. (12) and the minimum value of the sample

$C_{\min}=\min_{z}\\{C(z)\\}.$ (14)

We then define the approximation ratio,

$R=\langle C\rangle/C_{\min}\,.$ (15)

Note that, in practice, $C_{\min}$ is rarely the absolute minimum cost
achievable, as that would be the cost of the solution to the Max-Cut problem.
In most applications of such optimization procedures, $R$ is an estimate of
the “true” approximation ratio.

Once estimated, $R$ is treated as an objective function for a classical
optimization algorithm. Hence, in an iterative fashion, QAOA will initialize
the parameterized circuit with better problem-specific parameters, causing
constructive and destructive interference to states that are better and worst
for the problem respectively. After optimization the candidate optimal
solution is

$z^{*}=\mathop{\mathrm{argmin}}_{z}\\{C(z)\\}\,.$ (16)

For $p=1$ on 3-regular graphs, we are guaranteed an approximation ratio that
corresponds to $0.6924$ of the cost of the true optimal state [4]. It was also
shown in [4] that as $p$ goes to infinity, $C_{\min}$ corresponding to the
solution is achieved, and the approximation ratio converges to $1$ as the
distribution around the mean converges to the optimal cost of the problem.

##  IV Classical probabilistic variational circuits

In this section, we describe our classical probabilistic variational circuits.
We begin by summarizing Markov chains and their application in reversible
logic in Section IV.1. Then we present our variational circuit ansatz in
Section IV.2 for solving the Max-Cut problem.

Figure 2: Illustrative example of the Max-Cut algorithms for a 3-node graph
$G$ showing both QAOA and PAOA circuits. (Left) $H$ is the Hadamard gate and
$p$ is the circuit depth (see Section III for the in-depth explanation).
(Right) $R$ denotes a random initial state, and $P$ represents the
probabilistic gate ansatz we use (see Section IV.2). We assume it is possible
to run the PAOA circuit directly on the graph as SWAPs are basically free in
classical computation. Thus the SWAPs depicted are virtual but allow us to map
the linear circuit topology to the problem graph topology.

###  IV.1 Classical probabilistic circuits

Let us consider probability distributions over a classical bit, which have the
following zero entropy states,

$\ket{0}=(1,0)^{\mathsf{T}},\quad\ket{1}=(0,1)^{\mathsf{T}}.$ (17)

Although these are classical vectors, we have used Dirac notation to make a
stronger analogy with QAOA. A linear combination of these vectors is a
probabilistic-bit or p-bit,

$\ket{\psi}=(1-p)\ket{0}+p\ket{1}=(1-p,p)^{\mathsf{T}},$ (18)

where $p\in[0,1]$.

The two possible logical operations on a single p-bit are identity and NOT,
which correspond to the (Pauli) permutation matrices,

$I=\begin{bmatrix}1&0\\\ 0&1\end{bmatrix},\quad{\rm and}\quad
X=\begin{bmatrix}0&1\\\ 1&0\end{bmatrix}.$ (19)

The convex hull of these two permutations gives rise to the bit-flip channel,

$\mathcal{E}_{q}\ket{\psi}=(1-q)I\ket{\psi}+qX\ket{\psi}=\begin{bmatrix}(1-q)&q\\\
q&(1-q)\end{bmatrix}\ket{\psi}\,,$ (20)

where $q\in[0,1]$.

For $n$ p-bits, the zero entropy states are the familiar computational basis
states $|z\rangle$, $z\in\\{0,1\\}^{n}$, and the convex hull of the
permutation matrices is the set of doubly stochastic matrices [18, 19].

In general, the probability of moving from state $|j\rangle$ to state
$|i\rangle$ is denoted $P_{ij}$, which need not be equal to $P_{ji}$. Such
processes are physically motivated by e.g. the probability of an excited state
of an atom to decay to the ground state but not vice versa. A probability
transition matrix $P$ for which $P_{ij}\neq P_{ji}$ for some $i,j$ is called a
stochastic matrix. As the total probability of transitioning from state
$|j\rangle$ to any other state in $\\{0,1\\}^{n}$ is 1, a stochastic matrix
must obey

$\sum_{i=1}^{2^{n}}P_{ij}=1,$ (21)

for all $j\in\\{0,1\\}^{n}$. In what follows, we will use stochastic matrices,
rather than doubly stochastic matrices, to construct our circuit ansatz.

Since the Max-Cut problem is specified on a graph, binary strings will encode
vertices. For each edge in the graph, the possible bit-string assignments for
two vertices are $\\{0,1\\}^{2}=\\{00,01,10,11\\}$. Thus, the general two-bit
stochastic matrix describing the transitions between the states of the bits on
edge $\langle kl\rangle$ is

$\boldsymbol{p}_{\langle
kl\rangle}=\begin{bmatrix}P_{11}&P_{12}&P_{13}&P_{14}\\\
P_{21}&P_{22}&P_{23}&P_{24}\\\ P_{31}&P_{32}&P_{33}&P_{34}\\\
P_{41}&P_{42}&P_{43}&P_{44}\end{bmatrix}.$ (22)

For the task of optimization, $\boldsymbol{p}_{\langle kl\rangle}$ can be
written as a 12-dimensional vector, noting the four linear constraints imposed
by Eq. 21.

Since the state would remain a “classical” mixture, it is obvious that the
circuits created with these gates are not universal for quantum computing.
Interestingly, they are not universal for classical reversible computation
either — it is known that three-bit gates (e.g., the Fredkin or Toffoli gate)
are required to make classical reversible computing universal [20, 21].
Nevertheless, with these “sub-universal” resources, we can still solve the
Max-Cut problem with high approximation ratios.

###  IV.2 PAOA

In analogy with the parameterized quantum circuit of QAOA, here we propose a
parameterized probabilistic circuit called the related protocol PAOA. Given a
graph, a parameterized probabilistic circuit is constructed using independent
stochastic matrices that act on some subset of the vertices, see Fig. 2.
Generally, one could imagine applying one, two, and three-bit stochastic
matrices to the vertex bits and iterating over layers as in QAOA. The limiting
case would be a single $n$ bit stochastic matrix, see Eq. 21, which is like a
(classical) Boltzmann machine [22] or Ising machine [23]. However, in
designing PAOA, we have found that a simple single-depth circuit of two-bit
stochastic matrices is sufficient and this has the benefit of reducing the
dimensionality of the optimization space. Thus for all of the variants we
consider below, a depth 1 PAOA circuit creates a parameterized probability
distribution on the graph $G$ of the form

$\Pr(G|\boldsymbol{x})=\prod_{\begin{subarray}{c}\langle{kl}\rangle\in E\\\
k<l\end{subarray}}\boldsymbol{p}_{\langle
kl\rangle}(\boldsymbol{x}_{\langle{kl}\rangle})$ (23)

where $\boldsymbol{x}$ is the vector of all variational parameters for the
graph and $\boldsymbol{x}_{\langle{kl}\rangle}$ are the variational parameters
for the edge $\langle{kl}\rangle$. We will see that as our ansatz only the
distribution between two edges doing higher depth circuits doesn’t add to the
expressivity of our ansatz. Instead, we have to add different probability
distribution to vertices that don’t have edges, see Fig. 3.

Figure 3: (left) In the simple version of depth one ($p=1$) PAOA we optimize
stochastic matrices on the problem graph. To make the probability distribution
richer we have to either optimize over higher-depth circuits or more than two-
bit stochastic matrices. (right) The original problem graph is depicted in
grey. A possible second layer of PAOA is depicted with the blue edges.

In principle, we could use Eq. 22 to construct a variational ansatz for the
edges of a graph, which would involve $12$ parameters for every edge in the
graph. To reduce the number of parameters intelligibly, let’s reexamine our
objective Eq. 7. Recall the objective of Max-Cut: Find the arrangement of
vertices that maximizes the number of edges with opposing bits on each end.
Thus, we set transition probabilities to unwanted states, such as
$\ket{01}\mapsto\ket{00}$, for example, to zero. This ensures maximum
disagreement between edges.

This motivates the following variational ansatz, which forms the basis of
PAOA,

$\boldsymbol{p}_{\langle kl\rangle}^{\textsc{paoa}}=\begin{bmatrix}0&0&0&0\\\
p_{1}&p_{2}&p_{3}&p_{4}\\\ 1-p_{1}&1-p_{2}&1-p_{3}&1-p_{4}\\\
0&0&0&0\end{bmatrix}.$ (24)

The vector $\boldsymbol{p}$ only encodes four variational parameters per edge
where $p_{i}\in[0,1]$. If the number of edges in the graph is $|E|$, PAOA has
$4|E|$ parameters. This ansatz allows all of the four bitstrings between
vertices to transition to the strings $\\{01,10\\}$ with unique probabilities.

In an effort to minimize the number of optimization parameters, we also
construct Reduced PAOA, which sets all probabilities per edge to be equal,
such that each edge is associated with a gate of the following form,

$\boldsymbol{p}_{\langle
kl\rangle}^{\textsc{r-paoa}}=\begin{bmatrix}0&0&0&0\\\ p&p&p&p\\\
1-p&1-p&1-p&1-p\\\ 0&0&0&0\end{bmatrix},$ (25)

which amounts to $|E|$ parameters in total. Notice that if we multiply two of
these stochastic matrices that
$\boldsymbol{p}^{\prime}\times\boldsymbol{p}=\boldsymbol{p}^{\prime}$, so, in
this case, larger depth circuits don’t add expressivity to our anzatz.

The objective of the PAOA is to replicate QAOA classically (Figure 2 provides
an example of solution circuits using both methods). Given a graph, a
parameterized probabilistic circuit is constructed using independent
stochastic matrices for each edge. As one last ansatz, we define Min PAOA,
which is parameterized as follows,

$\boldsymbol{p}_{\langle kl\rangle}^{\textsc{min-
paoa}}=\begin{bmatrix}0&0&0&0\\\ p&q&1-q&1-p\\\ 1-p&1-q&q&p\\\
0&0&0&0\end{bmatrix}$ (26)

which has the same two parameters for every edge. Like QAOA, we allow this
circuit to have multiple layers with different parameters. The form of this
ansatz is chosen so that the transitions $\ket{00}\Leftrightarrow\ket{01}$ and
$\ket{11}\Leftrightarrow\ket{10}$ are controlled by $p$, while
$\ket{01}\Leftrightarrow\ket{10}$ are parameterized by $q$. Both Min PAOA and
standard QAOA use $2p$ parameters.

Once the parameterized probabilistic circuit is defined, we follow the same
protocol as in the QAOA. Namely, we conduct a sequence of experiments where
the output of an experiment is the approximation ratio as defined in Eq. (15).
After each experiment, an optimizer attempts to improve the choice of
parameters such that the approximation ratio for the next experiment is larger
than the previous one. We will discuss the details of our numerical
experiments next.

##  V Numerical experiments

In this section, we present numerical evidence for the effectiveness of PAOA
on several graphs, see Fig. 4. We start by considering small 3 regular graphs
with up to 10 edges and comparing the performance of QAOA to PAOA and show
PAOA’s performance is better than QAOA.

As numerical simulations of large quantum systems are difficult we then switch
tact and simulate larger graphs. We consider several graph types an compare
the performance of QAOA to PAOA on a graph with 20 edges. Then we consider the
scaling of the performance of PAOA to random guessing for graphs with 50 to
250 edges. For each considered graph, we run each Max-Cut optimization
algorithm 100 times. The average and standard deviation of the cut sizes as
well as the estimated approximation ratio will form the basis of our
conclusions.

For the fairest comparison, an “out of the box” optimizer [24] was used to
train the QAOA and PAOA circuits. Each was given 100 iterations and 100
experimental runs per iteration. In no cases were the optimization algorithm’s
hyperparameters tuned (the defaults were used). The QAOA circuit was built and
simulated using Qiskit [25]. The code to reproduce these results can be found
at [26].

$2$-regular graph

$3$-regular graph

Complete graph

Barabasi-Albert graph

Erdos-Renyi graph

Figure 4:  We consider running QAOA and variants of PAOA on these graphs to
solve Max-Cut.

###  V.1 Performance as a function of graphs size for 3-regular graphs

Regular, or $k$-regular graphs are those where each node has an equal ($k$)
number of edges. For $k=0$, there are no edges. For $k=1$, the graph consists
of disjoint pairs of nodes connected by a single edge so the cut is trivial.
Here we will consider 3-regular graphs.

Figure 5 is a comparative analysis of the variants of PAOA, QAOA, random
guessing, and brute force methods for Max-Cut on 3-regular graphs of
increasing size. Specifically we consider graphs with $|V|\in\\{4,6,8,10\\}$
where the number of corresponding 3-regular graphs are $\\{1,2,6,21\\}$ [27,
A005638]. We run the different protocols on all possible graphs of size $|V|$
and average the results.

We compare several protocols and several performance metrics as a function of
graph size. The x-axis represents graph size, i.e. the order or number of
vertices $|V|$, and the y-axis showcases the performance metrics. Across the
graph sizes, PAOA consistently outperforms other methods, with the exception
of Best Cut which the brute force method obviously is the most performant.
Moreover, PAOA’s narrower distribution, denoted by a smaller standard
deviation in Figure (b), indicates its consistent and reliable performance.
The fact that all methods get close to the brute force method with respect to
the best cut is not surprising as the graphs are small and our optimizer gets
100 shots. This also explains why the approximation ratios also look good. For
this reason, we will study larger graphs in the latter part of this section.

Notice that we did not include the original PAOA ansatz, see Eq. 24, this is
because it’s performance is worse than “Reduced PAOA” and “Min. PAOA” which
are Eqs. 25 and 26 respectively. We conjecture this is because of the curse of
dimensionality in the original PAOA which has $4|E|$. While Reduced and Min.
PAOA have parameters vs $|E|$ and $2$ parameters for each layer.

Figure 5: A Comparison of the different protocols to solve Max-Cut on
3-regular graphs of increasing graph size i.e. $|V|$. For each graph of size
$|V|$ the protocols were given 100 iterations and 100 experimental runs per
iteration. If there is more than one graph for a given size $|V|$ we average
the performance metrics.

###  V.2 Larger $2$ and $3$-regular graphs

In this section, we will focus on comparing the performance of QAOA and PAOA
for larger graphs when $k=2$ or $k=3$. The maximum cut is trivial for $k=2$,
where the graph (if fully connected) is a cycle. The maximum cut is clearly
$n$, where $n$ is the (even) number of nodes. However, this example provides
an interesting test case as we will soon see. We have also considered $k=3$,
where the solution is non-trivial. The two example graphs corresponding to the
data collected below are shown here.

Table 1: 2-regular graph performance $(n=20)$ Method | Best | Average | SD | $R$
---|---|---|---|---
Brute force | 20 | 10.00 | 2.24 | 0.50
Random | 16 | 10.16 | 2.34 | 0.64
PAOA | 18 | 14.58 | 1.53 | 0.81
Reduced PAOA | 18 | 16.72 | 1.54 | 0.93
Min PAOA (1 layer) | 18 | 16.22 | 1.10 | 0.90
Min PAOA (3 layers) | 16 | 11.24 | 2.17 | 0.70
QAOA (1 layer) | 16 | 10.76 | 1.97 | 0.67
QAOA (3 layers) | 16 | 11.12 | 1.95 | 0.69
QAOA (6 layers) | 14 | 10.22 | 2.00 | 0.73

Table 1 compares the performance for the algorithms on a 2-regular graph with
$n=20$ nodes for several performance metrics. As the algorithms are
probabilistic and run several times, outcomes are distributed. Thus we
consider the following metrics to explore performance. The first metric we
consider is the best cut found by the algorithm in any trial; we call this
metric “Best.” The metrics “Average” and “SD” refer to the average cut of the
distribution and the standard deviation of the distribution. Finally, “R” is
the approximation ratio given in Eq. (15).

Surprisingly, this very simple graph seems to present a relative challenge for
all algorithms — except, of course, the brute force algorithm, which will
always yield the optimal cut. However, since it is searching over every
possible cut, its performance on the other metrics is quite low. According to
the approximation ratio cost function, Reduced PAOA is the best performer.
However, a single layer of Min PAOA does quite well and is more “reliable”
based on the standard deviation of the cut sizes it produces. QAOA and larger
depth circuits seem to struggle with the chosen meta-heuristics.

Table 2: 3-regular graph performance $(n=20)$ Method | Best | Average | SD | $R$
---|---|---|---|---
Brute force | 26 | 15.00 | 2.74 | 0.58
Random | 24 | 15.02 | 2.72 | 0.63
PAOA | 24 | 19.26 | 2.28 | 0.80
Reduced PAOA | 26 | 21.35 | 2.54 | 0.82
Min PAOA | 26 | 21.66 | 2.39 | 0.83
Min PAOA (3 layers) | 22 | 15.99 | 2.30 | 0.73
QAOA (1 layer) | 25 | 17.62 | 2.32 | 0.70
QAOA (3 layers) | 24 | 17.75 | 2.81 | 0.74
QAOA (6 layers) | 22 | 15.38 | 2.68 | 0.70

In Table 2, the performance for a 3-regular graph with $n=20$ nodes is
presented. In this case, both of the reduced parameter variants of PAOA find
the solution with similar approximation ratios. While the approximation ratio
of QAOA is better than random guessing, the standard deviation at deeper
circuits is higher than PAOA.

Over the course of many trials and observations not presented here, we note
that either Min PAOA or Reduced PAOA are the best-performing algorithms for
both $k=2$ and $k=3$ regular graphs. In either case, the number of gates (and
hence the runtime) grows linearly with the number of nodes.

Since QAOA was simulated classically, its space/time complexity was
exponential in the number of graph edges — thus, we were limited to the range
below roughly 20 graph nodes. On the other hand, PAOA scales linearly with the
number of edges. Since, as we will see in the following sections, Reduced PAOA
is the best-performing algorithm, we tested its performance well-beyond the 20
qubit limit. The results, summarized in Figure 6, show that PAOA continues to
outperform random guessing as the graph size increases.

Figure 6: A Comparison of Reduced PAOA and random guessing to solve max cut on
2-regular graphs of increasing size. (Top) Is a comparison of the
approximation ratios, and (bottom) is the maximum cut normalized to the size
of the graph i.e. (the best cut)$/|V|$. Each algorithm was run 10 times on a
2-regular graph. All data are presented along with the average (line).

###  V.3 Complete graphs

A complete graph is one in which every pair of nodes is connected by an edge,
see Fig. 4. By symmetry, any cut which equally partitions an even number of
nodes will be maximum. This was not difficult to find for any of the
algorithms we considered. Note, however, that variational algorithms have
runtimes that scale with the number of edges in a graph. While we did not
intentionally benchmark the timing of each algorithm, complete graphs were
certainly the most time-consuming to optimize.

The performance results of each algorithm on a complete graph with $n=10$
nodes are presented in Table 3. Surprisingly, Min PAOA is nearly perfect,
finding a set of variational parameters which produce a maximum cut
deterministically, for all practical purposes. The other variants of PAOA also
performed extremely well.

Table 3: Complete graph performance $(n=10)$ Method | Best | Average | SD | $R$
---|---|---|---|---
Brute force | 25 | 22.50 | 3.35 | 0.90
Random | 25 | 22.74 | 3.86 | 0.91
PAOA | 25 | 24.14 | 1.30 | 0.97
Reduced PAOA | 25 | 24.52 | 0.92 | 0.98
Min PAOA (1 layer) | 25 | 24.99 | 0.10 | 1.00
Min PAOA (3 layers) | 25 | 20.03 | 5.11 | 0.80
QAOA (1 layer) | 25 | 22.13 | 4.07 | 0.89
QAOA (3 layers) | 25 | 14.82 | 8.52 | 0.59
QAOA (6 layers) | 25 | 19.82 | 7.39 | 0.79

###  V.4 Other random graphs

Lastly, we assessed the performance of the algorithms on some other popular
random graphs from network theory. First, the Barabasi-Albert model is a
technique for generating “scale-free” networks that mimic human-made networks
such as the Internet. It uses a mechanism called preferential attachment
whereby new nodes are added to the graph with connections to existing nodes
that exist probabilistically, weighted by how many connections each node
currently has. The graph in Fig. 4 the left was created starting with two
connected nodes.

An Erdos-Renyi graph is one where each potential edge is added with some fixed
and independent probability $p$. Here, and in Fig. 4, we have chosen
$p=\frac{1}{2}$, which you can intuit as a complete graph with roughly half
the edges removed.

In Table 4, the performance of the algorithms is presented for a Barabasi-
Albert graph on $n=20$ nodes. In this case, Reduced PAOA is a clear winner
with the other variants of PAOA falling slightly behind on all metrics. Again,
QAOA seems to struggle using the same meta-heuristics.

Table 4: Barabasi-Albert graph performance $(n=20)$ Method | Best | Average | SD | $R$
---|---|---|---|---
Brute force | 29 | 18.00 | 3.00 | 0.62
Random | 27 | 18.39 | 3.04 | 0.68
PAOA | 26 | 22.68 | 2.22 | 0.87
Reduced PAOA | 28 | 24.91 | 2.04 | 0.89
Min PAOA (1 layer) | 28 | 22.26 | 2.61 | 0.80
Min PAOA (3 layers) | 27 | 21.69 | 3.03 | 0.80
QAOA (1 layer) | 23 | 18.59 | 2.41 | 0.81
QAOA (3 layers) | 26 | 18.79 | 2.70 | 0.72
QAOA (6 layers) | 27 | 19.22 | 3.01 | 0.71

The last detailed comparison appears in Table 5, where the performance of all
algorithms is shown for an Erdos-Renyi graph on $n=20$ nodes. The results bear
a resemblance to the complete graph, whereby all algorithms achieve a
reasonably high approximation ratio. However, Reduced PAOA appears to be the
most reliable, though it did not find the absolute optimal solution.

Table 5: Erdos-Renyi graph performance $(n=20)$ Method | Best | Average | SD | $R$
---|---|---|---|---
Brute force | 61 | 44.00 | 4.69 | 0.72
Random | 53 | 43.32 | 4.36 | 0.82
PAOA | 61 | 48.99 | 4.87 | 0.80
Reduced PAOA | 57 | 50.04 | 3.44 | 0.88
Min PAOA (1 layer) | 55 | 45.81 | 3.53 | 0.83
Min PAOA (3 layers) | 55 | 44.07 | 5.03 | 0.80
QAOA (1 layer) | 52 | 44.39 | 3.91 | 0.85
QAOA (3 layers) | 53 | 44.77 | 4.93 | 0.84
QAOA (6 layers) | 52 | 43.88 | 4.67 | 0.84

As in Figure 6 from Section V.2, we test the continued performance of PAOA on
much larger graphs. In Figure 7, the results again demonstrate a reliable
improvement over random guessing on a different class of random graphs.

Figure 7: A Comparison of Reduced PAOA and random guessing to solve max cut on
Barabasi-Albert graphs of increasing size. Each algorithm was run 10 times on
a Barabasi-Albert graph with a single initial node. All data are presented
along with the average (line).

##  VI Discussion

In this work, we have introduced the idea of using sub-universal variational
circuits to compare with quantum variational circuits. We explored a single-
layer circuit composed of variational stochastic matrices, which can be
physically realized. Numerical experiments have demonstrated that the ansatz
we have called PAOA is preferred to QAOA, its quantum analog. Though, the
following caveats apply.

First, and most obvious, is the limited scope available to test quantum
algorithms with classical simulators. It would be difficult to justify the
extrapolation to practically relevant sized problems from such small qubit
numbers. Second, PAOA and QAOA were trained using the same algorithm — in
other words, neither was optimized. The effect of this can be evidenced in
some data not presented here for very small graphs. (The reader is encouraged
to play with the simulations themselves at [26]). On small graphs, QAOA (as
trained here) performs equally well as PAOA — it is only on larger graphs that
it struggles. We expect QAOA to perform better when its classical optimizer is
optimized. That being said, PAOA might also improve its performance with
hyperparameter tuning.

The striking thing we have found is that PAOA works well “out of the box.” It
is fast, convenient, and produces high-quality results with no tuning. If PAOA
can be implemented directly in hardware (as in [16], for example) and used to
find solutions to CSPs in a cost-effective manner, it would impose a
significant opposition to justifying investment in some quantum alternatives.
In particular, the Reduced PAOA ansatz has good performance on a variety of
graphs. Based on the strong performance of Reduced PAOA on all the graphs
considered, we conjecture that this improved performance is due to it finding
the sweet spot where it has enough parameters to compute the cut but not too
many to burden the optimizer. Moreover, as our ansatz is local, it would be
interesting to prove if quantum methods have an advantage over classical as in
Ref. [28].

Beyond the particular case we have solved, one could imagine benchmarking
quantum machine learning protocols that have quantum inputs and quantum
outputs in a similar fashion. In particular, one could construct parametric
circuits out of other non-universal gate sets like (discrete) Cliffords [29,
30] or Match gates [31]. As the Match gates are continuously parameterized, it
is easy to imagine using gradient descent type optimization, but the Cliffords
could be optimized over genetic algorithms, for example.

In any case, we hope PAOA can provide a useful benchmark for testing
parameterized quantum circuits in the future. While random guessing can
provide a theoretical lower bound, PAOA serves as a practical performance
gauge in numerical experiments.

Acknowledgments: The authors acknowledge helpful discussions with Charlie
Carlson, Stuart Hadfield, Zackary Jorquera, Alexandra Kolla, Steven Kordonowy,
Laurent Laborde, Nicholas Rubin, and Andrew Sornborger. LP was supported by
the Sydney Quantum Academy, Sydney, NSW, Australia.

## References

  * Cerezo  _et al._ [2021] M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, and P. J. Coles, Variational quantum algorithms, Nature Reviews Physics 3, 625 (2021).
  * Peruzzo  _et al._ [2014] A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’Brien, A variational eigenvalue solver on a photonic quantum processor, Nature Communications 5, 4213 (2014).
  * Bilkis  _et al._ [2022] M. Bilkis, M. Cerezo, G. Verdon, P. J. Coles, and L. Cincio, A semi-agnostic ansatz with variable structure for quantum machine learning, arXiv:2103.06712 [quant-ph, stat] (2022), arXiv: 2103.06712.
  * Farhi  _et al._ [2014] E. Farhi, J. Goldstone, and S. Gutmann, A quantum approximate optimization algorithm, arXiv: 1411.4028 (2014).
  * Mohseni  _et al._ [2022] N. Mohseni, P. L. McMahon, and T. Byrnes, Ising machines as hardware solvers of combinatorial optimization problems, Nature Reviews Physics 4, 363 (2022).
  * Garey and Johnson [1979] M. R. Garey and D. S. Johnson, Computers and intractability: A guide to the theory of np-completeness, W. H. Freeman and Company (1979).
  * Goemans and Williamson [1995] M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM 42, 1115–1145 (1995).
  * Otterbach  _et al._ [2017] J. S. Otterbach, R. Manenti, N. Alidoust, A. Bestwick, M. Block, B. Bloom, S. Caldwell, N. Didier, E. S. Fried, S. Hong, P. Karalekas, C. B. Osborn, A. Papageorge, E. C. Peterson, G. Prawiroatmodjo, N. Rubin, C. A. Ryan, D. Scarabelli, M. Scheer, E. A. Sete, P. Sivarajah, R. S. Smith, A. Staley, N. Tezak, W. J. Zeng, A. Hudson, B. R. Johnson, M. Reagor, M. P. da Silva, and C. Rigetti, Unsupervised Machine Learning on a Hybrid Quantum Computer (2017), arXiv:1712.05771 [quant-ph].
  * Pagano  _et al._ [2020] G. Pagano, A. Bapat, P. Becker, K. S. Collins, A. De, P. W. Hess, H. B. Kaplan, A. Kyprianidis, W. L. Tan, C. Baldwin, L. T. Brady, A. Deshpande, F. Liu, S. Jordan, A. V. Gorshkov, and C. Monroe, Quantum approximate optimization of the long-range ising model with a trapped-ion quantum simulator, Proceedings of the National Academy of Sciences 117, 25396 (2020).
  * Harrigan  _et al._ [2021] M. P. Harrigan, K. J. Sung, M. Neeley, K. J. Satzinger, F. Arute, K. Arya, J. Atalaya, J. C. Bardin, R. Barends, S. Boixo, and et al., Quantum approximate optimization of non-planar graph problems on a planar superconducting processor, Nature Physics 17, 332–336 (2021).
  * Ebadi  _et al._ [2022] S. Ebadi, A. Keesling, M. Cain, T. T. Wang, H. Levine, D. Bluvstein, G. Semeghini, A. Omran, J.-G. Liu, R. Samajdar, X.-Z. Luo, B. Nash, X. Gao, B. Barak, E. Farhi, S. Sachdev, N. Gemelke, L. Zhou, S. Choi, H. Pichler, S.-T. Wang, M. Greiner, V. Vuletić, and M. D. Lukin, Quantum optimization of maximum independent set using rydberg atom arrays, Science 376, 1209 (2022).
  * Yurtsever  _et al._ [2021] A. Yurtsever, J. A. Tropp, O. Fercoq, M. Udell, and V. Cevher, Scalable semidefinite programming, SIAM Journal on Mathematics of Data Science 3, 171 (2021).
  * Hastings [2019] M. B. Hastings, Classical and Quantum Bounded Depth Approximation Algorithms, arXiv:1905.07047 [quant-ph] (2019), arXiv: 1905.07047.
  * Bapat and Jordan [2021] A. Bapat and S. P. Jordan, Approximate optimization of the maxcut problem with a local spin algorithm, Phys. Rev. A 103, 052413 (2021).
  * Camsari  _et al._ [2017] K. Y. Camsari, R. Faria, B. M. Sutton, and S. Datta, Stochastic $p$-bits for invertible logic, Phys. Rev. X 7, 031014 (2017).
  * Camsari  _et al._ [2019a] K. Y. Camsari, B. M. Sutton, and S. Datta, p-bits for probabilistic spin logic, Applied Physics Reviews 6, 011305 (2019a).
  * Camsari  _et al._ [2019b] K. Y. Camsari, S. Chowdhury, and S. Datta, Scalable emulation of sign-problem–free hamiltonians with room-temperature p-bits, Physical Review Applied 12 (2019b).
  * Bhatia [2013] R. Bhatia,  _Matrix analysis_ , Vol. 169 (Springer Science & Business Media, 2013).
  * Marshall  _et al._ [1979] A. W. Marshall, I. Olkin, and B. C. Arnold,  _Inequalities: theory of majorization and its applications_ (Springer, 1979).
  * Toffoli [1980a] T. Toffoli,  _Reversible computing_ , Tech. Rep. TM-151 (MIT Laboratory for Computer Science, 1980).
  * Toffoli [1980b] T. Toffoli, Reversible computing, in  _Automata, Languages and Programming_ , edited by J. de Bakker and J. van Leeuwen (Springer Berlin Heidelberg, Berlin, Heidelberg, 1980) pp. 632–644.
  * Korst and Aarts [1989] J. H. Korst and E. H. Aarts, Combinatorial optimization on a boltzmann machine, Journal of Parallel and Distributed Computing 6, 331 (1989).
  * Haribara  _et al._ [2016] Y. Haribara, S. Utsunomiya, and Y. Yamamoto, A coherent ising machine for max-cut problems: performance evaluation against semidefinite programming and simulated annealing, Principles and Methods of Quantum Information Technologies , 251 (2016).
  * PyPI [2013] PyPI, spsa: Simultaneous perturbation stochastic approximation (2013), accessed on May 1, 2023.
  * IBM [2021] IBM, Qiskit: An Open-Source Framework for Quantum Computing (2021), accessed on May 1, 2023.
  * Weitz  _et al._ [2023] G. Weitz, L. Pira, C. Ferrie, and J. Combes, PAOA simulations, https://github.com/lirandepira/paoa-simulations (2023), accessed on August 29, 2023.
  * OEIS Foundation Inc. [2023] OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences (2023), published electronically at https://oeis.org/A005638.
  * Carlson  _et al._ [2023] C. Carlson, Z. Jorquera, A. Kolla, and S. Kordonowy, A quantum advantage over classical for local max cut, arXiv 10.48550/arXiv.2304.08420 (2023), arXiv:2304.08420 [quant-ph].
  * Gottesman [1998] D. Gottesman, The heisenberg representation of quantum computers, Proc. XXII International Colloquium on Group Theoretical Methods in Physics, 1998 , 32 (1998).
  * Koh [2017] D. E. Koh, Further extensions of clifford circuits and their classical simulation complexities, Quantum Information and Computation 17, 0262 (2017).
  * Brod [2016] D. J. Brod, Efficient classical simulation of matchgate circuits with generalized inputs and measurements, Phys. Rev. A 93, 062332 (2016).


# Skeet: Towards a Lightweight Serverless Framework Supporting Modern AI-
Driven App Development

Kawasaki Fumitake1, Shota Kishi1 and James Neve1
1ELSOUL LABO B.V., Netherlands, Amsterdam
{f.kawasaki<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

The field of web and mobile software frameworks is relatively mature, with a
large variety of tools in different languages that facilitate traditional app
development where data in a relational database is displayed and modified. Our
position is that many current frameworks became popular during single server
deployment of MVC architecture apps, and do not facilitate modern aspects of
app development such as cloud computing and the incorporation of emerging
technologies such as AI. We present a novel framework which accomplishes these
purposes, Skeet, which was recently released to general use, alongside an
initial evaluation. Skeet provides an app structure that reflects current
trends in architecture, and tool suites that allow developers with minimal
knowledge of AI internals to easily incorporate such technologies into their
apps and deploy them.

##  1 INTRODUCTION

The use of artificial intelligence (AI)-based technologies has rapidly
expanded in recent years [Makridakis, 2017]. Where AI was previously a useful
but relatively niche technology used for extracting information from large
datasets, it has recently been more broadly incorporated into a variety of
existing technologies, from self-driving cars [Badue et al., 2021] to
healthcare [Hamet and Tremblay, 2017]. The technology is also easier for non-
specialist software developers to access, with companies such as Google
offering pre-trained models via Google Cloud Platform (GCP) which allow the
incorporation of AI-driven technologies without requiring specific knowledge
of model internals or training methodologies.

In particular, the incorporation of AI systems into standard web app
development is becoming increasingly universal. For example, many companies
incorporate chatbot technologies pioneered by services such as
ChatGPT111https://chat.openai.com/ into their websites in order to assist
users interactively [Adamopoulou and Moussiades, 2020]. Recent rapid
developments in Large Langauge Model (LLM) technology have allowed AI-driven
chatbots to communicate more naturally and become useful components of app
development [Brown et al., 2020]. Methods of communication involving customer
service representatives are typically frustrating for users [Parasuraman et
al., 1991], either often requiring long waiting periods on the phone or for an
email response. Chatbots trained in specific domain knowledge can help reduce
the volume of communication with human customer service representatives by
providing more specific advice than an FAQ page in a format tailored to the
user’s own knowledge, communication style and language [Nicolescu and
Tudorache, 2022].

Traditional software frameworks are not usually equipped to facilitate
development of AI-driven web apps. Since the advent and popularity of Ruby on
Rails222https://rubyonrails.org/, many frameworks in different languages have
followed its example in adopting Model-View-Controller (MVC) paradigm of
software development as the base of the framework [Laaziri et al., 2019], with
the assumption that models are classes that form a 1-to-1 relationship with
relational database tables; controllers orchestrate data retrieval of objects
derived from one or more models; and views display this data to users. This
paradigm has been an effective method of software development for many years,
being both flexible enough to support a wide variety of software apps, and
rigid enough that it is easy for developers to quickly understand, edit and
test code. Unfortunately, this paradigm is often not well suited to developing
AI-driven web apps. These usually depend on faster read/write operations from
data sources such as NoSQL databases [Han et al., 2011] or even data
warehouses such as BigQuery333https://cloud.google.com/bigquery, which are not
always easy to conform to the MVC convention of exact correspondence between a
model and a relational database table. AI-driven apps also often depend on
cloud infrastructure, communicating with hosted machine learning resources.
Third party libraries can alleviate some of these frustrations, but after a
certain point considering alternative paradigms becomes appropriate.

In this paper, we present a novel lightweight
Typescript444https://www.typescriptlang.org/ framework called
Skeet555https://github.com/elsoul/skeet-cli, which solves these problems.
Skeet is based on development according to Domain-Driven Design [Evans, 2004]
philosophies: it encourages developers to split their code into domains which
are independent in terms of business logic, and provides them with facilities
for cloud deployment with support for multiple datasources, including
relational and NoSQL database reads and writes. It also incorporates a
command-line interface (CLI) suite which helps developers include popular pre-
trained models such as those from Vertex AI666https://cloud.google.com/vertex-
ai in their apps without requiring specific domain knowledge. As of January
$2024$, the framework is increasing in popularity, with $562$ Stars on Github
and having been used in a number of small projects.

The novel contributions made by this paper are as follows:

  1. 1.

We present design goals for a modern framework that represent the needs of
people whose development goals are misaligned with current popular frameworks,
which natively facilitates the incorporation of AI and cloud services.

  2. 2.

We present the architecture of a novel app framework, Skeet, including user-
friendly documentation, which aims to solve these design goals.

  3. 3.

An initial implementation of this software framework is evaluated using survey
data collected from users who are experienced in traditional software
frameworks, and have attempted app development with Skeet.

##  2 VISION AND DESIGN GOALS

This section provides an overview of the original motivations and design goals
for Skeet. It contains a review of the state of the art of software frameworks
including definition of terminology, the vision for a modern software
framework Skeet, and a set of concrete design principles that guided Skeet’s
development.

###  2.1 Web Frameworks

This section describes web frameworks conceptually and provides definitions of
terminology used throughout this paper.

Web frameworks are suites of tools that facilitate the development of a web
app. Frameworks generally anticipate that an app will use a particular
development paradigm (for example MVC) and provide specific tools and commands
around this. For example, these tools often include:

  * •

Database management systems, commonly migrations which allow reversible step-
by-step database construction in different environments.

  * •

Object-relational Mapping (ORM) libraries to facilitate communication with
data stores using code.

  * •

Automatic code and test generation via a Command Line Interface (CLI) suite
for common tasks.

  * •

Routing libraries to connect specific subdomains to executable functions which
return HTML or formatted data such as JSON.

Existing frameworks are in practice classified along a scale of lightweight to
heavyweight. Lightweight frameworks are minimalist, providing tools to create
an app while allowing the developer to retain relative freedom of architecture
design. An example of a lightweight framework in Ruby is
Sinatra777https://github.com/sinatra/sinatra, which provides minimal tools
such as routing. A heavyweight framework often defines the structure of the
app, and uses assumptions about the developer’s use of this structure to
provide more detailed tools and commands. For example, Ruby on Rails extends
its tool suite to security, boilerplate code and test generation and data
extraction.

The framework examples above are used to solve the general problem of
constructing a web app. In the absence of terminology, this paper defines them
as generalist frameworks. In contrast, specialist frameworks attempt to solve
a problem in a more specific domain. For example, e-commerce in the context of
the Semantic Web [Li and Horrocks, 2003] or medical image processing [Tournier
et al., 2019].

###  2.2 The Vision

This section describes the original motivations for the development of Skeet,
which were threefold:

  1. 1.

Services such as ChatGPT and Vertex AI have been rising in popularity as a
result of developments in machine learning algorithms and advances in cloud
computing that have made training large scale models more accessible. Using
these models as a base, construction of specific chatbots has become more
accessible to a wide variety of developers. It would be particularly useful
for individual developers to be able to rapidly construct chatbots from their
company’s data (for example, customer service communications data from an
e-commerce app). A framework is needed which facilitates this through a simple
CLI.

  2. 2.

There has recently been an expansion in popularity of using strongly typed
languages which compile into Javascript to write front-end and back-end code.
For example, Scala.js888https://www.scala-js.org/ and Dart999https://dart.dev/
allow the compilation of their respective languages into Javascript. This
facilitates communication between front-end and back-end developers, which has
traditionally been a pain point in organisations where the two departments may
struggle with scheduling due to lack of understanding of the other’s
development processes. We consider that Typescript has been popular for a long
time as the base for front-end frameworks such as
AngularJS101010https://angularjs.org/ and React111111https://react.dev/, and
is also suitable as a back-end language. Skeet is intended to provide a tool
suite for both back- and front-end developers to use Typescript for their
development, and thus reduce the intra-organisational communication burden.

  3. 3.

Skeet’s serverless architecture should allow developers to quickly set up
infrastructure without in-depth knowledge and support scalability. Traditional
development approaches often require upfront design considerations for load
balancing and resource allocation, which not only lead to higher design and
fixed infrastructure costs but also limit the application’s ability to scale
efficiently. The serverless model is designed to automatically adjust to
varying loads, enabling not just rapid but also scalable product development.
This adaptability ensures that service owners pay according to resource usage,
effectively solving longstanding issues related to infrastructure knowledge,
management and cost.

###  2.3 Design Goals

This section describes concrete design goals of Skeet, which were distilled
from the three overarching motivations described in section 2.2. As a
framework, Skeet should:

  1. 1.

Allow full-stack or backend developers to create apps based on AI chatbots
with minimal machine learning expertise. It should have a command line
interface that allows for the implementation and fine tuning of various models
with relatively little direct coding on the part of the developer themselves,
allowing them to focus on preparing the data and building the back end and
front end around the chatbot.

  2. 2.

Be a lightweight framework. While little machine learning expertise is
assumed, we consider that a wide variety of apps can be built around chatbots,
and therefore the framework should not place unnecessary restrictions on the
developer. Skeet does allow and indeed facilitates the use of a user’s choice
of front-end framework such as React in addition, in order to shape design
code.

  3. 3.

Support cloud infrastructure. Chatbots and other AI services are often
processor- and memory-intensive technologies that require cloud computing for
training and prediction. Skeet provides a suite of tools for connecting to
popular chatbot APIs such as ChatGPT and Vertex AI, fine tuning models and for
deploying AI-driven apps directly on Google Cloud Platform.

  4. 4.

Facilitate communication between back-end and front-end developers by reducing
the burden of the language barrier. Skeet assumes a back end written in
Typescript, which is by far the most popular front-end language thanks to
frameworks such as React, and therefore improves understanding of back-end
technologies by front-end developers including AI-related components.

  5. 5.

Leverage Serverless Architecture for Scalability and Cost-Efficiency. Skeet’s
serverless framework eliminates the need for upfront infrastructure design,
thereby reducing both time and cost. This serverless model inherently supports
scalability, automatically adjusting to varying loads without requiring manual
intervention. This not only enables rapid and scalable product development but
also allows for a pay-as-you-go approach to resource usage. The serverless
architecture makes it feasible for small teams or even individual developers
to build and scale applications without the complexities of traditional
infrastructure management.

##  3 Framework Design

This section introduces the architecture of the Skeet framework. It describes
how the concepts introduced in the previous sections are used in terms of
concrete implementation.

###  3.1 Cloud Infrastructure Architecture

Figure 1: An overview of the Skeet infrastructure architecture.

Figure 1 shows the overall structure of the Skeet infrastructure architecture.
As outlined in Section 1, the framework is designed around the assumption that
GCP will be used for infrastructure, which allows communication between the
backend and infrastructure to be handled by the framework code and CLI
commands, simplifying the process for users and especially developers who are
specialised in coding but less so in infrastructure design.

The architecture assumes a general use app which requires a front end, back
end and data storage. The overall architecture is designed with the suggested
best practices of Statelessness and
Immutability121212https://cloud.google.com/architecture/best-practices-for-
operating-containers#immutability.

The architecture incorporates appropriate data storage, with structured data
in a Cloud SQL instance, unstructured data accessible directly to the front
end stored in a NoSQL database and BigQuery used as a data warehouse for
analysis purposes. These instances are automatically set up as part of the
Skeet initialization process, but these steps can be omitted if the user
desires to design their own cloud architecture.

Configuration parameters for database settings are defined by internal
variables which are stored as Fireabse Secrets when they are initiated. Users
have the option to modify these configuration parameters manually, giving them
fine-grained control over their infrastructure.

The workflow of a typical Skeet app as shown in Figure 1 is as follows. The
client communicates with a frontend which is either a mobile app or a website.
The main frameworks recommended by Skeet and supported at the CLI generator
level are React131313https://react.dev/ and React
Native141414https://reactnative.dev/, but other frontends can be used if the
user has particular preferences. The frontend communicates directly with
Firestore in order to rapidly access data authorized for the user based on
Firebase login protocols. Where business logic or relational data is required,
the front end accesses the back end via a load balancer. Back-end logic is
expected to be hosted as a series of independent functions on Cloud Functions

AI services are accessed via business logic stored on Cloud Functions. Popular
LLM-based chatbots such as OpenAI and Vertex AI can be accessed by registering
API keys with the framework. The framework code automates API access and
provides CLI code generators to quickly output the Typescript code required.

###  3.2 Back-End Architecture

Back-end code in a Skeet app is divided into Functions. As a general rule, the
flow of execution of back end code is as follows:

  1. 1.

The frontend calls a Skeet function as an HTTP request.

  2. 2.

The function retrieves data from data sources, potentially including
relational and NoSQL data and responses from AI resources.

  3. 3.

The function performs business logic operations on the data, re-formats it for
displayability and returns it as a JSON response.

A Skeet app can have any number of functions, and users are encouraged to
design fine-grained functions which separate business logic, following SOLID
design principles [Martin, 2000] and in particular the Single Responsibility
principle, which states that each class should solve only one problem; broadly
speaking the same can be said of a Skeet function within the broader context
of domain logic.

A new function can be generated by a CLI command skeet add functions \--name
with initial configuration files and an src directory for user-written code. A
function is initialised with the following directories:

  * •

lib directory contains classes that perform business logic operations on data.

  * •

routings directory provides HTTP endpoints which can be called by the front
end to retrieve or mutate data.

  * •

scripts directory contains code which executes scheduled operations
independent of the HTTP endpoints.

  * •

types directory contains data storage classes related to front-end logic. Data
from the database is reorganised from models into types before being returned.

Users can create blank functions for their own code, or they can create pre-
build functions with scaffolding for the purposes of using AI tools such as
chatbots. In the future, community users will be able to design pre-built
functions that anyone can add to their project.

In addition to domain-specific code which is cleanly separated into functions,
Skeet also provides a common directory for cross-function code. This is
deployed independently, can be accessed from all functions, and includes the
following:

  * •

models directory provides data storage classes that correspond to units of
structured data, such as relational database tables. It is likely that
independent pieces of domain logic will require data from the same sources.

  * •

utils directory contains code that executes common operations across business
logic. This is intended for small, repeated functions that are independent of
domain logic.

  * •

enums directory contains domain-independent variable definitions.

The Skeet CLI expects that users will organise their apps using this broad
structure, and provides commands to generate scaffolding and tests under this
assumption. However, as a lightweight framework, it does not enforce this
structure as such; users are free to decide their own directory structure, and
the framework will still function with the exception of the automatic code
generation functions from the CLI.

###  3.3 Skeet AI

A key feature of Skeet is the tools that facilitate incorporating AI and in
particular chatbot features into web and mobile apps. Machine learning models
are often difficult for developers to understand from first principles, and
training and deploying original models requires considerable specialist
knowledge in addition to, depending on the model and data, significant
expenditure on computing resources.

Skeet provides internal libraries and code scaffolding CLI commands for
connecting to common AI services such as ChatGPT and Vertex AI such that users
only have to input their API credentials in order to connect to and employ
models in their apps.

In addition to back-end code scaffolding and endpoint generation, Skeet also
provides front-end resources to help users specifically with chatbot setup.
Chatbot implementation can be time-consuming to implement for front-end
developers. Skeet provides front-end commands to assist with this process, so
users can set up pre-trained or fine tuned implementations with minimal manual
code entry.

Finally, Skeet uses pretrained models to assist in automatic code generation.
Employing the Prisma151515https://www.prisma.io/ ORM, it allows users to
define their database tables using natural language, and converts them to
migrations and model files automatically.

##  4 EVALUATION

This section describes the evaluation of an initial implementation of Skeet
based on the design goals outlined in Section 2.3.

###  4.1 Survey Design

An initial evaluation for the framework was conducted based on survey data
collected to identify its successes and fix potential flaws. The framework is
still in development, and this survey therefore represents a snapshot of early
adopters, and is not intended as a rigorous and unbiased evaluation, which
will be conducted when development is completed. The objectives of the survey
were threefold:

  1. 1.

To establish the extent to which the initial release of Skeet achieves the
design goals outlined in Section 2.3.

  2. 2.

To find out what kind of developers the framework currently appeals to.

  3. 3.

To identify current issues and pain points for developers using the framework
so they can be fixed.

Survey questions were designed with these goals in mind. The questions can be
split into two categories: questions to gather information about the
participant, and questions to evaluate the framework. Where possible,
questions were asked with answers on a Likert Scale [Nemoto and Beglar, 2014]
from $1$-$5$, which provides a quantitative measurement of the results, with
two positive responses, a neutral response and two negative responses.

Information gathering questions were asked with the objective of tailoring
future development and better understanding the participants’ evaluative
questions. These are listed below, with possible answers in brackets where
answers were not free choice:

  1. 1.

Did you complete the tutorial and create a sample project using Skeet? (Yes /
No)

  2. 2.

Which programming languages do you have experience with? (Checkbox Selection)

  3. 3.

Which web frameworks do you have experience with? (Checkbox Selection)

  4. 4.

How experienced are you with AI technologies? (Professional experience / Quite
experienced / Some experience / Inexperienced / No experience)

  5. 5.

How experienced are you with setting up cloud architectures? (Professional
experience / Quite experienced / Some experience / Inexperienced / No
experience)

Evaluation questions were asked with the objective of finding out
participants’ satisfaction with the framework as compared to other frameworks,
and identifying specific pain points that they may have experienced. The
questions with available answers in brackets are listed below.

  1. 6.

How easy was it to create and run a new project in Skeet compared to other
frameworks? (Very easy / Quite easy / Average / Quite difficult / Very
difficult)

  2. 7.

Compared to other frameworks you’ve used in the past, how easy was it to
create a chatbot using Skeet? (Very easy / Quite easy / Average / Quite
difficult / Very difficult)

  3. 8.

Compared to other frameworks, how easy was it to understand the code
architecture of Skeet? (Very easy / Quite easy / Average / Quite difficult /
Very difficult)

  4. 9.

How easy was it to set up GCP services using Skeet’s CLI compared to the time
taken to do it manually? (Very easy / Quite easy / Average / Quite difficult /
Very difficult)

  5. 10.

How likely are you to consider using Skeet for a future project? (Very likely
/ Quite likely / Possible / Unlikely / Very unlikely)

The survey also asked for qualitative comments from participants about the
framework, with the following question: ”Please write any comments you have
about your experience using Skeet below”. The survey was conducted on Google
Forms, and collected email addresses but no other identifying information from
participants. All quantitative responses were mandatory, and qualitative
responses were optional.

###  4.2 Results

$136$ participants responded to the online survey, advertised on X (formerly
Twitter), on the Discord for the framework’s development and on the website
for the framework. Percentages in the text of this section are rounded to the
nearest whole number.

The development experience of users was diverse, but answers indicated that
most respondents came from a web development background. Most commonly
(question $2$), users had experience developing in Python ($62\%$), Javascript
($58\%$) and Typescript ($47\%$). Framework experience (question $3$) was
similar, with ReactJS ($51\%$), Ruby on Rails ($41\%$) and Angular ($37\%$)
being significantly higher than other choices.

Figure 2: Question 4 - How experienced are you with AI technologies?

Questions $4$ and $5$ asked about users’ previous experience with technologies
outside of strictly development. Experience with AI development was of
particular note, shown in Figure 2: $64\%$ of users expressed at least some
experience, with $13\%$ having professional experience, which is larger than
we anticipated given that the original objective of Skeet is to assist
developers who have very little experience with AI technologies. Experience
with cloud architectures showed a similar distribution, with a slightly higher
level of general experience: $68\%$ with at least some experience or more,
$17\%$ with professional experience. This is not unsurprising, as cloud
deployment is relatively common in the web development space. Both results,
however, are slightly higher than originally anticipated, and possibly reflect
the fact that early adopters of a framework are more likely to be experienced
developers. Further user interviews focused specifically on an inexperienced
audience might be illuminating.

$92\%$ of users who submitted the survey were able to complete the tutorial
(question $1$). This indicates a high level of reliability across a wide
variety of different development environments. One user who was not able to
complete the tutorial submitted the error they encountered as a comment, which
implied that mistakenly skipping steps in the tutorial was a possible reason
users were unable to complete it. In order to address this, the steps that
appear to be commonly skipped will be further emphasised in the tutorial, and
error messages will be updated to indicate to users when steps might have been
missed, and what should be done to correct this.

Figure 3: Question 6 - How easy was it to create and run a new project in
Skeet compared to other frameworks?

$92\%$ of users who were able to complete the tutorial responded that being
able to create and run a new project in Skeet (question $6$) was average or
easier than average, with $32\%$ answering that it was very easy (Figure 3).
This is an encouraging distribution, as it indicates that a significant
percentage of users who were inexperienced or have no experience with AI and
cloud technologies found it quite easy or very easy, which was the original
objective of framework development.

Figure 4: Question 8 - Compared to other frameworks you’ve used in the past,
how easy was it to create a chatbot using Skeet?

Distributions for questions $8$ and $9$ were similarly skewed towards the
positive end of the spectrum. $69\%$ of users indicated that it was either
quite or very easy to create a chatbot using Skeet compared to other
frameworks (Figure 4) and $72\%$ said the same thing about their experience
setting up cloud services in question $9$.

Qualitative results were similarly encouraging. $14$ comments were submitted,
of which $12$ were positive but nonspecific (for example, “The speed of
development and support is fast, which is helpful for developers.”). One
criticism submitted the error they encountered during the tutorial which, as
discussed higher up in this section, came from skipping a tutorial step. The
other criticism stated, “It was difficult for beginners”. The implication here
is unclear, but Skeet is not designed for complete beginners to programming,
so this user’s experience may not be inconsistent with the design goals.

These results indicate that this early version of Skeet is effectively solving
the design goals outlined in Section 2.3. Users were consistently able to
complete the tutorial, and those that did so indicated that their experience
with the framework was positive, and they found it easier than other
frameworks than they had used for the specific purposes of AI and cloud
service integration. When development work is completed on the framework, more
rigorous surveys will be conducted examining all aspects of the framework’s
ease of use.

##  5 CONCLUSIONS

Our position is that many of the popular frameworks currently being used to
develop apps were designed in a previous era, and methods of modern app
development such as serverless architectures and the use of tools such as AI
are not correctly served by these frameworks. Where they do provide these
features, they are often added subsequently by third parties and therefore
more difficult to use than those same features in a framework that had been
designed with them in mind.

As a potential solution to this problem, this paper presented a lightweight
framework, Skeet. Skeet is written in Typescript, and allows immediate
serverless deployment upon app creation, regardless of the level of
infrastructure expertise of the user. The framework also allows simple
incorporation of AI features such as chatbots based on pretrained models as
CLI-generated functions. Section 2.3 described specific design goals for the
framework, and Section 3 described how each section of the framework was
developed and therefore achieved the outlined goals.

The framework was initially evaluated through collecting survey data from
users of the framework, as described in Section 4. This evaluation indicated
that this early version of the framework has been successful in achieving its
design goals: a vast majority of the early adopters completed the tutorial,
and found it easier than mainstream alternatives for accomplishing the
objectives outlined in the initial design goals.

For web development to continue to progress into the modern era, and for
advanced techniques to continue to be accessible, we require new frameworks
which allow non-specialist developers to incorporate these features while
hiding some of the complexity involved in their implementation. Skeet
represents an innovative solution to this problem, and will continue to be
developed with this goal in mind.

## ACKNOWLEDGEMENTS

We would like to acknowledge and thank East Ventures, MIRAISE and Rikka for
supporting this research project.

## REFERENCES

  * Adamopoulou and Moussiades, 2020 Adamopoulou, E. and Moussiades, L. (2020).  An overview of chatbot technology.  In Artificial Intelligence Applications and Innovations, pages 373–383. Springer International Publishing.
  * Badue et al., 2021 Badue, C., Guidolini, R., Carneiro, R. V., Azevedo, P., Cardoso, V. B., Forechi, A., Jesus, L., Berriel, R., Paixão, T. M., Mutz, F., de Paula Veronese, L., Oliveira-Santos, T., and De Souza, A. F. (2021).  Self-driving cars: A survey.  Expert Systems with Applications, 165:113816.
  * Brown et al., 2020 Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. (2020).  Language models are few-shot learners.  Advances in neural information processing systems, 33:1877–1901.
  * Evans, 2004 Evans, E. (2004).  Domain-driven design: tackling complexity in the heart of software.  Addison-Wesley Professional.
  * Hamet and Tremblay, 2017 Hamet, P. and Tremblay, J. (2017).  Artificial intelligence in medicine.  Metabolism, 69:S36–S40.
  * Han et al., 2011 Han, J., Haihong, E., Le, G., and Du, J. (2011).  Survey on nosql database.  In 2011 6th international conference on pervasive computing and applications, pages 363–366. IEEE.
  * Laaziri et al., 2019 Laaziri, M., Benmoussa, K., Khoulji, S., and Kerkeb, M. (2019).  A comparative study of php frameworks performance.  Procedia Manufacturing, 32:864–871.
  * Li and Horrocks, 2003 Li, L. and Horrocks, I. (2003).  A software framework for matchmaking based on semantic web technology.  In Proceedings of the 12th international conference on World Wide Web, pages 331–339.
  * Makridakis, 2017 Makridakis, S. (2017).  The forthcoming artificial intelligence (ai) revolution: Its impact on society and firms.  Futures, 90:46–60.
  * Martin, 2000 Martin, R. (2000).  Design Principles and Design Patterns.  objectmentor.com.
  * Nemoto and Beglar, 2014 Nemoto, T. and Beglar, D. (2014).  Likert-scale questionnaires.  In JALT 2013 conference proceedings, pages 1–8.
  * Nicolescu and Tudorache, 2022 Nicolescu, L. and Tudorache, M. (2022).  Human-computer interaction in customer service: the experience with ai chatbots—a systematic literature review.  Electronics, 11(10):1579.
  * Parasuraman et al., 1991 Parasuraman, A., Berry, L., and Zeithaml, V. (1991).  Understanding customer expectations of service.  MIT sloan management review.
  * Tournier et al., 2019 Tournier, J.-D., Smith, R., Raffelt, D., Tabbara, R., Dhollander, T., Pietsch, M., Christiaens, D., Jeurissen, B., Yeh, C.-H., and Connelly, A. (2019).  Mrtrix3: A fast, flexible and open software framework for medical image processing and visualisation.  Neuroimage, 202:116137.