2003 - Quantum Computation Lecture 5

Duration: 00:45:59

Transcript

David Deutsch

00:01:14 - 00:06:08

An algorithm is a hardware independent specification of a computation by hardware independent I mean that it doesn’t specify what the computer should be made of only the effect that it should have on information that’s provided to it as input so that if you had access to any technology that allowed you to build a computer a universal computer you could translate the algorithm into a program for that computer which would perform the information processing that the algorithm specifies an algorithm is a way of performing a computational task like sorting a list or factorizing a number in general to specify a computational task you specify properties that the output information should have as a function of the input information so a computational task is a problem to which an algorithm is the solution the algorithm that I’m going to describe today is probably the simplest of all quantum algorithms so I’ll first describe the problem that it solves you’re given a black box containing a computer that’s dedicated to computing a particular function $F$ using reversible classical computation it operates coherently though because part of our task is going to be to use this black box as a component in a quantum computational network you’re not allowed to look inside the box all you’re allowed to do is feed qubits into it at one end and then retrieve them at the other end after a fixed time that’s independent of the input such a box is known as an oracle the idea of having an oracle in the specification of a computational task is a trick much beloved by complexity theorists both classical and quantum because it can greatly simplify the analysis of algorithms that’s because often looking inside the oracle doesn’t help you to perform the task yet it’s quite hard to prove that it doesn’t why that’s so often the case is quite a deep question it’s beyond the scope of these lectures but I’ll explain why it’s plausible in this case in a moment. Okay, the oracle in this problem computes a boolean function $F$ with one Boolean parameter, that is to say $F:\{-1,+1\}\to\{-1,+1\}$ since the oracle performs a reversible computation it can’t just do this $x\mapsto F(x)$ that wouldn’t be reversible the oracle must have an auxiliary input and output and when it computes $F$ what it must really be doing is something like this $(x,y)\mapsto(x,yF(x))$ that’s a reversible computation and if you want to use the oracle to compute $F(x)$ then you just have to make sure that $y$ is initialized to the value $+1$ now there are only four functions that map a single bit to a single bit the identity the not operation or delivering a constant output minus one or one

00:06:08 - 00:07:13

Internally the oracle may be computing something arbitrarily complex or rather one of two arbitrarily complex things depending on the input for instance it might be doing the traveling salesman problem or some other hard problem for one of two graphs depending on the input and then reporting some boolean property of the answer such as whether the shortest path has an even or odd number of steps but however complex the oracle is internally it will be computing one of these four functions that’s why it’s plausible that looking inside the oracle won’t in general help the oracle might contain a complicated network with a large number of qubits doing things in parallel so it might still be a lot faster to run it twice than to work out what it does once

00:07:13 - 00:09:24

Anyway a simple computational task given the oracle would be find out what $F$ is. Well, the only way to do that without looking inside is to run the oracle once for each possible input. The resulting four pairs of outputs tabulate $F$ . Is it possible to perform that task using only one run of the oracle? Well, we can prove that it isn’t. If you’re only allowed to run the oracle once, then whatever else you do you’ll have to pick a particular pair of values for its inputs $x$ and $y$ , and you’ll get output values $x$ , which you already knew, and $yF(x)$ . Only the second of those two outputs even depends on $F$ , so that can’t fully specify what $F$ is because $F$ can be one of four different functions. It turns out that that is true in the quantum case too. You can’t work out what $F$ is without invoking the oracle twice, so quantum computation doesn’t help with that task, which illustrates the general fact that quantum computation doesn’t speed up all computational tasks, only some of them. That’s one reason why quantum complexity theory is fundamentally different from classical complexity theory.

00:09:24 - 00:11:20

