# Structure Learning of Quantum Embeddings

<EMAIL_ADDRESS>Francesco
Martinihttps://orcid.org/0000-0003-2651-140X Alessandra Di
Pierrohttps://orcid.org/0000-0003-4173-7941 *

###### Abstract

The representation of data is of paramount importance for machine learning
methods. Kernel methods are used to enrich the feature representation,
allowing better generalization. Quantum kernels implement efficiently complex
transformation encoding classical data in the Hilbert space of a quantum
system, resulting in even exponential speedup. However, we need prior
knowledge of the data to choose an appropriate parametric quantum circuit that
can be used as quantum embedding. We propose an algorithm that automatically
selects the best quantum embedding through a combinatorial optimization
procedure that modifies the structure of the circuit, changing the generators
of the gates, their angles (which depend on the data points), and the qubits
on which the various gates act. Since combinatorial optimization is
computationally expensive, we have introduced a criterion based on the
exponential concentration of kernel matrix coefficients around the mean to
immediately discard an arbitrarily large portion of solutions that are
believed to perform poorly. Contrary to the gradient-based optimization (e.g.
trainable quantum kernels), our approach is not affected by the barren plateau
by construction. We have used both artificial and real-world datasets to
demonstrate the increased performance of our approach with respect to randomly
generated PQC. We have also compared the effect of different optimization
algorithms, including greedy local search, simulated annealing, and genetic
algorithms, showing that the algorithm choice largely affects the result.

###### keywords:

Quantum Kernel, Quantum Embedding, Quantum Machine Learning, Quantum
Computing, Quantum Optimization, Kernel Optimization, Simulated Annealing,
Genetic Algorithms

[1]Massimiliano Incudinihttps://orcid.org/0000-0002-9389-5370

[1]Dipartimento di Informatica, Università di Verona, Verona, 34137, Italy

##  1 Introduction

Quantum machine learning biamonte2017quantum  aims to exploit the properties
of quantum computation to improve the performances of machine learning models
in terms of speed or accuracy. Early works have aimed to find strong, rigorous
speedup based on the HHL algorithm for matrix inversion harrow2009quantum , a
building block for many algorithms such as the quantum SVM
rebentrost2014quantum  and quantum PCA lloyd2014quantum ; or to find
topological properties of data lloyd2016quantum . These approaches require
reliable quantum hardware, severe assumptions on the data (e.g. sparsity),
aaronson2015read  and the use of QRAM giovannetti2008quantum , a hypothetical
hardware device that allows efficient access to a quantum state. Recent works
have been focused on NISQ-ready algorithms preskill2018quantum , i.e.
algorithms that can be run on noisy quantum devices with a limited number of
qubits. The most notable techniques are the variational quantum algorithms
cerezo2021variational  such as VQE peruzzo2014variational  and QAOA
farhi2014quantum ; zhou2020quantum  exploiting both quantum and classical
hardware to solve material-related and combinatorial optimization problems,
and Quantum Neural Networks abbas2021power  to solve supervised learning
tasks. Among these techniques, quantum kernels havlivcek2019supervised  are
one of the most promising.

Quantum embedding and quantum kernels are powerful data analysis techniques
that allow us to define non-linear predictors through the encoding of
classical data into a quantum system. The use of (classical) kernel methods in
machine learning shawe2004kernel ; hofmann2008kernel  has found applications
in many field of science including biology scholkopf2004kernel , chemistry
ralaivola2005graph  and physics karniadakis2021physics . Most kernel methods
algorithms such as Ridge Regression and kernel PCA are based on convex
optimization and thus are efficiently solvable on classical hardware. Kernel
methods use positive definite, symmetric functions to encode data points into
a Reproducible Kernel Hilbert Space (RKHS). Quantum kernel naturally arises
from the similarity between the RKHS and the Hilbert space of the quantum
system: each parametric quantum transformation that encodes the data within a
quantum state is an embedding function schuld2021supervised , and taking the
inner product between quantum states encoding the data points (eg. through the
swap test gottesman2001quantum  or the fidelity measure) implements a kernel
function.

Quantum kernels are a well-studied algorithmic technique. The use of quantum
kernel can lead to an exponential speedup over classical machine learning
algorithms on artificially generated tasks liu2021rigorous . They have been
used to efficiently classify group-structured data glick2021covariant  and to
predict properties of quantum systems Huang2021 . In Huang2021 , the concept
of _projected_ or _biased_ quantum kernel is introduced, which first exploits
the high-dimensional Hilbert space of the quantum system to perform complex
transformations, then projects the states into a low-dimensional subspace to
mitigate the curse of dimensionality. The approach requires prior knowledge to
choose a favorable projection. In kubler2021inductive , expressible quantum
transformations are introduced, which are able to spread vectors all over the
Hilbert space, and are shown to lead to machine learning models that can learn
no function. Almost-constant transformations are the only ones capable to
generalize. In canatar2022bandwidth , it is suggested that a good
generalization is obtained by limiting the angle of parametric rotational
gates using a tunable hyper-parameter called bandwidth. The problem of
expressibility of quantum transformations holmes2022connecting  is closely
related to the barren plateau mcclean2018barren  in quantum neural networks,
in which the variance of the gradient vanishes exponentially in the system
size, preventing learning. An effect similar to the barren plateau happens in
quantum kernels when the non-diagonal coefficients of the kernel matrix are
concentrated around a single value thanasilp2022exponential , with variance
decreasing exponentially in the system size. It has been shown in
larocca2021diagnosing  that the choice of generators of the quantum
transformations greatly affects the expressibility of the model.

In this work, we deal with the problem of deciding the structure of quantum
transformations in the form of the parametric quantum circuit (PQC,
mitarai2018quantum ) without any prior knowledge of the problem data to guide
the choice. The lack of prior knowledge is a common situation for most real-
world datasets. The works in glick2021covariant ; lloyd2020quantum  propose
trainable quantum embeddings, i.e. PQC parameterized both by the data point
features and some trainable angle, which can be learned through gradient-
descent based algorithm to minimize some loss function. Such an approach still
requires prior knowledge to decide the structure of the transformation, and
the barren plateau might prevent the optimization. altares2021automatic  has
pioneered the use of genetic algorithms to place random gates automatically.
However, the latter approach has an expensive optimization procedure that
penalizes non-local gates, leading to circuits having only local operation and
being therefore classically simulatable. Another work chen2022genetically  has
improved the optimization by penalizing the circuit length. A similar approach
has been proposed in huang2022robust  by using variational quantum algorithms.

In our work, we model the problem of choosing the best structure for the PQC
of the quantum kernel as a combinatorial optimization problem. The structure
of the circuit has a fixed number of gates, avoiding the need for a circuit
length penalty. The structure of the circuit can be optimized using any meta-
heuristic such as greedy local search, simulated annealing, and genetic
algorithms. The principal objects of our optimization are the generators of
the gates. As shown in larocca2021diagnosing , these generators largely
influence the expressibility of the circuit. Any combinatorial optimization
process is computationally expensive. To lower this computational cost, we
have introduced an efficient policy to evaluate candidate solutions, based on
the exponential concentrations of inner products around the average value
thanasilp2022exponential . In contrast to the gradient-descent-based approach,
our optimization does not suffer from the barren plateau problem by
construction and leads to solutions that are not affected by unfavorable
numerical properties. We have tested our approach on several real-world and
artificial datasets. In particular, we have used greedy local search,
simulated annealing, and genetic algorithms to optimize our PQC. Finally, we
have compared our results with those obtained with other stochastic-based
techniques for designing quantum embedding.

##  2 Background

Consider the regression setting where we are trying to learn the function $f$
such that $Y=f(X)+\epsilon$, where random variable $X$ having domain
$\Omega\subset\mathbb{R}^{d}$ and probability distribution $\mu$, and
$\epsilon$ represents noise sampled from a Gaussian distribution having zero
mean. Consider the set of observations $\\{(x^{(i)},y^{(i)})\\}_{i=1}^{n}$
where $x^{(i)}$ is i.i.d. sampled from $\mu$ and
$y^{(i)}=f(x^{(i)})+\epsilon$.

###  2.1 Kernels Methods, and their Spectral and Probabilistic Properties

Kernel methods shawe2004kernel  generalizes the notion of similarity between
data samples, allowing the definition of predictors that are nonlinear in
$\Omega$. A Mercer kernel $k:\Omega\times\Omega\to\mathbb{R}$ is positive
definite and symmetric. Kernel methods can be used to enhance most similarity-
based algorithms: Kernel Ridge Regression murphy2012machine  (KRR) is a
generalization of the linear regressor, in the form

$\hat{f}(x)=\sum_{i=1}^{n}\alpha_{i}k(x^{(i)},x)\qquad\alpha_{i}=\sum_{j=1}^{n}((k(x^{(i)},x^{(j)})-\lambda))^{-1}y_{j}$
(1)

where $\lambda>0$ is the regularization term that penalizes higher norm
solutions, avoiding overfitting of noise. The predictor minimizes the mean
square error. The Support Vector Machine cortes1995support  (SVM) defines a
similar predictor with lower memory consumption. Kernel Principal Component
Analysis scholkopf1998nonlinear  (K-PCA) finds the directions that best fit
the data in $\mathcal{H}$. The similarity between data points is completely
specified by the kernel matrix $K=[k(x^{(i)},x^{(j)})]_{i,j=1}^{n}$, which can
be rescaled such that $\Tr[K]=1$. The Mercer kernel $k$ allows the spectral
decomposition

$k(x,x^{\prime})=\sum_{i=1}^{\infty}\gamma_{i}\phi_{i}(x)\phi_{i}(x^{\prime})$
(2)

where $(\gamma_{i})_{i>0}$ is a sequence of non-increasing numbers and
$(\phi_{i})_{i>0}$ are orthonormal functions. These are the eigenvalues and
eigenfunctions of the integral operator

$T[g]=x\mapsto\int_{\Omega}k(x,x^{\prime})g(x^{\prime})d\mu(x^{\prime}).$ (3)

