# Classification with Quantum Measurements

Fabio A. González<EMAIL_ADDRESS>MindLab Research Group,
Departamento de Ingeniería de Sistemas e Industrial
Universidad Nacional de Colombia, Bogotá, Colombia  Vladimir Vargas-Calderón
Herbert Vinck-Posada  Grupo de Superconductividad y Nanotecnología,
Departamento de Física
Universidad Nacional de Colombia, Bogotá, Colombia

###### Abstract

This paper reports a novel method for supervised machine learning based on the
mathematical formalism that supports quantum mechanics. The method uses
projective quantum measurement as a way of building a prediction function.
Specifically, the relationship between input and output variables is
represented as the state of a bipartite quantum system. The state is estimated
from training samples through an averaging process that produces a density
matrix. Prediction of the label for a new sample is made by performing a
projective measurement on the bipartite system with an operator, prepared from
the new input sample, and applying a partial trace to obtain the state of the
subsystem representing the output. The method can be seen as a generalization
of Bayesian inference classification and as a type of kernel-based learning
method. One remarkable characteristic of the method is that it does not
require learning any parameters through optimization. We illustrate the method
with different 2-D classification benchmark problems and different quantum
information encodings.

quantum computing, quantum machine learning

##  I Introduction

In recent years, the interest in the combination of quantum information
processing and machine learning has been growing fueled by the increasing
popularity and advances in both fields Biamonte  _et al._ (2017). The field
product of the intersection of these research areas is commonly denoted as
quantum machine learning Schuld  _et al._ (2015a). The new field has produced
a considerable amount of research work that explores different interactions
between the two areas Perdomo-Ortiz  _et al._ (2018).

The different approaches to quantum machine learning can be broadly classified
into four categories depending on whether a classical or quantum system
generates the data and whether the processing device is a classical computer
or a quantum computer Schuld and Petruccione (2018a). In the category of
classical-data/quantum-processing, a large amount of work has been devoted to
the development of quantum versions of different classical machine learning
algorithms with an emphasis on showing an advantage, at least theoretically,
of the quantum version in terms of speedup Schuld and Petruccione (2018a). The
classical-data/classical-processing category refers to the use of tools of
quantum information research to formulate machine learning methods that take
advantage of the quantum conceptual machinery. This category has been less
explored than the former one and is the primary motivation of the work
discussed in this paper.

This paper presents a classification method based on the mathematical
formalism that supports quantum mechanics. The method can be implemented both
as an algorithm for a classical computers and as a hybrid classical/quantum
algorithm. The main idea of the method is to represent the joint probability
of input and output variables, $P(x,y)$, as the state of a bipartite quantum
system. Training corresponds to calculating this state from training samples.
Prediction corresponds to performing a projective measurement with an
operator, prepared from the new input sample to be classified, and
subsequently calculating a partial trace to obtain the state of the output
subsystem.

The representation of $P(x,y)$ as the state of a quantum system, more
specifically as a density matrix, generalizes the classical probabilistic
representation and enriches it with the additional representation capabilities
of the quantum formalism. We show that the method generalizes Bayesian
inference and can also be seen as a type of kernel learning method. Another
remarkable feature of the proposed framework is that training, unlike many
machine learning methods, does not require to optimize a cost function that
depends on parameters. Instead, training is done merely by averaging quantum
states representing training samples.

Different works have addressed the implementation of supervised learning
models based on formalism from quantum mechanics or quantum information
processing. Lloyd  _et al._ (2013) present a quantum algorithm for supervised
cluster assignment based on calculating the minimum distance from a sample to
the centroids representing clusters. Analogous quantum algorithms based on
nearest-neighbor classification have been explored by Wiebe  _et al._ (2015);
Sergioli  _et al._ (2018); Schuld  _et al._ (2017a) among others. Different
quantum versions of classical machine learning algorithms have been studied:
support vector machines (Anguita  _et al._ , 2003; Rebentrost  _et al._ ,
2014; Li  _et al._ , 2015), decision trees (Lu and Braunstein, 2014),
classifier ensembles (Schuld and Petruccione, 2018b), neural networks (Schuld
_et al._ , 2015b, 2014; Wiebe  _et al._ , 2016; Wan  _et al._ , 2017), among
others. Another line of work is the application of methods traditionally used
for modeling quantum systems to supervised machine learning. Tensor networks,
a tool for efficient modeling and simulation of many-body quantum systems, are
the most representative of these methods (Stoudenmire and Schwab, 2016;
Stoudenmire, 2018) and have been applied to different classification problems
including image classification (Klus and Gelß, 2019), language analysis (Zhang
_et al._ , 2019) and probabilistic modeling (Glasser  _et al._ , 2019). With
the exception of nearest-neighbor-based methods, all the other quantum machine
learning methods rely on optimization to learn the parameters of the model.
The method presented in this paper does not make use of optimization since
learning is accomplished by averaging quantum states. The method can be seen
as a form of kernel-based learning, but in contrast with typical kernel
methods and nearest-neighbor learning, there is no need for storing any
individual training sample to be used during prediction.

##  II Quantum Measurement Classification (QMC)

