マーミンは、2000年から2006年にかけて6回、コーネル大学で量子計算に関する講義を行ったという。本書は、その講義ノートを進化させたものだそうな。とはいえ、物理的構造を想像せずにはいられない。実現不可能なものをいくら理論武装しても、技術屋にしてみればやはり興味を欠く。おまけに、本書には物理的構造を巧みに匂わせているところがある。尚、断っておくが、この記事はハードウェア構造をいい加減に想像しながら書いているので、注意されたし！
読者に求められる前提は、複素数体上の有限次元線形空間(複素ベクトル空間)に精通していることだという。こんな宣言をされると、数学の落ちこぼれには辛いが、あまり心配はいらない。付録には、ベクトル空間の性質とディラックの表記法などが解説される。基本となる演算系は、アダマール変換とユニタリ変換であって、それに cNOT演算子、NOT演算子、スワップ演算子、Z演算子、射影演算子を作用させるぐらいなもの。古典的なビット演算子で言えば、AND、OR、NOT、NAND、XORのような位置づけといったところか。古典コンピュータでは、NANDゲートだけですべての演算を実装できるが、量子コンピュータでは、ユニタリゲートとcNOTゲートがあれば最も単純な量子ゲートが構成できそうだ。
ただ、従来の論理回路では、FF(フリップフロップ)素子が重要な役割を果たす。すなわち、一時的に状態を保持できる仕掛けがなければ、多段演算を形成することができない。というより、FFには初期状態を与えるという重要な役割を同時に持っており、これがなければ回路検証はほぼ不可能である。量子コンピュータにおいて、その役割を担うのが量子レジスタということになろうか。だが、量子ビットが重ね合わせ状態として存在すれば、測定不可能となるから頭が痛い。
また、なんといっても数学的に最も重要な概念は、正規直交系である。これに演算子を合わせて眺めれば、対称性に射影的な幾何学操作でほとんど事足りることが見えてくる。複素空間で言えば、複素共役の性質、すなわちエルミート行列を検討することになる。そして、量子力学の角運動量との絡みをイメージさせてくれる。
さらに、量子の重ね合わせ状態を一気に平面空間に展開される様は、いかに行列式が並列演算と相性がいいかを味あわせてくれる。そして、数式を眺めているうちに、Σ や Π といった演算記号が量子の重ね合わせに見えてくる。
なるほど、線形代数学の参考書としてもなかなかだ。とはいえ、量子コンピュータはやはり手強い！
さて、量子コンピュータとは何か？それは、量子の重ね合わせ状態をとる量子ビットを利用することで、超並列演算を可能にするアイデアとでも言っておこうか。だが、量子の振る舞いは尋常ではない。量子状態に観測系が関与すると、たちまちデコヒーレンスに陥り状態自体を破壊してしまう。おまけに、複製不可能定理がつきまとい、光子の偏光状態を複製することすらできない。量子状態が測定不可能となれば、それを実現する量子ゲートを、どうやって検証できるというのか？測定という概念そのものを考え直す必要がありそうだ。不確定性原理とは、自己矛盾の法則であったか。
だからといって、そんなに悲観することもないのかもしれない。現在、ほとんどの機器が電子制御されるが、その根幹にあるトランジスタが電子の流れを完璧に制御できているわけではない。あるエネルギー準位において統計的に多数決の原理が確実に働けば、ON/OFFスィッチとして作用できるというだけのこと。しかも、半導体の歩留まりは、通常の製造ラインの感覚からすると信じられないほど低い。歩留まり60%なんて当たり前だが、自動車の製造ラインで40%が欠陥車となれば大騒ぎになるだろう。自動車のブレーキシステムが半導体制御となれば、こんなものに命を預けている。おまけに、集積設計の自動化が進めば、技術者はトランジスタが何であるかなど漠然としか知らなくていい。したがって、本書が量子力学の知識において極度にソフトウェアに重点を絞ってくれるのは、理に適っているのかもしれない。
その感覚は、実現性では一歩先を行く量子暗号技術に垣間見ることができる。量子暗号では、光子の直線偏光を利用して符号化される。垂直偏光、水平偏光、あるいは対角に±45度の偏光を量子状態に対応させるといった具合に。4つの偏光状態を識別できるだけでも、量子ビットの多様性、いや多次元性と言った方がいいかもしれないが、はるかに従来のビット構造の情報量を凌ぐ。本書は、最低限の回路構造であっても、強力な暗号システムが構築できることを教えてくれる。実験レベルでも、かなりの成果を上げているらしい。量子暗号が実用化されれば、RSA暗号をはじめ従来の暗号システムはことごとく危険に曝されるだろう。素因数分解が簡単に解けるとなれば、素数の正体までも明らかになるのだろうか？素数分布と深く関わるとされるリーマン予想までも？さらに、真のランダム性の正体までも？そして、計算の概念までも変革されるのかもしれん。量子暗号技術だけが実用化され、量子コンピュータが実用化されないとなると、それは幸か不幸かは知らんが...
1. ディラックの表記法と基本的な思考
本書は、古典的なビットをCビット(Classical)と呼び、量子ビットをQビット(Quantum)と呼んでいる。ちなみに、qubit という用語が幅を利かせているそうだが、著者はこの呼名を嫌っている。
ポール・ディラックは、ベクトルをケット(ket)と呼び、ボックス "| >" で表記した。ベクトル表記するものなら、なんでもボックスに入れられるという。
例えば、|5cm 北西に水平な方向> などと書いてもいいと。
数学のベクトル表記では、記号の頭に矢印を書き、記号の添字が次元的な意味を持つ。物理学では次元的な意味が重要であり、φ7798 と書くよりも、|7798> と書く方が合理的というわけか。数学者の中には、こうした記法をよく思わない人も少なくない。おいらも毛嫌いしてきたが、本書のお陰で抵抗感が薄れた。垂直棒と折れ線で囲むのが、三次元の物理空間をイメージさせるんだとか、んー？そうは見えんが...
また、元の空間ベクトルをケットベクトルと呼び、双対空間のベクトルをブラベクトルと呼んで区別している。<φ|ψ> と表記すれば、左半分がブラベクトルで右半分がケットベクトル。要するに内積を表している。
さて、重ね合わせの状態を持つQビットの最も単純な形は、Cビットの二つの直交関係として列ベクトルで表される。
|0> = [1; 0], |1> = [0; 1]
尚、octave風に行列を [ ]、行の区切りを ; を用いて表記している。
2次元空間の2つの直交ベクトル |0> と |1> を4次元に拡張すると、
|00>, |01>, |10>, |11>
ベクトル同士のテンソル積として、より厳密に記述すると、
|0> ⊗ |0>, |0> ⊗ |1>, |1> ⊗ |0>, |1> ⊗ |1>
基本的な思考は、2-Qビットエンタングル状態(量子のもつれ)に見ることができる。アダマール(Hadamard)を作用してから、cNOTを作用するといった具合に。
|ψ00> = (1/√2)(|00> + |11>) = C10H1|00>
一般化すると、
|ψxy> = C10H1|xy>
4つの状態 |xy> は正規直交系で、アダマールとcNOTはユニタリ。4つのエンタングル状態 |ψxy> も正規直交系。これを、ベル基底と呼ぶそうな。量子の重ね合わせ状態には、とりあえずアダマールを施してから考えようといったところか。
2. 測定ゲートとボルンの規則
量子の重ね合わせ状態を測定しようとすれば、状態そのものを破壊してしまう。おまけに、ユニタリ変換などとは違い、測定ゲートの作用を元に戻すことができない。測定の不可逆性に対して観測者ができることと言えば、確率を決定するぐらいであろうか。量子状態から情報を抽出する規則は、マックス・ボルンによって述べられたという。
n-Qビット状態 |Ψ> を 2n 個の基底状態で展開した場合、
|Ψ>n = Σ αx|x>n , (0 ≦ x < 2n)
この状態において、全Qビットの測定から得られる 0 と 1 の列が x となる確率 p(x) が与えられる。
p(x) = |αx|2
この式によると、振幅の持つ役割は特定の出力に対して確率を決定することになる。
「量子計算の芸術的な能力は、巧みに構成されるユニタリー変換を通じて、ほとんどの振幅 αx をゼロまたはきわめてゼロに近くすることで、有用な情報をもつどれかの x が測定で表示されるように十分大きな確率をもつような重ね合わせ状態にすることにある。」
確率を 0 か 1 に十分に偏らせる仕掛けこそが、量子コンピュータの実現の鍵というわけか。
ところで、一般的な計算過程では、入力値 x に対して、出力値 f(x) を計算することになる。古典的な計算では、その精度は 2k で規定される。対して、量子コンピュータでは、k個のQビットに対応する計算基底状態で表現されるという。そして、nビットの値 x と、mビットの値 f(x) を扱うために、入出力の双方でレジスタを装備する必要があるという。その理由は、逆変換できるように考慮されている。実は、n + m よりも多くのQビットレジスタを必要とするのだけど。
さて、アダマール変換は、Qビット状態のどちらが標的になるかを交代する効果があるという。そして、初期状態 |0>n にある入力レジスタの全Qビットにアダマール変換を作用させるだけで、関数 f(x) の 2n 個の評価ができるという。このような巨大スケールで瞬時に保存できるのは、量子並列性によって実現されるというわけだが、いきなりそう言われても狐につままれた気分になる。まぁ、物理構造には目をつぶるという前提だから...
3. トフォリゲート
Qビットゲートは、ユニタリ変換のみが、物理的に実現可能な制約であるという。とはいえ、現状では、1-Qビットや2-Qビットでも難しく、3-Qビットともなると、その実現は絶望的なようだ。
可逆演算のできる古典的な論理ゲートの最小構成は、3-Cビットゲートである。要するに、3入出力回路。演算するからには2入力は必要だし、桁上りにも対処したりと、そうした万能性を踏まえて可逆性を考慮すれば、最低限の論理ゲートはそんな構成になるだろう。量子計算で、これに対応する一例として、トフォリゲートというものを紹介してくれる。これは、制御-制御 NOTゲート（ccNOTゲート）とも言われる。なんと、トフォリゲートのQビットへの線形拡張は、2-QビットcNOT ゲートと、1-Qビットのユニタリゲートの組み合わせで構成できるという。
T|x>|y>|z> = |x>|y>|z ⊕ xy>
4. ショアの周期発見アルゴリズム
周期関数 f(x) = ax (mod N) の周期を高速に計算する方法は、RSA暗号の解読を可能にする。ただし、N = pq で、p, q は十分大きな素数で構成される。この関数は、s が周期の倍数の時のみ、 f(x + s) = f(x) が成り立つという単純な性質がある。ただ、データ群が正弦波や余弦波のような連続関数であれば、周期性を見出すことはそれほど難しくない。実際、フーリエ変換が連続性に対して強力な道具となる。だが、暗号で扱うデータ列は極めてランダム的な離散群であり、ここから周期性を見出そうとすれば、半端なサンプル数では済まない。そして、ランダムに与えられる x に対して、f(x)を計算しながら、再び f(x) に等しくなるまで評価を続けるというようなことを繰り返す羽目になる。しかも、ビット数 n が増えれば指数関数的に演算量が増大する。
ところが、1994年、ピーター・ショアは、量子計算を用いると n3 よりもほんの少しだけ増大する時間で周期が求まることを発見したという。周期を求めるアルゴリズム自体は古くからある。そぅ、フェルマーの小定理から起因する問題として知られるやつだ。
それは、xr を N で割った時、余りが 1 となる最小値 ｒ を求めるという考え方である。
xr ≡ 1 (mod N), (x < N)
x を適当に決めながら、r が偶数であれば、因数分解できるのは明らか。
xr - 1 = (xr/2 + 1)(xr/2 - 1)
よって、xr/2 ± 1 と N の最大公約数は、ユークリッド互除法で求まる。ユークリッド互除法自体は単純で、大きい方を小さい方の数で割り、余りでさっきの除数を割るという繰り返し。余りがゼロになった時点で終わる。
しかし、r を高速に求める方法が見つかっていなかった。フーリエ変換ではかなり手間がかかり、FFTでも n ビットに対して、だいたい 2n 回の演算が必要である。ヘタすると、しらみ潰しに余りが 1 になる r を求める方が早い。
さて、ショアのアルゴリズムの核心部分はここから...
両辺に xm を掛けて拡張すると、
xrxm = xr + m = ≡ xm (mod N)
これは、x の累乗を N で割った余りにおいて周期性が現われることを示している。除算の余りとは、除数に対する巡回演算でもあるのだから当たり前だけど。
ショアのアルゴリズムとは、多重周期性を確率的に多項式によって一気に計算してしまおうという考え方のようだ。その中核には超高速な量子フーリエ変換が関与する。それは、単純に全Qビットに対してアダマールを作用させるだけ。
UFT |x>n = (1/2n/2)Σexp(2πixy/2n) |y>n , (0 ≦ y ≦ 2n - 1)
まず驚かされるのは、ユニタリ変換で定義されることである。ちょっと考えれば、驚くほどでもないけど。言うまでもないが、フーリエ変換が三角関数を基底にするのに対して、アダマール変換は矩形波を基底にする。なるほど、位相 exp(πi/2n) を多段シフトするようなゲート回路を考えればよさそうだ。量子計算は、周期性を多重化するような演算には、とびっきり強いということは言えそうか。とはいえ、振幅の確率分布でしかない。まぁ、奇妙な量子の振る舞いを振幅の確率分布で示せるというだけでも感動ものか。しかも、アダマールとユニタリだけで。
また、量子フーリエ変換は、n重アダマール変換と類似しているという。参考までに、n重アダマール変換も記しておく。
H ⊗ n |x>n = (1/2n/2)Σexp(πix・y/2n) |y>n , (0 ≦ y ≦ 2n - 1)
ただし、H ⊗ n = H ⊗ ... ⊗ H (n回)
原理的な違いは、n重アダマール変換でビットごとのx・y の内積の部分が、量子フーリエ変換では xy の通常の積になっている。
5. グローバーの探索アルゴリズム
データ検索に思いっきり時間がかかるのは古くからある問題で、ヘタすると比較一致処理を全データに施すことになる。
ところが、量子コンピュータでは (π/4)√n 回程度で、1 に非常に近い確率で検索できるという。ランダム検索よりも因子 1/√N だけ効率よく探索できるというのがミソ。そのアルゴリズムは、ロブ・グローバーによって発見されたという。
さて、n ビット整数 x が、目的の a かどうかを伝える量子探索サブルーチンが利用できると仮定すると、その値は f(x) で与えられる。
f(x) = 0, (x ≠ a); f(x) = 1, (x = a)
そして、1-Qビット出力レジスタに作用するユニタリ変換 Uf を利用するという。
Uf(|x>n |y>1) = |x>n |y ⊕ f(x)>1
まず、Uf を適用する前に、1-Qビット出力レジスタにアダマールを作用させておく。
H|1> = (1/√2)(|0> - |1>)
Uf の作用は、x = a の時だけ、-1 を掛けることになる。
Uf(|x> ⊗ H|1>) = (-1)f(x) |x> ⊗ H|1>
すると、n-Qビット入力レジスタ上の計算基底状態の作用が、次のユニタリ変換 V の作用と同じ効果を得るという。
V|x> = (-1)f(x) |x> = { |x> (x ≠ a の時) , -|a> (x = a の時) }
まず動作に入る前に、n-Qビットの初期状態を、起こりうる全状態の一様な重ね合わせとしておく。
|φ> = H ⊗ n |0>n = (1/2n/2)Σ|x>n , (0 ≦ x ≦ 2n - 1)
さらに、ユニタリ変換 W を加えて、V と W を次のように与えている。
V = 1 - 2|a><a|
W = 2|φ><φ| - 1
尚、|a><a| と |φ><φ| は射影演算子。
ここまでは非常に複雑なプロセスである。ところが、ユニタリ変換 V と W を仮定した途端に思いっきり単純になるから、これまた狐につままれた気分になる。初期状態 |φ> にある入力レジスタに、積 WV を何度も適用させるだけという仕掛けに変貌するのだから。V と W は一見関係ないようにも見えるが、|a> と |φ> がほとんど直交していることがミソのようだ。そのなす角度をγとすると、
cos γ = <a|φ> = 2-n/2 = 1/√N
さらに、|φ> と θ = 2π - γ をなすような、|φ> と |a> の実線形結合による規格化されたベクトル |a⊥> を用いると便利だという。
sin θ = cos γ = 2-n/2 = 1/√N
そして、√N が大きい時、θはほとんど正確に次のように与えられるという。
θ ≈ 2-n/2
平面上で角運動を繰り返せば無限になる。そこで、最終的には、
(π/4)2n/2
に近い回数を適用すればいいとしている。積 WV を適用する回数で、θの整数倍になるという仕掛け。グローバーのアルゴリズムとは、角運動的な作用のループで構成できるというわけか。
6. 量子誤り訂正
本書で紹介される単純化した例はイメージしやすい。1-Qビット状態に対して、3-Qビット符号を適用している。
この図は、単一ビットのフリップエラーが生じると仮定した場合の量子誤り訂正回路の一例を示している。
まず、α|0> + β|1> を α|000> + β|111> へ拡張する。破損していない状態は、|000> と |111> だけ。Qビット状態は、ボルンの規則により |α|2 の確率で、|000> に、|β|2 の確率で |111> になる。さらに、巧妙な手段として、初期状態 |0> にある二つの補助Qビット |x> と |y> を付加する。図のMは測定ゲートを示している。つまり、補助Qビット経由で間接的に測定すれば、出力 α|000> + β|111> に影響を与えないという仕掛けだ。|x> と |y> で構成される4つの状態で、符号語のどのビットがフリップされたかに対応させている。
Qビット同士の相互関係のみを抽出することで、重ね合わせは維持されるということだが、補助Qビットだって測定した瞬間に破壊されるのではないか？どう転んでも測定が関与する限り、自己矛盾に陥るのではないか？確率的に定められる何らかの方策があるのか？Qビット状態とCビット状態を変換するような仕掛けがあれば、ありがたいのだか。あるいは、光子の直線偏光の位相差で、ほぼ確実に定められる方法があるのか？そのあたりを量子暗号の説明で匂わせてくれる。
7. 量子暗号
どんなに強力な暗号システムを構築しても、理論的には解読の危険性が常につきまとう。ランダム列を用いるバーナム暗号は、完全に解読不能とされる。使い捨て暗号方式(One-time Pad)とも呼ばれるやつだ。それでも、遠隔地へ暗号鍵の配送が必要で、暗号通信において重要なのは、いかに鍵を秘密裏に送れるかにかかっている。
では、通信経路が量子システムで構築されていたらどうだろうか？盗聴するということは測定することなので、必然的にデコヒーレンスに陥り、データは破壊される。となれば、受信者は伝送路で介在している奴がいることに気づくかもしれない。
こっそり測定装置を設置したところで意味がないとなれば、堂々と伝送路をジャックしてしまえばどうだろうか？盗聴者は伝送路に細工することができても、受信者の装置を遠隔操作したり、送信者になりすましたりするのは難しい。送受信者の間では、通信プロトコルによってソフトウェア的に経路が確立されるはずで、テレビ放送のように一方的な受信とはならないだろう。
さて、量子暗号は最も実用化に近いテクノロジーだそうな。それは、Qビット1個ずつで機能し、1-Qビットゲートだけで済むからだという。少なくとも最も簡単なプロトコルでは、cNOTゲートなど必要としないらしい。物理系は非常に単純で、単一光子による直線偏光で、Qビットの状態を担う。1984年 BB84 として知られるアイデアはチャーチル・ベネットとジル・ブラサールによって発明された。
ここでは、暗号鍵の受け渡しに絞って記述してみる。
|0> および |1> を垂直偏光と水平偏光に対応させ、これをタイプ1としよう。
状態 H|0> = (1/√2)(|0> + |1>) と H|1> = (1/√2)(|0> - |1>) を±45度の対角に偏光させ、これをタイプHとしよう。
受信者は、Qビットを受け取ると、アダマールを作用させるかどうかをランダムに決める。受信が終了した時点で、送信者は Qビットがタイプ1かタイプHかを伝える。
だが、タイプ1が |0> と |1> で、タイプHが、H|0> と H|1> だということはまだ伝えない。送信側で、タイプ1とタイプHがランダムに切り替えられるならば、受信側で当てすっぽに選んでも、ほぼ半分の確率で情報は読めるだろう。
次に、受信者は、どのQビットから等しいランダムビットを共有できるのかを送信者に問い合わせる。そして、受信者と送信者でタイプが異なる約半分のデータを捨てる。共有した等しいランダム列から使い捨て鍵を作るわけだ。
確かに、Qビットが保存できるならば、理に適っていそうだ。しかしながら、光子の偏光状態を保持することは無理だと、散々聞かされてきた。位相が90度もずれれば確率的になんとか識別できるということか？いや、わざと二つのタイプに分けることにミソがあるのか。
0 コメント:
コメントを投稿