Quantum Physics

   

One-Wayness in Input-Saving (Turing) Machine

Authors: Alexandre de Castro

In computer science, the P =?NP problem is to determine whether every language accepted by some nondeterministic algorithm in polynomial-time is also accepted by some (deterministic) algorithm in polynomial-time. Currently, such a complexity-class problem is proving the existence of one-way functions: operations that are computationally ‘easy’, while their inverses are computationally ‘hard’. In this paper, I show that this outstanding issue can be answered by an appeal to physics proofs about the thermodynamic cost of computation. The physics proof presented here involves Bennett's reversible algorithm, a physically-motived input-saving (Turing) machine – that computationally corresponds to two successive controlled-NOT quantum gates – used to reconcile Szilárd's one-molecule engine (a variant of Maxwell’s demon gedankenexperiment) and Landauer’s principle, which asserts a minimal thermodynamic cost to performing a bitwise operation, and which can be derived solely on the basis of the properties of the logical operation itself. In what follows, I show that by running the Bennett's input-saving machine backwards the critical inequality in Landauer’s principle is reversed, which provokes time-reversal symmetry. This outcome determines the condition of existence of a thermodynamically non-invertible quantum circuit in polynomial-time, that would otherwise be mathematically invertible. The main finding of this paper shows that a quantum circuit of two successive controlled-NOT gate becomes one-way, provided that adiabatically immersed in a heat bath. This physical constraint can be particularly important to model symmetry-protected isomorphism from a cluster state to itself in quantum teleport by measurement-based quantum computing.

Comments: 11 Pages.

Download: PDF

Submission history

[v1] 2014-03-31 12:41:07
[v2] 2014-04-14 05:38:11

Unique-IP document downloads: 17 times

Add your own feedback and questions here:
You are equally welcome to be positive or negative about any paper but please be polite. If you are being critical you must mention at least one specific error, otherwise your comment will be deleted as unhelpful.

comments powered by Disqus