The Computational Power of Minkowski Spacetime

Abstract

The Lorentzian length of a timelike curve connecting both endpoints of a classical computation is a function of the path taken through Minkowski spacetime. The associated runtime difference is due to time-dilation: the phenomenon whereby an observer finds that another's physically identical ideal clock has ticked at a different rate than their own clock. Using ideas appearing in the framework of computational complexity theory, time-dilation is quantified as an algorithmic resource by relating relativistic energy to an $n$th order polynomial time reduction at the completion of an observer's journey. These results enable a comparison between the optimal quadratic \emph{Grover speedup} from quantum computing and an $n=2$ speedup using classical computers and relativistic effects. The goal is not to propose a practical model of computation, but to probe the ultimate limits physics places on computation.

6 pages, LaTeX, feedback welcome

References in corpus (6)

• Quantum Computational Complexity in the Presence of Closed Timelike Curves
• Computers with closed timelike curves can solve hard problems
• The twin paradox in compact spaces
• Differential aging from acceleration, an explicit formula
• An analytical treatment of the Clock Paradox in the framework of the Special and General Theories of Relativity
• Relativity principles in 1+1 dimensions and differential aging reversal

Cited by in corpus (1)

• Comparison theorems for causal diamonds