# Variational Quantum Linear Solver with Dynamic Ansatz

Hrushikesh Patil<EMAIL_ADDRESS>Department of Electrical and
Computer Engineering, Stony Brook University, Stony Brook, NY 11794  Yulun
Wang<EMAIL_ADDRESS>Predrag S. Krstić<EMAIL_ADDRESS>Institute for Advanced Computational Science, Stony Brook University, NY
11794-5250

###### Abstract

Variational quantum algorithms have found success in the NISQ era owing to
their hybrid quantum-classical approach which mitigate the problems of noise
in quantum computers. In our study we introduce the dynamic ansatz in the
Variational Quantum Linear Solver for a system of linear algebraic equations.
In this improved algorithm, the number of layers in the hardware efficient
ansatz circuit is evolved, starting from a small and gradually increasing
until convergence of the solution is reached. We demonstrate the algorithm
advantage in comparison to the standard, static ansatz by utilizing fewer
quantum resources and with a smaller quantum depth on average, in presence and
absence of quantum noise, and in cases when the number of qubits or condition
number of the system matrix are increased. The numbers of iterations and
layers can be altered by a switching parameter. The performance of the
algorithm in using quantum resources is quantified by a newly defined metric.

††preprint: APS/123-QED

##  I INTRODUCTION

Solving a System of Linear Equations (SLE) is the fundamental problem in
computation. Nearly 70% of the scientific and engineering numerical problems
reduces to solving SLE [1], which can be symbolically expressed as finding
unknown vector $\bm{x}$ of dimension $N$ from a system of equations
$A\bm{x}=\bm{b}$ , where $A$ is a matrix of dimension $M\times N$, and
$\bm{b}$ is a vector of dimension $M$. In this paper we will consider only
square SLEs with $N=M$, since these appear most often in applications. In
classical computation, solving of a SLE scales polynomially with $N$ [2]. Well
known quantum computing SLE algorithm HHL [3] scales logarithmically with N.
However, the application of HHL is severely limited in the Noisy Intermediate-
Scale Quantum (NISQ) era due to its considerable quantum depth. The hybrid
approaches, which combine quantum and classical computing [4, 5, 6, 7, 8, 9],
result in a family of algorithms called Variational Hybrid Quantum Classical
Algorithms (VHQCA). These have been successfully applied in computational
chemistry (VQE) [4]), fidelity estimation [5], quantum machine learning [10],
etc. Characteristics of a VHQCA is quantum ansatz of a small quantum depth,
combined with a classical, post-processing optimization routines. Despite the
promising results, VHQCAs have shown to be also susceptible to damaging
effects of noise [11], especially when the number of qubits increases.

Bravo-Prieto et al. [6] proposed a VHQCA for solving a system of linear
equations called Variational Quantum Linear Solver (VQLS). This algorithm uses
a variational quantum circuit to evaluate the overlap between states
$A\ket{x}$ and $\ket{b}$, where the state $\ket{x}$ is a trial wave function
which approximates the solution of the SLE. This is encoded iteratively by a
variational quantum circuit, ansatz, followed by the classical optimization of
the variational parameters until convergence is reached. VQLS has
polylogarithmic scaling with $N$ and was used to solve linear systems of size
$N=1024$ with $n=log_{2}(N)=10$ qubits on a quantum computer [6]. This is a
significant achievement as compared to the maximal system size 8 (i.e. with 3
qubits) achieved by the HHL algorithm [12]. Similar VHQCA’s for SLE have been
proposed by Huang et al. [7] and Xu et al. [8]. However, since VQLS has
polylogarithmic scaling (as $O((log_{2}(N))^{8.5}\kappa log(1/\epsilon))$ [6],
iterative classical methods like conjugate gradient (CG) which scale as
$O(Ns\kappa log(1/\epsilon))$ [3] are faster for small system sizes. VQLS is
expected to show advantage over CG for very large system sizes, $N>2\times
10^{12}$ ($>$ 41 qubits) with sparsity $s=0.5$, precision $\epsilon=0.01$ and
condition number $\kappa=1$ . However, unlike VQLS the CG method is
constrained to positive definite matrices. Hence, for classical iterative
solvers like GMRES (Generalized Minimum Residual Method) which are more
generalized which scale as $O(N^{2})$[13], VQLS would perform better for
matrix sizes larger than $2\times 10^{5}$ (corresponding to $>$ 17 qubits).
When we compare VQLS to a direct solver like Gaussian Elimination with
$O(N^{3})$ complexity we can expect VQLS to show advantage for $N>750$ ($>$9
qubits).

The primary interest in quantum computing of the SLE is the problems of large
dimension. Hence, for a prospective SLE quantum algorithm it is of interest to
reach a good performance with increase of N, i.e., the scalability. The
scalability of VQLS is limited by the quantum noise and appearance of barren
plateaus in the optimization landscape. The latter is a consequence of
vanishing gradients, a well-known problem in classical [14] and quantum
machine learning algorithms [15]. Recent papers by Mclean et al. [15] and
Cerezo et al. [16] demonstrated the appearance of the barren plateaus in
VHQCA.

The quantum noise has been a stumbling block in the quantum computer
implementations of all quantum and quantum-classical algorithms. Recent
studies [11] have shown that quantum noise can induce barren plateaus. The
ansatzes for both local and global cost functions are susceptible to noise-
induced barren plateaus in the NISQ era applications, though local cost
functions are considered more resistant to the barren plateaus [16]. The noise
is dependent on the number of gates, and thus, correlated to the quantum depth
of an ansatz circuit [17][18]. Hence, a smaller quantum depth will result in a
smaller overall damaging effect of the quantum noise.

In the present work, we address the scalability problem of VQLS by developing
an algorithm with evolving, dynamic ansatz as inspired in part by the adaptive
VQE [19] and NASNet [20]. The idea of using a variable structure ansatz has
been explored for Quantum Machine Learning (QML) [21] and for VQE [22] and was
termed Quantum Architecture Search [23][24]. Ostaszewski et al. [25],
demonstrated that variation of the ansatz structure along with the variational
parameters in VQE significantly improved the algorithm performance. Layerwise
learning of ansatz layers for quantum neural networks was investigated by
Skolik et al. [26], while Rattew et al. [22] developed evolutionary algorithm
to grow the VQE ansatz. Our adaptive algorithm does not aim to improve the
computational complexity of VQLS. It has the same polylogarithmic complexity
as standard VQLS. We aim to improve the performance of VQLS in presence of
quantum noise. Our work focuses on varying the ansatz for VQLS by gradual
change of the number of layers in ansatz until desired accuracy was reached
while keeping used quantum resources at minimum. We evaluate our approach
against the standard VQLS algorithm with hardware efficient ansatz [4] by
comparing the quantum depths of the standard and dynamic VQLS ansatzes in a
number of SLE test examples. We define and use in Section III a new metric
termed “total resource cost” for a more stringent comparison between the two
approaches to VQLS in both, presence and absence of the quantum noise. To
induce the quantum noise, we use IBM Qiskit noise models [27] in the
simulators. The motivation behind this study is the reduction of the effective
quantum depth in the algorithm, thereby limiting the noise and allowing
increase of the SLE dimension $N$ in the VQLS implementations.

The paper is organized as following: Section II describes the methods used in
the paper. In Section III we show and discuss the results, while our
conclusions are presented in Section IV.

##  II Methods

The cost functions and ansatz circuits involved in the standard VQLS method
[6] are reviewed in subsections II.1 and II.2. The new dynamic ansatz, the
algorithm for its evolution through iterations, classical optimization as well
as relevant quantum noise simulations are presented in subsections II.3, II.4,
and II.5.

###  II.1 The cost function and the quantum circuits in VQLS

Figure 1: Quantum circuits for VQLS: a) Hadamard test to calculate
denominator, and b) swap test to calculate numerator of the cost function for
a system of size $N=8$.

The cost function is defined in VQLS [6] as the overlap of states $A\ket{x}$
and $\ket{b}=U\ket{0}$, where $U$ is an unitary operator which is the state
initialization circuit as defined in [28]. The trial state is encoded by a
variational ansatz $\ket{x}=V(\bm{\theta})\ket{0}$, with a set of variable
parameters, expressed as a vector of rotation angles
$\bm{\theta}=[\theta_{0},\theta_{1},...,\theta_{m}]$. Since matrix $A$ is an
arbitrary matrix, it is decomposed into a linear combination of unitary
matrices of the form $A=\sum_{l}c_{l}P_{l}$ where $c_{l}$ are complex numbers
and $P_{l}$ are Pauli matrices [29]. The decomposition process is a
preparatory, one-time, process which we illustrate a few examples in the
Supplemental Information (section S1). The Hamiltonian $H_{G}$ and equation
for the global cost function $C_{G}$ are defined in [6] as

$H_{G}=A^{\dagger}(1-\langle b|b\rangle)A$ (1) $C_{G}=1-\frac{|\langle
b|\psi\rangle|^{2}}{\langle\psi|\psi\rangle}$ (2)

