## Want to keep learning?

This content is taken from the Keio University's online course, Understanding Quantum Computers. Join the course to learn more.
2.14

# Reversible Evolution

In quantum mechanics, every change except measurement (and noise that damages the state, known as decoherence, which we will discuss in the last week when we discuss hardware and quantum error correction) must be reversible. (In mathematical terms, this means that it can be represented by a unitary matrix.) This means that it must be possible for us to recreate the initial state using only the output state, without additional information. Here, we will introduce some of those changes as discrete operations which we call gates.

## Basic Classical Logic Gates

You may already be familiar with the most basic logic gates we use in creating a classical computer, but just in case you’re not, let’s review them. Some of the gates have one input bit and one output bit, others have two input bits and only one output bit.

### NOT

The NOT gate, as you might expect, flips a single bit.

input output
0 1
1 0

The NOT gate is reversible: if you apply a NOT gate twice to the same signal, you get out the same value you started with: NOT(NOT(X)) = X.

### AND

The AND gate takes two input bits, and its output is one only if both input bits are one:

input $$A$$ input $$B$$ output $$C$$
0 0 0
0 1 0
1 0 0
1 1 1

The AND gate is not reversible: there are four different possible input states (00, 01, 10, 11) and only two possible output states (0 and 1), so there isn’t enough information in the output to know for sure what the inputs were. In the case that the output C is 1, you know that both inputs were 1, but in all three of the other cases, you can’t tell.

### OR

The OR gate takes two input bits, and its output is zero only if both input bits are zero:

input $$A$$ input $$B$$ output C
0 0 0
0 1 1
1 0 1
1 1 1

Its behavior in a lot of ways is similar to that of the AND gate. The OR gate is not reversible: there are four different possible input states (00, 01, 10, 11) and only two possible output states (0 and 1), so there isn’t enough information in the output to know for sure what the inputs were. In the case that the output C is 0, you know that both inputs were 0, but in all three of the other cases, you can’t tell.

In fact, with the AND or OR gate, even if I gave you the output and one of the inputs, you wouldn’t be able to tell unambiguously what the other input value was in all cases.

### XOR

The XOR, or exclusive OR, gate takes two input bits, and its output is one only if exactly one input bit is one:

input $$A$$ input $$B$$ output $$C$$
0 0 0
0 1 1
1 0 1
1 1 0

The XOR gate is close to reversible: with two input bits and one output bit, there still isn’t enough information in the output to know for sure what the inputs were. But, if I give you one of the inputs, you can now tell unambiguously what the other input was! We will see below that one of the important reversible two-qubit gates is related to XOR.

## Reversible Classical Gates

### Entropy and Information

In the early 1970s, Charles Bennett of IBM, later joined by Richard Feynman of Caltech, and Tommaso Toffoli and Ed Fredkin of MIT, laid the groundwork for discrete reversible logic operations. Bennett was an acolyte of Rolf Landauer, who recognized that the destruction of information adds to the entropy of the Universe, and must generate waste heat.

Entropy is the amount of disorder in something. If you take a physics class, or possibly chemistry, you will learn about entropy when you learn about thermodynamics. If you have a lot of energy confined in one place, you can use it to do work, such as turning a motor. This spreads energy around. Once the energy is spread out evenly, the entropy is maximized and it is no longer possible to do useful work with it.

In computer science we also talk about the entropy of information. If you have a certain amount of data, it might be all zeroes or all ones, in which case it’s very easy to tell a friend how to recreate the same state: just say, “I have seven hundred ones.” If your data is more complex, though, it gets harder to describe; it has high entropy.

I (Van Meter) can recall taking Feynman’s class at Caltech, in which he explained the relationship between information and entropy in terms of thermodynamics. For quite a while, I believed that he was speaking allegorically, and couldn’t understand why he was bringing in physical constants. When I finally understood that he meant it quite literally, I could feel the hair on the back of my neck stand up. It remains one of the most startling ideas I have ever encountered.

### Reversible Computing

Generally, entropy increases when we lose information, or when information is erased. The AND and OR gates we discussed above necessarily lose information: they start with two input bits, and end with only one, so there is no way to carry all of the information through.

If, instead, we require all of our gates to have the same number of input and output bits, it’s possible that we might be able to undo our computation. A second additional criteria is necessary to make it reversible: every possible output state comes from exactly one input state. Then we say that the function is “one to one”, or bijective.

Any logic function can be computed using one, two, and three-bit reversible gates, so we will look at a few of them.

### Identity

The identity gate does nothing to the state: its output is the same as its input. It is obviously reversible; since it does nothing, in order to get back to where we started, we only have to do nothing one more time!

input output
0 0
1 1

### NOT

We have already seen the NOT gate above. Executing NOT twice in a row brings us back to where we started: NOT(NOT(X)) = X.

