# Why do we need reversibility?

Suppose we have qubit $$|a\rangle$$ and we want to implement quantum addition say adding $$|a\rangle$$ and $$|a\rangle$$. When drawing the circuit for this operation one of the outputs that we get is keeping the state $$|a\rangle$$ unaltered for reversibility. But since we know the the sum is just the twice of the state, can't we just keep the sum and nothing else and to get back the original we just half it? Pardon if this question sounds weird.

• It would help if you provide concrete example qbit values and define what you mean by quantum addition. – ahelwer Apr 25 '19 at 19:03
• Classically multiplication by $2$ is merely a shift operation. This is reversible. Certainly you do not want overflow, however. If anything overflows, then you would not be reversible. – Mark S Apr 26 '19 at 0:55

## 2 Answers

There is a standard way for constructing a function evaluation $$f(x)$$ in a reversible manner: you define a circuit that acts $$|x\rangle|y\rangle\mapsto |x\rangle|y\oplus f(x)\rangle$$. This always works (you prove reversibility by acting it twice). Note that while I've used the quantum notation, this is actually a classical statement.

That does not mean it's the only way to construct a reversible circuit for a specific function. A particularly simple example is the binary function $$f(x)=1-x$$ for $$x\in\{0,1\}$$. If we use the standard construction, we end up with a two-bit gate, controlled-NOT. However, if it sufficient to just apply NOT on the bit, as this is reversible. If I've understood your question correctly, this is exactly what's happening with your example.

The way in which we typically describe quantum computation is by unitary circuits, which is a sequence of transformations $$\def\ket#1{\lvert#1\rangle}\ket\psi \mapsto U\ket\psi$$, for unitary operators $$U$$. (This is not the only way in which to describe quantum computation — for instance, there is measurement-based quantum computation, and quantum annealing — but measurement-based quantum computation is almost always considered just a way to simulate unitary circuits, and quantum annealing doesn't lend itself well to describing computations by a sequence of operations which you do to compute functions on data.) So for us the starting point is to consider how to describe computations with unitary transformations.

When you have a piece of classical data, such as $$a \in \{0,1\}^n$$ for some $$n>0$$, this data is represented by a "standard basis state": a state $$\ket{a}$$ which is a vector in $$\mathbb C^{2^n}$$, whose coefficients are indexed by the $$\{0,1\}$$ strings of length $$n$$. The vector $$\ket{a}$$ is the one where the $$a$$-th coefficient is $$1$$, and the others are zero. We can transform this state — do computations on it — by acting on it with unitary transformations $$U$$, which are $$2^n \times 2^n$$ matrices over $$\mathbb C$$ which are (a) invertible, and (b) satisfy $$U^{-1} = U^\dagger$$.

The short answer to you question is then that because the computations that you do are by invertible transformations, that there has to be a way to invert it. And if the transformation you're interested in maps every standard basis state to another standard basis state (as it would if it is realising a computation just with classical data), that transformation is precisely a 'reversible computation'.

For a somewhat longer answer you would have to consider how to do your computation reversibly. Building on DaftWullie's answer above, it matters what computation you are doing, and what conditions you want on the output. If you want to add some integer $$b$$ to $$a$$, you either have to be flexible enough to allow this to be done reversibly on just the $$n$$ qubit register — for instance, by performing your computation modulo $$2^n$$ — or you have to allow for the possibility that $$a+b \geqslant 2^n$$, which will require that you use something like an extra 'overflow' qubit in a particular way. The same goes for multiplying $$a$$ by $$2$$, or by any other constant. (As Mark S mentions in a comment, multiplying by $$2$$ is not automatically a reversible operation: if you multiply by $$2$$ in a binary representation on $$n$$-bit integers, there will be an overflow if $$a \geqslant 2^{n-1}$$; and also the reverse operation of dividing by $$2$$ is not well-defined on odd integers.) There are common conventions for what you might choose to do, but ultimately it depends on what you want to compute and how many qubits, how few operations, etc. you are prepared to use to do it.

• if i have a bit string $100$ and other as $100$ which is the equivalent for $4$ and realizing them as quantum states $|100\rangle$ and $|100\rangle$, i am prepared to use $3$ qubits and add them then i know that the answer would be the state $|000\rangle$ since there is no fourth qubit which is where the overflow takes place. But since i know that my function just adds the same states i.e does twice, by looking at the final state I can certainly say that the initial input state to the system was state $|100\rangle$ neglecting $|000\rangle$ state. can that be the case? – Upstart Apr 26 '19 at 18:39
• Why are you prepared to ignore the state $\lvert 000 \rangle$? If the result were $\lvert 100 \rangle$ instead, how would you decide between the possible inputs $\lvert 010 \rangle$ or $\lvert 110\rangle$? If you have answers to those questions and all other possible collisions on inputs, then maybe that would point the way to realising the computation you care about in a reversible way. Otherwise, you might have to think a bit more about the computation which you're trying to perform, and the possible inputs which you may have to consider. – Niel de Beaudrap Apr 26 '19 at 18:51
• okay so i need to keep one of the inputs and the final output if i want to go back to the initial state?. – Upstart Apr 26 '19 at 18:57
• That's one approach, which works for all functions. In this specific case you could instead use a carry/overflow qubit which you initially prepare in the state $\lvert 0 \rangle$ and then perform a cyclic shift, e.g. $\lvert c \rangle \lvert x_{n-1} \rangle \cdots \lvert x_0 \rangle \mapsto \lvert x_{n-1} \rangle \cdots \lvert x_0 \rangle\lvert c \rangle$, which represents multiplication by 2 if initially $c=0$. You'll have to do that every time you perform the operation, though. There are also other ways, but it depends on what you want to compute and what resources you're prepared to use. – Niel de Beaudrap Apr 26 '19 at 19:14
• okay, and for adding any two $n$ qubits we need to perform the operations $U|xy\rangle = |x, (x+y)\mod 2^n\rangle$ – Upstart Apr 27 '19 at 7:10