The proposed method is similar in principle to a generative Bayesian inference
approach Ng and Jordan (2002). Generative supervised learning models estimate
the joint probability of inputs and outputs $P(x,y)$ that is used during the
prediction stage to calculate the conditional probability of the output given
a new sample. During training, QMC estimates the joint probability of inputs
and outputs from training samples and represents it as a density matrix,
$\rho_{\text{train}}$, that corresponds to a quantum state of a bipartite
system $S_{\mathcal{XY}}=S_{\mathcal{X}}+S_{\mathcal{Y}}$. $S_{\mathcal{X}}$
is the subsystem representing the inputs with associated Hilbert space
$\mathcal{H}_{\mathcal{X}}$ and the subsystem $S_{\mathcal{Y}}$ represents the
outputs in the Hilbert space $\mathcal{H}_{\mathcal{Y}}$. Consequently, the
representation space of the system $S_{\mathcal{XY}}$ is
$\mathcal{H}_{\mathcal{X}}\otimes\mathcal{H}_{\mathcal{Y}}$. Prediction is
made by performing a quantum measurement over $S_{\mathcal{XY}}$ with an
operator specifically prepared from a new input sample.

Figure 1: Training process: training samples are represented as quantum states
of a bipartite system; states are averaged to calculate the training density
matrix.

Figure 1 shows the training process that consists of two main steps, quantum
feature mapping, and training state estimation:

  1. 1.

Quantum feature mapping. In this step each training sample is mapped to
$\mathcal{H}_{\mathcal{X}}\otimes\mathcal{H}_{\mathcal{Y}}$ using the
following function:

$\displaystyle\begin{aligned}
\psi:{\mathcal{X}}\times{\mathcal{Y}}&\to\mathcal{H}_{\mathcal{X}}\otimes\mathcal{H}_{\mathcal{Y}}\\\
(x,y)&\mapsto\ket{\psi_{\mathcal{X}}(x)}\otimes\ket{\psi_{\mathcal{Y}}(y)},\end{aligned}$
(1)

where $\psi_{\mathcal{X}}:{\mathcal{X}}\rightarrow\mathcal{H}_{\mathcal{X}}$
and $\psi_{\mathcal{Y}}:{\mathcal{Y}}\rightarrow\mathcal{H}_{\mathcal{Y}}$ are
functions that map inputs and outputs, respectively, to the corresponding
quantum Hilbert spaces. As a short-hand notation, every data sample
$(x_{i},y_{i})\in T$ is mapped to the quantum feature space as
$\psi:(x_{i},y_{i})\mapsto\ket{\psi_{i}}:=\ket{\psi_{\mathcal{X}}(x_{i})}\otimes\ket{\psi_{\mathcal{Y}}(y_{i})}$.
Here, $T$ is a set of $n$ training samples.

  2. 2.

Training state estimation. In this step, we calculate a quantum state that
summarizes the training data set. This state is represented by a density
matrix $\rho_{\text{train}}$ There are three alternatives to calculate
$\rho_{\text{train}}$:

     * •

Pure state. In this case the training state corresponds to a superposition of
the states representing training samples. First we calculate the superposition
state $\ket{\psi_{\text{train}}}$ as:

$\ket{\psi_{\text{train}}}=\frac{\sum_{i=1}^{n}\ket{\psi_{i}}}{\norm{\sum_{i=1}^{n}\ket{\psi_{i}}}},$
(2)

and define

$\rho_{\text{train}}=\ket{\psi_{\text{train}}}\bra{\psi_{\text{train}}}.$ (3)

     * •

Mixed state. Here, $\rho_{\text{train}}$ corresponds to a mixture of the
states corresponding to the training samples:

$\rho_{\text{train}}=\frac{1}{n}\sum_{i=1}^{n}\ket{\psi_{i}}\bra{\psi_{i}}.$
(4)

     * •

Classical mixture. In this case we extract the probabilities associated with
the quantum state $\ket{\psi_{i}}$ and use them to build a quantum state,
represented by a density matrix, that only has classical uncertainty:

$\rho_{\text{train}}=\frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{m}\absolutevalue{\innerproduct{\psi_{i}}{j}}^{2}\ket{j}\bra{j},$
(5)

where $m$ is the dimension of
$\mathcal{H}_{\mathcal{X}}\otimes\mathcal{H}_{\mathcal{Y}}$ and $\ket{j}$ are
the elements of the canonical basis.

The three alternatives to calculate the training state in step 2 correspond to
three different ways of combining quantum and classical uncertainty in a
quantum state Jacobs (2014). The pure state (eq. 3) encodes the training data
set using only quantum uncertainty, the classical mixture (eq. 5) encodes the
training samples using classical probabilities exclusively, and the mixed
state (eq. 4) uses a combination of quantum and classical uncertainty to
encode the training samples in the training quantum state.

Figure 2: Prediction process: a new sample is represented as a quantum state;
a projective measure operator is built from the input quantum state; the
operator is applied to the training density matrix, a partial trace is used to
calculate a density matrix of the $y$ subsystem, which represent the
prediction.

The prediction process is depicted in fig. 2. The process receives as input a
new sample $x^{\star}$ to be classified, and the training state
$\rho_{\text{train}}$ from the training phase. The steps of the prediction
process are described next.

  1. 1.

Quantum feature mapping. $x^{\star}$ is mapped to
$\ket{\psi_{\mathcal{X}}(x^{\star})}$.

  2. 2.