with $\ket{\psi}=A\ket{x}=AV(\bm{\theta})\ket{0}$. Although the local cost
functions are more resistant to barren plateaus [16], we will use the global
cost function for which the quantum circuits are simpler than those for the
local cost functions. We note that we compare strategies for relatively small
ansatzes (up to eight qubits), for which barren plateaus usually do not
present a critical problem.

To calculate the denominator and numerator of the global cost function, Eq.
(2), one makes use of the Hadamard and swap tests [6], shown in Fig. 1 on the
example of $N=8$. The $S^{\dagger}$ and $R_{Z}$ gates are used only when
measuring the imaginary part of the cost function. The main advantage of both
tests is that only the ancilla qubit needs to be measured. While the Hadamard
test can also be used to calculate the numerator of the cost function, it
leads to a more complex quantum circuit with multiple unitaries needed to be
controlled. In contrast, swap test requires twice the number of qubits than
the Hadamard test but yields a much simpler circuit with fewer controlled
unitaries.

###  II.2 Static and Dynamic Ansatzes

We discern two algorithms, the Algorithm with Static Ansatz (ASA) and with
Dynamic Ansatz (ADA). In ASA, the total number of layers “$d$” is predefined
and fixed during the VQLS run. In ADA the number of layers evolves, depending
on the instantaneous value of the cost function. ADA avoids search in an
initially large Hilbert space. Instead, the algorithm starts finding the
minima in a small subspace spanned by the single layered ansatz, then another
layer of ansatz is appended, and the algorithm moves into a larger subspace.
This procedure of adding new layers keeps repeating until value of the cost
function reaches the pre-defined convergence criterium.

Like in ASA [6], we use in ADA the basic hardware efficient ansatz with
layered structure to generate a trial state $\ket{x}$. Each layer consists of
a sublayer of rotation gates, followed by a sublayer of entanglers, as
illustrated in Fig. 2 for $N=16$. This structure is repeated for a total
number of “$d$” layers, as needed. The minimum number of layers in ASA
estimated to guarantee convergence is given by

$d_{min}=\frac{2^{n}}{n}$ (3)

where $n$ is the number of qubits. The reasoning behind the Eq. (3) is that
the vector $\ket{x}$ contains $2^{n}$ elements, hence at maximum we need one
parameter per element. The denominator comes from the fact that hardware
efficient ansatz contains $n$ parameters at one layer. The number of layers
for ASA is $d_{min}$

Figure 2: The layered structure of hardware efficient ansatz for SLE with
$N=16$.

The motivation behind ADA is to improve the performance in comparison to the
“standard” VQLS with ASA by reducing the total quantum depth of the ansatz,
accumulated through iterations and evolution of the number of layers, thereby
reducing damaging effects of noise. This is achieved for some types of the SLE
systems, as discussed in Section III, thus reducing the quantum noise.

###  II.3 Classical Optimization

In the classical part of the VQLS algorithm we apply the gradient-based
optimization utilizing the gradient descent method [30] defined by the
equation

$\bm{\theta_{t+1}}=\bm{\theta_{t}}+\delta\nabla_{\bm{\theta_{t}}}C_{G}(\bm{\theta_{t}})$
(4)

where $\bm{\theta_{t}}$ is the value of the parameter vector at iteration $t$,
$\delta$ is the step size of the optimizer and $C_{G}$ is the cost function
parameterized by $\bm{\theta_{t}}$. The step size is an input to VQLS
algorithm. Choosing too large value of $\delta$ may result in lack of
convergence while too small value results in long runtimes of VQLS. Below we
explain how the gradients $\nabla\theta_{j}$ are calculated in Eq. (4).

In classical computing, backpropagation has been the method of choice for
calculating gradients in a neural networks. The ansatz bears some resemblance
to the neural network, more specifically to the parameterized connected
network of parameters which are “trained” using an optimizer. Still, the
ansatz cannot be optimized using backpropagation, since this requires the
measurement of intermediate layers of the “neural network”, which would cause
collapse of the quantum wave function, disabling its transfer to the next
layer. Hence, approaches which do not require intermediate measurements like
are finite differences, automatic differentiation, and parameter shift rule
are choices for gradients calculations in a quantum ansatz [31]. We use the
parameter shift rule which provides exact gradients and is defined by
equation,

$\frac{\partial
C_{G}(\bm{\theta})}{\partial\theta_{i}}=\frac{C_{G}\left([\theta_{1},...,\theta_{i}+\frac{\pi}{2},...,\theta_{k}]\right)}{2}\\\
-\frac{C_{G}\left([\theta_{1},...,\theta_{i}-\frac{\pi}{2},...,\theta_{k}]\right)}{2}$
(5)

where $\bm{\theta}=[\theta_{1},...,\theta_{i},...,\theta_{k}]$, where $k$ is
the iteration dependent number of parameters and $i=1,2,...,k$.

This equation requires two cost function computations for gradient calculation
of each parameter. The cost function evaluations are executed on a quantum
computer and hence are affected by quantum noise. The time $t_{L}$ spent in
each optimization loop which calculates all gradients can be is calculated
from

$t_{L}=2\nu t_{c}$ (6)

where $\nu$ is the total number of variational parameters and $t_{c}$ is the
time for each cost function computation. In case of the hardware efficient
ansatz $\nu$ is obtained as the number of qubits multiplied by the number of
layers, which can be conjectured from Fig. 2.

We performed a benchmarking experiment comparing various simulators for time
taken by each of them to calculate the cost function as well as for time taken
for gradient calculations and parameter updates. The details are presented in
Supplemental Information, section S7. From Table S9 it is clear that
Pennylane-qulacs is on average about 2 times faster than Pennylane default and
about 3 times faster than Pennylane-qiskit in calculations of the gradients.

###  II.4 Evolution of ansatz in ADA

As discussed in subsection II.1 the idea behind ADA is to start with a small
configuration space, and increase it successively, limiting the total number
of layers when convergence is reached. Initially, we limit the search space to
a subspace smaller than the one for a hardware-efficient ansatz with $d_{min}$
layers (Eq. (3)). After finding the minima in the subspace, a check of overall
convergence is performed. If convergence is not reached, a new layer of ansatz
is appended to the existing ansatz (Fig. 3). The procedure is continued until
the convergence is reached, i.e. value of the cost function goes below a
specified threshold $d_{t}=\frac{\epsilon^{2}}{\kappa^{2}}$. To control the
speed of appending layers in ADA, we define a hyperparameter which we name the
switching parameter (SP). When the difference in costs of two successive
optimization steps drops below SP, a new layer is appended. The switching
parameter governs the dynamical nature of the ansatz.

Figure 3: Flowchart for ADA algorithm

For example, one would have potentially lesser layers at the cost of
increasing number of optimization steps, but setting the SP low. Conversely,
setting the SP too high would add too many layers before the maximum
predefined quantum depth is reached. In this case, the ADA performs like the
ASA in terms of both the number of iterations and the Total Resource Cost (to
be defined in Section III).

A good way to determine value of SP is by following formula,

$SP=\frac{1-d_{t}}{n_{iterd}}$ (7)

where $d_{t}$ is the stopping threshold (given by the user, which depends on
the desired precision ($\epsilon$) of solution
$d_{t}=\frac{\epsilon^{2}}{\kappa^{2}}$) and $n_{iterd}$ is the maximum
allowed number of iterations which is also set in advance by a user. There is
no guarantee that the algorithm will converge by any specified number of
iterations. Setting $n_{iterd}$ low will make SP value high, thereby making
ADA algorithm to add layers faster. Conversely, setting $n_{t}$ to a higher
value will make SP value low. The idea behind the choice of SP can be
understood from the figure 4

Figure 4: Effect of different SP values on the number of iterations for
addition of a new layer

SP value is compared with the difference of cost function values between two
successive optimization iterations to decide the addition of layer of ansatz.
Essentially what the algorithm does is comparison of the slope of the cost
function at each iteration with slope of SP. In figure 4 the blue line
approximates values of cost function against the number of iterations. The
other three lines indicate the slopes of different values of SP obtained from
the Eq. 7. The points where they are tangent to the blue curve indicate the
points where an addition of a new layer is triggered. The $SP=0.0009$ line
will trigger the addition of layer at iteration 344 as compared to $SP=0.0005$
at iteration 462.

###  II.5 Noise Simulation

We study the effect of noise on VQLS with ADA and ASA using PennyLane [32]
with the access to IBM QASM noise simulator. The simulator uses a noise model
generated by the calibration data at “ibmq_16_melbourne” as an approximation
to the noise in the real quantum computer. This noise model is contains
depolarizing errors on both single and two-qubit gates, thermal relaxation
errors for simulating decoherence, and single-qubit readout errors on all
individual measurements, as explained in the Supplemental Information (Section
S7). We compare the ASA and ADA in presence of noise in Section III.5.

##  III Results

