NMR量子計算によるNP完全問題と因数分解の解法
9
0
0
全文
(2) Vol. 43. No. SIG 7(TOM 6). SAT と因数分解に対する NMR 量子計算. プ記号の有限集合 Γ を用いて，状態遷移関数 δ によ. テープ. り定義される．たとえば，量子 Turing 機械 M の状. a. ···. 態遷移規則 δ(p, a, b, q, d) = c は，M が状態 p で記. ···. ❅ ❅ヘッド. 号 a を読んでいるとき（ M のこの様相を c1 と呼ぶ） に，テープ上の現在ヘッドがある区画に記号 b を書き. p. 込み，状態を q に遷移させ，ヘッドを方向 d ∈ {L, R} に 1 区画動かす（ M のこの様相を c2 と呼ぶ ）とい. 有限制御部. う事象の振幅が c であることを表している（ c は複素. 図 1 Turing 機械． Fig. 1 A Turing Machine.. 数） ．このとき，M が様相 c1 から c2 に遷移する確 率は，|c|2 となる．. 1994 年に AT & T の Peter Shor が，この量子 Turing 機械を用いると，整数の因数分解を小さな誤り確. 11. に示すように，テープ，ヘッド と有限制御部から構成 される．テープは，同じ大きさの区画ごとに区切られ. 率で多項式時間内に行えることを示した．このアルゴ. ていて，両方向に無限に伸びている．ヘッドは，テー. リズムの動作の概要は，以下のとおりである．入力を. プの 1 つの区画に対して記号の読み出しや，書き込み. 整数 N とするとき，まず滑らかな整数 q を選び，す. を行うことができ，また，テープ上を 1 区画ずつ左右. べての x mod N に対し ，|N, q, x, 0 とラベル付け. に移動することができる．ある時点における有限制御. された状態の重ね合わせに対し ，modq の 2 段離散. 部の状態と，その時点でヘッドが読んでいる記号との. Fourier 変換を行う．すると所望の結果が得られるラ ベルについては正の干渉が起こり，そうでないラベル については負の干渉が起こるので，所望の結果が得ら. 対によって，Turing 機械の次の状態への遷移，テー. れる確率が増幅される22) ．. プへの記号の書き込み，テープヘッド の移動の方向が すべて定まる． 形式的には，Turing 機械は以下のように定義される．. このアルゴ リズムにより，もし量子 Turing 機械が. 定義 2.1 Turing 機械（ Turing Machine，以下. 物理的に実現できれば，現在の多くの公開鍵暗号系の. TM と略す）M は，以下の条件を満たす 7 項組 Q, Σ, Γ, δ, B, q0 , F として定義される． ( 1 ) Q は状態の有限集合，. 安全性が保証できなくなるため，Shor の結果は世間 の注目を集めた． 一方，量子計算機の実現に対する研究も現在さかん に行われており，イオントラップ，量子ドット，cavity. QED や，NMR を用いた方法などが提案されている． 量子力学的状態が崩れる，デコヒーレンスという現象 を考えた場合，NMR は緩和時間が長いため非常に有 利であり，このため，量子計算機の実現を目指す研究 者の間で広く注目を集めている3)∼5),7)∼16),19),20),23) ． しかし，NMR を用いた量子計算は通常の量子計算 とは異なっている．このため，量子 Turing 機械上で. (2) (3). Γ はテープ記号の有限集合， B ∈ Γ は空白記号，. (4) (5). Σ ⊆ Γ − {B} は入力アルファベット ， q0 ∈ Q は初期状態，. (6) (7). F ⊆ Q は最終状態の有限集合， δ : Q × Γ → Q × Γ × {L, R} は M の状態遷 ✷ 移関数．. TM M の動作は，状態遷移関数 δ によって定義さ れる．δ (p, a) = (q, b, d) は，M の現在の状態が p で，. 動作するアルゴ リズムでも，そのままでは，NMR 装. ヘッドが読み込んだ記号が a ならば，M は状態を q. 置上では正し く動作しないものが存在する．Shor の. に変え，テープ上の現在ヘッドがある区画に記号 b を. 因数分解アルゴ リズムもその 1 つである．. 書き込み，ヘッドを方向 d ∈ {L, R} に 1 区画移動す. 本論の目的は，NP 完全である充足可能性判定問題 に対する NMR 装置上の量子アルゴ リズムの提案と，. Shor の因数分解アルゴ リズムを NMR 装置上で正し く実行するための修正の提案を行うことである．. 2. 諸 定 義 2.1 Turing 機械 Turing 機械は，1936 年に A.M. Turing が考案した 計算機の数学的モデルである．Turing 機械は，図 1. るという動作を表している． また，TM M は，δ の値が定義されていない組 (p, a) に陥ったときと，最終状態 qf ∈ F となったときに停 止する．特に，最終状態 qf ∈ F で停止するとき，TM. M は入力を受理するという． Turing 機械は，有限制御部の状態，テープの内容， ヘッド の位置を 1 ステップごとに変化させる．3 項組 (p, a1 a2 · · · am , i) を Turing 機械の様相という．ただ し ，p ∈ Q，a1 a2 · · · am ∈ Γ∗ ，0 ≤ i ≤ m + 1 とす.
(3) 12. Sep. 2002. 情報処理学会論文誌：数理モデル化と応用. る．ここで，p は現時点での有限制御部の状態，記号. QTM においては，時間発展作用素 Mδ はユ. 列 a1 a2 · · · am はテープの内容，i はヘッド の位置を. ニタリ行列でなければならない． すなわち，Mδ† を Mδ の転置共役行列，I を単位行列. 表す． 次に，通常の TM に条件を付加し ，可逆 TM とい う概念を導入する． 定義 2.2 2) 以下の 2 つの条件をともに満足すると き，かつそのときに限り，TM M は可逆であるという．. (1). (2). M の各状態が一方向にのみ遷移する．つまり， δ (p1 , a1 ) = (q, b1 , d1 )，δ (p2 , a2 ) = (q, b2 , d2 ) ならば，d1 = d2 である．. とするとき，. Mδ† Mδ = Mδ Mδ† = I が成り立たなければならない．. ✷ また，QTM と RTM の間に以下の定理が成り立つ． 定理 2.1 2) QTM M の時間発展作要素 UM が Eu-. 状態遷移関数 δ は方向が無視されるとき，1 対. clid 距離を保存するとき，M は適格であるという．任. 1 である．. 意の RTM は適格な QTM である．. TM M が可逆であるとき，M のことを可逆 Turing 機械（ Reversible Turing Machine，RTM ） という． 量子計算のモデルである量子 Turing 機械は，以下 のように定義される．. QTM が，通常の Turing 機械と最も大きく異なる 点は，QTM では単一のプロセッサ上で任意の並列度 の並列計算が行える点にある． QTM では，2 つの入力 X ，Y の両方を同時に符 号化した入力を用意することができる．このことは実 ，Y として 際には，X ，Y をある線形空間内の点 X. 2.2 量子 Turing 機械 定義 2.3 17) 量子 Turing 機械（ Quantum Turing Machine，QTM ）M は，以下の条件を満たす 7 項組. この符号化を，X と Y の量子重ね合わせ（ quantum. Q, Σ, Γ, δ, q0 , B, F として定義される．ただし ，C は複素数全体の集合とする．. superposition ）という．4 章で示す変換 V を用いる と QTM は，指数個の入力の量子重ね合わせを線形時. (1) (2) (3). Q は状態の有限集合， Γ はテープ記号の有限集合， B ∈ Γ は空白記号，. 間で用意できる．. (4) (5). Σ ⊆ Γ は入力記号の集合， q0 ∈ Q は初期状態，. (6) (7). F ⊆ Q は受理状態の集合， δ : Q × Γ × Γ × Q × {L, R} → C は M の状. +Y を入力することに相当する． 表現し，QTM に X. 情報の最小単位である 1 bit を 2 状態物理系で構成 する．この 2 状態に対応する物理状態を 2 次元 Hilbert 空間上の基底 |0，|1 で表す．量子論では列ベクトル を |· と表記し，ケット ベクト ルと呼ぶ．通常，. . |0 =. ✷ 態遷移関数． QTM M において，δ(p, a, b, q, d) = c は，M が 状態 p で記号 a を読んでいるとき（ M のこの様相を. ととる．. . 1 0. . ,. |1 =. . 0 1. 状態の任意の重ね合わせを保持できるビットを量子. c1 と呼ぶ ）に，テープ 上の現在ヘッドがある区画に. ビット（ quantum bit，qubit ）といい，入力の量子重. 記号 b を書き込み，状態を q に遷移させ，ヘッド を. ね合わせに対して行われる計算を，量子並列計算と. 方向 d ∈ {L, R} に 1 区画動かす（ M のこの様相を. いう．. c2 と呼ぶ）という事象の確率振幅が c であることを 表している．このとき，M が様相 c1 から c2 に遷移. QTM のテープのある区画が重ね合わせ状態 α|0 + β|1 にある場合（ ただし ，|α|2 + |β|2 = 1 とする） ，. する確率は，|c|2 であると定義する．. その区画を観測すると，0 が確率 |α|2 で，1 が確率. M の状態遷移関数 δ は，以下の行列 Mδ で表され. |β|2 でそれぞれ読み取れる．また，観測が行われると. るような様相の重ね合わせの線形空間における線形写. 波束が収縮し，重ね合わせ状態は失われて，観測され. 像を定義する．Mδ の各行，各列には M の様相が対. た区画の値は 0 または 1 に定まる．. 応する．c1 ，c2 を M の 2 つの様相とするとき，Mδ. 3. NMR 量子計算のモデル. の c1 行 c2 列成分は，c2 から c1 への M の 1 ステッ プの遷移と対応した δ の値である．このような遷移. NMR とは核磁気共鳴（ Nuclear Magnetic Reso-. が M に存在しなければ，Mδ の対応する成分は 0 と. nance ）の略である．NMR は，有機化合物の構造や その立体配座，立体配置の決定を可能にする．そのた. する．.
(4) Vol. 43. No. SIG 7(TOM 6). SAT と因数分解に対する NMR 量子計算. 13. め，有機化合物の構造決定に NMR はなくてはならな. f (x1 , x2 , · · · , xn ) に対する SAT を解く BQTM M を. いものである．合成高分子に対しては，基本化学構造. 以下のように構成することができる．. の決定はもとより，末端基分析，立体規則性の決定，. (1). ブール式 f と n 個の変数の値は，M の入力と して与えられる．以下では M の様相と f の変. 共重合体の共重合比の決定も可能である．また，分子 量 2 万程度のタンパク質では，溶液中の立体構造が決. 数に対する割当てを同一視する．つまり，M の. 定できる．NMR は赤外線吸収分光法などの他の分光. 様相を |x1 , x2 , · · · , xn , xn+1 で表す．ただし，. 法とは異なり，「位相」を取り扱うことのできる分光. x1 , x2 , · · · , xn は f の n 個の変数に対応する量 子ビットであり，xn+1 は f の値に対応した量子. 法であるという点が特徴的である． 量子計算の観点から，NMR を考えた場合，各分子. ビットである．M の初期様相を |0, 0, · · · , 0, 0. を 1 つの量子計算機と考えることができる4) ．そして，. とする．f の n 個の変数に対して 2n 個の異な. 測定という行為により，多数の量子計算機を観測し ，. る割当てが存在する．x1 から xn の各量子ビッ. 計算によって得られた重ね合わせ状態を収縮させて，. トに以下の変換を適応することにより，M は. そのアンサンブル平均をとることができる．この計. これら 2n 個の異なった割当てに対応する様相. 算モデルは，通常の量子 Turing 機械とは異なってい. の重ね合わせ状態になる．. . る．我々は，NMR 量子計算に対する計算モデルであ る Bulk 量子 Turing 機械を以下のように定義した18) ． 定義 3.1 18) Bulk 量子 Turing 機械（ Bulk Quan-. tum Turing Machine，BQTM ）M は，QTM と同様 に定義される．ただし BQTM の場合，観測の定義が 以下のように変更される．QTM の場合と区別するた. 1 1 1 1 √ ··· |x1 , x2 , · · · , xn , 0 2n x =0 x =0 x =0. 測定という用語を用いることにする．BQTM のテー. 1. プの区画が重ね合わせ状態 α|0 + β|1 にある場合， 2. 2. 2. 実数値 θ = |β| − |α| が測定される．|α| + |β| = 1. . −1 1. M は 1 ステップでこの変換を 1 回適用するこ とができる．最終的に，以下の重ね合わせ状態 を得ることができる．. め，BQTM においては，観測という用語は用いずに，. 2. 1 1. 1 V = √ 2. (2). n. 2. 上の重ね合わせの各様相においては，変数 x1 ,. であるから，−1 ≤ θ ≤ 1 である．実数値 θ は k. x2 , · · · , xn に対する割当ては明確に指定されて. ビットの 2 進数で表されるものとする．ここで，k. いる．したがって，M はこれらの 2n 個の異. は定数である．したがって， = 1/2k とするとき，. なる割当てに対し，f の値を量子並列的に求め. |β|2 − |α|2 − ≤ θ ≤ |β|2 − |α|2 + を満たす実数値 θ が確率 1 で読み出される．また，テープ上の任意の. れた割当てのもとで，f の値を評価する決定性. ることができる．M は n 変数に対する指定さ. 区画の測定はビットごとに行われ，各ビットの測定値. RTM を模倣することによりこの処理を実行す. からその区画に記された値（ 0 または 1 ）を決定する．. る．このステップの後，以下の重ね合わせが得. さらに，BQTM における測定では，複数量子ビット. られる．. の観測値を先頭のビットから順次決定していくような. √1 2n. 部分的観測は行えない．すなわち，BQTM のテープ の複数の区画を測定すれば，各テープ区画に対し，独 立に実数値 θ が得られるだけである．. (3). また，BQTM における測定では，波束が収縮しないの. 1 x1 =0. 1 x2 =0. ···. 1 xn =0. |x1 , x2 , · · · , xn , f (x1 , x2 , · · · , xn ). 最後に，量子ビット xn+1 を測定し，測定値 θ を得る．もし，前述の重ね合わせの 2n 個の様. で状態を乱さずに定数回測定を行うことができる（つ. 相すべてにおいて，xn+1 = 0 が成り立つなら. まり，Bulk 量子計算で採用されているのは，古典的. ば，|xn+1 は重ね合わせ状態 1|0 + 0|1 とな. 測定である） ．. ✷. 4. 充足可能性判定問題 n 変数ブール式 f (x1 , x2 , · · · , xn ) が与えられたとき に，f の値を 1 にするような，ブール変数 x1 , x2 , . . . xn に対する 0,1 の割当てが存在するか否かを判定する問 題を充足可能性問題（ SAT ）という．n 変数ブール式. る．この場合，θ = −1 を得ることができ，f は 充足可能ではないことが分かる．一方，|xn+1 の重ね合わせ状態内に，xn+1 = 1 となる様相 が少なくとも 1 つ存在すれば，θ > −1 が得ら れる．この場合，f は充足可能となる． 測定が任意の精度で行えるならば，上記の BQTM.
(5) 14. Sep. 2002. 情報処理学会論文誌：数理モデル化と応用. は SAT を多項式時間で解くことができる．しかし ，. xa mod N. NMR における測定が任意に高い精度で行えるという. ✻. 仮定は，現実的ではない．そこで，本論においては. NMR の測定精度を 2−k と仮定したため，すべての SAT を多項式時間で解くことができない．与えられた 長さ l のブール式の値を計算する RTM の最小ステッ プ数を h(l) とするとき，以下の定理を証明すること ができる． 定理 4.1 k を定義 3.1 で示した定数とする．この とき，h(l) + cl ステップで k 変数ブール式に対する. SAT を解く BQTM が存在する．ただし，l はブール 式の長さであり，c は定数である． 証明：k は，NMR の測定精度を表す定数であった ことに注意する．k 個のブール変数 x1 , x2 , . . . , xk に 対しては，全部で 2k 通りの 0，1 割当てが存在する．. ✲ 0. 1. 2. 3. 4. 5. 6. 7. 8. a. 9. 図 2 N = 15，x = 7 のときの a と xa mod N の関係． Fig. 2 A relationship between a and xa mod N when N = 15 and x = 7.. れば，上記の量子アルゴ リズムを実行すれば，少なく. N 2 < q < 2N 2 なる滑らかな数 q を選ぶ．た だし ，整数 q が滑らかであるとは，整数 q の. とも 1/2k 以上の実数値 θ が測定でき，f が充足可能. すべての素数ベキ qi i が A(log q)c で上からお. したがって，k 変数ブール式 f がもし 充足可能であ. e. ✷. さえられるときをいう．x mod N をランダム. 定理 4.2 k を定義 3.1 で示した定数とする．この. に選び，|N, q, x, 0 とラベル付けされた状態か. であることを正しく検出できる．. とき，充足割当の数が 2n−k 個以上であるような n 変 数ブール式の SAT を h(l)+cl ステップで解く BQTM. ら計算を始める．. (2). DF T q を QTM のテープの第 4 区画に適用す. が存在する．ただし，l はブール式の長さであり，c は. る．その結果を a(a = 0, 1, · · · , q − 1) とする. 定数である．. とき，xa mod N を計算し，その結果を第 5 区. 証明：定理 4.1 の証明とほぼ同様なので省略する．. 画に貯えると以下を得る．. ✷. q−1 1 |N, q, x, a, xa mod N √ q. 5. Shor の因数分解アルゴリズム. a=0. x と N が互いに素のとき，x の modN に関する. この第 5 区画の値は，a について周期的になる. r. オーダ r とは，x ≡ mod N を満たす最小の整数 r の ことをいう．x と N が互いに素のとき，x の mod N. ． ことに注意する（ 図 2 参照）. (3). 第 5 区画について観測を行うと，以下を得る． A 1 √ |N, q, x, jr + l, y A+1. のオーダを知ることができれば ，N の因数を多項式 時間内に求めることができる．. Shor の因数分解アルゴ リズム21)は，ランダムに選. (1). j=0. ばれた整数 x の modN のオーダ r を小さな誤り確. ただし，ある最小の l に対し ，xl ≡ y mod N. 率で，多項式時間内に発見する量子アルゴ リズムで. とし，A = q−l とする．以下，簡単のために r. ある．. 小さな丸め誤差を無視して，. q r. Shor の因数分解アルゴ リズムで 用いられ る離散 Fourier 変換（ DF T q ）は，q 次元 Hilbert 空間上. A=. で作用するが，基底 |0, · · · , |q − 1 に関して，次の. と置く．. (4). ように定義される．. 1 DF T q : |a → √ exp(2πiac/q)|c q q−1. c=0. 以下に Shor のアルゴ リズムの概略を示す．. (1). 因数分解すべき整数 N が与えられたならば ，. (2). 式 (1) に対して DF T q を適用することにより， 以下を得る． q−1 A−1 √ r αjc |N, q, x, c, y q c=0 j=0. ただし，. (3).
(6) Vol. 43. (5). No. SIG 7(TOM 6). SAT と因数分解に対する NMR 量子計算. 15. αjc = exp(2πi(jr + l)c/q) 第 4 区画を観測する．ここで，ラベル c を観測. 1/ log r ≥ 1/ log N となるので，4/(π 2 log N ) より大 きな確率で r が得られ，したがって，N の因数が得ら. する確率 P rob(c) は以下のとおり．. れる．この多項式時間量子アルゴ リズムを O(log N ). q/r−1 2 r P rob(c) = 2 βjc q j=0. 回繰り返すことにより，任意に高い成功確率を持った. (4). 多項式時間因数分解アルゴ リズムが得られる． 例 5.1 ここで，N = 15，q = 420，x = 7 のとき の Shor のアルゴ リズムの実行例を示す．初期状態は，. ただし，. βjc = exp(2πij(rc mod q)/q). (5). 式 (4) において，rc mod q が十分小さい c のみを. |15, 420, 7, 0 である．この状態の第 4 区画に DF T q を適用すると，以下のような重ね合わせ状態を得る．. 考えて，正の干渉を評価する．このとき，加え合わさ れた項はすべて，複素平面内の単位円 |z| = 1 の片側 に集まる．実際，もし c が. +. r r − ≤ rc mod q ≤ 2 2. (6). を満たすならば，P rob(c) 内の項はすべて，半円上に 分布する．このような P rob(c) を評価すると以下を 得る．. + + +. r 4 1 1 P rob(c) ≥ 2 ≈ 2 q sin2 πr π r 2q. (7). このような c は r 個存在するので，式 (6) を満た 2. す c の値を観測する確率は，4/π よりも大きい． 最後に，式 (6) を満たす c の値が与えられたときに，. r の値に関する情報を取り出したい．これを行うため に，式 (6) は以下の式と等価であることに注意する． ある 0 ≤ d ≤ r − 1 に対し，|rc − dq| ≤ r/2 (8) d の異なる r 個の値は，c の可能な r 個の値に対応. + +. 第 5 区画に xa mod N（ a は第 4 区画の値）を格納す ると，以下のようになる．. P rob(d) ≥. + + +. 4 1 π2 r. (9). + +. 式 (8) は次のようにも書ける．. c d − ≤ 1 q r 2q. (10). ここで，c と q は既知であり，かつ，r ≤ N ，q ≥ N 2. +. 再び，第 4 区画に DF T q を適用すると，以下を得る．. である． 2. したがって，q ≥ N なので，式 (10) で示された 範囲の中に，分母がたかだか N のちょうど 1 つの分. +. 数 d/r が存在する．この分数は，c/q の連分数展開を. +. 用いて，その近似として効率的に発見することができ る．ここで，もし d と r が互いに素ならば，r の値. +. が得られる．d と互いに素な値が φ(r) 個存在すると. +. すれば，式 (9) より次を得る．. P r[d は r と互いに素である] ≥. 4 φ(r) π2 r. 素数定理より，十分大きな r に対しては，φ(r)/r ≥. 1 |15, 420, 7, 0, 1 420 1 √ |15, 420, 7, 1, 7 420 1 √ |15, 420, 7, 2, 4 420 1 √ |15, 420, 7, 3, 13 420 1 √ |15, 420, 7, 4, 1 420 ··· 1 √ |15, 420, 7, 419, 13 420 √. する．したがって，式 (8) より，d の各値に対して以 下が成り立つ．. 1 |15, 420, 7, 0 420 1 √ |15, 420, 7, 1 420 1 √ |15, 420, 7, 2 420 1 √ |15, 420, 7, 3 420 1 √ |15, 420, 7, 4 420 ··· 1 √ |15, 420, 7, 419 420 √. + +. 1 |15, 420, 7, 0, 0 4 1 |15, 420, 7, 105, 0 4 1 |15, 420, 7, 210, 0 4 1 |15, 420, 7, 315, 0 4 1 |15, 420, 7, 0, 1 4 1 |15, 420, 7, 105, 1 4 1 |15, 420, 7, 210, 1 4.
(7) 16. Sep. 2002. 情報処理学会論文誌：数理モデル化と応用. ただし ，C = c0 , · · · , cl−1 ，A = a0 , · · · , al−1 ，. 1 |15, 420, 7, 315, 1 4 ··· 1 |15, 420, 7, 105, 13 4 1 |15, 420, 7, 210, 13 4 1 |15, 420, 7, 315, 13 4. + + + + +. M = xa0 mod N, . . . , xal−1 mod N ． (4). ci /q の連分数展開により得られた値 ri を第 (2l + 4) 区画以降に順次格納する．得られる重 ね合わせ状態は以下のようになる． 1 ql. q−1 q−1 . . exp. C=0 A=0. 最後に，第 4 区画を観測する．この場合，0，105，210，. 315 がそれぞれ等確率で得られる．これらのうち，正 しいオーダが得られるのは，105 と 315 である．この 2 つから得られるオーダは 4 である．この得られたオー ダを用いて，15 の 1 組の因数 (3, 5) を得ることがで. 2πi. l−1 . . (aj cj )/q. j=0. |N, q, x, C, M, R . ただし，R = r0 , r1 , · · · , rl−1 ．. (5). 上式において，R に含まれる値はほとんどが正. しいオーダであり，その他の値は，その約数と なることに注意する．r0 に対して，以下のよう. ✷. な xr0 ≡ ±1 mod N であるときは，第 (3l +4). 6. BQTM 上における因数分解アルゴリズム. 区画に 0 の列を書き込み，それ以外のときは r0. きる．. Shor のアルゴ リズムの観測においては，所望の値 が複数存在し，それぞれ異なっているため，前章のア ルゴ リズムをそのまま BQTM 上で実行しても正しい 値を読み出すことができない．また，BQTM の測定 はアンサンブル平均をとることに相当するため，測定 の回数を増やしても，ほぼ同じ測定値が得られるだけ で，アルゴ リズムの成功確率を増幅することができな い．そこで，以下のように，アルゴ リズムを修正する 必要がある．なお，以下では一般性を失うことなく， 奇数の合成数の因数分解のみを考える．. (1). を書き込む（ 各区画は O(log n) ビットを含む ものとする） ．すると，オーダの定義より，0 の 列もしくは，正しいオーダが第 (3l + 4) 区画に 書き込まれる． 次に，r1 に対して，同様の判定を行い，その結 果を第 (3l + 4) 区画の内容とビットごとに OR をとる．そして，第 (3l+5) 区画にその結果を格 納する．以下同様に，ri (2 ≤ i ≤ l − 1) に対し て，同様の判定を行い，その結果と第 (3l+i+3) 区画の内容の OR をとって，第 (3l + i + 4) 区 画にその結果を格納する．. 入力 N に対して，滑らかな数 q を 1 つ選び，N と互いに素な x mod (N − 1) をランダムに選 んで，|N, q, x, 0, · · · , 0 とラベル付けされた状 態から計算を始める．ここで，x mod (N − 1) と選ぶのは，論文 1) より，入力として奇数が 与えられた場合，x = N − 1 を選ぶと N が素 数と判定されてしまうためである．また，ラベ ルの右端の連続した 0 の個数を l とする．. (2). . DF T q をすべての 0 に順次適用する．その結 果を ai , 0 ≤ i ≤ l − 1 とする．この時点での重. rl−1 まで 同様の処理が 終了し たならば ，第 (4l + 3) 区画を測定する． 次に，上記アルゴ リズムの正当性と成功確率を考察 する． まず，ステップ 4 の R に含まれる整数 r は正しい オーダ，もしくは，その約数であることを見る．説明を 簡単にするために，いま，q が r で整除できるものとす る．この場合，Shor の因数分解アルゴリズムの実行後 に最終的に観測される値 c は，λ qr , (λ = 0, 1, · · · , r−1) と表される 1 つの値となる．つまり，. ね合わせ状態は以下のようになる．. 1. . ql. (3). q−1 . ···. a0 =0. q−1 . c=λ |N, q, x, a0 , . . . , al−1 . al−1 =0. 第 (l + 4) 区画以降に xai mod N を順次格納 し，以下の重ね合わせを得る． 1 ql. q−1 q−1 C=0. A=0. . exp 2πi. l−1. . (aj cj )/q |N, q, x, C, M ,. j=0. q r. (11). であり，q ，c は既知の値，λ，r は未知の値である．式. (11) を変形すると以下のようになる． λ c = q r. (12). したがって，λ と r が互いに素であるような c を観測 できれば，c/q を既約分数にまで払うことにより，そ の分母から正しいオーダを得ることができる（ 実際，.
(8) Vol. 43. No. SIG 7(TOM 6). SAT と因数分解に対する NMR 量子計算. これは連分数展開の結果と等しい） ．一方，λ と r が互 いに素でなければ，そのときは，c/q を既約分数にま で払うことによって，その分母から，正しいオーダの 約数を得ることになる．したがって，r は正しいオー ダ，もしくは，その約数となる． 最後に，本アルゴ リズムの成功確率について考察す る．本来の Shor のアルゴ リズムにおけるオーダ r の， 重ね合わせ状態内における占有率 P は 4/(π 2 log N ) と置くことができる（ 前章参照） ．. (4l + 3) 区画での r の占有率を Pl とすると，Pl は， Pl = (1 − Pl−1 )P + Pl−1. (13). と表すことができる．この漸化式を解くと Pl = 1 −. (1 − P )i となる． Pl > 12 となる l を求めると， 1 2 1 exp(−P l) < 2 −P l < − ln 2 π 2 ln 2 log N l> 4. 1 − (1 − P )l >. (14). を得る．したがって，所望の結果は，l = O(log N ) 個 の連続した 0 を用いることにより，任意に高い確率で 求めることができ，測定の精度に依存せずに所望の結 果を得ることができる．. 7. お わ り に 本論では ，まず NMR 量子計算のモデルとし て，. Bulk 量子 Turing 機械（ BQTM ）を導入し，BQTM 上で，NP 完全問題である充足可能性判定問題のある 種のインスタンスや，因数分解問題が多項式時間内に 解けることを示した．現在，NMR を用いる方式が， 量子コンピュータの実現方法として最も現実性がある と考えられている．本論の結果は，定義 3.1 に現れる 定数 k で表現された NMR 装置の測定精度が大きく なれば，NP 完全問題のサイズの大きなインスタンス を NMR 量子コンピュータで効率良く解けることを示 している．なお，本論の結果は，NMR 量子計算ばか りではなく，その他の Bulk 量子計算に対しても適用 可能である．将来，本論の理論的結果を物理的に実現 し，飛躍的に高速な量子コンピュータを実現するため に，物理学者や電子工学者との活発な共同研究が必要 となっていくであろう． 謝辞 本論に対して貴重なコメントをくださった， 査読者の方々に深謝いたします．また，本論を作成す るにあたり，ご助力をいただいた金田直樹氏に感謝い たします．. 17. 参 考 文 献 1) 渥美賢嗣，西野哲朗：因数分解に対する量子ア ルゴ リズムのシミュレ ーション ，電子情報通信 学会論文誌 A，Vol.J81-A, No.12, pp.1670–1677 (1998). 2) Bernstein, E. and Vazirani, U.: Quantum Complexity Theory, Proc. 25th Annual ACM Symposium on Theory of Computing, pp.11–20, ACM, New York (1993). Also in Special issue of SIAM J. Comp., October (1997). 3) Brun, T. and Schack, R.: Realizing the quantum baker’s map on an NMR quantum computer, quant-ph/9807050 (1998). 4) Chuang, I.L., Gershenfeld, N., Kubinec, M.G. and Leung, D.W.: Bulk Quantum Computation with Nuclear Magnetic Resonance: Theory and Experiment, Proc. R. Soc. Lond., Vol.A 454, pp.447–467 (1998). 5) Cory, D.G., Fahmy, A.F. and Havel, T.F.: Ensemble Quantum Computing by Nuclear Magnetic Resonance Spectroscopy, Proc.Natl.Acad. Sci., Vol.94, pp.1634–1639 (1997). 6) Deutsch, D.: Quantum Theory, the ChurchTuring Principle and the Universal Quantum Computer, Proc. R. Soc. Lond., Vol.A 400, pp.97–117 (1985). 7) Dorai, K. and Kumar, A.: Implementing quantum logic operations, pseudo-pure states and the Deutsch-Jozsa algorithm using noncommuting selective pulses in NMR, quantph/9906027 (1999). 8) Fang, X., Zhu, X., Feng, M., Mao, X. and Du, F.: Experimental Implementation of Dense Coding Using Nuclear Magnetic Resonance, quant-ph/9906041 (1999). 9) Fu, L., Luo, J., Xiao, L. and Zeng, X.: Experimental Realization of Discrete Fourier Transformation on NMR Quantum Computer, quant-ph/9905083 (1999). 10) Gershenfeld, N. and Chuang, I.L.: Bulk SpinResonance Quantum Computation, Science, Vol.275, pp.350–356 (1997). 11) Havel, T.F., Somaroo, S.S., Tseng C.H. and Croy, D.G.: Principles and Demonstrations of Quantum Information Processing by NMR Spectroscopy, quant-ph/9812086 (1998). 12) Jones, J.A. and Mosca, M.: Approximate quantum counting on an NMR ensemble quantum computer, quant-ph/9808056 (1998). 13) Jones, J.A. and Knill, E.: Efficient Refocussing of One Spin and Two Spin Interactions for NMR Quantum Computation, quantph/9905008 (1999)..
(9) 18. Sep. 2002. 情報処理学会論文誌：数理モデル化と応用. 14) Linden, N., Barjat, H. and Freeman, R.: An implementation of the Deutsch-Jozsa algorithm on a three-qubit NMR quantum computer, quant-ph/9808039 (1998). 15) Luo, J. and Zeng, X.: NMR Quantum Computation with a hyperpolarized nuclear spin bulk, quant-ph/9811044 (1998). 16) Marx, R., Fahmy, A.F., Myers, J.M, Bermel, W. and Glaser, S.J.: Realization of a 5-Bit NMR Quantum Computer Using a New Molecular Architecture, quant-ph/9905087 (1999). 17) 西野哲朗：量子コンピュータ入門，東京電機大 学出版局 (1997). 18) 西野哲朗，芝田 浩，渥美賢嗣，志摩孝夫：NMR 量子計算による関数問題と NP 完全問題の解法に ついて，電子情報通信学会コンピュテーション研 究会資料 COMP98-71, pp.65–72 (1998). 19) Pravia, M., Fortunato, E., Weinstein, Y., Price, M.D., Teklemariam, G., Nelson, R.J., Sharf, Y., Somaroo, S., Tseng, C.H., Havel, T.F. and Cory, D.G.: Observations of Quantum Dynamics by Solution-State NMR Spectroscopy, quant-ph/9905061 (1999). 20) Schulman, L.J. and Vazirani, U.: Scalable NMR Quantum Computaion, quantph/9804060 (1998). 21) Shor, P.W.: Algorithms for Quantum Computation: Discrete Log and Factoring, Proc. 35th Annual IEEE Symposium on Foundations of Computer Science, pp.124–134 (1994). Also in Special issue of SIAM J. Comp., October (1997). 22) Simon, D.R.: On the Power of Quantum Computation, Proc. 35th Annual IEEE Symposium on Foundations of Computer Science, pp.116– 123 (1994). Also in Special issue of SIAM J. Comp., October (1997).. 23) Wei, H., Xue, X. and Morgera, S.D.: NMR Quantum Automata in Doped Crystals, quantph/9805059 (1998). (平成 14 年 1 月 4 日受付) (平成 14 年 4 月 23 日再受付) (平成 14 年 5 月 10 日採録) 渥美 賢嗣 昭和 50 年生．平成 10 年電気通信 大学電気通信学部電子情報学科卒業． 平成 12 年同大学大学院電気通信学 研究科電子情報学専攻博士前期課程 修了．同年（ 株）PFU 入社． 西野 哲朗（ 正会員） 昭和 34 年生．昭和 57 年早稲田大 学理工学部数学科卒業．昭和 59 年 同大学大学院理工学研究科博士前期 課程修了．同年日本アイ・ビー・エ ム（ 株）入社．昭和 62 年東京電機 大学理工学部情報科学科助手．平成 4 年北陸先端科学 技術大学院大学助教授．平成 6 年電気通信大学電子情 報学科助教授．現在に至る．理学博士．回路計算量理 論，量子計算量理論，計算論的学習理論等の研究に従 事．平成 7 年本学会 Best Author 賞，平成 10 年人工 知能学会研究奨励賞各受賞．日本ソフトウェア科学会， 人工知能学会，日本数学会，ACM，IEEE，EATCS 各会員．.
(10)
図
関連したドキュメント
非自明な和として分解できない結び目を 素な結び目 と いう．.. 定理 (
まず適当に道を書いてみて（ guess ）、それ がオイラー回路になっているかどうか確かめ る（ check
In particular separability criteria based on the Bloch representation, covariance matrix, normal form and entanglement witness, lower bounds, subadditivity property of concurrence
What relates to Offline Turing Machines in the same way that functional programming languages relate to Turing Machines?.. Int Construction.. Understand the transition from
Note that most of works on MVIs are traditionally de- voted to the case where G possesses certain strict (strong) monotonicity properties, which enable one to present various
Note that most of works on MVIs are traditionally de- voted to the case where G possesses certain strict (strong) monotonicity properties, which enable one to present various
The next lemma implies that the final bound in (2.4) will not be helpful if non- negative weight matrices are used for graphs that have small maximum independent sets and vertices
We introduce a new hybrid extragradient viscosity approximation method for finding the common element of the set of equilibrium problems, the set of solutions of fixed points of
