6
$\begingroup$

In Quantum Machine Learning for data scientists, Page 34 gives an algorithm to calculate the distance between two classifical vectors. As mentioned in this question, it is not clear how the SwapTest is done and used to derive the distance. One answer from @cnada suggested that the swap is on the ancilla qubit only, per the original paper Quantum algorithms for supervised and unsupervised machine learning. However, the SwapTest was not designed on partial inputs.

I try to adapt SwapTest (on Page 33 of Quantum Machine Learning for data scientists) to derive as follows (by updating formula 131 with a minus sign, per the same answer from @cnada above), but cannot find the distance from the measurement at all.

First, initialize per DistCalc: $$ |\psi\rangle = \frac{1}{\sqrt{2}} (|0,a\rangle + |1,b\rangle) $$ $$ |\phi\rangle = \frac{1}{\sqrt{Z}} (|a||0\rangle - |b||1\rangle) $$ Also let: $$ |\psi'\rangle = \frac{1}{\sqrt{2}} (|a,0\rangle + |b,1\rangle) $$ Note that $\psi'$ is a valid (normalized) qubit as it can be obtained by swapping qubits from $|\psi\rangle$.

Now, initialize per SwapTest: $$ | 0, \psi, \phi \rangle = \frac{1}{\sqrt{2Z}} (|a|| 0,0,a,0\rangle - |b|| 0,0,a,1\rangle +|a|| 0,1,b,0\rangle - |b|| 0,1,b,1\rangle $$

Apply Hadamard gate on first qubit: $$ | 0, \psi, \phi \rangle = \frac{1}{2\sqrt{Z}} (|a|| 0,0,a,0\rangle + |a|| 1,0,a,0\rangle - |b|| 0,0,a,1\rangle -|b|| 1,0,a,1\rangle$$ $$+ |a|| 0,1,b,0\rangle+|a|| 1,1,b,0\rangle - |b|| 0,1,b,1\rangle - |b|| 1,1,b,1\rangle ) $$

Apply Swap gate on the ancilla qubit of $\psi$ (before $a$ or $b$) and the only qubit on $\phi$ (after $a$ or $b$): $$ | 0, \psi, \phi \rangle = \frac{1}{2\sqrt{Z}} (|a|| 0,0,a,0\rangle + |a|| 1,0,a,0\rangle - |b|| 0,1,a,0\rangle -|b|| 1,1,a,0\rangle$$ $$+ |a|| 0,0,b,1\rangle+|a|| 1,0,b,1\rangle - |b|| 0,1,b,1\rangle - |b|| 1,1,b,1\rangle ) $$ $$= \frac{1}{\sqrt{2Z}} (|a|\frac{| 0 \rangle+| 1 \rangle}{\sqrt{2}}| 0 \rangle - |b|\frac{| 0 \rangle+| 1 \rangle}{\sqrt{2}}| 1 \rangle)(| a,0 \rangle+| b,1 \rangle)$$

Apply Hadamard on first qubit: $$ \frac{1}{\sqrt{2Z}} (|a|| 0,0 \rangle - |b|| 0,1 \rangle)(| a,0 \rangle+| b,1 \rangle)$$

Measure on first qubit to get probability in getting first qubit in $| 0 \rangle$: $$ \vert \frac{1}{\sqrt{2Z}} (|a|\langle 0| 0,0 \rangle - |b|\langle 0| 0,1 \rangle)(| a,0 \rangle+| b,1 \rangle)]\vert^2$$ $$=\frac{1}{2Z} \vert(|a||0 \rangle - |b||1 \rangle)(| a,0 \rangle+| b,1 \rangle)\vert^2$$ $$=\vert\frac{|a||0 \rangle - |b||1 \rangle}{\sqrt{Z}}\vert^2 \vert\frac{| a,0 \rangle+| b,1 \rangle}{\sqrt{2}}\vert^2$$ $$=||\phi\rangle|^2||\psi'\rangle|^2 = 1$$.

However, this is independent of the distance $|a - b|$=$||a||a\rangle - |b||b\rangle|$.

Another way to think about this is that in the SwapTest, both $|a\rangle$ and $|b\rangle$ are $|0\rangle$ if the swap is indeed done on the ancilla bit of $\psi$. Then $|\langle a| b\rangle|=1$.

Is there anything wrong in my derivation above?

$\endgroup$
  • $\begingroup$ this might help you quantumcomputing.stackexchange.com/questions/5719/… $\endgroup$ – Aman Aug 21 '19 at 10:26
  • $\begingroup$ @Aman thanks. I had read through that thread and your thread about the inner product before posting this question. Thanks to both, I was able to try the above derivation. I appreciate the extension of inner product of two vectors with different length. My problem is to apply the SwapTest on such vectors without detailed derivation. In case you can help me by pointing out the mistakes made in my derivation, that would be very helpful for my stubborn brain :-) $\endgroup$ – czwang Aug 21 '19 at 14:10
1
$\begingroup$

The problem is that you applied a Swap gate when you should have applied a CSWAP, and so you never entangled the readout qubit with your query states (as a result the readout qubit will always return a "0", which makes sense because the net effect of $HH|0\rangle$ is $I|0\rangle$).

Continuing your derivation starting from just after the first Hadamard, we apply a CSWAP gate on the ancilla qubit of $\psi$ (before $a$ or $b$) and the only qubit on $\phi$ (after $a$ or $b$):

$$ \rightarrow \frac{1}{2\sqrt{Z}} (|a|| 0,0,a,0\rangle + |a|| 1,0,a,0\rangle - |b|| 0,0,a,1\rangle -|b|| 1,1,a,0\rangle$$ $$+ |a|| 0,1,b,0\rangle+|a|| 1,0,b,1\rangle - |b|| 0,1,b,1\rangle - |b|| 1,1,b,1\rangle ) $$

Rearranging before applying the Hadamard: $$ \rightarrow \frac{1}{2\sqrt{Z}} (|a|(|0\rangle + |1\rangle) |0,a,0\rangle - |b|(|0\rangle + |1\rangle) |1,b,1\rangle$$ $$ + (|a|| 0,1,b,0\rangle +|a|| 1,0,b,1\rangle - |b|| 0,0,a,1\rangle -|b|| 1,1,a,0\rangle) $$

Now apply a Hadamard to the first qubit and group by the state of the first qubit (you only need to work out the amplitude for the first qubit being in "$|0\rangle$", and normalization will tell us the amplitude for being in "$|1\rangle$"): $$ \rightarrow \frac{1}{\sqrt{2Z}} |0\rangle \lbrack 2 |a| |0,a,0\rangle - |b| |0,a,1\rangle + |a| |1,b,0\rangle - 2|b| |1,b,1\rangle + |a||0,b,1\rangle -|b||1,a,0\rangle\rbrack + \cdots$$

$$=\frac{1}{\sqrt{2Z}} |0\rangle \lbrack (|0,a\rangle + |1,b\rangle ) (|a| |0\rangle - |b| |1\rangle ) + (|a| |0\rangle - |b| |1\rangle )(|a,0\rangle + |b,1\rangle ) \rbrack + \cdots $$

You can check that this is on the correct track because it has the form of the "symmetric" combination of swapped states that provides the amplitude for a "0" readout in the SWAP test (equation 127 from your first ref): $$ \frac{1}{2}|0\rangle (|\psi\rangle|\phi\rangle + |\phi\rangle|\psi\rangle) + \cdots $$

Though in this case you need to account for the fact that you only partially swapped the registers of $|\psi\rangle$ and $|\phi\rangle$, which is why the $a$ and $b$ states remain in the third slot for both parts of the superposition. Then from this simpler expression you can continue with the derivation of the ordinary SWAP test to find that the readout probability for "0" is directly related to Euclidean distance.

$\endgroup$
  • $\begingroup$ Thanks a lot for pointing out the mistakes of using SWAP instead of C-SWAP. I will provide a complete derivation according to your input! $\endgroup$ – czwang Sep 1 '19 at 22:52
0
$\begingroup$

Thanks for the answers from @forky40. I accept it as the right answer, but do want to provide a complete derivation as follows.

(Same as in the original question) First, initialize per DistCalc: $$ |\psi\rangle = \frac{1}{\sqrt{2}} (|0,a\rangle + |1,b\rangle) $$ $$ |\phi\rangle = \frac{1}{\sqrt{Z}} (|a||0\rangle - |b||1\rangle) $$ Also let: $$ |\psi'\rangle = \frac{1}{\sqrt{2}} (|a,0\rangle + |b,1\rangle) $$ Note that $\psi'$ is a valid (normalized) qubit as it can be obtained by swapping qubits from $|\psi\rangle$.

(Same as in the original question) Now, initialize per SwapTest: $$ | 0, \psi, \phi \rangle = \frac{1}{\sqrt{2Z}} (|a|| 0,0,a,0\rangle - |b|| 0,0,a,1\rangle +|a|| 0,1,b,0\rangle - |b|| 0,1,b,1\rangle $$

(Same as in the original question) Apply Hadamard gate on first qubit: $$ \frac{1}{2\sqrt{Z}} (|a|| 0,0,a,0\rangle + |a|| 1,0,a,0\rangle - |b|| 0,0,a,1\rangle -|b|| 1,0,a,1\rangle$$ $$+ |a|| 0,1,b,0\rangle+|a|| 1,1,b,0\rangle - |b|| 0,1,b,1\rangle - |b|| 1,1,b,1\rangle ) $$

(Updated as suggested by @forky40) Apply Control-Swap gate on the ancilla qubit of $\psi$ (before $a$ or $b$) and the only qubit on $\phi$ (after $a$ or $b$) with the first qubit as the control bit: $$ \frac{1}{2\sqrt{Z}} (|a|| 0,0,a,0\rangle + |a|| 1,0,a,0\rangle - |b|| 0,0,a,1\rangle -|b|| 1,1,a,0\rangle$$ $$+ |a|| 0,1,b,0\rangle+|a|| 1,0,b,1\rangle - |b|| 0,1,b,1\rangle - |b|| 1,1,b,1\rangle ) $$ $$= \frac{1}{\sqrt{2Z}} (|a|\frac{| 0 \rangle+| 1 \rangle}{\sqrt{2}}| 0,a,0 \rangle - |b|\frac{| 0 \rangle+| 1 \rangle}{\sqrt{2}}| 1,b,1 \rangle)$$ $$+\frac{1}{2\sqrt{Z}} ( - |b|| 0,0,a,1\rangle -|b|| 1,1,a,0\rangle+ |a|| 0,1,b,0\rangle+|a|| 1,0,b,1\rangle ) $$

Apply Hadamard on first qubit: $$ \frac{1}{\sqrt{2Z}} (|a|| 0,0,a,0 \rangle -|b|| 0,1,b,1 \rangle)$$ $$+\frac{1}{2\sqrt{2Z}} ( - |b|| 0,0,a,1\rangle - |b|| 1,0,a,1\rangle -|b|| 0,1,a,0\rangle+|b|| 1,1,a,0\rangle$$ $$+ |a|| 0,1,b,0\rangle+ |a|| 1,1,b,0\rangle+|a|| 0,0,b,1\rangle -|a|| 1,0,b,1\rangle ) $$

Measure on first qubit to get probability in getting first qubit in $| 0 \rangle$: $$ \vert \frac{1}{\sqrt{2Z}} (|a|| 0,a,0 \rangle - |b|| 1,b,1 \rangle) +\frac{1}{2\sqrt{2Z}} ( - |b|| 0,a,1\rangle -|b|| 1,a,0\rangle + |a|| 1,b,0\rangle+ |a|| 0,b,1\rangle ) \vert^2$$ $$=\frac{1}{8Z} \vert(|a|(2|0,a,0 \rangle + |1,b,0 \rangle+|0,b,1\rangle)-|b|(2| 1,b,1 \rangle+| 0,a,1 \rangle+|1,a,0\rangle)\vert^2$$

Now consider qubits before and after $a$ and $b$, there are four combinations. Hence the probability is $$\frac{1}{8Z}(|a|^2(2^2+1+1) + |b|^2 (2^2+1+1) $$ $$ -|a||b|(\langle 0,b,1|0,a,1\rangle+\langle 0,a,1|0,b,1\rangle) -|a||b| (\langle 1,b,0|1,a,0\rangle+\langle 1,a,0|1,b,0\rangle)$$ $$=\frac{1}{8Z}(6(|a|^2+|b|^2)-2|a||b|\langle a|b \rangle -2|a||b|\langle b|a \rangle) = \frac{1}{8Z}(6Z-4|a||b|\langle a|b \rangle)$$ $$=\frac{3}{4} - \frac{|a||b|}{2Z}\langle a|b \rangle$$

Alternatively, the probability can be rewritten to $$\frac{1}{4Z} \vert(|a|(|0,\psi' \rangle + |\psi,0\rangle) -|b|(| 1,\psi' \rangle+| \psi,1\rangle)\vert^2$$ $$=\frac{1}{4} \vert(|\phi,\psi' \rangle + |\psi,\phi\rangle)\vert^2$$ $$=\frac{1}{4} (\langle \phi,\psi'|\phi,\psi' \rangle + \langle \psi,\phi |\psi,\phi\rangle + \langle \phi,\psi'|\psi,\phi \rangle + \langle \psi,\phi |\phi,\psi'\rangle) $$

Note that $$|\psi,\phi\rangle = \frac{1}{\sqrt{2Z}}(|a|(|0,a,0\rangle+|1,b,0\rangle)-|b|(|0,a,1\rangle+|1,b,1\rangle)$$ $$|\phi,\psi'\rangle = \frac{1}{\sqrt{2Z}}(|a|(|0,a,0\rangle+|0,b,1\rangle)-|b|(|1,a,0\rangle+|1,b,1\rangle)$$ $$\langle \phi,\psi'|\psi,\phi\rangle = \langle \psi,\phi|\phi,\psi'\rangle = \frac{1}{2Z}(|a|^2+|b|^2-2|a|b|\langle a|b \rangle)=\frac{1}{2}-\frac{1}{Z}|a|b|\langle a|b \rangle$$ Hence the probability is $$\frac{1}{4}(1+1+2(\frac{1}{2}-\frac{1}{Z}|a|b|\langle a|b \rangle)=\frac{3}{4} - \frac{|a||b|}{2Z}\langle a|b \rangle$$

Finally $$\frac{3}{4} - \frac{|a||b|}{2Z}\langle a|b \rangle=\frac{1}{2}+\frac{Z-2|a||b|\langle a|b \rangle}{4Z}$$ $$=\frac{1}{2}+\frac{|a|^2 \langle a|a \rangle + |b|^2 \langle b|b \rangle -2|a||b|\langle a|b \rangle}{4Z}$$ $$=\frac{1}{2}+\frac{||a||a \rangle - |b||b \rangle|^2}{4Z}=\frac{1}{2}+\frac{|a-b|^2}{4Z}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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