All experimental results were obtained using Xanadu’s PennyLane library [32].
For the simulations we chose the qulacs backend [33] on basis of the results
and discussion in subsection II.3. For the experiments with noisy simulations
we use IBM QASM simulator. The optimization method is utilized with the
gradient descent (Eq. (4)) with parameter shift rule as in Eq. (5), and with a
step size of 0.05. To reduce the computation time, we set convergence
threshold $d_{t}$ of the cost function to 0.1 and the maximum number of
iterations to 6400. Only the cases where convergence is reached are discussed
in our analysis. Interestingly, the cases when convergence is not achieved are
appearing simultaneously for both ASA and ADA. This approach is used in all
experiments.

###  III.1 Total Resource Cost (TRC)

To evaluate and compare efficacies of the ADA and ASA , we define a new
performance metric, Total Resource Cost (TRC). From Eq. (5), two cost function
evaluations are needed per parameter in each iteration of the optimizer. The
number of parameters is determined by the number of rotational gates in the
ansatz which is proportional to the number of layers in ansatz. These together
define the Effective Quantum Depth (EQD) as quantum depth of the circuit
accumulated through the iterations. In ADA the EQD is proportional to the sum
of all layers in the evolution of the ansatz. The quantum noise in the
algorithm implementation is function of the number of gates, which is
proportional the EQD.

TRC is defined as the sum of number of layers of each ansatz over iterations.
For ASA, this is simply product of the number of iterations needed for
convergence, $z_{ASA}$, and the predefined number of layers in ansatz,
$d_{ASA}$,

$TRC_{ASA}=z_{ASA}d_{ASA}$ (8)

For ADA the TRC is a cumulative sum of number of layers at each optimization
step

$TRC_{ADA}=\sum^{z_{ADA}}_{i=0}d_{ADA}(i)$ (9)

where $z_{ADA}$ is the total number of iterations of VQLS with ADA and
$d_{ADA}(i)$ is the number of layers in the iteration “$i$”. For example,
assume that ADA has 10 iterations in total with iteration 1 and 2 having 1
layer, 3 and 4 having 2 layers, 5 to 8 having 3 layers and 9 and 10 having 4
layers in total. The $TRC_{ADA}=2\cdot 1+2\cdot 2+4\cdot 3+2\cdot 4$. For ASA,
even if we have 7 iterations with 4 layers the $TRC_{ASA}=28$, i.e. ASA has a
higher resource cost in this example.

The TRC metric is proportional to the EQD of the variational quantum circuit.
Each iteration in ASA contains larger or equal number of parameters than ADA
(since $d_{ADA}(i)\leq d_{ASA}$ for all i). Fewer number of parameters means
lesser number of gradient calculations, thereby implying more efficient
computation in each iteration, but also lesser number of (rotational) gates,
which means smaller noise.

Here we compare two ASA examples, which have different number of iterations,
$z_{ASA}$, and different number of layers, $d_{ASA}$, showing that neither of
these parameters defines unambiguously the algorithm efficacy. In the first
example $z^{(1)}_{ASA}=10$ and $d^{(1)}_{ASA}=4$. In the second example
$z^{(2)}_{ASA}=20$ and $d^{(2)}_{ASA}=2$. We also assume that each layer in
both cases contains R rotational gates, i.e. R optimization parameters. Since
there are two cost function evaluations per parameter, the total number of the
cost evaluations is the same for both cases, i.e. $4\cdot 10\cdot 2=2\cdot
20\cdot 2=80$, implying the same running time. This is correctly reflected by
the equality $TRC^{(1)}=TRC^{(2)}=40$, but not with either number of
iterations or number of layers.

The rationale behind introducing TRC is that, unlike classical computing,
quantum computing is heavily affected by quantum noise. The noise is directly
proportional to depth of a quantum circuits. Polylogarithmic computational
complexity of the quantum algorithm vs. polynomial computational complexity of
the classical algorithms does not capture the effect of noise on the
algorithm. Even when two algorithms have the same computational complexity,
the needed number of operations could be different because of a different
quantum circuit depth. Hence, we need a metric that tracks the usage of
resources (i.e. number of gates) over all iterations. Since addition of each
gate increases noise in the circuit, the TRC measures how the proposed
algorithm is noise resilient.

###  III.2 Variation of the number of qubits

In this experiment we use 20 randomly generated SLEs for each of the sizes
$N=16,32$ and $256$ (i.e. with 4, 5 and 8 qubits), using the PennyLane
software library. The condition numbers of SLE are varied from 1 to 20. About
50% of these tests reach convergence for which we compare TRCs, final number
of layers and total number of iterations with both ASA and ADA. The averaged
results are shown in Table 1. The detailed results can be seen in tables S2-S6
of Supplemental Information (sections S2- S5).

Table 1: Comparison of arithmetically averaged experimental data for ADA and ASA of VQLS. Number | TRC | Final Layers | Total iterations
---|---|---|---
of qubits | ADA | ASA | ADA | ASA | ADA | ASA
4 | 1777.8 | 1949.2 | 3.4 | 4 | 613.3 | 487.3
5 | 2385.68 | 2910.81 | 4.5 | 6 | 572.77 | 485.13
6 | 6442.53 | 7366.93 | 6.33 | 8 | 890.06 | 920.86

The arithmetic averages of $TRC_{ADA}$ are smaller (up to 20%) than these in
$TRC_{ASA}$ for all considered cases. This implies the faster calculations and
smaller total noise of ADA. We also compare the number of layers of ansatz in
the final iteration, which we term as “final layers”. On average ADA finishes
with smaller number of final layers than ASA. As the number of qubits
increases, the ADA requires fewer number of iterations than ASA to converge.

###  III.3 Variation of the matrix condition number

Here we use 25 SLEs of dimension $N=32$ (5 qubits). Condition number is
calculated by taking the ratio of the largest to the smallest eigenvalue of
matrix A. The number of layers in ansatzes was 6 (refer Eq. (3)) for ASA while
the maximum number of layers was set to 6 for ADA. We varied the condition
number in range 1 to 20 (see Table 2). For each condition number, the
experiments at four systems are performed and these all reach convergence. We
calculate TRC for both ASA and ADA, and and for comparison we calculate
Average of the Relative TRC (ARTRC) deviation:

$\frac{\Delta TRC}{TRC}=\frac{TRC_{ADA}-TRC_{ASA}}{TRC_{ADA}}$ (10)

Table 2:  Comparison of ARTRC deviation between ASA and ADA results with respect to the condition number for SLEs of a fixed size 32 (5 qubits). Condition Number | ARTRC deviation
---|---
1 | 0.0625
3.684 | 0.41
7.899 | 0.31
13.572 | 0.27
20.651 | -1.18

The averaged results are presented in Table 2, while the details are shown in
Supplemental Information (section S3, table S5). The minus sign indicates
better performance of ADA.

Better performance is obtained for ASA when the condition numbers are smaller.
Up to condition number 5 $TRC_{ADA}$’s are more than 40% larger. But with
further increase of condition number, the performance of the ADA is improving.
For poorly conditioned matrices (i.e matrices with a high condition number 20)
the ADA results in 18% lower TRC than that of ASA.

###  III.4 Variation of the matrix sparsity

The systems of equations with sparse matrices are common occurrence in science
and technology. In our experiments, we define sparsity of a matrix as the
ratio of the number of zero matrix elements to the total number of matrix
elements. We used matrices of size $N=16$. The maximum number of layers was
set to 4. The sparsity was varied in 4 steps, from 0.9375 to 0.75, while the
condition number of the matrices was kept low, between 1 and 1.5. For each
sparsity, experiments were performed with ten different matrices. The ARTRC
deviation is presented in the table 3 (details in SI, table S6)

Table 3:  Comparison of ARTRC deviation between ASA and ADA results with respect to the condition number for systems of a fixed size 32 (5 qubits). Sparsity | ARTRC deviation
---|---
0.9375 | -0.04
0.875 | 0.17
0.8125 | -0.012
0.75 | -0.14

The sparsity does not significantly impact performance of VQLS with ADA vs
ASA, although there is a weak advantage of the ADA results. This advantage is
expected to increase for the system matrices with larger condition numbers.

###  III.5 Comparison of ADA and ASA in presence of quantum noise

In the noisy simulations we used systems of dimension $N=16$. More details on
how we perform the noise simulations can be found in subsection II.5.

Table 4:  Comparison of the TRCs for ADA and ASA in presence of noise. Condition | Average TRC | % of cases
---|---|---
Number | ADA | ASA | $TRC_{ADA}<TRC_{ASA}$
1 | 261.1 | 205.6 | 30
3.6840 | 639 | 625 | 75
7.8995 | 542.4 | 550.4 | 80
20.6519 | 699.5 | 1024.5 | 100

From Table 4, the TRC of ADA is becoming substantially smaller than of ASA
with increase of the condition number and with quantum noise present. Also, in
almost 30% of cases, ADA reached convergence with lesser number of final
layers than ASA. In all other cases both algorithms reached the convergence
with same number of final layers.

###  III.6 Variation of the number of layers in ASA

