(57)【要約】【課題】  与えられたゲノム配列（塩基配列、アミノ酸）に対して最も類似度の高い配列をデータベースから高速に探索できるようにする。【解決手段】  入力配列を配列１とし、データベースから取り出される配列を配列２とする。量子アルゴリズムにより、配列２を重ね合わせ状態とする重ね合わせ処理（ステップ５）と、量子クエリを用い、配列１と重ね合わせ状態にある配列２とに対し、動的計画法に対応する量子演算を行い、配列１と配列２との間のペアワイズアラインメントのスコアを求める処理（ステップ６）と、を実行する。その後、配列２に対し量子オラクルと拡散変換の適用とからなるGroverの反復処理を繰り返し（ステップ７〜１０）、配列２に対応するキュービットを観測して解の候補ｙ’を得る（ステップ１１）。【選択図】        図２
2005078407.tif 000002
【特許請求の範囲】
【請求項１】
配列を格納したデータベース中から、入力配列として与えられたゲノム配列に最も類似した配列を探索するデータ探索方法であって、
前記入力配列を入力配列記憶部から取り出して第１のキュービット列とする段階と、
前記データベースを記憶するデータベース記憶部から配列を取り出して第２のキュービット列とし、前記第２のキュービット列を重ね合わせ状態とする重ね合わせ段階と、
前記第１のキュービット列と前記重ね合わせ状態にある第２のキュービット列に対して動的計画法に対応する量子演算を行い、前記入力配列と前記データベース記憶部から取り出された配列との間のペアワイズアラインメントのスコアを求める量子クエリ段階と、
を有する、データ探索方法。
【請求項２】
前記最も類似した配列に関する候補となる配列をしきい値として、
前記しきい値の初期値を求め、該初期値の配列と前記入力配列との間のペアワイズアラインメントによるスコアを求める段階と、
前記しきい値に対応する配列と前記入力配列との間のペアワイズアラインメントのスコアよりも前記量子クエリ段階で得たスコアの方が大きい配列に対応する第２のキュービット列に対し、量子オラクルと拡散変換を適用する反復演算段階と、
前記反復演算段階を経た第２のキュービット列を観測して解の候補を得る観測段階と、
をさらに有する、請求項１に記載のデータ探索方法。
【請求項３】
前記データベース記憶部中に格納された配列の数をｎとして、前記解の候補に対応するペアワイズアラインメントのスコアが前記しきい値に対応するペアワイズアラインメントのスコアよりも大きければ、前記解の候補で前記しきい値を更新し、そうでなければ、ｎに対してＯ（√ｎ）のオーダーで増加する演算回数だけ前記重ね合わせ段階、前記量子クエリ段階、前記反復演算段階及び前記観測段階を繰り返し、その後に最終的な解の候補を出力配列として出力配列記憶部に格納する、請求項２に記載のデータ探索方法。
【請求項４】
配列を格納したデータベース中から、入力配列として与えられたゲノム配列に最も類似した配列を探索するデータ探索装置であって、
入力された入力配列を記憶する入力配列記憶部と、
出力する出力配列を記憶する出力配列記憶部と、
ゲノム配列のデータベースを保存するデータベース記憶部と、
演算の途中経過を一時的に記憶する入力一時保持記憶部と、
前記入力配列記憶部、前記出力配列記憶部、前記データベース記憶部及び前記入力一時保持記憶部との間で情報の書き込み・読み出しを行うとともに量子アルゴリズムによる演算を行う演算部と、を備え、
前記演算部は、前記入力配列を入力配列記憶部から取り出して第１のキュービット列とする処理と、前記データベース記憶部から配列を取り出して第２のキュービット列とし、前記第２のキュービット列を重ね合わせ状態とする重ね合わせ処理と、前記第１のキュービット列と前記重ね合わせ状態にある第２のキュービット列に対して動的計画法に対応する量子演算を行い、前記入力配列と前記データベース記憶部から取り出された配列との間のペアワイズアラインメントのスコアを求める量子クエリ処理と、を実行する、
データ探索装置。
【請求項５】
前記最も類似した配列に関する候補となる配列をしきい値として、前記演算部は、さらに、前記しきい値の初期値を求め、該初期値の配列と前記入力配列との間のペアワイズアラインメントのスコアを求める処理と、前記量子クエリ処理の実行後、前記しきい値に対応する配列と前記入力配列との間のペアワイズアラインメントのスコアよりも前記量子クエリ段階で得たスコアの方が大きい配列に対応する第２のキュービット列に対し、量子オラクルと拡散変換を適用する反復演算処理と、前記反復演算処理を経た第２のキュービット列を観測して解の候補を得る観測処理と、を実行する、請求項４に記載のデータ探索装置。
【請求項６】
前記データベース記憶部中に格納された配列の数をｎとして、前記演算部は、前記解の候補に対応するペアワイズアラインメントのスコアが前記しきい値に対応するペアワイズアラインメントのスコアよりも大きければ、前記解の候補で前記しきい値を更新し、そうでなければ、ｎに対してＯ（√ｎ）のオーダーで増加する演算回数だけ、前記重ね合わせ処理、前記量子クエリ処理、前記反復演算処理及び前記観測処理を繰り返し、その後、最終的な解の候補を出力配列として前記出力配列記憶部に格納する、請求項５に記載のデータ探索装置。
【請求項７】
コンピュータに、
入力配列を入力配列記憶部から取り出して第１のキュービット列とする処理、
配列を記憶したデータベースを記憶するデータベース記憶部から配列を取り出して第２のキュービット列とし、前記第２のキュービット列を重ね合わせ状態とする重ね合わせ処理、
前記第１のキュービット列と前記重ね合わせ状態にある第２のキュービット列に対して動的計画法に対応する量子演算を行い、前記入力配列と前記データベース記憶部から取り出された配列との間のペアワイズアラインメントのスコアを求める量子クエリ処理、
を実行させる、データ探索プログラム。
【請求項８】
前記最も類似した配列の候補となる配列をしきい値として、コンピュータに、
前記しきい値の初期値を求め、該初期値の配列と前記入力配列との間のペアワイズアラインメントのスコアを求める処理、
前記しきい値に対応する配列と前記入力配列との間のペアワイズアラインメントのスコアよりも前記量子クエリ段階で得たスコアの方が大きい配列に対応する第２のキュービット列に対し、量子オラクルと拡散変換を適用する反復演算処理、
前記反復演算処理を経た第２のキュービット列を観測して解の候補を得る観測処理、
をさらに実行させる、請求項７に記載のデータ探索プログラム。
【請求項９】
前記データベース記憶部中に格納された配列の数をｎとして、コンピュータに、
前記解の候補に対応するペアワイズアラインメントのスコアが前記しきい値に対応するペアワイズアラインメントのスコアよりも大きければ、前記解の候補で前記しきい値を更新し、そうでなければ、ｎに対してＯ（√ｎ）のオーダーで増加する演算回数だけ、前記重ね合わせ処理、前記量子クエリ処理、前記反復演算処理及び前記観測処理を繰り返し、その後、最終的な解の候補を出力配列として出力配列記憶部に格納する処理をさらに実行させる、請求項８に記載のデータ探索プログラム。
【請求項１０】
コンピュータが読み取り可能な記録媒体であって、請求項７乃至９のいずれか１項に記載のデータ探索プログラムを記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、量子コンピュータを用いてあるいは量子アルゴリズムを適用して、与えられたゲノム配列（塩基配列、アミノ酸配列）と最も類似度が高い配列をデータベースから探索する方法及び装置に関する。
【背景技術】
【０００２】
生物学に情報科学を応用したバイオインフォマティクスの分野においては、生物が持つＤＮＡやＲＮＡにおける塩基配列や、タンパク質やペプチドにおけるアミノ酸配列などの解読が急速に進められている。本明細書では、塩基配列やアミノ酸配列を総称してゲノム配列と呼んでいる。解読された配列はデータベースに蓄積されている。そして、多数の配列の中で類似度の高い配列を発見することで、生物の新しい機能や進化の系統を解明することが可能になり、また、創薬や遺伝子治療に有効な知見を得ることができる。
【０００３】
しかしながら、精度の高い類似度の計算を行うことは、大量の計算時間とメモリ空間とを要してコストが高くなるので、現実的ではない。そこで、近似的な計算方法を用いたアルゴリズムによって配列間の類似度を計算する手法が主流となってきている。
【非特許文献１】S. B. Needleman and C. D. Wunsch, Journal of Molecular Biology, Vol. 48, pp. 443-453 (1970)
【非特許文献２】L. Grover, 28th Annual ACM Symposium on the Theory of Computing, pp. 212-219 (1996)
【非特許文献３】M Boyer, G. Brassard, P. Hoyer and A. Tapp, 4th Workshop on Physics and Computation, pp. 36-43 (1996)
【非特許文献４】C. Durr and P. Hoyer, "A quantum algorithm for finding the minimum," [online], 1999年1月7日、［2003年8月27日検索］、インターネット<URL: http://arXiv.org/abs/quant-ph/9607014>
【発明の開示】
【発明が解決しようとする課題】
【０００４】
現在、ゲノム配列の解読が急激に進んでおり、データベースに蓄積されるデータ量も膨大になっている。データベースに蓄積されている配列の数をｎとすると、現在使用されている類似度計算アルゴリズムによる計算量はＯ（ｎ）の程度であるが、データベースに蓄積されるデータ量すなわちｎが加速度的に増大しているため、配列の類似度の算出のための計算量が膨張しつつある。配列間の類似性に基づいて配列の特徴や機能の解明をより高速に行うために、データベースを効率的に探索するアルゴリズムの開発が急務の課題となっている。
【０００５】
２個の配列の間の類似性は、一般に、ペアワイズアラインメント(pair-wise alignment)という手続きを経て計算されており、類似性が高いほどそのスコアも高くなる。一般に、ペアワイズアラインメントの計算では、ＤＰ（動的計画法）が用いられている（非特許文献１参照）。しかし、信頼性の高いＤＰの計算には、多くの計算量を必要とする。このため、実際には近似計算によって計算速度の向上を図ることが多いが、精度が劣るといった問題点がある。
【０００６】
そこで本発明の目的は、与えられたゲノム配列に対して最も類似度の高い配列をデータベースから高速に探索するためのデータ探索方法及び装置を提供することにある。
【課題を解決するための手段】
【０００７】
現在広く利用されているコンピュータに比べ、原理的にはるかに高速に問題を解くことができる「量子コンピュータ」と呼ばれるコンピュータが提案されている。量子コンピュータは、量子力学で記述される物理現象に特有な現象である量子重ね合わせ状態を利用する。量子コンピュータの実現には、量子重ね合わせ状態を保持したまま演算を実行するキュービットと呼ばれる素子を使用する。量子コンピュータは、因数分解などの問題に対して現在のコンピュータ（古典的計算機）よりはるかに高速に計算を行うことができるため、世界中の多くの研究機関が開発が進められている。
【０００８】
本発明は、量子コンピュータの計算原理を用いたアルゴリズム（非特許文献２〜４参照）を利用して、ＤＰを用いた最適なペアワイズアラインメントのスコアを、従来のコンピュータよりも効率的に求めようとするものである。したがって、ゲノム配列のデータベースの中から、入力として与えられた配列と最も類似度が高いゲノム配列を発見することができる。ここで類似度とは、ペアワイズアラインメントのスコアである。
【０００９】
すなわち本発明のデータ探索方法は、配列を格納したデータベース中から、入力配列として与えられたゲノム配列に最も類似した配列を探索するデータ探索方法であって、入力配列を入力配列記憶部から取り出して第１のキュービット列とする段階と、データベースを記憶するデータベース記憶部から配列を取り出して第２のキュービット列とし、第２のキュービット列を重ね合わせ状態とする重ね合わせ段階と、第１のキュービット列と重ね合わせ状態にある第２のキュービット列に対して動的計画法に対応する量子演算を行い、入力配列とデータベース記憶部から取り出された配列との間のペアワイズアラインメントのスコアを求める量子クエリ段階と、を有する。
【００１０】
本発明のデータ探索装置は、配列を格納したデータベース中から、入力配列として与えられたゲノム配列に最も類似した配列を探索するデータ探索装置であって、入力された入力配列を記憶する入力配列記憶部と、出力する出力配列を記憶する出力配列記憶部と、ゲノム配列のデータベースを保存するデータベース記憶部と、演算の途中経過を一時的に記憶する入力一時保持記憶部と、入力配列記憶部、出力配列記憶部及び入力一時保持記憶部との間で情報の書き込み・読み出しを行うとともに量子アルゴリズムによる演算を行う演算部と、を備え、演算部は、入力配列を入力配列記憶部から取り出して第１のキュービット列とする処理と、データベース記憶部から配列を取り出して第２のキュービット列とし、第２のキュービット列を重ね合わせ状態とする重ね合わせ処理と、第１のキュービット列と重ね合わせ状態にある第２のキュービット列に対して動的計画法に対応する量子演算を行い、入力配列とデータベース記憶部から取り出された配列との間のペアワイズアラインメントのスコアを求める量子クエリ処理と、を実行する。
【発明の効果】
【００１１】
本発明は、量子アルゴリズムを使用することにより、膨大の数の配列が保存されているデータベースから、入力されたゲノム配列と最も類似度が高い配列を、従来のコンピュータすなわち古典的計算機を用いた場合よりも効率的に発見することができるという効果がある。本発明を用いた場合のその計算速度は、データベース中の配列数の増加率をｎとしたとき、従来のコンピュータよりも√ｎ倍高速になり、また計算空間のコストは、ｌｏｇ（ｎ）に圧縮される。例えば、データベース中の配列数が１００個から１００００個に増えたとき、すなわち、ｎ＝１００のとき、従来のコンピュータでは、配列数が１００個のときに必要なものの１００倍の計算時間とメモリ空間とを必要とする。しかし本発明によれば、１０倍の計算時間とｌｏｇ（１００）すなわち２ｌｏｇ2（１０）倍のメモリ空間を用意するだけでよい。したがって本発明によれば、従来のものと比べ、データベース中の配列数が多くなるほど、アルゴリズムの実行効率が飛躍的に増大する。
【発明を実施するための最良の形態】
【００１２】
次に、本発明の実施の形態について、図面を参照して説明する。
【００１３】
図１は、本発明の実施の一形態のデータ探索装置の構成を示すブロック図である。このデータ探索装置１００は、塩基配列やアミノ酸配列などのゲノム配列における類似度の計算を量子アルゴリズムに従って実行する量子コンピュータとして構成されており、キュービットを用いて計算を行う演算部１１０と、記憶部１２０とを備えている。記憶部１２０には、入力された入力配列を記憶する入力配列記憶部１２１と、出力する出力配列を記憶する出力配列記憶部１２２と、最も類似度が高い配列を探索するための量子アルゴリズムを記憶するアルゴリズム記憶部１２３と、ゲノム配列のデータベースを保存するデータベース記憶部１２４と、計算の過程を一時的に記憶する入力一時保持記憶部１２５とが設けられている。ここで入力配列は、量子アルゴリズムを実行するときに入力として与えられる配列であり、出力配列は、量子アルゴリズムの実行が終了したときに得られる配列である。演算部１１０は、入力配列記憶部１２１、出力配列記憶部１２２、データベース記憶部１２４及び入力一時保持記憶部１２５との間で情報の書き込み・読み出しを行い、アルゴリズム記憶部１２３に記憶された量子アルゴリズムにしたがって量子演算を行う。
【００１４】
このデータ探索装置１００では、入力配列が入力されると、それは入力配列記憶部１２１に格納される。また、ゲノム配列のデータベースは予めデータベース記憶部１２４に格納され、最も類似度が高い配列を探索するアルゴリズムはアルゴリズム記憶部１２３に格納されている。次に、出力配列記憶部１２２と入力一時保持記憶部１２５が初期化される。その後、量子アルゴリズムに応じて、演算部１１０で量子演算処理が繰り返される。この間、入力一時保持記憶部１２５は、演算のステップごとにその内容が更新される。最後に、出力配列記憶部１２２の内容が計算結果として出力される。その結果、このデータ探索装置１００では、入力された１個の配列に最も類似した配列がデータベース中から検索されて出力されることになる。
【００１５】
以下、本実施形態において用いる量子アルゴリズムについて、詳細に説明する。
【００１６】
まず、量子アルゴリズムを定義する。
【００１７】
量子アルゴリズム：
チューリングマシンによって数学的モデルが与えられる計算機であって、典型的にはノイマン型コンピュータである計算機のことを古典的計算機と呼ぶことにする。古典的計算機におけるビットに相当する量子コンピュータにおける概念は、キュービット(qubit)と呼ばれる。各キュービットは、古典的計算機における“１”，“０”、またはそれを拡張した（“１”と“０”の重ね合わせに相当する）ビット情報を保有する。量子コンピュータは、有限個のキュービットで構成される。「量子コンピュータで計算を行う」とは、各キュービットに初期値を与え、それらに操作を施してキュービットが保有するビット情報を操作し、最後に観測を行ってこれらのビット情報を取り出すことを意味する。キュービット上に施されるビット情報の一連の操作のことを、量子アルゴリズムと呼ぶ。キュービットに施される操作の基本単位を定めれば、量子アルゴリズムは、この基本操作の列によって記述される。
【００１８】
次に、本実施の形態において用いられるデータベースを定義する。
【００１９】
入力配列（配列１とする）をα、データベース中の配列（配列２とする）をαiとする。データベースには、配列αiが、ｎ個、すなわち、α1、α2、…、αnまで格納されているとする。配列１、２は、いずれも、ｉｎｄｅｘ（インデックス）とｉｎｄｅｘでラベルがつけられたｔａｂｌｅ（テーブル：配列の実体）とから構成されている。ｉｎｄｅｘは、データベース中の配列番号を意味する変数ｉ（１≦ｉ≦ｎ）によって区別され、ｔａｂｌｅは、コード化された配列αiを保存している。コード化とは、配列を構成する塩基あるいはアミノ酸の種類を番号で区別したものを、“０”と“１”の数字の列で表現することと定義する。
【００２０】
次に、類似度を求めるための本実施形態におけるＤＰ（動的計画法）のアルゴリズムを説明する。
【００２１】
１個の配列１が入力配列として与えられてそれが入力配列記憶部１２１に格納され、また、データベース記憶部１２４に記憶されたデータベースには配列２があるとして、配列１と配列２の間の類似度の算出を説明することとする。ここでは、配列１、２は塩基配列であるとするが、アミノ酸配列である場合も全く同様の手順が採用される。配列１を構成する塩基の数をｐ個、配列２を構成する塩基の数をｑ個とするとき、配列１は、ｘ1，…，ｘa，…，ｘp、配列２はｙi1，…，ｙib，…，ｙiqと表す。ａは、ａ番目の塩基を指定する変数であり、ｉｂはｉ番目の配列のｂ番目の塩基を指定する変数である。何番目の塩基であるかは、一般には、配列のＮ末端側から数えられる。アミノ酸配列の場合であれば、何番目のアミノ酸であるかは、一般には、配列の５’末端側から数えられる。
【００２２】
まず、配列１の塩基を行列の行番号に、配列２の塩基を列番号にした行列を考える。この行列の各要素のことをセルと呼ぶこととし、１個のセル(ｘa，ｙb)に、１個のアラインメントのスコアｆi(ａ，ｂ)を保持する。
【００２３】
ｆi(ａ，ｂ)は、
ｆi(ａ，ｂ)＝ｍａｘ（ｆi(ａ−１，ｂ−１)＋ｓ(ａ，ｂｉ)，ｆi(ａ−１，ｂ)−ｄ，ｆi(ａ，ｂ−１)−ｄ）                            …(1)
と表される。ここでｍａｘ（Ａ，Ｂ，Ｃ）とは、Ａ，Ｂ，Ｃの中から最も大きい値を採用する意味の記号である。ｓ(ａ，ｂｉ)は、配列１のｘaと配列２のｙibとの置換行列を用いたときの置換スコアであり、ｄは、配列に欠失や挿入が生じたときのギャップスコアである。置換行列は、２個の塩基またはアミノ酸の尤度の組み合わせを表にしたものであって、いくつかのものが知られている。後述する具体例では、置換行列として、ＢＬＯＳＵＭ５０を用いている。
【００２４】
このときのセルは、(０，０)から(ｐ，ｑ)まで存在し、行番号あるいは列番号に０が含まれる場合は、境界条件として、
ｆi(０，０)＝０，
ｆi(０，ｂ)＝−ｂｄ，
ｆi(ａ，０)＝−ａｄ
と定められている。このような境界条件を用いて(1)式を適用することにより、(１，１)から(ｐ，ｑ)までの各セルのスコアを計算することができ、最終的にｆi(ｐ，ｑ)を計算できる。このスコアｆi(ｐ，ｑ)が、配列１と配列２との間の類似度を示すペアワイズアラインメントのスコアＳ(α，αi)となる。
【００２５】
上述したＤＰのアルゴリズムは、それ自体では量子アルゴリズムの適用を前提としたものではなく、古典的計算機上で通常に実行されるアルゴリズムである。次に、上述したＤＰアルゴリズムを実行するための量子アルゴリズムの手順について説明する。図２はここで用いる量子アルゴリズムを示すフローチャートである。
【００２６】
ステップ１．しきい値ｙのｉｎｄｅｘ及びλの設定：
入力配列として配列１が入力して入力行列記憶部１２１に格納され、まず、ステップ１において、しきい値の初期値のｉｎｄｅｘを１からｎ以下の整数から無作為に選んだ整数ｙとする。ここで、ｎはデータベース中の配列の数である。また、ｍの増加分を決める定数であるλを６／５とする。しきい値とは、解（配列２の中で、配列１に対して最も類似度が高い配列）の候補となるものである。以下の説明から明らかなようにこの実施形態では、しきい値に対するペアワイズアラインメントのスコアより大きなスコアが得られた場合に、しきい値のｉｎｄｅｘであるｙを更新することによってしきい値を更新し、このような処理を繰り返すことによって、最終的な解を得るようにしている。以下の説明では、ｉｎｄｅｘがｙであるしきい値のことをしきい値ｙと表現している。
【００２７】
ステップ２．しきい値のｔａｂｌｅ及びｍの設定：
ステップ１の実行後、ステップ２では、ステップ１で選んだしきい値ｙのｉｎｄｅｘと対応するように、ｔａｂｌｅを設定する。アルゴリズムが繰り返される回数を定めるｍを、初期値として、ｍ＝１と設定する。
【００２８】
ステップ３．ペアワイズアラインメントスコアＳ(α，αy)の計算：
ステップ２の実行後、ステップ３では、しきい値ｙのｔａｂｌｅに対応するペアワイズアラインメントスコアＳ(α，αy)を古典的計算機を用いて計算する。しきい値ｙに対応するペアワイズアラインメントスコアＳ(α，αy)は、量子アルゴリズムによって得られる解の候補を評価する際に必要であるから、ここでは古典的計算機で事前に計算しているが、もちろん、量子アルゴリズムを用いて計算してもよい。ペアワイズアラインメントスコアＳ(α，αy)を求めるためのアルゴリズムとしては、上述したＤＰのアルゴリズムを適用することができる。
【００２９】
ステップ４．ｍより小さく、かつ負でない整数ｊの無作為選択：
ステップ３の実行後、ステップ４では、ｍより小さく、かつ負でない整数ｊを無作為に選択する。ｊは、後述するステップ７と８を繰り返すために設定される変数である。
【００３０】
ステップ５．配列２のｉｎｄｅｘに対するWalsh-Hadamard変換Ｈの適用：
ステップ４の実行後、ステップ５では、データベース記憶部１２４内の配列２に対し、演算部１１０が、Walsh-Hadamard（ウォルシュ−アダマール）変換Ｈを適用する。このとき、配列２は、キュービット列として表されている。Walsh-Hadamard変換Ｈとは、１個のキュービットに対する変換行列Ｈが、
【００３１】
【数１】
2005078407.tif 000003
【００３２】
と表される変換である。入力０に対しては、０と１が等しい振幅の重ね合わせ状態を出力し、入力１に対しては０と１が符号のみ異なる等しい振幅の重ね合わせ状態を出力する。振幅とは、キュービットを観測したときに０または１を得るそれぞれの確率の平方根であって、一般に、複素数で表される。
【００３３】
ステップ６．量子クエリ（量子query）を用いたＳ(α，αi)の計算：
ステップ５の実行後、ステップ６では、量子クエリを用いて、配列１及び配列２の間の類似度のスコアＳ(α，αi)を求める。ここでは量子クエリとは、両方またはどちらか一方が重ね合わせ状態にある２個の配列のＤＰ計算を行い、ペアワイズアラインメントのスコアを求める量子演算と定義する。
【００３４】
図３は、スコアＳ(α，αi)を求めるための量子クエリを示している。ここでは、量子クエリを表す量子アルゴリズムは、量子レジスタなどの意味を持つキュービットの集合と、それに対する関数からなる。左から時系列に量子演算がキュービットに適用される。この図において、１本の横線は複数のキュービットを指し、四角形は、それと重なっている横線（標的キュービット）に対する関数である。関数と縦線で繋がれている黒い丸は、関数を実行するときに必要な制御キュービットを指定している。ここで示した量子演算は、演算部１１０で行われる。配列１（配列α）のｉｎｄｅｘとｔａｂｌｅ（すなわちｘ1，…，ｘa，…，ｘp）は、入力行列記憶部１２１から演算部１１０にキュービット列として供給され、配列２（配列αi）のｉｎｄｅｘとｔａｂｌｅ（すなわちｙi1，…，ｙib，…，ｙiq）は、データベース記憶部１２４からキュービット列として演算部１１０に供給される。置換行列は、量子演算に用いるパラメータとして、アルゴリズム記憶部１２３から演算部１１０にキュービットとして与えられる。演算の途中結果であるｆi(０，０)からｆi(ｐ，ｑ)までは、入力一時保持記憶部１２５に格納されることになる。
【００３５】
ステップ７．配列２のｉｎｄｅｘへの量子オラクルの適用：
ステップ６の実行後、ステップ７では、演算部１１０は、配列２のｉｎｄｅｘに対して量子オラクルを適用する。量子オラクル(oracle)とは、０と１のキュービット列で表された入力に対して、０または１、または０と１の重ね合わせ状態を出力する関数である。この関数によって、重ね合わせ状態の配列２のｉｎｄｅｘのうち、設定された条件を満たすｉｎｄｅｘの符号のみが反転される。
【００３６】
ステップ８．配列２のｉｎｄｅｘへの拡散変換の適用：
ステップ７の実行後、ステップ８では、演算部１１０は、配列２のｉｎｄｅｘに拡散変換を適用する。拡散変換Ｄは、ｎ次の正方行列であって、その対角成分は、いずれも−１＋（２／ｎ）であり、その他の成分はいずれも２／ｎである。
【００３７】
ステップ９．ｊのデクリメント：
ステップ８の実行後、ステップ９では、ｊから１を引く。上述したステップ７、８の処理は、Grover（グローバー）の反復演算(iteration)であり、ここでｊから１を引くことにより、ステップ４で定めたｊの回数だけ、この反復演算が繰り返されるようにしている。この反復演算の結果、より高いスコアを持つｉｎｄｅｘとその他のｉｎｄｅｘとの振幅の差が拡大する。
【００３８】
ステップ１０．条件分岐：
ステップ９の実行後、ステップ１０においてはｊの値を評価し、ｊが正ならばステップ１１に進み、そうでなければステップ７へ戻る。
【００３９】
ステップ１１．配列２の観測：
ステップ１１では、配列２のｉｎｄｅｘを観測し、解の候補となるｙ’とαy'とＳ(α，αy')を得る。
【００４０】
ステップ１２．アルゴリズムの実行ステップ数の確認：
ステップ１１の実行後、ステップ１２において、ステップ７、８で実行した合計ステップ数Ｔを求め、このＴがＯ(√ｎ)に満たないときは、次のステップ１３へ進む。そうでなければ、このときのｙを解として出力し、アルゴリズムを終了する。ここでの合計ステップ数Ｔの数え方は、１個のキュービットに対する１回の演算を１ステップとする。Ｏ(√ｎ)とは、たかだか、√ｎの次数を持つ多項式のことである。本発明によれば、量子アルゴリズムを用いることにより、配列数がｎであるデータベース中から最も類似度の高い配列を探索するための計算量をＯ(√ｎ)の程度とすることができる。具体的にどの値をもってここでのアルゴリズムの終了条件とするかは、用いられる量子コンピュータの実装に依存する。
【００４１】
ステップ１３．条件分岐：
ステップ１３では、Ｓ(α，αy')−Ｓ(α，αy)の値を評価し、この値が正であればステップ１４へ進み、そうでなければステップ１５へ進む。ここでの評価は、ステップ１１で得られた解の候補ｙ’に対応するスコアＳ(α，αy')が、現時点でのしきい値ｙに対応するスコアＳ(α，αy)を上回っているかを判断するものである。解の候補ｙ’の方が大きなスコアを示すとき、すなわち類似度が高い場合には、しきい値ｙをｙ’に置き換えるために、ステップ１４に進むことになる。
【００４２】
ステップ１４．しきい値の更新：
ステップ１４では、しきい値ｙをｙ’に書き換えて、ステップ２へ戻る。
【００４３】
ステップ１５．ｍの更新：
ステップ１５では、ｍにλｍと√ｎのうちの小さい方の値を代入することによってｍを更新し、ステップ４に戻る。
【００４４】
以上の量子アルゴリズムが終了したら、最大値の候補となるしきい値のｉｎｄｅｘ及びｔａｂｌｅを出力行列記憶部１２２に格納することによって出力する。
【００４５】
図４は、上述した量子アルゴリズムにおいて、各配列、各変数などについてどのような処理が行われるかを時系列に示したものである。ここでも、量子アルゴリズムは、量子レジスタなどの意味を持つキュービットの集合とそれに対する関数から構成されている。図において、１本の横線は複数のキュービットを指し、四角形は、それと重なっている横線（標的キュービット）に対する関数である。関数と縦線で繋がれている黒い丸は、関数を実行するときに必要な制御キュービットを指定している。また、図中の「ｗｏｒｋ  ｓｐａｃｅ」（作業空間）は、演算途中で一時的に使用する補助的なキュービットである。
【００４６】
《計算の具体例》
以下、本実施形態に基づく具体的な計算例を説明する。ここでは、ゲノム配列をアミノ酸配列として、類似度が最も高い配列を発見することとする。また、類似度の計算には、ＢＬＯＳＵＭ５０という置換行列を用いる。入力として与えられた配列の数は１個、データベース中の配列数ｎは４、各アミノ酸配列が持つアミノ酸数を３個とする。ｎを表現するのに２キュービット、アミノ酸の種類は２０種類なので、１個のアミノ酸配列を表現するためには１５キュービットが必要である。また、ギャップスコアを−８とする、入力として与えられた配列αは“ＡＲＮ”、データベース中の配列は、それぞれ、（ｉｎｄｅｘ，ｔａｂｌｅ）＝｛（ｉ，αi）｜（１，ＡＬＫ），（２，ＡＮＱ），（３，ＡＰＮ），（４，ＴＷＹ）｝であるとする。ここでは、２０種類のアミノ酸をそれぞれ、アルファベットの大文字１文字からなる略号で表しており、ここに記載された範囲では、Ａはアラニン、Ｒはアルギニン、Ｎはアスパラギン、Ｌはロイシン、Ｋはリジン、Ｑはグルタミン、Ｐはプロリン、Ｔはトレオニン、Ｗはトリプトファン、Ｙはチロシンである。これらのアミノ酸は、キュービットとして、Ａ＝“０００００”、Ｒ＝“００００１”、Ｎ＝“０００１０”、…、Ｖ＝“１００１１”のように、０と１の数字の列に置き換えられる。もちろん、入力がこの例に限られるわけではない。
【００４７】
以下に示すものは、この例において、類似度が最も高い配列を出力するための計算過程を、図２に示したフローチャートにおける各ステップに対応させて示したものである。
【００４８】
ステップ１．  しきい値をｙ＝２、λ＝５／６に設定する。
ステップ２．  αy＝ＡＮＱ、ｍ＝１に設定する。
ステップ３．  アラインメントのスコアは、Ｓ(α，αy)＝４となる。
ステップ４．  ｊ＝１とする。
ステップ５．  配列２のｉｎｄｅｘに、Walsh-Hadamard変換を適用する。このときの量子状態は、１／２｛（１，ＡＬＫ，０）＋（２，ＡＮＱ，０）＋（３，ＡＰＮ，０）＋（４，ＴＷＹ，０）｝となる。量子状態の表記は、１個の量子状態（ｉｎｄｅｘ，ｔａｂｌｅ，スコア）が｛｝の中で重ね合わせの状態になっているものとする。
ステップ６．  Ｓ(α，αi)を求めたときの量子状態は、１／２｛（１，ＡＬＫ，２）＋（２，ＡＮＱ，４）＋（３，ＡＰＮ，９）＋（４，ＴＷＹ，−５）｝である。
ステップ７．  量子オラクルを用いて、Ｓ(α，αi)＞Ｓ(α，αy)を満たすｉｎｄｅｘの係数のみを反転する。このときの量子状態は、１／２｛（１，ＡＬＫ，２）＋（２，ＡＮＱ，４）−（３，ＡＰＮ，９）＋（４，ＴＷＹ，−５）｝になる。
ステップ８．  配列２のｉｎｄｅｘに拡散変換を適用する。このときの量子状態は｛（３，ＡＰＮ，９）｝である。
ステップ９．  ｊ＝０となる。
ステップ１０．  ｊ≦０なので、ステップ１１に進む。
ステップ１１．  配列２のｉｎｄｅｘを観測し、（３，ＡＰＮ，９）を得る。
ステップ１２．  ステップ７と８の合計ステップ数がＯ(√ｎ)に達していなければ、ステップ１３へ進む。
ステップ１３．  Ｓ(α，αy')−Ｓ(α，αy)＝９−４＞０なので、ステップ１４へ進む。
ステップ１４．  ｙ＝３に更新する。
ステップ１５．  ｍ＝６／５に更新して、ステップ４へ戻る。
【００４９】
以上のようにして各ステップが実行された後、ｙ＝３、αy＝ＡＰＮを出力し、アルゴリズムを終了する。
【００５０】
ここでは、ゲノム配列がアミノ酸配列である場合の具体例を説明したが、ゲノム配列が塩基配列の場合にも、同様の手順で処理される。ただし、塩基配列の場合には塩基は４種類しかないので、１個の塩基を記述するのに２キュービットが必要である。
【００５１】
以上、本発明の好ましい実施形態について説明した。上述したデータ探索装置は、専用のハードウェアとしての量子コンピュータにより実行されるほか、その機能を実現するためのプログラムを、コンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行するものであってもよい。古典的計算機であっても、演算時間はかかるものの、量子アルゴリズムの検証やシミュレーションを行うことは可能であるから、古典的計算機であるコンピュータシステムにそのようなプログラムを実行させて、上述したようなデータ探索を行ってもよい。
【００５２】
コンピュータ読み取り可能な記録媒体とは、フレキシブルディスク（ＦＤ）、光磁気ディスク（ＭＯ）、ＣＤ−ＲＯＭ等の記録媒体、コンピュータシステムに内蔵されるハードディスク装置などの記憶装置を指す。さらに、コンピュータ読み取り可能な記録媒体は、インターネットなどのネットワークを介してプログラムを送信する場合のように、短時間の間、動的にプログラムを保持するもの（伝送媒体もしくは伝送波）、その場合のサーバとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含んでいる。
【図面の簡単な説明】
【００５３】
【図１】本発明の実施の一形態のデータ探索装置のブロック図である。
【図２】本発明に基づくデータ探索方法のアルゴリズムを示すフローチャートである。
【図３】量子アルゴリズムとして示した量子クエリを説明する図である。
【図４】量子アルゴリズムを構成する量子演算を時系列に表現した図である。
【符号の説明】
【００５４】
１〜１５    ステップ
１００    データ探索装置
１１０    演算部
１２０    記憶部
１２１    入力配列記憶部
１２２    出力配列記憶部
１２３    アルゴリズム記憶部
１２４    データベース記憶部
１２５    入力一時保持記憶部
【図１】
2005078407.tif 000004
【図２】
2005078407.tif 000005
【図３】
2005078407.tif 000006
【図４】
2005078407.tif 000007