The eigenvalues of a finite kernel matrix $K$ approximate $(\gamma_{i})_{i>0}$
as $n\to\infty$ [x]. The study of eigenvalues is of paramount importance: for
example, scholkopf1998nonlinear  have used to identify the principal
components, and caponnetto2007optimal  to define lower bounds to the
approximation error between $f$ and $\hat{f}$, amini2021concentration  relates
it to the concentration of random kernel matrices around their mean. Note that
if the non-diagonal values of a single kernel matrix are highly concentrated
around its mean, the learning is made difficult and requires higher precision
to distinguish the distance between different pairs of points
thanasilp2022exponential . cristianini2001kernel  quantify the quality of
learning $f$ with the kernel $k$ using the target-kernel alignment

$A(k,g)=\frac{\langle k,g^{\otimes 2}\rangle}{\lVert k\rVert\lVert g\rVert}$
(4)

with $0\leq A(k,g)\leq 1$, the higher the better, and can be related to the
eigenvalue distribution too. It has been used to learn kernel functions
themselves cortes2012algorithms .

###  2.2 Parametric Quantum Circuits

Consider the Hilbert space $\mathcal{H}=(\mathbb{C}^{2})^{\otimes n}$ and the
group of unitary operators $\mathcal{U}$ acting on $\mathcal{H}$. A parametric
quantum circuit (PQC) mitarai2018quantum  is an family of unitary
transformations $U:[0,2\pi]^{LK}\to\mathcal{U}$ in the form

$U(\theta)=\prod_{\ell=1}^{L}\prod_{k=1}^{K}W_{k}\exp(-i\theta_{\ell
k}H_{k})V_{k}$ (5)

where $W_{j},V_{j}\in\mathcal{U}$ are arbitrary, non-parametric unitaries and
$H_{j}$ is the generator, i.e. traceless Hermitian matrix, which can be
expressed as the sum of products of Pauli matrices. The parameters $\theta$
can be optimized to minimize a cost function
$C(\theta)=\expectationvalue{U(\theta)OU^{\dagger}(\theta)}{0}$. The
optimization is possible if we do not encounter the barren plateau phenomena
mcclean2018barren : $\nabla_{\theta}C$ approaches zero exponentially fast with
respect to $n$, resulting in the lack of a gradient direction for the
training.

The expressibility of a PQC sim2019expressibility ; nakaji2021expressibility
is the ability of the PQC to generate pure states exploring all $\mathcal{H}$.
The expressibility can be quantified by comparing the distribution of states
$\mathcal{E}$ generated by $U(\theta)$ and the uniform distribution of states
(Haar random states) using the formula

$A=\int_{\text{Haar}}(\outerproduct{\phi}{\phi})^{\otimes
t}d\phi-\int_{\mathcal{E}}(\outerproduct{\psi}{\psi})^{\otimes t}d\psi.$ (6)

If $\lVert A\rVert_{\infty}\leq\varepsilon$ then $U$ is an
$\varepsilon$-approximate t-design. As $t$ grows, the distribution of state
approximates better than the Haar distribution. holmes2022connecting  has
defined an upper bound on the gradient magnitude given the expressibility of a
PQC: if the group of unitaries generated by $U(\theta)$ forms a 2-design, then
the variance of $\nabla_{\theta}C$ vanishes exponentially fast in $n$. The
lack of expressibility does not guarantee a large gradient magnitude: global
cost function cerezo2021cost  and noise wang2021noise  contribute to the
appearance of the barren plateau.

The expressibility of a PQC $U(\theta)$ is strongly related to the
controllability problem in Quantum Optimal Control: $U(x)$ is (pure state)
controllable if $\forall\ket{\phi},\ket{\psi}$ exists $\bar{\theta}$ such that
$\ket{\phi}=U(\bar{\theta})\ket{\psi}$ albertini2003notions . Given the set of
generators $\\{H_{k}\\}_{k=1}^{K}$ of $U(\theta)$, we can define the Dynamical
Lie Algebra (DLA) as the span of $\\{iH_{k}\\}$ under the operation of
commutation. The system is controllable, thus maximally expressible, if the
DLA is full rank. In particular, a DLA polynomially sized in $n$ may lead to
trainable circuits while exponentially sized DLA will not
larocca2021diagnosing ; larocca2021theory .

###  2.3 Quantum Kernels

Quantum kernel methods havlivcek2019supervised  are obtained by encoding a
couple of data points $x,x^{\prime}$ within the Hilbert space of the quantum
system of $n$ qubits using a unitary encoding $U:\Omega\to\mathcal{U}$ in the
form of Equation 5 then taking the inner product. The latter calculation can
be efficiently estimated with the fidelity measure:

$k(x,x^{\prime})=\expectationvalue{U(x)\sigma_{z}^{\otimes
n}U^{\dagger}(x^{\prime})}{0}$ (7)

or alternatively, with the SWAP test gottesman2001quantum . If $U$ is not
classically simulable there is the possibility of a quantum advantage, which
has been already proven for highly artificial tasks liu2021rigorous ;
kubler2021inductive .

The exponential dimensionality of $\mathcal{H}$ may deteriorate the fidelity-
based quantum kernel due to the curse of dimensionality: the inner product
between two (random) vectors is expected to reach zero as $n$ grows. Huang2021
have introduced projected or biased kernel:

$\phi(x)=\expectationvalue{U(x)OU^{\dagger}(x)}{0}\qquad
k(x,x^{\prime})=\exp(-\gamma\lVert\phi(x)-\phi(x^{\prime})\rVert)$ (8)

where $\lambda>0$, which projects the quantum state toward a lower-
dimensionality subspace using the observable $O$, e.g. a local $\sigma_{z}$
measurement of $k\leq n$ qubits. Biased kernels have been used to learn the
prediction of a quantum system from experimental data Huang2021 .

kubler2021inductive  have studied the spectral properties of quantum kernels,
and proven that learning is feasible with fidelity-based quantum kernels only
if $U$ is almost constant, i.e. don’t exploit the whole (exponentially sized)
Hilbert space. This aspect seems to be strongly related to the expressibility
characteristic leading to the barren plateau in PQC. kubler2021inductive  have
suggested that even biased kernels are problematic to use in practice if we
have no assumptions suggesting to us which observable $O$ projects the data
onto a subspace of $\mathcal{H}$ that well represents our points.
kubler2021inductive ; thanasilp2022exponential  have shown that expressible
unitaries lead to kernel matrices whose non-diagonal elements are
exponentially concentrated around their mean, requiring an exponential amount
of measurements to distinguish the kernel value of different pairs of points.
Other sources of concentrations are noise and high entanglement
thanasilp2022exponential .

Finally, canatar2022bandwidth  has shown that the rescaling of input by a
constant (bandwidth) can improve the generalization error of quantum kernels,
therefore is an important hyperparameter to optimize.

##  3 Learning the structure of quantum circuits

As stated in glick2021covariant , if we have enough assumptions to decide the
set of generators a priori, i.e. fixing the structure of the PQC, we can
effectively optimize some parameters using target-kernel alignment techniques.
However, in many problems we lack such assumptions and struggle to fix an
effective structure for the PQC; this forces us to select an expressible form
that is difficult to train.

Here we introduce an approach where the object of the optimisation is the
structure of the generators rather than the circuit itself. More precisely, we
define a combinatorial optimization problem whose objective function is a
scheme for PQC where each gate corresponds to a variable ranging in the set of
allowed generators. We assume that input $x$ has already undergone a pre-
processing that has extended it with nonlinear classical pre-calculated
features (e.g. $x_{d+1}=x_{k}\cdot x_{k^{\prime}}$ for some $k,k^{\prime}<n$
as in havlivcek2019supervised ) and that data are rescaled according to a
bandwidth canatar2022bandwidth .

###  3.1 Structure of the quantum embedding

We propose a rigid structure for a PQC composed of $L$ repeated layers of $2n$
gates, where $n$ corresponds also to the number of features. In this
structure, depicted in Figure 1, each layer is composed of a column of single-
qubits gates followed by a column of two-qubits gates acting on (circularly)
adjacent qubits. Each gate is associated with a generator in
$P=\\{\mathbb{I}_{2},\sigma_{x},\sigma_{y},\sigma_{z}\\}$ (for single-qubit
gates) or $P^{\otimes 2}$ (for two-qubits gates), and an angle corresponds to
one of the components of $x$. The PQC can be described by a $2\times 2Ln$
matrix where each column corresponds to a quantum gate in a fixed position
indicated by the first component of the column (generator), and the second
component (the angle).

Alternatively, a more flexible structure can be used: we can set $m$ to the
number of (local or non-local) gates and let the optimization process decide
which operation to perform on which qubit. This formulation comes at the
expenses of searching in a much larger space of candidate solutions. In this
case, the PQC can be described by a $4\times m$ matrix, where each column
corresponds to a quantum gate in an arbitrary position: the two components
correspond to the ones in the rigid structure, and the third and fourth
components are the pair of qubits, which the gate acts on ($0$ to $n-1$). Such
structure is shown in Figure 2 and allows for short, effective circuits at the
expenses of having a larger discrete space of candidate solutions. This
structure shares some similarities with the one proposed by
altares2021automatic , except that, contrary to the latter, in our approach
the number of gates is fixed, thus avoiding the need for a penalty due to
unreasonably long circuits.

For both structures in Figure 1 and Figure 2, the initialization consists of
finding an initial value for the matrix representing the PQC. Initialization
can be deterministic, by choosing the zero matrices, or stochastic, by
selecting the values randomly. Each row has its own domain: the first row
contains elements of $P\cup P^{\otimes 2}$, and the second row contains
features of $x\in\mathbb{R}^{n}$. For the flexible structure, the third and
fourth rows range in the list of qubits (which we have fixed to $n$ as the
number of features). The pseudocode describing the construction of this family
of PQC is shown in Figure B.

Figure 1: An instance of a circuit having $n=4$ qubits and $L=1$ layers. The
embedding can be represented by the $2\times 2Ln$ matrix below the circuit.
There is a bijection between PQC and its matrix representation. Each column
corresponds to a (parameterized) gate at a fixed position: the first $n$ gates
of each layer are 1-local, and the last $n$ are 2-local. The first component
of the column is the generator ranges in $P^{\otimes 2}$ (if the operation is
1-local, the second Pauli matrix is ignored) while the second component is one
of the features of $x$ (assumes $x\in\mathbb{R}^{n}$).

