Questions tagged [reversible-computing]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
0answers
15 views

Why isn't energy wasted with reversible computing? Isn't information discarded when we feed the function with a new input?

I understand that irreversible computing consumes energy because it has to "get rid" of outputs which have been used. With reversible computing that information is not "wasted" because with the ...
2
votes
2answers
284 views

Is it possible to make N-way Controlled-NOTs out of Toffoli gates, without extra work bits?

I'm working on exercise 4.29 of Nielsen and Chuang: Find a circuit containing O(n^2) Toffoli, CNOT, and single qubit gates which implements a $C^n(X)$ gate (for n >3), using no work qubits. As ...
3
votes
1answer
51 views
1
vote
0answers
60 views

What is the relation between reversible circuits and invertible functions?

A reversible circuit, if I understand it correctly, is a circuit where every gate in the circuit is invertible, i.e. can simply be “turned in the opposite direction”, so that the entire circuit can in ...
5
votes
0answers
239 views

How Janus (Reversible Programming Language) `if`, `while`, and Update Work

In Reversible Computing, all program statements are reversible. I understand for example that the following: \begin{align} x\ {+}&{=}\ 4\\ y\ {*}&{=}\ x\\ x\ {-}&{=}\ 10 \end{align} Has ...
2
votes
1answer
80 views

Reversible computation and no cloning theorem in quantum computing

I am having a problem in understanding a conflict between reversibility in quantum computation and the No cloning theorem. Given a function f, we construct the reversible version of f by adding ...
2
votes
1answer
108 views

How to prove Landauer's principle [closed]

I have some questions about energy emitted when one bit of information is processed. Landauer's principle states the minimum possible amount of energy required to erase one bit of information is <...
4
votes
0answers
97 views

How to model reversible interactive programs

Reversible programs with finite execution steps are well studied. For example, a Turing machine whose transitions are reversible and halts can be executed backwards consuming its tape in the reverse ...
9
votes
1answer
723 views

What's flawed about the “save-the-input” method of reversible computing?

I'm an undergraduate just beginning to read about reversible computing. I know that, because of Landauer's principle, irreversible computations dissipate heat (and reversible ones do not). I brought ...
3
votes
1answer
139 views

What difference does it make when universal classical gates in quantum computation are reversible but not unitary?

As I've come across Grovers algorithm I dont understand why when computing F(X), which is an oracle function people use classical reversible circuits(toffoli, fredkin) to evaluate the circuit. Why can'...
10
votes
1answer
447 views

A programming language that can only implement computable bijective functions?

Are there programming languages(or logic) that can implement(or express) a function $f:\mathbb{N}\to \mathbb{N}$ if and only if $f$ is a computable bijective functions?