### CNOT

The controlled NOT gate, or CNOT, takes two input bits and produces two output bits. If one of the bits (called the control bit) is one, the other bit (called the target bit) is flipped. If the control bit is zero, the target bit is passed through unchanged.

input $$A$$ input $$B$$ output $$A'$$ output $$B'$$
0 0 0 0
0 1 0 1
1 0 1 1
1 1 1 0

A quick examination of the table shows that $$A'$$ is the same as $$A$$, and $$B'$$ is the XOR of $$A$$ and $$B$$, $$B' = A \oplus B$$. If we apply the same gate twice, obviously $$A$$ stays the same, and the new $$B'' = A \oplus (A \oplus B) = B$$, and we are back where we started.

### CCNOT (Toffoli Gate)

The control-control-NOT gate, or CCNOT gate, is also called the Toffoli gate, named for Tommaso Toffoli. It uses two control bits instead of one.

input $$A$$ input $$B$$ input $$C$$ output $$A'$$ output $$B'$$ output $$C'$$
0 0 0 0 0 0
0 0 1 0 0 1
0 1 0 0 1 0
0 1 1 0 1 1
1 0 0 1 0 0
1 0 1 1 0 1
1 1 0 1 1 1
1 1 1 1 1 0

### CSWAP (Fredkin Gate)

The control-SWAP gate, or CSWAP gate, is also called the Fredkin gate, named for Ed Fredkin. If the control bit is zero, the other two bits are left alone. If the control bit is one, the other two bits are swapped.

input $$A$$ input $$B$$ input $$C$$ output $$A'$$ output $$B'$$ output $$C'$$
0 0 0 0 0 0
0 0 1 0 0 1
0 1 0 0 1 0
0 1 1 0 1 1
1 0 0 1 0 0
1 0 1 1 1 0
1 1 0 1 0 1
1 1 1 1 1 1

Either the CCNOT or the CSWAP gate is powerful enough to be able to create any classical logic circuit.

## Single-Qubit Gates

The reversible gates above all have quantum equivalents, and we will use them in constructing quantum algorithms. But qubits are more complex objects than simple classical bits, allowing a broader range of operations that all qualify as unitary. Here, we will look at some single-qubit gates that go beyond just the Identity and NOT gates above.

### Rotations on the Bloch Sphere

When we introduced qubits, we introduced the notion of the Bloch sphere, and the idea of the state of a single qubit as a point on the sphere. The one-qubit gates can be understood as rotations about the X, Y, or Z axis of the Bloch sphere.

Rotation is a naturally reversible operation: just rotate back in the opposite direction by the same amount. Every point on the sphere has a starting position and an ending position, and no two points ever come together. No two different starting points come to the same ending position. This is a key factor maintaining reversibility. If two points did come together, when we attempted to reverse the operation, we would have no way of distinguishing them and returning them to separate starting positions.

### The NOT Gate and Other X Gates

A simple reversible gate, like the classical NOT gate, the $$X$$ gate takes 0 to 1 and 1 to 0. Since our state can be a superposition, it does a little more than this, it swaps our 0 and 1 values, or the contents of our 0 and 1 dials. It is a rotation of 180 degrees, or $$\pi$$, about the $$X$$ axis. It’s also possible to rotate by any angle, which swaps the 0 and 1 values less completely.

### The Phase Gates

Although rotating around the $$X$$ axis is somewhat like the classical NOT gate, rotating around the $$Z$$ axis has no classical equivalent. $$Z$$ rotation modifies the phase of the state. We call a 180 degree rotation simply the Z gate. For other angles, we call it a Z rotation or a phase gate, and specify the angle.

The Hadamard gate is our most basic means of creating superposition. It takes our $$\vert0\rangle$$ state to a 50/50 superposition of $$\vert0\rangle$$ and $$\vert1\rangle$$:

$\vert0\rangle \rightarrow \frac{\vert0\rangle + \vert1\rangle}{\sqrt{2}}$

If it also took the $$\vert1\rangle$$ state to the same 50/50 superposition, it wouldn’t be reversible. Instead, it takes it to a superposition with a phase twist on the $$\vert1\rangle$$ state:

$\vert1\rangle \rightarrow \frac{\vert0\rangle + (\pi)\vert1\rangle}{\sqrt{2}}$

Applying the Hadamard twice to the same qubit returns it to its original state. In fact, this is our first use of interference! If we began with the $$\vert0\rangle$$ state, we get constructive interference that builds us a new $$\vert0\rangle$$ state, and destructive interference that eliminates the $$\vert1\rangle$$ state:

$$\frac{\vert0\rangle + \vert1\rangle}{\sqrt{2}}\rightarrow \vert0\rangle$$.