In ASA, the number of layers have to be specified before the algorithm is
executed. It is important to have sufficient number of layers so that the ASA
is not under-parameterized to reach convergence. However, it is not always
easy to predict the number of layers as the input system matrix can vary in
terms of condition number and sparsity. Hence, to guarantee convergence with
ASA, one might over-parameterize the ansatz by adding more than the needed
number of layers. The problem with overparameterization is that the extra
layers increase the quantum depth of the circuits used to calculate the cost
function, thus increasing the total amount of noise. Due to these factors,
setting the right number of layers is essential in ASA. This is not a problem
with ADA since it changes the number of layers dynamically without specifying
it in advance.

In the present experiments, the number of qubits is 8. To guarantee
convergence, irrespective of the input matrix, the needed number of layers is
32, for which the vector $\ket{x}$ contains 256 elements (more details in
Supplemental Information, section S2). With 8 parameters in each layer, 32
layers contain 256 parameters. We purposely under-parameterize the ASA by
setting the maximum number of layers to 8 and 16. This is done to show that
for some matrices the needed number of layers in ASA is lesser than the
$d_{min}$ of Eq. (3). We utilize VQLS to 21 systems, applying 8 and 16 layers
ASA, and also ADA with maximum 8 layers. We found that out of 21 matrices only
6 matrices reached convergence, in each case with $d_{t}=0.1$. The convergence
was reached with the similar values of TRC’s for all three case groups.
Another interesting observation is that for ASA with 16 layers the algorithm
takes fewer iterations than with ansatz with 8 layers but still converges with
only slightly higher TRC. The details are shown in SI Section S8, Table S10.

###  III.7 Variation of the switching parameter

Table 5:  Variation of the TRC and Final number of layers in ADA when SP is varied. | ADA | ASA
---|---|---
SP | $10^{-1}$ | $10^{-2}$ | $10^{-3}$ | $10^{-5}$ | NA
Lowest TRC (%) | 33 | 14 | 52 | 14 | 0
FL111FL stands for Final Layers (%) ADA $<d_{min}$ | 0 | 0 | 66.67 | 71.42 | NA

In these experiment we use 30 systems of $N=16$ (4 qubits) with varying
condition numbers of their matrices A. We consider results for the 21 systems
which reached convergence with ADA, with each of the SPs (0.1, 0.01, 0.001,
0.0001) as well as with ASA. Limiting number of layers for ADA is set to 4,
which was also the fixed number of layers for ASA. The main objective is to
test the effect of the choice of SP on the TRC performance of ADA, which could
provide a mean to obtain a good balance between the number of iterations and
number of layers in ansatz to reach convergence.

In Table 5, first row shows percentage of cases when ADA with particular value
of SP (in columns) has the minimal value of TRC among all 105 cases (4x21
converged with ADA plus 21 converged with ASA). The second row indicates
percentage of cases when final number of layers with a particular SP value in
columns was less than the $d_{min}$.

As seen in the Table 5, some applications of ADA have lesser TRC than ASA. The
TRC and final number of layers of ADA and ASA is almost the same when SP is
0.1 (Section S6). The TRC of ADA seems to have a convincing minimum when SP is
0.001. This indicates that there is an optimum value of switching parameter
which can be found out empirically from numerical experiments. For example,
the optimum value for above system is obviously between 0.00001 and 0.01. From
the Table 5 one can also see that out of all experimental runs, in 67% cases
the final number of layers of ADA is less than that of ASA if SP is 0.001
(Refer SI, section S7 for details).

###  III.8 Future directions with ADA

In this work ADA was used to improve performance of the VQLS algorithm.
However, we expect that ADA could be also applicable in VQE and Quantum
Machine Learning, since ADA algorithm is agnostic. The future improvements of
the algorithm could be done by implementing the popular optimizers like ADAM
[34] and other momentum based gradient optimizers. The momentum value can help
to adjust the switching parameter. It would be also interesting to investigate
the performance of ADA with non-gradient based optimizers like are Powell and
COBYLA [35]. These have fewer evaluations of the quantum cost function.
Another possible improvement can be also made by using optimizers like L-BFGS
[36] which use the second order derivatives for faster convergence, but on
account of more cost function computations. ADA tends to have fewer parameters
than ASA and thus can make use of L-BFGS more feasible for NISQ era. The
second order derivative values can be leveraged in ADA for switching decision
between the layers.

##  IV Conclusion

Developing an efficient solver for a system of linear equations is one of the
central tasks in computing due to its wide use in many physical and
engineering applications. Unlike the classical algorithms, VQLS is an
algorithm with polylogarithmic scaling with respect to the system size, which
promises to offer the quantum advantage even in the NISQ era. The goal of this
study was to show that with a good decision making process within a
variational algorithm, in particular with VQLS, we can significantly improve
its performance in the NISQ era. In our study the decision making process is
the variation of the number of layers in the VQLS ansatz, which is the basis
for development of our algorithm with dynamic ansatz, ADA. We computationally
compared efficiency of ADA with the standard algorithm with static ansatz,
ASA, varying the system size (i.e. the number of qubits), condition number and
sparsity of the system matrix, as well as switching parameter and number of
layers in the hardware efficient ansatz. In presence of noise, ADA tends to
outperforms ASA algorithm, quantified by reduction of the total resource cost.
Since TRC is directly dependent on the number or layers in the ansatz as well
as of the number of iterations, reduction of the TRC results into reduction of
the effective quantum depth of the circuit, accumulated through the
iterations. ADA also outperformed ASA when the system is ill-conditioned, i.e.
when the system matrix has a large condition number. With the increase of
number of qubits, ADA starts outperforming ASA not only measured by TRCs but
also by number of iterations. While one can always estimate the number of
layers for ASA to guarantee convergence, this may often lead to
overparameterization, and thus unnecessary increase of the quantum noise. ADA
is not susceptible to the overparameterization problem since it doesn’t
require specifying number of layers of ansatz in advance. Rather, the
algorithm gradually finds the appropriate amount of layers, i.e. the number of
optimization parameters, for convergence. Fewer parameters mean fewer cost
function evaluations on the quantum computer to calculate gradients. In
particular, the values of gradients are less affected by noise. In ADA we
define the switching parameter, SP, which controls the addition of new layers
in the iteration process. By a proper choice of SP one can adapt the optimum
performance of ADA to the noise characteristics of the particular quantum
computer. Finally we remark that, ADA is a subset of Quantum Circuit
Architecture Search Algorithms. This class of algorithms is useful in
optimizing a quantum circuit architecture during the algorithm run.

##  V Acknowledgments

HP acknowledges the useful discussions with Dr. Ji Liu. YW was supported by a
graduate student scholarship from IACS. All experiments were performed at
Seawulf HPC cluster of SBU, and at XSEDE HPCs Comet and Expanse of SDSC.

