第三部、量子コンピュータのその4

これまで、2回にわたって量子コンピュータの基礎を説明してきて、話が長くなってしまった。これも、量子コンピュータの概念そのものが、奥深く、新しいものであるためである。

第二部で示したアルゴリズムの誕生とソフトウェアの図に、さらに量子コンピュータとの関係を加えてみると、量子コンピュータの意義と現状が明確になる。

ポイントは、既に現行の従来型コンピュータによるソフトウェア社会が出来上がっている中に、量子コンピュータが競争できる可能性を示すこと。そのためには、全く新しい、量子現象に基づくハードウェア技術が未だまだ、発展途上であること。今は、この技術開発に注力しながら、既に成熟したソフトウェアと融合的な技術の架け橋を用いて量子コンピュータの可能性を示そうと努力している段階である。

はっきりしていることは、従来のパソコンのような低位コンピュータの市場は、量子コンピュータには元々ないことである。量子現象に基づくハードウェア技術をそのような市場に持ち込む意味はない。従来型コンピュータが発展して来た、半導体 LSIの高集積化、微細化の競争トレンドとは、異なる共存の可能性が量子コンピュータには求められる。

量子コンピュータが機器、部品として世の中に供給されるのではない。量子コンピュータがソフトウェア世界の中に組み入れられる形で、利用されて行くという、クラウドとか、大きな通信インフラ(暗号通信)の中での存在意義ということになるのではないか、と考えられる (次図参照)。

ハードウェアとしては、従来のコンピュータが半導体 LSI中での電流のスイッチ制御による0, 1の古典ビットによる論理で動いている。対して、量子コンピュータのハードウェアは量子力学的状態による特有の量子の位相制御などによる並列処理の論理で動いている。量子ビットが量子もつれの状態を安定に保ち動作することが必要である。現状の量子コンピュータのハードウェアは未だ集積度が低く、動くソフトウェアとしても限定されたものではあるが、ある意味では量子コンピュータのソフトウェア環境の整備は、既存の古典コンピュータ上のソフトウェアの発展のおかげでハードウェアよりも先に整備が進んでいると言える状況である。既に、IBMをはじめ実際に動くソフトウェア環境が用意されている。

しかし、一方、量子コンピュータは万能選手ではない。既存の古典コンピュータ上のソフトウェアとそれぞれの長所、特徴を補完しあう関係にある。例えば、次表のようなものが有望であると考えられている。

いよいよ、ここからが本番。

前にドイチュのアルゴリズムを紹介したが、これは量子アルゴリズムとして最初の先駆的なものであった。実用化を目指す量子アルゴリズムの中で、代表的な二つを先ず、説明していく。

グローバーのアルゴリズム

データベースの検索問題。二分探索法などでは検索できない大規模な(Nで規模をあらわして)データベースの検索を、古典コンピュータではN回の探索処理が必要であったものが量子コンピュータでは $\sqrt{N}\$ で可能であることをグローバーが数学的に明らかにした。

その手法は、前のドイチュ-ジョサの方法に少し似ているところがあるが、図示すると、量子nビットでデータベースを検索する状況、 $2^n = N$ を想定する。下図では、量子nビットを簡略化して2ビット、2本線のみで表記した。

Hはアダマールゲート、Xはパウリゲートで量子ビットの0と1を切り替える。マーキングの中の中央のゲートはCNOTゲートで上のコントロールビットと、下のターゲットビットの値により挙動が異なる。コントロールビットが1のときにだけ、ターゲットビットを反転させる (前のドイチュ-ジョサのステップC)。コントロールビットが0のときには何も操作しない。マーキングは二分探索のような目印を付けることで、検索条件を設定することです。振幅増幅反転では、データベースへ問い合わせた測定結果が目印を付けただけの何もしない状態では、同じ確率で出てしまう。そこで、平均値を軸にして、目印の値の符号を反転させる処理を繰り返し行い、目印を付けたデータの出現確率を上げます。

出現確率は $sin^2 (mθ)$ のように、繰り返しの回数m(とある角度θ、下記)により変わる。

