Closed timelike curves make quantum and classical computing equivalent

Scott Aaronson, John Watrous

Abstract

While closed timelike curves (CTCs) are not known to exist, studying their consequences has led to non-trivial insights into general relativity, quantum information and other areas. In this paper, we show that, if CTCs existed, quantum computers would be no more powerful than classical computers: both would have the (extremely large) power of the complexity class polynomial space (Embedded Image), consisting of all problems solvable by a conventional computer using a polynomial amount of memory. This solves an open problem proposed by one of us in 2005, and gives an essentially complete understanding of computational complexity in the presence of CTCs. Following the work of Deutsch, we treat a CTC as simply a region of spacetime where a ‘causal consistency’ condition is imposed, meaning that nature has to produce a (probabilistic or quantum) fixed point of some evolution operator. Our conclusion is then a consequence of the following theorem: given any quantum circuit (not necessarily unitary), a fixed point of the circuit can be (implicitly) computed in Embedded Image. This theorem might have independent applications in quantum information.

Keywords:

1. Introduction

The possibility of closed timelike curves (CTCs) within general relativity and quantum gravity theories has been studied for almost a century (van Stockum 1937; Gödel 1949; Morris et al. 1988). A different line of research has sought to understand the implications of CTCs, supposing they existed, for quantum mechanics, computation and information (Deutsch 1991; Brun 2003; Bacon 2004).

In this paper we contribute to the latter topic, by giving the first complete characterization of the computational power of CTCs. We argue that if CTCs containing polynomially many bits could be created and maintained then both classical and quantum computers would have exactly the power of the complexity class polynomial space (Embedded Image), which consists of all problems solvable on a classical computer with a polynomial amount of memory. To put it differently, CTCs would make polynomial time equivalent to Embedded Image as computational resources, and would also make quantum and classical computers equivalent to each other in their computational power. Our results treat CTCs using the ‘causal consistency’ framework of Deutsch (1991), together with the assumption that a CTC involving polynomially many bits can be maintained using polynomial resources.

It will not be hard to show that classical computers with CTCs can simulate Embedded Image and be simulated in it (though as far as we know, this result is new). The main difficulty will be to show that quantum computers with CTCs can be simulated in Embedded Image. To prove this, we need to give an algorithm for (implicitly) computing fixed points of superoperators in Embedded Image. Our algorithm relies on fast parallel algorithms for linear algebra due to Borodin et al. (1983), and might be of independent interest.

The paper is organized as follows. In §2, we explain needed background about Deutsch's causal consistency framework and computational complexity, and review previous work by Brun (2003), Bacon (2004) and Aaronson (2005). In §3, we show that classical computers with CTCs have exactly the power of Embedded Image. In §4, we extend the analysis of §3 to show that quantum computers with CTCs have exactly the power of Embedded Image. In that section, we make the simplifying assumption that all quantum gates can be applied perfectly and that amplitudes are rational. In §5, we consider what happens when gates are subject to finite error, and extend previous work of Bacon (2004) to show that quantum computers with CTCs can solve Embedded Image problems in a ‘fault-tolerant’ way. We conclude in §6 with some general remarks and open problems.

2. Background

(a) Causal consistency

It was once believed that CTCs would lead inevitably to logical inconsistencies such as the grandfather paradox. But in a ground-breaking paper, Deutsch (1991) argued that this intuition fails, provided the physics of the CTC is quantum mechanical. While Deutsch's resolution of the grandfather paradox is not universally accepted, we will adopt it throughout in this paper, since it leads in a particularly clear and elegant way to a model of computation. Deutsch's insight was that a CTC should simply be regarded as a region of spacetime where nature enforces a requirement of causal consistency: in other words, that the evolution operator within that region should map the state of the initial hypersurface to itself. Given the evolution operator f, nature's ‘task’ is thus to find a fixed point of f, i.e. an input x such that f(x)=x. Of course, not every deterministic evolution operator f has a fixed point: that is just one way of stating the grandfather paradox. On the other hand, it is a basic linear algebra fact that every quantum operation Φ has a fixed point, i.e. a density matrix ρ such that Φ(ρ)=ρ. For any Φ such a ρ can then be used to produce a CTC evolution that satisfies the causal consistency requirement. So, for example, a consistent resolution of the grandfather paradox is that you are born with 1/2 probability, and if you are born you go back in time to kill your grandfather, therefore you are born with 1/2 probability, etc.

Note that Deutsch's resolution works just as well in classical probabilistic theories as in quantum-mechanical ones. For just as every quantum operation has a fixed point, so every Markov chain has a stationary distribution. What matters is simply that the state space and the set of transformations are such that fixed points exist.

It might be thought mysterious that nature ‘finds’ a fixed point ρ of Φ: how, one might ask, does nature do this? Does nature not have to find ρ before the CTC computation starts, so that, in some sense, running the computation is not even necessary? While these issues are admittedly mysterious, to us they are not more mysterious than the starting assumption that CTCs exist! One should keep in mind that any account of a universe with CTCs is going to be strange, so perhaps the most one can hope for is that the account should be mathematically clear and consistent. And at a purely mathematical level, Deutsch's causal consistency account of CTCs is the clearest we have seen.

