Replicating the benefits of Deutschian closed timelike curves without breaking causality

Abstract

In general relativity, closed timelike curves can break causality with remarkable and unsettling consequences. At the classical level, they induce causal paradoxes disturbing enough to motivate conjectures that explicitly prevent their existence. At the quantum level such problems can be resolved through the Deutschian formalism, however this induces radical benefits--from cloning unknown quantum states to solving problems intractable to quantum computers. Instinctively, one expects these benefits to vanish if causality is respected. Here we show that in harnessing entanglement, we can efficiently solve NP-complete problems and clone arbitrary quantum states--even when all time-travelling systems are completely isolated from the past. Thus, the many defining benefits of Deutschian closed timelike curves can still be harnessed, even when causality is preserved. Our results unveil a subtle interplay between entanglement and general relativity, and significantly improve the potential of probing the radical effects that may exist at the interface between relativity and quantum theory.

http://www.nature.com/npjqi

Web End =www.nature.com/npjqi

All rights reserved 2056-6387/15

Xiao Yuan1, Syed M Assad2, Jayne Thompson3, Jing Yan Haw2, Vlatko Vedral3,4, Timothy C Ralph5, Ping Koy Lam2, Christian Weedbrook6 and Mile Gu1,3

In general relativity, closed timelike curves can break causality with remarkable and unsettling consequences. At the classical level, they induce causal paradoxes disturbing enough to motivate conjectures that explicitly prevent their existence. At the quantum level such problems can be resolved through the Deutschian formalism, however this induces radical benetsfrom cloning unknown quantum states to solving problems intractable to quantum computers. Instinctively, one expects these benets to vanish if causality is respected. Here we show that in harnessing entanglement, we can efciently solve NP-complete problems and clone arbitrary quantum stateseven when all time-travelling systems are completely isolated from the past. Thus, the many dening benets of Deutschian closed timelike curves can still be harnessed, even when causality is preserved. Our results unveil a subtle interplay between entanglement and general relativity, and signicantly improve the potential of probing the radical effects that

npj Quantum Information (2015) 1, 15007; doi:http://dx.doi.org/10.1038/npjqi.2015.7

Web End =10.1038/npjqi.2015.7 ; published online 24 November 2015

INTRODUCTION

Causality aligns with our natural sense of reality. We expect there to be a natural chronology to our realitytwo events should not be simultaneous causes for each other. The breaking of causality dees classical logic, resulting in causal paradoxes with no simple solutionthe iconic example being the case where a man travels back in time to kill his own grandfather. Thus, physical predictions that break causality face intense scrutinyoften considered to be theoretical artifacts that are likely suppressed once we gain a more complete understanding of realitymotivating various chronology protection conjectures.1

Nevertheless, causality breaking theories are consistent with current scientic knowledge. Closed timelike curves (CTCs) are valid solutions of Einsteins equations in general relativity.24

Meanwhile, Deutsch put forward a model of CTCs, such that in the quantum regime, the resulting causal paradoxes always have self-consistent solutions.5 This resolution, however, has radical operational consequences. Many foundational constraints of quantum theory break. Non-orthogonal quantum states can be perfectly distinguished, the uncertainty principle can be violated, and arbitrary unknown quantum states can be cloned to any xed delity.68 In harnessing these effects, many problems thought to be intractable for standard quantum computers now eld efcient solutions.912 Though radical, these effects seem somewhat rationalized in the context of requiring broken causalitythe sentiment being that they are curiosities that will vanish once causality is imposed.

What happens, however, if causality is not strictly broken? In this context, Pienaar et al. considered a special case of Deutschian CTCs known as open timelike curves13 (OTCs). Consider a particle that travels back in time with respect to a chronology-respecting

2015 University of New South Wales/Macmillan Publishers Limited

ARTICLE OPEN

Replicating the benets of Deutschian closed timelike curves without breaking causality

may exist at the interface between relativity and quantum theory.

observer, but is completely isolated from anything that can affect its own causal past during the time-traveling process (See Figure 1). While the time-traveling particle has the potential to break causality, its complete isolation ensures that causality never actually breaks. Nevertheless, such OTCs can violate uncertainty principles between position and momentum. This opens a remarkable possibilitycould the many other radical effects of CTCs stand independent from the breaking of causality?

