イメージでざっくり理解する量子コンピュータ

# 前置き
ついに、アドベントカレンダーが始まりました！！
量子コンピュータのカレンダを企画し、第１日目はどうしようと悩んでいたのですが、25日を通して幅広い方に読んでほしいので、まずは量子計算のイメージを掴んで頂くことが重要と考えました。
そこで、初日の本日は、

* **量子計算ってなにもの？** かを **イメージで**ご理解いただく記事をご準備しました。
* **量子計算って「そういう雰囲気なのね！」** と言っていただけるように、頑張ります。

最初に、本日の結論をお示しすると、こちらの**栗まんじゅう**でございます。

![sweets_kurimanju.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/808c8c8b-e0e5-3a7a-427f-5eeacb91ac44.png)<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/fdff85b9-dd33-7656-7865-4c53bf2e7847.png" width=80px> 

# 注意
**超入門**を目指すために、**理解／イメージ**最優先で、正確性をある程度犠牲にし進めます。
なお、筆者の理解が及ばず、正確性を犠牲にしている場合もありますので（笑）、、
その場合はコメントいただけますと幸いです。

# 量子コンピュータってなに？
![quantum_computer.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/86efc257-b83f-7a6d-eb3f-135f3834f94b.png)

こちらの資料[^1]で説明を進めて行ければと、

## 古典コンピュータ
**「ふつーの計算機（PC・サーバ）」** は上段の **「古典コンピュータ」** です。
古典というのは、古いとかっていう意味ではなく、、

* 物理学で、「量子力学」登場前の、ニュートン力学等を「古典力学」と呼称します[^2]
* その背景で、量子コンピュータと対比し「古典コンピュータ」と呼称します
* 英語だと*Classical Computer*ですので、**従来型**のくらいのイメージでしょうか

なので、古いとか、ましては、遅いとかっていう意味ではありません。
では、普通のコンピュータの特徴とは何でしょうか？議論は、色々ありそうですが、

* **古典ビット** ：計算で利用するビットは、「0か1」のどちらか
* **逐次計算** ：複数の入力を与えても、１個づつ[^3]処理をして計算（入力の数だけ計算）

といった点ではないでしょうか？では、量子コンピュータになるとどうでしょうか？

## 量子コンピュータ
古典コンピュータの逐次計算が苦手とする、複数の状態を同時に扱うような問題に対し、
量子力学での「重ね合わせ・もつれ合い」という現象がうまく生きるようにプログラムを構成し、並列・一括での計算を実現しよう。というのが量子コンピュータです。

量子コンピュータでは、上記の２要素が下記となります。

* **量子ビット** ：計算で利用するビットは、 **「0と1の重ね合わせ」** を取れる。
* **並列計算** ：それにより、複数状態を同時に表現し、それらを **並列に(一括で)** 計算できる

**「重ね合わせ」** とか **「一括で」** とか、早速、よう分からんですね。。
イメージしろと言われても、無理な話ですね。
![question_head_gakuzen_girl.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/e856b399-cde3-bee6-7d21-bc37afec6a94.png)![question_head_gakuzen_boy.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/7b1e1c59-1667-78b5-343d-4598b2d8f2f2.png)

## 前提として
「重ね合わせ・もつれ合い」等の量子力学的な現象ですが、理解するのがどれだけ困難か？
ですが、かの有名な**リチャード・P・ファインマン**[^4]先生のお言葉を借りると

>If you think you understand quantum mechanics, you don't understand quantum mechanics.[^5]
>もしも量子力学を理解できたと思ったならば...それは量子力学を理解できていない証拠だ。[^6]

つまり、研究者ではない一般人が理解を試みる事、そのものが、おこがましいのですが、、
一方で、現象の**本質は理解できずとも**、その活用が**計算を高速化する可能性**があるなら、
それは、計算機科学の立場の人間からすると、とても魅力的に思えます。

# というわけで、今日お話したいこと
量子コンピュータの本質に迫る！みたいな記事は私には書けませんが（笑）、、

