特集

量子コンピュータと量子計算

3

Shor のアルゴリズムのための効率的な量子回路
高橋 康博〔日本電信電話（株）NTT コミュニケーション科学基礎研究所〕
1994 年，AT&T Bell 研究所の Shor は，因数分解問題や離散対数問題を効率的に解く量子コンピュータ
上のアルゴリズムを提案した．これ以来，Shor のアルゴリズムを実行するための効率的な量子回路の理論的研究が行われている．本稿では，量子ビット数の最小化に焦点を当て，このような研究の最新の成果について紹介する．
ズムのための効率的な量子回路の研究は，このような課

はじめに題の解決に多くの知見を与える重要な研究である．

1994 年，AT&T Bell 研究所の Shor（現 MIT）は，因数

Shor のアルゴリズムが提案されて以来，焦点が当て分解問題や離散対数問題を効率的に解く量子コンピューられてきた問題は，どの程度少ない量子ビットで因数分

タ上のアルゴリズムを提案した ．現在のコンピュータ

解問題を解くことができるのかという問題である．詳細

ではこれらの問題を効率的に解くことは困難であると考は次の章で述べるが，この問題は，どの程度少ない量子

えられているため，量子コンピュータは現在のコンピュビットで量子フーリエ変換の逆演算とべき乗剰余演算がータよりも高い計算能力を持つと考えられる．したがっ実行できるのかという問題に帰着される．量子フーリエて，量子コンピュータは有用なコンピュータになり得る

変換の逆演算を実行するためには 1 量子ビットあれば十と予想される．一方で，量子コンピュータにより，RSA

分であることが知られているため ，以下の議論で中心

暗号など一般に使われている暗号のいくつかは破られてとなるのはべき乗剰余演算である．n ビットで表される

しまう．これは，このような暗号の安全性が因数分解

数 N を因数分解したい場合，Shor のアルゴリズムにお問題や離散対数問題の困難さに根拠を置いているからでいて使われるべき乗剰余演算は，7）ある．
現在，量子コンピュータの実現に向けて多くの研究が行われている．しかし，現状では量子コンピュータが暗5）x

x 1 → x a mod N

という演算であり，x は n ビットで表される数，a は 1<
a < N を満たす事前に与えられた数である．

号にとって脅威となっているわけではない．これは，多1996 年，Vedral らは，少ない量子ビットでべき乗剰余

くの計算資源（量子ビット数や計算時間等）を持つ量子演算を行う方法を提案し，n ビットで表される数の因数

コンピュータが実現されていないからである．それでは，

分解が 7n  1 個の量子ビットで行えることを示した

どの程度の計算資源を持つ量子コンピュータが実現する

その後，上で触れた量子フーリエ変換の逆演算を行う方と暗号にとって脅威となるのであろうか．言い換えると，

法 や少ない量子ビットで加算を行う方法 が提案されどの程度少ない計算資源で Shor のアルゴリズムが実行た．これらの方法と Vedral らのべき乗剰余演算を行うできるのであろうか．このような問題を扱うのが Shor

方法を組み合わせ，さらに，事前に与えられた数を量子のアルゴリズムのための効率的な量子回路の研究である．

回路に “組み込む” ことにより，2003 年に Beauregard が量子コンピュータの実現に向けた研究が進むにつれて，

2n  3 個の量子ビットで因数分解が行えることを示し

量子コンピュータに対する現在の暗号の安全性を詳細にた ．2006 年には Takahashi らが，Beauregard の量子回分析し，量子コンピュータに対しても安全な暗号を構築

路における未使用な量子ビットを利用し，2n  2 個のすることが大きな課題となってくる．Shor のアルゴリ

量子ビットで因数分解が行えることを示した ．これは，

5）

．

10）

2）

1）

9）

IPSJ Magazine Vol.47 No.12 Dec. 20061323

特集：量子コンピュータと量子計算

現在推奨されている 1024 ビットの鍵の長さを持つ RSA
暗号が，2050 個の量子ビットを持つ量子コンピュータ
で理論上破られることを示している．
本稿では，Beauregard の量子回路とそれに関連する
最新の成果について紹介する．以下では，まず始めにShor のアルゴリズムのための量子回路と 1 量子ビットだけを使って量子フーリエ変換の逆演算を行う方法について述べる．次に，Beauregard の量子回路について，
Vedral らのべき乗剰余演算を行う方法も含めて詳細に述べる．次に，関連する話題として，Takahashi らによる
Beauregard の量子回路の改良と Fowler らの隣接量子ビ