Although CTCs need not lead to inconsistencies, Deutsch pointed out that they would have striking consequences for the theory of computing. As an example, CTCs could be exploited to solve non-deterministic polynomial time (Embedded Image)-complete and other ‘intractable’ computational problems using only polynomial resources. To see this, suppose some integers x∈{0, 1, …, 2n−1} are ‘solutions’ and others are not, and that our goal is to find a solution in time polynomial in n, assuming solutions exist and can be recognized efficiently. Then we could build a machine M that applied the following transformation to its input x: if x is a solution then M(x)=x, while if x is not a solution then M(x)=(x+1)mod 2n. Now, suppose we use a CTC to feed M its own output as input. Then it is not hard to see that the only way for the evolution to satisfy causal consistency is for M to input, and output, a solution.

In this way, an exponentially hard computational problem could get solved without exponential effort ever being invested to solve it, merely because that is the only way to satisfy causal consistency. A rough analogy would be Shakespeare's plays being written by someone from the present going back in time and dictating the plays to him.

It is sometimes said that, if CTCs existed, one could obviously do computations of unlimited length in an instant, by simply computing the answer, then sending it back in time to before one started. However, this proposal does not work for two reasons. First, it ignores the grandfather paradox: what happens if, on receiving the output, one goes back in time and changes the input? Second, it is perhaps unclear why a computation lasting 101000 years should be considered ‘feasible’, merely because we are able to obtain the solution before performing the computation. It seems that an honest accounting should require the computations performed inside the CTC to be efficient (say, polynomial time), with any computational speedup coming from the requirement of causal consistency.

(b) Complexity theory

For background on classical computational complexity theory, see for example Arora & Barak (in press); for a recent survey of quantum complexity theory, see Watrous (2008). Here, we briefly describe the main complexity classes that we will consider. Embedded Image is the class of decision problems that are solvable by a classical computer, using an amount of memory that is bounded by a polynomial function of the size of the input n (but possibly an exponential amount of time). An example of such a problem is, given a configuration of an n×n Go board, to decide whether White has a winning strategy using n2 or fewer moves. Embedded Image is the class of decision problems for which every ‘yes’ answer has a polynomial-time checkable, polynomial-size proof or witness. Embedded Image-complete problems are, loosely speaking, the ‘hardest’ problems in Embedded Image, i.e. those Embedded Image problems to which all other Embedded Image problems can be efficiently reduced. An example is, given a graph, to decide whether it has a Hamiltonian cycle (i.e. a cycle that visits each vertex exactly once). Embedded Image contains Embedded Image (thus, in particular, the Embedded Image-complete problems)—since, in Embedded Image, one can simply loop over all possible witnesses and see if any of them are correct. However, Embedded Image is believed to be considerably larger than Embedded Image. So, in saying that computers with CTCs can efficiently solve Embedded Image problems, we are saying something stronger than just that they can solve Embedded Image-complete problems.

Our main result is that computers with polynomial-size CTCs have precisely the power of Embedded Image, and that this is true whether the computers are classical or quantum. Previously, Watrous (1999) showed that bounded-error quantum polynomial space (Embedded Image) is equal to Embedded Image, i.e. any problem solvable by a quantum computer with polynomial memory is also solvable by a classical computer with polynomial memory. (By contrast, quantum computers are conjectured to offer an exponential improvement over classical computers in time.) Here, we show that quantum computers are polynomially equivalent to classical computers in the CTC setting as well.

Our results will allow CTCs that contain a polynomial number of bits or qubits, as well as a polynomial number of gate operations. Given our ignorance of the physics of CTCs, it might be wondered whether these choices are justified. Our response is that the choices arise from treating CTCs the same way one would treat any other resource in computational complexity theory: for a ‘polynomial price’ one gets a polynomial amount of the resource (e.g. bits or qubits). Still, it is interesting to consider the effects of other choices, and we discuss some possibilities in §6.

(c) Related work

Besides Deutsch's (1991) paper, we know of three other works directly relevant to computational complexity in the presence of CTCs. First, Brun (2003) showed that CTCs would allow the efficient solution of Embedded Image-complete problems.1

Second, Bacon (2004) showed that Embedded Image-complete problems can be solved with polynomial resources, even using CTCs that are only ‘one-bit wide’ (i.e. able to transmit a single qubit or probabilistic classical bit back in time).2 Bacon also showed that, using his approach, one can solve not only Embedded Image problems but even #Embedded Image problems, which involve counting solutions rather than just finding one. (The class #Embedded Image—or more formally its decision version Embedded Image—is a subclass of Embedded Image, with the containment believed to be strict.) Finally, Bacon showed that techniques from the theory of quantum fault tolerance could be used to make certain CTC computations, including those used to solve #Embedded Image problems, robust to small errors.

