5 votes

How universal is the Toffoli gate for classical reversible computing?

I've seen claims that a single ancillary bit suffices to make the Toffoli gate universal; is there a good reference for that? See this blog post: With a single ancilla, you can do an operation that ...
Craig Gidney's user avatar
4 votes

How to build a quantum circuit of a given reversible function?

I assume you know how to turn a classical circuit that computes $f$ into a quantum circuit that computes $|x,\,y\oplus f(x)\rangle$ from $|x,y\rangle$, since that should be covered in any introduction ...
benrg's user avatar
  • 818
3 votes
Accepted

How universal is the Toffoli gate for classical reversible computing?

It turns out Toffoli + NOT is universal for alternating permutations of bit-strings for $n \ge 4$. The construction of a $\mathrm{C}^n\mathrm{NOT}$ gate with one borrowed bit (starting in unknown ...
Dylan Thurston's user avatar
3 votes
Accepted

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

In the standard convention, a state $|\psi\rangle$ is a column vector and operator $M$ is left multiplied with the state for evolution, i.e $M|\psi\rangle = |\phi\rangle$. In this convention, the (row,...
3 votes

Thermodynamic Speed Limit to Quantum Computing

I think there's some difficulty in communication and a lack of common language between physics and computer science, that make the question hard to answer. But I'll try to give some the computer ...
Mark Spinelli's user avatar
2 votes

What role does Landauer's principle play in quantum reversibility?

That is not directly related. Heat and noise can ruin classical information in a classical computer too. In practice that's not such a problem because classical information, unlike quantum information,...
John Gardiner's user avatar
2 votes
Accepted

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

As far as I know, there is no way to violate the reversibility property because, given a valid quantum state $| \psi \rangle$ and a unitary operator $U$, you will always have that $| \psi \rangle = U^\...
SimoneGasperini's user avatar
1 vote

Do some Hamiltonian simulations require an irreversible process?

The postulate that all quantum evolutions are unitary applies to the case of closed systems. The Lindbladian form comes into picture when we are discussing about open systems. In this case, where ...
HypnoticZebra's user avatar
1 vote

What role does Landauer's principle play in quantum reversibility?

Actually, classical physics is also reversible, whether you're considering classical dynamics or considering it as the limit of quantum physics (which is reversible). The means for neither classical ...
Sam Jaques's user avatar
  • 2,024
1 vote

"Bennett’s trick" for reversible circuits

Yes, it will work fine. If a classical reversible circuit works on every classical basis state, it will also work on superpositions of those states. Try it in a simulator. Of course, the output qubit ...
Craig Gidney's user avatar
1 vote

Can there be different gate implementations of same oracle implementation?

I am answering my own question as I found an answer. The answer is affirmative, that the standard phase oracle made of CNOT gates and an ancilla qubit can be replaced by Z and I gates by discarding ...
Chetan Waghela's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible