# 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.

10 questions
Filter by
Sorted by
Tagged with
146 views

### Is it known that Clifford circuits are not universal for classical computation?

I'm interested in whether there is some known result about Clifford circuits being insufficent for classical computation. Aaronson and Gottesman in their 2004 paper Improved Simulation of Stabilizer ...
1 vote
84 views

### Does the Bell's state entanglement violate the reversibility property of unitary matrices?

I read unitary matrices are reversible, so when we apply a unitary operator $U$ on some input state and got an output state, then if we apply $U^\dagger$ (transpose conjugate) we get back the original ...
285 views

### How does one convert a truth table to a square permutation matrix?

Given a classical circuit of $m$ inputs and $n$ outputs, composed of various AND gates, OR gates, NOT gates, etc., a truth table is a $2^{m}\times(m+n)$-sized matrix, where, in general, the first $m$ ...
366 views

### Thermodynamic Speed Limit to Quantum Computing

There's a lot of mystifying jargon in the field of quantum computation, so I would like to examine some elementary physics to maybe help clarify the assumptions being made. Is it not true that the ... 161 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 ...
209 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 ...
146 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$...
816 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 ...
1 vote
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 ...