## References

  * Dahlquist and Bjorck [1974] G. Dahlquist and A. Bjorck,  _Numerical Methods_ (Prentice-Hall, 1974).
  * Pan [1991] V. Pan, Complexity of algorithms for linear systems of equations, in  _Computer Algorithms for Solving Linear Algebraic Equations_ , edited by E. Spedicato (Springer Berlin Heidelberg, Berlin, Heidelberg, 1991) pp. 27–56.
  * Harrow  _et al._ [2009] A. W. Harrow, A. Hassidim, and S. Lloyd, Quantum algorithm for linear systems of equations, Phys. Rev. Lett. 103, 150502 (2009).
  * Kandala  _et al._ [2017] A. Kandala, A. Mezzacapo, K. Temme, M. Takita, M. Brink, J. M. Chow, and J. M. Gambetta, Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets, Nature 549, 242 (2017).
  * Cerezo  _et al._ [2020] M. Cerezo, A. Poremba, L. Cincio, and P. J. Coles, Variational Quantum Fidelity Estimation, Quantum 4, 248 (2020).
  * Bravo-Prieto  _et al._ [2020] C. Bravo-Prieto, R. LaRose, M. Cerezo, Y. Subasi, L. Cincio, and P. J. Coles, Variational quantum linear solver (2020), arXiv:1909.05820 [quant-ph] .
  * Huang  _et al._ [2019] H.-Y. Huang, K. Bharti, and P. Rebentrost, Near-term quantum algorithms for linear systems of equations (2019), arXiv:1909.07344 [quant-ph] .
  * Xu  _et al._ [2019] X. Xu, J. Sun, S. Endo, Y. Li, S. C. Benjamin, and X. Yuan, Variational algorithms for linear algebra (2019), arXiv:1909.03898 [quant-ph] .
  * Bharti  _et al._ [2021] K. Bharti _et al._ , Noisy intermediate-scale quantum (nisq) algorithms (2021), arXiv:2101.08448 [quant-ph] .
  * Biamonte  _et al._ [2017] J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd, Quantum machine learning, Nature 549, 195 (2017).
  * Wang  _et al._ [2021] S. Wang, E. Fontana, M. Cerezo, K. Sharma, A. Sone, L. Cincio, and P. J. Coles, Noise-induced barren plateaus in variational quantum algorithms (2021), arXiv:2007.14384 [quant-ph] .
  * Wen  _et al._ [2019] J. Wen, X. Kong, S. Wei, B. Wang, T. Xin, and G. Long, Experimental realization of quantum algorithms for a linear system inspired by adiabatic quantum computing, Phys. Rev. A 99, 012320 (2019).
  * Saad and Schultz [1986] Y. Saad and M. H. Schultz, Gmres: a generalized minimal residual algorithm for solving nonsymmetric linear systems, Siam Journal on Scientific and Statistical Computing 7, 856 (1986).
  * Shalev-Shwartz  _et al._ [2017] S. Shalev-Shwartz, O. Shamir, and S. Shammah, Failures of gradient-based deep learning, in  _Proceedings of the 34th International Conference on Machine Learning - Volume 70_ , ICML’17 (JMLR.org, 2017) p. 3067–3075.
  * McClean  _et al._ [2018] J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven, Barren plateaus in quantum neural network training landscapes, Nat. Commun. 9, 4812 (2018).
  * Cerezo  _et al._ [2021] M. Cerezo, A. Sone, T. Volkoff, L. Cincio, and P. J. Coles, Cost function dependent barren plateaus in shallow parametrized quantum circuits, Nat. Commun. 12, 1791 (2021).
  * Salas [2008] P. J. Salas, Noise effect on grover algorithm, The European Physical Journal D 46, 365 (2008).
  * Wang and Krstic [2020] Y. Wang and P. S. Krstic, Prospect of using grover’s search in the noisy-intermediate-scale quantum-computer era, Phys. Rev. A 102, 042609 (2020).
  * Grimsley  _et al._ [2019] H. R. Grimsley, S. E. Economou, E. Barnes, and N. J. Mayhall, An adaptive variational algorithm for exact molecular simulations on a quantum computer, Nat. Commun. 10, 3007 (2019).
  * Zoph  _et al._ [2018] B. Zoph, V. Vasudevan, J. Shlens, and Q. V. Le, Learning transferable architectures for scalable image recognition (2018), arXiv:1707.07012 [cs.CV] .
  * Bilkis  _et al._ [2021] M. Bilkis, M. Cerezo, G. Verdon, P. J. Coles, and L. Cincio, A semi-agnostic ansatz with variable structure for quantum machine learning (2021), arXiv:2103.06712 [quant-ph] .
  * Rattew  _et al._ [2020] A. G. Rattew, S. Hu, M. Pistoia, R. Chen, and S. Wood, A domain-agnostic, noise-resistant, hardware-efficient evolutionary variational quantum eigensolver (2020), arXiv:1910.09694 [quant-ph] .
  * Zhang  _et al._ [2020] S.-X. Zhang, C.-Y. Hsieh, S. Zhang, and H. Yao, Differentiable quantum architecture search (2020), arXiv:2010.08561 [quant-ph] .
  * Du  _et al._ [2020] Y. Du, T. Huang, S. You, M.-H. Hsieh, and D. Tao, Quantum circuit architecture search: error mitigation and trainability enhancement for variational quantum solvers (2020), arXiv:2010.10217 [quant-ph] .
  * Ostaszewski  _et al._ [2021] M. Ostaszewski, E. Grant, and M. Benedetti, Structure optimization for parameterized quantum circuits, Quantum 5, 391 (2021).
  * Skolik  _et al._ [2021] A. Skolik, J. R. McClean, M. Mohseni, P. van der Smagt, and M. Leib, Layerwise learning for quantum neural networks, Quantum Machine Intelligence 3, 5 (2021).
  * Aleksandrowicz  _et al._ [2019] G. Aleksandrowicz _et al._ , Qiskit: An Open-source Framework for Quantum Computing (2019).
  * Shende  _et al._ [2006] V. Shende, S. Bullock, and I. Markov, Synthesis of quantum-logic circuits, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 25, 1000 (2006).
  * Qiskit [2021] Qiskit, Proving universality (2021).
  * Ruder [2017] S. Ruder, An overview of gradient descent optimization algorithms (2017), arXiv:1609.04747 [cs.LG] .
  * Schuld  _et al._ [2019] M. Schuld, V. Bergholm, C. Gogolin, J. Izaac, and N. Killoran, Evaluating analytic gradients on quantum hardware, Phys. Rev. A 99, 032331 (2019).
  * Bergholm  _et al._ [2020] V. Bergholm _et al._ , Pennylane: Automatic differentiation of hybrid quantum-classical computations (2020), arXiv:1811.04968 [quant-ph] .
  * Suzuki  _et al._ [2020] Y. Suzuki _et al._ , Qulacs: a fast and versatile quantum circuit simulator for research purpose (2020), arXiv:2011.13524 [quant-ph] .
  * Kingma and Ba [2015] D. P. Kingma and J. Ba, Adam: A method for stochastic optimization, in  _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_, edited by Y. Bengio and Y. LeCun (2015).
  * Powell [1964] M. J. D. Powell, An efficient method for finding the minimum of a function of several variables without calculating derivatives, The Computer Journal 7, 155 (1964).
  * Fletcher [1987] R. Fletcher,  _Practical methods of optimization_ , 2nd ed. (Wiley, 1987).


# Instability of computer vision models is a necessary result of the task
itself

Turnbull  Artefact Ltd.
4th Floor, 1 Lloyd’s Avenue London, EC3N 3DS  Oliver
<EMAIL_ADDRESS>Artefact Ltd.
4th Floor, 1 Lloyd’s Avenue London, EC3N 3DS  Čevora  Artefact Ltd.
4th Floor, 1 Lloyd’s Avenue London, EC3N 3DS  George
<EMAIL_ADDRESS>Artefact Ltd.
4th Floor, 1 Lloyd’s Avenue London, EC3N 3DS

###### Abstract

Adversarial examples resulting from instability of current computer vision
models are an extremely important topic due to their potential to compromise
any application. In this paper we demonstrate that instability is inevitable
due to a) symmetries (translational invariance) of the data, b) the
categorical nature of the classification task, and c) the fundamental
discrepancy of classifying images as objects themselves. The issue is further
exacerbated by non-exhaustive labelling of the training data. Therefore we
conclude that instability is a necessary result of how the problem of computer
vision is currently formulated. While the problem cannot be eliminated,
through the analysis of the causes, we have arrived at ways how it can be
partially alleviated. These include i) increasing the resolution of images,
ii) providing contextual information for the image, iii) exhaustive labelling
of training data, and iv) preventing attackers from frequent access to the
computer vision system.

In recent years, there has been growing concern of the impact of adversarial
examples on the reliability of computer vision systems, particularly those
using deep learning as their core inference engine. These adversarial examples
are small changes to an input image that results in a change of classification
label from the model. This can look like adding a small amount of noise to an
image of a pig and having it mislabelled as an airliner, or paint on the
outside of a gun to make it unrecognisable to any system looking to detect
dangerous weapons as shown in Figure 1. Many [10, 13, 9] researchers have
published work on algorithms to generate white box or black box with querying
adversarial examples, which begs the question: are computer vision algorithms
doomed to fail? Some researchers [8] have identified grounds for the existence
of adversarial examples among the features of deep neural networks. In this
paper we aim to make a much broader statement: that the existence of
adversarial examples is a necessary result of how computer vision problems are
formulated.

Evolution has been the source of early examples (chameleon, octopus, praying
mantis, etc), with humans later inventing camouflage. We argue that the
Adversarial Examples in the Deep Learning context are fundamentally the same
concept; as such the DL Adversarial Examples should not be seen as a problem,
but as a necessary result of perceptual systems optimised to differentiate
between distinct predetermined categories. It is the emphasis on accuracy
within the ML framework that is to blame, though, at the same time, we do
actually want accuracy.

Here we may want to distinguish between formal and computational instability
for our classification function $f$ and input space $\Omega$. Formal
instability being that for any $\epsilon>0$, we can find an $x\in\Omega$ such
that there exists $y\in B_{\epsilon}(x)$ where $f(x)\neq f(y)$, and we can
prove that these points exist for any finite label classification problem.
Computational instability is thus therefore making a similar claim, but
placing some other conditions on the $\epsilon$ chosen i.e. that it is larger
than some minimum resolution so that images only change label for some
“perceptible” change in input. In this latter case we can imagine that given a
sufficiently low measure boundary that given our change sizes a change in
output label is still acceptable to the classification problem. Neither of
these are necessarily an issue for any classification problem provided that
the region of “instability” is small; small in relation to measure. We would
like it to be the case that it is unlikely that an input picked at random
would be a formally or computationally unstable point.

(a) The original image of a pig gets misclassified by a machine vision system
as an airliner after an addition of faint (0.005x) but carefully crafted
noise-like overlay. [1]

(b) An actual assault rifle disguised as a toy. [5]

Figure 1: Adversarial Examples in machine vision are images that the system
misclassifies. Some of the examples such as 1(b) seem as reasonable errors to
humans, while others such as 1(a) are treated as indicative of inferiority of
machine vision systems to human vision.

