量子コンピュータとは (リョウシコンピュータとは) [単語記事]

量子コンピュータとは、量子力学的な効果を用いて計算を行うコンピュータである。

量子計算機、量子演算器とも。

概要

ミクロな世界における原子や電子の特殊な振る舞い、特に重ね合わせの原理と量子もつれ（エンタングル）と呼ばれる効果を利用して計算を行う。従来のコンピュータによる計算と異なり、ひとつの量子状態で複数の計算を並列に行うことができる。計算結果は観測により確率的に得られる。

中二っぽく言い直すと「無数の並行世界で同時に計算を行い、その中から正しい答えを取り出すコンピュータ」となる。超かっこいい。

量子コンピュータと区別するため、いわゆる普通のコンピュータは古典コンピュータと呼ばれることがある。本項でもこの用語を使う。

主な方式	説明、主な開発企業
量子ゲート	極低温に冷やす超伝導の技術などで量子ビットを実現。汎用性は高いが大規模集積化などに課題。 Google IBM アリババ
量子アニーリング	超電導の技術を利用。組み合わせ最適化問題に特価し、産業応用に向けた研究が進む。 Dウェーブシステムズ NEC
量子ニューラルネットワーク	計算の過程で光の量子力学的な特性を利用。常温で動くなどの強みを持ち、組み合わせ問題への最適化を見込む。 NTT

【資料】
- 日本経済新聞 2020年 1月13日

量子ビット

量子ビットとは？

デジタルコンピュータの基本素子が論理ゲート回路であるように、量子コンピュータの基本素子は量子ビットである。では量子ビットとは何か？　…一言で言うならば「シュレーディンガーの猫」である。なので分からない人は一度同項目に入ってから戻ってくるように。シュレーディンガーの猫において箱の中に入れられた猫が「生きていてなおかつ死んでいる」状態で、「蓋を開けて『観測』することで初めて生死が確定する」ように、観測されなければ「１でありなおかつ０でもある」状態で、「観測することで初めて１か０が確定する」素子が量子ビットでありqub it（キュービット）という単位で表す。そして「１でありなおかつ０でもある」状態のことを「量子の重ね合わせ」という。

単独の量子ビットを繰り返し観測しても、１か０になる確率は半分半分で結果は完全にランダムである。ところが重ね合わせ状態の複数の量子ビットを（観測することなく）何らかの形で相互作用させると、量子ビット間に「相関関係」が発生し、相互作用させた量子ビットの一つを観測すると観測結果が即座に残りの量子ビット全てに影響する。これが「量子もつれ」である。多数の重ね合わせ状態の量子ビットを用意してこれらに適切な量子もつれを施し（量子ゲートタイプの場合は2〜4qub itの量子もつれを多数回行う。量子アニーリングタイプは一度に数千もの量子ビット全てをもつれさせる）、最終的に全ての量子ビットを観測すると望んでいた解が得られる。これが量子コンピュータの正体である。

量子コンピュータの動作を「エヴェレット解釈」で表すならば（コペンハーゲン解釈も可能だが、現在の量子コンピュータの理論はエヴェレット解釈前提で作られた）、N qub itの量子コンピュータの内部には２のN乗個もの平行世界が重なり合うようにして存在する。これに量子もつれを施すと解ではない可能性を持った世界が淘汰されて次々と消えていき、最後は正解を持った世界だけが生き残って観測される、という表現になる。

量子ビットの種類

有機化合物　適切な有機化合物を用意し、化合物分子を構成する原子の原子核スピンを量子ビットに使う。量子もつれと解の読み出しには核磁気共鳴を用いる。最も初期から使われていた方式だが、強力な超伝導磁石が必要であり、また多ビット化に難がある。
超伝導量子ビット　（量子ゲート、量子アニーリング共に）現在最も主流の方式。ジョセフソン接合を３つ持つ超伝導リングを用いる。特殊な素材と冷却用の液体ヘリウムが必要なため極めて高価である。
イオントラップ　電磁場でイオンを閉じ込めるイオントラップにイオンを一つずつ間隔を開けて閉じ込めて、レーザー冷却で固定したものを量子ビットに用いる。液体ヘリウムを用いない分、超伝導方式よりも難易度は低い。
ダイヤモンドNV中心　微量の窒素を含んだダイヤモンドに生じる格子欠陥（原子の穴）。通常は６個の電子が入っているが、その中の２個の電子のスピンが常温でも極めて安定しており、量子ビットに使える可能性がある。
光子　光子の偏光や旋光を量子ビットに用いる。量子もつれにはマッハ・ツェンダー干渉計を用いる。後述するように量子ビットにはデコヒーレンスの問題があるが、光子は長期間デコヒーレンスを起こしにくい上に室温で使用できるので将来性が期待されている。

量子コンピュータでできること

素因数分解

