(57)【特許請求の範囲】
【請求項１】
ｍ，ｎをそれぞれ予め定められた１以上の整数として、2n×2n×…×2nのｍ次元空間における環Ｚ2^(n+1)上のｍ変数多項式関数である予め与えられた２次関数f(x1,x2,…,xm)=a1x12+a2x22+…+amxm2mod 2n+1と、シフト量s1,s2,…,smによってg(x1,x2,…,xm)=f(x1-s1,x2-s2,…,xm-sm)と表される２次関数g(x1,x2,…,xm)に関するオラクル
【数４２】
0005496921.tif 000043
が予め与えられているとき、上記シフト量s1,s2,…,smを求めるための量子演算方法であって、
ｎ個の量子ビットからなる変数用レジスタがｍ個、ｎ個の量子ビットからなる補助レジスタが１個であり、各上記変数用レジスタ並びに上記補助レジスタに含まれる(m+1)n個の量子ビットの初期状態を|0〉とし、
【数４３】
0005496921.tif 000044
として、
各上記変数用レジスタに含まれるｍｎ個の量子ビットのそれぞれにアダマール変換を適用するアダマール演算ステップと、
上記補助レジスタに対して、２次関数g(x1,x2,…,xm)に関する上記オラクルを実行するオラクル演算ステップと、
上記補助レジスタに対して、
【数４４】
0005496921.tif 000045
で表される量子回転操作を実行する回転演算ステップと、
上記補助レジスタに対して、上記オラクルの量子逆操作を実行するオラクル逆演算ステップと、
ｍ個の上記変数用レジスタに対して、
【数４５】
0005496921.tif 000046
を実行する演算ステップと
を有する量子演算方法。
【請求項２】
ｍ，ｎをそれぞれ予め定められた１以上の整数として、2n×2n×…×2nのｍ次元空間における環Ｚ2^(n+1)上のｍ変数多項式関数である予め与えられた２次関数f(x1,x2,…,xm)=a1x12+a2x22+…+amxm2mod 2n+1と、シフト量s1,s2,…,smによってg(x1,x2,…,xm)=f(x1-s1,x2-s2,…,xm-sm)と表される２次関数g(x1,x2,…,xm)に関するオラクル
【数４６】
0005496921.tif 000047
が予め与えられているとき、上記シフト量s1,s2,…,smを求めるための量子演算装置であって、
ｎ個の量子ビットからなる変数用レジスタがｍ個、ｎ個の量子ビットからなる補助レジスタが１個であり、各上記変数用レジスタ並びに上記補助レジスタに含まれる(m+1)n個の量子ビットの初期状態を|0〉とし、
【数４７】
0005496921.tif 000048
として、
各上記変数用レジスタに含まれるｍｎ個の量子ビットのそれぞれにアダマール変換を適用するアダマール演算部と、
上記補助レジスタに対して、２次関数g(x1,x2,…,xm)に関する上記オラクルを実行するオラクル演算部と、
上記補助レジスタに対して、
【数４８】
0005496921.tif 000049
で表される量子回転操作を実行する回転演算部と、
上記補助レジスタに対して、上記オラクルの量子逆操作を実行するオラクル逆演算部と、
ｍ個の上記変数用レジスタに対して、
【数４９】
0005496921.tif 000050
を実行する演算部と
を含む量子演算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、量子演算方法、量子演算装置に関する。より詳しくは、所与の２次関数の隠れシフト問題を解く量子演算方法、量子演算装置に関する。
【背景技術】
【０００２】
1994年、Shorは量子コンピュータ上で動作する高速な素因数分解アルゴリズムと離散対数問題を解くアルゴリズムを提案した（非特許文献１）。Shorの量子アルゴリズムは拡張され、さまざまな問題に応用される。
【０００３】
Shorの量子アルゴリズムが応用される最も代表的な問題は、隠れ部分群問題である。隠れ部分群問題とは部分群のコセット上で同じ値を持つ関数が与えられたときに元の部分群を効率的に特定する問題であり、対称群の隠れ部分群問題が解けるとグラフ同型性判定問題が高速に解けることが知られている。
【０００４】
この他、Shorの量子アルゴリズムが応用される問題として隠れシフト問題が知られている。隠れシフト問題は、与えられた関数の空間上でのシフト量を計算する問題であり、非特許文献２で初めて提案された。隠れシフト問題の難しさは、与えられた関数のクラスによって決まる。非特許文献２ではMultiplicative character関数の隠れシフト問題が多項式時間で解けることが示されている。Multiplicative character関数は、ラビン暗号などと関係することで知られるルジャンドル関数（与えられた数が平方剰余であるかどうかを表す関数）を含む。
【０００５】
非特許文献２に触発され、さまざまな隠れシフト問題が研究されている。例えば、非特許文献３には２次ブール関数の隠れシフト問題を解くアルゴリズムが提案されている。ここで２次ブール関数とは、0または1の値をとる２次関数である。
【０００６】
隠れシフト問題は、与えられた形状の図形が空間内部に隠されているとき、その図形の位置を高速に決定する問題であると考えることができる。このため、隠れシフト問題の解決は図形のパターンマッチングへの応用など応用範囲が広く、種々の関数に対する隠れシフト問題を高速で解決することが望まれる。
【０００７】
なお、量子計算や量子アルゴリズムなどについては、非特許文献４に詳しい。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】P. Shor, "Algorithms for Quantum Computation: Discrete Logarithms and Factoring," Proc. of the 35th FOCS, pp. 124-134, 1994.
【非特許文献２】W. van Dam, S. Hallgren, and L. Ip, "Quantum algorithms for some hidden shift problems," In Proc. SODA'03, pp. 489-498, 2003.
【非特許文献３】Martin Roetteler, "Quantum algorithms for highly non-linear Boolean functions," Proceedings of SODA 2010, arXiv:quant-ph/0811.3208
【非特許文献４】M. A. Nielsen and I.L. Chuang, "Quantum Computation and Quantum Information", Cambridge University Press, 2000.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
非特許文献３では、量子アルゴリズムの適用対象が２次ブール関数に限定されているため、この量子アルゴリズムの応用範囲は狭い。例えば、２次関数f(x1,x2)=(x1-2)2+(x2-1)2mod 2n+1は(2,1)の位置に中心を持ち、f(x1,x2)の値が中心からの距離の２乗の2n+1を法とする剰余で表される同心円関数であるが、f(x1,x2)の値がブール値ではないため、非特許文献３で提案された量子アルゴリズムを用いても２次関数f(x1,x2)の中心を特定することができない。
【００１０】
本発明は、このような実情に鑑みて、所与の２次関数の隠れシフト問題を解く量子演算技術を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明は、ｍ，ｎをそれぞれ予め定められた１以上の整数として、2n×2n×…×2nのｍ次元空間における環Ｚ2^(n+1)上のｍ変数多項式関数である予め与えられた２次関数f(x1,x2,…,xm)=a1x12+a2x22+…+amxm2mod 2n+1と、シフト量s1,s2,…,smによってg(x1,x2,…,xm)=f(x1-s1,x2-s2,…,xm-sm)と表される２次関数g(x1,x2,…,xm)に関するオラクル
【数１】
0005496921.tif 000002
が予め与えられているとき、シフト量s1,s2,…,smを求めるための量子演算技術であり、下記のような処理を行う。
【００１２】
ｎ個の量子ビットからなる変数用レジスタがｍ個、ｎ個の量子ビットからなる補助レジスタが１個であり、各変数用レジスタ並びに補助レジスタに含まれる(m+1)n個の量子ビットの初期状態を|0〉とし、
【数２】
0005496921.tif 000003
とする。
【００１３】
各変数用レジスタに含まれるｍｎ個の量子ビットのそれぞれにアダマール変換を適用する（アダマール演算処理）。
【００１４】
補助レジスタに対して、２次関数g(x1,x2,…,xm)に関するオラクルを実行する（オラクル演算処理）。
【００１５】
補助レジスタに対して、
【数３】
0005496921.tif 000004
で表される量子回転操作を実行する（回転演算処理）。
【００１６】
補助レジスタに対して、オラクルの量子逆操作を実行する（オラクル逆演算処理）。
【００１７】
ｍ個の変数用レジスタに対して、
【数４】
0005496921.tif 000005
を実行する。
【発明の効果】
【００１８】
本発明によると、２次関数の隠れシフト問題を解くために拡張Clifford群の性質を或る特別な場合に限定することで得られる関係を、量子コンピュータ上で演算可能な２n次元複素ベクトル空間上の演算に置換することによって、所与の２次関数の隠れシフト問題を量子コンピュータ上で解くことができる。
【図面の簡単な説明】
【００１９】
【図１】回転角度τdの位相演算子を２乗する演算Ｖd,SPを表す量子回路。
【図２】図１に示される量子回路に含まれる量子演算の記法について図解した量子回路。
【図３】本発明である量子演算装置の実施形態の機能構成例を示す図。
【図４】２次関数の変数の個数を２として４を法とする演算の場合の実施形態を表す量子回路。
【図５】図４に示される量子回路に含まれる量子演算ＶF[1]を実現する量子回路。
【図６】図４に示される量子回路に含まれる量子演算ＶF[2]を実現する量子回路。
【発明を実施するための形態】
【００２０】
本発明は、拡張Clifford群の性質を利用することによって、量子コンピュータ上で所与の２次関数の隠れシフト問題を解く。そこでまず、本発明の原理の説明に先立ち、拡張Clifford群の性質について概説する。
【００２１】
＜本発明の原理を理解するために資する従来技術＞
以下、本発明の原理を理解するために資する従来技術として、下記参考文献Ａに開示された成果の一部を概説する。証明等の詳細は参考文献Ａを参照されたい。
（参考文献Ａ）D. Appleby, "SIC-POVM and the Extended Clifford Group", J. Math. Phys. 46, 052107 (2005). arXiv:quant-ph/0412001
【００２２】
まず、Ｕ(d)を全てのｄ次元ユニタリ演算子からなる群とする。ｄは正整数である。また、Ｚを整数環とし、Ｚdを整数環ＺのイデアルｄＺによる剰余環とする。すなわち、Ｚd＝｛０，１，・・・，ｄ−２，ｄ−１｝である。Ｚ2は各要素が整数である２次元ベクトルの集合を表す。→ｐ＝（ｐ1，ｐ2）T∈Ｚ2、→ｑ＝（ｑ1，ｑ2）T∈Ｚ2としたとき（記号Ｔは転置を表す）、ブラケット記号〈・，・〉を式（１）の如く定義する。また、記号"→"は、記号"→"の次の文字の頭上に附されることを意味し、例えば→Ａは文字Ａの頭上に記号"→"が附された組み合わせ文字を表す。
【数５】
0005496921.tif 000006
【００２３】
|0>，|1>，・・・，|d-1>をｄ次元複素ベクトル空間Ｃdにおける正規直交基底とし、演算子Ｔ、Ｓ、Ｄ→pを式（２）−（４）のように定義する。記号ｉは虚数単位（imaginary unit）であり、ネピア数（Napier's constant;自然対数の底）ｅのｐ乗をexp(ｐ)の如く表す。
【数６】
0005496921.tif 000007
【００２４】
このとき、全ての→ｐ＝（ｐ1，ｐ2）T∈Ｚ2，→ｑ＝（ｑ1，ｑ2）T∈Ｚ2に対して、式（５）−（７）が成り立つ。記号†はエルミート共役を表す。
【数７】
0005496921.tif 000008
【００２５】
式（４）に定義される演算子Ｄ→pに関して、式（８）の定義を満たすｄ×ｄの行列を要素（元）とする群ＧＰ(d)を一般化Pauli群（Weyl-Heisenberg群）と呼ぶ。Ｒは実数体を表す。
【数８】
0005496921.tif 000009
【００２６】
また、一般化Pauli群ＧＰ(d)に対する拡張Clifford群Ｃ(d)は、式（９）の定義を満たすｄ×ｄの行列を元とする群である。Ｕ†は、行列Ｕの共役転置行列である。
【数９】
0005496921.tif 000010
【００２７】
また、ｄに関して、~ｄを式（１０）のように定義する。また、記号"~"は、記号"~"の次の文字の頭上に附されることを意味し、例えば~Ａは文字Ａの頭上に記号"~"が附された組み合わせ文字を表す。
【数１０】
0005496921.tif 000011
【００２８】
このとき、環Ｚ~d上の特殊線形群ＳＬ（２，Ｚ~d）は、行列式が１になる２×２行列全体の集合として与えられる（式（１１）参照）。
【数１１】
0005496921.tif 000012
【００２９】
式（１１）で与えられる特殊線形群ＳＬ（２，Ｚ~d）の元のうち、βが０以外の値であり且つβが~ｄと互いに素である（ゆえに逆元β-1∈Ｚ~dが存在する）行列を、prime matrixという。なお、βが与えられているときに逆元β-1の算出は一次合同式β-1β≡１（mod ~d）の解法として古典的知識であるから説明を省略する。
【００３０】
〔補題１〕
拡張Clifford群Ｃ(d)に属する任意のユニタリ演算子Ｕ∈Ｃ(d)について、全ての→ｐ∈Ｚ2に対して式（１２）を満たすＦ∈ＳＬ（２，Ｚ~d），→Ω∈（Ｚd）2が存在する。
【数１２】
0005496921.tif 000013
【００３１】
〔補題２〕
Ｆをprime matrix((α，γ)T，(β，δ)T)∈ＳＬ（２，Ｚ~d）とし、演算子ＶFを式（１３）のように定義する。このとき、演算子ＶFは、全ての→ｐ∈Ｚ2に対して式（１４）を満たす拡張Clifford群Ｃ(d)に属するユニタリ演算子である。
【数１３】
0005496921.tif 000014
【００３２】
〔補題３〕
Ｆをprime matrixではない２×２行列((α，γ)T，(β，δ)T)∈ＳＬ（２，Ｚ~d）とする。このとき、δ＋ｘβが０以外の値であり且つδ＋ｘβが~ｄと互いに素である整数ｘが存在し、Ｆ1＝((0，1)T，(-1，x)T)，Ｆ2＝((γ＋ｘα，−α)T，(δ＋ｘβ，−β)T)とすると、Ｆ1とＦ2はそれぞれprime matrix∈ＳＬ（２，Ｚ~d）であり、Ｆ＝Ｆ1Ｆ2を満たす。
【００３３】
〔補題４〕
Ｆ∈ＳＬ（２，Ｚ~d），→Ω∈（Ｚd）2とせよ。Ｕを、拡張Clifford群Ｃ(d)に属する任意のユニタリ演算子Ｕ∈Ｃ(d)とする。もしＦがprime matrixならば式（１５）が成立し、もしＦがprime matrixでないならばＦ＝Ｆ1Ｆ2を満たすprime matrix Ｆ1とprime matrix Ｆ2を選択する（補題３参照）ことにより式（１６）が成立する。しからば、全ての→ｐ∈Ｚ2に対して式（１７）が成立する。ＶF，ＶF1，ＶF2については式（１３）を参照せよ。
【数１４】
0005496921.tif 000015
【００３４】
補題４から、拡張Clifford群の任意の要素（ユニタリ演算子）Ｕは、せいぜい２つのＶFと１つのＤ→Ωを使って表現できることが分かる。
【００３５】
＜本発明の原理＞
本発明では、既述の拡張Clifford群の性質を、隠れシフト問題の解を求めるために応用する。隠れシフト問題は、前述の通り、与えられた関数の空間上でのシフト量を計算する問題であり、ここでは具体的に、m,nを予め定められた１以上の整数として、2n×2n×…×2nのｍ次元空間における環Ｚ~d上のｍ変数多項式関数である２次関数f(x1,x2,…,xm)と、適当なs1,s2,…,smに対してg(x1,x2,…,xm)=f(x1-s1,x2-s2,…,xm-sm)と表される２次関数g(x1,x2,…,xm)に関するオラクルが与えられているとき、シフト量s1,s2,…,smを求める問題とする。2n×2n×…×2nのｍ次元空間における環Ｚ~d上のｍ変数多項式関数である２次関数f(x1,x2,…,xm)の多重指数は２であり、このようなf(x1,x2,…,xm)として、ここではf(x1,x2,…,xm)=a1x12+a2x22+…+amxm2mod 2n+1を考えることにする。２次関数g(x1,x2,…,xm)に関するオラクルとは式（１８）で表される量子操作である。ただし、式（１８）において、○と＋との組合せ記号は、２を法とする加算（排他的論理和）を表す。
【数１５】
0005496921.tif 000016
【００３６】
本発明では、補題２におけるprime matrix Ｆを式（１９）に示すＦとし、d=2nとすることが主要な特徴の一つである。つまり、補題２のＦ＝((α，γ)T，(β，δ)T)において、α＝１，γ＝０，δ＝１とおいたものが式（１９）のＦであり、式（２）においてd=2nとおいたものが式（２０）のτdである。このとき、式（１３）で表されるＶFは式（２１）のように表すことができる。なお、式（２１）のＶFは2n次元複素ベクトル空間上のユニタリ演算である。
【数１６】
0005496921.tif 000017
【００３７】
〔量子コンピュータ上の演算の基本的な性質〕
ここで、量子コンピュータにおける演算の基本的な事項について説明する。通常、量子コンピュータにおける情報の基本単位を「量子ビット」と呼ぶ。現在のコンピュータにおける「ビット」に相当するものである。第ｊ量子ビットの状態|xj>は、|0>，|1>の二値の重ね合わせ状態で表わされる（式（２２）参照）。
【数１７】
0005496921.tif 000018
【００３８】
ｐ0とｐ1は確率振幅と呼ばれ、|ｐ0|2＋|ｐ1|2＝１を満たす複素数であり、この量子状態を観測すると確率|ｐ0|2で|0>、確率|ｐ1|2で|1>の状態が得られる。量子状態は、式（２２）の右辺に示されるように、確率振幅を要素に持つ２次元複素ベクトルで表わされる。或る量子状態ｐ0|0>＋ｐ1|1>から別の量子状態ｐ0'|0>＋ｐ1'|1>に変換する量子コンピュータ上の演算Ｕは、式（２３）で表される。
【数１８】
0005496921.tif 000019
【００３９】
|ｐ0|2＋|ｐ1|2＝１かつ|ｐ0'|2＋|ｐ1'|2＝１なので、この演算Ｕは、２次元複素ベクトル空間Ｃ2上で全てのベクトルの位置関係を保ったまま同じように回転させる演算（ユニタリ演算）となる。
【００４０】
ｎ量子ビットの量子状態|x>は、式（２４）のようなテンソル積で表わされ、２n次元複素ベクトルとなる。よって、ｎ量子ビットに対する演算は２n次元複素ベクトル空間上のユニタリ演算となる。
【数１９】
0005496921.tif 000020
【００４１】
このように、量子コンピュータ上の演算は、２n次元複素ベクトル空間上のユニタリ演算である。したがって、ｄ=2nであるから、２n次元複素ベクトル空間上のユニタリ演算である式（２１）のＶFを量子コンピュータで実行することができる。そこで、式（２１）のＶFを量子コンピュータ上で実現する方法について説明する。最初に、以下の演算を定義する。ここで、|x>は式（２４）で表されるｎ量子ビットからなる量子状態を表す。式（２５）は、周知のｎ量子ビットの量子フーリエ変換（Quantum Fourier Transfrom）である。また、式（２６）は、角度τd(ただしｄ=2n)の位相演算子を２乗する（Square Phase）演算である。
【数２０】
0005496921.tif 000021
【００４２】
＜βが奇数の場合＞
式（２５）（２６）を用いると、式（１９）においてβが奇数の場合、式（２１）で表されるＶFは式（２７）のように変形される。詳しくは後述するが、βには所与の２次関数f(x1,x2,…,xm)=a1x12+a2x22+…+amxm2mod 2n+1の係数ai（i=1,2,…,m）の逆元が入る。係数aiが与えられているときに逆元ai-1の算出は一次合同式ai-1ai≡１（mod ~d）の解法として古典的知識であるから説明を省略する。
【数２１】
0005496921.tif 000022
【００４３】
既述のように、ＱＦＴ2^(n)は周知の量子フーリエ変換であり、量子コンピュータ上で効率的に実行できることが知られている〔非特許文献３の５．１節〕。なお、２^(n)は２nを表す。(ＱＦＴ2^(n))β^(-1)は量子コンピュータ上で演算ＱＦＴ2^(n)をβ-1回繰り返すことを意味する。
【００４４】
次にＶ(^x)2^(n),SPについて考える。^xの２進数表現を^x 1^x 2…^x nとする。１０進数表現では式（２８）が成り立つ。ここで記号"＾"は、記号"＾"の次の文字の頭上に附されることを意味し、例えば＾Ａは文字Ａの頭上に記号"＾"が附された組み合わせ文字を表す。この記号はべき乗を表す記号"＾"と同じであるが、文脈よりその区別は可能である。
【数２２】
0005496921.tif 000023
【００４５】
すると、式（２９）および式（３０）が成立する。
【数２３】
0005496921.tif 000024
【００４６】
ゆえに、入力状態|^x>=|^x1^x2…^xn>に対して、図１に示される量子回路に従った演算系列を施せば、Ｖ(^x)2^(n),SPの演算を実現できることが分かる。なお、図１では、一つの変数用レジスタに含まれるｎ個の量子ビットを単にxk（ｋ＝１，２，…，ｎ）と表記しているが、このxkが^xkに対応すると思えばよい。
【００４７】
ここで、図１に表れる単一量子ビットゲートないし制御ゲートに現れる記号Ｒ2^(n)jは、式（３１）で定義されるユニタリ変換Ｒ2^(n)をｊ回繰り返すことを表している。
【数２４】
0005496921.tif 000025
【００４８】
また、図１において、第３列目以降の演算は、図２に示すようなcontrolled-Ｒ2^(n)jの演算系列を省略表記したものである。よって、図１に示す演算は、controlled-Ｒ2^(n)jの系列で表わされることが分かる。
【００４９】
式（２７）における演算(Ｖ(^x)2^(n),SP)β＾(-1)は、演算Ｖ(^x)2^(n),SPをβ-1回繰り返すことを意味する。ここで、演算Ｖ(^x)2^(n),SPを実現する各演算（図１のＲ2^(n)jおよびcontrolled-Ｒ2^(n)j）が可換であることを考慮すると（このことは、Ｒ2^(n)jおよびcontrolled-Ｒ2^(n)jが対角行列で表せる演算であることから容易に分かる）、Ｖ(^x)2^(n),SPをβ-1回繰り返すことは、図１に示される各演算をβ-1回繰り返すこと、つまり、図１のＲ2^(n)jおよびcontrolled-Ｒ2^(n)jをＲ2^(n)j・β^(-1)およびcontrolled-Ｒ2^(n)j・β^(-1)に置き換えることと等価である。演算(Ｖ(x)2^(n),SP)β＾(-1)についても同様である。
【００５０】
＜βが偶数の場合＞
式（１９）においてβが偶数の場合、補題３に従い、２つのprime matrix Ｆ1, Ｆ2∈ＳＬ（２，Ｚ~d）を用いて式（１９）のＦをＦ＝Ｆ1Ｆ2と表すことができるので、βが奇数の場合に帰着される。つまり、βが偶数の場合は、βが奇数の場合のＶFを実行する量子回路を二つ直列に並べた量子回路によって実行できる。以下、このことを具体的に説明する。
【００５１】
補題３によると、式（１９）のＦは式（３１ａ）の２つのprime matrix Ｆ1, Ｆ2∈ＳＬ（２，Ｚ~d）を用いてＦ＝Ｆ1Ｆ2と表すことができる。式（３１ａ）においてｔは、「１＋ｔβ≠０且つ１＋ｔβが~ｄ（ただしd=2n）と互いに素である」を満たす整数ｔである。詳しくは後述するが、βには所与の２次関数f(x1,x2,…,xm)=a1x12+a2x22+…+amxm2mod 2n+1の係数ai（i=1,2,…,m）の逆元が入る。係数aiが与えられているときに逆元ai-1の算出は一次合同式ai-1ai≡１（mod ~d）の解法として古典的知識であるから説明を省略する。２次関数f(x1,x2,…,xm)が既知であるため、本発明の実施の前にｔを求めておくことができる。このｔの計算方法は古典的知識であるから説明を省略する。
【数２５】
0005496921.tif 000026
【００５２】
このとき、Ｆ1について式（３１ｂ）が成立し、Ｆ2について式（３１ｃ）が成立する。
【数２６】
0005496921.tif 000027
【００５３】
式（３１ｂ）は、式（２５）（２６）を用いると、式（３１ｄ）のように変形され、式（３１ｃ）は、式（２５）（２６）を用いると、式（３１ｅ）のように変形される。
【数２７】
0005496921.tif 000028
【００５４】
式（３１ｄ）にて、(ＱＦＴ2^(n))(-1)^(-1)は、量子コンピュータ上で演算ＱＦＴ2^(n)を(-1)-1回繰り返すことを意味する。元-1が与えられているときに逆元(-1)−１の算出は一次合同式(-1)−１(-1)≡１（mod ~d）の解法として古典的知識であるから説明を省略する。
【００５５】
式（３１ｄ）にて、(Ｖ(x)2^(n),SP)(-1)＾(-1)は、演算Ｖ(x)2^(n),SPを(-1)-1回繰り返すことを意味する。ここで、演算Ｖ(x)2^(n),SPを実現する各演算（図１のＲ2^(n)jおよびcontrolled-Ｒ2^(n)j）が可換であることを考慮すると（このことは、Ｒ2^(n)jおよびcontrolled-Ｒ2^(n)jが対角行列で表せる演算であることから容易に分かる）、Ｖ(x)2^(n),SPを(-1)-1回繰り返すことは、図１に示される各演算を(-1)-1回繰り返すこと、つまり、図１のＲ2^(n)jおよびcontrolled-Ｒ2^(n)jをＲ2^(n)j・(-1)^(-1)およびcontrolled-Ｒ2^(n)j・(-1)^(-1)に置き換えることと等価である。
【００５６】
式（３１ｅ）にて、(ＱＦＴ2^(n))(1+tβ)^(-1)は、量子コンピュータ上で演算ＱＦＴ2^(n)を(1+tβ)-1回繰り返すことを意味する。元1+tβが与えられているときに逆元(1+tβ)−１の算出は一次合同式(1+tβ)−１(1+tβ)≡１（mod ~d）の解法として古典的知識であるから説明を省略する。
【００５７】
式（３１ｅ）にて、(Ｖ(x)2^(n),SP)(1+tβ)＾(-1)・(-β)は、演算Ｖ(x)2^(n),SPを(1+tβ)-1・(-β)回繰り返すことを意味する。ここで、演算Ｖ(x)2^(n),SPを実現する各演算（図１のＲ2^(n)jおよびcontrolled-Ｒ2^(n)j）が可換であることを考慮すると、Ｖ(x)2^(n),SPを(1+tβ)-1・(-β)回繰り返すことは、図１に示される各演算を(1+tβ)-1・(-β)回繰り返すこと、つまり、図１のＲ2^(n)jおよびcontrolled-Ｒ2^(n)jをＲ2^(n)j・(1+tβ)＾(-1)・(-β)およびcontrolled-Ｒ2^(n)j・(1+tβ)＾(-1)・(-β)に置き換えることと等価である。
【００５８】
式（３１ｅ）にて、(Ｖ(^x)2^(n),SP)(1+tβ)＾(-1)・tは、演算Ｖ(^x)2^(n),SPを(1+tβ)-1・t回繰り返すことを意味する。ここで、演算Ｖ(^x)2^(n),SPを実現する各演算（図１のＲ2^(n)jおよびcontrolled-Ｒ2^(n)j）が可換であることを考慮すると、Ｖ(^x)2^(n),SPを(1+tβ)-1・t回繰り返すことは、図１に示される各演算を(1+tβ)-1・t回繰り返すこと、つまり、図１のＲ2^(n)jおよびcontrolled-Ｒ2^(n)jをＲ2^(n)j・(1+tβ)＾(-1)・tおよびcontrolled-Ｒ2^(n)j・(1+tβ)＾(-1)・tに置き換えることと等価である。
【００５９】
〔装置構成〕
本発明の実施形態に係る量子演算装置１の機能構成図を図３に示す。この装置は、ｍ個の変数（２次関数fの変数）用レジスタと１個の補助レジスタを用いる。各変数用レジスタと補助レジスタはそれぞれｎ個の量子ビットで構成される。従って、使用される量子ビットの数は(m+1)n個である。
【００６０】
まず、初期化部１００が、全ての量子ビットを|0>に初期化する。
【００６１】
次に、アダマール演算部２００が、各変数用レジスタにおいて、各量子ビットにアダマール変換を適用する。アダマール変換は式（３２）で表される単一量子ビットに対する量子操作である。
【数２８】
0005496921.tif 000029
【００６２】
ｍ個の変数用レジスタに含まれるｍｎ個の量子ビットのそれぞれに対するアダマール変換によって、全レジスタに含まれる(m+1)n個の量子ビットの重ね合わせ状態は式（３３）で表される量子状態となる。|xi>は第ｉレジスタの量子状態を表す。
【数２９】
0005496921.tif 000030
【００６３】
次に、オラクル演算部３００が、補助レジスタに対して、２次関数g(x1,x2,…,xm)に関するオラクルを実行し〔式（１８）参照〕、補助レジスタの状態|0>を|g(x1,x2,…,xm)>に変える。既述のとおり、２次関数g(x1,x2,…,xm)に関するオラクルは事前に与えられているものである。２次関数g(x1,x2,…,xm)に関するオラクルを実行したのち、全レジスタに含まれる(m+1)n個の量子ビットの重ね合わせ状態は式（３４）で表される量子状態となる。
【数３０】
0005496921.tif 000031
【００６４】
次に、回転演算部４００が、補助レジスタに対して、式（３５）で表される量子回転操作を実行する。式（３５）で−τ2^(n)はτ2^(n)の複素共役を表す。Ｚ(τ)は式（３６）で定義される。ここで記号"−"は、記号"−"の次の文字の頭上に附されることを意味し、例えば−Ａは文字Ａの頭上に記号"−"が附された組み合わせ文字を表す。式（３５）において、○と×との組合せ記号はテンソル積を表す。
【数３１】
0005496921.tif 000032
【００６５】
量子回転操作を実行したのち、全レジスタに含まれる(m+1)n個の量子ビットの重ね合わせ状態は式（３７）で表わされる量子状態となる。
【数３２】
0005496921.tif 000033
【００６６】
次に、オラクル逆演算部５００が、補助レジスタに対して、オラクル演算部３００が実行したオラクルの逆操作を行い（予め与えられたオラクルを実現する演算を量子回路上で逆順に実行すればよい）、補助レジスタの状態を|0>にする。このため、各変数用レジスタと補助レジスタとのエンタングルメントがなくなるため、補助レジスタを無視してよいことになる。
【００６７】
さらに、ＶF演算部６００が、各変数用レジスタに対して、式（２１）の演算ＶFを実行する。ただし、β-1には各変数用レジスタに対応する２次関数f(x1,x2,…,xm)の係数a1,a2,…,amが入るので、具体的には、ＶF演算部６００は、ｍ個の変数用レジスタに対して式（３８）で表される演算を実行する。
【数３３】
0005496921.tif 000034
【００６８】
所与の２次関数f(x1,x2,…,xm)=a1x12+a2x22+…+amxm2mod 2n+1の係数ai（i=1,2,…,m）の逆元ai-1が奇数であるか偶数であるかは、事前に決定できているので、第ｉ変数用レジスタについて係数ai（i=1,2,…,m）の逆元ai-1が奇数である場合には、ＶF演算部６００は、第ｉ変数用レジスタに対して式（２７）に従ったユニタリ演算を実行する（ただし、β=ai-1である）。このユニタリ演算の量子回路は既に説明したとおりである。第ｉ変数用レジスタについて係数ai（i=1,2,…,m）の逆元ai-1が偶数である場合には、ＶF演算部６００は、第ｉ変数用レジスタに対して、まず式（３１ｅ）に従ったユニタリ演算を実行し、次いで式（３１ｄ）に従ったユニタリ演算を実行する（ただし、β=ai-1である）。式（３１ｅ）に従ったユニタリ演算の量子回路と式（３１ｄ）に従ったユニタリ演算の量子回路は既に説明したとおりである。
【００６９】
つまり、ｍ個の変数用レジスタに対して適用される式（３８）の演算として、ＶF演算部６００は、ｉを１からｍまでの各整数を表すとして、ｉ番目の変数用レジスタについて、２次関数f(x1,x2,…,xm)=a1x12+a2x22+…+amxm2mod 2n+1の係数aiの逆元ai-1が奇数である場合、ｉ番目の変数用レジスタに対して、式（３８ａ）で表される演算を実行し、逆元ai-1が偶数である場合、ｉ番目の変数用レジスタに対して、ｔを「１＋ｔβ≠０且つ１＋ｔβが2n+1と互いに素である」を満たす整数として、式（３８ｂ）で表される演算を実行する。
【数３４】
0005496921.tif 000035
【００７０】
続いて、観測部７００が全ての変数用レジスタを観測することによって、シフト量が得られる。
【００７１】
〔具体例〕
具体例として、f(x1,x2)=x12-3x22mod 22+1, g(x1,x2)=f(x1-2,x2-1)とする。このときg(x1,x2)は、双曲線f(x1,x2)を(2,1)だけ平行移動（シフト）した形状をしている。もし、空間上のシフト量(2,1)を古典計算機によって求める場合には、複数の(x1,x2)に対するg(x1,x2)の値を求め、その結果からシフト量を推定する必要がある。しかし、本発明によると、シフト量(2,1)を以下のようにして求めることができる。
【００７２】
量子演算装置１は、２個の変数用レジスタと１個の補助レジスタを用いる。22+1を法とする剰余を求めるから、各変数用レジスタと補助レジスタはそれぞれ２個の量子ビットで構成される。従って、使用される量子ビットの数は６個である。この具体例の量子回路を図４に示す。図４に示す量子回路にてＨはアダマールゲートを表し、ｇはオラクル演算を表し、ｇ-1はオラクル逆演算を表し、ＶF［1］は第１変数用レジスタに対するＶF演算を表し、ＶF［2］は第２変数用レジスタに対するＶF演算を表す。ＶF演算の詳細な量子回路は式（２７）に従うので、ＶF［1］は例えば図５に示す量子回路で実行され（22+1を法とする1の逆元は1である）、ＶF［2］は例えば図６に示す量子回路で実行される（22+1を法とする-3の逆元は5である）。
【００７３】
まず、初期化部１００が、全ての量子ビットを|0>に初期化する。
【００７４】
そして、アダマール演算部２００が、各変数用レジスタの各量子ビットに対してアダマール変換を適用する。この結果、式（３９）で表される量子状態が得られる。
【数３５】
0005496921.tif 000036
【００７５】
次に、オラクル演算部３００が、２次関数g(x1,x2)のオラクルを実行する。この結果、式（４０）で表される量子状態が得られる。
【数３６】
0005496921.tif 000037
【００７６】
次に、回転演算部４００が、補助レジスタに対して、式（４１）で表される量子回転操作を実行する。この結果、式（４２）で表される量子状態が得られる。
【数３７】
0005496921.tif 000038
【００７７】
次に、オラクル逆演算部５００が、２次関数g(x1,x2)のオラクルを逆順に実行して、補助レジスタの量子状態を|0>にする。この結果、式（４３）で表される量子状態が得られる。第１変数用レジスタ並びに第２変数用レジスタと補助レジスタとの間のエンタングルメントはないので、補助レジスタを無視してよい。g(x1,x2)=(x1-2)2-3(x2-1)2 mod 22+1なので、全変数用レジスタの量子状態を正確に書くと式（４４）である。
【数３８】
0005496921.tif 000039
【００７８】
次に、ＶF演算部６００が、第１変数用レジスタと第２変数用レジスタのそれぞれに対して、式（４５）、式（４６）に対応する拡張Clifford群の変換、つまり、第１変数用レジスタに対して式（４５）に対応する式（２７）のユニタリ演算（つまり式（４５ａ））を実行し、第２変数用レジスタに対して式（４６）に対応する式（２７）のユニタリ演算（つまり式（４６ａ））を実行する。式（２７）のユニタリ演算を実行する理由は、２次関数f(x1,x2)=x12-3x22mod 22+1の係数1，-3の逆元がそれぞれ奇数であるからである。
【数３９】
0005496921.tif 000040
【００７９】
既述のとおり、22+1を法とする-3の逆元は5であるから、式（４６ａ）は式（４６ｂ）のように展開できる。なお、QFT45=QFT4であることは、式（２５）から容易に確認できる。よって、ＶF[1]は図５の量子回路に示す演算系列によって、ＶF[2]は図６の量子回路に示す演算系列によって実行できることが分かる。なお、QFTを実行すると出力の量子ビットxは、^xの順序を逆にしたものとなるため、V(x)2^2,SPおよびV(x)2^2,SP5に対応する量子回路は、図１に示す量子回路の構成と異なる（演算関係を反転したような形となる）ことに注意する。
【数４０】
0005496921.tif 000041
【００８０】
続いて、観測部７００がＶF演算部６００による処理で得られた結果における第１変数用レジスタと第２変数用レジスタを観測する。この観測結果は|2>|1>になる。なぜなら、式（４５）、式（４６）の複素共役転置は式（４７）、式（４８）で表され、式（４７）に状態|2>を、式（４８）に状態|1>を代入すると、第１変数用レジスタは式（４９）で表される量子状態となり、第２変数用レジスタは式（５０）で表される量子状態となり、オラクル逆演算部５００による処理で得られた量子状態〔式（４４）参照〕と一致するからである。
【数４１】
0005496921.tif 000042
【００８１】
〔量子演算装置についての概説〕
次に、上述の量子回路に則って量子演算を行う量子演算装置について説明する。本発明の量子演算装置は、上述の量子回路から明らかなように、アダマール演算部、オラクル演算部、回転演算部、オラクル逆演算部、ＶF演算部を少なくとも含む。各演算部は、基本量子演算部（ＮＯＴ演算部、制御ＮＯＴ演算部、Toffoli演算部）により構成できる（上記非特許文献４参照）。なお、全ての演算は単一量子ビットに対する１量子ビット演算と制御ＮＯＴ演算に分解できる（上記非特許文献４参照）。
【００８２】
量子演算装置は、量子コンピュータ単体で実現できる。量子コンピュータの実現する物理系としては、例えば、イオントラップを用いる方法（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. 方式によってＣＮＯＴ演算を実現する。また、核スピンを量子ビットとして用いる場合には、例えば、所定の電磁波パルスを量子ビットに印加することによってＣＮＯＴ演算を実現できる。
その他、上記の文献に記載された方法でＣＮＯＴ演算を実現してもよい。
【００８６】
＜量子ビット単体操作＞
イオントラップ量子コンピュータでは、例えば、イオンを直線上に並べ、各イオンに狙いを定めたレーザービーム照射によって量子ビット単体の操作を実現する。核スピンを量子ビットとして用いる場合には、電磁波パルスやレーザービーム照射によって各処理を実現する。また、量子ビットとして光子の偏光を用いる場合には、例えば、偏光回転素子等によって実現する。
【００８７】
なお、本発明は既述の実施の形態に限定されるものではなく、その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。例えば、既述の可換な演算については演算の順序に限定がない。また、量子回路に使われる全ての演算は単一量子ビットに対する１量子ビット演算と制御ＮＯＴ演算に分解できるので（上記非特許文献４参照）、各変換部と各演算部の具体的構成についても種々等価な量子回路を構成できる。また、既述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００８８】
ところで、上述の量子回路に則って量子演算を行う手順自体は、古典コンピュータで決定することができる。上述の量子回路に則って量子演算を行う手順は、上述の量子回路を入力側から出力側に向かって順に行う各計算ステップである。
【００８９】
具体的には、例えば図４に示した量子回路の例から明らかなように、初期状態|0>に対する左からの各作用に対応する量子回路を作用の順番に従って量子回路の入力側から出力側に向かって並べることで、量子回路に則って量子演算を行う手順を決定できる。ただし、１計算ステップで並行演算可能であれば、これらの演算を並行するものを１手順とすればよい。換言すれば、この古典コンピュータは、図４に示した演算手順を決定して出力するものといえる。
【００９０】
このような古典コンピュータ、つまり、上述の量子回路における量子演算の手順を決定する量子演算手順決定装置は、いわゆる古典的な装置構成で実現される。例えばパーソナルコンピュータに例示されるように、記憶装置（例えばＲＡＭ、ＲＯＭやハードディスク）、演算処理装置（例えばＣＰＵ）、入力・出力装置（例えばキーボード、ディスプレイ）、これらの装置間でデータのやり取りが可能に接続するバスなどを備えた古典コンピュータによって実現することができる。
【００９１】
この場合、例えば図４の例のように、初期状態|0>に対する左からの各作用に対応する量子回路における量子演算の手順をそれぞれ決定するための各プログラム、決定された手順を上記作用の順番に従って量子回路の入力側から出力側へ並べるためのプログラムを記憶装置に記憶しておき、必要に応じて演算処理装置がプログラムを読み込んで解釈実行することで、初期状態|0>に対する左からの各作用に対応する量子回路における量子演算の手順をそれぞれ決定する各機能、決定された手順を上記作用の順番に従って量子回路の入力側から出力側へ並べる機能を実現する。また各プログラムは、コンピュータ読み取り可能な記録媒体（例えばＣＤ−Ｒ、ＤＶＤ−ＲＡＭ、ＭＯ）に記録することもできる。
【図１】
0005496921.tif 000051
【図２】
0005496921.tif 000052
【図３】
0005496921.tif 000053
【図４】
0005496921.tif 000054
【図５】
0005496921.tif 000055
【図６】
0005496921.tif 000056