##  1 The Computer Vision View

In this section we seek to establish a few key points. Firstly, that fractal
levels of instability can occur with even very simple convolution operations.
Secondly, that the manifold structure of our input space has fewer samples
closer to the boundary and so will necessarily fail at reproducing said
boundary. Thirdly, that nondifferentiable activation functions are partly
responsible for accelerating this problem, and fourthly that in spite of its
necessary existence, instability in a computer vision system is in some sense
a non-fundamental issue; i.e. as image resolution increases the effect becomes
less and less.

There are some specific considerations with regards to the structure of
computer vision systems. In particular, we take the view that computer vision
systems are essentially feature extractors for the input image, and these
features represent the semantic content of the image, which is then used as
the actual space where the categorical decision is made. This can be done as
simply dimensionality reduction on the raw image pixel values, or something
like a convolutional neural network where geometrically local dimensions of
input feature space are used to constrain how the features get generated.
There are thus three places where instability can arise; firstly in the input
space itself, secondly in the manifold-feature representation of the input
space, and thirdly in the mapping from the feature space to the output space
(usually a classification). The problems with the input space we will come
back to later, but in this first section we will talk about how feature
extraction and feature mapping- particularly in convolutional neural networks,
provide the opportunity for instability to occur.

###  1.1 Feature Entanglement

Here we wish to define the type of instability that we consider to be unique
to computer vision and particularly convolutional neural network classifiers,
and reason about this from a highly simplified lens. We informally define
features of a classifier as entangled if there is little distance from the
region of one feature’s highest expression to the other. Examples of this
might be one feature’s highest expression having points dense in another
region, or pseudodense to some tolerance $\epsilon$. It has been be shown [11]
that any kind of feature extraction on images can identify ‘fragile’ features;
features that correlate with output label at a point but not everywhere in a
neighbourhood around this point.

Though, indeed, fragile features can arise from even very simple types of
filtering. If instead of a componentwise product followed by a pooling
operation (as is the case with the filters in neural networks) we take an L1
similarity measure we can observe something like figures 2(a) and 2(b). Here
we have taken the similarity to the vectors $(1/2,1/2),(2/3,1/3),(1/3,2/3)$
and $(1/4,3/4)$ as our filtering, taking the argmax of the dot product of the
grid point coordinates with these given tuples. The colour shows which of
these is the max value.

(a) Result of the filtering over unit space.

(b) Subsection of the unit space showing clear instability resulting from the
filtering.

Figure 2: Demonstration of instability resulting from simple filtering. Four
vectors used for filtering are $(1/2,1/2),(2/3,1/3),(1/3,2/3)$ and
$(1/4,3/4)$. The vector with lowest L1 norm between itself and a given point
in space was selected as a ”winner” and determine the colour of the point. It
is apparent that even such simple filtering produces a great level of
instability.

In this, we see not just a computational instability but a true unstable
region; where points of different highest feature expressions are dense in
each other; any neighbourhood of a point here will contain another point of
different highest feature expression.

Maxpooling will create the exact kind of undifferentiability as generated in
the L1 filtering, suggesting an inherent tendency to regions of high
instability along any one particular feature axis apply to most current CNNs.
While the features embedded in a higher dimensional feature space as they are,
may not exhibit the same behaviour in conjunction with one another. We will
see a similar effect from softmaxing at the final layer, which is a smooth
approximation to an L1 max function. This will asymptotically approach the
behaviour observed in figure 2(a) as the number of labels predicted and or
temperature of the softmax increase.

###  1.2 Feature extraction as manifold learning; distribution gradients

Similarly to Ilyas [11], we define the classification problem in general as
follows

$C(x)=\textrm{sign}\bigg{(}b+\sigma\Big{(}\sum_{i=0}^{n}w_{i}f_{i}(x)\Big{)}\bigg{)}$
(1)

for some feature map $\vec{f}$. This feature map is a dimensionality reduced
representation of the data, with the goal of learning a statistical manifold
paramaterised by the components of $\vec{f}$ (in a geometric rather than
statistical sense). The final layer, therefore, is an attempt to learn the
statistical parameters of the distribution at each point; in this case the
parameterising probability of a Bernoulli distribution at each $x$.

The idea is thus that these statistical parameters vary continuously across
the manifold; with instability being generated by steep gradients in
neighbourhoods of certain points in the image of $\vec{f}$. If $C$ is
continuous on $\mathbb{R}^{n}\supseteq\mathcal{M}\rightarrow[0,1]$, and the
classification problem is sharply defined, then we will expect the classifier
to have steep gradients at the true boundary. If, as is more likely the case,
the problem is not sharply defined (i.e. not every image is a definite yes or
no) we may still be finding adversarial examples, depending on the number of
labels relative to the dimensionality of input and density of data.

###  1.3 Entanglement as a property of Translational Invariance and Feature
Equivariance

There is an important property of computer vision problems and their solution
space that could give us a clue as to why, in practice, there are many regions
of instability in algorithms that approximate the true boundary. Let us
consider the $m\times n\times 3$ grid of pixels that gets processed by machine
learning systems; we can think of the problem space as a classification
problem on $\mathbb{R}^{3mn}$ that has to preserve labelling under a number of
permutations. For a classification space
$\mathcal{C}\subset\mathbb{R}^{k}\times[0,\;1]$ we call the set (in this
particular case actually a group) of permutations on the components of
elements of $\mathbb{R}^{k}$ that preserve labelling
$\textrm{Inv}(\mathcal{C})$. For standard computer vision problems, this set
contains grid translations, reflections and rotations each of which can be
parameterised by at most two vectors (in this case grid coordinates) meaning
the size of $\textrm{Inv}(\mathcal{C})$ is $O((mn)^{2}))$.

Let us take some element of the input space $y\in\mathbb{R}^{3mn}$ with our
classification function (true or otherwise!) $f$, then we know the set of all
images of $y$ under some invariant transformation is the same size as the set
of all transformations:
$|\\{\alpha(y):\alpha\in\textrm{Inv}(\mathcal{C})\\}|=|\textrm{Inv}(\mathcal{C})|=O((mn)^{2})$,
an order parameter for the size of this set that will come in useful later.
Suppose $y$ is $\epsilon$-close to our classification boundary i.e. that a
ball of size $\epsilon$ will fit entirely within the classification subspace
of $y$ or mathematically, $f(B_{\epsilon}(y))=\\{f(y)\\}$. Then we must also
have

$f(\\{\alpha(x):\alpha\in\textrm{Inv}(\mathcal{C}),\;x\in
B_{\epsilon}(y)\\})=\\{1\\}$

You can think of this as taking a little ball entirely inside the input space
and seeing all its locations under each transformation that we know preserves
classification, so we end up with a collection of possibly overlapping balls
in the input space for which every point inside has the same classification,
chosen here to be $1$ WLOG. If we now consider $z\in f^{-1}({0})$ then we
know, if we call
$\mathcal{X}=\\{\alpha(x):\alpha\in\textrm{Inv}(\mathcal{C}),\;x\in
B_{\epsilon}(y)\\}$ that $z$ is $\nu$-close to the boundary where
$\nu=\textrm{min}(\\{|z-x|:x\in\mathcal{X}\\})$, with the immediate result
that $\nu\leq|z-y|$. What this means is that as the dimension of the input
space (in this case resolution of the image) increases, we get more
transformations on our input space that preserve labeling and so more points
that could be closer to the boundary than a given known classification point;
adding to the instability of our problem.

However, if we take a standard result from measure theory [12], we know that
if $B_{\epsilon}(y)\subset\mathbb{R}^{k}$, then

$\textrm{Volume}(B_{\epsilon}(y))=\frac{\pi^{k/2}}{\Gamma(\frac{k}{2}+1)}\epsilon^{k}$

So the volume of our set under our group actions becomes

$\textrm{Volume}(\mathcal{X})\leq|\textrm{Inv}(\mathcal{C})|\frac{\pi^{k/2}}{\Gamma(\frac{k}{2}+1)}\epsilon^{k}$

Immediately we see that the volume of this set tends to zero so long as
$|\textrm{Inv}(\mathcal{C})|\frac{\pi^{k/2}}{\Gamma(\frac{k}{2}+1)}|\rightarrow
0$, and so even though the number of unstable points increases, the
probability of falling within $\epsilon$ of one of these points tends to 0.
Since we know that for computer vision problems, we have
$|\textrm{Inv}(\mathcal{C})|\in O((mn)^{2})=O(k^{2})$, then we are happy that
we are not likely to fall within $\epsilon$ of a given boundary point.

Of course, we do not have just one point $\epsilon$-close to our boundary, but
we do have that our total measure will be bounded by integrating over a ball
of radius $\epsilon$ for each point on the boundary. But it is important to
note that in the context of computer vision, we have maximum and minimum
intensities of pixel values, meaning our input space is restricted to
(something homeomorphic to) the unit cube and as such the total measure will
be bounded by 1, so we can reason directly from our ratio still. This tells us
that while there may be an inherently greater level of instability in the
instance of computer vision problems than others, under a high enough
resolution this effect becomes small.