0
0

H

0

H

0

H

1

H

QFT

2

4

-1

8

U(a) U(a ) U(a ) U(a )図 -1 Shor のアルゴリズムのための量子回路

ット間の演算だけを使う Shor のアルゴリズムのための量子回路について触れる．隣接量子ビット間の演算だ

3）（4）第 1 レジスタを観測する．

けを使う量子回路は，量子コンピュータを実現する際の第 4 ステップで得られた値を使い，現在のコンピュータ

現実的な制限を考慮した量子回路である．最後に，今後により効率的に位数を求めることができる．

の課題について述べる．

第 2 ステップにおけるべき乗剰余は，第 1 レジスタの各量子ビットの値に依存して，剰余乗算 U(a ) (i  0,…,2i

Shor のアルゴリズムのための量子回路❐ Shor のアルゴリズム

2n1) を第 2 レジスタに適用することにより計算される．
ただし，U(a) は，
U(a)x  ax mod N

因数分解問題は，n ビットで表される合成数 N に対し，

N の自明でない（すなわち，1 と N 以外の）約数を求めるという演算であり，x は n ビットで表される数である．
a と N は事前に与えられていることに注意する．

問題である．Shor のアルゴリズムはこの問題を効率的に解くが，このアルゴリズムは，現在のコンピュータによって実行される部分と量子コンピュータによって実行❐ 量子回路量子回路は，量子コンピュータ上の各量子ビットにどされる部分に分けられる．量子コンピュータによって実のような演算を適用して計算を進めるかを表したもので行されるのは，位数発見問題を解く部分である．位数発ある．量子回路の効率性は，入力の長さに対し，その量見問題は，因数分解したい合成数 N と N より小さく N

子回路で使われる量子ビット数，基本演算数，そして計と互いに素な自然数 a に対し，N を法とする a の位数を算ステップ数がどのように表されるかによって測る．基求める問題である．ただし，N を法とする a の位数は，本演算は 1 量子ビットに対する演算と 2 量子ビットに対する演算であり，基本演算数はその量子回路で使われてar  1 mod Nとなる最小の自然数 r > 0 である．

いる基本演算の数である．計算ステップ数は，その量位数発見問題を解くアルゴリズムは次のようなもので子回路で使われている基本演算を並列に行える演算からある．2n 個の量子ビットからなる第 1 レジスタと n 個なるグループに分割したときのグループの数である．たの量子ビットからなる第 2 レジスタを用意する．初期状

だし，異なる量子ビットに対する演算は並列に行えると態として，第 1 レジスタが 0 を表し，第 2 レジスタが 1仮定する．大まかには，基本演算数は計算時間に対応し，を表しているとする．

計算ステップ数は各基本演算を可能な限り並列に処理し（1）第 1 レジスタの各量子ビットにアダマール変換 H を適用し，第 1 レジスタに 0 から 2 1 までの 2 個の2n2n値の重ね合わせを作る．

た場合の計算時間に対応する．
Shor のアルゴリズムのための量子回路は，上で述べた位数発見問題を解くアルゴリズムのための量子回路（2）第 1 レジスタに重ね合わせられた各値 x に対するべである．入力の長さは，因数分解したい合成数を 2 進数

き乗剰余 a mod N を計算し，第 2 レジスタに値を書で表したときの長さ n である．この量子回路は図 -1 のき込む．

ようになる．ただし，n  2 の場合である．1 本の横のx（3）第 1 レジスタに量子フーリエ変換 QFT の逆演算
1

QFTを適用する．

1324 47 巻 12 号

情報処理 2006 年 12 月

線は 1 個の量子ビットに対応しており，左から右へ向けて計算が進む．第 1 レジスタは上から 2n 個の量子ビ

3）Shor のアルゴリズムのための効率的な量子回路

ットからなり，第 2 レジスタはその下 n 個の量子ビットからなる．初期状態は最も左に記述している．図 -1 では，始めに第 1 レジスタの各量子ビットに H が適用さ

0

H

H

U1 H

U2 H

れているが，これはアルゴリズムのステップ 1 に対応す…

