Questions tagged [reversible-computation]
For questions related to reversible computing, i.e. computing models where each elementary operation (and hence every computation) can be undone.
6
questions
2
votes
0
answers
67
views
What role does Landauer's principle play in quantum reversibility?
In section 3.2.5 of Nielsen and Chuang (starting page 153) they talk about Landauer’s principle, where they discuss the lower bound on the thermodynamic cost of erasing information.
In irreversible ...
2
votes
1
answer
60
views
"Bennett’s trick" for reversible circuits
A textbook approach, attributed to Charlie Bennett, for creating reversible circuit which outputs the input qubits and the initialized ancilla qubits involves copying the function output between the ...
- 21
3
votes
1
answer
80
views
How to build a quantum circuit of a given reversible function?
Given a function $f : \{0,1\}^n \longrightarrow \{0,1\}^m$ and a function $g : \{0,1\}^m \longrightarrow \{0,1\}^n$ that both can be computed by polynomial-size classical circuits such that $g(f(x))=x$...
- 129
6
votes
2
answers
422
views
How universal is the Toffoli gate for classical reversible computing?
It is easy to see that no finite set of classical reversible gates can be strictly universal (without ancilla) for classical reversible computation: for any reversible gate on $n$ bits, in its action ...
- 223
1
vote
2
answers
71
views
Can there be different gate implementations of same oracle implementation?
I have been reading about Bernstein-Vazirani Algorithm, and it uses what is known as a phase oracle. Basically, it is CNOT gate with several controls attached to the ancilla qubit $|-\rangle$ (it is ...
- 197
4
votes
0
answers
79
views
Universality for reversible classical computation
Is there any way to check whether a set of gates (for example, take the set comprising of the CNOT gate and the Hadamard gate) is universal for reversible classical computation?
I can think of trial ...
- 943