Pith. sign in

REVIEW 1 cited by

Computability Theory of Closed Timelike Curves

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1609.05507 v2 pith:IVEMWFNX submitted 2016-09-18 quant-ph

Computability Theory of Closed Timelike Curves

Scott Aaronson , Mohammad Bavarian , Toby Cubitt , Sabee Grewal , Giulio Gueltrini , Ryan O'Donnell , Marien Raat This is my paper
classification quant-ph
keywords boundclosedcomplexitycomputablectcscurvesmarkovquantum
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved
0 comments
read the original abstract

We study the question of what is computable by Turing machines equipped with time travel into the past; i.e., with Deutschian closed timelike curves (CTCs) having no bound on their width or length. An alternative viewpoint is that we study the complexity of finding approximate fixed points of computable Markov chains and quantum channels of countably infinite dimension. Our main result is that the complexity of these problems is precisely $\Delta_2$, the class of languages Turing-reducible to the Halting problem. Establishing this as an upper bound for qubit-carrying CTCs requires recently developed results in the theory of quantum Markov maps.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Closed Timelike Curve Decoding on Quantum Hardware

    quant-ph 2026-07 accept novelty 6.0

    Routing a Deutsch-CTC loop state to a dump register makes the induced map the replacement channel σ ↦ ρ_M with unique fixed point ρ_M; IBM single-qubit data characterize the post-selected decoder branch.