る．次に適用されている黒丸とそれにつながった U(a)は，黒丸が置かれている量子ビットの値に依存して第2 レジスタに U(a) が適用されていることを表しており，その後の演算は U(a ) 等が同様に適用されていることを
2

1

8

4

U(a )

U(a )

表している．これはアルゴリズムのステップ 2 に対応する．最後に第 1 レジスタに QFT

1が適用されているが，これはアルゴリズムのステップ 3 に対応する．アルゴリ

図 -2 少ない量子ビットで QFT を行う方法-1

ズムでは最後に第 1 レジスタを観測するが，量子回路のジスタを 0 に戻すための演算であり，これに対応する

効率性とはかかわらないので図 -1 では省略している．

図 -1 の演算はない．このような操作を繰り返すことに

図 -1 の量子回路の構成から，Shor のアルゴリズムのより図 -1 と同等の量子回路が構成できる．したがって，ための量子回路の効率性は，U(a) と QFT

1

のための量

少ない量子ビットで Shor のアルゴリズムのための量子子回路の効率性により決まることが分かる．したがって，回路を構成するためには，少ない量子ビットで U(a) のShor のアルゴリズムのための効率的な量子回路を構成ための量子回路を構成すればよい．

するためには，U(a) と QFT

1のための効率的な量子回路を（基本演算を使って）構成すればよい．以下では，少ない量子ビットで Shor のアルゴリズムのための量子回路を構成するという問題を扱うが，これは，少ない量子ビットで U(a) と QFT

1のための量子回路を構成するとBeauregard の量子回路❐ U(a) の分解

Beauregard は，少ない量子ビットで U(a) のための量子回路を構成するために，Vedral らの方法いう問題に帰着される．

10）

に従って

U(a) を単純な演算に分解した．この方法では，U(a) を❐ 少ない量子ビットで QFT

1

を行う方法

剰余乗加算 V(a) に分解し，V(a) を剰余加算 W(a) に分解

Mosca らは，Shor のアルゴリズムのための量子回路において，少ない量子ビットで QFT

1を行う方法を提案した ．この方法は，観測を交えることにより，図 -25）のように 1 量子ビット上で QFT

1を適用する．したがって，第 1 レジスタは 1 量子ビットあれば十分であるということになる．
図 -1 と図 -2 における演算の対応関係は次のようになる．図 -2 では，始めに第 1 レジスタに H が適用されているが，これは図 -1 の最も上の量子ビットに適用されている H に対応する．次に第 1 レジスタの量子ビットの値に依存して第 2 レジスタに U(a ) が適用されている
8が，これは図 -1 の第 1 レジスタの量子ビットの値に依する．ただし，V(a) は，
V(a)xb  xax  b mod N
x と b は n ビットで表される数である．
という演算であり，また，W(a) は，

W (a) cb =)cca + b mod Nbc = 1 のとき
c = 0 のときという演算であり，c は 0 または 1，b は n ビットで表される数である．
1
より正確には，U(a) は V(a) と V(a ) とスワップ演算を使って次のように計算できる．
x0 → xax mod N→ ax mod Nx

存して第 2 レジスタに適用されている U(a ) に対応す8

→ ax mod Nx  a1ax mod N

る．次に第 1 レジスタに H が適用されているが，これ ax mod N0の中で最も上の量子ビットに適用され最初の演算が V(a) であり，2 番目の演算はスワップ演ている H（図 -1 では簡単のために省略している）に対応

1 1
1
算であり，3 番目は V(a ) である．ただし，a は N

する．次の第 1 レジスタの観測は，図 -1 の QFTを法とする a の逆元である．a と N が互いに素であるこは図 -1 の QFT

1

1

の後

に最も上の量子ビットを観測することに対応する．次とから aに第 1 レジスタに 1 量子ビットに対する演算 U1 が適用

り現在のコンピュータを使って効率的に aされているが，これは先ほどの観測結果に応じて第 1 レとができる．また，V(a) は，

1は存在し，ユークリッドのアルゴリズムによ
1

を求めるこ

IPSJ Magazine Vol.47 No.12 Dec. 20061325

特集：量子コンピュータと量子計算

る．0 は x  y の最上位ビットのために用意してある．

