<p>I'm interested in the (pre)history of quantum computing, especially in light of the work of physicists and engineers who studied reversible computing in the 60's through the late 70's/early 80's.  This work illustrated non-trivial reductions between languages based on circuits built with standard, irreversible gates and those with reversible logic gates.</p>
<p>We may have:</p>
<ul>
<li><a href="https://ieeexplore.ieee.org/document/5392446" rel="nofollow noreferrer">Landauer</a> noted that functions built with reversible circuits were not wholly vacuous or trivial, and were objects of interest in their own right;</li>
<li>Following Landauer, <a href="https://link.springer.com/article/10.1007/BF01857727" rel="nofollow noreferrer">Toffoli and Fredkin</a> reduced any reversible circuit to an irreversible one, based on the universality of the CCNOT (Toffoli) and CSWAP (Fredkin) gates;</li>
<li><a href="https://www.cc.gatech.edu/computing/nano/documents/Bennett%20-%20The%20Thermodynamics%20Of%20Computation.pdf" rel="nofollow noreferrer">Bennett</a> realized that to make a circuit reversible, it suffices to copy the input of the circuit to the output; and</li>
<li>Any garbage picked up along the way from this copying can be removed with the trick of <a href="https://en.wikipedia.org/wiki/Uncomputation#cite_note-1" rel="nofollow noreferrer">uncomputation</a>.</li>
</ul>
<p>Indeed, reading the above broadly and with the benefit of hindsight, and letting &quot;<strong>RevP</strong>&quot; be a placeholder denoting the class of languages decidable with a polynomial-sized uniform circuit of Toffoli and Fredkin gates, we might be able to say this work showed that &quot;<strong>P<span class="math-container">$=$</span>RevP</strong>&quot;, because:</p>
<ol>
<li>Every reversible circuit built with CCNOT/CSWAP gates can be rewritten using AND, OR, and NOT gates (<strong>RevP</strong><span class="math-container">$\subseteq$</span><strong>P</strong>) with polynomial overhead, and</li>
<li>Every circuit constructed with AND, OR, and NOT gates can be rewritten using CCNOT or CSWAP gates (<strong>P</strong><span class="math-container">$\subseteq$</span><strong>RevP</strong>), with polynomial overhead, by using uncomputation.</li>
</ol>
<blockquote>
<p>Is there a better, or more commonly used, name for what I call &quot;<strong>RevP</strong>&quot; above, even knowing that it's precisely equal to <strong>P</strong>?</p>
</blockquote>
<p>The connection to quantum computing is clear - Feynman and others showed that <strong>RevP</strong><span class="math-container">$\subseteq$</span><strong>BQP</strong> because the Toffoli and Fredkin gates are unitary, while conjecturing that <strong>RevP</strong><span class="math-container">$\subsetneq$</span><strong>BQP</strong> because &quot;nature isn't classical, dammit!&quot;</p>
<p>Of course the work is interesting precisely because <strong>RevP</strong> is at least as powerful as, but no more powerful than, <strong>P</strong>.    But as far as I can tell, the physicists didn't appear to name this class prior to showing that it was equal to <strong>P</strong>.</p>

CC BY-SA 4.0
2022-07-26T00:19:03.187Z
I don't think it has a name, precisely because it was shown equivalent to P so close to when people started studying it. Possibly of interest: https://doi.org/10.4230/LIPIcs.ITCS.2017.23 (classification of clones of reversible gates) and https://doi.org/10.1145/2591796.2591874 (catalytic computation, which can return arbitrary garbage ancilla bits back to their original state, yet still leverage the bits for nontrivial computation)
Joshua Grochow
CC BY-SA 4.0
2022-07-26T01:55:46.350Z
Thanks! I think that’s about right- it’s only in hindsight that we can say this class *could* have been named something other than P, prior to being shown to be equal to P. Like if IP were immediately shown to be PSPACE, then would we care what the names were? Also, I was aware of the first link, but not of the second!
Mark S
<quantum-computing><ho.history-overview><reversible-computing>
Is there a name for the class of languages based on reversible circuits, as studied by the physicists of the late 70's/early 80's?
Mark S
# Is there a name for the class of languages based on reversible circuits, as studied by the physicists of the late 70's/early 80's?

(Asked by: username_0 on 2022-07-25)

I'm interested in the (pre)history of quantum computing, especially in light of the work of physicists and engineers who studied reversible computing in the 60's through the late 70's/early 80's. This work illustrated non-trivial reductions between languages based on circuits built with standard, irreversible gates and those with reversible logic gates.

We may have:

* [Landauer](https://ieeexplore.ieee.org/document/5392446) noted that functions built with reversible circuits were not wholly vacuous or trivial, and were objects of interest in their own right;
* Following Landauer, [Toffoli and Fredkin](https://link.springer.com/article/10.1007/BF01857727) reduced any reversible circuit to an irreversible one, based on the universality of the CCNOT (Toffoli) and CSWAP (Fredkin) gates;
* [Bennett](https://www.cc.gatech.edu/computing/nano/documents/Bennett%20-%20The%20Thermodynamics%20Of%20Computation.pdf) realized that to make a circuit reversible, it suffices to copy the input of the circuit to the output; and
* Any garbage picked up along the way from this copying can be removed with the trick of [uncomputation](https://en.wikipedia.org/wiki/Uncomputation#cite_note-1).

Indeed, reading the above broadly and with the benefit of hindsight, and letting "**RevP**" be a placeholder denoting the class of languages decidable with a polynomial-sized uniform circuit of Toffoli and Fredkin gates, we might be able to say this work showed that "**P$=$RevP**", because:

1. Every reversible circuit built with CCNOT/CSWAP gates can be rewritten using AND, OR, and NOT gates (**RevP**$\subseteq$**P**) with polynomial overhead, and
2. Every circuit constructed with AND, OR, and NOT gates can be rewritten using CCNOT or CSWAP gates (**P**$\subseteq$**RevP**), with polynomial overhead, by using uncomputation.

> Is there a better, or more commonly used, name for what I call "**RevP**" above, even knowing that it's precisely equal to **P**?

The connection to quantum computing is clear - Feynman and others showed that **RevP**$\subseteq$**BQP** because the Toffoli and Fredkin gates are unitary, while conjecturing that **RevP**$\subsetneq$**BQP** because "nature isn't classical, dammit!"

Of course the work is interesting precisely because **RevP** is at least as powerful as, but no more powerful than, **P**. But as far as I can tell, the physicists didn't appear to name this class prior to showing that it was equal to **P**.

**Tags:** quantum-computing, ho.history-overview, reversible-computing
> **Comments:**
> **username_1**: I don't think it has a name, precisely because it was shown equivalent to P so close to when people started studying it. Possibly of interest: https://doi.org/10.4230/LIPIcs.ITCS.2017.23 (classification of clones of reversible gates) and https://doi.org/10.1145/2591796.2591874 (catalytic computation, which can return arbitrary garbage ancilla bits back to their original state, yet still leverage the bits for nontrivial computation)  
> **username_0**: Thanks! I think that’s about right- it’s only in hindsight that we can say this class *could* have been named something other than P, prior to being shown to be equal to P. Like if IP were immediately shown to be PSPACE, then would we care what the names were? Also, I was aware of the first link, but not of the second!  

---

## 0 answers

