6
$\begingroup$

In quantum computing, there is famous "law" which is to say that all the computation must be reversible. I understand that, for simplicity, it may be easier to consider reversible operation, and that they are general enough to make us happy to stick to these reversible circuits, and if necessary, perform the measurements at the very end. However I don't see why it would need to be reversible all the time. I read lot's of random answers on the internet, and none of them convince me. For example, the other question on Phys.SE states that

quantum mechanics is reversible (and even more specifically it is unitary). [...] Even measurement can be modeled as a reversible unitary operation, inconvenient though that may be.

And the measurement is exactly the thing that disturb me, and "breaks" for me the reversible property of quantum mechanics.

For example, let us imagine that I create, in my lab, a "gate" that project one qubit into the canonical (computational) basis, which is already completely possible. Then if I get $|0\rangle$ , I won't be able to know if I had at the beginning, for example $|0\rangle$ or $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$.

And even the formalism based on density matrix and CPTP maps (Completely Positive Trace Preserving maps) cannot explain this, because if I consider the above "gate", then the CPTP map associated would be $M: \rho \rightarrow |0\rangle\langle0|\rho|0\rangle\langle0| + |1\rangle\langle1|\rho|1\rangle\langle1|$, which, basically, forget all the information contained in the two inverse diagonal coefficients of $\rho$: $\rho_{1,0}$ and $\rho_{0,1}$, so has no chance to be invertible.

So can anyone explain me precisely what we have in mind when we say that quantum computation need to be reversible?

-- EDIT --

To answer ACuriousMind question about references for the "law", you can find lot's of courses that make this kind of assumption that quantum computation is always unitary, like this one that states on first page, section 2, first line of the section:

Quantum evolution is unitary; a quantum circuit corresponds to a unitary operator $U$ acting on kets in $\mathcal{C}^{2n}$.

The affirmation "Quantum evolution is unitary" looks pretty general.

In research paper you also see lot's of things about reversible quantum gates. On this one for example they say page 4 section 4 second paragraph:

Unlike many classical logic gates, quantum logic gates are reversible.

And the first thing that a reader will understand is that all the quantum gates are reversible, so it exists no irreversible quantum gate, so because all the circuits could be "packed" as a new quantum gate, then there exists no irreversible quantum circuit... Which is quite disturbing.

And I don't even talk about forums that try to prove by "reductio ad absurdum" that the gates must be unitary...

