Quantum Computing Stack Exchange
Quantum Computing Stack Exchange

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.

Reversible computing is a type of model of computation in which every computation can be reversed. In other words, not only can the output be computed from the input, but also the input from the output.

13 questions
9
votes
2 answers

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 on $n+1$ bits it induces an even permutation, and…
Dylan Thurston
  • 263
  • 1
  • 7
6
votes
1 answer

To what degree could additional ancilla qubits affect the complexity of a quantum algorithm?

It is a known trick in quantum computing to use additional ancilla qubits and uncomputation to construct efficient quantum circuits. I wonder, are there some rigorous results that estimate how big this effect could be? For example, is it possible to…
Danylo Y
  • 8,076
  • 13
  • 24
6
votes
1 answer

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 speed of a real-world reversible computer scales…
user22003
4
votes
1 answer

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$ for all $x\in\{0,1\}^n$, how can I build a…
omerna
  • 199
  • 3
4
votes
1 answer

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 and error methods, like checking whether we can…
BlackHat18
  • 1,527
  • 9
  • 22
3
votes
0 answers

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 Circuits say the following... Since stabilizer…
Callum
  • 1,260
  • 1
  • 5
  • 24
3
votes
2 answers

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 input state. So, when we apply a Bell's circuit…
Lalit Vinde
  • 45
  • 4
3
votes
1 answer

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$ columns encode the binary inputs while the last…
Mark Spinelli
  • 15,378
  • 3
  • 26
  • 83
2
votes
1 answer

On cyclically shifting an $n$-qubit register conditioned on one of the qubits being $|0\rangle$

This is kind of a follow-up to a prior question on cyclic rotations of the qubits in an $n$-qubit register - the key to that question includes judiciously applying a number of SWAP gates. I'm interested in a small-sized reversible circuit to…
Mark Spinelli
  • 15,378
  • 3
  • 26
  • 83
2
votes
1 answer

Do some Hamiltonian simulations require an irreversible process?

I just stumbled upon this research paper https://arxiv.org/abs/2309.16596. They claim to have found a problem which is easy to solve quantumly but hard classically: to find local minima of 2D Hamiltonians (which turns out to be all the same). From a…
matteo
  • 23
  • 4
2
votes
2 answers

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 computing (i.e. classical computers), we can build…
irritable_phd_syndrome
  • 141
  • 2
2
votes
1 answer

"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 two blocks - the forward and the reverse…
inq
  • 211
  • 2
  • 4
1
vote
2 answers

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 discussed in detail over here link) in the circuit…
Chetan Waghela
  • 408
  • 2
  • 11