Quantum Computing Talk

A gentle introduction to quantum computing Mark Przepiora University of Calgary

July 9, 2009

Mark Przepiora

CUMC 2009

What is a computation?

Intuitively, you start with n bits, say 011011101. Gears turn, electrons flow, and you modify the bits in some way, until you end up with an m-bit string, say 101. So a computation implements some function f : {0, 1}n → {0, 1}m This doesn’t explain how the computation is performed, though. Strategy: interpret a simple computation algebraically, and see how this interpretation generalizes to the quantum world.

Mark Przepiora

CUMC 2009

A simple, classical computation Say our computer has exactly one bit of storage, so the state of our machine is always simply either 0 or 1. We want to compute the NOT function, i.e. NOT(0) = 1 and NOT(1) = 0. Let’s identify states in our machine with basis vectors:     1 0 0∼ 1∼ 0 1 Then it makes sense to identify   0 1 NOT ∼ 1 0 The above gives us an algebraic way of looking at computation without needing to worry about the physical process performing it. Mark Przepiora

CUMC 2009

(1)

And now for something completely different Let’s interpret the above in the context of quantum mechanics. According to quantum mechanics, every physical system can be represented by a Hilbert space (i.e. Cn in the finite-dimensional case) Any nonzero vector |ψi ∈ Cn is a possible state of the system And a mechanism can (in principle) be built to implement any unitary transformation on Cn Only unitary transformations can be realized. In particular, all operations are invertible. (Information never destroyed.) Given a state |ψi and any orthonormal P basis {|xi}, we can build a device to measure |ψi = x ax |xi in this basis, which will result in |xi being observed with (relative) probability |ax |2 and the system will “collapse” into this state. So if |ψi is already a basis vector, it can be measured exactly. Mark Przepiora

CUMC 2009

Reinterpreting the first slide Consider a system with n = 2 (e.g., the spin of an electron.) A system whose state space is C2 is called a qubit.     1 0 By convention we denote |0i = and |1i = 0 1   0 1 Note that the NOT matrix X = is unitary 1 0 If we could prepare the system in one of the states |0i or |1i and construct a device to implement the above matrix, we could apply it to compute NOT of a single bit. This method is actually much more general, though, because we could prepare the system in any superposition a |0i + b |1i and compute its “quantum NOT”

Mark Przepiora

CUMC 2009

A more interesting one-qubit operator

Consider the unitary transformation H =

√1 2



1 1 1 −1

 (the

Hadamard matrix.) Easy to see it is unitary. H |0i =

|0i+|1i √ 2

and H |1i =

|0i−|1i √ 2

“Generates a qubit that’s half 0 and half 1.” Measuring such a qubit would result in either a 0 or 1 being observed, each with 50% probability. This transformation is a fundamental part of many quantum algorithms.

Mark Przepiora

CUMC 2009

Quantum circuits

A quantum computation is the path a qubit takes (time passing from left to right) along a series of “quantum gates” (each of which implements a single unitary transformation.) For example, the circuit the transformation HX .

X

implements

H

A circuit may also involve a measurement denoted by

, which measures that qubit in the computational basis NM (according to the laws given earlier.) For example, the circuit |0i H implements a random number generator.



NM

b

We will use this model later to discuss a quantum algorithm.

Mark Przepiora

CUMC 2009

Tensor products More generally, two qubits (which are physically separate) may be considered to be a single physical system via tensor products. Their combined state space is C4 , and a basis for it is given by {|00i , |01i , |10i , |11i} For example, a two-qubit system may be in the state |01i, i.e. the first qubit is a |0i and the second qubit is a |1i. Here it makes sense to talk about the state of each qubit individually. Or it could be in the state |00i + |11i which is an example of an entangled state. The state |01i may also be written |0i ⊗ |1i or |0i |1i or |0, 1i to emphasize that it comes from two separate physical systems. This product behaves exactly like you’d expect. (Distributivity, etc.) Mark Przepiora

