The Truth About Reversible Computing

The Reversible and Quantum Computing Group (Revcomp)

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.

Ref: https://en.wikipedia.org/wiki/Reversible_computing

Computation

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.

Failure: Why Taking Risks and Failing Is the Path to ...

Where can I learn more?

Start here…

Reversible Computing

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: