# Picture What you Read

Ignazio Gallo  Shah Nawaz  Alessandro Calefati  Riccardo La Grassa  Nicola
Landro

###### Abstract

Visualization refers to our ability to create an image in our head based on
the text we read or the words we hear. It is one of the many skills that makes
reading comprehension possible. Convolutional Neural Networks (CNN) are an
excellent tool for recognizing and classifying text documents. In addition, it
can generate images conditioned on natural language. In this work, we utilize
CNNs capabilities to generate realistic images representative of the text
illustrating the semantic concept. We conducted various experiments to
highlight the capacity of the proposed model to generate representative images
of the text descriptions used as input to the proposed model.

##  I Introduction

Recent years have seen a surge in multimodal data containing various media
types. Typically, users combine text, image, audio or video to sell a product
over an e-commence platform or express views on social media. The combination
of these media types has been extensively studied to solve various tasks
including classification [1, 2, 3], cross-modal retrieval [4] semantic
relatedness [5, 6], image captioning [7, 8], multimodal named entity
recognition [9, 10] and Visual Question Answering [11, 12]. In addition,
multimodal data fueled an increased interest in generating images conditioned
on natural language [13, 14]. In recent years, generative models based on
conditional Generative Adversarial Network (GAN) have remarkably improved text
to image generation task [15, 16]. Furthermore, generative models based on
Variational Autoencoders are employed to generate images conditioned on
natural language [17, 18]. Generally, image generation from natural language
is divided into phases: the first phase learns the distribution from which the
images are to be generated while the second phase learns a generator, which in
turn produces the image conditioned on a vector from this distribution.

In this work, we are interested in transforming natural language in the form
of technical e-commerce product specifications directly into image pixels. For
example, image pixels may be generated from the text description such as
‘‘Heavy Duty All Purpose Hammer - Forged Carbon Steel Head’’ as shown in Fig.
1. We assume we are given technical specifications of a set of images
available on e-commence platforms, and train the generator block, available
inside our model, from the pixel distribution. We propose to use an ‘up-
convolutional’ generative block for this task and show that it is capable of
generating realistic e-commerce images. Fig. 3 shows some generated images
conditioned on technical product specification along with the original images.

Figure 1: A Neural Model reading natural language (‘‘Heavy Duty All Purpose
Hammer - Forged Carbon Steel Head’’) can generates a representative image
(‘‘Hammer’’).

Following are the main contributions of our work:

  * –

We propose a new loss function to transform a text description into a
representative image;

  * –

The proposed model generates images conditioned on technical e-commerce
specifications. Moreover, it generates images never seen before;

  * –

An end-to-end convolutional model capable of classifying the text and at the
same time generating a representative image of the text. The generated image
can be used as text encoding or as a realistic image representing the object
described in the input document;

  * –

We propose a model that can also be used to transform a multimodal dataset
into a single dataset of images.

Figure 2: A schematic representation of the proposed model. The model extracts
features from the text document using an embedding layer and three different
convolutive filters. Through different deconvolutive layers the textual
features are transformed into an image representative of the text. Finally,
through convolutive layers, the image and the encoded text are classified.

##  II Related Work

Recently, image generation conditioned on natural language has drawn a lot of
attention from the research community. Various approaches have been proposed
based on Variational Autoencoders [17, 18], Auto-regressive models [19] and
optimization techniques [20]. Similarly, GANs based approaches have noticeably
improved image synthesis conditioned on natural language. These approaches
consist of a generator and a discriminator that compete in a two player
minimax game: the discriminator tries to distinguish real data from generated
images, and the generator tries to trick the discriminator. In the proposed
model, the generator and discriminator are part of the same model and are
linked by a single loss function, in order to generate images within the
classification process. In the following paragraph, we reviewed couple of the
ground breaking approaches on image generation conditioned on natural
language.

Reed et al. [13] proposed to learn both generator and discriminator
conditioned on captions. Zhu et al. [16] proposed a generative method to
generate synthesized visual features using the noisy text descriptions about
an unseen class. Xu et al. [21] proposed attentional generative network to
synthesize fine-grained details at different subregions of the image by paying
attentions to the relevant words in the natural language description. Zhang et
al. [22] decomposed text to image generation in two stages: the first stage
GAN sketches the basic shape and color of the object condition on the natural
language, resulting in low resolution image. While the second stage GAN takes
first stage results and natural language to generate high-resolution images
with photo-realistic details.

Furthermore, various approaches have exploited the capability of ‘up-
convolutional’ network to generate realistic images. Dosovitskiy et al. [23]
trained a deconvolutional network with several layers of convolution and
upsampling to generate 3D chair renderings given object style, viewpoint and
color. In this work we are interested in generating new images through up-
sampling but we limit this generative process to a medium resolution.

##  III Model description

Our goal is to train a neural network to generate accurate e-commerce images
from a low-level and noisy text description. We develop an effective loss
function to transform a text document into a representative image and at the
same time exploits the information content of the image and the text, to solve
a classification problem.

Formally, we assume that we are given a dataset of examples
$D=\\{t_{1},\dots,t_{N}\\}$ with targets
$O=\\{(y_{1},\mathcal{I}_{1}),\dots,(y_{N},\mathcal{I}_{N})\\}$. The inputs
$t_{i}$ are text descriptions describing the objects showed in the images
$\mathcal{I}_{i}$. The targets are tuples consisting of two elements: the
class label $y_{i}$ in one-hot encoding and a $RGB$ image $\mathcal{I}_{i}$.

Generated | Original |  Input Text
---|---|---
|  |  draper expert knipex 27723 side trimmer for electronics for cutting head satin without facet 115 mm
|  |  spax universal screw half round head t star plus 4 cut partial shiny thread galvanized with a2j galvanization
|  |  screws mustad panel vitals bronzed 3x20 mm. conf. 500 pcs universal countersunk flat head screw suitable for screwing ...
|  |  sicutool padlocks 2090p 50 width body 50 mm
|  |  sicutool copper hammers 2718 800 total weight 800 copper hammers
|  |  sicutool nippers for electronics and fine mechanics 557gf lenght total mm 125 wire cutters for electronics and fine mechanics
|  |  sicutool circular saws with teeth shown in hartmetall 4840g 150b type null 150b ø mm 150 thickness mm 2 8 hole mm 16 teeth nr 20
|  |  valex wrench 20 x 22mm inclined forks of 15 ° body in chrome vanadium steel with polished finish. size 20x22 mm length 235 mm
|  |  syrom adhesive tape in textile tes special 38 mm x 2 7 m black tightly woven plasticized tape to repair binding edges etc.
|  |  oem 20 pcs sticker number 6 mm 50 black pvc sticker number 6
Figure 3: Some examples of generated images from test dataset, associated with
a correct classification. In some cases, the generated images are slightly
different from the respective expected image but the object shown is very
similar.

Neural networks typically produce class probabilities by using a ‘‘softmax’’
output layer that converts the logit, $a_{i}$, computed for each class into a
probability $p_{i}$, by comparing $a_{i}$ with the other logits. Softmax
function takes an $n$-dimensional vector of real numbers and transforms it
into a vector of real number in range $[0,1]$ which add upto 1.

$p_{i}=\frac{\exp(a_{i})}{\sum_{j}\exp(a_{j})}$ (1)

‘‘Cross entropy’’ indicates the distance between what the model believes the
output distribution should be ($y_{i}$), and what the original distribution
really is. It is defined as

$\mathcal{L}_{0}(y,p)=-\sum_{i}y_{i}\log\left(p_{i}\right)$ (2)

Cross entropy measure is a widely used alternative of squared error. If we
want to minimize the pixel-by-pixel distance between the input image
$\mathcal{I}_{i}$, associated with the text document and a CNN’s features
layer $\mathcal{F}_{i}$ that has the same dimensions as the image
$\mathcal{I}_{i}$, then we can apply the following formula

$\mathcal{L}_{1}(\mathcal{F},\mathcal{I})=\sum_{i}(\mathcal{F}_{i}-\mathcal{I}_{i})^{2}$
(3)

or the following mean version

$\hat{\mathcal{L}_{1}}(\mathcal{F},\mathcal{I})=\frac{1}{N}\sum_{i}(\mathcal{F}_{i}-\mathcal{I}_{i})^{2}$
(4)

$\mathcal{F}_{i}$ is the output of the last transposed convolutions -- also
called fractionally strided convolutions -- used to upsampling the text
features to attain a feature layer having the same size of the image
$\mathcal{I}$.

The final loss function we used in this work is the following