Prediction operator. An operator acting on
$\mathcal{H}_{\mathcal{X}}\otimes\mathcal{H}_{\mathcal{Y}}$ is defined as
follows:

$\pi(x^{\star})=\ket{\psi_{\mathcal{X}}(x^{\star})}\bra{\psi_{\mathcal{X}}(x^{\star})}\otimes\text{Id}_{\mathcal{H}_{\mathcal{Y}}},$
(6)

where $\text{Id}_{\mathcal{H}_{\mathcal{Y}}}$ is the identity operator on
$\mathcal{H}_{\mathcal{Y}}$.

  3. 3.

Quantum measurement. The operator $\pi(x^{\star})$ is applied to
$\rho_{\text{train}}$:

$\rho^{\prime}=\frac{\pi(x^{\star})\rho_{\text{train}}\pi(x^{\star})}{\Tr[\pi(x^{\star})\rho_{\text{train}}\pi(x^{\star})]}$
(7)

  4. 4.

Partial trace. The partial trace of $\rho^{\prime}$ with respect to subsystem
$S_{\mathcal{X}}$ is calculated. It corresponds to the reduced state of
$\rho^{\prime}$ on subsystem $S_{\mathcal{Y}}$:

$\rho^{\prime}_{{\mathcal{Y}}}=\Tr_{\mathcal{X}}[\rho^{\prime}]$ (8)

The density matrix $\rho^{\prime}_{{\mathcal{Y}}}$ contains information about
the state of the subsystem $S_{\mathcal{Y}}$ after the state of the subsystem
$S_{\mathcal{X}}$ is projected onto the state
$\ket{\psi_{\mathcal{X}}(x^{\star})}$. This density matrix gives information
about the probability of predictions. For instance if
${\mathcal{Y}}=\\{y_{k}\\}_{k=1\dots m}$ and $\psi_{\mathcal{Y}}$ corresponds
to a one-hot or a probability encoding (see Subsection III.2), the diagonal
element $\rho^{\prime}_{{\mathcal{Y}}i,i}$ can be interpreted as the
probability of the value $y_{i}$, i.e., the probability that $x^{\star}$ is
labeled as $y_{i}$.

QMC not only resembles generative Bayesian inference, but it also generalizes
it. The following proposition formally states this claim.

######  Proposition 1.

Let $T=\\{(x_{i},y_{i})\\}_{i=1,\dots,n}$ be a set of training samples,
$x^{\star}$ a sample to classify, with $x_{i},x^{\star}\in\\{1,\dots m\\}$ and
$y_{i}\in\\{1,2\\}$. Let $\rho_{\text{train}}$ be the state calculated using
the mixed state, eq. 4 or equivalently the classical mixture eq. 5, and a one-
hot encoding feature map for both $x_{i}$ and $y_{i}$. Then the diagonal
elements of the density matrix $\rho^{\prime}_{{\mathcal{Y}}}$ calculated
using eq. 8 correspond to an estimation, using Bayesian inference, of the
conditional probabilities $P(y=i|x^{\star})$:

$\rho^{\prime}_{{\mathcal{Y}}i,i}=P(y=i|x^{\star})=\frac{P(x^{\star}|y=i)P(y=i)}{P(x^{\star})},$
(9)

where $P(x^{\star}|y=i)$, $P(y=i)$ and $P(x^{\star})$ are estimated from $T$.

###### Proof.

Since both $x_{i}$ and $y_{i}$ are represented using a one-hot encoding
representation, then

$\displaystyle\ket{\psi_{i}}=\ket{x_{i}}\otimes\ket{y_{i}}=\ket{x_{i}y_{i}}.$
(10)

Applying eq. 4:

$\displaystyle\begin{aligned}
\rho_{\text{train}}={}&\frac{1}{n}\sum_{i=1}^{n}\ket{x_{i}y_{i}}\bra{x_{i}y_{i}}\\\
{}={}&\sum_{j=1}^{m}\sum_{k=1}^{2}P(x=j,y=k)\ket{jk}\bra{jk},\end{aligned}$
(11)

with $P(x=j,y=k)=\frac{1}{n}\sum_{i=1}^{n}\delta_{x_{i}j}\delta_{y_{i}k}$.
Applying the prediction operator (eq. 6)

$\displaystyle\pi(x^{\star})=\ket{x^{\star}}\bra{x^{\star}}\otimes\text{Id}_{H_{\mathcal{Y}}}$
(12)

to eq. 11 produces

$\displaystyle\begin{aligned}
\rho^{\prime}&=\frac{\sum_{k=1}^{2}P(x=x^{\star},y=k)\ket{x^{\star}k}\bra{x^{\star}k}}{\sum_{k=1}^{2}P(x=x^{\star},y=k)}\\\
&=\sum_{k=1}^{2}P(y=k|x=x^{\star})\ket{x^{\star}k}\bra{x^{\star}k}.\end{aligned}$
(13)

Finally, we calculate the partial trace of eq. 13 to obtain:

$\displaystyle\begin{aligned}
\rho^{\prime}_{\mathcal{Y}}&=\text{Tr}_{\mathcal{X}}[\rho^{\prime}]\\\
&=\sum_{k=1}^{2}P(y=k|x=x^{\star})\ket{k}\bra{k}.\end{aligned}$ (14)

∎

Using a one-hot encoding makes the general mixture (eq. 4) equivalent to a
classical mixture (eq. 5). Proposition 1 states that estimating the training
state using a classical mixture is equivalent to do classical Bayesian
inference. This is not surprising since the classical mixture corresponds to a
conventional probabilistic encoding of the information in the training data
set.

When using the more general quantum feature map along with a mixed state (eq.
4) to estimate the training quantum state, the prediction process involves
more complex interactions between states. The following proposition shows
that, in this case, the resulting density matrix
$\rho^{\prime}_{{\mathcal{Y}}}$ for the subsystem $S_{\mathcal{Y}}$
corresponds to a linear combination of the density matrices representing the
output variables of the training samples.

######  Proposition 2.

Let $T=\\{(x_{i},y_{i})\\}_{i=1\dots n}$ be a set of training samples,
$x^{\star}$ a sample to classify, with $x_{i},x^{\star}\in{\mathcal{X}}$ and
$y_{i}\in{\mathcal{Y}}$. Let $\rho_{\text{train}}$ be the state calculated
using a mixed state (eq. 4) and quantum feature maps $\psi_{\mathcal{X}}$ and
$\psi_{\mathcal{Y}}$. Then the density matrix $\rho^{\prime}_{{\mathcal{Y}}}$,
calculated with eq. 8, can be expressed as:

$\rho^{\prime}_{{\mathcal{Y}}}=\mathcal{M}\sum_{i=1}^{n}\absolutevalue{k(x^{\star},x_{i})}^{2}\ket{\psi_{\mathcal{Y}}(y_{i})}\bra{\psi_{\mathcal{Y}}(y_{i})},$
(15)

where
$k(x^{\star},x_{i})=\innerproduct{\psi_{\mathcal{X}}(x^{\star})}{\psi_{\mathcal{X}}(x_{i})}$
and $\mathcal{M}^{-1}=\Tr[\pi(x^{\star})\rho_{\text{train}}\pi(x^{\star})]$ .

###### Proof.

Equation 4 can be expressed as:

$\displaystyle\begin{aligned}
\rho_{\text{train}}&=\frac{1}{n}\sum_{i=1}^{n}\ket{\psi_{i}}\bra{\psi_{i}}\\\
&=\frac{1}{n}\sum_{i=1}^{n}\ket{\psi_{\mathcal{X}}(x_{i})}\bra{\psi_{\mathcal{X}}(x_{i})}\otimes\ket{\psi_{\mathcal{Y}}(y_{i})}\bra{\psi_{\mathcal{Y}}(y_{i})}\\\
&\equiv\frac{1}{n}\sum_{i=1}^{n}\sigma_{\mathcal{X}}(x_{i})\otimes\sigma_{\mathcal{Y}}(y_{i}),\end{aligned}$
(16)

where
$\sigma_{\mathcal{X}}(x_{i})=\ket{\psi_{\mathcal{X}}(x_{i})}\bra{\psi_{\mathcal{X}}(x_{i})}$
and
$\sigma_{\mathcal{Y}}(y_{i})=\ket{\psi_{\mathcal{Y}}(y_{i})}\bra{\psi_{\mathcal{Y}}(y_{i})}$.
Applying eq. 7 to eq. 16 we get:

$\displaystyle\begin{aligned}
\rho^{\prime}&=\mathcal{M}\sum_{i=1}^{n}\sigma_{\mathcal{X}}(x^{\star})\sigma_{\mathcal{X}}(x_{i})\sigma_{\mathcal{X}}(x^{\star})\otimes\sigma_{\mathcal{Y}}(y_{i})\\\
&=\mathcal{M}\sum_{i=1}^{n}\absolutevalue{k(x^{\star},x_{i})}^{2}\sigma_{\mathcal{X}}(x^{\star})\otimes\sigma_{\mathcal{Y}}(y_{i}),\end{aligned}$
(17)

where
$k(x^{\star},x_{i})=\innerproduct{\psi_{\mathcal{X}}(x^{\star})}{\psi_{\mathcal{X}}(x_{i})}$
and $\mathcal{M}^{-1}=n\Tr[\pi(x^{\star})\rho_{\text{train}}\pi(x^{\star})]$.

Finally, we calculate the partial trace of eq. 17 to obtain:

$\displaystyle\begin{aligned}
\rho^{\prime}_{\mathcal{Y}}&=\text{Tr}_{\mathcal{X}}[\rho^{\prime}]\\\
&=\mathcal{M}\sum_{i=1}^{n}k(x^{\star},x_{i})^{2}\sigma_{\mathcal{Y}}(y_{i})\\\
&=\mathcal{M}\sum_{i=1}^{n}k(x^{\star},x_{i})^{2}\ket{\psi_{\mathcal{Y}}(y_{i})}\bra{\psi_{\mathcal{Y}}(y_{i})}\end{aligned}$
(18)

∎