Third, as part of a survey on ‘Embedded Image-complete problems and physical reality’ Aaronson (2005), Aaronson sketched the definitions of Embedded ImageCTC and Embedded ImageCTC (classical and quantum polynomial time with CTCs) that we adopt in this paper. He also sketched a proof that Embedded Image=Embedded ImageCTCEmbedded ImageCTCEmbedded Image. That is, classical computers with polynomial-size CTCs have exactly the power of Embedded Image, while quantum computers with polynomial-size CTCs have at least the power of Embedded Image and at most the power of classical exponential time. The key problem that Aaronson left open was to pin down the power of quantum computers with CTCs precisely. This is the problem we solve in this paper.

3. The classical case

To state our results, it is crucial to have a formal model of computation in the presence of CTCs.

We define a deterministic CTC algorithm Embedded Image to be a deterministic polynomial-time algorithm that takes as input a string x=∈{0,1}n, and that produces as output a Boolean circuit C=Cx, consisting of AND, OR and NOT gates. The circuit C acts on bits in two registers: a CTC register Embedded ImageCTC and a causality-respecting register Embedded ImageCR (figure 1). The registers Embedded ImageCTC and Embedded ImageCR consist of p(n) and q(n) bits, respectively, for some polynomials p and q depending on Embedded Image. Thus, C can be seen as a Boolean function C:{0,1}p(n)+q(n)→{0,1}p(n)+q(n), which maps an ordered pair 〈y,n〉∈Embedded ImageCTC×Embedded ImageCR to another ordered pair C(〈y,n〉).

Figure 1

Diagram of a classical CTC computer. A circuit C performs a polynomial-time computation involving ‘CTC bits’ (the register Embedded ImageCTC) as well as ‘causality-respecting bits’ (the register Embedded ImageCR). Nature must then find a probability distribution over Embedded ImageCTC which satisfies Deutsch's causal consistency equation. The final answer is read out from Embedded ImageCR.

For convenience, we assume that the causality-respecting register Embedded ImageCR is initialized to 0q(n). The CTC register, on the other hand, must be initialized to some probability distribution over p(n)-bit strings that will ensure causal consistency. More formally, let Embedded Image be a probability distribution over Embedded ImageCTC×Embedded ImageCR and let C(Embedded Image) be the distribution over Embedded ImageCTC×Embedded ImageCR induced by drawing a sample from Embedded Image and then applying C to it. Also, let [.]CTC be an operation that discards the causality-respecting register (i.e. marginalizes it out), leaving only the CTC register. Then we need the initial probability distribution Embedded Image over Embedded ImageCTC×Embedded ImageCR to satisfy the following two conditions:

  1. Embedded Image has support only on pairs of the form 〈y,0q(n)〉 and

  2. Embedded Image satisfies the causal consistency equation [Embedded Image]CTC=[C(Embedded Image)]CTC.

We claim that such a Embedded Image always exists. This is easy to prove: let C′(y)≔[C(〈y,0q(n)〉)]CTC be the induced circuit that acts only on the CTC register. Then it suffices to find a distribution Embedded Image′ over Embedded ImageCTC such that C′(Embedded Image′)=Embedded Image′. To find such a Embedded Image′, we consider the directed graph representing the function C′≔{0,1}p(n)→{0,1}p(n), find a cycle in that graph (which must exist, since the graph is finite) and let Embedded Image′ be the uniform distribution over points in the cycle. Finally, we set Embedded Image=〈Embedded Image′,0q(n)〉.

We are now ready to define the complexity class Embedded ImageCTC of problems solvable using classical computers with CTCs. We say that a CTC algorithm Embedded Image accepts the input x if, for every distribution Embedded Image satisfying conditions (i) and (ii) above, C(Embedded Image) has support only on pairs of the form 〈y,z1〉; i.e. such that the last bit of the causality-respecting register is a 1. (Recall that C=Cx depends on the input x.) Likewise, we say Embedded Image rejects x if, for every Embedded Image satisfying (i) and (ii), C(Embedded Image) has support only on pairs of the form 〈y,z0〉. (Of course, it is possible that C(Embedded Image) has support on both kinds of pairs, in which case Embedded Image neither accepts nor rejects.) We say Embedded Image decides the language L⊆{0,1}* if Embedded Image accepts every input xL, and rejects every input x∉L. Then Embedded ImageCTC is the class of all languages L that are decided by some deterministic CTC algorithm.

Let us make a few remarks about the definition. First, the requirement that some polynomial-time algorithm Embedded Image output the circuit C=Cx is intended to prevent hard-to-compute information from being hard-wired into the circuit. This requirement is standard in complexity theory; it is also used, for example, in the definition of Embedded Image. Second, our definition required C to succeed with certainty, and did not allow C to introduce its own randomness, besides that produced by the causal consistency condition. We could relax these requirements to obtain the complexity class Embedded ImageCTC, or bounded-error probabilistic polynomial time with access to a CTC. However, it will turn out that Embedded ImageCTC=Embedded ImageCTC=Embedded Image anyway.

(a) Results

We now prove Embedded ImageCTC=Embedded Image.

Embedded ImageCTCEmbedded Image.