$\mathcal{L}=\mathcal{L}_{0}(y,p)+\lambda\mathcal{L}_{1}(\mathcal{F},\mathcal{I})$
(5)

but we also performed experiments replacing the $\mathcal{L}_{1}$ with the
$\hat{\mathcal{L}_{1}}$.

$\hat{\mathcal{L}}=\mathcal{L}_{0}(y,p)+\lambda\hat{\mathcal{L}_{1}}(\mathcal{F},\mathcal{I})$
(6)

In this last case the contribution of the lambda parameter has a different
effect with the same $\lambda$ values, this because the interval of
variability of $\mathcal{L}_{1}$ and $\hat{\mathcal{L}_{1}}$ are very
different. For example, using the Eq. 6 as loss function, we need much larger
$\lambda$ values to take advantage of the contribution of
$\hat{\mathcal{L}_{1}}$ and obtain in $\mathcal{F}$ a realistic image,
representative of the object described in the text $t_{i}$.

The $\lambda$ parameter is important to balance the contribution of
$\mathcal{L}_{0}$ against $\mathcal{L}_{1}$. Setting $\lambda=0$ we minimize
only $\mathcal{L}_{0}$ and therefore the feature layer $\mathcal{F}$,
representing the input text, will be very different from the image
$\mathcal{I}$. In Fig. 5 we have a graphical representation of the image
learned by minimizing Eq. 5, using various $\lambda$ values and it is
important to note that when $\lambda=0$ the model does not generate realistic
images.

Learning proceeds by minimizing the loss function $\mathcal{L}$ via Adam
optimizer [24]. Since we are using the combination of two loss functions to
modify the weights of the entire neural network, we know that within the image
$\mathcal{F}$ that we generate, it contains text representations. In fact, in
many cases it may happen that the $\mathcal{F}$ image cannot be interpreted as
one of the objects belonging to a particular class but the classification is
correct.

We experimented with a network for generating images of size $100\times 100$.
The structure of the generative network is shown in Fig. 2. Conceptually, the
network we propose can be seen as a convolutive classification model for text
documents, that incorporates a generative network. The starting point of the
proposed model is the classification model of sentences proposed by Kim [25]
to transform a text document into a features vector. This is followed by a set
of 4 deconvolutive layers that transform textual features into an RGB image
that we can then generate. Finally, we used a sequence of 4 convolutive layers
that transform the generated image into features for the classification
problem.

###  III-A Text features

The input to our model are sequences of words $[w_{i},\dots,w_{|t|}]$ from
each input document $t$, where each word is drawn from a vocabulary $V$. Words
are represented by distributional vectors $\mathbf{w}\in\mathbb{R}^{1\times
d}$ looked up in a word embeddings matrix
$\mathbf{W}\in\mathbb{R}^{d\times|V|}$. This matrix is formed by simply
concatenating embeddings of all words in $V$.

For each input text $t$, we build a matrix
$\mathbf{S}\in\mathbb{R}^{d\times|t|}$, where each row $i$ represents a word
embedding $w_{i}$ at the corresponding position $i$ in the document $t$. To
capture and compose features of individual words in a given text from low-
level word embeddings into higher level semantic concepts, the neural network
applies a series of transformations to the input matrix $S$ using convolution,
non-linearity and pooling operations. The convolution operation between $S$
and a filter $\mathbf{F}\in\mathbb{R}^{d\times m}$ of height $m$ results in a
vector $\mathbf{c}\in\mathbb{R}^{|t|+m−1}$. In our model we used three groups
of $128$ different kernels in parallel, having dimensions $d\times 3$,
$d\times 4$ and $d\times 5$. In this way we obtained three feature maps
$\mathbf{c}_{i}$, having different lengths. Note that the convolution filter
is of the same dimensionality $d=128$ as the input sentence matrix, so this is
like a 1-D convolution operation. To allow the network to learn an appropriate
threshold, we also added a bias vector $b\in\mathbb{R}^{n}$ for each feature
map $\mathbf{c}_{i}$.

Each convolutional layer is followed by the Rectified Linear Unit (ReLU) non-
linear activation function, applied element-wise. ReLU speeds up the training
process [26], defined as $\max(0,x)$ to ensure that feature maps are always
positive. To capture the most important feature -- one with the highest value
-- for each feature map, we apply a max-overtime pooling operation [27] over
each feature map. In this way, for each particular filter we take the maximum
value as the feature corresponding to this particular filter. The
convolutional layer utilizing the activation function and the pooling layer
acts as a non-linear feature extractor.

Up to this point we have described the process by which a single feature is
extracted from a single filter. The set of these individual features are
linked into a single layer and then connected to a subsequent fully-connected
layer that has the purpose of connecting the textual features with the next
block of deconvolution layers used to transform textual features into an
image.

###  III-B Up-sampling

The purpose of the up-sampling block is to transform the features extracted
from the text into image format that best represents the description contained
in the text.

We use 4 deconvolution layers, each of which doubles the size of the input
features. In practice, we start with 512 features maps of size $7\times 7$ and
then move to a second layer with 256 features maps of size $13\times 13$,
followed by a new layer having 128 features maps o size $25\times 25$, another
layer with 64 features maps of size $50\times 50$ and finally, a last layer
$\mathcal{F}$ with 3 features maps of size $100\times 100$. The up-sampling
blocks consist of the nearest-neighbor up-sampling followed by a $5\times 5$
stride 1D convolution. Batch normalization and ReLU activation are applied
after every convolution except the last one where we used a sigmoid to
guarantee that the values of features maps $\mathcal{F}$ were all in the range
$[0,1]$. This last layer can be interpreted directly as an image.

###  III-C Classification

The last block is similar to a convolutive neural network that feeds the
features $\mathcal{F}$ to 4 successive convolutive layers. Each of these
layers produces features maps of size $50\times 50$, $25\times 25$, $13\times
13$ and $7\times 7$ respectively. Starting from the largest layer, we used
$2\times 2$ stride and the following number of $5\times 5$ filters: 64, 32, 16
and 8 respectively.

The convolutional layers are followed by two fully connected layers having
1024 and 512 neurons respectively.

For regularization we employ dropout before the output layer with a constraint
on $l_{2}$-norms of the weight vectors. Dropout prevents co-adaptation of
hidden units by randomly dropping out a proportion $p$ of the hidden units
during foward backpropagation.

The last layer is the output layer that has a number of neurons equal to the
number of classes of the problem that we want to learn.

Figure 4: 11 different executions made on the validation set of the Ferramenta
dataset, to estimate the best value for the $\lambda$ parameter of the
proposed loss function in Eq. 5. The best value obtained is for $\lambda=0.8$.

##  IV Datasets

In multimodal dataset, modalities are obtained from multiple input sources.
Dataset used in this work consists of images and accompanying text
descriptions. We select Ferramenta [3] multimodal dataset that are created
from e-commerce website. Table I shows information on this dataset. Ferramenta
multi-modal dataset [3] is made up of $88,010$ adverts split in $66,141$
adverts for train set and $21,869$ adverts for test set, belonging to $52$
classes. Ferramenta dataset provides a text and a representative image for
each commercial advertisement. It is interesting to note that text
descriptions in this dataset are in Italian Language.

TABLE I: Information on multi-modal datasets used in this work. A multi-modal dataset consists of an image and accompanying text description. The last column indicates the text description language. Dataset | #Cls | Train | Test | Lang.
---|---|---|---|---
Ferramenta | 52 | 66,141 | 21,869 | IT

Another dataset used in our work is the Oxford-102 Flowers dataset [28]
containing 8,189 flow images in 102 categories. Each image in this dataset is
annotated with 10 descriptions provided by [29]. Because this dataset has
class-disjoint training and test sets, with 82 train+val and 20 test classes,
we randomly shuffled all the classes and split back into training and test. In
this way, all the classes available in the training set are also present in
the test set.

$\lambda=0$ | $\lambda=0.2$ | $\lambda=0.4$ | $\lambda=0.6$ | $\lambda=0.8$ | $\lambda=1$
---|---|---|---|---|---
|  |  |  |  |
$\lambda=1.2$ | $\lambda=1.4$ | $\lambda=1.6$ | $\lambda=1.8$ | $\lambda=2$ | Expected
|  |  |  |  |
Figure 5: Some examples of generated images from Ferramenta test dataset. The
models trained for each $\lambda$ by minimizing Eq. 5, were trained for 20
epochs only, to speed up the experiment.

##  V Experiments

The proposed approach transforms text descriptions into a representative
image. We use standard CNN hyperparameters. The initial learning rate is set
to $0.001$ along with Adam as optimizer. In our experiments, accuracy is used
to measure classification performance.