Figure 2: An instance of a circuit having $n=4$ qubits and $m=5$ gates. The
embedding can be represented by the $4\times m$ matrix below the circuit. Each
column corresponds to a 1-local or 2-local qubits (parameterized) gate at an
arbitrary position: the first component is the generator in $P^{\otimes 2}$,
the second one is the feature of $x$ to be used as a rotational parameter, and
the third and fourth are the qubits in which the transformation will act to
(the fourth component may be ignored if the generator acts non-trivially on a
single qubit).

###  3.2 Optimization

The optimization phase has to select the best matrix (i.e. PQC) according to a
certain cost function. Since the space of solution is exponential in the
number of variables, exhaustive search is not a good option for finding a
global optimum. We instead rely on deterministic or stochastic meta-
heuristics, which give us no guarantees about the quality of the solution but
generally lead to satisfactory solutions.

We have selected three well-known approaches: a greedy (local) search, the
simulated annealing algorithm kirkpatrick1983optimization  and the genetic
optimization algorithm katoch2021review . Such techniques are discussed in
Appendix A. Heuristics for combinatorial optimization is an active field of
research and many more approaches exist in the literature, some of the most
notable being Taboo Search cvijovic1995taboo , Graph Neural Networks
schuetz2022combinatorial  and Reinforcement-Learning-based techniques
mazyavkina2021reinforcement . It is important to notice that our approach
gives a general scheme for constructing kernels, which can be used with any
optimization algorithm.

###  3.3 Cost function evaluation

To evaluate the quality of solutions we utilize a cost function that minimizes
the expressibility and maximizes the accuracy.

Earlier approaches altares2021automatic ; chen2022genetically  penalize the
length of the circuit or the number of CNOT gates; however, this does not
necessarily guarantee that the circuit becomes non-maximally expressive
larocca2021diagnosing .

The expressibility can be quantified in different ways as discussed in Section
2.2. Instead of expressibility, we use another quality based on an estimate of
the concentration around the mean thanasilp2022exponential . We use the
quantum kernel to calculate a small, constant number of similarities between
randomly chosen pairs of data points: if the variance of the values is below
an arbitrary threshold, the PQC is immediately discarded.

The accuracy can be estimated by first training an SVM (whose kernel matrix is
the result of our PQC) with respect to a training set, and then calculating
the mean square error with respect to a validation set. Note that the target-
kernel alignment can be used as a proxy for the empirical (training) error but
cannot be straightforwardly used for the generalization error.

Calculating the expressibility cost as concentration around the mean is much
faster than calculating the accuracy cost, which requires the computation of
the kernel matrix. Therefore, it is convenient that the overall cost function
is _not_ a linear combination of the two terms, which would force the
calculation of both terms. Instead, we first calculate the expressibility; if
this s above a certain threshold, we immediately return cost $\infty$ without
calculating the accuracy. Otherwise, the cost is directly the (estimated)
generalization error. If the expressibility is large enough to discard most
solutions, the overall optimization phase is quite fast.

##  4 Application to artificial and real-world problems

To test the efficacy of our formulation, we have tested our approach on both
artificially generated and real-world regression problems. We have compared
the quantum kernel generated using random PQC compared with the combinatorial
quantum kernel (optimized using greedy, simulated annealing, and genetic
algorithms). The implementation details and the instructions to download the
code and reproduce the experiments are detailed in Appendix C.

###  4.1 Datasets

We have generated three artificial dataset: the first dataset is generated by
sampling $\sin^{2}(x)$, the second one by sampling the step function
$f(x)=(\mathrm{sign}(x)+1)/2$, the third one by sampling the Meyer Wavelet
$\psi$ function daubechies1992ten . Each artificial dataset has 100 elements
$\\{(x^{(i)},y^{(i)})\\}_{i=1}^{100}$ with
$x^{(i)}\in\mathbb{R}^{2},x^{(i)}_{0}=x^{(i)}_{1}$ uniformly sampled from the
interval $[-1,1]$. We need to repeat the feature twice since the number of
features corresponds to the number of qubits in our formulation, and we are
not interested in testing single-qubit circuits. Each dataset is then used to
define the training, validation, and testing set each one created by randomly
subsampling 90 elements out of the original dataset. Thus, the training,
validation, and testing datasets partially overlap.

We have also used five real-world regression datasets: the prediction of the
price of fish dataset_fish_market , cancer mortality rates in US
dataset_ols_cancer , worldwide life expectancy dataset_life_expectancy , the
cost of medical treatments dataset_medical_bill , the cost of the real estate
market dataset_real_estate . The datasets have been preprocessed with PCA to
find the 5 principal components. For each dataset, the training, validation,
and testing set has been found by subsampling 150 random elements from the
whole dataset. Any feature and label have been resized to fit the interval
$[-1,1]$. The details of the datasets are shown in Table 1.

Name | Source | License | #F | #PC | #E | #SE
---|---|---|---|---|---|---
Fish market | dataset_fish_market  | GPL-2 | 6 | 5 | 159 | 150
OLS cancer | dataset_ols_cancer  | Public domain | 33 | 5 | 3047 | 150
Life Expectancy | dataset_life_expectancy  | Public domain | 31 | 5 | 3111 | 150
Medical Bill | dataset_medical_bill  | DbCL v1.0 | 6 | 5 | 1338 | 150
Real estate | dataset_real_estate  | Public Domain | 7 | 5 | 414 | 150
$\sin^{2}$ function | A | See code | 2 | 2 | 100 | 90
Step function | A | See code | 2 | 2 | 100 | 90
Meyer Wavelet | A | See code | 2 | 2 | 100 | 90
Table 1: Dataset specifications. Legend: #F: number of features, #PC:
principal components, #E: number of elements of the dataset, #SE: number of
sampled elements per training, validation, and testing set, A: artificially
generated.

###  4.2 Experimental setup

We have generated quantum kernels using different techniques. We first tried
the PQC scheme in Figure 1 by optimizing the circuit using a greedy local
search algorithm, simulated annealing, and genetic algorithms. The
optimization phase is allowed to estimate both the empirical error of the
training set and the generalization error with respect to a validation set. We
show the effect of the optimization by comparing the generalization error of
the model using the PQC as quantum embedding before and after the
optimization. The generalization error in the comparison is calculated with
respect to a testing set that is different from the validation one.

We have tested the configuration with $L=3$ layers. The matrix for the PQC has
been initialized randomly. The greedy algorithm is deterministic and the cost
function is queried as many times as the number of gates. The simulated
annealing algorithm has been run for $50000$ iterations (queries of the cost
function) starting with temperature $25000.0$ and decreasing exponentially to
$2.5$. The genetic algorithm has considered an initial population of $50$
elements; for each of the $10000$ iterations, we select the best $10$
instances which are then merged and mutated to generate the next generation of
$50$ elements. Each iteration discards the old generation. The pseudocode for
all optimization techniques is shown in Appendix A.

Then, we have compared our approach with highly expressive PQC in the form:

$U_{\mathrm{he}}(\theta)=\exp(-i\sum\limits_{i\in
1,...,4^{n}-1}\theta_{i}\sigma_{i})$ (9)

where $\sigma_{i}$ are a product of Pauli matrices with $\sigma_{0}$ product
of identities, and the angles $\theta_{i}=x_{i}w_{i}$ are obtained by
multiplying the feature $x_{i}$ with weight $w_{i}$ randomly sampled from a
normal distribution of mean 0 and variance 1. This kind of circuit has an
exponential length in the number of qubits and is the most general scheme for
a PQC, with kubler2021inductive  suggesting we shouldn’t use it for quantum
embedding since its high expressibility will affect the generalization
performances. In contrast with all the other approaches having a number of
qubits equal to the number of data features, here the number $n$ is
independent of the number of features $m$. If $m<4^{n}-1$ number of
parameters, the data features are repeated until any parameter has been
assigned.

Finally, we have compared the approaches with randomly generated PQC with an
arbitrary number of gates, in the form:

$U_{\mathrm{rand}}(\theta)=\prod_{\ell=1}^{L}\left(\prod_{j=1}^{\lceil
0.3n\rceil}\mathrm{CNOT}^{(q_{j},q_{j}^{\prime})}\right)\left(\prod_{i=1}^{n}\exp(-ix_{i}\sigma_{{\ell,i}}^{(i)})\right)$
(10)

where the
$\mathrm{CNOT}=\outerproduct{0}{0}\otimes\mathbb{I}+\outerproduct{1}{1}\otimes
X$ gates are applied to randomly chosen locations $q_{j},q_{j}^{\prime}$ and
the single qubit rotations are applied to qubit $i$ and has generator
$\sigma_{{\ell,i}}\in\\{\sigma_{x},\sigma_{y},\sigma_{z}\\}$. Each layer has
at $\lceil 0.3n\rceil$ CNOTs. We have tested this scheme with $L=3$ layers.
The procedure generates a less expressive circuit than $U_{\mathrm{he}}$ as
long as the number of layers is small.

The experiments have been performed on a noiseless, linear algebra-based
simulator on the PennyLane framework and JAX simulator. For any circuit except
$U_{\mathrm{he}}$, the number of qubits matches the number of (PCA) features
in Table 1. Each experiment (dataset, approach, optimization technique) has
been repeated 10 times.

###  4.3 Results

(a)

(b)

Figure 3: 3(a): effect of the optimization process on the generalization
error. On the $X$-axis there is the dataset, the $Y$-axis is the relative
change (ratio between the difference of MSE before and after the process, and
the MSE before the process, the maximum value is 1 meaning zero loss after
optimization), the hue is the optimization technique. Each semi-transparent
point corresponds to a candidate solution, the highlighted point is the best
solution found by the optimization technique and all the repetitions of the
process, which is the one solution kept. 3(b): comparison of the proposed
approaches in terms of MSE. The $X$, $Y$-axes and hue have the same meaning;
the bar represents the average MSE while the error bars represent the standard
deviation. _Dataset legend_ : XS: $\sin^{2}$ function, XT: step function, XM:
Meyer wavelet function, OC: OLC cancer, RE: real estate, FM: fish market, MB:
medical bill dataset, LE: life expectancy. _Technique legend_ : C: any
optimized circuit (include all three techniques), HE3: $U_{\mathrm{he}}$
acting on three qubits, HE4: $U_{\mathrm{he}}$ acting on four qubits, R:
$U_{\mathrm{rand}}$.

