19
$\begingroup$

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, 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)?

$\endgroup$
  • 2
    $\begingroup$ an interesting question. $\endgroup$ – Suresh Venkat May 13 '11 at 22:43
  • 4
    $\begingroup$ Presumably this question only applies to public-key cryptography. Can't symmetric cryptosystems (such as DES) be made entirely reversible? $\endgroup$ – Peter Shor May 13 '11 at 22:52
  • 1
    $\begingroup$ 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). $\endgroup$ – Joe Fitzsimons May 14 '11 at 12:07
14
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – mikero May 14 '11 at 2:27
  • 4
    $\begingroup$ @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! $\endgroup$ – Joe Fitzsimons May 14 '11 at 12:15
  • $\begingroup$ @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. $\endgroup$ – Antonio Valerio Miceli-Barone May 16 '11 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.