The purpose of the first experimental phase is to analyze the generative
capacity of our model. We conducted following experiments with this aim in
mind: (1) estimate of the best $\lambda$ parameter for Eq. 5, (2) qualitative
analysis of the generated images $\mathcal{F}$, (3) ability of the model to
generate new images according to the description given in input.

As a second group of experiments we have analyzed the capacity of the proposed
model to generate embedding in image format of the input text. We conducted
following experiments with this second aim in mind: (1) estimate of the best
lambda parameter to obtain the most significant encoding, (2) extraction of a
new dataset of encoded text in image format to compute the classification
accuracy using a well-known CNN.

The first experiment concerned the estimation of the best $\lambda$ value to
be used in the proposed loss function described in Eq. 5. To achieve this, we
first extracted a validation set from our training set and on this we
calculated the classification accuracy to extract the best value to assign to
the lambda parameter. Fig. 4 shows the results of all the experiments
conducted on the validation set. The accuracy results reported in this figure
were obtained by averaging the accuracy values of 5 runs. As can be seen from
the figure, the best value we obtained is for $\lambda=0.8$. To visually
analyze the effect of the $\lambda$ parameter, we also performed a quick test
by training 11 different models for 20 epochs using
$\lambda\in\\{0,0.2,0.4,0.6,0.8,1,1.2,1.4,1.6,1.8,2\\}$. Then we compared some
of the resulting images as shown in Fig. 5. The best defined image is for
$\lambda=0.8$ while for $\lambda=0$ we have an abstract visual representation
since the second part of the loss function described in Eq. 3 has been
removed.

As a second experiment, we first trained a model using the entire training set
and then visually analyzed generated images with our model on the test set.
Fig. 3 shows some examples of generated images beside the images we expected
and the text passed as input. As you can see from the figure, many of the
images generated are identical to those we expect to find, while some of them
represent the same object but arranged differently (see for example the screw
and the pliers with the red handle). We observed that some images have no
visual meaning and do not represent any of the objects in the training set,
even if in many of these cases the classification is correct. This means that
the information extracted from the text is still present in the image which is
then used by the last block to classify.

In generalization, the proposed model has the ability to generate images that
it has never seen in training and this ability is directly correlated with the
words we feed in input. In this experiment we tried to mix the tokens of two
descriptions belonging to different categories to highlight the capacity. As
can be seen from Fig. 8, by taking some tokens from two different descriptions
and feeding them to the neural model, in some cases this produces images that
are a combination of the objects representing the two descriptions. For
example, in the same Fig. 8 you can see an image of an object that is the
composition of a screw and a clamp. This is because in the description given
as input to the model, the most important tokens of both objects are present.

Figure 6: Columns (a) and (b) show some examples of images extracted from
Flowers and Ferramenta datasets, respectively. The columns to the right of (a)
and (b) show the text encodings extracted as features layer $\mathcal{F}$
using $\lambda=6$ in Eq. 6.  Figure 7: The top row contains encodings for the
same image belonging to the Ferramenta dataset when the model was trained
using Eq. 6 with $\lambda$ parameters showed on the top. The images on bottom
row are created using an image of the Flowers dataset. Below each image is the
test accuracy obtained with the corresponding $\lambda$ parameter.

Using the loss function of Eq. 6, which has a much more restricted range of
variability, it is possible to give more emphasis to the encoding of the input
text in image format. To find the best $\lambda$ parameter that produces the
best encoding we varied the parameter and for each of its values we computed
the classification accuracy on the test set of the Ferramenta and Flowers
datasets. Fig. 7 shows the encodings and the accuracy obtained when the
parameter changes. On these results we performed the last experiment using the
$\lambda=6$ parameter.

Figure 8: A set of $\mathcal{F}_{k}$ images generated by the proposed model.
$\mathcal{F}_{i}$ and $\mathcal{F}_{j}$ have generated starting from text
documents $t_{i}$ and $t_{j}$ respectively. All other $\mathcal{F}_{k}$ images
were generated by combining different percentages of tokens extracted
simultaneously from $t_{i}$ and $t_{j}$. The two colored rectangles below
$\mathcal{F}_{k}$ images are indicative of the percentages of tokens from
$t_{i}$ and $t_{j}$ used to generate the $\mathcal{F}_{k}$ images.

In this latest experiment we extracted two new image datasets using two
different models trained on the two datasets. In Fig. 6 you can see some
examples of images generated, alongside the original image of the dataset. It
can be seen how different source images correspond to a different text
encoding. To analyze the information content of these two new datasets we have
trained two CNN AlexNet to calculate their classification accuracy. For the
Ferramenta dataset we got $93.68\%$ while for the Flowers dataset we got
$99.05\%$. The first result is slightly higher than the one published in [30]
while the second result obtained on the Flowers dataset is incredibly high.
The reason we got such high accuracy is because our dataset contains 10
different text descriptions associated with the same image. Having divided the
training set randomly into training and test, the same images can be found
both in the training set and in the test set. Ultimately this means that the
new datasets created do not only encode information extracted from the text
but also from images.

##  VI Conclusion

In this work we have proposed a new approach to generate an image that is
representative of a noisy text description available in natural language. The
approach we proposed uses a new loss function in order to simultaneously
minimize the classification error and the distance between the desired image
and a features map of the same model. The qualitative results are very
interesting but, for the moment, we have ignored the classification
performances because this was not our focus of the present work. In the future
we want to exploit the same idea to try to improve the classification accuracy
that can be obtained with a single convolutive neural model.

Another interesting aspect emerged from this work is that the same approach we
proposed can be used to encode in image format both the information contained
in the input text and the information extracted from the image associated with
the text. This feature is very interesting to be able to incorporate
multimodal information into a single image dataset. In this way, multimodal
information can be processed directly by a single CNN normally used to process
only images.

