Calculating the quantum euclidean distance between vectors

Question

I am trying to get the distance using the swap test circuit.

,

With the help of the codes I shared, I can only estimate the distance between two vectors. Can it calculate the distances of many vectors from each other with the help of a single circuit?

# import the necessary libraries 
import math as m
from qiskit import *
from qiskit import BasicAer
from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister, execute
from qiskit_quantum_knn.encoding import analog
from numpy import linalg as LA
from scipy.spatial import distance



# First step is to encode the data into quantum states. 
#There are some techniques to do it, in this case Amplitude embedding was used.


A= [2,9,8,5,4,18,16,10]
B= [7,5,10,3,14,10,20,6]


A_norm=LA.norm(A)
B_norm=LA.norm(B)
Dist=distance.euclidean(A, B)
Z = round( A_norm**2 + B_norm**2 )
 
# create phi and psi state with the data    
phi = [A_norm/m.sqrt(Z),-B_norm/m.sqrt(Z)]
psi = []

for i in range(len(A)):
    psi.append(((A[i]/A_norm) /m.sqrt(2)))
    psi.append(((B[i]/B_norm) /m.sqrt(2)))
    
# Quantum Circuit
q1 = QuantumRegister(1,name='q1')
q2 = QuantumRegister(1,name='q2')
q3 = QuantumRegister(4,name='q3')
c = ClassicalRegister(1,name='c')
qc= QuantumCircuit(q1,q2,q3,c)

# states initialization
qc.initialize( phi, q2[0] )
qc.initialize( psi, q3[0:4])

# The swap test operator 
qc.h( q1[0])
qc.cswap( q1[0], q2[0], q3[0] )
qc.h( q1[0] )
qc.measure(q1,c)

display(qc.draw(output="mpl"))


## Results
shots = 1000000
job = execute(qc,Aer.get_backend('qasm_simulator'),shots=shots)
job_result = job.result()
counts = job_result.get_counts(qc)
x = abs(((counts['0']/shots - 0.5)/0.5)*2*Z)
Q_Dist = round(m.sqrt(x),4)
print('Quantum Distance: ', round(Q_Dist,3))    
print('Euclidean Distance: ',round(Dist,3))   

Answer 1

Edit: this answer refers to v1 of the preprint in the link OP provided. I didn't look closely at the subsequent versions.

As explained in the link you provided, given access to an oracle that prepares each state in the set $\{ |\phi_i\rangle\}$ for $i=1, \dots, M$ and some fixed state $|\psi\rangle$, you can estimate $F_i =|\langle \psi |\phi_i \rangle|^2$ for $i=1, \dots, M$ using many repetitions of the circuit provided in Figure 4 of that preprint. If you read through Section IIIA it will describe how to modify the standard SWAP test for this purpose. The only major change is that you need to add a fourth register containing $m=\lceil \log (\text{len}(A))\rceil$ qubits (3 in your case) and have a unitary $W$ that acts on your third and fourth registers according to $$ \tag{1} W|0\rangle^{\otimes n}|i\rangle = |\phi_i\rangle |i\rangle $$

If you read carefully through the rest of that section it will describe the outputs of this circuit and therefore how it samples approximations of $F_i$ according to their magnitude, thereby sampling the distances of $|\psi\rangle$ to its K nearest neighbors. However, you are probably better off just using your code for a normal SWAP test with randomly sampled $|\phi_i\rangle$, as I will demonstrate below.

---

An equivalent alternative

I'm going to demonstrate why this is maybe not such a good idea compared to just performing the standard SWAP test. Consider Equations 18 and 22 in the preprint, the first of which describes the probability of measuring the first qubit as "0" and the second describes the probability of measuring the fourth register in "i" conditioned on the first register being "0":

\begin{align} p(0) &= \frac{1}{2} + \frac{1}{2M} \sum_{j=1}^M F_j \tag{2, 18 in preprint}\\ p(i|0) &= \frac{1 + F_i}{M + \sum_{j=1}^M F_j} \tag{3, 22 in preprint} \end{align}

Then the joint probability distribution over both registers is just \begin{align} p(i, 0) &= p(i|0) p(0) \tag{4} \\&= \frac{1 + F_i}{M + \sum_{j=1}^M F_j} \cdot \frac{1}{2M}\left(M + \sum_{j=1}^M F_j \right) \tag{5} \\&= \frac{1 + F_i}{2M} \tag{6} \end{align}

Now consider a different protocol with joint distribution $p'(i, 0)$ over the same registers. This protocol is very simple: Randomly uniformly sample $i \in \{1, \dots, M\}$, and then perform a standard SWAP test between $|\psi\rangle$ and $|\phi_i\rangle$. Using standard results from the SWAP test we have \begin{align} p'(i, 0) &= p'(i) p'(0|i) \tag{7} \\&= \frac{1}{M} \left(\frac{1}{2} + \frac{1}{2} F_i\right) \tag{8} \\&= \frac{1 + F_i}{2M} \tag{9} \\&= p(i, 0) \tag{10} \end{align}

This demonstrates that we can exactly reproduce the output distribution of their proposed protocol using classical random numbers instead of quantum superposition (and significantly fewer operations and qubits). Of course, their approach uses marginals $p(i|0)$ which we can't directly access here, but we can of course compute these just using postprocessing on $p'(i, 0)$.

---

Why this algorithm isn't necessary

Intuitively what's going on here is that when they apply $H^{\otimes m}$ to the fourth register that they introduce, they put the register into a uniform superposition over all computational basis states $\{|i\rangle \}$ for $i=1, \dots, M$. Then the $W$ operator combined with a SWAP test is able to slightly bias sampling of states $i$ according to their inner product $F_i$ with $|\psi\rangle$, but the amount of bias is bounded by the fact that $F_i \leq 1$. So your chances of finding the K nearest neighbors can only improve from an initial $1/M$ to $2/M$. But this is exactly how much you can improve the chance of success for a standard SWAP test when you initially draw $i$ with probability $1/M$

On a more intuitive level, the problem here is that they do not actually use the superposition of the fourth register in a quantum way. Compare their circuit in Figure 4 to the circuit for the Deutsch-Jozsa algorithm, for example, in which case an additional layer of Hadamards is applied at the end of the register to take advantage of destructive intereference of the amplitudes. In contrast, here they just use registers 3 and 4 to prepare a uniform superposition over $\{|\phi_i\rangle\}$ before feeding it into the SWAP test.