振幅増幅反転での符号反転、リフレクション。リフレクションは回転か?量子状態は複素数のベクトルなので、3次元空間での鏡映変換を考える。A fast quantum mechanical algorithm for database search, Lov K. Grover

https://arxiv.org/abs/quant-ph/9605043

$2^n$ の計算基底に対して、検索を行う検査器は3次元的に直交していなければならない。検査器のことを、オラクルoracle。もちろん、数値計算上は直交から多少ずれていても問題ない。

グローバーの探索アルゴリズムの実装については、

「量子コンピューティング」PythonとQ#で学ぶ、Sarah Kaiser, Cassandra Granade,朝倉書店2022年

等を参照。

量子アルゴリズムのタイプの大別として、このようなグローバー型の、いわゆる計算を繰り返すデータベース検索と、もう一方、位相推定型と呼ばれるものがあります。位相推定型は、各種問題の最小コストを求めるもので、次項のショアのアルゴリズムもその一つです。

ショアのアルゴリズム

素因数分解の量子計算アルゴリズム、ショア、1994年はRSA暗号という現在使われている暗号の将来に関わるということでも、注目を集めたものです。素因数分解の裏には、周期性があり、前に述べた位相推定という周期性を探す回路。それと、量子フーリエ変換という周期をビットに落とし込む操作の二つから成り立ちます。数論と量子の物理の世界、さらに計算アルゴリズムを組み合わせた理論なので複雑、まわりくどい説明になることをご容赦下さい。

なお、ショアのアルゴリズムは理想的な量子コンピュータの存在を前提としている。前に述べた現在の量子コンピュータの安定性のレベルでは十分な精度が得られないので、今の時点では(暗号化に必要な大きな数に対しては)現実には実現されない理論での話にとどまっている。

二つの数の最大公約数は高速に計算が可能。ユークリッドの互除法として知られている。ショアのアルゴリズムによる因数分解の手順。

手順1: 因数分解したい数をNとする。Nに対してお互いに約数をもたないNより小さい数xを勝手に決める(ユークリッドの互除法が使える)。

手順2: のうち、Nで割ったら余りが1になっているような最小の自然数rを探す。

手順3: もし、求まったrが奇数だった場合には、手順1に戻りxを決め直す。

手順4: 偶数のrが求まったので、

$(x^\frac{r}{2} +1)(x^\frac{r}{2} -1)$ とNは公約数をもつから、これら積のうちのどちらかとNは公約数をもつ。それをzとし、ユークリッドの互除法で最大公約数zを求める。

ここまでは古典的な方法で、よく知られていたものだった。問題は、手順2のrの探索を高速に行う方法がなかったことで、ショアは量子アルゴリズムによりこれを高速に行う方法を発見した。エッセンスは、

周期関数となる、冪剰余 $x^a modN$ を計算して(a=0, 1, 2, …)、その周期r(=位数)を見つける。前に述べた「位相推定という周期性を探す回路。それと、量子フーリエ変換という周期をビットに落とし込む操作」の二つからなる。

フローは、

初期状態を準備する

第1レジスタすべてにアダマールゲートを作用させる

制御ユニタリゲート $U_{x,N}$ を作用させる

第1レジスタに量子フーリエ逆変換を行う

第1レジスタを測定し、s/rを得る

位数rを決定する

となる。

制御ユニタリゲートは $U_{x,N}$ |a> = |ax modN> です。sは0とr-1の間のランダムな整数で、ユニタリ演算子の固有状態に対応します。

ブラケット記法で

|0>|1> $\xrightarrow{H}$ $\frac{1}{\sqrt{2^t}}$ $\displaystyle \sum_{a=0}^{2^t-1}$ |a>|1>

$\xrightarrow{U_{x,N}}$ $\frac{1}{\sqrt{2^t}}$ $\displaystyle \sum_{a=0}^{2^t-1}$ |a>| $x^a modN$ >

$\xrightarrow{QFT^{-1}}$ $\frac{1}{\sqrt{r}}$ $\displaystyle \sum_{s=0}^{r-1}$ |s/r>| $u_{s}$ >

ここでは、固有状態| $u_{s}$ >についての説明は省略します。