## References

  * [1] J. Arevalo, T. Solorio, M. Montes-y Gómez, and F. A. González, ‘‘Gated multimodal units for information fusion,’’ _arXiv preprint arXiv:1702.01992_ , 2017.
  * [2] D. Kiela, E. Grave, A. Joulin, and T. Mikolov, ‘‘Efficient large-scale multi-modal classification,’’ _Proceedings of AAAI 2018_ , 2018.
  * [3] I. Gallo, A. Calefati, and S. Nawaz, ‘‘Multimodal classification fusion in real-world scenarios,’’ in _Document Analysis and Recognition (ICDAR)_. IEEE, 2017, pp. 36--41.
  * [4] L. Wang, Y. Li, and S. Lazebnik, ‘‘Learning deep structure-preserving image-text embeddings,’’ in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 5005--5013.
  * [5] D. Kiela and L. Bottou, ‘‘Learning image embeddings using convolutional neural networks for improved multi-modal semantics,’’ in _Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , 2014, pp. 36--45.
  * [6] C. W. Leong and R. Mihalcea, ‘‘Going beyond text: A hybrid image-text approach for measuring word relatedness.’’ in _IJCNLP_ , 2011, pp. 1403--1407.
  * [7] A. Karpathy and L. Fei-Fei, ‘‘Deep visual-semantic alignments for generating image descriptions,’’ in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2015, pp. 3128--3137.
  * [8] K. Xu, J. Ba, R. Kiros, K. Cho, A. Courville, R. Salakhudinov, R. Zemel, and Y. Bengio, ‘‘Show, attend and tell: Neural image caption generation with visual attention,’’ in _International conference on machine learning_ , 2015, pp. 2048--2057.
  * [9] Q. Zhang, J. Fu, X. Liu, and X. Huang, ‘‘Adaptive co-attention network for named entity recognition in tweets,’’ in _Thirty-Second AAAI Conference on Artificial Intelligence_ , 2018.
  * [10] O. Arshad, I. Gallo, S. Nawaz, and A. Calefati, ‘‘Aiding intra-text representations with visual context for multimodal named entity recognition,’’ _arXiv preprint arXiv:1904.01356_ , 2019.
  * [11] A. Fukui, D. H. Park, D. Yang, A. Rohrbach, T. Darrell, and M. Rohrbach, ‘‘Multimodal compact bilinear pooling for visual question answering and visual grounding,’’ _Proceedings of Empirical Methods in Natural Language Processing, EMNLP 2016_ , pp. 457--468, 2016.
  * [12] P. Anderson, X. He, C. Buehler, D. Teney, M. Johnson, S. Gould, and L. Zhang, ‘‘Bottom-up and top-down attention for image captioning and visual question answering,’’ in _CVPR_ , vol. 3, no. 5, 2018, p. 6.
  * [13] S. Reed, Z. Akata, X. Yan, L. Logeswaran, B. Schiele, and H. Lee, ‘‘Generative adversarial text to image synthesis,’’ _arXiv preprint arXiv:1605.05396_ , 2016.
  * [14] M. Cha, Y. Gwon, and H. Kung, ‘‘Adversarial nets with perceptual losses for text-to-image synthesis,’’ in _2017 IEEE 27th International Workshop on Machine Learning for Signal Processing (MLSP)_. IEEE, 2017, pp. 1--6.
  * [15] S. Hong, D. Yang, J. Choi, and H. Lee, ‘‘Inferring semantic layout for hierarchical text-to-image synthesis,’’ in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 7986--7994.
  * [16] Y. Zhu, M. Elhoseiny, B. Liu, X. Peng, and A. Elgammal, ‘‘A generative adversarial approach for zero-shot learning from noisy texts,’’ in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 1004--1013.
  * [17] E. Mansimov, E. Parisotto, J. Ba, and R. Salakhutdinov, ‘‘Generating images from captions with attention,’’ in _ICLR_ , 2016.
  * [18] E. Mansimov, E. Parisotto, J. L. Ba, and R. Salakhutdinov, ‘‘Generating images from captions with attention,’’ _arXiv preprint arXiv:1511.02793_ , 2015.
  * [19] S. Reed, A. van den Oord, N. Kalchbrenner, S. G. Colmenarejo, Z. Wang, Y. Chen, D. Belov, and N. de Freitas, ‘‘Parallel multiscale autoregressive density estimation,’’ in _Proceedings of the 34th International Conference on Machine Learning-Volume 70_. JMLR. org, 2017, pp. 2912--2921.
  * [20] A. Nguyen, J. Clune, Y. Bengio, A. Dosovitskiy, and J. Yosinski, ‘‘Plug & play generative networks: Conditional iterative generation of images in latent space,’’ in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2017, pp. 4467--4477.
  * [21] T. Xu, P. Zhang, Q. Huang, H. Zhang, Z. Gan, X. Huang, and X. He, ‘‘Attngan: Fine-grained text to image generation with attentional generative adversarial networks,’’ in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 1316--1324.
  * [22] H. Zhang, T. Xu, H. Li, S. Zhang, X. Wang, X. Huang, and D. N. Metaxas, ‘‘Stackgan: Text to photo-realistic image synthesis with stacked generative adversarial networks,’’ in _Proceedings of the IEEE International Conference on Computer Vision_ , 2017, pp. 5907--5915.
  * [23] A. Dosovitskiy, J. T. Springenberg, M. Tatarchenko, and T. Brox, ‘‘Learning to generate chairs, tables and cars with convolutional networks,’’ _IEEE transactions on pattern analysis and machine intelligence_ , vol. 39, no. 4, pp. 692--705, 2016.
  * [24] D. P. Kingma and J. Ba, ‘‘Adam: A method for stochastic optimization,’’ _arXiv preprint arXiv:1412.6980_ , 2014.
  * [25] Y. Kim, ‘‘Convolutional neural networks for sentence classification,’’ in _Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, EMNLP_ , 2014, pp. 1746--1751.
  * [26] V. Nair and G. E. Hinton, ‘‘Rectified linear units improve restricted boltzmann machines,’’ in _Proceedings of the 27th international conference on machine learning (ICML-10)_ , 2010, pp. 807--814.
  * [27] R. Collobert, J. Weston, L. Bottou, M. Karlen, K. Kavukcuoglu, and P. Kuksa, ‘‘Natural language processing (almost) from scratch,’’ _Journal of machine learning research_ , vol. 12, no. Aug, pp. 2493--2537, 2011.
  * [28] M.-E. Nilsback and A. Zisserman, ‘‘Automated flower classification over a large number of classes,’’ in _2008 Sixth Indian Conference on Computer Vision, Graphics & Image Processing_. IEEE, 2008, pp. 722--729.
  * [29] S. Reed, Z. Akata, X. Yan, L. Logeswaran, B. Schiele, and H. Lee, ‘‘Generative adversarial text to image synthesis,’’ in _Proceedings of the 33rd International Conference on International Conference on Machine Learning - Volume 48_ , ser. ICML’16. JMLR.org, 2016, pp. 1060--1069.
  * [30] I. Gallo, A. Calefati, S. Nawaz, and M. K. Janjua, ‘‘Image and encoded text fusion for multi-modal classification,’’ in _2018 International Conference on Digital Image Computing: Techniques and Applications (DICTA)_ , Dec 2018, pp. 1--7.


# A hybrid quantum-classical approach to warm-starting optimization

Vanessa Dehn<EMAIL_ADDRESS>Thomas Wellens
<EMAIL_ADDRESS>Fraunhofer Institute for Applied Solid State
Physics IAF, Tullastr. 72, 79108 Freiburg, Germany

###### Abstract

The Quantum Approximate Optimization Algorithm (QAOA) is a promising candidate
for solving combinatorial optimization problems more efficiently than
classical computers. Recent studies have shown that warm-starting the standard
algorithm improves the performance. In this paper we compare the performance
of standard QAOA with that of warm-start QAOA in the context of portfolio
optimization and investigate the warm-start approach for different problem
instances. In particular, we analyze the extent to which the improved
performance of warm-start QAOA is due to quantum effects, and show that the
results can be reproduced or even surpassed by a purely classical
preprocessing of the original problem followed by standard QAOA.

##  1 Introduction

The quantum approximate optimization algorithm (QAOA) [1, 2] is often
presented as a candidate for the efficient solution of combinatorial
optimization problems in the current noisy intermediate-scale quantum (NISQ)
era [3], i.e. the era of working on quantum hardware with error rates and
limitations in size [4]. However, an advantage over classical algorithms has
not yet been proven, so various modifications of QAOA such as warm-start QAOA,
recursive QAOA, spanning tree QAOA [5, 6, 7, 8] or using an alternative
objective function [9] are proposed to further improve its performance.

The warm-start approach is a well-known recipe for reducing the time needed to
solve an optimization problem by starting the optimization with an efficiently
computable approximate solution [10]. Applying this concept to quantum
optimization, it has been shown that warm-starting the QAOA based on the
classically obtained solution of a relaxed continuous optimization problem
shows an improvement at a lower depth [5, 11]. The warm-start QAOA has been
applied and discussed in the context of the MaxCut problem [12, 13], where the
key idea is to find the maximum cut of a graph. Various problems, such as
unstructured clustering problems, can be mapped to such a graph optimization
problem and are shown to be solved using the warm-start QAOA [14]. An
extensive study of warm-start including the selection and optimization of
hyperparameters (also applied to the MaxCut problem) is reported in [15]. In
addition to the above mentioned versions of warm-start, referred to as the
continuous warm-start procedure, Egger et al. [5] have proposed modifications
such as the rounded warm-start QAOA, where the initial state is generated by
randomly rounding the SDP (semidefinite programming) relaxation of the QUBO
problem. Another approach, called classically-boosted quantum optimization
algorithm (CBQOA) [16], also uses a rounded solution of the SDP relaxation as
initial state, followed by an efficiently-implementable continuous-time
quantum walk.

From a general perspective, warm-starting quantum optimization is an example
of a hybrid approach, where classical tools for solving a combinatorial
optimization problem are combined with quantum methods. The idea is to analyze
the processing steps throughout an optimization algorithm and to evaluate
which steps are more efficient with classical methods and in which steps
quantum methods are more suitable [17, 18]. In this paper, we focus on the
problem of portfolio optimization and investigate the original warm-start QAOA
proposed in [5] to analyze what factors are responsible for its improved
performance compared to its standard version. In particular, we compare the
performance of warm-start QAOA and standard QAOA for different problem
instances, depending on how well the classically obtained solution of the
relaxed problem (serving as the starting point of warm-start QAOA) agrees with
the desired solution of the combinatorial optimization problem. Moreover, we
propose a classical preprocessing scheme for standard QAOA, thereby
formulating a hybrid quantum-classical approach to warm-start optimization
that reproduces or even outperforms the performance of the actual warm-start
QAOA.

This paper is organized as follows: in Sec. 2, we give a short introduction to
the portfolio optimization problem and a brief presentation of solving the
problem for random problem instances by using the warm-start QAOA in
comparison to the standard QAOA. We then subdivide our problem instances into
"hot" and "cold" optimizable instances, i.e. instances with a relaxed solution
that is either closer to or further from the optimal solution, and discuss the
performance of warm-start vs. standard QAOA for different instances in Sec. 3.
In Sec. 4, we present a classical preprocessing method for the standard QAOA
routine and analyse its performance in comparison with standard and warm-start
QAOA for random, hot and cold problem instances. Finally, in Sec.5 we conclude
and give a brief perspective for further investigations.

