4
$\begingroup$

I've been reading Peter Wittek's Quantum Machine Learning. In chapter 10.2 of this book, the author explains how we can calculate the dot product of two states:

To evaluate the dot product of two training instances, we need to do the following (Lloyd et al., 2013a):
● Generate two states, $|\psi\rangle$ and $|\phi\rangle$, with an ancilla variable;
● Estimate the parameter Z = $\|x_i\|^2$ + $\|x_j\|^2$, the sum of the squared norms of the two instances;
● Perform a projective measurement on the ancilla alone, comparing the two states.

The author further goes on explaining the process:

Z times the probability of the success of the measurement yields the square of the Euclidean distance between the two training instances: $\|x_i - x_j\|^2$. We calculate the dot product in the linear kernel as $x_i^Tx_j = \frac{Z-\|x_i-x_j\|^2}{2}.$

I am not sure what does 'success of measurement' means in this context. From my understanding, we first need to estimate Z (which is done while preparing $|\psi \rangle$ and $|\phi \rangle$) and then using the prepared states, along with an ancilla, we measure the distance(?) between the two training instances by using a swap test on the above-prepared state. Just for reference, the states are: $$|\psi \rangle = \frac{|0\rangle|x_i\rangle + |1\rangle|x_j\rangle}{\sqrt 2}$$ $$|\phi \rangle = \frac{\|x_i\| |0\rangle - \|x_j\| |1\rangle}{Z}.$$

$\endgroup$
6
  • $\begingroup$ In the swap test, you usually measure the ancilla qubit in the computational basis and the result would be something like '0101111011101100....'. The probability of the success of the measurement, I think (though I didn't carefully check it), should be the probability of getting 0 (or +1 from +1/-1 if you like). For the relationship between the probability and the estimate of the 'dot product', maybe Michael Walter's lecture (staff.fnwi.uva.nl/m.walter/physics491/lecture10.pdf, starting from 10.2) well explained it or you can check it by yourself using only linear algebra. $\endgroup$
    – raycosine
    Commented Jan 5, 2021 at 8:11
  • $\begingroup$ is this the swap test, or another algorithm? $\endgroup$
    – glS
    Commented Jan 5, 2021 at 11:27
  • $\begingroup$ @glS we only use a swap test in the last part of the algorithm to determine whether or not they are equivalent. $\endgroup$ Commented Jan 5, 2021 at 12:51
  • $\begingroup$ it's a bit hard to say without having the book at hand, but the extract you quote mentions doing a projective measurement on the ancilla. I assume the "success of measurement" is meant as the event in which the ancilla is measured in some state (presumably $|1\rangle$?). Does that make sense in the context? $\endgroup$
    – glS
    Commented Jan 5, 2021 at 15:37
  • $\begingroup$ @gIS The sub-section is available in the link that I have provided, I would have added that here but that would have made the post unnecessarily long. From what I can understand from the book and source provided in the comments is that we use swap test to confirm if they are equivalent or not. If they are not equivalent, the result that we will get is somehow correlated to the distance between the points. If they are exactly equal we will get |0\rangle with 100% probability, otherwise, we'll get an expected value somewhere in between. $\endgroup$ Commented Jan 6, 2021 at 16:33

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.