ax  b mod N (2axn1  (… (2 ax1 n1x を含むレジスタを第 1 レジスタと呼び，それ以外の量

1(2 ax0  b mod N) mod N)…) mod N)
0

子ビット全体を第 2 レジスタと呼ぶとき，この量子回路という関係が成り立つので，W(2 a) (i  0,…, n1) をは次のように構成される．

使って計算できる．ただし，xn1 … x0 は x を 2 進数で（1）第 2 レジスタに QFT を適用する．

表したものである．したがって，少ない量子ビットで（2）第 1 レジスタの各量子ビットの値に依存して，第 2U(a) のための量子回路を構成するためには，少ない量レジスタの各量子ビットに位相シフト演算を適用

子ビットで W(a) のための量子回路を構成すればよい．

する．

i（3）第 2 レジスタに QFT

1❐ W(a) のための量子回路を適用する．

この量子回路は，少ない量子ビットで W(a) のため

Beauregard の W(a) のための量子回路は次のようなアの量子回路を構成するために有用な 2 つの性質を持つ．

ルゴリズムに基づいている．ただし，c  1 と仮定し，c1 つは，第 1 レジスタと第 2 レジスタ以外に量子ビットを含むレジスタは省略する．初期状態は b である．

を必要としないことである．もう 1 つは，x が事前に与（1）a を b に加える．結果は b  a となる．

えられた（古典的な）数の場合，x を量子回路に “組み込（2）b  a から N を引く．結果は b  a  N となる．

む” ことができることである．すなわち，第 1 レジスタ（3）b  a  N < 0 であるかどうかを判定するため，b 

は用意する必要がない．これは，x が第 2 レジスタに位a  N の最上位ビット y を 1 つの補助ビットに書き込

相シフト演算を適用するかどうかを制御することだけにむ．結果は b  a  Ny となる．ただし，b  a  N

使われているからである．この 2 つの性質を同時に持つ< 0 ならば y は 1 であり，そうでなければ 0 である．

ADD のための量子回路は現時点ではほかに例がない．

（4）y が 1 ならば N を b  a  N に加える．結果は a 

この量子回路は，基本演算数については不利であるこb mod Ny となる．
（5）a  b mod N から a を引く．結果は (a  b mod N) とに注意する．これは，この量子回路の基本演算数がO(n2) である一方で，多くの量子ビットを使えば基本演
算数が O(n) である ADD のための量子回路を構成できる

ay となる．
（6）(a  b mod N)  a < 0 であるかどうかを判定するたからである．QFT を使う ADD のための量子回路に10）め，(a  b mod N)  a の最上位ビット z の否定を補助おいて，近似 QFT を使い，小さい誤り確率を許して基ビットに書き込む．結果は (a  b mod N)  ay ⊕ z ⊕本演算数を O(n log n) に削減できることが知られている．

1 となる．ただし，(a  b mod N)  a < 0 ならば z は計算ステップ数は近似 QFT を使うかどうかにかかわら1 であり，そうでなければ 0 である．⊕ は 2 を法とす

ず O(n) である．

る加算を表す．
（7）a を (a  b mod N)  a に加える．結果は a  b mod

以上のことから，Beauregard の量子回路全体の効率性を測ることができる．量子ビット数については，ADD

N0 となる．

のために n  1 個，W(a) のために n  3 個，V(a) のたステップ 6 において，

めに 2n  2 個，U(a) のために 2n  2 個の量子ビットを使う．第 1 レジスタの 1 個の量子ビットを合わせて，回y⊕z⊕10であることに注意する．なぜなら，路全体が使う量子ビットは 2n  3 個である．基本演算a  b mod N ≥ a ⇔ a  b < N

数と計算ステップ数は，それぞれ O(n log n)，O(n ) とという関係が成り立つからである．Beauregard の W(a)

3

3

なる．

のための量子回路は，上のアルゴリズムにおける加算や減算を以下で述べる QFT を使う加算のための量子回路により実現したものである．

❐ QFT を使う加算のための量子回路

Draper は，加算 ADD のための効率的な量子回路を提関連する話題❐ Beauregard の量子回路の改良

Takahashi らは，Beauregard の量子回路における未使用な量子ビットを利用し，2n  2 個の量子ビットを使う案した ．ただし，ADD は，Shor のアルゴリズムのための量子回路を構成した ．基ADDxy0  xx  y