##  2 Background

###  2.1 Formulation of the Portfolio Problem

In the general quadratic unconstrained binary optimization (QUBO) problem, a
cost function is defined on $N$ binary variables
$F:\mathbb{B}^{N}\rightarrow\mathbb{R}$:

$F({\bf
x})=\sum_{i,j=1}^{N}F_{ij}x_{i}x_{j}+\sum_{i=1}^{N}f_{i}x_{i}\leavevmode\nobreak\
,$ (1)

with symmetric matrix $F_{ij}\in\mathbb{R}^{N\times N}$, vector
$f_{i}\in\mathbb{R}^{N}$ and $N$ binary variables ${\bf
x}=(x_{1},x_{2},\dots,x_{N})\in\\{0,1\\}^{N}$. Note that, since
$x_{i}=x_{i}^{2}$ for binary variables, the vector $f_{i}$ can also be added
to the diagonal of the matrix $F_{ij}$. However, we will keep the linear term
in the following, since it will be relevant for the continuous relaxation (see
below). The solution of the problem is given by $\bf x^{\rm opt}$ that
minimizes the above cost function.

Considering the portfolio problem as our problem model, we can directly
identify the matrix $F_{ij}$ with the covariance matrix of the stock returns
$\sigma_{ij}$ and the vector $f_{i}$ with the expected return $\mu_{i}$,
respectively. The binary variables $x_{i}$ represent the portfolio weights,
which are 1 or 0, depending on the stock being chosen for the portfolio or
not. Additionally, with the parameter $q\in[0,1]$ the risk-preference,
depending on whether the risk or the return is to be taken into account with
larger weight, can be set. The function that has to be minimized thus reads:

$F_{C}({\bf
x})=q\sum_{i,j=1}^{N}x_{i}x_{j}\sigma_{ij}-(1-q)\sum_{i=1}^{N}x_{i}\mu_{i}\leavevmode\nobreak\
.$ (2)

The investment of a fixed amount of money can be addressed by introducing a
budget constraint $B=\sum_{i}x_{i}$, where $B$ is the number of the assets
selected from the $N$ available assets for the portfolio. In order to deal
with this constraint, a penalty term, denoted with $A$, is added to the cost
function. Finally, the cost function of our QUBO problem is obtained as:

$F({\bf x})=F_{C}({\bf
x})+A\left(B-\sum_{i=1}^{N}x_{i}\right)^{2}\leavevmode\nobreak\ .$ (3)

The routine that is used to determine a suitable factor for $A$ is described
in [19]. In the following, we refer to a created portfolio as "feasible" only
if the budget constraint is met.

###  2.2 Standard and warm-start QAOA

Figure 1: Mean approximation ratio $r$ (a) and ground state probability $P$
(b), both as a function of the number $p$ of QAOA iterations for standard
(teal line) and warm-start (pink line) QAOA for an ensemble of 20 random
portfolio instances consisting of $N=10$ assets with budget constraint of
$B=5$. Compared to the standard mixer, the warm-start mixer yields a better
performance (i.e. approximation ratio tends towards $r=1$ and probabilities
are higher) since the initial state ($p=0$) for the warm-start version,
prepared with the relaxed solution, is already closer to the optimal solution
than for the standard mixer.

In order to address the optimization problem with the quantum computer, the
cost function has to be mapped onto a cost Hamiltonian $\hat{F}$. This can be
done by converting the binary variables to operators with
$x_{i}=(\hat{I}_{i}+\hat{Z}_{i}/2)$, with $\hat{I}_{i}\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ \hat{Z}_{i}$ being the identity and the
Pauli-$\hat{Z}$ operator acting on qubit $i$ ($i=1,2,\dots,N$). The QAOA
circuit then generates the parametrized variational quantum state

$\displaystyle\ket{\psi_{\gamma,\beta}}_{\text{std}}=\hat{U}_{\text{std}}(\beta_{p})e^{-i\gamma_{p}\hat{F}}...\leavevmode\nobreak\
\hat{U}_{\text{std}}(\beta_{1})e^{-i\gamma_{1}\hat{F}}\ket{\psi_{0}}_{\text{std}}$
(4)

with parameters $\vec{\gamma}=(\gamma_{1},...,\gamma_{p})$ and
$\vec{\beta}=(\beta_{1},...,\beta_{p})$ and number of iterations $p$, and
standard mixer $\hat{U}_{\text{std}}$:

$\hat{U}_{\text{std}}(\beta)=e^{i\beta\sum_{i=1}^{N}\hat{X}_{i}}.$ (5)

The initial state is chosen to be $\ket{\psi_{0}}=\ket{+}^{\otimes N}$, which
is the minimum energy eigenstate of the mixing operator
$-\sum_{i}\hat{X}_{i}$. Further, all qubits are measured in the computational
basis to determine the expectation value $\langle\hat{F}\rangle$. This
intermediate result is then passed on to a classical optimizer, which updates
the parameters to minimize the expectation value.
The form of the generated quantum state of QAOA, see Eq. (4), is inspired by
adiabatic quantum computing (AQC) in terms of starting in the ground state of
the mixing Hamiltonian, which is then gradually transferred to the ground
state of the cost Hamiltonian by approximating the adiabatic annealing path
via Trotterization [20, 21] for iteration depth $p\rightarrow\infty$.
Therefore, the performance of QAOA improves with increasing $p$ [22].

In contrast to the standard variant of QAOA, which starts from a uniform
superposition $\ket{\psi_{0}}=\ket{+}^{\otimes N}$ of all portfolios, the
warm-start variant, introduced by [5, 13], starts with solving the continuous
relaxation of the QUBO problem

${\bf x^{*}}=\underset{{\bf\tilde{x}}\in[0,1]^{N}}{\text{arg
min}}\leavevmode\nobreak\ F({\bf\tilde{x}})$ (6)

where the variables ${\bf\tilde{x}}$ are not binary, but real numbers
$\in[0,1]$. The continuous optimization problem (6) can be easily solved by
classical optimization if the matrix $F_{ij}$, see Eq. (1), is positive-
semidefinite (leading to a convex quadratic problem). For our problem, this is
the case, since $F_{ij}=q\sigma_{ij}+A\delta_{ij}$, see Eqs. (1)-(3), with
positive semidefinite $\sigma_{ij}$ (as a covariance matrix) and $q,A\geq 0$.
In the general case, if $F_{ij}$ is not positive semidefinite, the problem can
be "convexified" either by changing the diagonal of $F$ together with the
linear term $f_{i}$ such that the binary problem remains invariant (i.e.
$F_{ii}\to F_{ii}+c$, $f_{i}\to f_{i}-c$) [23] or by a semidefinite
programming (SDP) procedure, see [5].

The optimal solution ${\bf x^{*}}=(x_{1}^{*},x_{2}^{*},\dots,x_{N}^{*})$ of
Eq. (6) can now be used to initialize the QAOA, thus warm-starting it. For the
warm-start algorithm as introduced in [5], the initial state of the standard
algorithm $\ket{\psi_{0}}_{\text{std}}=\ket{+}^{\otimes N}$ is replaced by the
state

$\displaystyle\ket{\psi_{0}}_{\text{WS}}=\overset{N}{\underset{i=1}{\otimes}}\hat{R}_{Y}(\theta_{i})\ket{0}_{N}$
(7)

with angle $\theta_{i}=2\,\text{arcsin}(\sqrt{x_{i}^{*}})$. Further, the mixer
$\hat{U}_{\text{std}}(\beta)$ is replaced by
$\hat{U}_{\text{ws}}(\beta)=e^{-i\beta\hat{M}_{\text{ws}}}$ with mixing
operator

$\displaystyle\hat{M}_{\text{ws}}=-\sum_{i=1}^{N}\left[\text{sin}(\theta_{i})\hat{X}_{i}+\text{cos}(\theta_{i})\hat{Z}_{i}\right]$
(8)

whose ground state is the initial state $\ket{{\psi_{0}}}_{\text{WS}}$. When a
bit in the relaxed solution is exactly set to 0 or 1 (i.e. $x_{i}^{*}=0$ or
$x_{i}^{*}=1$), the respective qubit is then initialized either in the
$\ket{0}$ or $\ket{1}$ state. Since the cost Hamiltonian only applies
$Z$-gates, the qubits in the above mentioned states will remain in these
states during the optimization. To avoid this, a regularization parameter can
be introduced [5] which, however, we will not consider in the present paper.