Let C be a polynomial-size circuit that maps Embedded ImageCTC×Embedded ImageCR to itself, as in the definition of Embedded ImageCTC. Then our Embedded Image simulation algorithm is as follows. First, let C′=(y)≔[C(〈y,0q(n)〉)]CTC be the induced circuit that acts only on Embedded ImageCTC. Then given a string y∈{0,1}p(n), say y is cyclic if C(k)(y)=y for some positive integer k. In other words, y is cyclic if repeated application of C′ takes us from y back to itself. Clearly, every C′ has at least one cyclic string. Furthermore, it is clear from the definition of Embedded ImageCTC that if xL then every cyclic string must lead to an output of 1 in the last bit of Embedded ImageCR, while if x∉L then every cyclic string must lead to an output of 0. Hence, the problem essentially reduces to finding a cyclic string.

But it is easy to find a cyclic string in Embedded Image: the string y*C(2p(n))(y) will be cyclic for any y. The one remaining step is to compute C(〈y*,0q(n)〉), and then output the last bit of Embedded ImageCR. ▪

We are indebted to Lance Fortnow for the following lemma.

Embedded ImageEmbedded ImageCTC.

For some polynomial p, let M be a p(n)-space Turing machine (i.e. every configuration of M takes p(n) bits to describe). We can assume without loss of generality that M includes a ‘clock’, which is incremented at every time step, and which causes M to accept automatically once it reaches its maximum value. This prevents M from ever going into an infinite loop, regardless of its starting configuration.

Let m1, …, mT be the successive configurations of M when run on an input x∈{0,1}n. Then our task is to decide, using a CTC computer, whether mT is an accepting or a rejecting configuration.

Our CTC algorithm Embedded Image will produce a circuit C that acts on two registers: a (p(n)+1)-bit CTC register Embedded ImageCTC, and a one-bit causality-respecting register Embedded ImageCR. For simplicity, we start by describing the induced circuit C′ that acts on Embedded ImageCTC. Given a configuration m of M, let S(m) be the successor of m, i.e. the configuration obtained from m by incrementing the clock and performing one step of computation. Then the circuit C′ acts as follows, on ordered pairs 〈m,b〉 consisting of a configuration m and a ‘control bit’ b.

  1. If m is neither an accepting nor a rejecting configuration, then C′ (〈m,b〉)=〈S(m),b〉.

  2. If m is an accepting configuration, then C′(〈m,b〉)=〈m1,1〉.

  3. If m is a rejecting configuration, then C′(〈m,b〉)=〈m1,0〉.

In other words, if m produces an output then C′ sets the control bit to that output and goes back to the starting configuration; otherwise, C′ increments the computation and leaves the control bit unchanged (figure 2).

Figure 2

To simulate a Embedded Image machine with a CTC, we perform a computation for which the only causally consistent evolution is a loop over all configurations of the machine, with a control bit b set to its final value (in this example, b=1).

Now consider the graph of the function C′≔{0,1}p(n+1)→{0,1}p(n+1). It is not hard to see that the only cycle in this graph is (〈m1,1〉,…,〈mT,1〉) if mT accepts, or (〈m1,0〉,  …,  〈mT,0〉) if mT rejects. Indeed, this is true even if there are configurations that are not reachable from 〈m1,1〉 or 〈m1,0〉, since those configurations will ultimately lead back to either 〈m1,1〉 or 〈m1,0〉 and therefore not produce new cycles. In other words, the only cycle is a loop over m1,  …,  mT, with the control bit b set to M's final output. Therefore, the only probability distribution Embedded Image′ over {0,1}p(n)+1 that is stationary, in the sense that C′(Embedded Image′)=Embedded Image′, is the uniform distribution over 〈m1,b〉, …, 〈mT,b〉 where b is M's final output.

Finally, the full circuit C simply applies C′ to Embedded ImageCTC, and then copies the control bit into the causality-respecting register. ▪

4. The quantum case

Let G be a universal set of quantum gates, with amplitudes having rational real and imaginary parts. Then a quantum CTC algorithm Embedded Image is a deterministic polynomial-time algorithm that takes as input a string x∈{0,1}n, and which produces as output an encoding of a unitary quantum circuit Q=Qx with gates from G.

The circuit Q acts on two quantum registers: a q(n)-qubit CTC register Embedded ImageCTC and an r(n)-qubit causality-respecting register Embedded ImageCR. The causality-respecting register Embedded ImageCR is initialized to |0〉r(n) while the CTC register must be initialized to some q(n)-qubit mixed state ρ that will ensure causal consistency. More formally, we require thatEmbedded Image(4.1)which is equivalent to ρ being a fixed point of the quantum operation defined asEmbedded ImageDeutsch (1991) proved that every such quantum operation has a fixed point, and an alternative proof of this fact follows from our results in §4c below.

We can now define the complexity class Embedded ImageCTC of problems solvable using quantum computers with CTCs. Let Embedded Image be a measurement of the last qubit of Embedded ImageCR in the computational basis. Then we say the algorithm Embedded Image accepts x if, for every mixed state ρ satisfying equation (4.1) above, Embedded Image(Q(ρ⊗(|0〉〈0|)r(n))Q) results in output 1 with a probability of at least 2/3. We say Embedded Image rejects x if, for every ρ satisfying the equation, Embedded Image(Q(ρ⊗(|0〉〈0|)r(n))Q) results in output 1 with a probability of at most 1/3. We say Embedded Image decides the language L⊆{0,1}* if Embedded Image accepts every input xL, and rejects every input x∉L. Then Embedded ImageCTC is the class of all languages L that are decided by some quantum CTC algorithm.

In what follows, we develop some needed background, and then prove the main result that Embedded ImageCTCEmbedded Image.

(a) Matrix representation of superoperators

We will make use of a simple way of representing quantum operations as matrices. This representation begins with a representation of density matrices as vectors by the linear function defined on standard basis states asEmbedded ImageIf ρ is an N×N density matrix, then vec(ρ) is the N2-dimensional column vector obtained by stacking the rows of ρ on top of one another. For example,Embedded Image

Now, suppose that Φ is a given quantum operation acting on an N-dimensional system, meaning that Φ:Embedded ImageN×NEmbedded ImageN×N is linear, completely positive and trace preserving. Given that the effect of Φ on density matrices is linear, there must exist an N2×N2 matrix K(Φ) that satisfiesEmbedded Imagefor every possible N×N density matrix ρ. The matrix K(Φ) is called the natural matrix representation of the quantum operation Φ, and is uniquely determined by Φ.

The natural matrix representation can easily be calculated from other standard forms. For example, if an operation Φ is represented in the usual Kraus form asEmbedded Imagethen it holds thatEmbedded Imageand, therefore,Embedded Image(Here Embedded Image represents the entry-wise complex conjugate of Embedded Imagej.)

In the section that follows, we will make use of the following simple way to calculate the natural matrix representation of a quantum operation that is specified by a quantum circuit. Suppose that Embedded Image is an r-qubit system, Embedded Image is an s-qubit system and U is a unitary operation on r+s qubits. Then, for the quantum operation Φ defined asEmbedded Imagewe haveEmbedded Image(4.2)for Embedded Image(In both cases, each identity matrix I acts on Embedded Image, or equivalently is the 2r×2r identity matrix.)

(b) Space-bounded and depth-bounded computations

When we speak of a family {Cn:nEmbedded Image} of Boolean circuits, we assume that each Cn is an acyclic circuit, composed of AND, OR and NOT, and constant-sized fanout gates, with n input bits and an arbitrary number of output bits. Such a family computes a function f:{0,1}*→{0,1}* if, for each nEmbedded Image and string x∈{0,1}n, the circuit Cn outputs f(x) when given input x. The depth of a Boolean circuit C is the length of the longest path in C from an input bit to an output bit. The size of C is the sum of the number of input bits, output bits and gates.

For a given function s:Embedded ImageEmbedded Image, we say that a Boolean circuit family {Cn:nEmbedded Image} is space O(s) uniform if there exists a deterministic Turing machine M that runs in space O(s(n)), and that outputs a description of Cn on input 1n for each nEmbedded Image.3 As is usual when discussing space-bounded computation, a deterministic Turing machine is assumed to be equipped with a read-only input tape that does not contribute to the space it uses, so it is meaningful to consider sublinear space bounds. Given a space O(s)-uniform family {Cn:nEmbedded Image}, the size of Cn can be at most 2O(s(n)).

We say a function f:{0,1}*→{0,1}* is in the class Embedded Image(s) if there exists a space O(s)-uniform family of Boolean circuits {Cn:nEmbedded Image} that computes f, and where the depth of Cn is at most s(n)O(1).4 Also, a language L is in Embedded Image(s) if its characteristic function is in Embedded Image(s). We write Embedded Image for Embedded Image(log n), and Embedded Image(poly) for the union of Embedded Image(nc) over all constants c. Borodin (1977) proved that, if s satisfies s(n)=Ω(log n), every function in Embedded Image(s) is computable by a deterministic Turing machine in space s(n)O(1). It follows that Embedded Image(poly)⊆Embedded Image. (The reverse containment also holds, so in fact we have Embedded Image(poly)⊆Embedded Image.)

It is clear that, if fEmbedded Image(poly) and gEmbedded Image, their composition gf is in Embedded Image(poly), since we can create a circuit for gf by composing the circuits for f and g in the obvious way.

Many functions of matrices are known to be computable in Embedded Image. These include sums and products of matrices, inverses and the trace, determinant and characteristic polynomial, all over a wide range of fields for which computations can be efficiently performed (see von zur Gathen 1993). In particular, we will rely on a fact that follows from a result of Borodin et al. (1983, §4).

The determinant of an n×n matrix whose entries are rational functions in an indeterminate z can be computed in Embedded Image.

(c) Projecting onto fixed points

In this subsection, we prove a general theorem about efficient construction of quantum operations that project onto the fixed points of other quantum operations. This theorem is the technical core of our Embedded ImageCTCEmbedded Image result, but it might be of independent interest as well.

