Transcript Quantum Computing

1
Why does quantum computing matter?
 Quantum mechanics has proven to be extremely successful at predicting particle behavior. But it’s also
deeply weird: 90 years after the basic math was worked out in the 1920s, there’s still nothing like a
consensus as to what’s actually happening at the particle level (or even, arguably, at the macro level!).
All we have are these incredibly accurate formulas and a bunch of wacko theories.

Feynman: “I think I can safely say that nobody understands quantum mechanics.”
 Starting around 1980, people wondered whether the weirdness at the core of quantum physics could be
used to speed up computers. A series of landmark papers concluded with a strong yes: in theory (that is, if
we can build the required equipment), there are problems that can be solved exponentially faster using
quantum phenomena, and problems that are only tractable at all using quantum phenomena!
 But progress on the actual hardware is slow. The required setups are very delicate: several decades in, we
only have toy proof-of-concept results. The state of the art is an experiment that factored 143 into 11×13…
 Still, this is the only active field I know of with the potential for drastic leaps in computation speed.
 It’s a technical topic and I’m no expert, just an interested layman1… So this is neither a broad nor deep
overview, just a taste of the unique particle behavior that makes quantum computing work. (Largely
adapted from Thomas Strub’s nice presentation at http://katzgraber.org/teaching/FS08/files/strub.pdf.)
1
In particular, I can’t follow the math at all.
2
The essence of quantum, in one simple experiment
 The Mach-Zehnder interferometer gives us a beautiful illustration
of the fundamental weirdness of quantum physics.
Photons
 The setup at right sends photons, one at a time, into a series of
mirrors and half-silvered mirrors, to either detector D1 or D2.


The red arrows show the paths of photons whose phase has been
reversed by being reflected in a mirror.
Half-silvered mirrors are special mirrors that reflect incoming photons
50% of the time. They also have the cunning property that only one
side of a half-silvered mirror reverses the phase of reflected photons:
the other side leaves a reflected photon’s phase unchanged.
 So there are four equally likely paths a photon can take. Two
end at D1, two at D2. And if we cover either of the (full) mirrors,
we indeed see 50% of photons hitting D1, 50% D2.
 But if we leave both mirrors uncovered, 100% of photons hit D1!
This is really weird. By blocking one path (covering a mirror with
our hand), we cause more photons to hit D2.
Mirror
Half-silvered
mirror
Red =
reversed
phase
Detector D2
Detector D1
3
The essence of quantum, in one simple experiment
 What’s going on? The short answer is that after 90 years, there’s
still no consensus understanding of how blocking a path can
cause more particles to hit a detector. But there are excellent
mathematical formulas for predicting the results.
 Quantum mechanics tells us that, if we carefully set up an
apparatus like this with multiple paths each particle may take,
but no way for us to tell which path it took, then our results will
be as if each particle followed the “sum” of the paths – where
the “sum” can include wave-like destructive interference.

Photons
Mirror
Half-silvered
mirror
Red =
reversed
phase
Detector D2
We see destructive interference at D2. The key difference between
D1 and D2 is that the two paths arriving at D1 are in the same phase,
and thus add up as usual; but the two paths arriving at D2 are in
opposite phase, and therefore “sum” destructively to 0 – no photons.
 This is a fascinating topic with implications far beyond particle
physics… (Do particles actually follow all available paths, or are
the results just “as if” they did? What about things larger than
particles?) But why does this matter for computer science?
Detector D1
4
Primitive quantum computing: Deutsch’s Algorithm
 Suppose I give you two filters A and B, each of which takes in a
photon and either emits it unchanged, or reverses its phase (like
a mirror does) – you don’t know which.
Photons
 Your task is to determine whether:
a)
b)
A and B match (both leave phase unchanged/both reverse it), or
A and B are different.
 Classically, we’d need to send one photon into A and observe
the result, then send a 2nd photon through B and see if the result
matches A. So we’d need two photons.
 But using quantum, we only need a single photon! We just stick
the filters in front of the two (full) mirrors in our Mach-Zehnder
setup from before. If A and B are the same, our photon will hit
D1 (since all photons will hit D1, as before).
 And if A and B are different, our photon (all photons) will hit D2!
So we can just send one photon and see which detector is hit.
B
Half-silvered
mirror
A
Mirror
Red =
reversed
phase
Detector D2
Detector D1
 This is a contrived problem. But going from “need 2
observations” to “need 1 observation” has major implications…
5
2 observations->1 seems like a small gain, but…
 The next step up in sophistication is the Deutsch-Jozsa Algorithm, a generalization of the previous problem.

Suppose I give you a function mapping n binary inputs to a binary output. That is, there are 2n possible combined
inputs, and each one maps to either 0 or 1.

I further assure you that either the function is constant (there’s only one output: either all inputs map to 0, or all inputs
map to 1), or it’s balanced (half the 2n inputs map to 0, the other half to 1). Your task is to figure out which.

Classically, we’d have to keep trying different input combos one by one. So in the worst case, if we keep getting the
same output value, we could need to try half the inputs (2n-1+1) to determine the answer, “constant” or “balanced”…

Whereas by a clever extension of the quantum setup from the previous problem, we can get our answer by sending n
photons through in a single pass! That’s an exponential speedup – from 2n-1+1 executions of the function, to 1.
 OK, that’s still a contrived problem. But toy problems like this spurred research, leading to spectacular
results like Shor’s Algorithm (1994). Shor showed how a quantum computer could factor large integers in
polynomial time – much faster than the known (exponential) classical algorithms.

Shor’s Algorithm is too complex to cover here, but fast factoring would have major real-world implications: many
cryptographic security systems, like RSA, are based on the difficulty (slowness) of factoring large numbers.
 Quantum algorithms abstract away the mechanics of mirrors and photons, and compute in terms of qubits
– not just 1 or 0 like classical bits, but in some uncertain superposed (interfering) combination of 1 and 0.
6
State of the art: promising, always promising…
 As mentioned before, in 2011 a quantum apparatus with 4 qubits
was successfully used to factor 143. But nothing resembling a
general-purpose quantum computer is visible on the near horizon.
 D-Wave Systems sell what they claim is a 128-qubit quantum
computer, but academics are skeptical. Certainly they aren’t the
general-purpose quantum computer that could run Shor’s
Algorithm on large numbers, etc, though the consensus seems to
be that they do make genuine use of quantum phenomena.
 Quantum computing’s potential is often exaggerated: doesn’t let
us do arbitrary parallel calculations and see all the results – in the
end we only get to see one result (the photon only ends up in one
place, once we observe it). But the interference between those
parallel worlds does let us do something near magic.
Img source: http://www.canadianbusiness.com/
7