10. Quantum Computing

Note: these notes are fairly short and do not comprehensively discuss the background behind quantum computing. This is because I had prior knowledge regarding quantum computing, and wasn't particularly interested in writing a whole essay here about it since I already knew... sorry :(

That said, I do recommend books like Quantum Mechanics: The Theoretical Minimum (Susskind and Friedman) or Quantum Computation and Quantum Information (Nielsen and Chung) for learning the basics (and perhaps even more!)

Quantum Complexity

$\mathrm{BQP}$ is the class of all problems efficiently solvable by a quantum computer. It is believed that $\mathrm{P}\subseteq \mathrm{BQP}$ , but $\mathrm{BQP}\not\subseteq \mathrm{NP}$ and $\mathrm{NP}\not\subseteq \mathrm{BQP}$ . In other words, there are problems within $\mathrm{BQP}$ that are not efficiently verifiable (e.g. how do you verify a physics simulation?) and there are problems within $\mathrm{NP}$ that are probably not efficiently solvable by a quantum computer.

Elitzur-Vaidman Bomb

Consider a box that may or may not contain a bomb, that interacts as follows with a qubit:

If it is empty, and we send $\ket{x}=a\ket{0}+b\ket{1}$ , nothing happens and $\ket{x}$ is returned.
If it has a bomb, and we send $\ket{x}$ as before, the bomb measures $\ket{x}$ in the $\{ \ket{0},\ket{1} \}$ basis. If the outcome is $\ket{0}$ , $\ket{0}$ is returned. Otherwise, the bomb explodes.

We want to determine a way to distinguish if the box has a bomb or not without causing an explosion if the box has a bomb.

In the classical world, there exists no such algorithm for this. Sending $\ket{0}$ does not confirm anything, and sending $\ket{1}$ will cause the bomb to explode if it exists. However, in the quantum world, we can create an opportunity to determine if a bomb exists without causing an explosion!

Let $\ket{x}=\ket{0}$ initially. Then, apply a $\frac{\pi}{4}$ (45°) rotation to $\ket{x}$ to produce $\ket{x}=\ket{+}=\frac{1}{\sqrt{ 2 }}(\ket{0}+\ket{1})$ . Then, we send $\ket{x}$ through the box.

If there is a bomb, it has an explosion probability of 50%.
Alternatively, if there is no bomb, $\ket{x}$ will be returned.

Finally, we rotate the output of the box by $\frac{\pi}{4}$ again and measure $\ket{x}$ .

If $\ket{0}$ is observed, we output "bomb."
If $\ket{1}$ is observed, we output "not sure."

Let's walk through the possible outcomes to see why this is the case.

If there is no bomb, $\ket{+}$ will be output by the box, which a $\frac{\pi}{4}$ degree rotation will then bring to $\ket{1}$ .
If there is a bomb, but no explosion, $\ket{0}$ will be output by the box, which a $\frac{\pi}{4}$ degree rotation will then bring to $\ket{+}$ . Measuring $\ket{+}$ has a $\frac{1}{2}$ chance of measuring $\ket{0}$ and a $\frac{1}{2}$ chance of measuring $\ket{1}$ .
If there is a bomb, but an explosion, it doesn't matter—we know there's a bomb, but we haven't accomplished our goal.

So, if there isn't a bomb, we'll always receive "not sure." After running this test $n$ times, there is a $1-\frac{1}{2^{n}}$ probability that the box has a bomb.

If there is a bomb, there is a 50% chance that the bomb's measurement results in $\ket{1}$ , an explosion. Otherwise, there is an addition 50/50 between returning "bomb" and returning "not sure." Thus, there is a $\frac{1}{2}$ chance of an explosion, a $\frac{1}{4}$ chance of returning "bomb," and a $\frac{1}{4}$ chance of returning "not sure."

However, $\frac{1}{2}$ is still a high chance—we can do better!

As before, let $\ket{x}=\ket{0}$ initially. However, our rotation angle now changes to $\theta=\left( \frac{\pi}{2} \right)/N$ , where $N$ is some chosen parameter. Then, for $t=1,\dots,N$ , we perform the same procedure.

Rotate $\ket{x}$ by $\theta$ .
Send $\ket{x}$ through the box. Let $\ket{x}$ be the value returned by the box.

Then, at the end, measure $\ket{x}$ . If $\ket{0}$ , return "bomb." Otherwise, return "empty."

Note that, in this procedure, the $\ket{x}$ sent into the box changes between rounds.

Let's analyze the possibilities again.

Empty:
The box will output $\ket{x}$ each time. After $N$ iterations, $\ket{x}$ will have rotated the full $N\cdot\theta=\frac{\pi}{2}$ radians. Thus, $\ket{x}=\ket{1}$ at the end.

Bomb:
Each time $\ket{x}$ passes through the box, if the bomb doesn't explode, $\ket{0}$ is returned. If there is never an explosion, and $\ket{x}=\ket{0}$ at the end, we know there is a bomb in the box. (Since empty implies $\ket{x}$ should be $\ket{1}$ ). But then, what's the probability of the bomb exploding? Well, the probability of the bomb exploding at $t=i$ is $\sin ^{2}\theta$ . The probability of the bomb exploding at some $t\in \{ 1,\dots,N \}$ is

P[\text{explosion}]=P[\text{explosion at }t=1]+\dots +P[\text{explosion at }t=N]

since the events are all disjoint. Thus,

P[\text{explosion}] = N\sin ^{2}\theta

For small $\theta$ , $\sin\theta \leq\theta$ , so

P[\text{explosion}]\leq N\theta^{2}=N\left( \frac{\pi/2}{N} \right)^{2}\leq \frac{2.5}{N}

Thus, for this algorithm, if the box is empty, it will output "empty" with a probability of $1$ . If there is a bomb, the box will explode with probability $\frac{2.5}{N}$ , and otherwise output "bomb." The time complexity, meanwhile, is $O(N)$ .

$N$ is known as the safety level—if avoiding an explosion is extremely important (especially if it's an actual bomb...), increasing $N$ will decrease the explosion probability, but increase the time complexity.