Here we can see that the phase of the state has a critical impact on the interference; reversing the other state results in constructive interference on the $$\vert1\rangle$$ state, and destructive interference on the $$\vert0\rangle$$ state:

$$\frac{\vert0\rangle + (\pi)\vert1\rangle}{\sqrt{2}}\rightarrow \vert1\rangle$$.

# 可逆発展

## 基本的な古典論理ゲート

### NOT

NOTゲートは、その名の通り一つのビットを反転させます。

input output
0 1
1 0

NOTゲートは可逆な操作です。例えば、同じ信号に二度NOTゲートをかければ、操作の後に出力される値は操作を始める前のものと同じものになることが分かるかと思います。

### AND

ANDゲートは2つの入力ビットを持ち、両方の入力ビットが1だった場合のみ、出力値として1を返します。

input $$A$$ input $$B$$ output $$C$$
0 0 0
0 1 0
1 0 0
1 1 1

ANDゲートは不可逆な操作です。異なる四つの入力状態 (00, 01, 10, 11)と二つの出力状態(0, 1)があり、出力だけからは入力がどんな値だったのかは分からなくなってしまいます。出力Cが1の場合は、両方の入力が1であったことが分かりますが、それ以外の場合は入力の値が何だったかは知ることができません。

### OR

ORゲートは二つの入力ビットを持ち、両方の入力ビットが0だった場合のみ、出力値として0を返します。

input $$A$$ input $$B$$ output C
0 0 0
0 1 1
1 0 1
1 1 1

ANDゲートと同様に、ORゲートも不可逆な操作です。 異なる四つの入力状態(00, 01, 10, 11)と二つの出力状態 (0, 1)があり、出力だけからは入力がどんな値だったのかを推測することはできません。 この場合、出力Cが0の場合のみ、両方の入力が0であったことが分かりますが、それ以外では入力値が何だったかを知ることはできません。

### XOR

XORゲート(exclusive OR)は、二つの入力ビットをとり、一つの入力ビットだけが1だった場合にのみ出力は1になります。

input $$A$$ input $$B$$ output $$C$$
0 0 0
0 1 1
1 0 1
1 1 0

XORゲートは可逆に近い操作です。 二つの入力ビットと一つの出力ビットをもち、出力値だけで入力値を逆算することはできませんが、２つの入力値のどちらか一つを与えられれば、もう片方の入力値についても自動的に知ることができます。 続いて、最も重要な2量子ビットゲートが、XORゲートに関連していることを学んでいきます。

## 可逆古典ゲート

### エントロピーと情報

1970年代前半、カルフォルニア工科大学のRichard Feynman、IBMのCharles Bennett、MITのTommaso Toffoli と Ed Fredkin等によって可逆論理演算の基礎が築かれました。 Bennettは当時、Rolf Landauerの助手として働いていました。Rolf Landauer 教授は、情報の破壊が宇宙のエントロピーを増大し廃熱をもたらすことを発見した研究者です。

エントロピーとは、何かに存在する無秩序の度合いを示す物理量です。 皆さんが、物理や化学の授業を受けていれば、その中で熱力学を学ぶ際にエントロピーについて勉強したことがあると思います。 ある場所にエネルギーを蓄えれば、それをモーターの回転などの仕事に使うことができます。 こういった仕事はエネルギーを周囲に拡散します。 一度エネルギーが広がりきると、エントロピーは最大化し、もはや有効な仕事に使うことができなくなります。

コンピュータサイエンスの分野においても、「情報のエントロピー」という概念があります。もしあながた一定量のデータを持っていたら、それが全て0か全て1のどちらかだとすると、友達にどのように同じ状態を再構築するかを教えるのはとても簡単です。単に、「私は700個の1を持っています」と教えるだけです。もしデータがより複雑になると、それを記述することは難しくなり、これを「エントロピーが高い」と表現します。

### 可逆計算

もし、全ゲートについて入力と出力が同じ数であるなら、、処理を元に戻すことが可能かもしれません。 それでも、完全なる「可逆」のためには、もう一つの条件が必要になります。その条件とは、すべての出力状態は、それぞれ一意に決まる入力状態と対応付けられている、という場合です。そのとき、関数は”one to one”、もしくは全単射であると言えます。

すべての論理関数は、1ビット、2ビット、3ビットの可逆ゲートを用いて計算することができます。 そういった論理関数をいくつか見ていきましょう。

input output
0 0
1 1

NOT(NOT(X)) = X

### CNOTゲート

CNOT(controlled NOT gate, or CNOT)は二つの入力ビットをとり、二つの出力ビットを生み出します。 もし片方のビット(制御ビットと呼ばれる)が1の場合、もう片方のビット(ターゲットビットと呼ばれる)は反転されます。 もし制御ビットが0の場合、ターゲットビットの状態は変わらず、そのまま出力されます。

