What is Reversible Computing?
Reversible computing is a model of computing where the computational process to some extent is time-reversible. In a model of computation that uses deterministic transitions from one state of the abstract machine to another, a necessary condition for reversibility is that the relation of the mapping from states to their successors must be one-to-one. Reversible computing is a form of unconventional computing.
Computation deals with Logic and Arithmetic Operations at its core. So when we talk about Reversible Computing we talk about Reversing those two kinds of operations.
By doing so we
- Reverse Time
- Reverse Causality
Efforts At Automatski
At Automatski we achieved the following 3 things in independent efforts…
- We Built a Probabilistic Reversible Computer
- We Reversed Native Logic Gates
- We Built a Reversible Computer using a Reversible Logic Gates Set and building everything on top of it.
What were we trying to achieve?
Our goal was to reverse time and causality. Which is also the goal of or yet another effort Quantum Gravity Computer. But thats Quantum and everything we mentioned earlier is Classical. We still don’t have a Universal Computational Paradigm we can implement over our Quantum Gravity Computer to solve problems of interest to us. While the QGC itself is perfect and works very well at its core.
The immediate objective was to improve Grovers Algorithm from O(Sqrt(N)) to One Shot Algorithms O(1)
How is it different from other efforts?
Other efforts are focusing on Energy benefits of Reversible Computing. We are focussing purely on the Computational Benefits of Reversible Computing.
Landauer’s principle is a physical principle pertaining to the lower theoretical limit of energy consumption of computation.It holds that “any logically irreversible manipulation of information, such as the erasure of a bit or the merging of two computation paths, must be accompanied by a corresponding entropy increase in non-information-bearing degrees of freedom of the information-processing
The Results & The Failure
Maybe we are missing something. Our Reversible Computers are Computationally and Logically Perfect. Yet the moment we apply them to real world problems which go from multiple-inputs to unique-outputs. And we reverse them. We encounter O(Exponential Time)
Our failure lies in not being able to better Grovers Algorithm to O(1) atleast not yet. There are other efforts which could bear fruit but thats for a separate discussion.
In both Classical and Quantum Reversible Computing we face problems reversing many-to-one circuits, and in reducing complexity to Linear O(N) or Single Shot O(1), sometimes we need such reduced complexity of algorithms to solve really large problems.
Where can I learn more?