# Aren't reversible logic gates a necessity for efficiently executing quantum algorithms?

The Wikipedia article on logical reversibility says:

...reversible logic gates offered practical improvements of bit-manipulation transforms in cryptography and computer graphics.

But I guess that's not all? Aren't reversible logic gates a necessity for the (efficient) execution of quantum algorithms? [1]

To clarify, I'm basically asking this: Isn't the use of reversible operations or unitaries necessary for efficiently executing quantum algorithms? Or are there models of quantum computation which can execute these algorithms efficiently without making use of logically reversible operations at all?

[1]: Inspired from Reversibility and irreversibility of logic gates (quantum vs classical).

• There is the energy consumption advantage already mentioned in the article. – AHusain Jan 27 '19 at 1:04
• @AHusain True. But I'm not interested in the energy consumption advantage at the moment. I've modified the question. – Sanchayan Dutta Jan 27 '19 at 1:06
• Are you asking whether all quantum logical operations must be reversible? The answer is yes (except measurement). – ahelwer Jan 27 '19 at 2:13
• @ahelwer It is well known that quantum algorithms can be represented in terms of unitary quantum gates (reversible) and measurement operations (irreversible according to general interpretation) in the gate model. My question was: is this reversibility or use of unitaries a necessity for efficient (quantum) computation? Or can there be models where reversibility isn't required at all (in any stage of the computation)? – Sanchayan Dutta Jan 27 '19 at 7:31

Originally, I misunderstood the question, and was answering a question like "Is it true that quantum computers are necessarily formulated only out of reversible gates?". However, I now understand that the question was intended to be "Must there always be a reversible step inside a quantum computation?"

No - there are some computational schemes, such as the this paper, in which every computational step can be formulated as a dissipation, which is non-reversible.

Another way to think about it is in terms of the measurement-based model. Here, one must prepare a particular state, and perform a sequence of measurements on it. Usually, we talk about the initial state preparation as a unitary, but that's not necessary. The usual cluster state is the common eigenstate of a set of stabilizers $$\{K_n\}$$ ($$K_n^2=1$$ and $$[K_n,K_m]=0$$). So, imagine you take some initial state of a system, and start measuring sets of qubits according to the stabilizers $$\{K_n\}$$. The state people normally talk about preparing is the +1 eigenstate of all of these. Obviously, it's quite unlikely the we succeed in preparing that. However, we will have a record of which stabilizers gave -1 answers. It's a particular property of these stabilizers that each one anti-commutes with a $$Z$$ on a particular site, while all others commute with that particular $$Z$$. This means that the list of stabilizers with -1 values corresponds to a list of sites with $$Z$$ errors. But, knowing that, we can just incorporate the existence of the $$Z$$ rotations into the measurement bases of the computation. Everything can be achieved through measurements! (Although you require 5-qubit measurements. While not impossible, I think most people would consider implementing them using some unitaries and single-qubit measurements, but the formalism doesn't require it.)