Suppose that Φ:Embedded ImageN×NEmbedded ImageN×N is a given quantum operation acting on an N-dimensional system, meaning that it is a completely positive and trace-preserving linear map. We will prove that there exists another quantum operationEmbedded Imagewhich satisfies the following three properties:

  1. for every density matrix σEmbedded ImageN×N, it holds that ρ=Λ(σ) is a fixed point of Φ,

  2. every density matrix ρ that is a fixed point of Φ is also a fixed point of Λ, and

  3. Λ can be computed from Φ in Embedded Image.

In essence, Λ is a (non-orthogonal) projection onto fixed points of Φ, so if we want a fixed point of Φ it suffices to compute Λ(σ) for any density matrix σ, and moreover every fixed point ρ of Φ arises in this way from some density matrix σ (which always includes the choice σ=ρ).

The operation Λ is defined as follows. First, for each real number z∈(0,1), we define a superoperator Λz:Embedded ImageN×NEmbedded ImageN×N asEmbedded ImageHere, Φk represents the k-fold composition of Φ, and Φ0 is the identity operation. Each Φk is obviously completely positive and trace preserving. Given that z(1−z)k∈(0,1) for each choice of z∈(0,1) and k≥0, and that Embedded Image for every z∈(0,1), we have that Λz is a convex combination of completely positive and trace-preserving maps. Thus, Λz is completely positive and trace preserving as well. Finally, we takeEmbedded ImageWe must of course prove that this limit exists—and in the process, we will prove that Λ can be produced from Φ by an Embedded Image computation, which is an important ingredient of our simulation of Embedded ImageCTC in Embedded Image. Once this is done, the required properties of Λ will be easily verified.

We assume that Φ is represented by the N2×N2 complex matrix M=K(Φ) as discussed in §4a. Since Φ is a quantum operation, every eigenvalue of M lies within the unit circle.5 It follows that the matrix I−(1−z) M is invertible for every real z∈(0,1), and moreover there is a convergent series for its inverse,Embedded Image(4.3)Now, for every z∈(0,1) we define an N2×N2 matrix Rz as follows:Embedded ImageWe note that Rz=K(Λz) for Λz as defined above—and as each Λz is completely positive and trace preserving, each entry of Rz must be bounded in absolute value by 1.

Next, by Cramer's rule, we haveEmbedded Image(4.4)where (I−(1−z)M)j,i denotes the (N2−1)×(N2−1) matrix obtained by removing the jth row and ith column from I−(1−z)M. It follows that each entry of Rz is given by a rational function in the variable z having degree at most N2. As the entries of Rz are rational functions that are bounded for all z∈(0,1), we have that the limit Embedded Image exists. DefineEmbedded Imageand note that R=K(Λ). We have therefore proved that the limit Embedded Image exists as claimed.

The fact that R can be computed from M in Embedded Image follows from the above discussion, together with theorem 4.1. In particular, equation (4.4) above expresses the entries of Rz as ratios of polynomials of degree at most N2 in z having coefficients with rational real and imaginary parts. It remains to compute the limit, which is also done symbolically for the real and imaginary parts of each entry. To computeEmbedded Imagefor polynomials Embedded Image and Embedded Image, we perform a binary search on the coefficients of g to find the smallest k for which dk≠0, and then output the ratio ck/dk. Each of the required computations can be done in Embedded Image, and can be applied in parallel for each entry of R to allow R to be computed from M in Embedded Image.

Finally, we verify the required properties of Λ. It is clear that every fixed point ρ of Φ is also a fixed point of Λ, sinceEmbedded Imageand, therefore, Embedded Image. To prove that ρ=Λ(σ) is a fixed point of Φ for every density matrix σ, it suffices to prove ΦΛ=Λ. For each z∈(0,1) we haveEmbedded Imageand, therefore,Embedded Imageas claimed. ▪

(d) Proof of containment

We can now complete the proof that quantum computers with CTCs are simulatable in Embedded Image.

Embedded ImageCTCEmbedded Image.

Let LEmbedded ImageCTC be given, and assume that Embedded Image is a quantum CTC algorithm for L. As discussed in §4b, it suffices to prove LEmbedded Image(poly).

Assume for simplicity that an input x of length n has been fixed. Let Q be the unitary quantum circuit that is output by Embedded Image on input x; then, as in the definition of Embedded ImageCTC, define a quantum operationEmbedded ImageOur goal will be to compute the probabilityEmbedded Image(4.5)for some arbitrary fixed point ρ of Φ. This value can then be compared with 1/2 to decide whether to accept or reject. This computation will be performed in a uniform manner, in Embedded Image(poly), therefore establishing that LEmbedded Image(poly).

The first step is to compute the matrix representation M=K(Φ) of the operation Φ. This can be done by a polynomial-space uniform family of Boolean circuits with exponential size and polynomial depth, since M is expressible as in equation (4.2), and Q is expressible as a product of a polynomial number of exponential-size matrices determined by the gates of Q.

Next, we compute the matrix representation R=K(Λ), where Λ is the quantum operation that projects onto fixed points of Φ discussed in §4c. We have argued that R can be computed from M in Embedded Image, and, therefore, by composing this computation with the Embedded Image(poly) computation of M, we have that R can be computed in Embedded Image(poly).