* **「重ね合わせ」** がどんなイメージか？
* なぜ、それにより **並列計算が実現されるか？**
 
について **数式は使わずに、イメージで** お伝えしてみたいと思います。
量子力学の本質は分からない、が、計算高速化に可能性を感じる一般的なエンジニアとして。。

# 今までの議論と説明のアウトライン
古典コンピュータと量子コンピュータを、**ビット**と**計算方式**で比較しました。
整理すると、

|　|ビット|計算方式|
|:---:|:---:|:---:|
|古典<br/> コンピュータ|古典ビット <br/> (0と1)|逐次計算|
|量子<br/> コンピュータ|量子ビット <br/> (0と1と**①重ね合わせ**)|**②並列計算**|

といった状況ですので、「**①重ね合わせ**」のイメージをご説明し、
それが「**②並列計算**」にどうつながるか？の順序で説明を進めます。

# ①重ね合わせ
## コイン　と　コイントスで考える[^7]
急になぜコインが出てくるか？というと、みなさんが良くご存知の**コイントス**にて、重ね合わせをうまく説明できそうだからです。では、話を進めましょう。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/7608a428-30e5-0613-9fb1-f728316f1b6d.png" width="200px" />

### コインで数字を表現する
たとえば、手元にコインが１枚あったとしたら、表(0)と裏(1)を使うと、0と1が表現できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/f0cbd617-719b-adee-da5b-c825176362ec.png" width="300px" />

### 複数枚あると、２進数でいろいろな数字を表現できる
たとえば、３枚のコインがあれば、**「0～7の数字を<font color="red">同時に一つ</font>表現することができます。」**
**「同時に一つ」** というのがとても重要です。どういう意味かというと、

* 5を表現することもできるし、7を表現することもできる。
* 一方、5と7を**同時には表現できず**、5→7に変更しようとすると**2枚目を裏返す**必要がある
* **0と1を同時に両立するコイン!?** があれば、2枚目をそれにすれば、5と7を同時に表現できるのですが…

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/4f47aa1b-7e2b-b6ab-c07e-237a062732a7.png" width="500px" />

### 表(0)でも裏(1)でもない、コインを考える
ここで、表／裏向きのコインについて、見方を変えてみると、、
**「100%で表(0)の状態」、「100%で裏(1)の状態」** と考えることができそうです。


<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/63f668d6-93cb-e92e-450d-8ffaa562776a.png" width="500px" />


これらと対比して、 **コイントスし、くるくる回るコイン** を考えると、この **くるくるコイン** は、**「表(0)になるかもしれないし、裏(1)になるかもしれない」** と言った様に、
両者の確率を50%／50%で両立する状態。つまり両者が、 **「重なり合った状態」** と
見ることができるのでは無いでしょうか？


<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/1dea5f9a-3779-09f8-3f9d-0b9fdae1d354.png" width="500px" />


## くるくるコイン　と　重ね合わせ
「重ね合わせ」を「くるくるコイン」として模すことができたので、、
改めて、古典／量子ビットの違いを見てみましよう。

* 古典ビット　：　0か1　を決定的（100%）に表現する。
* 量子ビット　：　0か1　を確率的（例50% vs 50%）に[^8]表現し、重なった状態も取れる

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/b030a944-fb85-6398-2272-3542c40ce102.png" width="500px" />

## 「ファインマン先生、重ね合わせが、よく分わからないのです!!」

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/ed837c24-7be1-aa19-4b66-160daa60991f.png)

ここまで、説明すると、、

* 「ゼロ　と　イチ」が重なっているけど、**データ混じらないの?**
* そんなものに、**どうやってアクセスすればいいの** 
* 「計算」なのに、**あとは、「偶然に任せる」** 的な理屈でいいの

とか、色々不安がでてくるのですが、ここで、ファインマン先生の言葉を思い出してください。

>If you think you understand quantum mechanics, you don't understand quantum mechanics.[^5]
>もしも量子力学を理解できたと思ったならば...それは量子力学を理解できていない証拠だ。[^6]