Equation 15 can be seen as type of kernel-based classification function
$f(x)=\sum_{(x_{i},y_{i})\in S}\alpha_{i}k(x,x_{i})y_{i}$, where $k$ is a
kernel function and the $\alpha_{i}$ are learned parameters. In QMC
$\alpha_{i}:=k^{*}(x^{\star},x_{i})$ and $y_{i}$ is replaced by
$\ket{\psi_{\mathcal{Y}}(y_{i})}\bra{\psi_{\mathcal{Y}}(y_{i})}$. Notice that
$k(x^{\star},x_{i})$ corresponds to the dot product in the quantum Hilbert
space $H_{\mathcal{X}}$, so it is in fact a kernel function. This means that
QMC can be seen as type of kernel-based learning method. However an important
difference is that while conventional kernel methods require to learn, usually
through optimization, the $\alpha_{i}$ parameters, in QMC there are not
parameters to be learned. Nevertheless, the method has hyperparameters, mainly
associated to feature maps to be discussed in next section, that has to be
estimated or fixed by the user. This is done through cross validation, the
common practice in machine learning.

It is important to note that it is possible to use eq. 15 to calculate
$\rho^{\prime}_{y}$, however this will require keeping all the training
samples. QMC does not require this as training samples are compactly
represented by the $\rho_{\text{train}}$ density matrix.

It is worth emphasizing that QMC can, in principle, be implemented in quantum
devices through the preparation of a pure training state of the form eq. 2
with well-known preparation protocols (Plesch and Brukner, 2011; Shende  _et
al._ , 2006). With the same protocol, the state of the new data sample
$x^{\star}$ can be built. Finally, the projective measurement can be achieved
via a third ancillary state that allows a SWAP test (Buhrman  _et al._ , 2001;
Garcia-Escartin and Chamorro-Posada, 2013; Cincio  _et al._ , 2018; Park  _et
al._ , 2020), as in other distance-based classifiers (Blank  _et al._ , 2020;
Schuld  _et al._ , 2017b) (with the upside that data need not be radially
separable, as well as keeping the size of the physical system to be
independent from the amount of training data).

Assuming that the dimensions of $\mathcal{H}_{\mathcal{X}}$ and
$\mathcal{H}_{\mathcal{Y}}$ are $k$ and $\ell$ respectively, a straighforward
implementation of QMC training takes time $O(k\ell n)$. This means that
training is linear on the training set size. Storing $\rho_{\text{train}}$
requires space $O((k\ell)^{2})$. For prediction, the most costly process is
calculating eq. 7. A direct implementation will take time $O((k\ell)^{4})$,
however a more careful implementation can perform it in time $O((k\ell)^{3})$.
This can be further reduced by performing a previous eigendecomposition of
$\rho_{\text{train}}$.

##  III Quantum feature maps

In quantum machine learning literature, there are several approaches to
represent data as quantum states. Schuld and Petruccione (2018a) propose
different strategies such as basis encoding, encoding data directly as qubits,
and amplitude encoding, which is encoding data in the amplitude of quantum
states (Schuld  _et al._ , 2017b). Next, we describe several approaches that
we use in the illustrative examples.

###  III.1 Softmax encoding

A common approach to represent real numbers in the interval $[0,1]$ is to use
the mapping $\phi:x\mapsto\sin{(2\pi x)}\ket{0}+\cos{(2\pi x)}\ket{1}$,
encoding the number as a the superposed state of a qubit. We propose a softmax
quantum encoding that extends this approach from two dimensions to multiple
dimensions.

First we define a probability encoding for real values
$P:\mathbb{R}\rightarrow[0,1]^{m}$ where $m$ is the number of states:

$\displaystyle
P_{i}(x)=\left(\frac{\exp{-\beta\|x-\alpha_{i}\|^{2}}}{\sum_{j=1}^{m}\exp{-\beta\|x-\alpha_{j}\|^{2}}}\right)_{i=1\dots
m},$ (19)

where $\alpha_{i}=\frac{i-1}{m-1}$. Using these probabilities we build a
quantum state representing a real number

$\displaystyle\ket{\varphi(x)}=\sum_{j=1}^{m}\sqrt{P_{i}(x)}\ket{j}.$ (20)

The quantum state corresponding to a vector $x_{i}\in\mathbb{R}^{n}$ is
defined as

$\displaystyle\ket{\psi_{\mathcal{X}}(x_{i})}=\ket{\varphi(x_{i,1})}\otimes\dots\otimes\ket{\varphi(x_{i,n})}.$
(21)

###  III.2 One-hot encoding

This representation corresponds to a basis encoding for discrete variables
with $m$ possible values, $\mathcal{X}=\\{1,\dots,m\\}$. The encoding for
$x=j$ is given by

$\displaystyle\psi_{\mathcal{X}}(j)=\ket{j}.$ (22)

###  III.3 Squeezed states

Recently, Schuld and Killoran (2019) proposed to encode data to the phase of a
light squeezed state

$\displaystyle\ket{(r,\varphi)}=\frac{1}{\sqrt{\cosh(r)}}\sum_{n=0}^{\infty}\frac{\sqrt{(2n)!}}{2^{n}n!}(e^{i(\varphi+\pi)}\tanh(r))^{n}\ket{2n},$
(23)

so that a vector $x_{i}\in[0,\pi]^{n}$ is mapped to
$\psi_{\mathcal{X}}(c,x_{i})=\ket{(c,x_{i,1})}\otimes\ldots\otimes\ket{(c,x_{i,n})}$.

###  III.4 Coherent states

Data can also be encoded into the average number of photons of a canonical
coherent state Chatterjee and Yu (2017):