$\endgroup$
  • 4
    $\begingroup$ Measurement is not reversible. By a long stretch of imagination, and mostly faith, some people claim that it can be described as a unitary operation, but last time I checked there was no proof of that. Of course you can always redefine measurement in such a theoretical way that, according to a specific interpretation of QM, it is unitary (for example considering that one never leaves some wildly hypothetical "wave function of the universe"). But experimentally, and for all practical purposes, measurement is not reversible. $\endgroup$ – Stéphane Rollandin Mar 15 '18 at 14:14
  • $\begingroup$ A quantum gate is not a measurement, it's by definition a unitary operation on the current state of some qubits. I don't understand what exactly the question here is supposed to be - if you do an "irreversible" measurement somewhere in between, you're by definition not doing a "quantum computation", but something different. Perhaps you could add some references to this alleged "law"? $\endgroup$ – ACuriousMind Mar 15 '18 at 17:51
  • $\begingroup$ @ACuriousMind yes, but most of the time people do not talk just about gate (and even if they do, why don't we also include in the gates the non invertible ones, just like in classical computing ?), but about a whole computation, so I just wanted to make sure that in some strange definitions one could not consider all the computation as reversible. Indeed, in 99% of the time we consider algorithm as unitaries, and that's all, as you can see in the references I added at the end of my question. But I guess that now I have my answer! $\endgroup$ – tobiasBora Mar 15 '18 at 18:56
  • $\begingroup$ The wikipedia entry is very clear on the fact that measurement is not a quantum gate: en.wikipedia.org/wiki/Quantum_gate#Measurement $\endgroup$ – Stéphane Rollandin Mar 15 '18 at 19:11
2
$\begingroup$

The deferred measurement principle is a mathematical theorem that basically says that WLOG you can always move all measurements to the very end of the quantum circuit without changing anything important. Making measurements as intermediate rather than final steps is never helpful in a fully coherent quantum circuit. So you can always assume that you never measure anything until the very end, and up until that measurement everything must be unitary and therefore reversible.

$\endgroup$
  • $\begingroup$ Well yes, I know that you cannot force a given output (that's basically the assumption PostBQP != BQP), I was just saying that we define the trivial projection on the basis {|0>,|1>}, I did not say that I wanted to force the output to be |0>, it can be either |0> or |1>. And actually I'm not sure to understand what you mean about MBQC and decoherence (I've always used MBQC in an environment with no noise). $\endgroup$ – tobiasBora Mar 16 '18 at 1:47
  • $\begingroup$ @tobiasBora Sorry, I misread you question. I deleted part of my answer which is no longer relevant. I also deleted my MBQC comment because I'm not familiar enough with that field to be sure I'm right. $\endgroup$ – tparker Mar 16 '18 at 2:17
  • $\begingroup$ My question would be why should unitary operators only be used to describe operations then? I think this answer is the other way around - we use unitaries to describe computations because they are reversible, not that we decided that unitaries should describe the operation arbitrarily, and then realise because they are described a unitary they need to be reversible. $\endgroup$ – Mahathi Vempati Jul 6 '18 at 11:57
  • 1
    $\begingroup$ @Tinkidinki No, the fact that time-evolution is unitary is definitely more fundamental than the fact that it's reversible. The unitarity comes first logically, and follows directly from the Schrodinger equation. Also, in your bounty text, the hypothetical gate that you describe is irreversible - did you mean to say "irreversible" instead of "reversible"? $\endgroup$ – tparker Jul 6 '18 at 16:56
1
$\begingroup$

There are models of quantum computation other than the gate based schemes mentioned in the comments. In general these models do not have to be reversible. For example, measurement based quantum computing is based on first preparing a highly entangled resource state, and then performing measurements on it to perform the computation. These measurements are irreversible, yet the scheme still performs quantum computation. Indeed, it is equivalent to the gate based model of quantum computation.

$\endgroup$
1
$\begingroup$

This is just my speculation, rather than a definitive answer, but you might find it interesting.

You can represent logic gates using mechanical systems where information is transmitted by marbles or billiard balls (e.g. https://en.wikipedia.org/wiki/Billiard-ball_computer). Consider an XOR gate made this way. It has two 'input' holes for balls to go in, leading into a tunnel which is only wide enough for one ball to fit through, which goes to the 'output' hole. If a single ball is sent through at one time, a single ball comes out of the output. If balls are sent in both of the inputs at the same time, they collide and get stuck, and nothing comes out at the output. Importantly, they are not allowed to go back out through the input holes in the second situation; they come to rest inside the gate.

When the balls come to rest, physically we say that their energy has been dissipated as heat. But if we really wanted to, we could look at the molecules that make up the balls, and track down where the kinetic energy went exactly. Then we wouldn't call this energy 'heat', but would describe it as kinetic energy of a bunch of molecules. So saying that the energy has been dissipated as heat really just means we have given up on tracking the full dynamics of the system. Therefore we have lost the ability to reverse the dynamics; we can't infer where the balls started from a macroscopic description of where they ended up. To do that, we would need a microscopic description of where they ended up, including all of their constituent molecules.

Now we want to make a 'quantum' version of the same logic gate, which operates on individual electrons or photons or something like that. If Particle A and particle B go into the two inputs at the same time, they are supposed to get stuck in the gate so that nothing comes out from any of the holes. If this happens, the energy has been dissipated as heat, again meaning that we don't know precisely where the energy went. But because the particles are not made up of any smaller particles, this means we must have lost track of them entirely. How can this be? The interactions of the particles are well understood physically, and the initial conditions were controlled, but the final state is unknown.

Therefore we simply don't know enough about the logic gate that we built to figure out what happened to the particles we sent into it. In this sense, an irreversible gate is simply a system whose action on quantum particles is not known to enough precision to reliably predict its dynamics. And therefore it is not useful as a logic gate; even if we send in only a single particle at a time, the behavior will still be unpredictable. If we were able to predict what would happen when we sent a single particle in, we would be able to predict what would happen when we sent two particles in, but we can do neither.

$\endgroup$
  • $\begingroup$ 'To do that, we would need a microscopic description of where they ended up, including all of their constituent molecules.' - You would need a microscopic description of the system as a whole, including the air molecules in the pipe, maybe. This would help you reverse the computation. I don't see why the electrons are any different. You would need a microscopic description of the system (of air molecules around the electrons included) which will help you reverse the reaction. But what has this got to do with making non-unitary (reversible) functions? $\endgroup$ – Mahathi Vempati Jul 6 '18 at 12:11
  • $\begingroup$ For a macroscopic system which dissipates heat we can generally evolve the dynamics forwards but not backwards (i.e. it is irreversible). This only works when considering motion "averaged over" large numbers of particles. For a logic gate this means that the inputs uniquely determine the outputs but the outputs do not uniquely determine the inputs. But for a quantum system with only a few particles, if we can't reliably evolve it backwards then we can't evolve it forwards either; if the inputs can't be inferred from the outputs than the outputs will not be consistent functions of the inputs. $\endgroup$ – Maxwell Aifer Jul 8 '18 at 1:01
1
$\begingroup$

So can anyone explain me precisely what we have in mind when we say that quantum computation need to be reversible?

I think it's simply referring to the conservation of the probabilistic interpretation of the wavefunction.

Take a generic qubit:

$$|\psi>=\alpha |0>+\beta |1>$$

Given the probabilistic interpretation we know that $||\psi>|^2= |\alpha|^2 + |\beta|^2 =1$. To conserve this probability, any operator acting on it must be unitary. By definition of unitarity, it exist an inverse operator.

Therefore the operation must be reversible.

$\endgroup$
  • $\begingroup$ Well you can always do a measurement, on this state, that will bring the state to $|0\rangle$ or $|1\rangle$ and you won't be able to come back to the initial $| \phi \rangle$ without additional knowledge on $|\phi \rangle$... $\endgroup$ – tobiasBora Jul 4 '18 at 10:36
  • $\begingroup$ Indeed, I'm not including the measurements inside the quantum computations. $\endgroup$ – Rexcirus Jul 4 '18 at 19:45
  • $\begingroup$ I don't need a unitary function to conserve probability. Consider any function that is many to one, such that the range consists of valid qubits. For example (If alpha<0.3, it takes the state to |0>, otherwise to |0x>). This is not unitary but conserves probability. $\endgroup$ – Mahathi Vempati Jul 6 '18 at 12:05
  • $\begingroup$ I don't understand your example, what is the action of this operator on the basis $(|0>,|1>)$? $\endgroup$ – Rexcirus Jul 7 '18 at 14:03

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.