Anyway the problem that we are going to solve with a quantum algorithm is not to find out what $F$ is but to determine a property of $F$ , specifically whether $F(1)=F(-1)$ or not or more concisely the task is to compute the product $F(1)F(-1)$ without looking inside the oracle knowing the quantity $F(1)F(-1)$ certainly doesn’t tell you everything about $F$ ; it just tells you one bit of information about it which is half the information in the table of $F$ , so the proof I gave that the previous task requires two calls of the oracle doesn’t hold for this task so is there any way of computing the single boolean value $F(1)F(-1)$ using only one invocation of the oracle for the case of classical computation it’s again easy to prove that there is no way even though it’s only one bit of information this time because again there are only four possible ways of invoking the oracle in a classical computation and in all four the first output is again independent of $F$ and the second depends on only one of the two values $F(1)$ or $F(-1)$ never both so $F(1)F(-1)$ can never be deduced from it

00:11:20 - 00:12:47

Here’s a classical network that finds the answer using two instances of the oracle this is a controlled not gate which we’re using in its capacity as an exclusive OR gate alternatively we could find the answer by invoking one instance of the oracle twice doubling the running time like this the input bits both start at one they pass through the oracle making them $+1$ and $F(1)$ then they each go around a loop the first one passes through a not gate that flips it to minus one and the second goes in again as the auxiliary bit so the final output is $F(1)F(-1)$ strictly speaking this network runs forever so I’ll leave it as an exercise to modify it so that it delivers an output after exactly two oracle invocations

00:12:47 - 00:13:45

What the quantum algorithm does in short is that it uses only one instance of the oracle and it invokes it only once but it invokes it with a different input in different universes which means that the oracle performs different computations in different universes yielding potentially different outputs and the single qubit that holds those two outputs in different universes combines them in an interference phenomenon it exclusive-ORs them a bit like this except that the invocations of the oracle occur in different universes

00:13:45 - 00:16:38

To describe the quantum algorithm that does that as with most quantum algorithms it’s simplest to work in the Schrödinger picture where as you’ll recall the observables are constant matrices and the state changes with time in this problem we can make the further simplification of considering only pure states remember that a quantum system is said to be in a pure state when its density matrix takes the form $|\psi\rangle\langle\psi|$ for some $|\psi\rangle$ psi is then said to be the state vector of the system and we often refer to the state vector as just the state of such a system the effect of a quantum gate operating between times $t$ and $t+1$ on an arbitrary pure state is $\psi(t+1)=U\psi(t)$ where $U$ is a constant unitary matrix characteristic of the gate like the reversible classical algorithms for performing this task this algorithm involves two qubits that’s not counting whatever qubits might be inside the oracle combining two quantum systems in the Schrödinger picture is much the same as doing it in the Heisenberg picture any tensor product of observables one from each system is an observable of the combined system and if both systems are in pure states say $|\psi\rangle$ and $|\phi\rangle$ then the combined system is in a pure state too and its state vector is the tensor product $|\psi\rangle|\phi\rangle$ we write the tensor product of kets without any explicit multiplication symbol like this and that’s a ket of the combined system consider a system of two qubits then in an eigenstate of both their $Z$ observables $Z_1$ and $Z_2$ the four such eigenstates $|a\rangle|b\rangle$ where a and b range over the eigenvalues plus and minus one form an orthonormal basis in the four-dimensional vector space of all pure states of the combined system

00:16:38 - 00:23:51