Here, we demonstrate that OTCs are remarkably powerful, and can replicate many dening operational benets of Deutschian CTCs. In sending a particle back in timeeven when it interacts with nothing in its causal pastwe can clone arbitrary quantum states to any xed accuracy, and thus violate any uncertainty principle. Meanwhile, they also grant quantum processors additional computational power, allowing efcient solution of NP-complete problems. Our results hint that the remarkable power of Deutschian CTCs may survive the censorship of chronology protection. This drastically improves the potential of harnessing such power via alternative effectssuch as certain models of gravitational time dilation.13 Thus, we open the possibility of testing the many radical protocols that harness CTCs in signicantly less controversial settings.

RESULTS

FrameworkIn general relativity, causality can be violated due to the presence of spacetime wormholes that facilitate closed timelike curves (See Figure 1). This can lead to physical processes where a system A, starting out in a state (in), interacts with a second system A0 in state CTC via a unitary U. System A then enters the wormhole and

1Center for Quantum Information, Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing, China; 2Centre for Quantum Computation and Communication Technology, Department of Quantum Science, The Australian National University, Canberra, ACT, Australia; 3Centre for Quantum Technologies, National University of Singapore, Singapore, Singapore; 4Clarendon Laboratories, Oxford University, UK; 5Centre for Quantum Computation and Communication Technology School of Mathematics and Physics, University of Queensland, St Lucia, Queensland, Australia and 6QKD Corp., Toronto, Canada.

Correspondence: M Gu (mailto:[email protected]

Web End [email protected])

Received 25 February 2015; revised 2 June 2015; accepted 1 August 2015

Replicating closed timelike curves without breaking causality

X Yuan et al

2

CTC

tB

tA

t

A

B

CTC

( )

in

A

U

U

AB

CTC

(out)

B

OTC

A

OTC

( )

in

A

AB

(out)

Figure 1. Deutschian timelike curves. (a) depicts a physical visualization of a CTC, where an object entering one mouth of a wormhole at some point tA may jump to a prior time tB (with respect to an chronology respecting observer) and interact with its past self via some unitary U. (b) In the special case where no interaction occurs, we obtain an open timelike curve. This naturally occurs, for example, in instances where the wormhole mouths are spatially separated.

OTC

Figure 2. CTCs and OTCs in presence of ancilla. A represents the system to be sent through the spacetime wormhole, A0 represents the same system after it passes through the spacetime wormhole, and B some chronology-respecting system initially correlated with A. (a) In general CTCs, temporal self-consistency demands that CTC satises CTC TrAUinAB CTCUy . (b) In the case of OTCs, this implies that system A has state OTC TrA inAB OTCh i

A after application of

the protocol.

becomes system A0. The Deutschian model, resolves potential paradoxes by enforcing temporal self-consistency conditions.5,14

CTC TrA Uin CTCUy h i

; 1 where TrA represents tracing over everything apart from system

A. Given a solution for CTC, the nal output of the process is

given by

out TrA Uin CTCUy h i

: 2 The many radical effects of CTCs rely on using specic self-interactions U to break causality in different ways.6,7,911

Note that since the effects of CTCs are non-linear, many conventional assumptions of linear quantum mechanics break. One consequence is that different unravellings of a density operator give different predictions, and therefore must be treated very carefully. While the above analysis does not assume (in) is pure, these conditions only apply to mixed inputs if (in) represents one partition of a larger composite system that is pure. In cases where the input state is deterministically prepared in a pure state, shot-by-shot, but the particular state may change shot-by-shot, there remains some ambiguity. The conventional view is taken by Bacon,10 Brun et al.6 and Pienaar et al.13that sub-ensembles of identical input states should be treated as pure. Others argue that if this sequence is truly random, then the randomness must always be treated as if it arose from the purication of an entangled quantum state.15 The former view, which we adopt here, is supported by studies of CTCs in the context of information ow.14 Also note that if the sequence of input states were chosen via a pseudo random number generator, then both perspectives agree.