本演算数は Beauregard の量子回路のおよそ半分である．

2）という演算であり，x と y は n ビットで表される数であ1326 47 巻 12 号

情報処理 2006 年 12 月

9）Takahashi らの量子回路と Beauregard の量子回路の違い

3）Shor のアルゴリズムのための効率的な量子回路

は，W(a) のための量子回路の構成である．Takahashi らiW(2 a) (i  0,..., n1) を適用している際の xj (j  i) を表の W(a) のための量子回路は次のようなアルゴリズムにしている量子ビットが利用できる．したがって，新たな基づいている．ただし，c  1 と仮定し，c を含むレジ

量子ビットを使わずに，COMP(a) のための量子回路がスタは省略する．初期状態は b である．

構成できる．ページ数の都合によりこの量子回路の詳細（1）b と N  a の大小を比較し，その結果 y を 1 つの補は述べられないが，基本演算数と計算ステップ数は共に助ビットに書き込む．結果は by となる．ただし，bO(n) である．

< N  a ならば y は 1 であり，そうでなければ 0 である．
（2）y が 1 ならば a を b に加え，y が 0 ならば b から N
 a を引く．結果は a  b mod Ny となる．

❐ 隣接量子ビット間の演算だけを使う量子回路

量子コンピュータの実現に向けた研究において，量子（3）a  b mod N と a の大小を比較し，その結果 z の否

ビットを 1 列に並べ，隣同士の量子ビット間の演算だけ定を補助ビットに書き込む．結果は a  b mod Ny ⊕を使って計算を進める量子コンピュータの構造が提案さ

z ⊕ 1  a  b mod N0 となる．ただし，a  b mod

れている．これは，1 量子ビットに対する演算と（任意N < a ならば y は 1 であり，そうでなければ 0 である．

の 2 量子ビット間ではなく）隣接量子ビット間の演算だy ⊕ z ⊕ 1  0 となるのは，Beauregard のアルゴリズムのけを量子回路の基本演算とすることに対応する．このよ場合と同様である．

うな現実的な計算資源だけを使う量子回路において，ど計算結果 a  b mod N を含むレジスタに必要となる量の程度少ない計算資源で Shor のアルゴリズムが実行で子ビット数が，Beauregard のアルゴリズムと Takahashi

きるのかを明らかにしようという研究が行われている．

らのアルゴリズムでは異なる．Beauregard のアルゴリズ

Fowler らは Beauregard の量子回路を基に，隣接量子

ムは減算を使って数の大小比較を行うため，b  a  N

ビット間の演算だけを使う Shor のアルゴリズムのためのような n  1 ビットで表される可能性のある値を扱う．

の量子回路を構成した ．基本演算に制限が加えられてしたがって，そのレジスタに n  1 個の量子ビットを必いるため，多くの計算資源を必要とするのではないか

要とする．一方，Takahashi らのアルゴリズムはそのよと予想されるが，実際には Fowler らの量子回路の効率

うな値を扱わないため，n 個の量子ビットで十分である．

性は，Beauregard の量子回路の効率性とほぼ同等である．

また，Takahashi らのアルゴリズムで使う加算や減算のまた，上で述べた Takahashi らの改良が隣接量子ビット

回数は，Beauregard のアルゴリズムで使う加算や減算の間の演算だけを使う量子回路においても可能であること

回数よりも少ないため，基本演算数が削減される．

を示すことができる．

3）

Takahashi らのアルゴリズムにおける加算，減算，そして大小比較を新たな量子ビットを使わない量子回路で実現すれば，上で述べたことから Takahashi らの量子

今後の課題

回路は Beauregard の量子回路と比較して，1 個の量子

今後の課題の 1 つは，より現実的な制限のもとで，どビットを削減することができる．加算と減算についての程度少ない計算資源で Shor のアルゴリズムが実行では QFT を使う量子回路を使えばよい．問題は大小比較

きるのかを明らかにすることである．このような研究にのための量子回路を構成することである．より正確には，ついては上で触れたが，たとえば，隣接量子ビット間の新たな量子ビットを使わずに COMP(a) のための量子回演算についても現実的に容易に適用できる演算とそうで路を構成することである．ただし，COMP(a) は，ない演算があるであろう．容易に適用できる演算だけでCOMP(a)bz  bz ⊕ y