The space of all pure states that a system could be in is technically a Hilbert space basically that’s just a vector space with a norm and we usually refer to it as the Hilbert space of the given system strictly speaking pure states are always unit vectors that follows from the definition of a pure state that I’ve given because the trace of the density matrix has to be one but it’s no big deal some people like to work with unnormalized vectors and they insert a normalization factor in this formula so unnormalized kets are usually called states too and eigenvectors of observables are called eigenstates the normalized pure states lie on a unit sphere in the Hilbert space and all the non-zero states along any straight line through the origin represent the same physical state when working with pure states we usually pick a fixed basis in the system’s Hilbert space and express the evolving state of the system as a linear combination with time varying coefficients time varying complex coefficients of those basis states a linear combination of states is called a superposition in quantum computation we call whatever basis we choose for doing that the computation basis we can choose any basis as the computation basis but usually some choices are more convenient than others usually the most convenient one is determined by the classical operations that form part of the computation I’ll explain in a classical computer the state of the computation at each step is specified by the sharp values of a set of observables the computational variables so when a quantum computer simulates a classical computer there’s a set of observables which are sharp at the beginning and end of every step and that sharpness is maintained because as I mentioned last time the elementary classical operations in a quantum computer have the property that a particular set of observables evolve autonomously we usually use a notation in which these are the Z observables of the qubits so that means that during periods when our quantum computer is executing only classical operations the Z observables of the qubits are distinguished by being the observables on which those gates perform classical operations note that in general the Z observables will not be sharp during those classical operations because they need not have been sharp when the classical part of the computation began some earlier quantum operations will in general have made them unsharp nevertheless the Z observables form an autonomous evolving system under classical operations and that’s why the basis of eigenstates of those Z observables is often the most convenient one to use as the computation basis I’ll explain classical reversible computations starting in a computation basis state proceed from computation basis state to computation basis state for this and other reasons the dynamics of simple quantum gates are particularly easy to represent in the Schrödinger picture it’s enough to specify the behavior of each member of a set of basis states such as the computation basis for instance the NOT gate is a single qubit gate a single qubit has a two-dimensional Hilbert space so we can completely specify the behavior of the NOT gate by giving its effect on just two states like this $|A\rangle\mapsto|-A\rangle$ where $A$ is $+1$ or $-1$ and these are eigenstates of the qubit’s $Z$ observable this statement means that if the state at time zero is the eigenvalue- $A$ eigenstate of $Z$ then the state at time one after the gate has acted is the eigenvalue- $-A$ eigenstate compare that with the description of the NOT gate in the Heisenberg picture and you begin to see why the Schrödinger picture is preferred for most calculations in the quantum theory of computation another important single qubit gate that I haven’t mentioned before and which is used in the algorithm I’m going to describe is the so-called Hadamard gate named after the mathematician Jacques Hadamard for historical reasons it has this effect $|1\rangle\mapsto \frac{1}{\sqrt{2}}(|1\rangle+|-1\rangle)$ and $|-1\rangle\mapsto \frac{1}{\sqrt{2}}(|1\rangle-|-1\rangle)$ the Hadamard operation is like the NOT operation a square root of the unit operation it’s its own inverse but unlike NOT it doesn’t have a classical analog by the way the square root of two factor is just there to normalize the states

00:23:51 - 00:24:50

Now here’s the definition of the controlled NOT gate in the Schrödinger picture look how simple it is it evolves a system of two qubits in the eigenstate $|x,y\rangle$ of the observables $Z_1$ and $Z_2$ into the state $|x,xy\rangle$ the $|x,y\rangle$ is just another way of writing the tensor product $|x\rangle|y\rangle$ and again compare this with the Heisenberg picture definition of the controlled NOT gate the operation of the oracle is as follows $|x,y\rangle\mapsto |x,yF(x)\rangle$

00:24:50 - 00:29:20

Now for the algorithm our two qubits start in the state where they’re both sharp with the value $+1$ we could think of that as the blank state of our two qubit computer memory by the way when analyzing algorithms in general the algorithm should always start with a state where all the qubits that are not given as part of the task are blank that way your analysis will automatically account for the resources required for any other initialization that you might want to do the quantum network that solves our problem contains a NOT gate three Hadamard gates and the oracle at time 0 the beginning of the computation the state of each qubit is the eigenvalue- $+1$ eigenstate of its $Z$ observable so the overall state at time 0 is the tensor product of those which we can write $|1,1\rangle$ then the second qubit encounters a NOT gate which flips its $Z$ observable to $-1$ next both qubits pass through Hadamard gates and we can just substitute from the definition of the Hadamard gate what the state will be at time 2: $\frac12(|1\rangle+|-1\rangle)(|1\rangle-|-1\rangle)$ then the oracle acts on the qubits once but neither of the $Z$ observables in the input is now sharp so we’re presenting the oracle with four different inputs in different universes next well the oracle will in general take a long time to run but the running time is a constant independent of the input and we’re not interested in what it is for the moment so let’s just call the time when it’s complete time 3 and again we can fill in what $\psi(3)$ will be at this point the computation isn’t quite finished yet we still have that final Hadamard gate to go but let’s just look at this state suppose that $F(1)=F(-1)$ so we can call them both $f$ then the state at time 3 will take this form which factorizes into a tensor product so we see that the qubits are still individually in pure states and the first qubit is in a state proportional to $|1\rangle+|-1\rangle$ okay, that’s if $F(1)=F(-1)$ if they’re unequal then $F(1)=-F(-1)$ which we can call $f$ again and again the qubits are each in a pure state this time qubit 1 is in a state proportional to $|1\rangle-|-1\rangle$