To evaluate the performance of the optimization procedure, i.e. the quality of
the solution, we use as a measure for both variants (standard and warm-start)
the approximation ratio

$r(x_{1},...,x_{N})=\begin{cases}\frac{F_{C}(x_{1},...,x_{N})-F_{C}^{\text{max}}}{F_{C}^{\text{min}}-F_{C}^{\text{max}}}&\text{if
$\sum_{i}x_{i}=B$}\\\ 0&\text{if $\sum_{i}x_{i}\neq B$}\\\ \end{cases}$ (9)

averaged over the different measurements results $x_{1},...,x_{N}$ performed
on the final state of the optimized QAOA circuit, where $F_{C}^{\text{max}}$
and $F_{C}^{\text{min}}$ indicating the worst and the best solution among all
feasible solutions. Measuring the optimal solution yields an approximation
ratio of 1, whereas measuring the worst feasible or unfeasible solution yields
an approximation ratio of 0. Note, that the approximation ratio is formulated
with the cost function $F_{C}$, see Eq. (2), to have a measure that is
independent of the choice of the penalty term $A$. As alternative measure, we
also consider the probability $P$ of measuring the optimal solution (also
called "ground state probability" in the following).

Concerning our portfolio model, we use an ensemble of 20 randomly generated
portfolio instances, each consisting of $N=10$ assets (and budget constraint
$B=5$), corresponding to $N=10$ qubits in the quantum circuit. The solution of
the relaxed problem, which is used to initialize the warm-start QAOA, is
obtained using a gradient-based optimizer, whereas a gradient-free optimizer
was chosen for the classical subroutine of QAOA (see [19] for details). The
quantum circuits are executed using the qasm simulator with a fixed number of
shots (here: 1000).

For both variants (standard and warm-start), we compare the mean approximation
ratio $r$ and the ground state probability $P$ for increasing iteration depth
$p$ (up to $p_{\text{max}}=7$), see Fig. 1. The standard deviation obtained
from the 20 random instances is represented by the error bars. As expected, we
find that, both, the approximation ratio $r$ and the ground state probability
$P$ for the warm-start QAOA is significantly higher than for the standard
QAOA, since the initial state (at $p=0$) for warm-start QAOA is already closer
to the desired ground state energy of the problem Hamiltonian, i.e. the
optimal solution. From the varying errorbars, we also observe that the
fluctuations between the 20 random instances are larger for warm-start QAOA
(especially in case of the ground state probability $P$). Note that, in
contrast to standard QAOA, warm-start QAOA exhibits some fluctuations already
for the initial state ($p=0$), depending on how well the solutions of the
relaxed and the binary problem agree with each other.

##  3 Warm-start QAOA for different Problem Instances

Figure 2: Deviations $\varepsilon$ and $\sigma$ between the solutions of the
relaxed and binary problem for 1000 random instances (blue circles). For both
measures ($\varepsilon$ and $\sigma$), we identify "hot" and "cold" subsets of
20 instances exhibiting the smallest or largest deviation, respectively
("$\sigma$-hot": red down facing triangles, "$\varepsilon$-hot": tan hexagons,
"$\sigma$-cold": orange diamonds, and "$\varepsilon$-cold": olive plus
symbols). The yellow circles represent the 20 randomly chosen instances
considered in Fig. 1.

To clarify the behaviour for different problem instances, we generate a larger
set consisting of 1000 random portfolio instances, each consisting of $N=10$
assets. Then, we analyze the distance between the solutions $\bf x^{*}$ and
$\bf x^{\rm opt}$ of the relaxed and the binary problem in order to identify
samples of "hot" and "cold" instances where, respectively, the starting point
of warm-start QAOA is close (or not close) to the optimal solution of the
binary problem.

To quantify the distance, we compare the two vectors $\bf x^{*}$ and $\bf
x^{\rm opt}$ and determine the maximum deviation per instance, denoted with
$\varepsilon$:

$\varepsilon=\underset{i}{\text{max}}|x_{i}^{*}-x_{i}^{\text{opt}}|.$ (10)

A large deviation refers to what we call a "cold" instance, whereas for a
small deviation the instances are called "hot".

Figure 3: (a,b) Same as Fig. 1, but additionally for $\sigma$-hot and
$\sigma$-cold problem instances. (c,d) Same as Fig. 1, but additionally for
$\varepsilon$-hot and $\varepsilon$-cold problem instances. For both measures
($\sigma$ and $\varepsilon$), the warm-start performance is either reduced or
improved by choosing cold or hot instances. In particular, hot instances
exhibit significantly higher values of the ground state probability. The
advantage of warm-start QAOA compared to standard QAOA, however, still holds
for cold instances. In contrast, the performance of standard QAOA is not
sensitive to differentiating between cold or hot instances.

In addition to the maximum deviation $\varepsilon$, we also consider the root
mean square error (RMSE)

$\sigma=\sqrt{\sum_{i}\left(x_{i}^{*}-x_{i}^{\rm opt}\right)^{2}/N}$ (11)

as a second measure, which takes into account the differences between all
pairs of values (not only the maximum). For both measures, we identify, from
our ensemble of 1000 random instances, subsets of 20 instances exhibiting the
smallest ("hot") or largest ("cold") deviation, respectively, see Fig. 2.

In Fig. 3 the approximation ratios as well as the ground state probabilities
of the "hot" and "cold" instances for both QAOA variants are shown as a
function of the iteration depth $p$. For comparison, the values of the
randomly chosen instances, which are already displayed in Fig. 1(a), are also
shown. It is noticeable that, for the standard version, differentiating
between the two subsets does not make a difference to the result, neither for
the approximation ratio nor for the probability, i.e. all deviations are
within the error bars, see Fig. 3(a)-(d). With respect to the warm-start, we
see a clear improvement in performance in terms of the approximation ratio
when using the "hot" instances (Fig. 3(a,c)). For the ground state
probabilities, the increase is even significantly higher (Fig. 3(b,d)).
However, the improved performance of warm-start QAOA as compared to standard
QAOA is not restricted to hot instances, but still holds for clod instances.

##  4 Standard QAOA with Classical Preprocessing

Above, we have seen that warm-start QAOA displays a better performance (both,
in terms of approximation ratio and ground state probability) than standard
QAOA - especially (but not only) for those problem instances where the
classically obtained relaxed solution is close to the optimal solution. In
this chapter, we will show that a similar increase of performance can be
obtained by a purely classical preprocessing of the original optimization
problem, which can then be solved with standard QAOA.

####  4.0.1 Elimination of Variables

The solution of the relaxed problem frequently exhibits some bits, which are
already exactly set to 0 and 1 (i.e., $x_{i}^{*}=0$ or $x_{i}^{*}=1$). Since,
as already mentioned above, their value is not changed by the warm-start QAOA
algorithm, one can as well eliminate those bits from the original problem and
run warm-start QAOA on a reduced set of qubits without changing its
performance.

We will follow this idea and extend this procedure also to those bits where
the relaxed solution $x_{i}^{*}$ is not necessarily exactly 0 or 1, but close
to it. For this purpose, we introduce two bounds $\delta_{0}$ and $\delta_{1}$
and round the relaxed solution as follows:

Algorithm 1 Rounding Scheme

if $x_{i}^{*}\leq\delta_{0}$ then

$x_{i}=0$

else if $x_{i}^{*}\geq 1-\delta_{1}$ then

$x_{i}=1$

Depending on the choice of $\delta_{0}$ and $\delta_{1}$, a certain subset of
variables $x_{i}$ is thereby fixed to either 0 or 1. We then look at the
reduced problem depending only on those variables that have not been rounded,
which we finally solve using standard QAOA. In the following, we test a set of
different $\delta_{0}$, $\delta_{1}$ \- combinations and evaluate their
performance with increasing iteration depth $p$. As a baseline, we consider in
particular the case $\delta_{0}=\delta_{1}=0.5$ corresponding to a purely
classical naive rounding of all variables.

For our simulations, we use as input our generated ensembles of 20 random
instances, 20 "hot" and 20 "cold" instances classified by the
$\varepsilon$-measure and by the RMSE ($\sigma$-measure) with $N=10$ qubits
and $B=5$ selected assets. With this setup, we compute both the approximation
ratio $r$ and the probability $P$ for an increasing number of QAOA iterations
$p$ (up to $p_{\text{max}}=7$) including the initial state at $p=0$. For the
classical preprocessing, we set various bound settings as follows: two
symmetric bounds ($\delta_{0}=\delta_{1}=0.01$ and
$\delta_{0}=\delta_{1}=0.25$), one asymmetric bound
($\delta_{0}=0.1,\delta_{1}=0.25$), and the classical baseline as described
above ($\delta_{0}=\delta_{1}=0.5)$. For comparison, we again plot the results
of standard QAOA (without preprocessing) and warm-start QAOA as already
displayed above (see Figs. 1 and 3).