周期性の例、N=35, x=3 となる周期、位数r = 12 となる。

Uを作用させることにより $x^a modN$ をすべて計算する。 $U_{k}$ は $U^{2^k}$ でUを $2^k$ 回作用させたもの。しかし、全て計算したとしても特定の結果、周期性の情報などが取り出せるわけではないので(位数に関する情報が得られる状態を観測できる確率がほぼ0)、次のステップが必要になります。

逆量子離散的フーリエ変換を行って確率の強め合いを起こして位数の情報を取り出す。

N=21, x=5の例

位数rは5のベキ乗を21で割った余りがどのくらいの周期で変化するかというのと、一致しています。

実は、観測される確率が極大になるような|m⟩は、n量子ビットを使ったとき、求めたい位数をrとすれば $\frac{2^n}{m}$ ≃ $\frac{r}{k}$ (kは整数)を満たすものです。

Uをうまく作用させたことによって、 $5^0$ ～ $5^{15}$ を21で割った余りをすべて計算することができました。

Uを作用させていったあとには位数rより小さい0以上の整数をbとして

|b> + |b+r> + |b+2r> …

という形のベクトルがでてきます。これを逆量子離散的フーリエ変換するとどうなるか

逆量子離散的フーリエ変換は、

|j> $\rightarrow$ $\frac{1}{\sqrt{2^n}}$ $\displaystyle \sum_{k=0}^{2^n-1}$ $e^(-i\cfrac{2πkj}{2^n}$ ) |k>

という変換でしたから、

|b> $\rightarrow$ $\frac{1}{\sqrt{2^n}}$ $\displaystyle \sum_{k=0}^{2^n-1}$ $e^(-i\cfrac{2πkb}{2^n}$ ) |k>

|b+r> $\rightarrow$ $\frac{1}{\sqrt{2^n}}$ $\displaystyle \sum_{k=0}^{2^n-1}$ $e^(-i\cfrac{2πk(b+r)}{2^n}$ ) |k>

…

というように変換されていきます。

逆量子フーリエ変換されたあとのベクトルを重ねていくと|0⟩〜| $2^n$ −1⟩のベクトルの中で弱め合うベクトルと強め合うベクトルが出てくることに注目してください。強め合うベクトルというのはどのような条件を満たすものでしょうか？強め合うようなベクトル|m⟩は、同じ方向のベクトルが多数重なり合えばよいので、

$\frac{2πmr}{2^n}$ ≃2kπ

を満たすようなある整数kが存在しているのです。これを整理して

$\frac{2^n}{r}$ ≃ $\frac{m}{k}$

上記の関係が得られます。

今回で言えば、

16/m≃6/k (kは整数)

となるような|m⟩が観測される確率が極大になります。今回は、使っている量子ビットの数が少ないため、近似の精度が低くなってしまっていますが、もっと量子ビットを増やせばかなり精度の良い近似が得られて、rの情報が得やすくなります。

今回のように4量子ビットを使った場合には、

16/3,16/5,16/8,16/11,16/13≃r/k

となるので、何度も観測を繰り返して観測確率が極大になっているところを求めていけば、r=6ではないかということがわかります。

これで、ようやく位数を求めることができました。原理的には巨大な合成数についても全く同じようにできます。

位数rが求まれば、古典的な計算に戻り、前の手順3, 4にしたがい素因数分解が完成します。

量子力学の波動関数の周期と素数に関するオイラーの定理、フェルマーの小定理の「周期」、数論を組み合わせて、シンクロナイズさせているところが、ショアの方法のすごいところです。量子コンピュータはそれを実用化しようという、すばらしい発明なのです。

はじめにから、これまで10回かけて、AI、囲碁AIから量子コンピュータを経て、ようやく「囲碁と素数」(の関係性)にたどりついた。素数とはいっても、未だ、モジュラ算術の程度の話に過ぎない部分ではあるが。素数定理やリーマン予想に関する話、量子力学との関連などは、既に多くの本、サイトがあるのでしばらく書く予定はない。

モジュラ算術にからみ、ドイツのミュンヘンで面白い体験をしたので、最後に紹介する。

ただし、長くなったので次回にまわすことにする。