00:29:20 - 00:31:11

If we can distinguish those two states of qubit 1 we shall have determined whether $F(1)$ and $F(-1)$ are the same or different and that’s just what the final Hadamard gate does because Hadamard acting on $\frac{1}{\sqrt{2}}(|1\rangle+|-1\rangle)$ is $|1\rangle$ and Hadamard acting on $\frac{1}{\sqrt{2}}(|1\rangle-|-1\rangle)$ is $|-1\rangle$ and we can summarize that as at time 4 the state is proportional to $|F(1)F(-1)\rangle$ times some state of qubit number 2 so the $Z$ observable of qubit 1 now contains information that depends logically on the outcomes of the computations of both $F(1)$ and $F(-1)$ and it’s sharp although those computations were performed in different universes between times 2 and 3 the interference phenomenon effected by the Hadamard gate between times 3 and 4 combined those values and caused the answer to appear in qubit 1 in all the universes $Z_1$ is sharp at time 4

00:31:11 - 00:31:51

The problem solved by this algorithm has come to be known as the Deutsch problem, and the algorithm I’ve just described is known as the Deutsch algorithm. I should say that that gives me slightly too much credit. The algorithm that I originally proposed was somewhat less elegant and significantly less powerful than this one. I refer you to the worked examples to see in what way it was less powerful. The version I’ve shown you was published in 1998 by Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca.

00:31:51 - 00:34:56

The way this algorithm works is typical of how quantum algorithms work in general at least typical of those that have been discovered so far namely we start out with the state of the system being an element of the computational basis that is to say we prepare the Z observables with particular initial values and the first thing we do is unsharpen those observables so that they contain many possible values in our case all four possible values that unsharpening is a quantum operation then we perform a classical reversible computation using coherent quantum components in our case that’s the computation of $F$ by the oracle but this computation is being done with different inputs in different universes giving different outputs too and then these outputs are somehow combined using another quantum operation which gives a sharp answer in this case and more generally as sharp as possible an answer as the output and that means that these computations are interference phenomena observables which are sharp become unsharp and then sharp again an algorithm which performs multiple classical computations on unsharp inputs and then combines them is said to be using quantum parallelism that’s because as I’ve shown the process is reminiscent of classical parallel computation with the difference that you don’t need a second copy of the oracle you use the parallel universe counterparts of the one you’re given. Okay, so by using this quantum algorithm we’ve gained a factor of two in speed but the real significance of the existence of this algorithm is not its speed it’s the fact of being able to manage with just one evaluation of $F$ to obtain information that depends logically on both values it’s the fact that during that function evaluation something is going on that cannot be analyzed as a sequence of states in which each computational observable has a single value. This is the characteristic of this new mode of information processing which is not the implementation of any classical algorithm and performs a task that no classical algorithm can perform

00:34:56 - 00:35:41

The ability to perform this particular task is unlikely to have any practical application though well in some very contrived circumstances it just might say you have a time limit by which you have to perform a very important computation that consists of evaluating $F(1)F(-1)$ for some complex algorithm $F$ as I said the real significance is theoretical but next time I’ll describe an amazing quantum algorithm again using quantum parallelism that is both theoretically interesting and likely to be useful in a wide range of practical applications

Markdown