Figure 3(a) shows that the optimization process can improve the performance of
the machine learning model applied to any dataset. The $\sin^{2}$ dataset is
the one dataset that benefits less from our optimization, although we are able
to reduce the $19\%$ the MSE using the greedy local search, while Medical Bill
and Life Expectancy datasets benefit the most, both reducing the MSE by the
$58\%$ approximately. Table 2 shows the numerical details. We can note that
different optimization processes can lead to dramatically different results,
with the Genetic algorithm performing worse in general and the deterministic
Greedy local search performing best.

Figure 3(b) shows that our approach has better performances compared to any
approach tested, with the improvement varying largely with respect to the
dataset. It is important to note that $U_{\mathrm{he}}$ acting on three-qubits
always outperforms $U_{\mathrm{he}}$ acting on four-qubits. The phenomenon is
justified by the spectral properties of the kind of circuit worsen when
increasing the number of qubits: according to kubler2021inductive  the largest
eigenvalue of the kernel matrix decrease exponentially by increasing the
number of qubits, resulting in the impossibility to learn any function.
$U_{\mathrm{rand}}$ is a much simpler circuit than $U_{\mathrm{he}}$ in terms
of the number of gates and we expect to have favorable spectral properties.
Although, the simple structure of $U_{\mathrm{rand}}$ is also the reason for
its ineffectiveness. That suggests the solutions found by the optimization
process to be a good compromise, expressible enough to solve the problem but
not enough to struggle to generalize.

Detailed results are shown in Appendix D.

##  5 Conclusions

Quantum kernels are a promising technique of quantum machine learning, that in
some cases can even lead to an exponential speedup liu2021rigorous . However,
in order to construct effective transformations, their design must be guided
by some prior knowledge of the problem. When constructing a quantum embedding
such a knowledge is usually lacking. Our proposal is to use optimization
algorithms for designing optimal circuits for quantum embedding by
heuristically searching the data. We have modeled the problem as a
combinatorial optimization problem on gates generators, angles, and positions
and formulated it as the minimization of a certain cost function. In contrast
with gradient-descent-based approaches lloyd2020quantum , which train only the
rotational angles of some gates incurring in the barren plateau issue, we
avoid this problem by construction. larocca2021diagnosing  has shown the set
of generators of the circuit directly influence the expressibility of the
transformation, which leads to the barren plateau holmes2022connecting : in
lloyd2020quantum  the generators are fixed and decided a priori, while during
our optimization process the generators are varying, and the ineffective
(uselessly expressive) solutions are discarded.

The combinatorial optimization process is expensive: the cost function must be
queried for any candidate solution. Since the cost function should depend on
the generalization error of the model (created using the candidate solution as
a circuit), each call of the cost function must create the Gram matrix to be
fed to the SVM, which has a quadratic cost in the number of data. We have
introduced a policy to discard all the candidate solutions that result in an
exponential concentration of kernel similarities around their mean
thanasilp2022exponential , which can be estimated quickly and in constant
time, speeding up the process. The candidate solutions whose variance is below
the decided threshold are kept and their cost is their generalization error. A
higher threshold discards more solutions, speeding up the process as far as
needed.

Our experimental results on artificial and real-world datasets have shown that
our approach can largely reduce the generalization error, up to $57\%$. The
results depend on the dataset and the optimization process. This suggests that
more sophisticated algorithms can further improve performances. We believe
that the optimization process can be further improved by exploiting symmetries
in quantum transformations to reduce the space of candidate solutions.

## References

  *   * (1) Biamonte, J., Wittek, P., Pancotti, N., Rebentrost, P., Wiebe, N., Lloyd, S.: Quantum machine learning. Nature 549(7671), 195–202 (2017)
  * (2) Harrow, A.W., Hassidim, A., Lloyd, S.: Quantum algorithm for linear systems of equations. Physical review letters 103(15), 150502 (2009)
  * (3) Rebentrost, P., Mohseni, M., Lloyd, S.: Quantum support vector machine for big data classification. Physical review letters 113(13), 130503 (2014)
  * (4) Lloyd, S., Mohseni, M., Rebentrost, P.: Quantum principal component analysis. Nature Physics 10(9), 631–633 (2014)
  * (5) Lloyd, S., Garnerone, S., Zanardi, P.: Quantum algorithms for topological and geometric analysis of data. Nature communications 7(1), 1–7 (2016)
  * (6) Aaronson, S.: Read the fine print. Nature Physics 11(4), 291–293 (2015)
  * (7) Giovannetti, V., Lloyd, S., Maccone, L.: Quantum random access memory. Physical review letters 100(16), 160501 (2008)
  * (8) Preskill, J.: Quantum computing in the nisq era and beyond. Quantum 2, 79 (2018)
  * (9) Cerezo, M., Arrasmith, A., Babbush, R., Benjamin, S.C., Endo, S., Fujii, K., McClean, J.R., Mitarai, K., Yuan, X., Cincio, L., et al.: Variational quantum algorithms. Nature Reviews Physics 3(9), 625–644 (2021)
  * (10) Peruzzo, A., McClean, J., Shadbolt, P., Yung, M.-H., Zhou, X.-Q., Love, P.J., Aspuru-Guzik, A., O’brien, J.L.: A variational eigenvalue solver on a photonic quantum processor. Nature communications 5(1), 1–7 (2014)
  * (11) Farhi, E., Goldstone, J., Gutmann, S.: A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028 (2014)
  * (12) Zhou, L., Wang, S.-T., Choi, S., Pichler, H., Lukin, M.D.: Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices. Physical Review X 10(2), 021067 (2020)
  * (13) Abbas, A., Sutter, D., Zoufal, C., Lucchi, A., Figalli, A., Woerner, S.: The power of quantum neural networks. Nature Computational Science 1(6), 403–409 (2021)
  * (14) Havlíček, V., Córcoles, A.D., Temme, K., Harrow, A.W., Kandala, A., Chow, J.M., Gambetta, J.M.: Supervised learning with quantum-enhanced feature spaces. Nature 567(7747), 209–212 (2019)
  * (15) Shawe-Taylor, J., Cristianini, N.: Kernel Methods for Pattern Analysis. Cambridge University Press, Cambridge, UK (2004)
  * (16) Hofmann, T., Schölkopf, B., Smola, A.J.: Kernel methods in machine learning. The annals of statistics 36(3), 1171–1220 (2008)
  * (17) Schölkopf, B., Tsuda, K., Vert, J.-P.: Kernel Methods in Computational Biology. MIT press, Cambridge, MA (2004)
  * (18) Ralaivola, L., Swamidass, S.J., Saigo, H., Baldi, P.: Graph kernels for chemical informatics. Neural networks 18(8), 1093–1110 (2005)
  * (19) Karniadakis, G.E., Kevrekidis, I.G., Lu, L., Perdikaris, P., Wang, S., Yang, L.: Physics-informed machine learning. Nature Reviews Physics 3(6), 422–440 (2021)
  * (20) Schuld, M.: Supervised quantum machine learning models are kernel methods. arXiv preprint arXiv:2101.11020 (2021)
  * (21) Gottesman, D., Chuang, I.: Quantum digital signatures. arXiv preprint quant-ph/0105032 (2001)
  * (22) Liu, Y., Arunachalam, S., Temme, K.: A rigorous and robust quantum speed-up in supervised machine learning. Nature Physics 17(9), 1013–1017 (2021)
  * (23) Glick, J.R., Gujarati, T.P., Corcoles, A.D., Kim, Y., Kandala, A., Gambetta, J.M., Temme, K.: Covariant quantum kernels for data with group structure. arXiv preprint arXiv:2105.03406 (2021)
  * (24) Huang, H.-Y., Broughton, M., Mohseni, M., Babbush, R., Boixo, S., Neven, H., McClean, J.R.: Power of data in quantum machine learning. Nature Communications 12(1) (2021). https://doi.org/10.1038/s41467-021-22539-9
  * (25) Kübler, J., Buchholz, S., Schölkopf, B.: The inductive bias of quantum kernels. Advances in Neural Information Processing Systems 34 (2021)
  * (26) Canatar, A., Peters, E., Pehlevan, C., Wild, S.M., Shaydulin, R.: Bandwidth enables generalization in quantum kernel models. arXiv preprint arXiv:2206.06686 (2022)
  * (27) Holmes, Z., Sharma, K., Cerezo, M., Coles, P.J.: Connecting ansatz expressibility to gradient magnitudes and barren plateaus. PRX Quantum 3(1), 010313 (2022)
  * (28) McClean, J.R., Boixo, S., Smelyanskiy, V.N., Babbush, R., Neven, H.: Barren plateaus in quantum neural network training landscapes. Nature communications 9(1), 1–6 (2018)
  * (29) Thanasilp, S., Wang, S., Cerezo, M., Holmes, Z.: Exponential concentration and untrainability in quantum kernel methods. arXiv preprint arXiv:2208.11060 (2022)
  * (30) Larocca, M., Czarnik, P., Sharma, K., Muraleedharan, G., Coles, P.J., Cerezo, M.: Diagnosing barren plateaus with tools from quantum optimal control. arXiv preprint arXiv:2105.14377 (2021)
  * (31) Mitarai, K., Negoro, M., Kitagawa, M., Fujii, K.: Quantum circuit learning. Physical Review A 98(3), 032309 (2018)
  * (32) Lloyd, S., Schuld, M., Ijaz, A., Izaac, J., Killoran, N.: Quantum embeddings for machine learning. arXiv preprint arXiv:2001.03622 (2020)
  * (33) Altares-López, S., Ribeiro, A., García-Ripoll, J.J.: Automatic design of quantum feature maps. Quantum Science and Technology 6(4), 045015 (2021)
  * (34) Chen, B.-S., Chern, J.-L.: Genetically auto-generated quantum feature maps. arXiv preprint arXiv:2207.11449 (2022)
  * (35) Huang, Y., Li, Q., Hou, X., Wu, R., Yung, M.-H., Bayat, A., Wang, X.: Robust resource-efficient quantum variational ansatz through an evolutionary algorithm. Physical Review A 105(5), 052414 (2022)
  * (36) Murphy, K.P.: Machine Learning: a Probabilistic Perspective. MIT press, Cambridge, MA (2012)
  * (37) Cortes, C., Vapnik, V.: Support-vector networks. Machine learning 20(3), 273–297 (1995)
  * (38) Schölkopf, B., Smola, A., Müller, K.-R.: Nonlinear component analysis as a kernel eigenvalue problem. Neural computation 10(5), 1299–1319 (1998)
  * (39) Caponnetto, A., De Vito, E.: Optimal rates for the regularized least-squares algorithm. Foundations of Computational Mathematics 7(3), 331–368 (2007)
  * (40) Amini, A.A., Razaee, Z.S.: Concentration of kernel matrices with application to kernel spectral clustering. The Annals of Statistics 49(1), 531–556 (2021)
  * (41) Cristianini, N., Shawe-Taylor, J., Elisseeff, A., Kandola, J.: On kernel-target alignment. Advances in neural information processing systems 14 (2001)
  * (42) Cortes, C., Mohri, M., Rostamizadeh, A.: Algorithms for learning kernels based on centered alignment. The Journal of Machine Learning Research 13, 795–828 (2012)
  * (43) Sim, S., Johnson, P.D., Aspuru-Guzik, A.: Expressibility and entangling capability of parameterized quantum circuits for hybrid quantum-classical algorithms. Advanced Quantum Technologies 2(12), 1900070 (2019)
  * (44) Nakaji, K., Yamamoto, N.: Expressibility of the alternating layered ansatz for quantum computation. Quantum 5, 434 (2021)
  * (45) Cerezo, M., Sone, A., Volkoff, T., Cincio, L., Coles, P.J.: Cost function dependent barren plateaus in shallow parametrized quantum circuits. Nature communications 12(1), 1–12 (2021)
  * (46) Wang, S., Fontana, E., Cerezo, M., Sharma, K., Sone, A., Cincio, L., Coles, P.J.: Noise-induced barren plateaus in variational quantum algorithms. Nature communications 12(1), 1–11 (2021)
  * (47) Albertini, F., D’Alessandro, D.: Notions of controllability for bilinear multilevel quantum systems. IEEE Transactions on Automatic Control 48(8), 1399–1403 (2003)
  * (48) Larocca, M., Ju, N., García-Martín, D., Coles, P.J., Cerezo, M.: Theory of overparametrization in quantum neural networks. arXiv preprint arXiv:2109.11676 (2021)
  * (49) Kirkpatrick, S., Gelatt Jr, C.D., Vecchi, M.P.: Optimization by simulated annealing. science 220(4598), 671–680 (1983)
  * (50) Katoch, S., Chauhan, S.S., Kumar, V.: A review on genetic algorithm: past, present, and future. Multimedia Tools and Applications 80(5), 8091–8126 (2021)
  * (51) Cvijović, D., Klinowski, J.: Taboo search: an approach to the multiple minima problem. Science 267(5198), 664–666 (1995)
  * (52) Schuetz, M.J., Brubaker, J.K., Katzgraber, H.G.: Combinatorial optimization with physics-inspired graph neural networks. Nature Machine Intelligence 4(4), 367–377 (2022)
  * (53) Mazyavkina, N., Sviridov, S., Ivanov, S., Burnaev, E.: Reinforcement learning for combinatorial optimization: A survey. Computers & Operations Research 134, 105400 (2021)
  * (54) Daubechies, I.: Ten Lectures on Wavelets. SIAM, Philadelphia, PE (1992)
  * (55) Pyae, A.: Fish Market (dataset). Kaggle (2019). https://www.kaggle.com/datasets/aungpyaeap/fish-market
  * (56) Rippner, N.: OLS Regression Challenge (dataset). Kaggle (2019). https://data.world/nrippner/ols-regression-challenge
  * (57) Rajarshi, K.: Life Expectancy (dataset). Kaggle (2016). https://www.kaggle.com/datasets/kumarajarshi/life-expectancy-who
  * (58) Stednick, Z.: Medical Cost Personal (dataset). Kaggle (2017). https://www.kaggle.com/datasets/mirichoi0218/insurance
  * (59) Algor_Bruce: Real Estate. Kaggle (2021). https://www.kaggle.com/datasets/quantbruce/real-estate-price-prediction
  * (60) Lukac, M., Perkowski, M., Goi, H., Pivtoraiko, M., Yu, C.H., Chung, K., Jeech, H., Kim, B.-G., Kim, Y.-D.: Evolutionary approach to quantum and reversible circuits synthesis. Artificial Intelligence Review 20(3), 361–417 (2003). https://doi.org/10.1023/B:AIRE.0000006605.86111.79
  * (61) Di Marcantonio, F., Incudini, M., Tezza, D., Grossi, M.: Quask–quantum advantage seeker with kernels. arXiv preprint arXiv:2206.15284 (2022)
  * (62) Bergholm, V., Izaac, J., Schuld, M., Gogolin, C., Alam, M.S., Ahmed, S., Arrazola, J.M., Blank, C., Delgado, A., Jahangiri, S., et al.: Pennylane: Automatic differentiation of hybrid quantum-classical computations. arXiv preprint arXiv:1811.04968 (2018)
  * (63) Bradbury, J., Frostig, R., Hawkins, P., Johnson, M.J., Leary, C., Maclaurin, D., Necula, G., Paszke, A., VanderPlas, J., Wanderman-Milne, S., Zhang, Q.: JAX: Composable Transformations of Python+NumPy programs. http://github.com/google/jax

