<p>As I mentioned in my comment above, and as you allude to in the question, every computation can be made reversible, and by simply retaining the extra bits, there is no inherent thermodynamic cost.</p>

<p>Every circuit generated by using Toffoli gates and ancillas to replace irreversible gates becomes as efficient to reverse as it is to compute assuming you have access to all output bits. This is clearly not the case for the functions considered in cryptography, since many ancillae are used and discarded. It is by keeping secret this extra bits that makes the computation hard to reverse.</p>

<p>However, by computing the function reversibly, making a copy of the subset of bits corresponding to the output, and then inverting the function the total energy cost for computing and inverting the function will be zero, while the only cost incurred will be in making the copy of the output bits, which depends only on the number of output bits and not the function being computed. This is clearly the best you can do, since it costs the same energy as simply writing the output string to an empty register.</p>

<p>Turning to your restated question:</p>

<blockquote>
  <p>"Are there any trapdoor one-way
  functions that can be implemented
  using only reversible logical
  operations, without additional scratch
  space?"</p>
</blockquote>

<p>The answer is trivially no. If you apply the inverse of each gate in reverse order you compute the inverse of the function. Assuming a model where gates act on a fixed number of qubits at a time, then the inverse of each elementary reversible gate can be applied in constant time. Hence such a function is as easy to invert as to compute (up to a multiplicative constant), and hence is not a trapdoor function.</p>

CC BY-SA 3.0
2011-05-14T02:27:49.933Z
Is it safe to say that "inherent thermodynamic cost of $f$" is synonymous with "fewest ancilla bits needed to implement $f$ reversibly"? If so, is this already a measure of complexity studied in the quantum community?
mikero
CC BY-SA 3.0
2011-05-14T12:15:32.570Z
@mikero: No, it isn't safe to say this. I've added a paragraph to my answer above to try to make this clearer. The cost depends only on the output size and not on any other property of $f$, which is a rather trivial complexity measure!
Joe Fitzsimons
CC BY-SA 3.0
2011-05-16T15:47:45.553Z
@mikero: you need some energy to initialize all the ancilla bits to a known initial state, but since at the end of the computation all the ancilla bits have returned to the same known initial state, you can recover that energy.
Antonio Valerio Miceli-Barone
CC BY-SA 3.0
2011-05-13T23:30:59.677Z
2011-05-14T12:14:02.167Z
2011-05-14T12:14:02.167Z
Joe Fitzsimons
<p><strong>Reversible computing</strong> is a computational model that only allows
thermodynamically reversible operations.  According to Landauer's
principle, which states that erasing a bit of information releases $kT 
\ln(2)$ joules of heat, this rules out transition functions that are not
one-to-one (e.g., the Boolean AND and OR operators).  It is well known
that quantum computation is inherently reversible because the allowed
operations in quantum computation are represented by unitary matrices.</p>

<p>This question is about cryptography.  Informally, the notion of "reversibility" seems anathema to the fundamental goals of cryptography, thus suggesting the question: "Does cryptography have an inherent thermodynamic cost?"</p>

<p>I believe that this is a different question than, "Can everything be done in quantum?"</p>

<p>In his <a href="http://www.theory.caltech.edu/people/preskill/ph229/notes/chap6.ps" rel="noreferrer">lecture notes</a>, Dr. Preskill states,  "There is a general strategy for simulating an irreversible computation on a reversible computer. Each irreversible gate can be simulated by a Toffoli gate by fixing inputs and ignoring outputs.  We accumulate and save all 'garbage' output bits that are needed to reverse the steps of the computation."  </p>

<p>This suggests that these reversible quantum simulations of irreversible operations take an input as well as some "scratch" space. Then, the operation generates output along with some "dirty" scratch bits. The operations are all reversible with respect to the output plus garbage bits, but at some point, the garbage bits are "thrown away" and not considered further.</p>

<p>Since cryptography depends on the existence of trapdoor one-way
functions, an alternative statement of the question might be, "Are
there any trapdoor one-way functions that can be implemented using
only reversible logical operations, without additional scratch space?"  If so, is it also possible to COMPUTE an arbitrary trapdoor one-way function using only reversible operations (and no scratch space)?</p>

CC BY-SA 3.0
2011-05-13T22:43:24.237Z
an interesting question.
Suresh Venkat
CC BY-SA 3.0
2011-05-13T22:52:58.837Z
Presumably this question only applies to public-key cryptography. Can't symmetric cryptosystems (such as DES) be made entirely reversible?
Peter Shor 
CC BY-SA 3.0
2011-05-14T12:07:34.193Z
Damn, I wrote that last comment too late at night, and made a mess of it. What I should have said was that the thermodynamic cost is independent of the size of the scratch space for both public and private key systems, since you can simply perform the reversible computation, copying the output bits (but not the scratch space) to an ancilla register, and then reverse the original computation (uncomputing everything in the scratch space).
Joe Fitzsimons
<cr.crypto-security><quantum-computing><big-picture><physics><quantum-information>
Does cryptography have an inherent thermodynamic cost?
rphv
# Does cryptography have an inherent thermodynamic cost?