In OTCs, causality is preserved. The unitary U is the identity such that the time-travelling system does not interact with its causal past. Any observer in the frame of reference of the time travelling system can assign a valid chronology to all the events they witness. Meanwhile, to any outside observer, all events involving interactions with the time travelling system will occur in causal sequence. From an operational standpoint, there is no breaking of causality. If all information were classical, this entire procedure would only have the effect of desynchronizing a time travellers clock with that of an observer.

To observe non-trivial effects we must introduce an ancilla. Suppose we have access to a bipartite system AB in state AB, where only one bipartition is sent through the

OTC (see Figure 2). The self-consistency relations requires CTC TrAinAB CTC A, and as a consequence

out TrAinAB TrAinAB A B 3 Thus, the OTC acts as a universal decorrelator on Ain sending a system A though an OTC, we erase all quantum correlations between A and the rest of the universe (and in particular, B). The resulting state, AB elds identical local statistics with respect to the input AB, but none of its bipartite correlations. While this operation appears similar to trivial decoherence, it is non-linear, and shown to be impossible to synthesize with standard quantum dynamics.16 This decoherence ensures that the Deutschian formalism remains consistent with special relativity. If quantum correlations between A and B were preserved, the capacity for OTCs to clone quantum states (as we show in following sections) would allow for superluminal signalling via Herberts protocol.17

One way to understand this effect is through the monogamy of entanglement14a particle and its past self cannot be simultaneously entangled with the same external ancilla. While OTCs produce nontrivial dynamics when the input appears completely classical (e.g., when inAB 00

j i 00

h j 11

j i 11

h j=2), this only

occurs if this mixedness as being intrinsici.e., it arises from entanglement with some other system. If the input is deterministically prepared in either state 00

j i or 11

j i according to some

classical sequence, then the OTC will have no effect (for other viewpoints, see Bennett et al.15).

OTC enhanced measurementWe rst introduce OTC enhanced measurement, a procedure that harnesses OTCs to measure an arbitrary observable ^

O to any xed precision. Specically, given an unknown qudit (d dimensional quantum system) in state , we can determine ^

O

Tr

O to

any desired accuracy 40 with negligible failure probability. This protocol functions as a building block for more sophisticated applications of OTCs, such as the efcient solution of NP-complete problems and cloning of unknown quantum states.

^

npj Quantum Information (2015) 15007 2015 University of New South Wales/Macmillan Publishers Limited

Replicating closed timelike curves without breaking causality X Yuan et al

3

The protocol is illustrated in Figure 3. Let j

j i : j 0; 1; ; d - 1

denote a basis that diagonalizes ^

O. On this basis, we introduce the two qudit controlled addition operator, C i

j i j

j i i

j i j i

j i, where

addition is done modulo d. We then

1. Prepare N identical ancillary states in an eigenstates of ^

O,

say 0

j i.

2. 2. Apply the C+ operations N times, each controlled on and targeting a fresh ancilla state. This correlates with each of the N ancillaries.

3. Pass each of the ancillaries through an OTC to destroy all correlations in this N+1-partite system.

This results in N+1 uncorrelated qudits, each in state diag

Pdi1 ii ij i ih j, where ii are the diagonal elements of in

the ^

O basis. Thus, each qudit exhibits identical statistics to when measured in the ^

O basis. In taking the mean of these measurements, we obtain an estimate for ^

O

.

By the central limit theorem, the error of our estimate scales linearly with 1=

N

p .

This non-linear map can be replicated without breaking causality (see Figure 4). Consider a special case of OTC enhanced measurement, with z as the observable of interest and a single ancilla. For the input qubit with matrix elements ij, application of the enhanced measurement protocol outputs two uncorrelated qubits, each in state diag 00 0

j i 0

h j 11 1

j i 1

h j. Instead of

measuring each in z directly, we apply a further C+ gate controlled on the ancilla. After discarding the ancilla, the input qubit is now transformed to S() as required.

In generating S() using only OTCs, we can translate Bacons algorithm into one that does not break causality. We note that as each call of S() only takes one OTC, the translation from CTCs to OTCs incurs no overhead on the number of times a particle needs to be sent through a spacetime wormhole. Thus, for the purpose of solving NP-complete problems, an OTC, together with one bit of entanglement, is at least as powerful as a CTC.

