� � 6.896 Quantum Complexity Theory September 18, 2008 Lecture 5 Lecturer: Scott Aaronson Last time we looked at what’s known about quantum computation as it relates to classical complexity classes. Today we talk somewhat more ‘concretely’ about the prospects for quantum computing. 1 Recap 1.1 BQP and the Rest We’ve informally shown the following complexity class inclusions: P ⊆ BP P ⊆ BQP ⊆ P P ⊆P �P ⊆ P SP ACE ⊆ EXP . We know P =� EXP , so at least one of the inclusions in the chain must be strict (and we suspect that all except the first one are strict), but we can’t even show P �= P SP ACE. This shows that separating BP P from BQP is at least as hard as the older, notorious open problem of P vs P SP ACE. 1.2 Operations on Subsystems, Tensor Products We’ve identified quantum transformations with unitary matrices acting on states given as vectors of complex amplitudes. As in classical circuit complexity, it is natural to restrict ourselves to applying ‘local’ transformations on our data. In the quantum case, we realize this as follows. Suppose we conceptualize our quantum state as having two ‘registers’ each taking multiple possible values (the partition we use may change from gate to gate, as in the circuit setting, depending which parts of the system we are operating upon). We write a quantum state as |ψ� = αi,j |i�|j�, i≤m,j≤n where the first register takes on values identified in a manner of our choosing with {1, . . . m}and the second takes values in {1, . . . n}. A unitary transformation T on the system is considered ‘local’ to the first register if there exists some m-by-m matrix U = (ui,k)i,k≤m such that T ’s action on basis vectors can be summarized as |i�|j� → ( uk,i|k�)|j�, k≤m for all i ≤ m, j ≤ n. We note that for T to be unitary, U must itself be unitary. It can be verified that if we write the amplitudes of a state vector |ψ� in a column in the order αT = (α1,1, α2,1, . . . αm,1, α1,2, . . . αm,2 . . . α1,n, . . . αm,n), then the resulting state after the trans-formation T is given by (U ⊗ In) α. Here the tensor product of an m-by-m matrix A = (ai,j ), with · an n-by-n matrix B, is an mn-by-mn matrix, defined in block form by (A ⊗ B) = (ai,kB)i,k≤m. 5-1Similarly, if T is local to the 2nd register, summarized by an n-by-n unitary V , the action of T on the global state α is to produce (Im ⊗ V )α. This representation allows us to reason about quantum computations with tools from linear algebra. For instance, it allows us to show that operations applied to separate subsystems commute; see Pset 1. 2 Prospects for Quantum Algorithmics 2.1 Subroutines In classical programming, we’re used to the idea of designing a small algorithm to solve a simple problem, then calling this algorithm repeatedly to help solve a bigger problem. In our analyses we like to rely only on the fact that this ‘subroutine’ gives the correct answer, and think of it otherwise as a ‘black box’. This is called modularity. The fact that this idea works correctly, without an unacceptable increase in running time, is expressed in the oracle result P P = P . It is less obvious that a similar idea works in the world of quantum circuits, but it does. A trick called ‘uncomputing’, described in the previous lecture, allows us to call subroutines as we’d like. This yields the complexity result BQP BQP = BQP , which gives us confidence that BQP is a ‘robust’ class of languages, and a world in which we can design algorithms in modular fashion. 2.2 Controlling Error In the early days of quantum computing (the ’80s, say), skeptics said quantum computation was ‘just’ another form of analog computation (a machine manipulating real-valued quantities), and subject to the same limitation: perturbative noise that could erase information and throw off a computation by successively accumulating errors. This criticism ignored or glossed over an important insight (explained in Bernstein-Vazirani ’93): unlike other types of transformations used in classical analog computers, quantum operations cannot amplify error except by directly introducing more of it! To see what is meant, suppose the ‘true’ input to a unitary U in a computation is the state ψ�, but noise has intruded so that we have instead some |ψ�� at an l2 distance at most � away from ||ψ�. Then, using linearity and unitarity, ||U|ψ�� − U|ψ�||2 = ||U (|ψ�� − |ψ�)||2 = |||ψ�� − |ψ�|| ≤ �. Thus if all unitaries in the computation perform as expected, an � error in the initial prepared state will yield an output state � away from correct. This implies that the acceptance probability will be close to what it should’ve been. Similarly, suppose that a unitary operation performs not exactly to our specifications, but is off by a ‘small’ amount. Let’s model this as follows: we want to apply U , but instead apply (U + �V ), where V is a matrix with induced norm at most 1, i.e. ||V x||2 ≤ ||x||2 for all x. In this case, inputting some value ψ� yields (U + �V ) ψ� = U ψ� + �V ψ�, a state whose l2 distance from our desired state is at most |||�V |ψ�||2 ≤ �||V |||2|||ψ�|| =|�. |Applying this idea repeatedly to an entire computation, Bernstein and Vazirani observe that the total error is (in an appropriate sense) at most the ‘sum’ of the errors in all preparation and gate components. Thus, if engineers can produce circuit elements with error 1 t , we expect to be able to faithfully execute computations on quantum circuits with size on the order of t. This idea was improved upon substantially. In a sequence of papers, work by Aharanov, Ben-Or, Knill, Laflange, Zurek and others culminated in the 1996 ‘Threshold Theorem’, which showed how 5-2to use ‘hierarchical coding’ ideas to build quantum circuits for arbitrary BQP computations, which would remain reliable even if each gate was subjected to a sufficiently small (but constant) rate of error. This result was analogous to (but more complicated than) earlier work by Von Neumann on fault-tolerant classical computation. There are certain requirements for the Threshold Theorem to be valid. These are: a