(Asked by: username_0 on 2011-05-13)

**Reversible computing** is a computational model that only allows
thermodynamically reversible operations. According to Landauer's
principle, which states that erasing a bit of information releases $kT
\ln(2)$ joules of heat, this rules out transition functions that are not
one-to-one (e.g., the Boolean AND and OR operators). It is well known
that quantum computation is inherently reversible because the allowed
operations in quantum computation are represented by unitary matrices.

This question is about cryptography. Informally, the notion of "reversibility" seems anathema to the fundamental goals of cryptography, thus suggesting the question: "Does cryptography have an inherent thermodynamic cost?"

I believe that this is a different question than, "Can everything be done in quantum?"

In his [lecture notes](http://www.theory.caltech.edu/people/preskill/ph229/notes/chap6.ps), Dr. Preskill states, "There is a general strategy for simulating an irreversible computation on a reversible computer. Each irreversible gate can be simulated by a Toffoli gate by fixing inputs and ignoring outputs. We accumulate and save all 'garbage' output bits that are needed to reverse the steps of the computation."

This suggests that these reversible quantum simulations of irreversible operations take an input as well as some "scratch" space. Then, the operation generates output along with some "dirty" scratch bits. The operations are all reversible with respect to the output plus garbage bits, but at some point, the garbage bits are "thrown away" and not considered further.

Since cryptography depends on the existence of trapdoor one-way
functions, an alternative statement of the question might be, "Are
there any trapdoor one-way functions that can be implemented using
only reversible logical operations, without additional scratch space?" If so, is it also possible to COMPUTE an arbitrary trapdoor one-way function using only reversible operations (and no scratch space)?

**Tags:** cr.crypto-security, quantum-computing, big-picture, physics, quantum-information

> **Comments:**
> **username_1**: an interesting question.  
> **username_2**: Presumably this question only applies to public-key cryptography. Can't symmetric cryptosystems (such as DES) be made entirely reversible?  
> **username_3**: Damn, I wrote that last comment too late at night, and made a mess of it. What I should have said was that the thermodynamic cost is independent of the size of the scratch space for both public and private key systems, since you can simply perform the reversible computation, copying the output bits (but not the scratch space) to an ancilla register, and then reverse the original computation (uncomputing everything in the scratch space).  

---

## 1 answers

### Answer by username_3 on 2011-05-13. Score: 15

As I mentioned in my comment above, and as you allude to in the question, every computation can be made reversible, and by simply retaining the extra bits, there is no inherent thermodynamic cost.

Every circuit generated by using Toffoli gates and ancillas to replace irreversible gates becomes as efficient to reverse as it is to compute assuming you have access to all output bits. This is clearly not the case for the functions considered in cryptography, since many ancillae are used and discarded. It is by keeping secret this extra bits that makes the computation hard to reverse.

However, by computing the function reversibly, making a copy of the subset of bits corresponding to the output, and then inverting the function the total energy cost for computing and inverting the function will be zero, while the only cost incurred will be in making the copy of the output bits, which depends only on the number of output bits and not the function being computed. This is clearly the best you can do, since it costs the same energy as simply writing the output string to an empty register.

Turning to your restated question:

> "Are there any trapdoor one-way
> functions that can be implemented
> using only reversible logical
> operations, without additional scratch
> space?"

The answer is trivially no. If you apply the inverse of each gate in reverse order you compute the inverse of the function. Assuming a model where gates act on a fixed number of qubits at a time, then the inverse of each elementary reversible gate can be applied in constant time. Hence such a function is as easy to invert as to compute (up to a multiplicative constant), and hence is not a trapdoor function.

> **Comments:**
> **username_4**: Is it safe to say that "inherent thermodynamic cost of $f$" is synonymous with "fewest ancilla bits needed to implement $f$ reversibly"? If so, is this already a measure of complexity studied in the quantum community?  
> **username_3**: @username_4: No, it isn't safe to say this. I've added a paragraph to my answer above to try to make this clearer. The cost depends only on the output size and not on any other property of $f$, which is a rather trivial complexity measure!  
> **username_5**: @username_4: you need some energy to initialize all the ancilla bits to a known initial state, but since at the end of the computation all the ancilla bits have returned to the same known initial state, you can recover that energy.  

---

