Perfect state distinguishability and computational speedups with postselected closed timelike curves

Abstract

Bennett and Schumacher's postselected quantum teleportation is a model of closed timelike curves (CTCs) that leads to results physically different from Deutsch's model. We show that even a single qubit passing through a postselected CTC (P-CTC) is sufficient to do any postselected quantum measurement, and we discuss an important difference between "Deutschian" CTCs (D-CTCs) and P-CTCs in which the future existence of a P-CTC might affect the present outcome of an experiment. Then, based on a suggestion of Bennett and Smith, we explicitly show how a party assisted by P-CTCs can distinguish a set of linearly independent quantum states, and we prove that it is not possible for such a party to distinguish a set of linearly dependent states. The power of P-CTCs is thus weaker than that of D-CTCs because the Holevo bound still applies to circuits using them regardless of their ability to conspire in violating the uncertainty principle. We then discuss how different notions of a quantum mixture that are indistinguishable in linear quantum mechanics lead to dramatically differing conclusions in a nonlinear quantum mechanics involving P-CTCs. Finally, we give explicit circuit constructions that can efficiently factor integers, efficiently solve any decision problem in the intersection of NP and coNP, and probabilistically solve any decision problem in NP. These circuits accomplish these tasks with just one qubit traveling back in time, and they exploit the ability of postselected closed timelike curves to create grandfather paradoxes for invalid answers.

15 pages, 4 figures; Foundations of Physics (2011)

References in corpus (7)

• Closed timelike curves via post-selection: theory and experimental demonstration
• The quantum mechanics of time travel through post-selected teleportation
• Can closed timelike curves or nonlinear quantum mechanics improve quantum state discrimination or help solve hard problems?
• Information Flow of quantum states interacting with closed timelike curves
• Closed Timelike Curves Make Quantum and Classical Computing Equivalent
• Purification of Mixed State with Closed Timelike Curve is not Possible
• Verifiable nonlinear quantum evolution implies failure of density matrices to represent proper mixtures

Cited by in corpus (24)

• Quantum correlations with no causal order
• Quantum computation with indefinite causal structures
• Operational quantum theory without predefined time
• Experimental Simulation of Closed Timelike Curves
• Treating Time Travel Quantum Mechanically
• Quantum Interactions with Closed Timelike Curves and Superluminal Signaling
• Postselected quantum hypothesis testing
• Nonclassical advantage in metrology established via quantum simulations of hypothetical closed timelike curves
• Faster than light motion does not imply time travel
• Black holes as Andreev reflecting mirrors
• Simulations of closed timelike curves
• Deutschian closed timelike curves can create entanglement
• Closed timelike curves and the second law of thermodynamics
• Time-travelling billiard-ball clocks: a quantum model
• Postselected communication over quantum channels
• Reality, Causality, and Quantum Theory
• Revisiting Integer Factorization using Closed Timelike Curves
• Quantum Correlations in Space-Time: Foundations and Applications
• Mixedness and Entanglement in the presence of Localized Closed Timelike Curves
• Quantum state tomography on closed timelike curves using weak measurements
• Looping back to the past through free fall in a controlled warp drive spacetime
• Retrocausal capacity of a quantum channel: Communicating through noisy closed timelike curves
• Distinguishing quantum states using time travelling qubits in a presence of thermal environments
• Quantum Signaling to the Past Using P-CTCS