Cloning with OTCsGiven an unknown input , OTCs allow us to generate an unlimited number of clones to arbitrary delity. Our approach harnesses OTC enhanced measurements as a subroutine, which allows us to accurately determine Tr[Mi], for any observable Mi. First, observe that this remains possible even if we are supplied with

0 s

1 - sd I; 4

a very noisy version of . Here I is the d-dimensional identity matrix, and s is some xed parameter such that 0oso1.

This observation, together with an imperfect quantum cloner, forms the basis of our OTC enhanced cloning protocol (Figure 5). In conventional quantum theory, a unknown quantum state can be cloned if we are given sufciently many copies to

In particular, provided the eigenvalues of ^

O are bounded, Hoeffdings bound implies we can estimate ^

O to any desired accuracy and error rate using O[1/2log(1/)] OTCs (see methods for details).

We note this technique shares similarities with the proposal of Brun et al. to use closed timelike curves to perform the same task.7 Both protocols operate by harnessing spacetime wormholes to create many clones of with respect to the eigenbasis of ^

Oeach of which is measured to give a statistically independent estimate of ^

O

.

The key difference is that in Brun et al., each of these clones were trapped within a closed timelike curve, and reading out information from them required direct interaction with each clone. Our proposal shows that the use of CTCs is not compulsory. A comparison between the two methods indicate the use of OTCs incurs no overhead in the number of times a spacetime wormhole is used (see methods). Hence OTCsat least for this purposeare as powerful as CTCs.

Solving NP-complete problemsWe take inspiration from Bacon,10 who devised an efcient algorithm to solve the boolean satisfaction problema known NP-complete problemusing CTCs. We modify this algorithm to preserve causalitywithout losing efciency. In the causality breaking algorithm, the key role of CTCs is to implement the non-linear map S that maps an input qubit in state (nz)

to an output state n2z, where nz 12 I nzz

and

z 0

j i 0

h j - 1

j i 1

h j denotes the Pauli Z matrix (see methods

for details).

Figure 3. Quantum circuit of OTC enhanced measurement. The protocol rst introduces N ancilla qudits, all of which are initialized in the state E 0

j i 0

h j, where 0

j i is an eigenstate of

^

O. A sequence of C+ gates then perfectly correlates each ancilla with with respect to ^

O basis. The erasure of these correlations via OTCs, followed by ^

O

measurements on each individual qudit, allows determination of Tr

^

O to a standard error that scales inversely with N2.

Figure 4. Solving NP-complete problems with OTCs. The key nonlinear gate S, that takes (nz) to n2z, can be implemented via open

timelike curves. This is achieved by the use of a single OTC, applied between two successive C+ gates.

Figure 5. OTC Assisted Cloning An arbitrary qudit can be cloned to any desired delity. The process involves (i) application of a standard quantum cloner C to generate O(d2) imperfect copies, and (ii) use of OTC enhanced measurements to measure different observables Mi on each imperfect copy. We can choose Mi to be informationally-complete, and OTCs ensure that we can determine Tr[Mi] to any desired precision. Thus this protocol can yield (to any xed precision) the classical description of .

2015 University of New South Wales/Macmillan Publishers Limited npj Quantum Information (2015) 15007

Replicating closed timelike curves without breaking causality

X Yuan et al

4 perform accurate tomography.18 One way to do this, is to use a set of O(d2) informationally-complete measurements {Mi}, whose expectation values Tr[Mi] have a one-to-one correspondence with the classical matrix description of . If there is only a single copy of , this option is no longer available. Recently, Brun et al. demonstrated that closed timelike curves circumvent this restriction, and allow the estimation of each Mi

h i to any desired

accuracy.7

OTC enhancement measurements can replicate this effect while preserving causality. We use standard methods to construct O(d2)

imperfect clones in the form of equation (4), where s scales as 1/d for an optimal cloner.19 Each clone is passed through an OTC to remove all entanglement between clones. An OTC enhanced measurement is then performed on each clone with respect to a different Mi. The outcomes of these measurements determine the density matrix of . In methods, we show that by using Od4=2clog 1=c OTCs, we can ensure that each Mi

h i is obtained

to an accuracy of c with failure probability c.