####  4.0.2 Results for random instances

Fig. 4 shows the results for the 20 randomly chosen instances already
considered in Fig. 1. For the classical baseline
($\delta_{0}=\delta_{1}=0.5$), we achieve a mean approximation ratio and mean
probability of $r=P=15\%$ ($=\frac{3}{20}$), i.e. 3 out of 20 solutions are in
agreement with the optimal solution after the simple rounding (and hence
$r=P=1$). All other cases, where the optimal solution was not found, violate
the constraint (thus giving rise to $r=P=0$). Since the classical baseline
involves no QAOA optimization, the result does not improve and remains
constant over the iteration depth. For the two lower bounds (dashed black and
beige lines) we achieve an approximation ratio (left) of about $r\approx 80\%$
at $p=7$ and thus an improvement over the standard QAOA. As can be seen from
the initial state, this method provides a better starting point for the
algorithm.

Also concerning the probabilities of obtaining the optimal solution (right), a
slight increase over the standard version is visible, but for these three
settings (standard and the two lower bounds) the probabilities are below our
baseline probability, indicating that the bound settings are not large enough
to round the values up or down towards the optimal bits. For a large bound
setting (dashed green line) we can reproduce the approximation ratio of the
warm-start variant of $r\approx 92\%$ at depth $p=7$ within the error bars,
and even surpass it at lower depth. Only the probability of the warm-start is
not achievable for the random problem instances. However, compared to the
standard QAOA, a significant increase is accomplished. In summary, standard
QAOA with preprocessing yields higher approximation ratios than warm-start
QAOA, but lower ground state probabilities, indicating that alternative
solutions are found that are very close to the optimal solution.

Figure 4: Mean approximation ratio (a) and ground state probability (b)
obtained with the standard QAOA (teal line), the preprocessed standard QAOA
using different bounds (dashed colored lines) and the warm-start QAOA (pink
line), for 20 random problem instances with classical baseline (dashed
horizontal line). For a bound setting of $\delta_{0}=\delta_{1}=0.25$, the
improved approximation ratio (a) of warm-start QAOA can be reproduced (or even
outperformed at smaller $p$) by the preprocessed standard version. An increase
in probability (right) over the standard QAOA is achieved, although not as
high as with the warm-start.  Figure 5: Same as in Fig. 4, but for
$\varepsilon$-cold (a,b) and $\sigma$-cold (c,d) instead of random problem
instances. Again, for a large bound setting ($\delta_{0}=\delta_{1}=0.25$),
the approximation ratio of the warm-start QAOA can be reproduced by the
preprocessed standard version for both measures (a,c). However, the ground
state probabilities are lower than those obtained with warm-start QAOA (b,d).
For a different bound setting ($\delta_{0}=0.1,\delta_{1}=0.25$) a higher
probability than for the warm-start QAOA can be achieved, but only using
instances created with respect to the $\varepsilon$-measure, see (b).

Figure 6: Same as in Figs. 4 and 5 for $\varepsilon$-hot (a,b) and
$\sigma$-hot (c,d) problem instances. As for the cold instances, the
preprocessed QAOA with largest bound setting ($\delta_{0}=\delta_{1}=0.25$,
dashed green line) shows the highest approximation ratio (a,c). In particular,
it surpasses warm-start (solid pink line) especially at smaller $p$. In case
of the $\sigma$-hot instances, it also displays the largest ground-state
probability, see (d).

####  4.0.3 Results for cold instances

Fig. 5 shows the performance for the same settings as for the random problem
instances, but computed for the "cold" instances classified by the
$\varepsilon$\- and $\sigma$-measures respectively. From the baselines, we see
that the optimal solution is never reached by simple rounding of the relaxed
solution (since all cold instances exhibit $\varepsilon>0.5$, see Fig. 2) and
the budget constraint is never met. Besides that, the performance of warm-
start can be reproduced (approximation ratio of $r_{\varepsilon}\approx 89\%$
compared to $r_{\varepsilon,\text{WS}}\approx 92\%$ and of $r_{\sigma}\approx
83\%$ compared to $r_{\sigma,\text{WS}}\approx 86\%$ at $p=7$) for both
measures in the case of the larger symmetric bound, see the dashed green line
in Fig. 5(a) and (c). For the $\varepsilon$-measure, see Fig. 5(a), it is also
achieved with the asymmetric bound (dashed beige line) which, in addition,
yields the highest ground state probability, see Fig. 5(b). In contrast, for
the $\sigma$-measure, the approximation ratios of the lower symmetric and
asymmetric bounds, see the dashed beige and black lines in Fig. 5(c), coincide
within the error bars. Furthermore, the probabilities of finding the optimal
solution are below warm-start for all cases, see Fig. 5(c).

Note that, in Fig. 5 (b), we observe extremely large error bars especially in
case of the classically preprocessed standard QAOA with bound
$\delta_{0}=\delta_{1}=0.25$. This is due to the fact that, for most of the 20
$\varepsilon$-cold instances, the ground state probability strictly vanishes,
since at least one bit is rounded to the wrong value during the preprocessing.
For $\delta_{0}=\delta_{1}=0.25$, this occurs if $\varepsilon>0.75$, which, as
evident from Fig. 2, concerns 16 out of the 20 $\varepsilon$-cold instances.
In other words, the mean probability originates from only a few instances with
$P>0$, which leads to a large standard deviation.

####  4.0.4 Results for hot instances

In Fig. 6, we now discuss the results for the "hot" problem instances. For
these instances, the deviation between the relaxed and the discrete solution
is small, so after simply rounding, the optimal solution is expected to be
found in most cases. Concerning the $\varepsilon$-measure, see Fig. 6(a,b),
the approximation ratio and probability for the simple rounding (baseline) are
both at $r=P=100\%$, reflecting exactly what has just been described. For the
other measure ($\sigma$), depicted in Fig. 6(d,c), the baseline takes an
approximation ratio and probability of $r=P=85\%$ ($=\frac{17}{20}$), since 3
out of the 20 $\sigma$-hot instances exhibit $\varepsilon>0.5$, see Fig. 2,
and violate the constraint after naive rounding.

For the symmetric bound setting with the largest rounding (dashed green line),
we obtain a maximum approximation ratio of $r_{\varepsilon}\approx 96,7\%$ and
a probability of $P_{\varepsilon}\approx 60\%$ (compared to
$r_{\varepsilon,\text{WS}}\approx 96,9\%$ and
$P_{\varepsilon,\text{WS}}\approx 77\%$) for the $\varepsilon$-measure, see
Fig. 6(a,b), and an approximation ratio of $r_{\sigma}\approx 98\%$ and a
probability of $P_{\sigma}\approx 86\%$ (compared to
$r_{\sigma,\text{WS}}\approx 96\%$ and $P_{\sigma,\text{WS}}\approx 83\%$) for
the $\sigma$-measure, see Fig. 6(c,d). With this result, we conclude that, for
sufficiently large bound settings, the improved performance of the warm-start
QAOA can be reproduced and even be surpassed by standard QAOA with classical
preprocessing.

##  5 Conclusion and Outlook

We presented a classical preprocessing approach to warm-start optimization on
different problem instances. For this purpose, we applied the standard and the
warm-start version of the QAOA algorithm to the portfolio optimization problem
using an ensemble of 20 random, "hot", and "cold" instances with $N=10$
assets, where the two latter ones are created by comparing the relaxed and
discrete solution of 1000 random instances in terms of the maximum deviation
per instance $\varepsilon$ and the root mean square error $\sigma$.

Concerning the performance of the standard QAOA, we have found that dividing
into the two subsets does not show an improved or worse performance compared
to using the random instances. In contrast, for the warm-start QAOA, we
clearly see that the "hot" instances are better to optimize than the "cold"
instances, although an advantage as compared to standard QAOA still holds for
the latter ones.

We introduced a classical preprocessing approach to warm-start optimization by
first using a rounding scheme on the relaxed solution of the continuous
problem for values close to 0 or 1 and then solving the reduced problem with
standard QAOA. As a result, the performance of the standard QAOA, in terms of
the approximation ratio, can be boosted by applying this classical
preprocessing and, especially for smaller $p$, it also outperforms the results
of warm-start QAOA if the bounds for the rounding process are large enough.
For the ground state probability, we observe an increase compared to the
values generated by the standard QAOA, but, in general, we find them to be
lower than those of warm-start QAOA.

