2022 Developer Survey is open! Take survey.

# Questions tagged [reversible-computing]

The tag has no usage guidance.

15 questions
Filter by
Sorted by
Tagged with
1 vote
29 views

### Are there any algorithms that become much easier to design & implement in reversible computation settings?

If your program can move backwards (even if just for a preset amount like 10,000 atomic steps), then it's easier to do these things: Undo/Redo history (automatically for everything). This can be a ...
22 views

### How does the circuit depth of a bijective function change if it is optimally rexpressed in terms of larger gates?

Consider a bijective function $f:\{0,1\}^n\rightarrow \{0,1\}^n$. Let $d_k$ be the minimal circuit depth of $f$ when expressed in terms of arbitrary $k$ bit gates (i.e. arbitrary bijective functions ...
61 views

### Would all objects in a reversible computing language be mutable?

Full disclosure, I'm asking this after watching a couple pop science videos; I do not know anything about the actual physics and hardware. I suspect the presenters expected an audience like me because ...
55 views

### Is this statistical group summation unambiguously reversible?

Let $X$ be a finite multisubset of $\mathbb{N}^2$. Let's introduce the following notation: $A$ is a set of all first elements of pairs from $X$ and $B$ is a set of all second elements of pairs from $X$...
33 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 ...
111 views

### How to Implement a reversible OR operator with a Fredkin gate (controlled swap)?

How to implement a reversible OR operator with a Fredkin gate ?
205 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 ...
356 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 ...
114 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 ...
359 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 <...
114 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 ...
575 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 ...
143 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'...
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?