How do you reverse computation with only Boolean logic?

[u/Chance-Pen-5684]

So you got CNOT and Toffoli gates and you can write them into a reversible circuit fairly easily enough.

So what’s stopping us from having autonomous reversible computers then?

Surely that’s the only important question that needs to be answered. It would allow circuits that don’t emit as much heat thus saving energy, money, humanity.

So what’s actually stopping this from happening?

[u/CapitalismSuuucks]

Measurements are not unitary hence not reversible

[u/Chance-Pen-5684 → u/CapitalismSuuucks]

Is that just an engineering obstacle or mathematical limitations?

[u/CapitalismSuuucks → u/Chance-Pen-5684]

Worse, it's a physical limitation. Quantum mechanics is such that most measurements are destructive. Some measurements only destroy information partially, these are called weak measurements. On the other hand, they also only recover information partially. There are also gentle measurements, but those require copies of the state you're measuring, which blows up space requirements and are non unitary anyways. There's no way around it.

[u/Chance-Pen-5684 → u/CapitalismSuuucks]

But does an autonomous reversible computer need to perform measurements during the computation?

[u/CapitalismSuuucks → u/Chance-Pen-5684]

I do not know what you mean by autonomous reversible computer. Can you elaborate?

[u/Chance-Pen-5684 → u/CapitalismSuuucks]

By autonomous, I mean a proper physical system that basically runs off its own dynamics, rather than having some outside controller constantly stepping in to prep or reset the physical state after every operation.

So say I string together a load of reversible gates. The full physical state coming out of one gate should be able to go straight into the next one as a valid input, no messing about in between. And, at least in principle, you should be able to run the whole thing backwards and end up where you started.

If that’s the setup, do I actually need to measure anything while the computation is going on? Surely I could just leave it to do its thing and only measure it at the end, when I actually want the final answer?

[u/CapitalismSuuucks → u/Chance-Pen-5684]

That's already how the computers work, be it digital or analogue. The circuits are made of unitary operations. They could be reversed. The question is why would one want to reverse them, because I emphasise: the moment you introduce a measurement to try to recover information, the computation is over on that qubit and it changes the state of the other qubits. It's not like a regular computer that one just checks if a bit is 1 or 0 in the middle of the computation. Doing that to a qubit alters its own state and the overall state in an irreversible manner. Moreover, mid-circuit measurements are an engineering nightmare at this moment. If you leave all the measurements to the end of the circuit, it's still irreversible. If you don't measure at all,, you're left with a quantum state that has some information in it but you don't know what it is because you didn't measure. If you run a computation and then undo and then measure, you might as well have done nothing because there's no information to be gained since you're in the same state you started with.

So what is the point of only running reversible operations?

[u/Chance-Pen-5684 → u/CapitalismSuuucks]

I think we might be talking about slightly different things when I say reversible.
I don’t mean running the computation, getting an answer, then chucking the whole thing into reverse and wiping out the result. That would rather defeat the point.

What I mean is whether the physical computation itself can proceed reversibly, without having to irreversibly erase or reset the physical state each time it moves from one operation to the next.
You’d still measure the useful output at the end, of course.

So I suppose the real question is, before that final measurement, is there anything fundamentally stopping the complete physical system from evolving reversibly throughout the entire computation?

[u/Temporary_Shelter_40 → u/Chance-Pen-5684]

i'm lost man, i have no idea what you mean or are trying to get at

[u/Chance-Pen-5684 → u/Temporary_Shelter_40]

Basically can the computer get from input to output without irreversibly resetting any of its internal physical state along the way.

[u/CapitalismSuuucks → u/Chance-Pen-5684]

Are you asking if qubits can return to the original state if left alone long enough? And not only that, but return to it by taking the reverse path that got them to the current state?

In a perfect world, no. If no operation acts on the quantum system, then it doesn't interact with anything and stays stationary.

In the real world, the quantum system is interacting with an environment. It will eventually be dumped into a trivial classical state that is not the original state and all information is lost. This is why error correction is needed.

[u/Chance-Pen-5684 → u/CapitalismSuuucks]

Not quite. I don’t mean leaving it alone and waiting for it to spontaneously run backwards.
I mean can we design the dynamics so the computation goes forwards from input to output without irreversibly resetting its internal physical state along the way?
Basically, can each physical output become the next physical input without a reset?

[u/QuantumCakeIsALie]

Making a circuit reversible is not sufficient to make it efficient.

The "erasure" associated dissipation is a tiny tiny part of the heat output of contemporary transistors. You'd likely increase the heat output and inefficiency of a classical transistor based circuit by making it reversible, because of the hardware overhead.

[u/Chance-Pen-5684 → u/QuantumCakeIsALie]

That makes sense for ordinary transistor circuits. But is that really a limitation of reversible computing itself, or more a case of trying to make it work with hardware that was never built to be physically reversible in the first place?
If you designed the physical system around reversible dynamics from the ground up, what would actually be the main source of heat? Where would the losses creep in?

[u/QuantumCakeIsALie → u/Chance-Pen-5684]

That's a limitation of transistors.

Superconducting Josephson logic (however it's called) could in principle be closer to perfect efficiency by being reversible. But it's wildly inefficient because of the cooling.

Thermodynamics really is your enemy here.

[u/CarbonIsYummy]

Yes, it is possible to make reversible digital circuits for classical computers. No, this isn’t a good idea. Part of the problem is that a lot of the energy your CPU uses is just from moving information around. That’s totally reversible yet doesn’t result in anything useful.

The other big issue would be memory. Right now CPUs compute “a+b=c” using tiny amounts of memory. You can almost do it with just the amount of memory needed to store “a” and “b” alone. A reversible computer would need to keep track of “a” and “b” and “c” for every step in the calculation. Adding is one of the most common instructions, and most modern CPUs can do at least 2-3 billion additions per second. Where are you going to store that extra gigabyte of memory every second? If you erase that memory the computer isn’t reversible anymore

[u/Kinexity]

Majority of energy waste comes for resistance related heat emissions (iirc just clock signal propagation is like a quarter of energy use). We don't have classical reversible logic gates and quantum ones obviously don't have the fidelity necessary. Logical reversibility does not imply thermodynamic reversibility. Quantum gates are probably very inefficient once you include the energy used to drive the cooling setup and the fact that they take way longer to perform any operation than transistor gates.

We don't have the technology to build efficient reversible computers. It just doesn't exist. There is no conspiracy here.