# How to do quantum circuit arithmetic?

I'm looking at a circuit from this paper on quantum machine learning.

So to introduce my own notation:

• we start with $$|\psi_0⟩ = |0,a,b⟩ = a_0b_0|000⟩ + a_0b_1|001⟩ + a_1b_0|010⟩ + a_1b_1|011⟩$$
• after the first $$H$$-gate we have $$|\psi_1⟩$$
• after the controlled-SWAP we have $$|\psi_2⟩$$
• after the second $$H$$-gate we have $$|\psi_3⟩$$

The paper says that at the end we measure $$|0⟩$$ for the top qubit with the following probability:

$$P(|0⟩_{\psi_3}) = \frac{1}{2} + \frac{1}{2}|⟨a|b⟩|^2$$

As I'm new to this I decided to do the expansion by hand.

The first two rows are grouped for $$\vert 0xx\rangle$$ and the second two rows are for $$\vert 1xx\rangle$$. As I understand, I can get $$P(|0⟩_{\psi_3})$$ by summing the probability amplitudes for the first two rows.

Here's what's baffling me:

The first two rows are basically what you would get back if you skipped the controlled-swap. You'd just come back to $$|\psi_0⟩$$. And as before, you'd get:

$$P(|0⟩_{\psi_0}) = |a_0b_0| + |a_0b_1| + |a_1b_0| + |a_1b_1|$$

So that means the probability amplitudes of the first two rows sum up to 1. Which leaves me very confused because there are still two more rows to consider which would add on another $$|a_0b_1| + |a_1b_0|$$.

Thanks for your time!

• First of all count the terms with 0, you can see from counting that 1/2 of the terms will result in 0, this gives you the first part of the expression for P = 1/2 + .... , – Sam Palmer Jun 5 '20 at 14:23
• No worries I got it! Thank you – Alexander Soare Jun 5 '20 at 14:43
• Sorry I was looking at this on my phone, the first four do not sum to 1, because remember you are multiplying by the normalisation factor of 1/2, so you are summing $1/2a_nb_m$, also from a simple permutations argument you can see that half of the terms will have 0. – Sam Palmer Jun 5 '20 at 14:43
• it is also worth noting that $|\langle a|b\rangle|^2$ is known as the fidelity and for the two density operators is given as $(\text{tr}\sqrt{\sqrt{\rho_a}\rho_b\sqrt{\rho_a}})^2$ – Sam Palmer Jun 5 '20 at 14:57
• Awesome thank you. Yes that arithmetic was not well wired in my head. Hopefully this hour spent on it will hammer it in. – Alexander Soare Jun 5 '20 at 14:59

## 2 Answers

For completeness i'm going to give the proof of the swap test:

The initial state is given as, where I will use a slight abuse of notation on the R.H.S ($$|0\rangle|a\rangle|b\rangle \equiv |0\rangle \otimes|a\rangle \otimes|b\rangle$$, where $$|a\rangle$$ and $$|b\rangle$$ are states NOT bases).

$$|\phi_1 \rangle = a_0b_0|000\rangle + a_1b_0|010\rangle + a_0b_1|001\rangle + a_1b_1|011\rangle = |0\rangle|a\rangle|b\rangle$$

applying $$H$$

$$H|0\rangle|a\rangle|b\rangle = \frac{1}{\sqrt{2}}|0\rangle|a\rangle|b\rangle + \frac{1}{\sqrt{2}}|1\rangle|a\rangle|b\rangle$$,

Now, if we were to take the measurement of either $$|0\rangle$$ or $$|1\rangle$$ now the inner products of the measurements would give:

$$P(0) = (\frac{1}{\sqrt{2}}\langle b|\langle a| \langle 0|)(\frac{1}{\sqrt{2}}|0\rangle|a\rangle|b\rangle) = \frac{1}{2}$$

Which isn't very useful, so by applying the swap:

$$|\phi_3\rangle = \frac{1}{\sqrt{2}}|0\rangle|a\rangle|b\rangle + \frac{1}{\sqrt{2}}|1\rangle|b\rangle|a\rangle$$

we will see that this changes the inner product of the measurements.

Applying the second $$H$$

$$H|\phi_3\rangle = \frac{1}{2}|0\rangle|a\rangle|b\rangle + \frac{1}{2}|1\rangle|a\rangle|b\rangle + \frac{1}{2}|0\rangle|b\rangle|a\rangle - \frac{1}{2}|1\rangle|b\rangle|a\rangle = \frac{1}{2}|0\rangle \left[|a\rangle|b\rangle + |b\rangle|a\rangle\right] + \frac{1}{2}|1\rangle \left[|a\rangle|b\rangle - |b\rangle|a\rangle \right]$$.

So first by inspection we can see with at least probability $$\frac{1}{2}$$ that we will measure the first qubit in $$|0\rangle$$.

Now we take the inner product for the $$|0\rangle$$ measurement:

$$P(0) = \frac{1}{4}(\langle a|\langle b| + \langle b|\langle a|)\langle 0 |0\rangle(|a\rangle|b\rangle + |b\rangle|a\rangle) = \frac{1}{4}(\langle a| \langle b| a \rangle |b\rangle + \langle a| \langle b| b \rangle |a\rangle + \langle b| \langle a| a \rangle |b\rangle + \langle b| \langle a| b \rangle |a\rangle) = \frac{1}{2} + \frac{1}{2}\langle b| \langle a| b \rangle |a\rangle = \frac{1}{2} + \frac{1}{2}|\langle a|b\rangle|^2$$

(remembering the abuse of notation s.t. $$\langle a | b \rangle \neq 0$$ because it is the inner product of the states $$|a\rangle = a_0|0\rangle + a_1|1\rangle$$ and not the bases of type $$|a\rangle$$ and $$|b\rangle$$. However by completion we know that $$\langle a | a \rangle = 1$$)

Finally how can $$\langle b| \langle a| b \rangle |a\rangle)$$ be the fidelity? We will use some rearranging and remeber that the inner product is a scalar, however we need to be careful because it is a complex scalar! So we can write

$$\langle b| \langle a| b \rangle |a\rangle = \langle a| b \rangle\langle b| a \rangle$$,

by shuffling the scalar terms, and we can also see that

$$\langle b| \langle a| b \rangle |a\rangle = \langle a| b \rangle\langle b| a \rangle = \langle a| \langle b| a \rangle |b\rangle$$

However $$\langle a| b \rangle \neq \langle b| a \rangle$$ so we can't just square the inner product term. But we can use the relation via the complex conjugate:

$$\langle b| a \rangle = \langle a| b \rangle^\dagger$$.

Hence we can write this as the modulus squared

$$\langle a| b \rangle\langle b| a \rangle = \langle a| b \rangle\langle a| b \rangle^\dagger = |\langle a| b \rangle|^2$$

• Thanks for the added insight. Regarding your "by inspection" I'm trying to put your thinking cap on and see that as naturally as you do. The only difference in the two terms is the sign in front of |b>|a> so I suppose somehow you're using that. Unfortunately, I don't see clearly why it's so obvious that it guarantees |0> will be measured with at least as much probability as |1>. – Alexander Soare Jun 5 '20 at 16:14
• if you look at the q and p terms you will see p has a minus sign inside subtracting from the same term that is added in q, therefore q > p, and we that the result has to either one or the other, so the larger term has to be at least 0.5 – Sam Palmer Jun 5 '20 at 16:43
• Ahh I see, I think what wasn't clear to me is that one is allowed to use that logic when adding and subtracting wavefunctions. But thanks, that will help me make the connection. – Alexander Soare Jun 5 '20 at 16:47
• as long as you are careful about grouping terms and their amplitudes you can, however I have used a slight abuse of notation so I understand your confusion! But given both are exactly the same except for the minus sign it is safe to assume that q > p. – Sam Palmer Jun 5 '20 at 16:52
• I added a final bit at the end deriving the fidelity term to fully complete the proof :) – Sam Palmer Jun 5 '20 at 17:15

Found it! To me it actually feels very sneaky so I'll take the time to explain it.

Focussing on just the top two rows of my handwritten expansion:

I made the mistake of taking vertically adjacent pairs of coefficients, adding them together, and dividing by 2.

So from left to right in vertical pairs:

$$\frac{1}{2}\big[2a_0b_0|0xx⟩\big] + \frac{1}{2}\big[2a_0b_1|0xx⟩\big] + \frac{1}{2}\big[2a_1b_0|0xx⟩\big] + \frac{1}{2}\big[2a_1b_1|0xx⟩\big] \tag{1A}$$

Then I just cancelled the 2's and was left with:

$$|a_0b_0| + |a_0b_1| + |a_1b_0| + |a_1b_1| = 1 \tag{2A}$$

hence my confusion.

The mistake was made when I did the grouping for the first |0⟩ disregarding the rest of the state. But if we look at the columns 2 and 3 we see that the 2nd and 3rd qubits are inverted, so I can't do the grouping. The proper way of what I meant to do in (1A) would then be:

$$\frac{1}{2}\big[2a_0b_0|000⟩\big] + \frac{1}{2}\big[a_0b_1|001⟩\big] + \frac{1}{2}\big[a_0b_1|010⟩\big] + \frac{1}{2}\big[a_1b_0|010⟩\big] + \frac{1}{2}\big[a_1b_0|001⟩\big] + \frac{1}{2}\big[2a_1b_1|011⟩\big] \tag{1B}$$

And actually once you take the norms with these coefficients you get

$$|a_0 b_0|^2 + \frac{1}{2} | a_0 b_1 + a_1 b_0 |^2 + |a_1 b_1|^2 \neq 1 \tag{2B}$$

And that makes up the gap.

EDIT Also as pointed out in the comments, the whole point of this section in the paper is to express the result in terms of the fidelity $$|⟨a|b⟩|$$. This answer explains how to do that.