$\displaystyle\ket{(\alpha,\gamma)}=e^{-\frac{\gamma|\alpha|^{2}}{2}}\sum_{n=0}^{\infty}\frac{\alpha^{n}\gamma^{n/2}}{\sqrt{n!}}\ket{n}$
(24)

where a scaling characterized by $\gamma$ has been introduced so that the dot
product of the two states corresponds to a Gaussian kernel with $\gamma$
parameter. The mapping from a real data sample $x_{j}\in\mathbb{R}^{n}$ to the
complex $\alpha$ is done as follows. An auxiliary variable $\theta_{j}$ is
built through a min-max scaling of the data set to $[0,\pi]^{n}$, so that
$x_{j,\ell}\mapsto x_{j,\ell}e^{i\theta_{j,\ell}}$. Therefore, a data point
$x_{j}$ is mapped to the quantum feature space through

$\displaystyle\psi_{\mathcal{X}}(x_{j},\gamma)=\ket{(x_{j,1}e^{i\theta_{j,1}},\gamma)}\otimes\ldots\otimes\ket{(x_{j,n}e^{i\theta_{j,n}},\gamma)}$
(25)

which induces a kernel

$\displaystyle\absolutevalue{k_{\gamma}(x_{k},x_{j})}^{2}=\prod_{\ell=1}^{n}\exp(-\gamma|x_{k,\ell}e^{i\theta_{k,\ell}}-x_{j,\ell}e^{i\theta_{j,\ell}}|^{2}),$
(26)

where the argument of the exponential is explicitly
$-\gamma(x_{k,\ell}^{2}+x_{j,\ell}^{2}-2x_{k,\ell}x_{j,\ell}\cos(\theta_{k,\ell}-\theta_{j,\ell}))$,
which imposes a higher distance penalty in the feature space for distant data
points in the original space $\mathbb{R}^{n}$ than the usual Gaussian kernel.

###  III.5 Random Fourier Features

As in quantum state representations, the feature space of kernel methods is a
Hilbert space. This means that a quantum feature map implicitly defines a
kernel. A natural question is whether the opposite conversion also works,
i.e., given a particular kernel function, can we find a quantum feature map
such that the inner product of the corresponding Hilbert space corresponds to
the kernel. In general, the answer is no; however, it is possible to find an
approximation for certain kernels. Random Fourier features (RFF) Rahimi and
Recht (2008) provides a technique that finds an explicit Hilbert space such
that the inner product in this space approximates a shift-invariant kernel.
Specifically, for a given kernel
$k:\mathbb{R}^{d}\times\mathbb{R}^{d}\rightarrow\mathbb{R}$, RFF finds a map
$z:\mathbb{R}^{d}\rightarrow\mathbb{R}^{D}$ such that $k(x,y)\approx
z^{\prime}(x)z(y)$.

The quantum state corresponding to a vector $x_{i}\in\mathbb{R}^{d}$ is
defined as

$\displaystyle\ket{\psi_{\mathcal{X}}(x_{i})}=\frac{1}{||z(x_{i})||}\sum_{j=1}^{D}z_{j}(x_{i})\ket{j}.$
(27)

##  IV Method illustration

Figure 3: Decision heatmap for a two-moons dataset of the softmax, coherent,
squeezed, and random Fourier features states-based feature maps truncated at
20 Fock states. The regularization parameters were $\beta=70$ for the softmax
state, $\gamma=70$ for the coherent state, $r=2.5$ for the squeezed state, and
$\gamma=20$ for the random Fourier features state. In all four cases, a mixed
training state was used. The white boxes show the train/test accuracy of the
classifier. The values of the parameters were tuned using cross-validation.

In this section, we illustrate the performance of QMC with binary
classification toy problems for the different aforementioned feature maps.
Figure 3 compares the decision boundary obtained from a mixed training state
through the different feature maps, where the states are truncated up to the
first 20 Fock states for each input feature. The color tells the probability
that the output state belongs to the red or blue classes. For all the cases,
the method achieves high discrimination in both classes: 94%, 98%, 96% and 97%
accuracy in the test set for the softmax, coherent, squeezed and RFF
encodings, respectively.

Figure 4: Classification accuracy as a function of the regularization
parameter $\gamma$ on a spirals dataset for mixed, pure and classical training
states built with the coherent state encoding truncated at 32 Fock states.
Decision heatmaps are shown for the three training schemes at $\gamma=70$. The
white boxes are as in fig. 3.

Equations 3, 4 and 5 correspond to three different alternatives to estimate
the training state. The mixed and pure alternatives are expected to take
advantage of the quantum correlations induced by the feature mapping and
exploited in the projective measurement process. Figure 4 shows that this is,
in fact, the case for the 2D spirals dataset. The three plots show prediction
regions for the three different estimation strategies using the coherent state
quantum feature mapping truncated to the first 32 Fock states. The mixed state
representation has the best performance (98% accuracy in the test set),
followed closely by the pure state representation (83% accuracy in the test
set). Both are able to capture the particular shape of both classes. The
classical state representation fails to do good discrimination. This is better
observed on the top-left plot where the classification precision is measured
for a range of $\gamma$ values111The values of $\gamma$, $r$ and $\beta$ have
a similar effect on classification accuracy: the larger the value, the larger
the discrimination. This means that regions are assigned large probabilities
of belonging to one class or the other. This property is good for separable
data, but can lead to overfitting for non-separable data., showing that the
worst classification scheme is the classical representation state, whereas the
best one is the mixed representation state, closely followed by the pure
representation state. The same behavior is observed when the coherent state is
truncated to the first 20–64 Fock states (not shown).