**現象そのもの**を理解しきるのは困難です。（それは、専門家でも理解の厳しい世界ですので。。）
一方で、これを**受け入れる（前提とする）と**どんな世界が見えてくるでしょうか？
この **「くるくるコイン」を受け入れたとしたら** 、どんな計算ができるか？を見ていきましょう

# ②並列計算　～重ね合わせを受け入れると見える世界～
## 並列に計算するためには？
どうすればいいでしょうか？まずは、計算対象を**並列に（同時に）表現する必要があります。**
**並列に（同時に）表現**というのは、ちょっと乱暴な言い方でしたね。
では、旅行のプランを例に考えてみましょう。検討している旅行プランが３パターンあり、

* パターンA　：　その国の世界遺産をすべて回る、費用も高い、疲れるが大満足
* パターンB　：　１つだけ世界遺産に行き、浮いたコストで、美味しいレストランへ
* パターンC　：　１つだけ世界遺産に行き、浮いたコストで、最終日のホテルをランクアップ

**満足度が高く、コストもそこそこ、体力面も考慮し**、一番ベストなプランを選びたい。
**逐次計算**では、計算機に同時に入力できるのは、任意の１パターンです。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/cb52ec63-5bbe-8a49-bf92-62692b25bd9c.png" width="500px" />

一方で、計算対象を **並列に（同時）** に表現でき、それを処理できる並列計算機があれば、
こんなふうに、全部のパターンを同時に表現し、計算を行うことができます。入力は１回だが、全部のパターンを同時に（確率的に1/3で両立する）表現なので並列計算ができるイメージです。[^11]

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/5292deff-74fe-2d1f-926c-a9f172972c85.png" width="500px" />


## 並列に計算対象を表現するのに、便利なものはなかったか？
並列に、同時に、複数のパターンや状態を表現するのに、便利なものはなかったか？
そうです、先程、 **強引に受け入れて頂いた「重ね合わせ」** です。
旅行を例に出しましたが、もうすこし簡単な議論にしたいので、コインの世界に戻りましょう。
ただ、コインを複雑化していけば、旅行の最適化だってできるはずです。

## 0～7を同時に表現したい。
では、0～7という状態を同時に表現する方法を考えていきましょう。

## まずは、古典ビット（24枚必要。。）
0（000）～7（111）を**同時に**表現しようとすると、

* １パターンあたり、コイン（ビット）が３つ必要です。
* その上で、0～7の8パターンを表現するためには、**3x8=24枚**のコイン（ビット）が必要です。

なにが言いたいかというと

* １つのパターンが、ちょっとでも複雑になったり（3枚→30枚）
* 表現したいパターン数が、ちょっとでも増えると（8パターン→80パターン）

すぐに、**組み合わせ爆発を起こしそう。ということです。**

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/0985120a-5339-976b-79de-5fba9ab2ffb7.png" width="400px" />

## つぎに、量子ビット（なんと、、◯枚）
ここで、「重ね合わせ」が力を発揮します。
**1桁目、2桁目、3桁目と3つのコインを重ね合わせ**にします。
そうすると、全部のコインが、 **0 : 1 = 50% : 50%** の重ね合わせだとすると、全体としては、
0～7の8パターンが、それぞれ、**出現確率1/8** で重なりあっている状態と理解できます。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/c1f350bb-21eb-229e-80cf-42f3b24e3f2b.png" width="400px" />

そして、古典の**24枚**と比較すると、必要なコインの枚数は**3枚**です！なんと3枚です！
具体的には、コインN枚に対して、表現可能な状態は、$2^N$パターン[^9]となります。

## そして、コインの枚数が50枚になる頃には

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/4be9f76d-2d19-e1a9-9553-8a421bcd2d06.png" width="400px" />

$2^{50}$パターン（bit）となるので、

* 原理上、規模的には**ペタバイト級の空間**を手に入れることができます。[^10]
* もっとすごいことを言うと、**50→51になるだけで、$2^N$ですから空間は２倍になります。**
* もう、すごいんです。**バイバイン**です。栗まんじゅうも食べたい放題です。