##  Appendix A Pseudocode for Meta-Heuristic optimization algorithms

Figure 4 shows the pseudocode of the greedy algorithm that we have used to
optimize the PQCs. Starting from an initial configuration scheme representing
our candidate solution, the algorithm mutates a single operation while keeping
fixed the others. Each possible combination of generators and features for the
single operation are tested, and the best one (in terms of cost function
query) is kept. The procedure is repeated for any gate of the circuit, thus
$2nL$ times for the rigid structure in Figure 1.

Figure 4: Pseudocode for the Greedy Local Search

Figure 5 shows the pseudocode of the genetic algorithm employed in our
experiments. Genetic algorithms katoch2021review  are probabilistic meta-
heuristic optimization techniques inspired by natural selection. An initial
population of candidate solutions called _chromosome_ is randomly generated.
Each chromosome is usually represented as a vector or matrix of integer
elements. In our case, it is represented by the matrix in Figure 1. The
components of the chromosomes are the genes. We evolve the population through
an arbitrary number of iterations, the population of each iteration is a
_generation_. Each element of the population has a fitness value, which
corresponds to an inverse cost (the higher the fitness, the better the
solution). Each iteration is composed of the _selection_ step, the _crossover_
step and the _mutation_ step. The selection step chooses a subset of the
population to be bred and generate children. We select the 20% best items of
the population to be bred, but several other policies can be used. The
selected items are then used to instantiate the new generation during the
crossover phase: each child is generated using the first $m$ columns of the
left parent, and the other columns from the right parent, with $m$ chosen
randomly each time. Other crossover policies are allowed. Finally, each child
is then mutated by perturbing one or more genes (e.g. adding 1 to the gene).
The new generation substitutes completely the old one, although the algorithm
can be tuned to have only a small part of the population be substituted.
Genetic algorithms have been extensively investigated in the context of
quantum circuit synthesis with satisfactory results lukac2004evolutionary .

Figure 5: Pseudocode for the Genetic algorithm Figure 6: Pseudocode for
Simulated Annealing algorithm

Figure 6 shows the pseudocode of the Simulated Annealing algorithm
kirkpatrick1983optimization . Simulated Annealing is a probabilistic meta-
heuristic optimization techniques inspired by the annealing process in
metallurgy. An initial set of candidate solution is randomly generated at the
beginning of the process. For each solution, the annealing process perform an
arbitrary number of iterations that perturbs the candidate solution. If the
perturbed solution has lower cost than the original one, the former is
accepted as new candidate solution in substitution of the latter. If the
perturbed solution has higher cost, it can be either accepted or rejected
through a probabilistic policy that depends on both the difference of energy
and a temperature parameter $T$: low energy differences and high temperature
results in higher chances of solution acceptance. The temperature parameter
decreases linearly or exponentially toward a minimum value
($T_{\mathrm{min}}\geq 0$) at each iteration. The varying of temperature allow
to explore the space of solution at the beginning of the process, while at the
end of the process we converge to a local or global minima. At the end of the
process, we have a number of optimized solutions matching the initial
candidate solutions. The best solution in this set is kept.

##  Appendix B Pseudocode for circuit construction

The code for constructing $U_{\mathrm{he}}$ is taken from PennyLane framework.
It corresponds to the pseudocode shown in Figure 7(a). The code for
constructing $U_{\mathrm{rand}}$ is shown in Figure 7(b). The code for
constructing the scheme of PQC having the fixed structure in Figure 1 is shown
in Figure 7(c).

(a)

(b)

(c)

Figure 7: 7(a): pseudocode for construct the circuit corresponding to
$U_{\mathrm{he}}$ unitary transformation. 7(b): pseudocode for construct the
circuit corresponding to $U_{\mathrm{rand}}$ unitary transformation. 7(c):
pseudocode for construct the circuit corresponding to the fixed scheme of PQC
in Figure 1.

##  Appendix C Code and implementation details

The software for the experiments has been developed using Quask di2022quask ,
which is a software running on top of PennyLane bergholm2018pennylane
framework. The noiseless, linear algebra-based simulator is based on the JAX
library jax2018github  which allows for faster simulations of quantum
circuits. The code to reproduce the experiments, including intermediate
results and plot can be freely downloaded from
https://github.com/incud/Combinatorial-Optimization-Quantum-Embeddings.

##  Appendix D Detailed results

In Table 2 we show the change of MSE before and after the optimization process
for each technique. Figure 8 shows the detailed MSE for any dataset and kernel
technique proposed.

