# When and how do we use basis embedding?

It is suggested in various sources that a possible approach to representing classical data as a quantum state is simply to take the binary sequence $$x$$ and turn it to $$|x\rangle$$ (i.e., "basis embedding"). However, all of the implementations of quantum machine learning algorithms that I found use more complicated feature maps. Furthermore, according to the popular SVM paper of Havlicek et al, "To obtain an advantage over classical approaches we need to implement a map based on circuits that are hard to simulate classically".

Therefore, my questions are:

1. Since the map that turns $$|0...0\rangle$$ to $$|x\rangle$$ (for $$x\in \{0,1\}^n$$) can be implemented by a Clifford circuit, which can be efficiently simulated classically, does the above quote imply that no quantum advantage will be obtained by using it as our feature map? If not, then where's my mistake?
2. Are there any examples in the literature of quantum machine learning algorithms that actually use basis embeddings?
• please stick to a single question per post; you can open different posts to ask different questions – glS May 11 at 9:56

I'll denote $$x=x_1\dots x_n \in \{0,1\}^n$$ as a vector containing binary values. Certainly you can prepare $$|x\rangle = X^{x_1} \otimes \cdots \otimes X^{x_n} |0\dots 0\rangle$$ easily, and it turns out that a quantum circuit trying to classify $$|x\rangle$$ is also generally classically simulable since its entirely linear in elements of $$x$$. For completeness I'll justify this claim below before answering your questions.

To see this, consider a fairly general model for how one would learn about $$|x\rangle$$ using a quantum computer in a supervised learning setting - so assume that our data is actually datum-label pairs $$\{(|x_i\rangle, y_i)\}$$ for $$i=1\dots m$$.. First, we process $$|x_i\rangle$$ in some way using a parameterized unitary $$U(\theta)$$. Next, we perform a measurement to compute the expectation value of some Hermitian $$W$$. Finally, we use the information in $$\langle W\rangle$$ to make a prediction $$f(x_i)$$ for what $$y_i$$ should be, and then try to minimize the average error in $$f(x_i)$$. In summary, attempt the optimization $$\tag{1} \min_\theta \sum_{i=1}^m \ell(f(x_i), y_i)$$ with $$f$$ being some function of $$\langle W \rangle$$, a popular choice being: $$\tag{2} f(x_i) = \text{sign}(\langle x_i | U(\theta)^\dagger W U(\theta)| x_i \rangle )$$

This process is called "Empirical Risk Minimization" (ERM). Now examine (2) in a slightly different way: Instead of using $$|x_i\rangle$$, lets represent our state as $$|x_i\rangle\langle x_i |$$. This is a choice of representation and doesn't change the power of the classifier in any way. Furthermore, denote $$W(\theta) \equiv U(\theta)^\dagger W U(\theta)$$, which is still Hermitian under the action of a unitary transformation. Now since $$|x_i\rangle\langle x_i |$$ is also $$2^n \times 2^n$$ Hermitian matrix we can now view $$f(x_i)$$ as arising from an inner product$$^1$$ $$\langle \cdot, \cdot \rangle$$ on $$\mathbb{C}^{2^n \times 2^n}$$:

\begin{align}\tag{3} f(x_i) &= \text{sign}(\text{Tr}[| x_i \rangle\langle x_i | W(\theta)] ) \\ &\equiv \text{sign}(\langle W, |x_i\rangle \langle x_i|\rangle) \end{align}

The term $$\langle W, |x_i\rangle \langle x_i|\rangle$$ depends only linearly on the elements of $$x_i$$, and so this classification rule is strictly linear. A classical algorithm could be trained to find the classical vector $$w$$ such that $$\text{sign}(\langle w, x_i\rangle)$$ minimizes Equation (1). Note that $$w$$ will not necessarily be binary.

does the above quote imply that no quantum advantage will be obtained by using it as our feature map?

I don't think this reasoning follows directly from using a Clifford circuit for embedding your data. But I'm sure (Havlicek, 2019) had something like the above linearity argument in mind. The power of your classifier $$f$$ will be limited by your choice of feature map, and since the map $$x \rightarrow |x\rangle$$ is linear in elements of $$x$$ then the result is a fairly weak classifier.

Are there any examples in the literature of quantum machine learning algorithms that actually use basis embeddings?

Sure, here's one: (Arunachalam, 2016). They show that a quantum machine learning algorithm based on this kind of encoding can have only a constant factor of improvement over a classical learner in sample complexity (how many patterns $$x_i$$ you need to observe to "train" your model to be sufficiently accurate) in the PAC$$^2$$ setting. Or roughly speaking, quantum computers can't be made more efficient (in the number of samples needed) at learning about this data than classical computers in a general setting. Combined with the above demonstration that the quantum computers are also no more efficient in computational complexity this is probably enough evidence to discourage people from using this kind of embedding.

$$^1$$ Be careful - while we're dealing with inner products defined with respect to Hermitian matrices, that subspace of complex matrices isn't linear since its generally not closed under multiplication by elements of $$\mathcal{C}$$. e.g. for Hermitian $$H$$, $$iH$$ is generally not Hermitian.

$$^2$$ Probably Approximately Correct learning just means finding a classifier has at least $$1-\delta$$ probability of classifying the data with less than $$\epsilon$$ error, and the associated sample complexity is the number of training points needed for ERM to achieve these conditions. I'm omitting some other strict assumptions usually used in the PAC setting that you can find in standard texts on this subject.