Finally, we conclude that the improved performance of warm-start can be
reproduced by classical methods and is thus not a result of quantum effects
alone. In future work, this insight could be useful in order to explore
further ways of splitting an optimization routine into classical and quantum
processing parts and thereby to realize a quantum advantage over purely
classical methods. A better understanding of which steps in the optimization
routine can be replaced classically will be helpful to achieve a better
performance through more targeted use of quantum computing.

##  6 Aknowledgement

This work is funded by the Ministry of Economic Affairs, Labour and Tourism
Baden Württemberg in the frame of the Competence Center Quantum Computing
Baden-Württemberg (project ‘QORA II’).

##  Appendix A Portfolio data

In the tables 1 and 2, the return vector and covariance matrix are given as an
example for one of the random portfolio instances used in section 3. Other
instances can be generated as described in [19] (supplementary material).

FRE.DE | DTE.DE | IFX.DE | SIE.DE | ALV.DE | BAS.DE | HEN3.DE | LIN.DE | RWE.DE | MUV2.DE
---|---|---|---|---|---|---|---|---|---
-0.07998594 | 0.0444345 | 0.20639829 | 0.10283742 | 0.1030686 | 0.05094806 | 0.00832845 | 0.26801758 | 0.30300314 | 0.1128935

Table 1: Return vector $\mu_{i}$ for 10 assets chosen from the German DAX 30

| FRE.DE | DTE.DE | IFX.DE | SIE.DE | ALV.DE | BAS.DE | HEN3.DE | LIN.DE | RWE.DE | MUV2.DE
---|---|---|---|---|---|---|---|---|---|---
|  |  |  |  |  |  |  |  |  |
FRE.DE  | 0.0887543 | 0.02804199 | 0.05163708 | 0.0414294 | 0.04357646 | 0.04001491 | 0.02689946 | 0.02367172 | 0.03149689 | 0.03734508
DTE.DE  | 0.02804199 | 0.03999579 | 0.03292228 | 0.02906106 | 0.03254393 | 0.02991219 | 0.02124013 | 0.01764212 | 0.02967336 | 0.03081729
IFX.DE  | 0.05163708 | 0.03292228 | 0.13060002 | 0.05737477 | 0.0550938 | 0.05734743 | 0.0311434 | 0.04352947 | 0.04571444 | 0.04903502
SIE.DE  | 0.0414294 | 0.02906106 | 0.05737477 | 0.06472856 | 0.0489978 | 0.05052971 | 0.02730231 | 0.02944869 | 0.03578296 | 0.04289097
ALV.DE  | 0.04357646 | 0.03254393 | 0.0550938 | 0.0489978 | 0.06531374 | 0.0503312 | 0.02770636 | 0.02860439 | 0.03487315 | 0.05488462
BAS.DE  | 0.04001491 | 0.02991219 | 0.05734743 | 0.05052971 | 0.0503312 | 0.06984039 | 0.02911981 | 0.02908292 | 0.03458258 | 0.04606973
HEN3.DE  | 0.02689946 | 0.02124013 | 0.0311434 | 0.02730231 | 0.02770636 | 0.02911981 | 0.04272304 | 0.01806647 | 0.02791279 | 0.02735153
LIN.DE  | 0.02367172 | 0.01764212 | 0.04352947 | 0.02944869 | 0.02860439 | 0.02908292 | 0.01806647 | 0.21117209 | 0.02104146 | 0.02922818
RWE.DE  | 0.03149689 | 0.02967336 | 0.04571444 | 0.03578296 | 0.03487315 | 0.03458258 | 0.02791279 | 0.02104146 | 0.11322095 | 0.03446745
MUV2.DE  | 0.03734508 | 0.03081729 | 0.04903502 | 0.04289097 | 0.05488462 | 0.04606973 | 0.02735153 | 0.02922818 | 0.03446745 | 0.06765634

Table 2:  Covariance matrix $\sigma_{ij}$ for 10 assets chosen from the German
DAX 30

## References

  * [1] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann.  “A quantum approximate optimization algorithm” (2014).  arXiv:1411.4028.
  * [2] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Leo Zhou.  “The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size”.  Quantum 6, 759 (2022).
  * [3] Camille Grange, Michael Poss, and Eric Bourreau.  “An introduction to variational quantum algorithms on gate-based quantum computing for combinatorial optimization problems” (2022).  arXiv:2212.11734.
  * [4] Jonathan Wei Zhong Lau, Kian Hwee Lim, Harshank Shrotriya, and Leong Chuan Kwek.  “Nisq computing: where are we and where do we go?”.  AAPPS Bulletin 32, 27 (2022).
  * [5] Daniel J. Egger, Jakub Mareček, and Stefan Woerner.  “Warm-starting quantum optimization”.  Quantum 5, 479 (2021).
  * [6] Eunok Bae and Soojoon Lee.  “Recursive qaoa outperforms the original qaoa for the max-cut problem on complete graphs” (2023).  arXiv:2211.15832.
  * [7] Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang.  “Obstacles to variational quantum optimization from symmetry protection”.  Physical Review Letters125 (2020).
  * [8] Jonathan Wurtz and Peter Love.  “Classically optimal quantum algorithms”.  IEEE Transactions on Quantum Engineering PP, 1–1 (2021).
  * [9] Ioannis Kolotouros and Petros Wallden.  “Evolving objective function for improved variational quantum optimization”.  Phys. Rev. Res. 4, 023225 (2022).
  * [10] Matthias Poloczek, Jialei Wang, and Peter I. Frazier.  “Warm starting bayesian optimization” (2016).  arXiv:1608.03585.
  * [11] Reuben Tate, Majid Farhadi, Creston Herold, Greg Mohler, and Swati Gupta.  “Bridging classical and quantum with sdp initialized warm-starts for qaoa” (2022).  arXiv:2010.14021.
  * [12] Michel X. Goemans and David P. Williamson.  “Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming”.  J. ACM 42, 1115–1145 (1995).
  * [13] Reuben Tate, Jai Moondra, Bryan Gard, Greg Mohler, and Swati Gupta.  “Warm-started qaoa with custom mixers provably converges and computationally beats goemans-williamson’s max-cut at low circuit depths” (2022).  arXiv:2112.11354.
  * [14] Daniel Beaulieu and Anh Pham.  “Max-cut clustering utilizing warm-start qaoa and ibm runtime” (2021).  arXiv:2108.13464.
  * [15] Felix Truger, Martin Beisel, Johanna Barzen, Frank Leymann, and Vladimir Yussupov.  “Selection and optimization of hyperparameters in warm-started quantum optimization for the maxcut problem”.  Electronics11 (2022).
  * [16] Guoming Wang.  “Classically-boosted quantum optimization algorithm” (2022).  arXiv:2203.13936.
  * [17] Manuela Weigold, Johanna Barzen, Frank Leymann, and Daniel Vietz.  “Patterns for Hybrid Quantum Algorithms”.  In Proceedings of the 15th Symposium and Summer School on Service-Oriented Computing (SummerSOC 2021).  Pages 34–51.  Springer International Publishing (2021).
  * [18] Jarrod R. McClean, Matthew P. Harrigan, Masoud Mohseni, Nicholas C. Rubin, Zhang Jiang, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven.  “Low-depth mechanisms for quantum optimization”.  PRX Quantum 2, 030312 (2021).
  * [19] Sebastian Brandhofer, Daniel Braun, Vanessa Dehn, Gerhard Hellstern, Matthias Hüls, Yanjun Ji, Ilia Polian, Amandeep Singh Bhatia, and Thomas Wellens.  “Benchmarking the performance of portfolio optimization with qaoa”.  Quantum Information Processing 22, 25 (2022).
  * [20] Stefan H. Sack and Maksym Serbyn.  “Quantum annealing initialization of the quantum approximate optimization algorithm”.  Quantum 5, 491 (2021).
  * [21] Keith R. Fratus, Kirsten Bark, Nicolas Vogt, Juha Leppäkangas, Sebastian Zanker, Michael Marthaler, and Jan-Michael Reiner.  “Describing trotterized time evolutions on noisy quantum computers via static effective lindbladians” (2022).  arXiv:2210.11371.
  * [22] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D. Lukin.  “Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices”.  Phys. Rev. X 10, 021067 (2020).
  * [23] Alain Billionnet and Sourour Elloumi.  “Using a mixed integer quadratic programming solver for the unconstrained quadratic 0-1 problem”.  Mathematical Programming volume 109, 55 (2007).