最も有名なのは自然数の素因数分解である。そんなん俺でも出来るしｗｗｗと思った人は試しに38686873991 ^[1] を手で素因数分解してみてほしい。きっと途中で投げたくなるはずである。実はこれは数が大きくなると古典コンピュータを使っても同様であり、非常に大きな素因数（数百桁ぐらい）を持つ数をさくっと素因数分解できるアルゴリズムはまだ見つかっていない。あるのかどうかも分かっていない。

しかし充分にデカい量子コンピュータが使えると仮定すれば話は別であり、「ショアのアルゴリズム」と呼ばれるまともな速さで素因数分解を達成するアルゴリズムが見つかっている。これは量子コンピュータが古典コンピュータよりも素早くフーリエ変換を解けることを利用したアルゴリズムだ。

素因数分解なんかできても意味なくね？と思うかもしれないが大間違いである。インターネットで情報をやりとりする際よく使われる暗号化技術であるRSA暗号はこの「非常に大きな数の素因数分解にはすごく時間がかかること」を暗号が解かれないことの根拠としているため、素因数分解がさくさくできてしまうと現在のネットのセキュリティは無いも同然になってしまう。おちおちニコニコ動画も見られなくなる。ヤバい。

素因数分解の他にも高速に計算できる問題はいくつも見つかっているが、本項では割愛する。

量子暗号通信

つまり実用レベルの量子コンピュータを作ってしまうと世界は大混乱に陥ってしまうんだよ！！！……ということはない。

量子コンピュータと同様の原理を使うと、絶対に安全な暗号通信（正確には、攻撃を受けたときに絶対にそれを検知できる通信）を行えることが分かっている。達成しなければいけないハードウェアの規模を考えるとむしろ現在はこっちが本命なくらいであり、日本でも大学の研究室のほか東芝、三菱、NEC、NTTなどが実用化に向けて共同で研究を行っている。

量子コンピュータでできないこと

量子コンピュータは「どんな計算でも爆速で終わらせてしまうウルトラスーパーコンピュータ」のようなイメージを持たれていることがあるが誤解である。大事なことなのでもう一度言うと、誤解である。

仮に巨大な量子コンピュータを作れるようになったとしても、次のような問題は解くことができなかったり長い時間がかかったりする。

決定不能問題

意外かもしれないが量子コンピュータと古典コンピュータで計算できる問題に差はない。これは量子コンピュータの動作を古典コンピュータで（時間はめっちゃかかるかもしれないが）完全にシミュレートできることによる。つまり、量子コンピュータで解ける問題は（時間はめっちゃかかるかもしれないが）古典コンピュータでも必ず解ける。

なので、古典コンピュータでそもそも原理的に解けない問題（決定不能問題、または計算不能問題と呼ばれる。簡単に言えば答えの範囲が無限になる問題。）は量子コンピュータでも解けない。

永久機関などと同様、「できるかどうか分かっていない」のではなく「できないことが分かっている」問題である。諦めましょう。

計算量クラスが大きい問題

じゃあ計算可能な問題なら何でも爆速で解けるか？というとそうでもない。量子コンピュータを使っても長い時間がかかってしまう問題は計算の世界にはいくらでも存在する。

たとえば東ロボくんが入試数学の問題を解くのに使った「実閉体の限量子消去問題^[2]」は実行時間が指数タワーで抑えきれないほど難しい問題であり、問題のサイズを大きくすると量子コンピュータを使ってもすぐには解けなくなる。古典コンピュータしか使っていない東ロボくんでも回答できているのは問題が小さいからである。

つまり、大学入試数学の問題をいじって変数がものすごく多くなるようにすると量子コンピュータを使っても制限時間以内に解くことはできない^[3]。もちろん人間にも（たぶん）解けない。

実装の現状

量子コンピュータ実現の壁は量子デコヒーレンスと呼ばれる現象である。これは古典コンピュータでいうと計算中に勝手にメモリ上のビットが書き換わってしまう（その上絶対に元に戻せない）ようなものであり、しかも量子コンピュータを大きくしようとすればするほどデコヒーレンスは起きやすくなる。どうにかしようとして計算方法や実装方法が色々研究されているが、少なくともまだ当分無理そうだと考える人が多い。

とはいえ全く何もできていないわけではない。特に素因数分解の物理実装はいくつも存在し、規模も少しずつ大きくなってきている。この版の執筆時点での量子コンピュータによる素因数分解の最高記録は143である。……11×13だね。うん。現状では量子コンピュータより俺らの方が頭がいいと言って差し支えない。

量子コンピュータの登場する作品

など。多くの場合極めて高性能な、または特殊な性能を持つコンピュータとして描かれている。

脚注

*正しい分解は31337 × 1234543。これくらいなら古典コンピュータで解ける。
*限量子は∃「ある変数は～」∀「全ての変数で～」という論理学の記号であり、量子力学とは関係ない。
*正確には、「限量子消去アルゴリズムを経由して解こうとする限りは」できない。入試数学の範囲に特化した解法を使えば大きな問題も解けるかもしれないが、それは古典コンピュータにも言える。

量子コンピュータ単語

概要