This then gives us an interesting extension; while the classes of symmetries
are sufficiently small for computer vision problems that this isn’t an issue,
this becomes an issue for problem spaces with a higher degree of permutation
invariance, namely, graph neural networks. In such cases, our bound (given the
number of permutations is $k!$) does not tend to 0, which suggests it is
possible to cover our entire input space with neighbourhoods of unstable
points and their neighbourhoods under transformations.

We can also apply this argument to symmetries that exist within a classifier
i.e. that softmax of the feature layer is itself invariant under permutation.
The preimages of these feature vectors will in turn be responsible for many
$\epsilon$-balls in input space and as such increase the instability of the
space. Let us take a feature vector $\vec{f}$ as the output of some classifier
layer between the input and output spaces. If the input space is $k$
dimensions and the output space is $r$ dimensions then we can expect each
$\vec{f}$ to correspond to on average $\frac{k}{r}$ points in input space. So
in the case $\vec{f}$ is $\epsilon$-close to the decision boundary in feature
space, it corresponds to both $r$ points in feature space thus and
$r\frac{k}{r}=k$ points in input space, giving us another polynomial degree
term in our total measure calculation, preserving its tending to $0$.

###  1.4 Conclusion

We have established that while adversarial examples that arise from symmetries
of a particular problem or classification algorithm do exist, their proportion
in relation to points further away from the boundary shrinks to zero
eventually. Moreover, this kind of symmetric analysis can be used to analyse
all kinds of neural network architectures, namely where we see that for graph
neural networks (which have a much larger space of classification-invariant
transformations) that no such limiting process exists and the probability of
finding an adversarial example may tend to 1 as the input space gets bigger in
dimension.

Presence of adversarial examples, however, does not present a problem per se.
It is the ability of hostile actors to find them that causes practical issues.
The current methods of finding adversarial examples require either access to
the machine vision system itself or ability to query it repeatedly. A simple
protection from adversarial attacks is therefore denying access to the system
itself for potentially hostile actors. If a machine vision system in question
is required to be exposed to public, via interface such as an API the solution
is to prevent hostile actors from performing sufficient number of queries to
find adversarial examples - for instance by API throttling.

##  2 The Categorical View

Beyond the behaviour of the mathematical and computation models of image
recognition, we have the behaviour of classification algorithms more
generally. Here we will explore some of the limitations of any kind of
categorisation problem on certain classes of spaces, outside of the specifics
of the algorithm, problem subspace, or type of data. We will establish that
instability in a formal sense will always occur in any continuous
classification problem, when this instability becomes a problem in practice,
and to what extent we can foresee and interrupt situations where it may be a
problem by looking at the structure of the spaces used in these problems. We
will finish with a brief philosophical discussion of the relationship between
an object and its image, and how this relationship might affect systems built
to recognize objects from images.

It can be shown that for any compact topological space (which we discuss in
the appendix), a continuous map from it to a discrete set of values means that
there will either be an image mapped to more than one label, thus the
resulting map is not a function, or that there is a point mapped to no label.
Since we are presuming the former never occurs, i.e. our output is repeatable
and not stochastic, there must be points that are not mapped to either label;
the set of such points we call the boundary of our classification problem. If
we add metric structure to the compact topological space, then we know that
there will exist non-boundary points close to these boundary points,
necessitating the existence of unstable points (again, this can be justified
with a short proof). When we talk about stable classifiers in a formal sense
(a small change in input corresponds to a small change in output) we mean they
are are continuous in a topological sense.

The presence of adversarial examples does not necessitate instability in the
colloquial sense: the presence of a classification boundary necessitates the
existence of points epsilon-close to that boundary. Instead for practical
reasons we are concerned about far-deviations from emphcalibrated probability
guesses near the boundary - i.e. being certain when the result is certain and
uncertain when not.

###  2.1 Humans are No Better

However, beyond the problems with classification in general, we must
understand that this problem is situated under comparison with humans. It is
not simply that we want to understand classification instability in the
abstract, which is its own necessity, but that we want classification to be
unstable in exactly the same way as human classification is. While this notion
is rarely spelled out in the literature, it seems to underpin the wider
discussion of the topic.

(a) Is it a dog or is it a muffin? [2]

(b) Is it a dog or is it fried chicken? [3]

Figure 3: While the topic of adversarial examples is rarely related to human
vision it is useful to realize _visual illusions_ can be considered
adversarial examples to human vision system.

As demonstrated in figure 3 humans too have regions of indeterminacy where
small changes to the input features change confidence in labeling i.e. our
calssification boundary is not measure 0 either. This gives us a kind of hedge
against the embarrassment of computer vision systems; human errors in
classification are considered a natural feature of our visual system while
machine vision errors are considered failures at the task.

Yet, for some reason, we have a sense that humans, in their image
classifications, do not have the same problem of instability as we would not
change our labelling from an obvious example to the opposite label with a
small perturbation. Of course, any classifier (humans included!) will have
unstable points. However, we believe that our unstable points are in some
sense better than the examples such as the pig/airliner adversarial example
shown in figure 1(a).

We know that one model’s string classification could easily be another model’s
edge case; indeed that where decision boundaries fall can be very different
even when very similar around the training points. However, we also have a
sense of intelligibility about the content of an image (nonzero measure
boundary).

Consider the case where two classifiers are competing over an image containing
both cat and dog, one classifying the image as a cat, the other one as a dog.
Which of these is the correct classification of an image containing both? The
problem arises when our algorithms have been trained on single label images
only. In order for our labelling to be as accurate as possible we require that
we know when images of pigs do not have airliners in them and vice verse so
that we can capture these sorts of relationships that might appear. But this
is not representative of the datasets used in pracitce. If we treat each image
as only containing one thing, then we may be introducing instability where
there isn’t really any at all. This prompts a nice solution in first
specifying your ontology (collection of all possible labels) and training
classifiers on the images simultaneously, so that the statistical noise in
other classifiers (that may pick up on some significant feature here or there
in the background of an image) do not counteract the presence of other objects
or features in the image.

###  2.2 Ceci n’est pas le sujet

One last point to mention, a subtle but important one, is that the image of
something is not the thing itself. In our classification problem we are trying
to construct a probability distribution for an image coming from a thing we
are labeling, but the object of our classification is ultimately a photograph
of that thing - concept discussed by René Magritte in his seminal painting
Trechery of the images shown in Figure 4. Thus we fail to capture the full
range of features that might determine a classification and allow for
completely different features to be flattened into very similar
representations (such as wings and ears being similar in images but very
different in real life). The most common example of this is scale; an image is
often composed so that the object of it is at the center; meaning that the
classification of that object does not take into account the size of the
object itself, or the other objects it is surrounded by.

Figure 4: The treachery of images is a 1929 painting by René Magritte. [6] It
is generally understood to point out that the painting is not the painted
object itself.

The image presupposes a framing and a context that may create similarity
between two actually very different scenes. The image itself is just an image,
and so any instability in the classification may come from a fundamental
underparamaterisedness of the problem for computer vision; the classifiers do
not understand the relationships between the things they are trying to
predict; they have no understanding of, to use an earlier example, the
relation between pigs and airliners, they simply identify statistically
significant features of them each. In a similar sense, the number of possible
three-dimensional scenes that could give rise to a given image is potentially
infinite; objects occluded by foreground objects could be anything, meaning
always vital context that would come from the exploration of the object in the
same space humans experience it is lost when a photograph is captured. The
image could be of a deceptive actor holding up an image of something else to
the camera, even occluding the camera’s view altogether, meaning the supposed
true nature of the image (that it is of a person holding a piece of paper) is
lost entirely to the viewer of the image (both human and algorithm, since
there cannot be a distinction between replication of an image and an image
representing a real thing - especially digitally, where all images are copies
in some sense).

Herein lies what you might call a hubris of prediction; that the most likely
thing is always the _object of belief_. This term is a kind of frequentist
bastardisation of Occam’s razor; that the image represents an actual fixed and
determinate thing rather than a probability distribution over all possible
things, situations, known unknowns and unknown unknowns. To the contrary, this
inherent uncertainty and indeterminacy in the image, and in some sense all
problems of prediction, is something we must take into account when deciding
action on the basis of prediction. In practice if systems such as weapon
detection computer vision systems aren’t treated with the appropriate
epistemic humility, then the consequences for both harm reduction as well as
the impact on peoples’ lives could be severe. Instability exists in computer
vision in part at least because vision itself is unstable; what we see and
what we interpret from what we see is not always the truth. We must build in
contingency for the random failures that always occur in technological
systems, both machine learning and traditional if we ever want these systems
to be functional in a complex, imperfect, and fluctuating world. As
Baudrillard, a philosopher of simulacra and images said in [7]