Dataset | Optimization technique | $\frac{\Delta\mathrm{MSE}}{\mathrm{MSE\,before\,opt.}}$ | MSE before opt. | MSE after opt.
---|---|---|---|---
FM | Genetic | $0.2148$ | $0.1739$ | $0.2328$
| Greedy | $0.3676$ | $0.2150$ | $0.1731$
| Sim. Annealing | $0.3189$ | $0.2150$ | $0.2123$
LE | Genetic | $-0.0592$ | $0.2185$ | $0.4565$
| Greedy | $0.5843$ | $0.3024$ | $0.2943$
| Sim. Annealing | $0.5097$ | $0.3241$ | $0.2265$
MB | Genetic | $-0.0415$ | $0.1536$ | $0.2837$
| Greedy | $0.5798$ | $0.4207$ | $0.2098$
| Sim. Annealing | $0.2660$ | $0.1996$ | $0.2307$
OC | Genetic | $-0.0133$ | $0.1072$ | $0.1381$
| Greedy | $0.2184$ | $0.1429$ | $0.1291$
| Sim. Annealing | $0.3233$ | $0.1393$ | $0.1304$
RE | Genetic | $0.1638$ | $0.1686$ | $0.1979$
| Greedy | $0.3258$ | $0.2809$ | $0.2269$
| Sim. Annealing | $0.3661$ | $0.2271$ | $0.1792$
XM | Genetic | $0.3287$ | $0.0602$ | $0.0736$
| Greedy | $0.2999$ | $0.0600$ | $0.0586$
| Sim. Annealing | $0.3983$ | $0.0714$ | $0.0556$
XS | Genetic | $-0.1708$ | $0.5253$ | $1.0796$
| Greedy | $0.1475$ | $1.0678$ | $1.0678$
| Sim. Annealing | $-0.2028$ | $0.5869$ | $1.0176$
XT | Genetic | $-0.4621$ | $1.0537$ | $1.8781$
| Greedy | $0.2398$ | $1.7907$ | $1.7907$
| Sim. Annealing | $0.1913$ | $1.9618$ | $1.8295$
Table 2: Change of performance in terms of MSE before and after the
optimization process. These correspond to the best MSE obtained before the
optimization among all the repetitions and the best MSE after the optimization
among all repetitions, for each dataset. _Dataset legend_ : XS: $\sin^{2}$
function, XT: step function, XM: Meyer wavelet function, OC: OLC cancer, RE:
real estate, FM: fish market, MB: medical bill dataset, LE: life expectancy.

(a) Dataset FM

(b) Dataset LE

(c) Dataset MB

(d) Dataset OC

(e) Dataset RE

(f) Dataset XM

(g) Dataset XS

(h) Dataset XT

Figure 8: Detailed MSE analysis for any dataset and kernel technique. _Dataset
legend_ : XS: $\sin^{2}$ function, XT: step function, XM: Meyer wavelet
function, OC: OLC cancer, RE: real estate, FM: fish market, MB: medical bill
dataset, LE: life expectancy. _Technique legend_ : CGEN: genetic algorithm
optimization approach, GSA: simulated annealing optimized approach, CGLS:
greedy local search optimized approach, HE3: $U_{\mathrm{he}}$ acting on three
qubits, HE4: $U_{\mathrm{he}}$ acting on four qubits, R: $U_{\mathrm{rand}}$.


remdefinition rem exadefinition exa cordefinition cor lemdefinition lem
propdefinition prop thmdefinition thm

# The Veech group of the golden ladder

Anja Randecker

###### Abstract

These are the notes of a talk that I gave at the Weihnachtsworkshop 2017 in
Saarbrücken. It answered a question by Hooper and Treviño on the Veech group
of the golden ladder, a translation surface of infinite type.

A _ladder surface_ is a translation surface that we obtain when gluing
opposite sides of an infinite-sided polygon as in Figure 1.

Figure 1: For the ladder surface, we identify opposite edges of this polygon.

In the article [HT17], Hooper and Treviño consider a ladder surface with
specific edge lengths that are related to the golden mean. They ask whether
the symmetry group of this translation surface, the Veech group, is generated
by a multi-twist and a reflection.

In these notes, we answer the question affirmatively, using a similar
technique as for the baker’s map surface (see [Cha04, HR16]). In particular,
the Veech group of the golden ladder is a non-elementary Fuchsian group of the
second kind.

We show this result on the Veech group for a family of ladder surfaces where
the golden ladder is a special case.

##  1 Translation surfaces and Veech groups

We first review the definitions that we use for these notes. In particular,
note that in our definitions, translation surfaces are not necessarily of
finite topological type, so we do not include the singularities into the
surface.

A _translation surface_ $(X,\mathcal{A})$ is a connected two-dimensional
manifold $X$ together with a translation structure $\mathcal{A}$ on $X$, that
is, a maximal atlas on $X$ such that the transition functions are locally
translations. We can equip any translation surface $(X,\mathcal{A})$ with a
flat metric by pulling back the Euclidean metric via the charts. The metric
completion $\overline{X}$ may contain points which are not points of $X$ –
these are called _singularities_.

There are three kinds of singularities: A singularity is called _cone angle
singularity_ if it has a punctured neighborhood in $X$ which is isometric to a
finite translation covering of a once-punctured Euclidean disk. It is called
_infinite angle singularity_ if it has a punctured neighborhood in $X$ which
is isometric to an infinite translation covering of a once-punctured Euclidean
disk. Any other singularity is called _wild_.

A continuous map $f\colon(X,\mathcal{A})\to(Y,\mathcal{B})$ of translation
surfaces is called _affine_ if it is locally affine, that is, for every $x\in
X$ there exist charts $(U,\varphi)\in\mathcal{A}$ and $(V,\psi)\in\mathcal{B}$
with $x\in U$ and $f(U)\subseteq V$ such that for every
$z\in\varphi(U)\subseteq\mathbb{R}^{2}$, we have

$\left(\psi\circ f\circ\varphi^{-1}\right)(z)=A\cdot z+t\text{ for a fixed
}A\in\operatorname{GL}(2,\mathbb{R})\text{ and a fixed }t\in\mathbb{R}^{2}.$

For an affine map $f$, the matrix $A$ is globally the same for all choices of
charts. This matrix is called the _derivative_ of $f$. For a translation
surface $(X,\mathcal{A})$, the _Veech group_
$\operatorname{GL}^{+}(X,\mathcal{A})$ of $(X,\mathcal{A})$ is defined as the
group of all derivatives of orientation-preserving homeomorphisms of $X$ that
are affine with respect to $\mathcal{A}$.

For a translation surface with finite area, the elements of the affine group
are area-preserving, hence the Veech group is a subgroup of
$\operatorname{SL}(2,\mathbb{R})$. To make use of fundamental domains of the
action on $\mathbb{H}^{2}$ in Section 4, we will subscribe to the point of
view that the Veech group is in fact the image of
$\operatorname{GL}^{+}(X,\mathcal{A})$ in $\operatorname{PSL}(2,\mathbb{R})$.
This is also justified by the observation at the end of Section 5 that the
Veech group of a ladder surface does not contain the element
$\begin{pmatrix}-1&0\\\ 0&-1\end{pmatrix}$.

##  2 Ladder surfaces

We describe a family of translation surfaces, called ladder surfaces. Note
that the name comes from the fact that the gluing pattern resembles that of a
one-sided infinite staircase, not from the topological type of a Jacob’s
ladder.

We define a translation surface for every $\lambda\in(0,\infty)$ with a gluing
pattern and edge lengths as in Figure 2. For $\lambda=0$, the surface is a
torus; for $\lambda=1$, it is a one-sided version of the infinite staircase as
in [HHW13, MST19].

$1$$\lambda$$1$$\lambda^{2}$$\lambda$$\lambda^{2}$$\lambda^{3}$$1$$\lambda$$1$$\lambda^{2}$$\lambda$$\lambda^{2}$$\lambda^{3}$
Figure 2: For the ladder surface with parameter $\lambda$, we identify edges
that are parallel and have the same length (labels are indicating length).

We are particularly interested in the case of $\lambda\in(0,1)$. Then the area
of the surface is

$1^{2}+2\cdot\lambda\cdot
1+\lambda^{2}+2\cdot\lambda^{2}\cdot\lambda+\ldots=\sum_{k=0}^{\infty}\lambda^{2k}+2\cdot\sum_{k=0}^{\infty}\lambda^{2k+1}<\infty$

and it has exactly one singularity, which is wild. In the case of $\lambda\geq
1$, the ladder surface has infinite area and three infinite angle
singularities. In all cases, the surface has one end and infinite genus.
Hence, the topological type is that of a Loch Ness monster.

A ladder surface has many symmetries if its parameter $\lambda$ fulfills the
following condition: Let $k,l\in\mathbb{Z}$ be coprime numbers with $k>l>0$.
Then we define $\lambda_{k,l}$ to be the greater (i.e. the positive) solution
of the equation $k\cdot(\lambda+1)=l\cdot(\lambda^{-1}+1+\lambda)$. In
particular for $l=1$ and $k=2$, $\lambda_{2,1}$ is the inverse of the golden
mean. This is the case of the golden ladder that was considered in [HT17].

Ladder surfaces arise in different ways from previously known constructions
and examples. Hooper and Treviño describe the golden ladder as a translation
surface associated to an infinite grid graph construction.

We can also apply the matrix $\begin{pmatrix}1&\nicefrac{{1}}{{2}}\\\
0&\nicefrac{{\sqrt{3}}}{{2}}\end{pmatrix}$ (a shear combined with a scaling)
and obtain a translation surface as in Figure 3. This translation surface can
be thought of as being glued from semi-regular hexagons. Here, semiregular
means that every second edge has the same length. The first hexagon actually
has the edge lengths $1$ and $0$, alternatingly.

$1$$\lambda$$1$$\lambda^{2}$$\lambda$$\lambda^{2}$$\lambda^{3}$$1$$\lambda$$1$$\lambda^{2}$$\lambda$$\lambda^{2}$$\lambda^{3}$
Figure 3: The ladder surface with parameter $\lambda$ after applying an affine
transformation.

Finite translation surfaces that are glued together from semiregular polygons
have been described by Hooper in [Hoo13], based on earlier work of Bouw and
Möller in [BM10] where the translation surfaces are given by a different
description.

It is convenient to switch between the description as a ladder surface and as
gluing of semi-regular hexagons to determine the Veech group. In particular,
we can see from the description by semi-regular hexagon that there exists an
elliptic element of order $3$ in the Veech group.

##  3 Three parabolic elements of the Veech group