Finally, we compute a fixed point ρ of Φ using R along with an arbitrary choice of a density matrix input for Λ. For instance, we may take ρ=Λ((|0〉〈0|)q(n)), so that vec(ρ)=R|0〉⊗2q(n). The probability (4.5) can then be evaluated in Embedded Image(poly) by performing matrix–vector multiplication. ▪

5. Dealing with error

In defining the class Embedded ImageCTC, we required the quantum circuits to involve amplitudes with rational real and imaginary parts. However, while this assumption is mathematically convenient, it is also ‘unphysical’. Even in a CTC universe, quantum operations can presumably only be implemented to finite precision. In this section, we consider how to make our upper and lower bounds robust to small errors.

The basic difficulty is that, in a CTC universe, two quantum operations that are arbitrarily close can produce detectably different outcomes. As an example, consider the stochastic matrices,Embedded ImageAs ϵ→0, these matrices become arbitrarily close to each other and to the identity matrix. Yet, their fixed points remain disjoint: the first has a unique fixed point of (1,0)T, while the second has a unique fixed point of (1,0)T. Hence, were an algorithm to apply one of these matrices inside a CTC, an arbitrarily small error could completely change the outcome of the computation.

However, we will show that, while this ‘pathological’ situation can arise in principle, it does not arise in our simulation of Embedded Image by a CTC computer in lemma 3.2.

Given two probability distributions Embedded Image=(Px) and Embedded Image=(qx), recall that their variation distance is defined asEmbedded ImageAlso, given two mixed states ρ and σ, their trace distance is defined asEmbedded Imagewhere the maximum is over all unitary matrices U. Finally, given two superoperators Φ and Φ′, their diamond distance is defined asEmbedded Imagewhere the maximum is over all mixed states ρ on some larger Hilbert space.

Given a superoperator Φ, call ρ an ϵ-fixed point of Φ if Embedded Image.

Suppose ρ is a fixed point of Φ and Embedded Image. Then, ρ is an ϵ-fixed point of Φ′.

Since ρ=Φ(ρ), we have Embedded Image.

Let Φ be a classical operation mapping a finite set Embedded Image to itself, and let ρ be an ϵ-fixed point of Φ. Then Embedded Image for some state σ supported only on the cycles of Φ.

We prove the contrapositive. Let Embedded Image be the union of all cycles of Φ, and let Embedded Image. Also, for each element xEmbedded Image, let px=〈|x〉. Suppose ρ is not δ-close to any state supported only on C, where δ=2|Embedded Image|ϵ. Then Embedded Image. Hence, letting Embedded Image be the distribution over Embedded Image obtained by measuring ρ in the standard basis, we haveEmbedded ImageHere the fourth line follows from the triangle inequality. The fifth line follows from the triangle inequality, together with the fact that, if we fix an Embedded Image maximizing px, and then consider all z's ‘upstream’ from x (i.e. such that Φ(z)=x, or Φ(Φ(z))=x, etc.), we must eventually reach ‘source’ elements, i.e. z's for which there are no y's such that Φ(y)=z, and henceEmbedded Image ▪

We can now prove the following.

Every Embedded Image language L is decidable in Embedded ImageCTC even if every gate of the Embedded ImageCTC circuit is subject to 2q(n) error (for some polynomial q depending on L and the circuit).

Let C′ be the circuit from lemma 3.2 that maps Embedded ImageCTC to itself. As part of the proof of lemma 3.2, we showed that the graph of Embedded Image has a unique cycle L, in which every configuration leads to the desired output. Now let C″ be a corrupted version of C′ that satisfies Embedded Image, and let ρ be any fixed point of C″. Then ρ is an ϵ-fixed point of C′ by proposition 5.1. By lemma 5.2, this in turn means that Embedded Image for some state σ supported only on L. So provided Embedded Image, a CTC algorithm that uses C″ in place of C′ will still produce the correct answer with high probability. ▪

Moreover, as pointed out by Bacon (2004), even if every gate in our quantum circuit is subject to (sufficiently small) constant error, we can still use standard results from the theory of quantum error correction (Aharonov & Ben-Or 1997) to ensure that |C′−C″| is exponentially small, where C′ and C″ are the quantum circuits acting on the logical (encoded) qubits. See Bacon (2004) for a detailed version of this argument.

But what about our proof of the Embedded ImageCTCEmbedded Image upper bound, in §4: is that proof affected by precision issues? It might be thought that we simply need to represent all amplitudes and matrix elements to poly(n) bits of precision. As discussed earlier, however, the trouble is that the set of fixed points of a superoperator Φ can depend sensitively on Φ, so that an arbitrarily small change to Φ produces a large change in the set of fixed points. Indeed, this is precisely the reason why we assumed the amplitudes to be complex rational numbers. Owing to that assumption, we were able to use the algorithm of Borodin et al. (1983) to compute a fixed point symbolically rather than just numerically.

6. Discussion and open problems

(a) CTCs in other computational models