![sweets_kurimanju.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/808c8c8b-e0e5-3a7a-427f-5eeacb91ac44.png)<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/183826/fdff85b9-dd33-7656-7865-4c53bf2e7847.png" width=80px> 

# まとめ
改めて冒頭にお示しした、この表を眺めておしまいとしたいと思います。

* 古典／量子コンピュータの違いを、「ビット」と「計算方式」の２面で眺めてみました
* 量子ビットは「重ね合わせ」を取ることができます。
* それにより、様々なパターンを同時に表現し、並列計算が**実現可能です（原理上は）**

|　|ビット|計算方式|
|:---:|:---:|:---:|
|古典<br/> コンピュータ|古典ビット <br/> (0と1)|逐次計算|
|量子<br/> コンピュータ|量子ビット <br/> (0と1と**①重ね合わせ**)|**②並列計算**|

## 原理上は
最後に、一言 **「原理上は」** とか、気になる表現をしてしまいスミマセン。
ただ、これを説明するためには、もっと各論が必要になってきます。
ただ、**この原理上は**という現実も、皆様には是非ご理解頂きたいポイントになります。
そこで、本アドベントカレンダーでは、「理想的には～」と「現実的には～」の両方のテーマをあわせてご紹介・ご説明していければと考えています。

明日以降もよろしくおねがいします～

# おまけ
## 重ね合わせは、空想科学（SF)とかではないのです。
空想的な話・仮想的な話　と誤解されがちですが、現実です。
詳細を知りたい方は、こちらを参照されていただければと（リンクさせていただきます。）

https://quanta087.hatenablog.jp/entry/2017/12/03/231353

[^1]: 手前味噌で恐縮ですが、所属組織のHPの解説より引用しております。詳細については、下記をご確認ください。https://www.nri.com/jp/knowledge/glossary/lst/ra/quantum_computer

[^2]: https://ja.wikipedia.org/wiki/%E5%8F%A4%E5%85%B8%E5%8A%9B%E5%AD%A6

[^3]: マルチスレッドとかマルチプロセスプログラミングも、マシン語レベルでは、CPU時間を時分割し多重化しているので、ある瞬間（単位時間）でみれば１つというのは正しいかと

[^4]: https://ja.wikipedia.org/wiki/%E3%83%AA%E3%83%81%E3%83%A3%E3%83%BC%E3%83%89%E3%83%BBP%E3%83%BB%E3%83%95%E3%82%A1%E3%82%A4%E3%83%B3%E3%83%9E%E3%83%B3

[^5]: https://en.wikiquote.org/wiki/Talk:Richard_Feynman#%22If_you_think_you_understand_quantum_mechanics,_you_don't_understand_quantum_mechanics.%22

[^6]: 意訳してみました。直訳だとなんだかむ無味閑散な感じでしたので。

[^7]: [Aleksandar Radovanovic, Quantum Programming Illustrated](https://www.amazon.com/dp/B08B3MVXHB/)を参考にさせていただきました

[^8]: 実際には、複素確率振幅という複素数の絶対値（２乗）が、そのパターンを観測する確率となるのですが、まずは、ざっくり確率として捉えて頂ければと。悲しきかな、人類はその複素確率振幅に直接的にアクセスすることはできず、複数回観測による頻度確率から類推するしかないわけですが。。

[^9]: 数式使わない宣言でしたが、使っちゃいましてTex数式。スミマセン。

[^10]: 実際には、量子系のノイズに対応し、誤り訂正をする関係でもっと空間が小さくなる。（詳細は、量子誤り訂正の回でやります。）空間が広大過ぎても、正解に対応するパターンの複素確率振幅が小さくなり、制御精度を要する。頻度確率で正解を見つける関係で、必要な観測回数が増えるので測定回数が多くなる等、課題はいろいろあります。

[^11]: Groverのアルゴリズムをイメージして記述してみました。このアルゴリズムは、カレンダの後半で扱っていきますので、ご興味有る方は、カレンダの後半で。