3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ There is the energy consumption advantage already mentioned in the article. $\endgroup$ – AHusain Jan 27 at 1:04
  • $\begingroup$ @AHusain True. But I'm not interested in the energy consumption advantage at the moment. I've modified the question. $\endgroup$ – Sanchayan Dutta Jan 27 at 1:06
  • $\begingroup$ Are you asking whether all quantum logical operations must be reversible? The answer is yes (except measurement). $\endgroup$ – ahelwer Jan 27 at 2:13
  • $\begingroup$ @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)? $\endgroup$ – Sanchayan Dutta Jan 27 at 7:31
4
$\begingroup$

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


Original Answer

No. Usually, we phrase quantum algorithms in terms of unitaries (reversible) plus measurements (not reversible). You might even argue that for many algorithms, with a deterministic output, the final measurement does nothing, and hence does not do anything irreversible.

However, this is partially the fault of the gate model which hides measurement at the end. In fact, there is some degree of choice about trading off between the two. For example, measurement-based computation implements one very simple unitary operation that may have nothing to do with the computation to be performed, and then the computation itself is specified by the measurement choices, and the measurements also detect the outcomes. This extreme certainly shows that it is not necessary to have reversibility.

$\endgroup$
  • $\begingroup$ Interesting point. I am not acquainted with MBQC, but you say that even in MBQC a simple unitary operation (albeit it may have nothing to do with the computation to be performed) is used at the beginning. Isn't that unitary (reversible) operation a necessity for that computation? Or can there be computations in that model which doesn't make use of unitaries at all (in any stage)? $\endgroup$ – Sanchayan Dutta Jan 27 at 7:36
  • $\begingroup$ You could use measurements to prepare the initial state, but that would make the computation inefficient. Another option is that the state that you want to prepare is the ground state of a particular Hamiltonian. So you could use a cooling process to prepare the state, and that’s not reversible. $\endgroup$ – DaftWullie Jan 27 at 8:11
  • $\begingroup$ Perhaps I was actually misinterpreting your question. Were you wanting to know whether the whole computation has to be unitary, or whether you have to have a unitary operation somewhere in the computation? $\endgroup$ – DaftWullie Jan 27 at 8:12
  • $\begingroup$ If it’s the latter, you may be interested in arxiv.org/abs/0803.1447 $\endgroup$ – DaftWullie Jan 27 at 8:16
  • $\begingroup$ That was my point: using only irreversible logic operations to execute quantum algorithms would make them inefficient (note the term "efficiently" in the question title) and render the quantum speedup useless. "Were you wanting to know whether the whole computation has to be unitary, or whether you have to have a unitary operation somewhere in the computation?" - yes, I was talking about the latter! $\endgroup$ – Sanchayan Dutta Jan 27 at 8:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.