情報系の物理学　第７回レポート

草山　広丞

量子コンピューターの原理

　21世紀の光情報通信システムは当然のことながら超高速，超信頼度が要求されるであろう．その基盤技術としてコンピュータの発展は必要不可欠である．超高速計算の需要は益々高まったとき現在の原理に基づくコンピュータでは対処できなくなることも想定せねばならない．近年，欧米を中心に量子コンピュータの理論研究が急速に進展し，その一部は実験的検証の段階にある．量子コンピュータの能力の一例を示す｀素因数分解の多項式時間での解法’がベル研究所のShorによって発見され，世界中に衝撃が走った．それ以来，量子アルゴリズム（ソフト）と，それらを実現する量子論理回路（ハード）の研究が加速され，現在アメリカ，イギリス，イタリア，ドイツにおいて大きなプロジェクトが進められている．

ここで量子コンピュータの基本原理を概説する．ブール代数における要素0,1を量子直交状態に対応させた時，それらは基本量子ビット(qubit)と呼ばれ，この直交状態の様々な組み合わせ（重ね合わせ）もまた，量子ビットとなる．一般に空間的に異なるシステムのn個の基本量子ビットを配列したとき古典ブール代数ではその可能な組は2ⁿ個となる．しかし，量子ではこの数の基本量子ビットによる組み合わせによって定義される量子状態もまた量子ビットとして扱えるため，ほぼ無限の組み合わせが可能となる．量子計算とはそれらを1つのベクトルとして処理するベクトル変換過程であり，無限の成分を含むそのベクトルが瞬時に計算されるので計算時間を極めて小さくできる．古典の計算問題を解くためのにこのようなベクトルの変換過程を設計することを量子アルゴリズムと言う．

一方，量子アルゴリズムを物理的に実現するために量子論理回路が必要である．しかし，近年，Controlled NOTと位相回転を行う論理回路の組み合わせで任意の量子アルゴリズムが実現できることが証明された．これによって，量子コンピュータの実現は量子論理回路による量子ネットワークの実現問題となっている．

ここでControlled NOTの数学的モデルは

|e₁>|e₂>　・・・　　　　　　　　　　　　　　　　　　　　　　　　
U₁₂|e₁>|e₂> = |e₁>|e₁ + e₂>
U₂₁|e₂>|e₁> = |e₁ + e₂>|e₂>

ただし，|e₁>,|e₂>は直交状態であり，ケットのなかの+は排他的論理和（XOR）を表す．

上式は計算基底{ |0>, |1> }に関する量子Controlled NOT ゲートU₁₂を定義する．

すでに，このような量子Controlled NOTがアメリカのNISTにおいて実験的に実現されている．量子現象を計算に用いる新しいコンピュータは計算速度，メモリーサイズ等の評価基準において想像を遥かに超える性能が期待できる．

「量子計算機だとどんないいことがあるの？」
今のところ、素因数分解がものすごく速くできることがわかっています (Shor のアルゴリズム)。
（素因数分解を多項式時間で実行できる…と言えば、わかる人にはわかってもらえる…と信じよう。）
他には,整列されていないデータベースに対する探索が高速に行えます。 (Groverのアルゴリズム)
量子計算のアルゴリズムで古典計算より速いと思われるものは、実はまだこれだけしかありません。だから古典計算より速いと思われる量子アルゴリズムを考えたら世界中から注目されるでしょうね。（これは本当）

「素因数分解が速くできたところでそれがなんなの？」
現在の公開鍵暗号方式が破綻します。（暗号が解読されてしまう）

これは、現在の公開鍵暗号が「大きな桁数の素数同士をかけざんするのは簡単だけど、素因数分解するのはとても大変」ということを使って秘密を守っているからです。
つまり,現在の計算機では, 太陽が燃え尽きるまで計算してもできないような素因数分解を, 数日(問題のサイズによりますが)で実行できれば非常に困ってしまうわけです。

「だったら暗号はなくなってしまうの？」
公開鍵暗号については、今使われているのとは異なる一方向関数を探してくる必要がありますが、その関数がNP完全問題に属するようなものであればまず大丈夫でしょう。

さらに、（秘密鍵暗号ですが）「量子暗号」が用意されています。これは、直接に絶対解読できない暗号ではありませんが、その代わりに「盗聴したら必ず発覚する」ので、これを使って「他に漏れていないという保証付の暗号表」を地理的に離れた二つの場所に用意することができます。あとは普通に暗号化して送ればいいだけですね。 (一度使った暗号表は二度と使わない, ヴァーナム暗号とか言うやつです。これが絶対安全な暗号方式であることは昔からわかっています。)

量子暗号

Four - states 量子暗号の原理

（１）送信システム

送信信号：0と1

送信機（Ａ）は垂直偏光と水平偏光で0と1を送信

量子状態: |↑>，|↓>

送信機（Ｂ）は右回転円偏光と左回転円偏光で0と1を送信

（２）受信システム

直線偏光用受信機（Ａ）と円偏光受信機（Ｂ）を用意する．

（３）伝送システム

エネルギー損失のない理想伝送システムを考える．

（４）システム運用

0と1の乱数を送信機（Ａ）と（Ｂ）のどちらかをランダムに選んでその0と1を送信．

受信者は同様に受信機（Ａ）と（Ｂ）のどちらかをランダムに選んで光子を受信．

公衆回線で受信機の選択系列を送信者に伝達．

送信者は受信者に送信機と受信機の一致点（系列）を通知．

送受信者はその一致系列を共通の系列として共有する．それを秘密鍵とする．

（５）盗聴者の能力

盗聴者は受信者と同じ機能を持つと仮定する．

盗聴法（Ａ）：回線を切断し盗聴した後，得られた0あるいは1を再送信する．

盗聴法（Ｂ）：回線の光の一部をモニターする．

（６）盗聴者の影響

送信者の送信機と受信者がそれに対応の受信機を選択したとき，そのビットには誤りが発生しない．盗聴者が介入すればある確率で誤りが発生する．なぜなら送信者の選択した送信機と同種の受信機を選択するのは確率的であるから，不一致の時，盗聴者が再送信したとき正規の受信者が送信者の送信機と同種の受信機を選択すれば結果が誤る確率がゼロとはならない．

もし，直線偏光と円偏光を同時に観測しようとすれば，不確定性原理によって両偏光信号に対して誤りが発生する．したがって送信者と受信者の間には誤りが発生する．

（７）盗聴者の検出

送信者と受信者の間で選択した装置が一致したビット列の一部を公開してビットが正しいか否かをチェックする．誤りがあれば盗聴者の存在が解る．

Two- states 量子暗号理論

（１）送信システム

送信信号：0と1

非直交量子状態を二つ用意する．

量子状態： |＋>, |－>