For a translation surface $(X,\mathcal{A})$ with at least one singularity, a
_cylinder_ in $(X,\mathcal{A})$ of _circumference_ $w>0$ and _height_ $h>0$ is
an open subset of $X$ which is isometric to a Euclidean cylinder
$\mathbb{R}/w\mathbb{Z}\times(0,h)$. The _modulus_ of a cylinder is the ratio
$\frac{w}{h}$ of circumference and height.

A _saddle connection_ of $(X,\mathcal{A})$ is a geodesic segment in
$\overline{X}$ from one singularity to another or the same singularity which
does not contain singularities in its interior. If a cylinder can be extended
to a maximal cylinder then this maximal cylinder is bounded by saddle
connections. A _cylinder decomposition_ of $(X,\mathcal{A})$ is a collection
of maximal cylinders in $(X,\mathcal{A})$ such that the closures of the
cylinders in $X$ cover $X$ and such that each two cylinders are disjoint. The
_direction_ of the cylinder decomposition is the direction of the
corresponding bounding saddle connections.

We will use the following standard result to find elements of the Veech group.
It was first proven in [Vee89] as an equivalence for translation surfaces of
finite type. However, the proof of the implication that is stated here
literally works for the general case.

###### Proposition (Cylinder decompositions and parabolic elements [Veech])

Let $(X,\mathcal{A})$ be a translation surface and $\left\\{z_{n}\right\\}$ a
cylinder decomposition such that the cylinder $z_{n}$ has height $h_{n}$ and
circumference $w_{n}$. If the inverse moduli $\frac{h_{n}}{w_{n}}$ are
commensurable, that is, if there exists an $m\in\mathbb{R}$ such that each
inverse modulus is an integer multiple of $m$, then the Veech group contains a
parabolic element conjugated to the matrix
$\begin{pmatrix}1&\nicefrac{{1}}{{m}}\\\ 0&1\end{pmatrix}$.

$1$$\lambda$$1$$\lambda^{2}$$\lambda$$\lambda^{2}$$\lambda^{3}$$1$$\lambda$$1$$\lambda^{2}$$\lambda$$\lambda^{2}$$\lambda^{3}$
Figure 4: Ladder surface with a horizontal cylinder decomposition.

Figure 4 shows a horizontal cylinder decomposition on the ladder surface. It
consists of infinitely many cylinders where all except the bottom one are
similar. The bottom cylinder has a height of $1$ and a circumference of
$1+\lambda$, hence the modulus is $1+\lambda$. The cylinder above has a height
of $\lambda$ and a circumference of $1+\lambda+\lambda^{2}$, hence the modulus
is $\lambda^{-1}+1+\lambda$. For $\lambda=\lambda_{k,l}$, we get that the
moduli of all the cylinders but the bottom one are
$\frac{k}{l}\cdot(1+\lambda)$. Then section 3 implies that there exists a
parabolic element in the Veech group which preserves the horizontal direction
and acts as a (multiple) Dehn twist on every cylinder in the horizontal
cylinder decomposition. The derivative of it is
$\begin{pmatrix}1&k(1+\lambda)\\\ 0&1\end{pmatrix}$ and it twists the bottom
cylinder $k$ times and all other cylinders $l$ times.

Analogously, we have another parabolic element in the Veech group, coming from
a vertical cylinder decomposition. When considering the description by
semiregular hexagons, we can even see three cylinder decompositions directly
as in Figure 5: The horizontal decomposition in this description corresponds
to the horizontal decomposition we described before. Using the elliptic
element of order $3$, we also have two diagonal directions of cylinder
decompositions which correspond to the vertical decomposition and a
decomposition of slope $-1$ in the description as ladder surface.

Figure 5: Three cylinder decompositions in the description as semiregular
hexagons.

As a converse to the existence of these three cylinder directions, we prove
that a large set of directions cannot occur as eigen directions of parabolic
elements in the Veech group. Note that there can still exist cylinder
decompositions in these directions.

###### Lemma .

There is no parabolic element in the Veech group of the ladder surface with
parameter $\lambda\in(0,1)$ whose eigen direction corresponds to a slope in
the interval $(\lambda,\lambda^{-1})$.

###### Proof.

Consider the point $S=\left(\frac{1}{1-\lambda},\frac{1}{1-\lambda}\right)$ in
the metric completion of the ladder surface. As
$\frac{1}{1-\lambda}=\sum_{n=0}^{\infty}\lambda^{n}$, this point sits in the
top right corner of the ladder surface.

$1$$\lambda$$1$$\lambda^{2}$$\lambda$$\lambda^{2}$$\lambda^{3}$$1$$\lambda$$1$$\lambda^{2}$$\lambda$$\lambda^{2}$$\lambda^{3}$$S$
Figure 6: Geodesic segments in a direction which cannot be the eigen direction
of a parabolic element in the Veech group.

Consider a direction $\theta$ which corresponds to a slope in
$(\lambda,\lambda^{-1})$ and suppose $P$ is a parabolic element with eigen
direction $\theta$. There exist infinitely many geodesic segments in direction
$\theta$ that start in the singularity and have length $1$ (see Figure 6).
Then $P$ has to map the set of these geodesic segments to itself. Note that
the geodesic segment that starts in $S$ is distinguished from all others as it
is the limit of the geodesic segments in this set. Hence, $P$ has to fix this
distinguished segment pointwise. As $P$ is locally acting as a shear on the
ladder surface, this implies that also the geodesic segments close to the
limit segment have to be fixed pointwise. So $P$ fixes an open subset of the
ladder surface. Therefore, $P$ is the identity and not a parabolic element. ∎

##  4 Candidate for the Veech group

We found already a subgroup of the Veech group of the ladder surface with
parameter $\lambda_{k,l}$: In the description by semiregular hexagons, we have
the elliptic element
$\begin{pmatrix}\cos\nicefrac{{2\pi}}{{3}}&-\sin\nicefrac{{2\pi}}{{3}}\\\
\sin\nicefrac{{2\pi}}{{3}}&\cos\nicefrac{{2\pi}}{{3}}\end{pmatrix}=\begin{pmatrix}-\nicefrac{{1}}{{2}}&-\nicefrac{{\sqrt{3}}}{{2}}\\\
\nicefrac{{\sqrt{3}}}{{2}}&-\nicefrac{{1}}{{2}}\end{pmatrix}$ in the Veech
group. Hence in the description as ladder surface, the corresponding Veech
group element is given by

$R\coloneqq\begin{pmatrix}1&-\nicefrac{{1}}{{\sqrt{3}}}\\\
0&\nicefrac{{2}}{{\sqrt{3}}}\end{pmatrix}\cdot\begin{pmatrix}-\nicefrac{{1}}{{2}}&-\nicefrac{{\sqrt{3}}}{{2}}\\\
\nicefrac{{\sqrt{3}}}{{2}}&-\nicefrac{{1}}{{2}}\end{pmatrix}\cdot\begin{pmatrix}1&-\nicefrac{{1}}{{2}}\\\
0&\nicefrac{{\sqrt{3}}}{{2}}\end{pmatrix}=\begin{pmatrix}-1&-1\\\
1&0\end{pmatrix}.$

Furthermore, let $T\coloneqq\begin{pmatrix}1&k(1+\lambda)\\\ 0&1\end{pmatrix}$
be the parabolic element defined by the horizontal cylinder decomposition.

Let $G=\left\langle R,T\right\rangle$ be the group generated by the elliptic
and the parabolic element in $\operatorname{PSL}(2,\mathbb{R})$. We determine
the fundamental domain of $G$ in $\mathbb{H}$ in this section.

The elements of $\operatorname{PSL}(2,\mathbb{R})$ act as Möbius
transformations on
$\overline{\mathbb{H}}\coloneqq\mathbb{H}\cup\mathbb{R}\cup\infty$. Under this
action, the fixed point of $T$ is $\infty$. Hence, a fundamental domain of the
subgroup $\left\langle T\right\rangle$ can be chosen to be the strip
$F_{1}\coloneqq\\{z\in\mathbb{H}:-2<\mathrm{Re}(z)<k\cdot(1+\lambda)-2\\}$ as
shown in Figure 7.

For the elliptic element $R$, the fixed point in $\overline{\mathbb{H}}$ is
$\frac{-1+\sqrt{3}\cdot\mathrm{i}}{2}$. This means that $R$ sends the vertical
line from $-\frac{1}{2}$ to $\infty$ to the geodesic from $1$ to $-1$. Its
inverse sends the vertical line to the geodesic from $-2$ to $0$. Hence, we
have that $F_{2}$ as in Figure 8 is a fundamental domain of the subgroup
$\left\langle R\right\rangle$.

We now consider $F\coloneqq F_{1}\cap F_{2}$ as sketched in Figure 9. Note
that $F$ is an open convex hyperbolic polygon, $T$ and $R$ constitute a side
pairing for $F$, and the cusp at the boundary of $F$, namely $\infty$, is the
fixed point of a parabolic element, namely $T$. Hence Poincaré’s fundamental
polyhedron theorem implies that the group generated by the side pairings, i.e.
$G$, is discrete and that $F_{G}\coloneqq F$ is a fundamental domain for $G$
(see [Mas71]).

$-2$$-1$$0$$1$$k(1+\lambda)-2$$\mathrm{i}$$F_{1}$ Figure 7: Fundamental domain
of $\left\langle T\right\rangle$.
$-2$$-1$$0$$1$$k(1+\lambda)-2$$\mathrm{i}$$F_{2}$ Figure 8: Fundamental domain
of $\left\langle R\right\rangle$.
$-2$$-1$$0$$1$$k(1+\lambda)-2$$\mathrm{i}$$F$ Figure 9: Fundamental domain of
$G$.

##  5 The Veech group

For translation surfaces of finite type, the Veech group is always discrete.
This is not true in general for translation surfaces of infinite type but can
be shown for ladder surfaces with parameter $\lambda\in(0,1)$ with the
following lemma.

###### Lemma .

Let $\Gamma$ be the Veech group of the ladder surface with parameter
$\lambda\in(0,1)$. Then the limit set of $\Gamma$ has empty intersection with
the open real segment from $\lambda$ to $\lambda^{-1}$.

###### Proof.