In the proof that Embedded ImageEmbedded ImageCTC we did not actually need the full strength of polynomial-time computation inside the CTC: rather, all we needed was the ability to update the configuration of a Embedded Image machine and increment a counter. Thus, our proof also shows (for example) that Embedded Image, where Embedded Image0 denotes the class of problems solvable by constant-depth, polynomial-size circuits consisting of AND, OR and NOT gates, and Embedded Image is defined the same way as Embedded ImageCTC but with Embedded Image0 circuits instead of arbitrary polynomial-size circuits.

In the other direction, we could also define Embedded ImageCTC the same way as Embedded ImageCTC, but with Embedded Image machines in place of polynomial-size circuits. Then it is evident that our proof generalizes to show Embedded ImageCTC=Embedded Image.

It would be extremely interesting to study the consequences of Deutsch's causal consistency assumption in other settings besides polynomial-time computation, e.g. communication complexity, branching programmes and finite automata.

(b) Narrow CTCs

What is the power of classical CTCs with a single bit, or of quantum CTCs with a single qubit (as studied by Bacon (2004))? Let Embedded ImageCTC1, Embedded ImageCTC1 and Embedded ImageCTC1 be the corresponding deterministic, randomized and quantum complexity classes. Then it is not hard to show that Embedded ImageEmbedded ImageEmbedded ImageCTC1, i.e. a single use of a one-bit CTC, is enough to solve all problems in the class Embedded ImageEmbedded Image. For we can guess a random string w∈{0,1}p(n), then set the CTC bit b to 1 if w is a yes witness or to 0 if w is a no witness, and leave b unchanged if w is neither. If there exists a yes witness but not a no witness, then the only fixed point of the induced stochastic evolution is b=1, while if there exists a no witness but not a yes witness, then the only fixed point is b=0. Indeed, a simple extension of this idea yields Embedded ImageEmbedded ImageCTC1: we set b=1 if a yes witness w∈{0,1}p(n) was guessed, and set b=0 with some tiny probability Embedded Image independent of the witness. Again, the unique fixed point of the induced stochastic map will fix b=1 with overwhelming probability if there exists a yes witness, or b=0 with certainty if not. Fully understanding the power of ‘bounded-width CTCs’ remains a problem for the future.

(c) CTC computers with advice

Let Embedded ImageCTC/Embedded Image be defined the same way as Embedded ImageCTC except that, instead of being initialized to 0q(n), the chronology-respecting register Embedded ImageCR is initialized to a probability distribution Embedded Imagen, which depends only on the input length n, but can otherwise be chosen arbitrarily to help the CTC algorithm. Then we claim that Embedded ImageCTC/Embedded Image=Embedded Image: in other words, Embedded ImageCTC/Embedded Image contains every computational problem! To see this, let Embedded ImageCR be initialized to the uniform distribution over all ordered pairs 〈z,f(z)〉, where z is an n-bit input and f(x)∈{0,1} encodes whether xL. Also, let the CTC register Embedded ImageCTC contain a single bit b. Then given an input x, our circuit C acts on b as follows: if z=x then C sets b=f(x); otherwise C leaves b unchanged. It is easy to see that the unique fixed point of the induced stochastic map on Embedded ImageCTC fixes b=f(x) with certainty.

While it demonstrates that CTCs combined with randomized advice yield staggering computational power, this result is not quite as surprising as it seems: for it was previously shown by Aaronson (2006) that Embedded Image/Embedded Image=Embedded Image, and by Raz (2005) that Embedded Image(2)/Embedded Image=Embedded Image. In other words, randomized advice has a well-known tendency to yield unlimited computational power when combined with certain other resources.

Acknowledgments

We thank Lance Fortnow for suggesting the proof of lemma 3.2, and Dave Bacon, Todd Brun and David Deutsch for their helpful discussions. S.A. is supported by MIT CSAIL and the Keck Foundation. J.W. is supported by Canada's NSERC and the Canadian Institute for Advanced Research (CIFAR).

Footnotes

  • He also sketched a possible extension to Embedded Image problems. However, Brun did not specify the model of computation underlying his results, and the most natural interpretation of his ‘CTC algorithms’ would appear to preclude their solving Embedded Image problems. For Brun, a fixed point of a CTC evolution seems to be necessarily deterministic—in which case, finding such a fixed point is an Embedded Image problem (note that Embedded Image is almost universally believed to be smaller than Embedded Image). Thus, to prove that classical or quantum computers with CTCs give the full power of Embedded Image, it seems essential to adopt Deutsch's causal consistency model.

  • On the other hand, Bacon's approach would require a polynomial number of such CTCs, rather than a single CTC as in Deutsch's approach.

  • Considering inputs of the form 1n are just a standard trick to force n to be encoded in ‘unary’, i.e. such that it takes n bits to write down.

  • Embedded Image stands for ‘Nick's class’; the term is historical. Also, what we call Embedded Image(s) is called Embedded Image(2s) by Borodin et al. (1983).

  • This fact is proved in Terhal & DiVincenzo (2000). An alternative proof follows from the fact that ‖Φ=1 and that the diamond norm is submultiplicative (see theorem 5.6.9 of Horn & Johnson (1990)).

    • Received August 25, 2008.
    • Accepted October 10, 2008.

References

View Abstract