4
$\begingroup$

In a much cited paper by Lloyd et al Quantum Algorithm for Supervised and Unsupervised Machine Learning, they proposed a rather cute quantum algorithm to evaluate the distance between an input feature vector $\vec{u}$ and the centroid of a set of $M$ training vectors $\{\vec{v}_{j}\}$, i.e. an average $(1/M)\sum_{j=1}^{M}\vec{v}_{j}$. On page 3 of this paper, after they have constructed state $|\psi\rangle$ for "system and ancilla", they proceeded to "... use a swap test to perform a projective measurement on the ancilla alone to see if it is in the state $|\phi\rangle$ ...". I have three closely related questions.

  1. Which part of state $|\psi\rangle$ is due to the ancilla? If state $|0\rangle$ there represents part of the ancilla, it seems this ancilla state in $|\psi\rangle$ is not a single qubit, as it must have the same length as $|j\rangle$.

  2. What states are involved in this the swap test? My wild guess is state $|\psi\rangle$ and state $|\phi\rangle$ and the projection $\langle\phi|\psi\rangle$ is a state whose norm is the desired distance.

  3. How is this swap test performed in this setting? I guess an extra single qubit is needed to be the ancilla.

Your wisdom will be highly appreciated.

$\endgroup$
1
  • 2
    $\begingroup$ please keep in mind that posts on stackexchange should contain a single, laser-focused question; you can ask separate questions on separate posts $\endgroup$
    – glS
    Feb 10 '21 at 9:40
5
$\begingroup$

There are two different ancillas floating around, one used in $|\psi\rangle$ and another to conduct the swap test later on:

enter image description here

In the above picture with subsystems explicitly labeled we have \begin{align} |\psi \rangle_{A_2 B} &= \frac{1}{2} \left( |0\rangle_{A_2} |u\rangle_B + \frac{1}{\sqrt{M}} \sum_{j=1}^M |j\rangle_{A_2} |v_j\rangle_B\right) \\ |\phi\rangle_C &= \frac{1}{\sqrt{Z}} \left( ||\vec{u}|| |0\rangle_C - \frac{1}{\sqrt{M}} \sum_{j=1}^M ||\vec{v}_j|| |j\rangle_C \right) \end{align}

Its tedious to work out the SWAP test in this case, but you can verify that this makes sense by just choosing $M=1$ corresponding to a single vector $\vec{v}$ that you're comparing to $\vec{u}$. After the swap and final $H$ gate are performed your goal is to rewrite the state as

$$|0\rangle_{A_1} \left(|\psi_{A_2 B}\rangle |\phi\rangle_C + |\phi\rangle_{A_2} |\psi_{BC}\rangle \right) + \dots $$

which you will recognize from a typical SWAP test as having the readout probability of "0" in register $A_1$ being a function of $\langle \psi |\phi\rangle$. However the $|\psi_{BC}\rangle$ will have its registers out of order and will therefore appear ``backwards'' so you'll need to shuffle some subsystems to finish the derivation.

Answering your question:

  1. Yes, systems $A_2$ and $C$ are both $(M+1)$-dimensional, so you need $\lceil{\log_2 (M+1)}\rceil$ qubits in those registers
  2. Correct, you're trying to evaluate $\langle \psi | \phi \rangle $, which corresponds to $\langle \vec{u}, \vec{V}\rangle$ where ($\vec{V} = \frac{1}{M} \sum_j \vec{v}_j$). However you will also need to estimate $Z$ to find $|| \vec{u} - \vec{V} ||^2$ as discussed in the paper.
  3. See diagram above
$\endgroup$
4
  • $\begingroup$ Perhaps I didn't make my first question clear. Imagine I have prepared input $|u\rangle$ and training states $\{\vec{v}_{j}\}$. What procedure is required/recommended to "adjoin an ancilla variable with M+1 states", as the author called, in order to construct their superposition $\psi\rangle$? $\endgroup$ Feb 10 '21 at 4:53
  • $\begingroup$ the quoted text just means introducing an $(M+1)$-dimensional system, be that in $O(\log M)$ qubits or a single $(M+1)$-dit. In this context, the authors suppose that they have access to qRAM, which loosely is just an operation that sends $\sum_i |i\rangle \rightarrow \sum_i |i\rangle |v_i\rangle$ (and so you can see that $|\psi\rangle$ can be trivially constructed from this process). Actually implementing qRAM is not likely to be easy. $\endgroup$
    – forky40
    Feb 10 '21 at 7:40
  • $\begingroup$ Thank you very much for your clarification. Your comment seems to suggest that in their paper, they assumed that they have access to a qRAM which could presumably produce this particular state. Is this what you implied? $\endgroup$ Feb 10 '21 at 9:20
  • $\begingroup$ yes, this clustering algorithm along with quantum PCA, HHL, and a host of other algorithms offering speedups for linear algebra all typically assume access to qRAM $\endgroup$
    – forky40
    Feb 10 '21 at 19:14

Not the answer you're looking for? Browse other questions tagged or ask your own question.