Beauregard の量子回路と同等の効率性の量子回路が構成という演算であり，b は n ビットで表される数であり，
z は 0 または 1 である．また，a > b であれば y は 1 であり，そうでなければ 0 である．
Takahashi らは Vedral らの ADD のための量子回路できるであろうか．
もう 1 つの課題は，暗号とのかかわりを詳細に分析することである．このような研究の例として Proos らの研

10）

究が挙げられる ．Proos らは，楕円離散対数問題を解を 基 に，0 に 初 期 化 さ れ て い な い n1 個 の 補 助 ビ

く Shor のアルゴリズムのための効率的な量子回路を構ットを使い，COMP(a) のための量子回路を構成した．

成し，量子コンピュータに対する RSA 暗号の安全性とBeauregard の量子回路における未使用な量子ビットが，楕円曲線暗号の安全性について比較した．このような研このような n1 個の未初期化補助ビットとして利用で究においては，本稿で焦点を当てた量子ビット数だけできる．より正確には，Beauregard の量子回路において，はなく，Kunihiro が行っているような計算時間について

6）

IPSJ Magazine Vol.47 No.12 Dec. 20061327

特集：量子コンピュータと量子計算の詳細な分析 も重要となる．
4）

本稿では，どの程度少ない量子ビットで因数分解問
題を解く Shor のアルゴリズムが実行できるのかという問題に焦点を当て，最新の成果を紹介した．上で述べた以外の関連する研究として，加算のための効率的な量子回路の研究が挙げられる ．Los Alamos National
8）

Laboratory の量子物理学アーカイブにおいて，関連する
多くの興味深い論文を見つけることができる．
謝辞

本稿を作成するにあたり，電気通信大学の國廣昇先生に多くの貴重な助言をいただきました．ここに感謝いたします．
参考文献
1）Beauregard, S. : Circuit for Shor's Algorithm Using 2n+3 Qubits, Quantum
Information and Computation, Vol.3, No.2, pp.175-185 (2003).
2）Draper, T. G. : Addition on a Quantum Computer, quant-ph/0008033 (2000).
3）Fowler, A. G., Devitt, S. J. and Hollenberg, L. C. L. : Implementation of
Shor's Algorithm on a Linear Nearest Neighbour Qubit Array, Quantum
Information and Computation, Vol.4, No.4, pp.237-251 (2004).
4）Kunihiro, N. : Exact Analyses of Computational Time for Factoring in
Quantum Computers, IEICE Transactions on Fundamentals of Electronics,
Communications and Computer Sciences, Vol.E88-A, No.1, pp.105-111(2005).

1328 47 巻 12 号

情報処理 2006 年 12 月5）Mosca, M. and Ekert, A. : The Hidden Subgroup Problem and Eigenvalue
Estimation on a Quantum Computer, Lecture Notes in Computer Science,
Vol.1509, pp.174-188 (1999).
6）Proos, J. and Zalka, C. : Shor's Discrete Logarithm Quantum Algorithm
for Elliptic Curves, Quantum Information and Computation, Vol.3, No.4,
pp.317-344 (2003).
7）Shor, P. W. : Algorithms for Quantum Computation : Discrete Logarithms andFactoring, Proc. 35th Annual IEEE Symposium on Foundations of Computer
Science, pp.124-134 (1994).
8）Takahashi, Y. and Kunihiro, N. : A Linear-size Quantum Circuit for Addition
with No Ancillary Qubits, Quantum Information and Computation, Vol.5,
No.6, pp.440-448 (2005).
9）Takahashi, Y. and Kunihiro, N. : A Quantum Circuit for Shor's Factoring
Algorithm Using 2n+2 Qubits, Quantum Information and Computation, Vol.6,
No.2, pp.184-192 (2006).
10）Vedral, V., Barenco, A. and Ekert, A. : Quantum Networks for Elementary
Arithmetic Operations, Physical Review A, Vol.54, No.1, pp.147-153 (1996).
（平成 18 年 10 月 24 日受付）

高橋 康博（正会員）
takahasi@theory.brl.ntt.co.jp
2000 年東北大学大学院理学研究科数学専攻修士課程修了．同年 NTT
コミュニケーション科学基礎研究所入社．量子計算，計算量理論，暗号理論に興味を持つ．