��6.896 Quantum Complexity Theory November 6, 2008 Lecture Lecturer: Scott Aaronson Scribe: Joshua Horowitz On Election Day, November 4, 2008, the people voted and their decision was clear: Prof. Aaronson would talk about quantum computing with closed time-like curves. But before we move into strange physics with even stranger complexity-theoretic implications, we need to fill in a more basic gap in our discussion so far – quantum space-complexity classes. 1 BQPSPACE Recall that PSPACE is the class of all decision problems which can be solved by some classical Turing machine, whose tape-length is bounded by some polynomial of the input-length. To make BQPSPACE, we quantize this in the most straightforward way possible. That is, we let BQPSPACE be the class of all decision problems which can be solved with a bounded rate of error (the B) by some quantum Turing machine (the Q), whose tape-length is bounded by some polynomial of the input-length (the PSPACE). As we’ve seen before, allowing quantum computers to simulate classical ones gives the relationship PSPACE ⊆ BQPSPACE. If we believe that BQP is larger than P, we might suspect by analogy that BQPSPACE is larger than PSPACE. But it turns out that the analogy isn’t such a great one, since space and time seem to work in very different ways. As an example of the failure of the time-space analogy, take PSPACE vs. NPSPACE. We certainly believe that nondeterminism gives classical machines exponential time speed-ups for some problems in NP, making P = NP at least in our minds. But Savitch’s theorem demonstrates that the situation is different in the space-domain: PSPACE = NPSPACE. That is, nondeterministic polyspace algorithms can be simulated in deterministic polyspace. It turns out even more than this is true. Ladner proved in 1989 that PSPACE = PPSPACE, establishing PSPACE as a truly solid rock of a class. This is the result we need to identify BQPSPACE. Using the same technique we used to prove BQP ⊆ PP, we can prove that BQPSPACE ⊆ PPSPACE, and then using PPSPACE = PSPACE ⊆BQPSPACE we have BQPSPACE = PSPACE. 2 Talking to Physicists Some physicists have been known to react to the stark difference between time- and space-complexity with confusion and incredulity. “How can PTIME =� PSPACE,” they ask, “if time and space are equivalent, as suggested by Einstein’s theory of relativity?” The basic answer to this question is that time and space are in fact not perfectly equivalent. Einstein’s theory relates them in a non-trivial way, but distinctions remain. At the very least, they correspond to opposite signs in the metric tensor. And, for whatever reason, though objects can move about space at will, movem ent through time is constrained to the “forward” direction. Thus, our inability to travel back in time is in a s ense the reason why (we b elieve) P = PSPACE! 18-1 193 Time Travel But are we really so sure that time travel is impossible? Special relativity says that it takes infinite energy to accelerate faster than the speed of light and into the past. But general relativity extends our concept of space-time, allowing it to take the form of w hatever sort of topologically crazy 4D manifold we want (more or less). Is it possible that such a manifold could have loops of space-time which extended forwards in time but ended up bringing us back to where we started? That is, can the universe have closed time-like curves (CTCs)? In an amusing coincidence for a class on complexity theory, one of the first people to investigate this question was Kurt G¨odel, who in 1949 constructed a solution to the general-relativistic field equations which included CTCs, and gave it to Einstein as a birthday gift. Like all good birthday gifts, this left Einstein somewhat troubled. The solution was fairly exotic, howe ver, involving such strange constructions as infinitely long massive cylinders. The problem came up again in the 1980s, when Carl Sagan asked his physicist friend Kip Thorne if there was a scientific basis for the time travel in his novel-in-progress Contact. Though Thorne initially dismisse d the possibility, he later began to look into whether wormholes could be used for time travel. The problem turned out to be surprisingly difficult and subtle. The conclusion reached by Thorne and his collaborators was that such wormholes were theoretically possible, though they would require the presence of negative energy densities. Given that such negative energy densities have been known to arise in quantum situations such as the Casimir effect, Thorne’s work e ffe ctively linked the question of wormhole time-travel to that of quantum gravity (the “P vs. NP” of theoretical physics). Of course, it is not the place of computer scientists to say whether something actually exists or not. They need only ask “what if?”. So we will suppose that we have computers capable of sending information back in time, and see where that takes us. 4 Computing with CTCs: The Na¨ıve Proposal The first scheme many people think of for speeding up computations with CTCs is very simple: 1. Perform your computation however you like. 2. Send the answer back in time to whenever you wanted it. At first glance, this sounds pretty good. It makes every computation constant-time! Conceivably, even negative-time. . . But there are problems with this scheme, which is fortunate for anyone hoping time-travel computation would be anything other than c ompletely trivial. • It encourages “massive deficit spending”: Life may be easy for you, now that you’ve received the answer to your NP-complete question in no time at all, but the accounting of time as O(0) ignores the possible millennia of computation your computer still has to do to get that answer. Keeping a computer running that long could be extraordinarily costly or even impossible if the run-time exceeds the lifetime of the universe itself. • Complexity theory is all about knowing exactly how much of each computational resource you need in order to solve a problem. However, in the above treatment, we are completely 18-2� � � � � � 5 ignoring the CTC as a computational resource. If we accounted for its length, we would soon discover just how blithely