Regarding the squeezed state encoding, decision boundaries for a circles
dataset for pure and mixed training states are shown in fig. 5. Here, the
mixed training state outperforms the pure training state. The classical
training state is useless because the data is mapped to the phase of the
squeezed state, and the probabilities in eq. 5 do not depend on this phase.
Again, a signature of the kernel induced by the squeezed state is seen in the
regions at the middle top, bottom, right, and left parts of the decision
heatmaps that are wrongly classified. These regions emerge from the fact that
the similarity induced by the squeezed-based kernel between two points at a
fixed Euclidean distance is maximum if the horizontal or vertical components
of the two points are the same.

Figure 5: Decision heatmap for a two-circles dataset of the squeezed state
feature map with pure and mixed training states. Squeezed states were
truncated to the first 10 contributing Fock states, and a value of $r=2.5$ was
used, as in (Schuld and Killoran, 2019). The white boxes are as in fig. 3.

The accuracies obtained by every quantum feature map on each of the discussed
toy-datasets are shown in table 1. The coherent quantum feature map shows
similar results on all datasets, but random features and softmax quantum
feature maps show lower performance in the spirals dataset. Interestingly, the
squeezed state, whose related kernel is anisotropic (Schuld and Killoran,
2019) performs much better in the spirals dataset.

Table 1: Train/test accuracy for every quantum feature map and toy-dataset discussed in this paper for mixed training states. The number of Fock states considered for each dataset was 10 for circles, 20 for moons and 32 for spirals. The specific parameters for each quantum feature map were $r=2.5$ for squeezed states, $\beta=70$ for softmax states, $\gamma=20$ for random feature map states, and $\gamma=70$ for coherent states. QFM | Coherent | RFF | Softmax | Squeezed
---|---|---|---|---
Dataset |  |  |  |
Circles | 0.96/0.94 | 0.88/0.87 | 0.94/0.93 | 0.91/0.89
Moons | 0.96/0.98 | 0.95/0.97 | 0.94/0.94 | 0.95/0.96
Spirals | 0.98/0.98 | 0.82/0.75 | 0.85/0.83 | 1.00/0.99

##  V Conclusions

This paper presented a classification method based on quantum measurement. The
overall strategy of the method is based on two mechanisms: first, to represent
the joint probability of inputs and outputs by the state of a bipartite
quantum system and, second, to predict the outputs of new input samples
performing a quantum measurement.

Using this quantum measurement framework as a basis for function induction
contributes a two-fold novel perspective to supervised quantum machine
learning. On the one hand, the training process does not require optimization
of parameters, since training corresponds to state averaging. This is an
essential departure from current machine learning models, both classical and
quantum-based. On the other hand, the classification model induced by QMC can
be understood as a generalization of Bayesian-inference classification and as
a type of kernel classification model. This connection is a consequence of the
harmonious combination of linear algebra and probability provided by the
quantum framework. Some works connect kernel and probabilistic methods
Jaakkola and Haussler (1999); Muandet  _et al._ (2017); however the quantum
measurement framework constitutes a novel unifying perspective.

The ability of QMC of inducing a classification model without parameter
optimization suggests the possibility of an efficient classical
implementation. This is the case for the training process, whose time
complexity is linear on the number of training samples. However, the
computational burden moves from the training process to the prediction process
and from time complexity to space complexity. In particular the space required
by the training density matrix, $\rho_{\text{train}}$, is
$\mathcal{O}(m^{2}\ell^{2})$ where
$m=\absolutevalue{\mathcal{H}_{\mathcal{X}}}$ and
$\ell=\absolutevalue{\mathcal{H}_{\mathcal{Y}}}$. Scaling QMC to large scale
learning problems requires dealing with this space complexity. A promising
research line to address this problem is to use tensor networks (Stoudenmire
and Schwab, 2016) to build a compact representation of these density matrices
employing tensor factorizations. Another possibility of mitigating the
computational costs is the implementation of QMC as a hybrid classical-quantum
algorithm. Whether this could exploit a quantum advantage is part of our
future research.