input $$A$$ input $$B$$ output $$A'$$ output $$B'$$
0 0 0 0
0 1 0 1
1 0 1 1
1 1 1 0

A は $$A′$$ の値と常に同じであり、 $$B′$$は$$A$$と$$B$$を XOR でかけた$$B' = A \oplus B$$であることが分かります。もしCNOTゲートを２回連続で適用した場合、$$A$$は同様に同じ状態を保持し、ターゲットビットである$$B$$は$$B'' = A \oplus (A \oplus B) = B$$になり、結果、初期値に戻すことができます。

### CCNOTゲート (Toffoliゲート)

CCNOT(control-control-NOT gate)はTommaso Toffoli.に因んで、Toffoli （トフォリ）ゲートとも呼ばれています。CCNOTは二つの制御ビットを必要とします。

このゲートは3ビットの入出力をもちます。最初の2ビットはそのまま出力します。もし入力の最初の2ビットが1なら、第3のビットは反転して出力されます。

input $$A$$ input $$B$$ input $$C$$ output $$A'$$ output $$B'$$ output $$C'$$
0 0 0 0 0 0
0 0 1 0 0 1
0 1 0 0 1 0
0 1 1 0 1 1
1 0 0 1 0 0
1 0 1 1 0 1
1 1 0 1 1 1
1 1 1 1 1 0

### CSWAPゲート (Fredkinゲート)

CSWAPゲート(control-SWAP gate)は、Ed Fredkinに因んでFredkinゲートとも呼ばれます。 もし制御ビット（入力A）が0の場合、他のビット（入力B、入力C）の状態は何も変化せずに出力されます。 逆に、1だった場合、他の2つのビット状態は交換され、出力されます。

input $$A$$ input $$B$$ input $$C$$ output $$A'$$ output $$B'$$ output $$C'$$
0 0 0 0 0 0
0 0 1 0 0 1
0 1 0 0 1 0
0 1 1 0 1 1
1 0 0 1 0 0
1 0 1 1 1 0
1 1 0 1 0 1
1 1 1 1 1 1

CCNOTやCSWAPゲートは、其々のゲートだけで任意の古典論理回路を組むことができる、強力なゲートの一例として挙げられます。

## 単一量子ビットゲート

### ブロッホ球上での回転

Rotation is a naturally reversible operation: just rotate back in the opposite direction by the same amount. Every point on the sphere has a starting position and an ending position, and no two points ever come together. No two different starting points come to the same ending position. This is a key factor maintaining reversibility. If two points did come together, when we attempted to reverse the operation, we would have no way of distinguishing them and returning them to separate starting positions.

### 位相ゲート

$$X$$軸を中心とした回転は古典的なNOTゲートに似ている操作ですが、$$Z$$軸を中心に状態を回転させる操作に対応する古典的なゲートは存在しません。$$Z$$回転は、その量子状態の位相を変換します。 $$Z$$軸を中心に180度($$\pi$$)の回転を加える操作を「Zゲート」と呼びます。もちろん、他の角度の場合は、「Z回転」、もしくは「位相ゲート」と呼び、その角度を明記します。

### アダマール ゲート

アダマールゲートは重ね合わせを作るために用いる、最も基本的な操作です。$$\vert0\rangle$$の状態を50/50の割合で$$\vert0\rangle$$と$$\vert1\rangle$$の重ね合わせに変換します。

$\vert0\rangle \rightarrow \frac{\vert0\rangle + \vert1\rangle}{\sqrt{2}}$

もしアダマールゲートを$$\vert1\rangle$$の状態にかけて、上記と同じ50/50の重ね合わせになってしまったら、それは不可逆な操作になってしまいます。$$\vert1\rangle$$の状態にアダマールゲートをかけるときは、位相をねじって重ね合わせます。

$\vert1\rangle \rightarrow \frac{\vert0\rangle + (\pi)\vert1\rangle}{\sqrt{2}}$

アダマールゲートを同じ量子ビットに２回連続して適用すれば、出力状態は初期の入力状態と常に同じになります。 物理的には、この操作は波の干渉にあたります（はじめて登場しますね！）$$\vert0\rangle$$にアダマールゲートをかければ、新しい$$\vert0\rangle$$状態は元の$$\vert0\rangle$$状態と$$\vert1\rangle$$状態の強め合い干渉によって生成され、$$\vert1\rangle$$状態は弱め合い干渉によって消滅します。

$\frac{\vert0\rangle + \vert1\rangle}{\sqrt{2}}\rightarrow \vert0\rangle$

ここで位相が重要になってきます。

$\frac{\vert0\rangle + (\pi)\vert1\rangle}{\sqrt{2}}\rightarrow \vert1\rangle$