(57)【要約】【課題】Kuperbergアルゴリズムよりも2面体群のcoset問題を高速に解くことができる技術を提供する。【解決手段】coset状態2016057900.tif 000083が与えられているものとし、nを正の整数、d<2nを求めたい数、xをnビットのランダムなわからない数として、coset状態にmキュービットのレジスタである第3レジスタを追加し、第2レジスタに2n次元量子フーリエ変換を実行し、第2レジスタを観測して、得られたnビットの観測結果をkとし、rをkの下位n-mビットとし、第3レジスタで量子回転操作をすることにより、擬coset状態2016057900.tif 000084を得る。【選択図】なし【特許請求の範囲】
【請求項１】
coset状態
【数６５】
2016057900.tif 000066
が与えられているものとし、nを正の整数、d<2nを求めたい数、xをnビットのランダムなわからない数として、
上記coset状態にmキュービットのレジスタである第3レジスタを追加し、
第2レジスタに2n次元量子フーリエ変換を実行し、第2レジスタを観測して、得られたnビットの観測結果をkとし、
rをkの下位n-mビットとし、第3レジスタで量子回転操作をすることにより、擬coset状態
【数６６】
2016057900.tif 000067
を得る量子演算方法。
【請求項２】
nを正の整数、y<2nを求めたい数とし、量子状態
【数６７】
2016057900.tif 000068
が与えられているものとし、δi(x)はxを２進法nビット表記したときのi番目の数（すなわち、xを2進法表記したときのn-i+1桁目の数）であるとし、siをi-1ビットの数として、
xの第1キュービットにアダマール変換を実行し、
xの第1,2キュービット間で制御回転ゲート
【数６８】
2016057900.tif 000069
を実行し、
xの第2キュービットでアダマール変換を実行し、
xの第1,3キュービット間で制御回転ゲート
【数６９】
2016057900.tif 000070
を実行し、
xの第2,3キュービット間で制御回転ゲート
【数７０】
2016057900.tif 000071
を実行し、
xの第3キュービットでアダマール変換を実行し、
以下、同様の操作を第nキュービットまで繰り返し、最後に得られた量子状態を観測することにより、yの値を得る量子演算方法。
【請求項３】
coset状態
【数７１】
2016057900.tif 000072
がnc個与えられているものとし、c,nを正の整数、d<2nを求めたい数、xをnビットのランダムなわからない数として、
請求項１の量子演算方法でcoset状態から擬coset状態
【数７２】
2016057900.tif 000073
（ただし、riをiビットの奇数とし、すべてのriに対して
【数７３】
2016057900.tif 000074
とする）を作り、
各擬coset状態の第1レジスタ（キュービット）を集めて第0レジスタとし、
各擬coset状態の第1レジスタを第2〜nレジスタとし、
初期化されたnキュービットの第1レジスタを付け加え、
第0,1レジスタ間で
【数７４】
2016057900.tif 000075
（ただし、δi(y)はyを２進法nビット表記したときのi番目の数とし、
【数７５】
2016057900.tif 000076
とする）を実行し、
第0,1レジスタ間で
【数７６】
2016057900.tif 000077
（ただし、f-1はfの逆関数とする）を実行し、
第0レジスタを観測した結果が0である場合に、第2〜nレジスタに量子フーリエ変換を実行し、第2〜nレジスタを観測した結果をs2,s3,…,snとし、請求項２の量子演算方法を実行し、量子状態を観測することにより、dの下位(c-1)lognビットを特定する量子演算方法。
【請求項４】
[1]第j-1番目のキュービットに対して、第j,j+1,…,n番目のキュービットで作った数字に制御マイナス
【数７７】
2016057900.tif 000078
操作を行い、
【数７８】
2016057900.tif 000079
ここで、
【数７９】
2016057900.tif 000080
はrn-j+2の2ビット目以降が作る数字とし、
[2]第j-1番目のキュービットに対してHadamard操作を実行し、
[3]jキュービットの初期化されたオラクルを付け加える。第j,j+1,…,n番目のキュービットで作った数字をzとし、オラクルで2sjz+δj(z) mod 2jを計算し、
[4]第i番目(i=1,2,…,j-1)のキュービットとオラクル間で、制御回転ゲート
【数８０】
2016057900.tif 000081
を実行し、
[5] [3]の逆操作を行い、オラクルをdisentangleする、として。
nキュービットの量子状態に対して、上記の[1]〜[5]の操作を行う量子演算方法。
【請求項５】
nを正の整数、y<2nを求めたい数とし、量子状態
【数８１】
2016057900.tif 000082
が与えられているものとし、δi(x)はxを２進法nビット表記したときのi番目の数（すなわち、xを2進法表記したときのn-i+1桁目の数）であるとし、siをi-1ビットの数として、j=1,2,…,n-1の順で請求項４の操作を実行し、最後の第nキュービットにアダマールゲートを作用させる量子演算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、量子ビットを用いて計算を行う技術に関する。
【背景技術】
【０００２】
［2面体群のcoset問題について］
この発明は、2面体群のcoset問題を従来よりも高速で解く量子アルゴリズムを提案する。ここで、2面体群のcoset問題とは、「Nを与えられた正の整数、d<Nを求めたい(あらかじめ決められた任意の)値とする。複数個の量子状態
【数１】
2016057900.tif 000002
（ただし、x<Nは任意のわからない数）が与えられたとき、dの値を決定せよ。」という問題である。単一最短ベクトル問題は2面体群のcoset問題に帰着できることが既に知られているため、提案する量子アルゴリズムと組み合わせることにより、単一最短ベクトル問題を高速に解くことが可能になる。
【０００３】
［2面体群について］
2面体群とは、正N角形の自己同形変換全体が作る非可換群のことである。数学的には、
DN={<a,b>|aN=b2=1,ab=ba-1}で定義される。|DN|=2Nであり、DNの部分群の個数は、(Nの約数の個数)+(Nの約数)であることが知られている。cosetとは、剰余類または傍系と訳される群論の概念で、Gが群、Hがその部分群、g∈Gとするとき、Hg={hg|h∈H}をGにおけるHの（Hによる、Hに関する、Hを法とする）左剰余類(left coset) という。
【０００４】
［単一最短ベクトル問題について］
複数の一次独立なベクトルが与えられたときに格子点の中で原点に最も近い整数係数の一次結合を見つける問題は、最短ベクトル問題と呼ばれている。最短ベクトル問題はNP困難であることが知られている。
【０００５】
最短ベクトル問題に、格子点の中で原点に最も近い整数係数の一次結合が一つしかないという約束を付け加えた問題を、単一最短ベクトル問題と呼ぶ。単一最短ベクトル問題は、最短ベクトル問題より易しい問題であり、NP困難性が示されていない。しかし、NP困難に近い難問であると考えられている。このことについては、例えば、Divesh Aggarwal and Chandan Dubey, Improved hardness results for unique shortest vector problem, arXiv:1112.1564を参照のこと。
【０００６】
単一最短ベクトル問題は2面体群のcoset問題に効率的に帰着できることが、 Oded Regev, Quantum Computation and Lattice Problems, SIAM Journal on Computing, Vol. 33, No. 3, pp. 738 - 760 (2004) arXiv:quant-ph/0304005によって示されている。したがって、提案の量子アルゴリズムは、例えば単一最短ベクトル問題を解くために利用できる。この発明によりNP困難問題が効率的に解けるわけではないが、NP困難に近い問題を従来よりも高速に解くことができる。
【０００７】
古典コンピュータにより最短ベクトル問題を解く最も一般的な方法は、LLLアルゴリズム（Lenstra-Lenstra-Lovasz lattice basis reduction algorithm）を利用する方法である。この方法により効率的に近似解を得ることはできるが、解の厳密性は保証されない。詳細は、Cohen, Henri (2000). A course in computational algebraic number theory. GTM 138. Springer. ISBN 3-540-55640-0.などを参照のこと。
【０００８】
厳密解を求める量子アルゴリズムに関する既存研究として、大きく2つの方向がこれまで研究されてきた。
【０００９】
一番目に、一般の2面体群のcoset問題を解くアルゴリズムで、多項式時間では解けないが、素朴にGroverのアルゴリズムを使うよりもよいオーダーで解くアルゴリズムを提案する研究である。この方向の研究成果としてKuperbergのアルゴリズムが知られている（例えば、非特許文献１参照。）。
【００１０】
Kuperburgのアルゴリズムは
【数２】
2016057900.tif 000003
で、Groverのアルゴリズムよりも高速な計算が可能だが、エラーに弱いことが欠点である。
二番目に、一般の2面体群ではなく、制限された2面体群に対する多項式時間アルゴリズムを提案する研究である。２面体群のcoset問題に関する研究の大部分はこの方向の研究である。
【００１１】
［Kuperbergのアルゴリズム］
提案アルゴリズムを説明する前に、これまで知られている中で最も高速なKuperbergのアルゴリズムを解説する。
【００１２】
Kuperbergのアルゴリズムは、以下の量子状態（coset状態と呼ばれる）
【数３】
2016057900.tif 000004
が多数与えられているときにdを特定するアルゴリズムである。ここで、Nは与えられた整数、d<Nは求めたい0以上の決まった整数、xの値はcoset状態ごとに異なるunknownな整数である。coset状態を観測すると(0,x)または(1,x+d)が得られ、xの値がわからないため、どちらの場合でもdの値がわからない。言い換えると、ランダムな値xがdの値をマスクしているため、dの値を簡単に求めることができない。coset状態の次元数は2N次元であり、先頭キュービット（0または1のインデックスが格納されたキュービット）を除いた空間はN次元である。以下、先頭キュービットを第1レジスタ、第二キュービット以下を第2レジスタと呼ぶ。
【００１３】
Kuperbergのアルゴリズムでは、まず与えられたcoset状態の第2レジスタに対してN次元の量子フーリエ変換を実行し、観測する。観測した値をk<Nとすると、残った第一レジスタは
【数４】
2016057900.tif 000005
となる。この状態にはxが含まれておらず、代わりに現れたkは観測で得られた数である。以下、この状態をKuperbergキュービットと呼ぶことにする。k=20,21,22,…,2logNに対するKuperbergキュービットを得ることができれば、量子フーリエ変換によりdの値を求めることができる。しかし、kは観測によって得られるN未満のランダムな値であり、このような都合のよい状況を期待することはできない。
【００１４】
そこで、Kuperbergのアルゴリズムでは、k1,k2に対するKuperbergキュービットの組から、k1+k2またはk1-k2に対するKuperbergキュービットを生成する。この生成方法は以下のとおりである。k1,k2に対するKuperbergキュービットは、テンソル積
【数５】
2016057900.tif 000006
で表現できる。この状態は、
【数６】
2016057900.tif 000007
に等しい。第1キュービットと第2キュービット間でCNOTを実行し、第2キュービットを観測する。観測結果の値0、1に応じて、残った量子状態はそれぞれ
【数７】
2016057900.tif 000008
となり、k1+k2またはk1-k2に対するKuperbergキュービットが得られる。この方法によって得られるKuperbergキュービットが、k1+k2とk1-k2のどちらになるか、選択することはできない。以後、この生成方法をKuperberg合成と呼ぶ。
【００１５】
たとえば、k1,k2を2進表示した値の最後のjビットがすべて0の場合、k1+k2,k1-k2ともに最後のj+1ビットはすべて0となる。そこで、Kuperbergキュービットを多数用意し、上記操作を繰り返せば、k=1000...0（2進表示）に対するKuperbergキュービットを得ることができる。この状態をx軸で観測すればdの最終ビットdnが特定できる。
【００１６】
さらに、以下の方法によりdの全てのビットを特定することができる。dのj番目のビットをdjと表記する。帰納法の仮定として、dn,dn-1,…,djが既にわかっているものとする。coset状態
【数８】
2016057900.tif 000009
から、第1レジスタが|1>ならば第2レジスタからΣi=jn2n-idiを引く制御マイナス操作を実行することにより、
【数９】
2016057900.tif 000010
を作ることができる。この状態の第2レジスタのj番目〜n番目のビットは第1レジスタの値が|0>であっても|1>であっても同じである。そこで、第2レジスタのj番目〜n番目のビットをz軸で観測すれば、
【数１０】
2016057900.tif 000011
が得られる。ここで、x|j-1,d|j-1はx,dの2進展開を最初のj-1番目までに制限した数字である。この状態を新たなcoset状態と考えることで、d|j-1の最終ビットdj-1を特定することができる。
【００１７】
Kuperbergのアルゴリズムが解いている問題は、本質的にSubset Sum問題である。Subset SumはNP完全問題であり、Kuperbergのアルゴリズムでは多項式時間で計算を終了することができない。
【００１８】
［2面体群のcoset問題とSubset Sum］
以下、簡単のためにN=2nとする。Kuperbergのアルゴリズムを高速化するために、n個の状態を集め、一度に干渉させてdを求める方法を考える。coset状態がpoly(n)個与えられているとする。このテンソル積は
【数１１】
2016057900.tif 000012
である。各coset状態からKuperbergキュービットを作ると
【数１２】
2016057900.tif 000013
と書ける。ここで、k1,k2,…,knはわかっている値である。テンソル積を展開すると
【数１３】
2016057900.tif 000014
となる。ただし、k=k1δ1(j)+k2δ2(j)+…+knδn(j) mod 2n、δi(j)はjの先頭からi番目のビットである。もしk=jならば量子フーリエ変換によりただちにdの値が求められるが、一般にk≠jなので、この方法でdを求めることはできない。
【００１９】
しかし、もし基底{|j>|j=0,1,…,2n-1}の順序をユニタリ変換を用いて入れ替えることにより
【数１４】
2016057900.tif 000015
の形に変形すれば、量子フーリエ変換でdを求めることができる。これを実現するための最も自然な方法は、(3)に新たな2n次元のオラクル|0>をつけ、
【数１５】
2016057900.tif 000016
を実行し、kの値からjを計算する逆関数の計算により、
【数１６】
2016057900.tif 000017
を実行することである。このようにすれば(3)から
【数１７】
2016057900.tif 000018
が得られ、状態|0>は最後のレジスタとエンタングルしていないので、(4)を得ることができる。このアルゴリズムの計算量は、kの値からjを計算する逆関数計算の難しさによって決まり、kからjを求める計算はSubset Sumと呼ばれるNP完全問題である。したがって、上記の方法によって、2面体群のcoset問題を効率的に解ける可能性は低い。
【００２０】
一般に、Kuperbergキュービットのテンソル積(2)の状態から出発すると、Pretty Good Measurementと呼ばれる量子最適観測を行っても、dを特定する問題はSubset Sum問題に帰着されることが知られている（Dave Bacon, Andrew M. Childs, Wim van Dam, From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups, Proc. 46th IEEE Symposium on Foundations of Computer Science (FOCS 2005), pp. 469-478.）
【００２１】
Subset Sumは擬多項式時間アルゴリズムが知られているものの、NP完全であり、多項式時間量子アルゴリズムの存在は望めない。したがって、高速な量子アルゴリズム開発のためには、coset状態からKuperbergキュービットを経由せずにdを求める方法を考えなければならない。
【先行技術文献】
【非特許文献】
【００２２】
【非特許文献１】Greg Kuperberg. A subexponential-time quantum algorithm for the dihedral hidden subgroup problem. SIAM Journal on Computing, Vol. 35, No. 1, pp. 170 - 188 (2005) arXiv:quant-ph/0302112.
【発明の概要】
【発明が解決しようとする課題】
【００２３】
以上に述べたことを鑑み、この発明は、Kuperbergアルゴリズムよりも2面体群のcoset問題を高速に解くアルゴリズムを実現する量子演算方法を提案することを目的とする。
【課題を解決するための手段】
【００２４】
この発明の１つの態様による量子演算方法は、coset状態
【数１８】
2016057900.tif 000019
が与えられているものとし、nを正の整数、d<2nを求めたい数、xをnビットのランダムなわからない数として、coset状態にmキュービットのレジスタである第3レジスタを追加し、第2レジスタに2n次元量子フーリエ変換を実行し、第2レジスタを観測して、得られたnビットの観測結果をkとし、rをkの下位n-mビットとし、第3レジスタで量子回転操作をすることにより、擬coset状態
【数１９】
2016057900.tif 000020
を得る。
【発明の効果】
【００２５】
Kuperbergアルゴリズムよりも2面体群のcoset問題を高速に解くことができる。
【図面の簡単な説明】
【００２６】
【図１】(5)の量子状態を示す図。
【図２】(6)の量子状態を示す図。
【図３】(14)の量子状態を示す図。
【図４】(15)の量子状態を示す図。
【図５】(16)の量子状態を示す図。
【図６】量子変換の例を示す図。
【図７】回路図の例を示す図。
【図８】回路図の例を示す図。
【発明を実施するための形態】
【００２７】
提案する量子演算方法のアルゴリズムでは、coset状態のテンソル積(1)を変形し、量子状態(2),(3)とは異なる量子状態（擬coset状態と呼ぶ）を経由して、Subset Sum問題の部分問題を近似的に解くことにより、(4)に近い形に変形する。この(4)に近い量子状態から、量子フーリエ変換を拡張した変換アルゴリズムを利用してdを高い確率で特定する。
【００２８】
提案のアルゴリズムにおける最大のポイントは最後に使用する量子フーリエ変換を拡張した変換アルゴリズムである。この量子フーリエ変換を実行する回路において、制御回転ゲートの回転角を変えることで、周期性を持たない量子状態から情報を取り出す。
【００２９】
提案の量子アルゴリズムは、前項で述べたSubset Sum問題との同等性と矛盾するように見えるかもしれない。しかし、この問題点は提案量子アルゴリズムにおいて以下のように回避されている。一般のインスタンスに関してSubset Sum問題に対する高速な量子アルゴリズムは知られていない。しかし、インスタンスを特殊な数に限定すればSubset Sum問題を解くことは可能である。そこで、coset状態を観測して得られる値がSubset Sum問題を解くために適当でない場合はそのcoset状態を捨て、Subset Sum問題を近似的に解ける場合だけを残すのである。提案アルゴリズムはこの方法を利用して、一般のインスタンスに対するSubset Sum問題を解くことなく、dの値を特定する。
【００３０】
以下、簡単のためN=2nとする。また、cを適当な数として、nc個のcoset状態が与えられているものとする。
【００３１】
１．mをn未満の整数、xをnビットのランダムな数、rn-mをn-mビットのランダムな数とする。
【数２０】
2016057900.tif 000021
とおき、擬coset状態と呼ぶ。φ(x,0,rn-m)は通常のKuperbergキュービットであり、擬coset状態はcoset状態とKuperbergキュービットの中間的な量子状態である。nc個のcoset状態のテンソル積(1)から、(2)の代わりに
【数２１】
2016057900.tif 000022
を作る。ここで、riはiビットのランダムな奇数である。また、riを2進展開表示すると最上位桁の1と次に現れる1との間に、０がclogn個以上続くものとする。(5)の量子状態を、図１に例示する。(5)の最初の擬coset状態はKuperbergキュービットなので、第2レジスタを持たない。2番目以降の擬coset状態は1〜n-1キュービットの第2レジスタを持つ。
【００３２】
２．(5)の各擬coset状態の第1キュービットを集めて第0レジスタを作り、(5)のi番目の擬coset状態の第2レジスタを新しい量子状態の第iレジスタ（i=2,3,…,n）とする。この結果、量子状態
【数２２】
2016057900.tif 000023
が得られる。(6)の量子状態を、図２に例示する。(6)には第1レジスタがない点に注意のこと。
【００３３】
３．すべてのi=2,3,…,nに対して、第iレジスタをri倍する。この変形には、すべてのri,ri+1,…,rnが奇数（より一般的には、ri,ri+1,…,rnとNが互いに素）であることが利用されている。
【００３４】
４．i=2,3,…,nの順番に、第i+1,…,nレジスタを、第iレジスタに足し込む。すなわち、以下の変換
【数２３】
2016057900.tif 000024
をi=2,3,…,nの順番に実行する。すると、量子状態は
【数２４】
2016057900.tif 000025
となる。ここで、
【数２５】
2016057900.tif 000026
である。
【００３５】
５．全てのi=2,3,…,nに対して、第iレジスタで2i次元量子フーリエ変換を実行し、観測する。観測結果をs2,s3,…,snとする。ここで、siはi-1ビットの数である。量子状態は
【数２６】
2016057900.tif 000027
となる。
【００３６】
６．次に、(8)に第1レジスタとしてnキュービットの初期状態|000…0>を追加する。
【数２７】
2016057900.tif 000028
【００３７】
７．関数fを
【数２８】
2016057900.tif 000029
で定義する。第0,1レジスタ間で
【数２９】
2016057900.tif 000030
を実行し、さらに
【数３０】
2016057900.tif 000031
を実行する。ここで、f-1はfの逆関数の近似、すなわちほとんどのy<2nに対してf-1・f(y)=yが成立する関数である。この結果、ほとんどのy<2nに対して、第0、1レジスタは
【数３１】
2016057900.tif 000032
となる。ここで、逆関数f-1の実行にはSubset Sum問題の計算が必要で、Subset Sumの解が一意でないため、第0レジスタは常に|0>とはならない。しかし、f-1はほとんどのy<2nに対してfの逆関数となっているため、第0レジスタは高い確率で0となる。すなわち、第0レジスタを観測すると高い確率で0となり、
【数３２】
2016057900.tif 000033
に近似的な量子状態が得られる。
【００３８】
(10)の量子状態は、以下のように表現することができる。この式においては、dをyと表記している。
【数３３】
2016057900.tif 000034
【数３４】
2016057900.tif 000035
がほぼ1対1なので、インデックスとしてyの代わりにz=f(y)を使うことができる。zをインデックスとして書き換えると、状態(10)は
【数３５】
2016057900.tif 000036
にほぼ等しい。
【００３９】
【数３６】
2016057900.tif 000037
であることから、
【数３７】
2016057900.tif 000038
である。ここで、
【数３８】
2016057900.tif 000039
はyのiビット目以降が作る数である。（すなわち、
【数３９】
2016057900.tif 000040
である。）したがって、
【数４０】
2016057900.tif 000041
である。この値は、
【数４１】
2016057900.tif 000042
のときはzと一致するが、一般にはzとは異なる値である。しかし、「z≧2j'となる最大のj’を見つけz=z-rj’とおく」操作をz<2jとなるまで繰り返せば1-1/nc-1以上の確率で正しく計算できる。この操作をgjと書くことにすると、(11)は
【数４２】
2016057900.tif 000043
に近似的に等しい。これを書き換えると、
【数４３】
2016057900.tif 000044
となる。
【００４０】
８．状態(13)から量子フーリエ変換を拡張した変換アルゴリズムによりdを求める。この変換アルゴリズムはr2,r3,…,rn,s2,s3,…,snをパラメータとして保有し、第1、第5ステップで得たランダムなr2,r3,…,rn,s2,s3,…,snに対して、常に高い確率でdを出力する。具体的には、j=2,3,…,nの順で以下の[1]から[5]の操作を実行する。その後、最後の第nキュービットにアダマールゲートを作用させる。これらの[1]から[5]の操作の回路図の例を図７及び図８に示す。図７は、図８の点線の内部の回路図の例を描いたものである。
【００４１】
[1]第j-1番目のキュービットに対して、第j,j+1,…,n番目のキュービットで作った数字に制御マイナス
【数４４】
2016057900.tif 000045
操作を行う。
【数４５】
2016057900.tif 000046
ここで、
【数４６】
2016057900.tif 000047
はrn-j+2の2ビット目以降が作る数字である。
【００４２】
[2]第j-1番目のキュービットに対してHadamard操作を実行する。
【００４３】
[3]jキュービットの初期化されたオラクルを付け加える。第j,j+1,…,n番目のキュービットで作った数字をzとし、オラクルで2sjz+δj(z) mod 2jを計算する。
【００４４】
[4]第i番目(i=1,2,…,j-1)のキュービットとオラクル間で、制御回転ゲート
【数４７】
2016057900.tif 000048
を実行する。
【００４５】
[5] [3]の逆操作を行い、オラクルをdisentangleする。
【００４６】
９．以上の操作を量子状態(13)に実行したのち、観測すると、観測結果は高い確率でdと一致する。
【００４７】
以下、上記説明した操作を一つ一つ詳しく説明していく。
【００４８】
［擬coset状態への変形］
初めに、coset状態から擬coset状態への変形方法を説明する。
【００４９】
coset状態
【数４８】
2016057900.tif 000049
の量子状態を図３に示す。このcoset状態においては、図３に示すように、第1レジスタが|0>又は|1>であり、第2レジスタは、第1レジスタが|0>のときは|xi>であり、第1レジスタが|1>のときは|xi+d mod N>である。
【００５０】
このcoset状態にmキュービット(0≦m<n)の第3レジスタをつけ、第2レジスタの下位mビットをコピーする。これは、第2レジスタの状態に対して、mod 2mで剰余をとることに等しいので、量子状態は
【数４９】
2016057900.tif 000050
である。(15)の量子状態を図４に示す。第2レジスタで量子フーリエ変換を実行し、観測で得られたnビットの値をkとすると、量子状態は
【数５０】
2016057900.tif 000051
となる。(16)の量子状態を図５に示す。ここで、kの先頭mビットを
【数５１】
2016057900.tif 000052
という記号で表す。第3レジスタで
【数５２】
2016057900.tif 000053
を実行すると、言い換えれば量子回転操作をすると、
【数５３】
2016057900.tif 000054
が得られる。
【００５１】
【数５４】
2016057900.tif 000055
は、kの下位n-mビットに等しい。
【数５５】
2016057900.tif 000056
とすると、得られた量子状態は
【数５６】
2016057900.tif 000057
である。以下、この量子状態を擬coset状態、rn-mをランダム係数と呼ぶことにする。
【００５２】
［擬coset状態の選別］
上記では擬coset状態を作成する方法を説明したが、量子状態(5)に使用される擬coset状態は、ランダム係数rn-mに対して条件が課される。後に実行するSubset Sum問題の解ができるだけ一意になるようにするためである。
【００５３】
目的のためには、ランダム係数rn-mが2n-m-1に近い方がよい。ランダム係数rn-mはn-mビットのランダムな数であり、その数を意図的に選ぶことはできないが、擬coset状態をたくさん作り、2n-m-1に近いランダム係数に対する擬coset状態だけをアルゴリズムで利用する。
【００５４】
量子状態(5)として使用する擬coset状態は、rn-mを2進展開すると
【数５７】
2016057900.tif 000058
における
【数５８】
2016057900.tif 000059
の0の個数（つまり、先頭ビットの1と次に現れる1の間の０の個数）がclogn個以上あるものとする。ここで、cは適当な正の整数であり、rn-mが1+clognビットない場合は、先頭の1以降はすべて0とする。このような状態は、21+clogn回擬coset状態を作成すれば得られるので、nの多項式回で量子状態(5)が得られる。
【００５５】
［第0レジスタの作成］
m=0,1,…,n-1に対する擬coset状態を作り、そのテンソル積を以下のように変形する。
【００５６】
まず、i=0,1,…,n-1の擬coset状態の第1レジスタ（キュービット）を集め、nキュービットの第0レジスタを作る。一方、i=1,…,n-1の擬coset状態の第2レジスタを、それぞれ第i+1レジスタとする。この結果、量子状態(5)は第0および第2〜nレジスタに再構成され、量子状態(6)が得られる。第0レジスタはnキュービット、第2〜nレジスタは1〜n-1キュービットを持つ。
【００５７】
［第1レジスタの追加］
量子状態(6)に、nキュービット初期状態|000…0>を第1レジスタとして追加し、量子状態(7)を作る。
【００５８】
［第0レジスタの基底変更］
関数fを
【数５９】
2016057900.tif 000060
と定義する。量子変換
【数６０】
2016057900.tif 000061
は加算回路により簡単に実行できる。
【００５９】
逆に、
【数６１】
2016057900.tif 000062
を古典アルゴリズムで計算するためには、次のようにすればよい。まず、w1,w2,…,wnを全て0とする。そして、ri≦zを満たす最大のiに対してwi=1とし、z=z-wiとおく。以下同じことをz=0になるまで繰り返し、得られたw=2n-1w1+2n-2w2+…+20wnがf-1(y)を近似する値である。f-1・f(y)=yとなる確率は1-1/(nc-1)で下から抑えられる。
【００６０】
したがって、上記古典アルゴリズムを量子コンピュータで動かすことにより、確率1-1/(nc-1)以上で
【数６２】
2016057900.tif 000063
が得られる。第0レジスタを観測して0が得られた場合（この確率は1-1/(nc-1)以下である）は次のステップに進む。そうでなかった場合は、擬coset状態からもう一度作りなおす。
【００６１】
［第2〜nレジスタの消去］
ここまでの操作により、量子状態(9)が得られた。第2〜nに量子フーリエ変換を実行し、観測することにより第2〜nレジスタを消去する。観測結果をsi(i=2,3,…,n)とすると、量子状態(10)が得られる。
【００６２】
［量子変換の実行］
量子状態(10)からdの下位ビット(c-1)lognを得るために、図６に例示する量子フーリエ変換に似た量子変換を実行する。
【００６３】
量子状態(13)において、すべてのsi (i=2,3,…,n)が0ならば、2n次元量子フーリエ変換によってdが得られる。si(i=2,3,…,n)が0でなくても、すべてのi=2,3,…,nに対してgi(z)=δi(z)なら、2n次元量子フーリエ変換回路の第i,j番(1≦i<j≦n)ワイヤ間の制御回転ゲートcR(1/(2j-i+1))を
【数６３】
2016057900.tif 000064
に代えた量子回路によってdが得られる。一般のgi(z)の場合は、すべてのHadamard変換の手前で「z≧2j'となる最大のj'を見つけz=z-rj'とおく」操作に対応する制御マイナス操作を行う。さらに、すべての1≦i<j≦nに関して、cR((2sj+1)/(2j-i+1))を次の操作に置き換える。zをn-j-1ビット未満の数とする。まず、jビットのオラクルを用いて2sjz+δj(z) mod 2jを計算する。次に、第i番目のワイヤとオラクルの間で制御回転操作を行うことにより、
【数６４】
2016057900.tif 000065
を実行する。最後に逆演算によりオラクルを消去する。
【００６４】
〔量子演算装置についての概説〕
量子演算方法を実行するための量子演算装置は、量子コンピュータ単体で実現できる。量子コンピュータの実現する物理系としては、例えば、イオントラップを用いる方法（J. I. Cirac and P. Zoller, Quantum computations with cold trapped ions, Physical Review Letter 74;4091, 1995）、量子ビットとして光子の偏光や光路を用いる方法（Y. Nakamura, M. Kitagawa, K. Igeta, In 3-rd Proc. Asia-Pacific Phys. Comf., World Scientific, Singapore, 1988）、液体中の各スピンを用いる方法（Gershenfield, Chuang, Bulk spin resonance quantum computation, Science, 275;350, 1997）、シリコン結晶中の核スピンを用いる方法（B. E. Kane, A silicon-based nuclear spin quantum computer, Nature 393, 133, 1998）、量子ドット中の電子スピンを用いる方法（D. Loss and D. P. DiVincenzo, Quantum computation with quantum dots, Physical Review A 57, 120-126, 1998）、超伝導素子を用いる方法（Y. Nakamura, Yu. A. Pashkin and J. S. Tsai, Coherent control of macroscopic quantum states in a single-cooper pair box, Nature 393, 786-788, 1999）等を例示できる。また、それぞれの物理系に対する量子コンピュータの実現方法については、「http://www.ipa.go.jp/security/fy11/report/contents/crypto/crypto/report/QuantumComputers/contents/doc/qc_survey.pdf」や「M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, Cambridge UniversityPress, Chapter 7 Physical Realization」に詳しい。
【００６５】
＜量子ビット＞
イオントラップ量子コンピュータでは、例えば、イオンの基底状態と励起状態を利用して量子ビットを実現する。また、核スピンを量子ビットとして用いる場合には、例えば、「T. D. Ladd, et al., "All-Silicon quantum computer," Phys. Rev. Lett., vol. 89,no. 1, 017901-1‐017901-4, July 1, 2002.」に記載されているようにＳｉ（１１１）基板等に各量子ビットを生成する。なお、量子ビットの初期量子状態は、例えば、他の演算の量子回路による操作によって得られたものを用いてもよいし、各量子ビットが生成された基板をｍＫ（ミリケルビン）オーダー以下に冷却してスピンの向きを揃えた後、所定の電磁波パルスを印加して生成してもよい。また、量子ビットとして光子の偏光を用いる場合には、例えば、パラメトリックダウンコンバージョン（ＰＤＣ：parametric down conversion）（例えば、「P. G. Kwiat, K. Mattle, H. Weinfurter, A. Zeilinger, A. V. Sergienko, and Y. Shih, “New high-intensity source of polarization-entangled photon pairs,” Phys. Rev. Lett. ,75:4337-4341, 1995.」「P. G. Kwiat, E. Waks, A. G. White, I. Appelbaum, and P. H. Eberhard, “Ultrabright source of polarization-entangled photons,” Phys. Rev. A, 60:R773-R776, 1999.」等参照。）によって生成された複数個の単一光子を用いる。この場合、各量子ビットの初期量子状態は、例えば、他の演算の量子回路による操作によって得られたものを用いる。また、パラメトリックダウンコンバージョン等によって生成された単一光子に、ビームスプリッタや偏光回転素子等によって実現されるウォルシューアダマール変換、ＣＮＯＴ、回転等の操作を行い、既述の初期量子状態を生成することとしてもよい。
【００６６】
その他、上記の文献に記載された方法で量子ビットを用意することとしてもよい。
【００６７】
また、演算前後や演算途中において量子ビットの量子状態を保存する必要がある場合には、例えば、量子ドット内の電子準位、核スピン、あるいは超伝導体内部の電荷（クーパー対）量を量子ビットとして用いてデータを保存する量子メモリ等を用いてもよい（A.Barenco, D.Deutsch, and A.Ekert, Phys. Rev. Lett.74,4083(1995)、松枝秀明  電子情報通信学会誌  A Vol.J81-A No.12(1998)1978、T.H.Oosterkamp et.al., Nature 395,873(1998)、D.Loss and D.P. DiVincenzo, Phys. Rev. A57(1998) 120. T.Oshima, quant-ph/0002004, http://arxiv.org/abs/quant-ph/0002004、B.E.Kane, A silicon-based nuclear spin quantum computer, Nature, 393, 133(1998)、http://www.snf.unsw.edu.au/、Y.Nakamura, Yu. A. Pashkin and J.S.Tsai, Nature 398(1999)768）。
【００６８】
＜ＣＮＯＴ演算＞
イオントラップ量子コンピュータでは、例えば、イオンを直線上に並べ、各イオンに狙いを定めたレーザービーム照射によってＣＮＯＴ演算を実現する。また、量子ビットとして光子の偏光を用いる場合には、例えば、偏光ビームスプリッタ等を用い、「T.B. Pittman, M.J. Fitch, B.C. Jacobs, J.D. Franson: “Experimental Controlled-NOT Logic Gate for Single Photons in the Coincidence Basis,” quant-ph/0303095, http://arxiv.org/abs/quant-ph/0303095」記載のPittman et al. 方式によってＣＮＯＴ演算を実現する。また、核スピンを量子ビットとして用いる場合には、例えば、所定の電磁波パルスを量子ビットに印加することによってＣＮＯＴ演算を実現できる。
【００６９】
その他、上記の文献に記載された方法でＣＮＯＴ演算を実現してもよい。
【００７０】
＜量子ビット単体操作＞
イオントラップ量子コンピュータでは、例えば、イオンを直線上に並べ、各イオンに狙いを定めたレーザービーム照射によって量子ビット単体の操作を実現する。核スピンを量子ビットとして用いる場合には、電磁波パルスやレーザービーム照射によって各処理を実現する。また、量子ビットとして光子の偏光を用いる場合には、例えば、偏光回転素子等によって実現する。
【００７１】
なお、本発明は既述の実施の形態に限定されるものではなく、その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。例えば、可換な演算については演算の順序に限定がない。また、ｎ個の量子ビットに対する任意のユニタリ変換は、２種類の基本量子ゲート（１量子ビットに対し任意のユニタリ変換を作用させるＵゲートと、２量子ビットに作用する制御ＮＯＴゲート）を組み合わせることにより実現できることが知られている。また、量子回路に使われる全ての演算は単一量子ビットに対する１量子ビット演算と制御ＮＯＴ演算に分解できるので（上記非特許文献３参照）、各機能部の具体的構成についても種々等価な量子回路を構成できる。また、既述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【図１】
2016057900.tif 000085
【図２】
2016057900.tif 000086
【図３】
2016057900.tif 000087
【図４】
2016057900.tif 000088
【図５】
2016057900.tif 000089
【図６】
2016057900.tif 000090
【図７】
2016057900.tif 000091
【図８】
2016057900.tif 000092