CUMC 2009

Entanglement What about this state |00i + |11i? It no longer makes sense to talk about each qubit being in some state on its own. If we measure the two-qubit system all at once, by the laws of measurement we would expect to observe the results 00 and 11 with equal probability. But what if we measure a qubit individually? Remember they are separate physical systems, so we should be able to do this! We haven’t discussed the laws governing with this situation, but intuitively we can see that if we measure the first qubit to be a 0, then any subsequent measurement of the second qubit must also show that it is a 0. The qubits may be miles apart and this will still hold. (Why does this not allow for FTL information transfer?) Mark Przepiora

CUMC 2009

Controlled NOT So we can see that the two-qubit case is genuinely interesting! What kind of interesting two-qubit operators can we implement? “Controlled NOT” is a quantum analog of the XOR function, mapping |00i 7→ |00i , |01i 7→ |01i |10i 7→ |11i ,

|11i 7→ |10i

The above mapping can be restated as |a, bi 7→ |a, a ⊕ bi or “leave the first bit alone, and flip the second bit if the first bit is a 1.”

Mark Przepiora

CUMC 2009

Function oracles Quantum computation should be a generalization of classical computation, so it is reasonable to ask how we can compute a classical function f : {0, 1} → {0, 1} in the quantum world. Ideally, we’d like an operator that performs the following map: |a, ·i 7→ |a, f (a)i (In which the first qubit is the input, and we place the output in the second qubit.) However, it is clear that this mapping is not invertible. We can use a generalization of the CNOT operator instead. Let Uf denote the two-qubit operator that performs the following map: |a, bi 7→ |a, f (a) ⊕ bi An operator of this form is called the quantum oracle of f , and we can think of it as a black box. Mark Przepiora

CUMC 2009

Learning a boolean function

Forget about the quantum world, and say we have a black box that computes some unknown f : {0, 1} → {0, 1} classically. f could be one of four functions. Say we’d like to learn which it is, without being allowed to look inside the black box. How many queries are required? It’s easy to prove that we need two queries classically. In the quantum case, what if we’re given f as a bit oracle Uf ? Here, the answer is still two queries! So we see that quantum computation doesn’t allow us to speed up all computational tasks, only some.

Mark Przepiora

CUMC 2009

Learning a property So we can’t speed up the process of learning f exactly, but what if we simply want to determine the value f (0) ⊕ f (1), i.e. whether or not f is a constant function? Classically, it is again easy to convince yourself that two queries are required. However, only a single query is required to the quantum bit oracle! This is the Deutsch Algorithm, which is displayed below.

|0i H H b

NM

Uf |1i

H The result is b = f (0) ⊕ f (1).

Mark Przepiora

CUMC 2009

Quantum mythbusting I often read things like this: “A quantum computer could split into millions of identical copies, unleashing immense parallel computing power...” –New Scientist “Quantum machines may one day be capable of massively parallel computing, in which billions of calculations happen at once—a feat that will never be possible with silicon chips.” –Popular Science Why is it deceptive? The “billions of calculations” interfere with each other. Finding a quantum algorithm to determine even a simple property is hard! Can we really use a quantum computer to find a needle in a haystack? Mark Przepiora

CUMC 2009

Quantum search

Say we have n items, exactly one of which has an interesting property. How many items do we need to check before we find the needle? Classically, n − 1 in the worst case.

√ With a quantum computer, amazingly only n queries need to be made in the black box model. This is Grover’s algorithm. √ Just as importantly, n is the best we can do. This is the difference between 1,000,000 queries and 1,000 queries, but not the speedup promised by magazines.

Mark Przepiora

CUMC 2009

Addendum 1 - destroying information

Question: Doesn’t measurement destroy information? Answer: Not really, because of deferred measurement. Intermediate measurements can be moved to the very end of the computation, and the intermediate steps can be replaced by quantum operations. In other words, we can worry about measurements when the universe ends.

Mark Przepiora

CUMC 2009