> “I would like to conjure up the perversity of the relation between the image
> and its referent, the supposed real; the virtual and irreversible confusion
> of the sphere of images and the sphere of a reality whose nature we are less
> and less able to grasp. There are many modalities of this absorption, this
> confusion, this diabolical seduction of images. Above all, it is the
> reference principle of images which must be doubted, this strategy by means
> of which they always appear to refer to a real world, to real objects, and
> to reproduce something which is logically and chronologically anterior to
> themselves. None of this is true. As simulacra, images precede the real to
> the extent that they invert the causal and logical order of the real and its
> reproduction.”

In the computer vision system, we presuppose no distinction between real
subject and image, meaning that an image of an image as depicted in figure 5
or 4 can never be depicted from simply an image since the image is never made
distinct from its subject.

Figure 5: Machine itself is fooled by the image demonstrating the
impossibility to distinguish between object and its depiction purely from a
single snapshot. [4]

We must understand the image as a lower dimensional representation of what it
represents not only literally (two dimensional rather than three) but also
conceptually; the stop sign exists in relation to a road, it has different
forms in different countries, it has a material that it is made of and is only
placed at specific places on the road. Without this categorical information,
the image classification algorithm is already working at a far lower
dimensionality and with far less data than any live animal let alone a human,
and to truly increase its resolution enough to compete with a human’s vision
it will need to include these conceptual dimensions as well, not just spatial
and colour ones. Not only this but these extra dimensions reduce the
symmetries in the problem, meaning destabilisation can occur at lower
dimensions; a form of categorical regularisation.

In conclusion we understand instability as arising from a lack of context for
an image, from the fact that by the framing of the task, the image of the
thing is identical to the thing itself, and that adding context amounts to
increasing the dimensionality of the problem and removing possible symmetries
from the input space at the same time.

##  3 Conclusion

The framing of computer vision instability we have established offers some
interesting protections against the types of adversarial attacks we see in
practice, as well as establishes some a priori limits on the efficacy of these
attacks. Specifically protection from adversarial attacks can be increased
through:

  * •

Increasing the resolution of images.

  * •

Providing contextual information for the image.

  * •

Exhaustive labelling of training data.

  * •

Preventing attackers from frequent access to the system.

###  3.1 Is this behaviour undesirable?

If we ever want computer vision systems to not only replicate but outperform
human classification, we will need them to identify ever more fragile and
esoteric features of the data. These are features that are statistically
significant at some point in feature-space but fall off quickly in a
neighbourhood of that point. Our primary concern is that these don’t happen in
commonly acceptable regions of input space. We don’t have any way of
visualising what the true boundary of these classification spaces is, and our
ground truth labelling is always provided by humans in some way anyway. Not
only this, but computer vision systems must have contingencies for the ways in
which images inherently fall short of representing the object of the image,
which are precisely where these fragile features will arise. This is, however,
lucky for computer vision. Other types of data have a degree of symmetry much
higher than an image, such as a graph, for which there is not always a clear
way to increase its resolution but further that even if there were this would
increase the instability inherent in the problem.

###  3.2 Further steps

In this article, we have shown that in many ways instability is inevitable. We
have also shown that there are types of problems that by virtue of symmetry in
the problem lend themselves to instability, and propose this as a tool for
analysing many other machine learning tasks and algorithms. Further to this,
we have tried to understand the inclusion of extra data in these problems as a
way of breaking symmetries of the problem, thus making both the problem and
associated algorithms more stable. We can do this through understanding that
the images of our classifications may cover a range of phenomena (such as the
”image-of-image” as described earlier, and that our outputs could be
distributional or Bayesian in nature. In the future, we must make sure that
our detection or regression algorithms take place at a discriminative enough
resolution, and that epistemic uncertainly in build into the output
distributions that lay the foundations for our ”predictions of truth”,
predictions always predictaed on risk.

## References

  * [1] https://gradientscience.org/intro_adversarial/.  Accessed: 10. 7. 2023.
  * [2] https://medium.com/@cristianduguet/chihuahua-or-muffin-38560baf629d.  Accessed: 10. 7. 2023.
  * [3] https://metro.co.uk/wp-content/uploads/2014/08/fried-chicken-dogs.jpg?quality=90&strip=all&w=600&h=600&crop=1.  Accessed: 10. 7. 2023.
  * [4] Capatcha refuses to recognise image of traffic light not as traffic light.  https://twitter.com/ThatsMauvelous/status/1576675184165068800.
  * [5] North carolina: Police seize real gun disguised as nerf toy during drug raid.  https://news.sky.com/story/north-carolina-police-seize-real-gun-disguised-as-nerf-toy-during-drug-raid-12253885.  Accessed: 10. 7. 2023.
  * [6] The treachery of images.  https://en.wikipedia.org/wiki/The_Treachery_of_Images#/media/File:MagrittePipe.jpg.
  * [7] Jean Baudrillard.  The evil demon of images.  3:11, 1984.
  * [8] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples.  arXiv preprint arXiv:1412.6572, 2014.
  * [9] Warren He, Bo Li, and Dawn Song.  Decision boundary analysis of adversarial examples.  In International Conference on Learning Representations, 2018.
  * [10] Andrew Ilyas, Logan Engstrom, Anish Athalye, and Jessy Lin.  Black-box adversarial attacks with limited queries and information.  CoRR, abs/1804.08598, 2018.
  * [11] Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry.  Adversarial examples are not bugs, they are features.  2019\.
  * [12] David J. Smith and Mavina K. Vamanamurthy.  How small is a unit ball?  Mathematics Magazine, 62(2):101–107, 1989.
  * [13] Han Xu, Yao Ma, Hao-Chen Liu, Debayan Deb, Hui Liu, Ji-Liang Tang, and Anil K. Jain.  Adversarial attacks and defenses in images, graphs and text: A review.  International Journal of Automation and Computing, 17(2):151–178, March 2020.

##  4 Appendix

######  Definition 1.

Strict Classifier

We say a classifier is strict if its output space is discrete. Thus, a
classifier is non-strict if it outputs a continuous variable (i.e. a
probability $p\in[0,\;1]$)

######  Definition 2.

Stability

We say a strict classifier $f$ is stable on an input space $\Omega$ if

$\displaystyle\forall x\in\Omega,\;U\in\mathcal{T}(\Omega),\;x\in U:\;\exists
V\subset U\;\textrm{s.t.}\;x\in
V,\;V\in\mathcal{T}(\Omega)\;\textrm{and}\;f(V)=\\{f(x)\\}$

i.e. every point has an open neighbourhood that does not change label

An immediate is that a strict binary classifier can only be stable on a
disconnected topological space, meaning if your input space is connected there
must be some points that will change label in a neighbourhood under any
perturbation. This is by the topological definition of continuity which says:

######  Definition 3.

(Continuity): We say a mapping $f:X\rightarrow Y$ is continuous if whenever
$U$ is an open set in $Y$ then $f^{-1}(U)$ is open in $X$

We see that a classifier is stable if it is continuous on $\\{0,\;1\\}$ in the
topology where $\\{0\\}$ and $\\{1\\}$ are open sets, and so you could express
$\Omega$ as the union of two nonintersecting open sets:
$f^{-1}(\\{0\\})\bigcup f^{-1}(\\{1\\})$. We show these are nonintersecting by
taking for all $x\in\Omega$ a $U_{x}\in\mathcal{T}$ such that
$f(U_{x})=\\{0\\}$. Then we see $f^{-1}(\\{0\\})=\bigcup_{x\in\Omega}U_{x}$
since it contains and is contained by it, since we have used every $x$ that
gets mapped to $0$ in our construction and no element is mapped to $1$ by the
property of it being stable.

This is not the case in soft classification. In soft classification we can
define stability formally as $f$ being continuous. This is, perhaps, an overly
strict definition of stability for the case of computational tractability,
where we often have a minimum resolution changes can be seen at meaning that
even if a function is technically continuous it will appear discontinuous when
viewed at this level (in some sense no computational approximation is ever
continuous, but we can observe the size of changes given a minimum resolution
change). we can define this as follows (as in [11]);

######  Definition 4.

$\rho$-useful

For a given distribution $\mathcal{D}$, we call a feature $f$ $\rho$-useful
($\rho>0$) if it is correlated with the true label in expectation, that is if

$\displaystyle\mathbb{E}_{(x,y)\sim\mathcal{D}}[y\cdot f(x)]\geq\rho$ (2)

We then define $\rho_{\mathcal{D}}(f)$ as the largest $\rho$ for which feature
f is $\rho$-useful under distribution $\mathcal{D}$.

######  Definition 5.

$\gamma$-robustly useful

Suppose we have a $\rho$-useful feature $f(\rho_{D}(f)>0)$. We refer to $f$ as
a robust feature if, under adversarial perturbation, f remains
$\gamma$-useful. Formally, if we have that

$\displaystyle\textrm{inf}_{\delta\in\Delta}\mathbb{E}_{(x,y)\sim\mathcal{D}}[y\cdot
f(x+\delta)]\geq\gamma$ (3)