We first determine the slopes of eigen directions of parabolic elements that
correspond to fixed points in $(\lambda,\lambda^{-1})$. The parabolic element
$\begin{pmatrix}1-\lambda&1\\\
-\lambda^{2}&1+\lambda\end{pmatrix}\in\operatorname{SL}(2,\mathbb{R})$ has an
eigen direction with slope $\lambda$ and fixed point
$\lambda^{-1}\in\partial\mathbb{H}$, and the parabolic element
$\begin{pmatrix}1+\lambda&-\lambda^{2}\\\
1&1-\lambda\end{pmatrix}\in\operatorname{SL}(2,\mathbb{R})$ has an eigen
direction with slope $\lambda^{-1}$ and fixed point
$\lambda\in\partial\mathbb{H}$. Therefore, every parabolic element that has a
fixed point in $(\lambda,\lambda^{-1})$ has an eigen direction with a slope
between $\lambda$ and $\lambda^{-1}$. We have already seen in section 3 that
no parabolic element with such an eigen direction exists.

Suppose now that a point in $(\lambda,\lambda^{-1})$ is contained in the limit
set of $\Gamma$. Since the fixed points of hyperbolic elements of $\Gamma$ are
dense in the limit set, there also exists a point $x\in(\lambda,\lambda^{-1})$
which is the fixed point of a hyperbolic element. In particular, $x$ is the
attracting fixed point of a hyperbolic element $h\in\Gamma$. Note that
$\infty$, $0$, and $-1$ are the fixed points of the parabolic elements $T$,
$R^{-1}TR$, and $RTR^{-1}$, respectively, and not all three of them can be the
repelling fixed point of $h$. Hence, there exists an $n\in\mathbb{N}$ such
that at least one of $h^{n}(\infty)$, $h^{n}(0)$, and $h^{n}(-1)$ is contained
in $(\lambda,\lambda^{-1})$. However, this would again correspond to a
parabolic element in $\Gamma$ with a fixed point in $(\lambda,\lambda^{-1})$.
Therefore, $h$ cannot be contained in $\Gamma$. ∎

In particular, we can deduce the following description of $\Gamma$.

###### Proposition (Veech group as Fuchsian group)

The Veech group $\Gamma$ of the ladder surface with parameter
$\lambda\in(0,1)$ is a non-elementary Fuchsian group of the second kind.

###### Proof.

As $\Gamma$ acts discontinuously on a neighborhood of $(\lambda,\lambda^{-1})$
in $\mathbb{H}$, the group $\Gamma$ is a discrete subgroup of
$\operatorname{PSL}(2,\mathbb{R})$, i.e. a Fuchsian group.

On one hand, the fixed points of the parabolic elements $T$, $R^{-1}TR$, and
$RTR^{-1}$ are different elements of the limit set. This implies that the
limit set contains infinitely many elements and $\Gamma$ is not elementary. On
the other hand, the limit set of $\Gamma$ is disjoint from
$(\lambda,\lambda^{-1})$, hence $\Gamma$ is of the second kind. ∎

We need now one more lemma which implies that the candidate group $G$ from the
previous section is a normal subgroup of the Veech group $\Gamma$. For this,
we restrict to $\lambda=\lambda_{k,l}$ with $l=1$. Note that this also implies
$\lambda\in(0,1)$.

###### Lemma .

Let $\lambda=\lambda_{k,1}$. For any $A\in\Gamma$, the conjugates $A^{-1}TA$
and $A^{-1}RA$ are contained in $G$.

###### Proof.

Let $A\in\Gamma$. Then $A^{-1}TA\in\Gamma$ is parabolic and has a fixed point
$c\in\mathbb{R}\cup\\{\infty\\}$. There exists an element $g\in G$ such that
$g\cdot c$ is contained in the closure of $F_{G}$. Note that $F_{G}$ has
exactly one cusp and a hole which cannot contain fixed points of parabolic
elements of $\Gamma$, so $g\cdot c$ has to be $\infty$. In contrast, $g\cdot
c$ is also the fixed point of the parabolic element $gA^{-1}TAg^{-1}$ which
implies that $gA^{-1}TAg^{-1}$ has the same eigen direction as $T$. Hence,
$gA^{-1}TAg^{-1}$ has to fix the horizontal cylinder decomposition from Figure
4. In this decomposition, there exists a widest horizontal cylinder with
circumference $1+\lambda+\lambda^{2}$. Its boundary consists of four saddle
connections of lengths $1$, $\lambda+\lambda^{2}$, $1+\lambda$, and
$\lambda^{2}$. Hence, this boundary has to be fixed pointwise which means that
every parabolic element with horizontal eigen direction has to be a power of
$T$. In particular, $gA^{-1}TAg^{-1}$ is a power of $T$. Hence,
$gA^{-1}TAg^{-1}$ is contained in $G$ and so is $A^{-1}TA$.

Furthermore, $A^{-1}RA$ is elliptic of order $3$ and has a fixed point
$c\in\mathbb{H}$. There exists an element $g\in G$ such that $g\cdot c$ is
either the fixed point of $R$ or is contained in the interior of $F_{G}$. The
image of the geodesics from the fixed point of $R$ to $\infty$, $-1$, and $0$
under $gA^{-1}$ are geodesics from $g\cdot c$ to cusps. Such geodesics cannot
exist for a point in the interior of $F_{G}$, hence $g\cdot c$ has to be the
fixed point of $R$. Therefore, $R$ and $gA^{-1}RAg^{-1}$ are both elliptic
elements of the same order and with the same fixed point. Hence, they generate
the same subgroup and therefore $gA^{-1}RAg^{-1}$ is contained in $G$ and so
is $A^{-1}RA$. ∎

###### Theorem (Generators for Veech group)

The Veech group $\Gamma$ of the ladder surface with parameter $\lambda_{k,1}$
is generated by the parabolic element $P=\begin{pmatrix}1&k\cdot(\lambda+1)\\\
0&1\end{pmatrix}$ and the elliptic element $R=\begin{pmatrix}-1&-1\\\
1&0\end{pmatrix}$.

###### Proof.

Let $F_{\Gamma}$ be a fundamental domain of $\Gamma$ with $F_{\Gamma}\subseteq
F_{G}$ and such that $F_{G}$ is tessellated by translates of $F_{\Gamma}$
under elements of $\Gamma$. As $F_{G}$ contains exactly one cusp and a hole
and as $\Gamma$ cannot have cusps in the hole of $F_{G}$, also $F_{\Gamma}$
needs to have one cusp, which is $\infty$.

Let $A\in\Gamma$. Then we can choose $g\in G$ such that $gA^{-1}\cdot
F_{\Gamma}\subseteq F_{G}$. As in the previous lemma, $gA^{-1}TAg^{-1}$ is a
power of $T$ and $gA^{-1}RAg^{-1}$ is a power of $R$.

Note that, if for an elliptic or parabolic element
$H\in\operatorname{PSL}(2,\mathbb{R})$ and $n,m\in\mathbb{Z}$, we have
$gA^{-1}H^{n}Ag^{-1}=H^{m}$, then $gA^{-1}$ has the same fixed point as $H$.
Hence, $gA^{-1}$ and $H$ are both powers of the same element and hence they
commute. This shows that $n=m$.

In particular, we have $gA^{-1}TAg^{-1}=T$ and $gA^{-1}RAg^{-1}=R$, hence
$gA^{-1}$ commutes with both $T$ and $R$. Recall that nontrivial Möbius
transformations commute if and only if they have the same set of fixed points.
Therefore, we conclude that $gA^{-1}$ is the identity and hence $A\in G$. ∎

If we consider the Veech group in $\operatorname{SL}(2,\mathbb{R})$ instead of
in $\operatorname{PSL}(2,\mathbb{R})$, also the rotation
$\begin{pmatrix}-1&0\\\ 0&-1\end{pmatrix}$ might be contained in the Veech
group. This element would have to preserve the horizontal saddle connection of
maximal length $1+\lambda$ and the vertical saddle connection of maximal
length $1+\lambda$. However, the intersection pattern of these saddle
connections is not preserved under a rotation by $\pi$, hence
$\begin{pmatrix}-1&0\\\ 0&-1\end{pmatrix}$ cannot be an element of the Veech
group.

In contrast, $\begin{pmatrix}0&1\\\ 1&0\end{pmatrix}$ is an affine
orientation-reversing homeomorphism of the ladder surface. Hence, the extended
Veech group $\Gamma^{\pm}$ is generated by $P$, $R$ and $\begin{pmatrix}0&1\\\
1&0\end{pmatrix}$.

### Acknowledgements

I would like to thank Pat Hooper for asking and discussing the question.

## References

  * [BM10] Irene I. Bouw and Martin Möller, _Teichmüller curves, triangle groups, and Lyapunov exponents_ , Annals of Mathematics. Second Series 172 (2010), no. 1, 139–185.
  * [Cha04] Reza Chamanara, _Affine automorphism groups of surfaces of infinite type_ , In the Tradition of Ahlfors and Bers, III (William Abikoff and Andrew Haas, eds.), Contemporary mathematics, vol. 355, 2004, pp. 123–145.
  * [HHW13] W. Patrick Hooper, Pascal Hubert, and Barak Weiss, _Dynamics on the infinite staircase_ , Discrete and Continuous Dynamical Systems 33 (2013), no. 9, 4341–4347.
  * [Hoo13] W. Patrick Hooper, _Grid graphs and lattice surfaces_ , International Mathematics Research Notices 2013 (2013), no. 12, 2657–2698.
  * [HR16] Frank Herrlich and Anja Randecker, _Notes on the Veech group of the Chamanara surface_ , arXiv:1612.06877, 2016.
  * [HT17] W. Patrick Hooper and Rodrigo Treviño, _Indiscriminate covers of infinite translation surfaces are innocent, not devious_ , Ergodic Theory and Dynamical Systems (2017), 1–57.
  * [Mas71] Bernard Maskit, _On Poincaré’s theorem for fundamental polygons_ , Advances in Mathematics 7 (1971), 219–230.
  * [MST19] Alba Málaga Sabogal and Serge Troubetzkoy, _Unique ergodicity for infinite area translation surfaces_ , arXiv:1908.04019, 2019.
  * [Vee89] William A. Veech, _Teichmüller curves in moduli space, Eisenstein series and an application to triangular billiards_ , Inventiones Mathematicae 97 (1989), no. 3, 553–583.