A simple exampleWe illustrate these ideas by cloning a qubit. Here, the Pauli operators k, k = x, y, z form an informationally-complete setany is uniquely dened by the expectation values nk = Tr[k]. To determine nx, ny and nz, we rst apply a universal 1-to-3 quantum cloner20 to obtain three imperfect clones of , each in state 0 I s n

!U

!=2 with s = 5/9. All quantum correlations

between these three imperfect clones may be erased by applying OTCs.

An OTC enhanced measurement of z is then performed on one such imperfect clone. To do this, we rst initialize N fresh ancilla qubits in state 0

j i, and apply a CNOT gate between each ancilla

and the imperfect clone (with the clone as the control qubit). In erasing the resulting correlations by sending each ancilla through an OTC, we obtain N+1 qubits, each in the state (I+snzz)/2.

Provided N is sufciently large, measurement of these qubits allows nz to be determined to any desired accuracy with negligible error.

Repetition of this process with x and y on the two remaining imperfect clones then yields complete information about .

DISCUSSIONHere, we demonstrated that the many dening operational benets of Deutschian closed timelike curves can be retained without sacricing causality. Our approach was to consider open timelike curves, where physical systems may travel back in time, but do not interact with themselves, or any other system in their past light-cone. In harnessing these open timelike curves, we developed methods to efciently solve NP-complete problems, and clone unknown quantum states to arbitrary delity. Other radical effects commonly attributed to CTCs come as natural consequences, such as distinguishing non-orthogonal states,6 the capacity to communicate more than a bit of information in a single qubit and the breaking of non-entanglement based cryptographic schemes.8

More generally, our results imply that any non-linear quantum map that makes use of CTCs can also be synthesized using only open timelike curves. This follows from the reasoning of Brun et al.,6 which argued that if any two quantum states can be distinguished, then one can effectively implement any map between two quantum states. Related to this is the question of whether OTC enhanced computation has equal computational power to their CTC counterparts. Indeed, while we have shown OTCs can solve NP-complete problems, it remains an open question whether they can mimic CTCs capacity to efciently solve problems in PSPACE.11

The preservation of causality can also signicantly increase the likelihood for us to test theories of quantum gravity motivated by

the Deutschian formalism. For instance, from the perspective of a chronology-respecting observer, a particle sent through an OTC exhibits nothing more than time delay. Thus, in order to reconcile quantum eld theory with non-hyperbolic spacetimes, gravitational time-dilation has been conjectured to share similar operational effects as OTCs.21 If true, this suggests that some operational consequences of Deutschian CTCs may be observable without the need for spacetime wormholes, and the exotic benets of quantum processing in the general relativistic regime may be tested much sooner than previously expected.

Beyond the Deutschian framework, the present results also impact our understanding of general non-linear quantum theory. All protocols discussed require only a single non-linear operator the universal decorrelator that erases the correlations between two quantum systems while leaving local statistics of each unchanged. Provided a non-linear quantum theory can realize this operation, all of our results and the corresponding consequences apply. For example, it immediately follows that such a theory can also clone unknown quantum statesand thus behaves more like a classical probability theory where different density operators correspond to different points in the state space, and every point is perfectly distinguishable.6 There already exist models of gravitational decoherence that satisfy these conditions,21 and it would be exciting to see if this is true for other attempts to reconcile quantum theory with time travel,2224 or more general non-linear

candidate theories of quantum gravity.25,26

METHODS Scaling analysis

Execution of the OTC-enhanced measurement with N ancillaries (and therefore N uses of the OTC) to estimate ^

O

gives an output

Oest

PkOk=N 1. We dene the measurement as being successful if the estimate achieves a desired accuracy of (i.e., 9Oest - ^ O9<).

Application of Hoeffdings inequality27 gives failure probability pf that obeys

pf 2exp

- 2N 12

Omax - Omin2

" #

: 5

Here Omax and Omin are the respective maximum and minimum eigenvalues of ^

O. Therefore,

N4Omax - Omin2

22 log

2 ; 6

OTC applications ensures a failure probability of no more than . Provided ^

O is bounded, this scales as O[1/2log(1/)].

Brun et al.7 previously showed that one can also estimate ^

O

to

arbitrary accuracy with CTCs. In his protocol, one also creates N+1 copies of diag with N uses of the CTC system. Comparing between these two

protocols, we note that the classical information retrieved from measurements are statistically identical to our protocol. Thus, to achieve the same level of accuracy, the numbers of spacetime wormholes required by the two protocols coincide.

In OTC assisted cloning, we need to make d2 informationally complete measurements, each to a desired accuracy 40 with negligible failure probability 40. Recall this is achieved via a 1 d2 universal cloner, whose imperfect copies are to be decorrelated via the use of OTCs (Figure 5). For each of the d2 copies, we apply an OTC enhanced measurement. To ensure this measurement is within accuracy , an extra O(d2) overhead is required to compensate for the noise within the imperfect copies. The total number of OTCs required is then of order

N4O d4 1

22log

2 ; 7

where OmaxOmin = 1 for members of the informationally complete basis.

Solving NP-complete problemsHere we outline explicitly how a non-linear map that takes (nz)

to n2z

allows the efcient solution of NP-complete problems. Specically

npj Quantum Information (2015) 15007 2015 University of New South Wales/Macmillan Publishers Limited

Replicating closed timelike curves without breaking causality X Yuan et al

5

REFERENCES

1 Hawking, S. W. Chronology protection conjecture. Phys. Rev. D. 46,

603611 (1992).2 Gdel, K. An example of a new type of cosmological solutions of Einsteins eld equations of gravitation. Rev. Mod. Phys. 21, 447450 (1949).3 Morris, M. S., Thorne, K. S. & Yurtsever, U. Wormholes, time machines, and the weak energy condition. Phys. Rev. Lett. 61, 14461449 (1988).4 Gott, J. R. Closed timelike curves produced by pairs of moving cosmic strings: exact solutions. Phys. Rev. Lett. 66, 11261129 (1991).5 Deutsch, D. Quantum mechanics near closed timelike lines. Phys. Rev. D. 44, 3197 (1991).6 Brun, T. A., Harrington, J. & Wilde, M. M. Localized closed timelike curves can perfectly distinguish quantum states. Phys. Rev. Lett. 102, 210402 (2009).7 Brun, T. A., Wilde, M. M. & Winter, A. Quantum state cloning using Deutschian closed timelike curves. Phys. Rev. Lett. 111, 190401 (2013).8 Ahn, D., Myers, C. R., Ralph, T. C. & Mann, R. B. Quantum-state cloning in the presence of a closed timelike curve. Phys. Rev. A. 88, 022332 (2013).9 Brun, T. A. Computers with closed timelike curves can solve hard problems efciently. Found. Phys. Lett. 16, 245253 (2003).10 Bacon, D. Quantum computational complexity in the presence of closed timelike curves. Phys. Rev. A 70, 032309 (2004).11 Aaronson, S. & Watrous, J. Closed timelike curves make quantum and classical computing equivalent. Proc. R. Soc. A 465, 631647 (2009).12 Aaronson, S. Guest column: NP-complete problems and physical reality. ACM SIGACT News 36, 3052 (2005).13 Pienaar, J. L., Ralph, T. C. & Myers, C. R. Open timelike curves violate Heisenberg uncertainty principle. Phys. Rev. Lett. 110, 060501 (2013).14 Ralph, T. & Myers, C. Information ow of quantum states interacting with closed timelike curves. Phys. Rev. A. 82, 062330 (2010).15 Bennett, C. H., Leung, D., Smith, G. & Smolin, A. J. Can closed timelike curves or nonlinear quantum mechanics improve quantum state discrimination or help solve hard problems? Phys. Rev. Lett. 103, 170502 (2009).16 Terno, D. R. Nonlinear operations in quantum-information theory. Phys. Rev. A. 59, 33203324 (1999).17 Herbert, N. FLASHa superluminal communicator based upon a new kind of quantum measurement. Foundations of Physics. 12, 11711179 (1982).18 Thew, R. T., Nemoto, K., White, A. G. & Munro, W. J. Qudit quantum-state tomography. Phys. Rev. A. 66, 012303 (2002).19 Werner, R. F. Optimal cloning of pure states. Phys. Rev. A. 58, 18271832 (1998).20 Scarani, V., Iblisdir, S., Gisin, N. & Acn, A. Quantum cloning. Rev. Mod. Phys. 77, 12251256 (2005).21 Ralph, T. C., Milburn, G. J. & Downes, T. Quantum connectivity of space-time and gravitationally induced decorrelation of entanglement. Phys. Rev. A. 79, 022121 (2009).22 Lloyd, S. et al. Closed timelike curves via postselection: theory and experimental test of consistency. Phys. Rev. Lett. 106, 040403 (2011).23 Greenberger, D. M. & Svozil, K. Quantum theory looks at time travel. In Quo Vadis Quantum Mechanics? (Springer Verlag, Heidelberg, Germany, 2005).24 Allen, J. M. A. Treating time travel quantum mechanically. Phys. Rev. A. 90, 042107 (2014).25 Hawking, S. Quantum coherence and closed timelike curves. Phys. Rev. D. 52, 5681 (1995).26 Rosenberg, S. Testing causality violation on spacetimes with closed timelike curves. Phys. Rev. D. 57, 3365 (1998).27 Hoeffding, W. Probability inequalities for sums of bounded random variables.J. Am. Stat. Assoc. 58, 1330 (1963).