## References

  * Biamonte  _et al._ (2017) J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd, Nature 549, 195 (2017).
  * Schuld  _et al._ (2015a) M. Schuld, I. Sinayskiy, and F. Petruccione, Contemporary Physics 56, 172 (2015a).
  * Perdomo-Ortiz  _et al._ (2018) A. Perdomo-Ortiz, M. Benedetti, J. Realpe-Gómez, and R. Biswas, Quantum Science and Technology 3, 030502 (2018).
  * Schuld and Petruccione (2018a) M. Schuld and F. Petruccione,  _Supervised Learning with Quantum Computers_, Quantum Science and Technology (Springer International Publishing, Cham, 2018).
  * Lloyd  _et al._ (2013) S. Lloyd, M. Mohseni, and P. Rebentrost, “Quantum algorithms for supervised and unsupervised machine learning,”  (2013).
  * Wiebe  _et al._ (2015) N. Wiebe, A. Kapoor, and K. M. Svore, Quantum Information and Computation 15, 318 (2015).
  * Sergioli  _et al._ (2018) G. Sergioli, E. Santucci, L. Didaci, J. A. Miszczak, and R. Giuntini, Soft Computing 22, 691 (2018).
  * Schuld  _et al._ (2017a) M. Schuld, M. Fingerhuth, and F. Petruccione, EPL (Europhysics Letters) 119, 60002 (2017a).
  * Anguita  _et al._ (2003) D. Anguita, S. Ridella, F. Rivieccio, and R. Zunino, Neural Networks 16, 763 (2003).
  * Rebentrost  _et al._ (2014) P. Rebentrost, M. Mohseni, and S. Lloyd, Physical Review Letters 113, 130503 (2014).
  * Li  _et al._ (2015) Z. Li, X. Liu, N. Xu, and J. Du, Physical Review Letters 114, 140504 (2015).
  * Lu and Braunstein (2014) S. Lu and S. L. Braunstein, Quantum Information Processing 13, 757 (2014).
  * Schuld and Petruccione (2018b) M. Schuld and F. Petruccione, Scientific Reports 8, 2772 (2018b).
  * Schuld  _et al._ (2015b) M. Schuld, I. Sinayskiy, and F. Petruccione, Physics Letters A 379, 660 (2015b).
  * Schuld  _et al._ (2014) M. Schuld, I. Sinayskiy, and F. Petruccione, Quantum Information Processing 13, 2567 (2014).
  * Wiebe  _et al._ (2016) N. Wiebe, A. Kapoor, and K. M. Svore, in  _Advances in Neural Information Processing Systems_ (2016) pp. 4006–4014.
  * Wan  _et al._ (2017) K. H. Wan, O. Dahlsten, H. Kristjánsson, R. Gardner, and M. S. Kim, npj Quantum Information 3, 36 (2017).
  * Stoudenmire and Schwab (2016) E. M. Stoudenmire and D. J. Schwab, in  _Advances in Neural Information Processing Systems_ (2016) pp. 4806–4814.
  * Stoudenmire (2018) E. M. Stoudenmire, Quantum Science and Technology 3, 034003 (2018).
  * Klus and Gelß (2019) S. Klus and P. Gelß, Algorithms 12, 240 (2019).
  * Zhang  _et al._ (2019) L. Zhang, P. Zhang, X. Ma, S. Gu, Z. Su, and D. Song, in  _Proceedings of the AAAI Conference on Artificial Intelligence_, Vol. 33 (2019) pp. 7450–7458.
  * Glasser  _et al._ (2019) I. Glasser, R. Sweke, N. Pancotti, J. E. A. i. N. …, and U. 2019, in  _Advances in Neural Information Processing Systems_ (2019) pp. 1496–1508.
  * Ng and Jordan (2002) A. Y. Ng and M. I. Jordan, in  _Advances in neural information processing systems_ (2002) pp. 841–848.
  * Jacobs (2014) K. Jacobs,  _Quantum measurement theory and its applications_ (Cambridge University Press, 2014).
  * Plesch and Brukner (2011) M. Plesch and i. c. v. Brukner, Phys. Rev. A 83, 032302 (2011).
  * Shende  _et al._ (2006) V. V. Shende, S. S. Bullock, and I. L. Markov, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 25, 1000 (2006).
  * Buhrman  _et al._ (2001) H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf, Phys. Rev. Lett. 87, 167902 (2001).
  * Garcia-Escartin and Chamorro-Posada (2013) J. C. Garcia-Escartin and P. Chamorro-Posada, Phys. Rev. A 87, 052330 (2013).
  * Cincio  _et al._ (2018) L. Cincio, Y. Subaşı, A. T. Sornborger, and P. J. Coles, New Journal of Physics 20, 113022 (2018).
  * Park  _et al._ (2020) D. K. Park, C. Blank, and F. Petruccione, Physics Letters A , 126422 (2020).
  * Blank  _et al._ (2020) C. Blank, D. K. Park, J.-K. K. Rhee, and F. Petruccione, npj Quantum Information 6, 1 (2020).
  * Schuld  _et al._ (2017b) M. Schuld, M. Fingerhuth, and F. Petruccione, EPL (Europhysics Letters) 119, 60002 (2017b).
  * Schuld and Killoran (2019) M. Schuld and N. Killoran, Physical Review Letters 122 (2019), 10.1103/PhysRevLett.122.040504.
  * Chatterjee and Yu (2017) R. Chatterjee and T. Yu, Quantum Information and Communication 17, 1292 (2017).
  * Rahimi and Recht (2008) A. Rahimi and B. Recht, in  _Advances in neural information processing systems_ (2008) pp. 1177–1184.
  * Note (1) The values of $\gamma$, $r$ and $\beta$ have a similar effect on classification accuracy: the larger the value, the larger the discrimination. This means that regions are assigned large probabilities of belonging to one class or the other. This property is good for separable data, but can lead to overfitting for non-separable data.
  * Jaakkola and Haussler (1999) T. Jaakkola and D. Haussler, in  _Advances in neural information processing systems_ (1999) pp. 487–493.
  * Muandet  _et al._ (2017) K. Muandet, K. Fukumizu, B. Sriperumbudur, B. Schölkopf, _et al._ , Foundations and Trends® in Machine Learning 10, 1 (2017).