This work is licensed under a Creative Commons Attribution 4.0 International License. The images or other third party material in this article are included in the articles Creative Commons license, unless indicated otherwise in the credit line; if the material is not included under the Creative Commons license, users will need to obtain permission from the license holder to reproduce the material. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

Web End =http://creativecommons.org/licenses/ http://creativecommons.org/licenses/by/4.0/

Web End =by/4.0/

we study the satisfaction problem: Given a Boolean function f: {0, 1}n {0, 1}, specied in conjunctive normal form, does there exist a satisfying assignment ( b|f(b) = 1)? This problem is known to be NP-complete.

Bacon10 showed that this problem can be efciently solved if when given an input qubit I n

!U

!=2, we can synthesize a

quantum gate S such that S 12 I n2zz

.

Here n

! denotes the Bloch

! is a three-component vector of Pauli matrices. In Figure 4 we demonstrated how this gate can be synthesized using OTCs.

With this established, the satisfaction problem is efciently solved as follows:

1. Prepare n ancillary qubits in the state 1=

2n

sphere vector, and

P2 - 1i0 ij i and a target

qubit in state 0 j i.

2. Apply the unitary

Uf

X2 - 1i0ij i ih j fix; 8

on this system (with the last qubit representing the target). Tracing out the ancillary qubits leaves the target in

1

2 1 1 -

s 2n-1

z

; 9

where s is the number of x satisfying f(x) = 1.3. Apply S to the target via the use of OTCs (Figure 4). Repeat this step p times to get

p

1

2 1 1 -

" #

; 10

Notice that, we could easily check the case of s = 2n. Thus we only need to distinguish between s = 0 and 0oso2n. With the limit of p , the two output states corresponding to the cases of s = 0 and 0oso2n are p 0

j i 0

h j and p I/2, respectively. By performing measurement in the

z basis, one can distinguish the two types of output states 0

j i 0

h j and I/2,

that is, the case of s = 0 and 0oso2n, with failure probability being 1/2. By repeating these steps more times, say, q, the failing probability exponentially decays. For nite p and q that are polynomial in n, the probability of failure is given by10

Pfail

1

2q 1 1 -

s 2n-1 2

z

s2n-1

" 2 #q

: 11

ACKNOWLEDGEMENTS

We thank D. Terno and M. Wilde for helpful discussions. The research is supported by the National Basic Research Program of China Grant 2011CBA00300, 2011CBA00302, the National Natural Science Foundation of China Grant 11450110058, 61033001, 61361136003, the 1000 talents program of China, the National Research Foundation and Ministry of Education in Singapore, the Tier 3 MOE2012-T3-1-009 Grant Random numbers from quantum processes, and the Australian Research Council Centre of Excellence for Quantum Computation and Communication Technology Project number CE110001027 and the John Templeton Foundation grant 54914,Occams Quantum Mechanical Razor: Can Quantum theory admit the Simplest Understanding of Reality?

COMPETING INTERESTS

The authors declare no conict of interest.

2015 University of New South Wales/Macmillan Publishers Limited npj Quantum Information (2015) 15007