(57)【要約】【課題】  相互の情報提供を最小限に抑えつつ、データ提供者が、サンプリング者が必要とする属性の情報のみを提供する。【解決手段】  データ提供装置１０において、第１,第２キュービット列の組を複数生成し、第１キュービット列を各要素データの重ね合わせ状態とし、第２キュービット列を対応する各属性データの重ね合わせ状態とする。この際、第１,第２キュービット列は、この対応に応じた絡み合いの状態となる。そして、第２キュービット列のみをサンプリング装置３０に送信する。  サンプリング装置３０は、第２キュービット列を観測し、サンプリング対象の属性データに縮退した第２キュービット列を、サンプリング情報によって特定される数だけ選択する。そして、この選択内容を示す要求サンプル情報をデータ提供装置１０に送信する。  データ提供装置１０は、この要求サンプル情報に対応する第１キュービット列を返し、サンプリング装置３０は、それを観測する。  【選択図】        図１
2005242625.tif 000002
【特許請求の範囲】
【請求項１】
データを提供するデータ提供装置と、当該データ提供装置からデータを取得するサンプリング装置と、を有するサンプル抽出システムであって、
前記データ提供装置は、
複数の要素データを格納する要素集合記憶部と、
属性設定情報（要素データを示す量子状態から、それに対応する属性データの量子状態を生成するための情報）を格納する属性設定情報記憶部と、
第１キュービット列とそれに対応する第２キュービット列とからなる第３キュービット列を、複数生成するキュービット生成部と、
前記第１キュービット列の量子状態を、前記要素集合記憶部に格納された前記要素データの重ね合わせ状態とする要素量子化部と、
前記属性設定情報を用い、前記第２キュービット列の量子状態を、前記第１キュービット列が示す前記要素データに対応する前記属性データの重ね合わせ状態とし、前記第３キュービット列ごとに、当該第１キュービット列と第２キュービット列とを、当該要素データと属性データの対応に応じた絡み合いの状態とする属性量子化部と、
前記第２キュービット列と絡み合いの状態となった前記第１キュービット列を格納する量子記憶部と、
前記属性データの重ね合わせ状態となった前記第２キュービット列を出力する第１量子出力部と、
を有し、
前記サンプリング装置は、
サンプリング情報（属性データから、それに対応する要素データの取得数を特定するための情報）を格納するサンプリング情報記憶部と、
前記第２キュービット列の入力を受け付ける第１量子入力部と、
前記第２キュービット列を観測する第１観測部と、
属性データごとに、前記サンプリング情報によって特定される要素データの取得数分だけ、前記第１観測部における観測値が当該属性データとなった前記第２キュービット列を選択するキュービット列選択部と、
前記キュービット列選択部において選択された前記第２キュービット列と絡み合いの状態にある前記第１キュービット列を特定する要求サンプル情報を出力する古典出力部と、
を有し、
前記データ提供装置は、
前記要求サンプル情報の入力を受け付ける古典入力部と、
前記要求サンプル情報によって特定される前記第１キュービット列を、前記量子記憶部から選択する検索部と、
選択された前記第１キュービット列を出力する第２量子出力部と、
をさらに有し、
前記サンプリング装置は、
前記第１キュービット列の入力を受け付ける第２量子入力部を、
さらに有する、
ことを特徴とするサンプル抽出システム。
【請求項２】
データを提供するデータ提供装置であって、
複数の要素データを格納する要素集合記憶部と、
属性設定情報（要素データを示す量子状態から、それに対応する属性データの量子状態を生成するための情報）を格納する属性設定情報記憶部と、
第１キュービット列とそれに対応する第２キュービット列とからなる第３キュービット列を、複数生成するキュービット生成部と、
前記第１キュービット列の量子状態を、前記要素集合記憶部に格納された前記要素データの重ね合わせ状態とする要素量子化部と、
前記属性設定情報を用い、前記第２キュービット列の量子状態を、前記第１キュービット列が示す前記要素データに対応する前記属性データの重ね合わせ状態とし、前記第３キュービット列ごとに、当該第１キュービット列と第２キュービット列とを、当該要素データと属性データの対応に応じた絡み合いの状態とする属性量子化部と、
前記第２キュービット列と絡み合いの状態となった前記第１キュービット列を格納する量子記憶部と、
前記属性データの重ね合わせ状態となった前記第２キュービット列を出力する第１量子出力部と、
前記第２キュービット列がサンプリング装置において観測された後、当該サンプリング装置から送られた要求サンプル情報の入力を受け付ける古典入力部と、
前記要求サンプル情報によって特定される前記第１キュービット列を、前記量子記憶部から選択する検索部と、
選択された前記第１キュービット列を出力する第２量子出力部と、
を有することを特徴とするデータ提供装置。
【請求項３】
請求項２記載のデータ提供装置であって、
前記属性設定情報は、
前記要素データを変数ｘとし、それに対応する前記属性データをｙとした場合において、ｙ＝ｆ（ｘ）を満たす関数である、
ことを特徴とするデータ提供装置。
【請求項４】
請求項２或いは３記載のデータ提供装置であって、
前記要素データの集合は、
前記第１キュービット列ごとのキュービット数をｎとした場合における、０以上２ｎ−１以下の整数全体である、
ことを特徴とするデータ提供装置。
【請求項５】
請求項４記載のデータ提供装置であって、
前記要素量子化部は、
入力された各キュービットの量子状態に対してウォルシューアダマール（Walsh-Hadamard）変換を作用させる素子を、ｎ個並列に配列して構成される、
ことを特徴とするデータ提供装置。
【請求項６】
データ提供装置からデータを取得するサンプリング装置であって、
サンプリング情報（属性データから、それに対応する要素データの取得数を特定するための情報）を格納するサンプリング情報記憶部と、
データ提供装置から送られた第２キュービット列の入力を受け付ける第１量子入力部と、
前記第２キュービット列を観測する第１観測部と、
属性データごとに、前記サンプリング情報によって特定される要素データの取得数分だけ、前記第１観測部における観測値が当該属性データとなった前記第２キュービット列を選択するキュービット列選択部と、
前記キュービット列選択部において選択された前記第２キュービット列と絡み合いの状態にある前記第１キュービット列を特定する要求サンプル情報を出力する古典出力部と、
前記データ提供装置から送られた第１キュービット列の入力を受け付ける第２量子入力部を、
有することを特徴とするサンプリング装置。
【請求項７】
請求項６記載のサンプリング装置であって、
前記サンプリング情報は、
前記属性データを変数ｙとし、前記属性データに対応する要素データの取得数をｚとした場合において、ｚ＝α（ｙ）を満たす関数である、
ことを特徴とするサンプリング装置。
【請求項８】
請求項２から５のいずれかに記載のデータ提供装置の制御に必要な処理をコンピュータに実行させるためのプログラム。
【請求項９】
請求項６或いは７記載のサンプリング装置の制御に必要な処理をコンピュータに実行させるためのプログラム。
【請求項１０】
請求項８記載のプログラムを格納したコンピュータ読み取り可能な記録媒体。
【請求項１１】
請求項９記載のプログラムを格納したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、量子計算の応用技術に関し、特に、量子計算をデータベースからのデータ提供に適用したサンプル抽出システム、データ提供装置、サンプリング装置、それらのプログラム及び記録媒体に関する。
【背景技術】
【０００２】
情報を多数保有する者（データ提供者）が、その情報を第三者（サンプリング者）に提供する場合がある（例えば、非特許文献１参照。）。例えば、業者Ａが多数の個人情報を保有しており、この個人情報を、適切な範囲内で広告代理店Ｂに提供するような場合である。
通常、情報提供を受けようとするサンプリング者は、データ提供者が保有する全情報が必要なわけではなく、特定の属性の情報のみを必要としている場合が多い。例えば、上述の業者Ａと広告代理店Ｂの関係の場合、広告代理店Ｂが、所定の属性（性別、年齢、職業、趣味等）の個人情報（氏名、住所、電話番号等）のみ（例えば、２０代女性の住所のみ）を取得し、その統計的データを抽出しようとする場合等である。
【０００３】
一般に、サンプリング者が所定の属性に関する情報のみを取得しようとする場合、まず、このサンプリング者は、どのような属性の情報が必要であるか（サンプル基準）をデータ提供者に伝え、この要求を受けたデータ提供者は、この要求に合致する情報のみをサンプリング者に提供する。
【非特許文献１】“ＤＴＲ（ディスクトップリサーチ）”、［online］、［平成１６年２月２４日検索］、インターネット＜URL：http://www.info-plant.com/＞
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかし、従来、互いに相手に与える情報を最小限に抑えつつ、データ提供者が、サンプリング者が必要とする属性の情報のみを提供することはできなかった。
例えば、個人情報を多数保有する業者Aと広告代理店Bがあって、広告代理店Bが業者Aと契約し、業者Aのもつ個人情報リストから、特定の属性の統計的データのみを抽出したいと考えたとする。そして、業者Aは、必要以上の個人情報を開示することなく、広告代理店Bが必要とする属性の個人情報のみを提供したいと考えているとする。また、広告代理店Bは、企業戦略を秘密にするため、どのような属性の統計的データを取得しようとしているのかを業者Aに開示することなく、情報のサンプリングを行いたいと考えているものとする。
【０００５】
ここで、従来方法のように、広告代理店Bがサンプル基準を業者Aに開示し、業者Aがこのサンプル基準に従って情報を提供するとする。この場合、業者Aは個人情報データベースの全容を開示する必要はないが、広告代理店Bの戦略が業者Ａに漏洩してしまう。
逆に、広告代理店Bの戦略の漏洩を防ぐためには、広告代理店Bは、業者Aが保有する個人情報を（不要な属性の情報も含め）大量に購入しなければならず、業者Aは、必要以上の個人情報を開示しなければならない。
このような問題は、通常の商取引に限らず、情報を交換し合う参加者同士の間で利害が対立し、互いに相手に与える情報を最小限に抑えようとする状況下で同様に想定しうる。
【０００６】
本発明はこのような点に鑑みてなされたものであり、互いに相手に与える情報を最小限に抑えつつ、データ提供者が、サンプリング者が必要とする属性の情報のみを提供できるサンプル抽出システムを提供することである。
また、本発明の他の目的は、相互の情報提供を最小限に抑えつつ、データ提供者が、サンプリング者が必要とする属性の情報のみを提供できるデータ提供装置を提供することである。
さらに、本発明の他の目的は、相互の情報提供を最小限に抑えつつ、データ提供者が、サンプリング者が必要とする属性の情報のみを提供できるサンプリング装置を提供することである。
【課題を解決するための手段】
【０００７】
本発明では、データ提供装置がサンプリング装置にデータを提供する。
まず、前処理として、データ提供装置において、複数の要素データと、属性設定情報（要素データを示す量子状態から、それに対応する属性データの量子状態を生成するための情報）を格納する。また、サンプリング装置において、サンプリング情報（属性データから、それに対応する要素データの取得数を特定するための情報）を格納する。
次に、データ提供装置において、第１キュービット列とそれに対応する第２キュービット列とからなる第３キュービット列を複数生成し、これらの第１キュービット列の量子状態を、要素集合記憶部に格納された要素データの重ね合わせ状態（後述）とする。
【０００８】
その後、属性設定情報を用い、データ提供装置において、これらの第２キュービット列の量子状態を、第１キュービット列が示す要素データに対応する属性データの重ね合わせ状態とする。この際、第１キュービット列と第２キュービット列は、第３キュービット列ごとに、当該要素データと属性データの対応に応じた絡み合いの状態（後述）となる。すなわち、各第３キュービット列内で閉じた絡み合い状態となる。
データ提供装置は、これら第２キュービット列と絡み合いの状態となった第１キュービット列を格納し、属性データの重ね合わせ状態となった第２キュービット列を出力する。
サンプリング装置は、これらの第２キュービット列の入力を受け付け、これらを観測する。これにより、各第２キュービット列は、何れかの属性データを示す量子状態に縮退し、各第２キュービット列と絡み合いの状態にある各第１キュービット列も、この属性データに対応する要素データを示す量子状態にそれぞれ縮退（後述）する。ただし、データ提供装置は、格納する各第１キュービット列がどの量子状態に縮退しているかを知ることはできない。
【０００９】
次に、サンプリング装置は、属性データごとに、サンプリング情報によって特定される要素データの取得数分だけ、第１観測部における観測値が当該属性データとなった第２キュービット列を選択する。すなわち、サンプリングをしようとしている属性データの量子状態に縮退している第２キュービット列を、サンプリング情報によって特定される数だけ特定する。
その後、サンプリング装置は、選択した第２キュービット列と絡み合いの状態にある第１キュービット列を特定する要求サンプル情報を出力する。なお、前述のように、絡み合いの状態にある各第１キュービット列と第２キュービット列の組みの量子状態は、ある要素データとそれに対応する属性データに縮退している。したがって、サンプリング情報に従って選択した第２キュービット列と絡み合いの状態にある第１キュービット列は、サンプリング対象の属性データに対応する要素データに縮退している。つまり、この要求サンプル情報は、取得しようとする要素データに縮退した第１キュービット列を特定する情報である。
【００１０】
データ提供装置は、この要求サンプル情報の入力を受け付け、それによって特定される第１キュービット列を量子記憶部から選択し、出力する。
サンプリング装置は、この第１キュービット列の入力を受け付け、それを観測する。これにより、サンプリング装置は、必要な要素データを取得したことになる。
【発明の効果】
【００１１】
以上のように、サンプリング装置において各第２キュービット列が観測された際、各第２キュービット列は何れかの属性データを示す量子状態に縮退し、これらと絡み合いの状態にある各第１キュービット列も対応する要素データを示す量子状態に縮退する。しかし、データ提供装置は、各第１キュービット列がどの要素データを示す量子状態に縮退しているか分からない。よって、サンプリング装置が、要求サンプル情報によって、必要な要素データを示す量子状態に縮退した第１キュービット列を指定しても、データ提供装置側では、要求された第１キュービット列がどの要素データに対応しているか分からない。従って、要求サンプル情報に応じ、データ提供装置が第１キュービット列をサンプリング装置に送っても、このデータ提供装置は、どの要素データをデータ提供装置に提供したことになるか分からない。その結果、サンプリング装置は、どのような属性データに対応する要素データを集めているかをデータ提供装置に知られることなく、必要な要素データのみを取得することができる。
【００１２】
また、データ提供装置も、保有する全ての要素データをサンプリング装置に提供する必要がない。
以上より、本発明では、データ提供者及びサンプリング者が互いに相手に与える情報を最小限に抑えつつ、データ提供者が、サンプリング者が必要とする属性の情報のみを提供できる。
【発明を実施するための最良の形態】
【００１３】
以下、この発明の実施の形態を図面を参照して説明する。
〔原理〕
まず、本形態の原理について説明する。
＜量子情報技術＞
近年、従来の情報理論では解決が難しかった問題を、微細な世界に適用される物理法則である量子力学の原理を応用して解決する技術（量子情報技術）が注目を集めている。例えば、量子コンピュータは、量子力学の世界特有の現象である重ね合わせ状態を利用し、複数の演算を並列的に実行することができる（量子並列性）。そして、この量子並列性及び観測による状態の縮退により、量子コンピュータは、因数分解などの問題に対し、現在のコンピュータよりはるかに高速に計算が可能であることが示唆されている。
【００１４】
以下では、まず、この量子情報技術における基本的な概念について説明する。
＜重ね合わせ状態＞
「重ね合わせ状態」とは、古典的計算機（チューリングマシンにより数学的モデルが与えられる計算機であって、典型的にはノイマン型コンピュータである計算機）が取りうる全ての状態の線形結合で表現される状態を意味する。例えば、量子コンピュータでは、光子等の粒子の量子的な状態（光子の偏光方向等）をビットに対応させて演算を行うが、量子力学上、これら２以上の量子的な状態（量子状態）は、粒子が観測されるまで、重ね合わせの状態にある。例えば、光子は垂直偏光と水平偏光の重ね合わせ状態にある。
また、重ね合わせ状態にある１つのキュービット（qubit: quantumbit）の量子状態φ（状態ベクトル）は以下のように表される。
φ=c1|0>+c2|1>  （c12+c22=1）  …(1)
【００１５】
ここで、｜０＞は、ビット“０”に対応する量子状態（例えば垂直偏光）を意味し、｜１＞は、ビット“１”に対応する量子状態（例えば水平偏光）を意味する。また、ｃ１，ｃ２は、各量子状態の係数であり、これを「振幅」と呼ぶ。なお、一般に、「振幅」は複素数で表される。
なお、「キュービット」とは、この様な複数の状態の任意の重ね合わせを保持できるビットを意味する。すなわち、古典的計算機における「ビット」に相当する量子コンピュータ上の概念が「キュービット」である。
【００１６】
＜縮退＞
「縮退」とは、複数の量子状態の重ね合わせ状態が、それ以下の数の量子状態の重ね合わせ状態となること、或いは、いずれか一つの量子状態となることをいう。例えば、式（１）で示されるキュービットを観測すると、その重ね合わせ状態はいずれか１つの状態に縮退する。例えば、垂直偏光と水平偏光の重ね合わせ状態にあった光子は、観測によって、水平偏光あるいは垂直偏光のいずれか一方の状態となる。この際、ある状態が得られる確率は、その状態に係る「振幅」の２乗で表される。すなわち、式（１）の量子状態の場合、観測によって｜０＞に縮退する確率はｃ１２であり、｜１＞に縮退する確率はｃ２２である。
【００１７】
＜絡み合いの状態（エンタングルメント状態）＞
「絡み合いの状態」とは、２以上のキュービットが量子力学特有の相関を持ち、一方のキュービットの量子状態が決まると、瞬時にもう一方のキュービットの量子状態が決まる関係を意味する。例えば、あるキュービットが観測され、その量子状態が縮退すると、それと絡み合いの状態にある他のキュービットもその影響を受ける。
＜量子アルゴリズム＞
前述のように、各キュービットは、古典的計算機における“１”、“０”、またはそれを拡張した（“１”と“０”の重ね合わせに相当する）ビット情報を保有する。また、量子コンピュータは有限個のキュービットで構成される。そして、「量子コンピュータで計算を行う」とは、各キュービットに初期値を与え、それらに操作を施してキュービットが保有するビット情報を操作し、最後に観測を行ってこれらのビット情報を取り出すことを意味する。そして、このキュービット上に施されるビット情報の一連の操作のことを「量子アルゴリズム」と呼ぶ。キュービットに施される操作の基本単位を定めれば、量子アルゴリズムはこの基本操作の列により記述される。
【００１８】
本形態は、以上のような量子コンピュータの計算原理を用いたアルゴリズム（例えば、「P. Shor, Physical Review A, 52:2493 (1995).」、「B. Rylander, T. Soule, J. Foster and J. Alves-Foss, Proc. of Genetic and Evolutionary Computation Conference, pp. 1005-1011 (2001).」参照。）の思想に基づき、先にあげた課題を解決するものである。以下、本形態の概要について説明する。
＜概要＞
・  まず、データ提供者Ａは、“０”の状態（初期化された状態）の第１キュービット列及び第２キュービット列を複数組（ｓ組（ｓは２以上の整数））用意する。このとき、それぞれのキュービット列の組（第３キュービット列＝第１キュービット列＋第２キュービット列）には１,２,…,ｓの番号（キュービット列番号）がふられているものとする。なお、「キュービット列」とは、複数のキュービットの集合を意味する。また「列」という表現を用いているが、これは便宜上の表現であって、各キュービットの位置関係を示すものではない。
・  次に、データ提供者Aは、データベースの内容である要素データを各第１キュービット列上に重ね合わせ状態として作成する。なお、「要素データ」とは、データベースを構成するキー情報を意味し、例えば、個人情報のデータベースであれば、氏名、住所、電話番号等が該当する。
・  その後、データ提供者Aは、属性設定情報（属性関数）ｆを用い、第１キュービット列の量子状態から第２キュービット列の量子状態を生成し、両方のキュービット列を３キュービット列ごとに絡み合いの状態とする。そのため、この処理により、第２キュービット列の量子状態は、各要素データに対応する属性データの重ね合わせ状態となっている。なお、こうした操作は、ｓ回繰り返される。ここで、「属性設定情報」とは、データベースが有する要素データを示す量子状態から、それに対応する属性データの量子状態を生成するための情報を意味し、例えば、要素データを変数ｘとし、それに対応する属性データをｙとした場合において、ｙ＝ｆ（ｘ）を満たす関数（属性関数ｆ）である。また、「属性データ」とは、各要素データに対応する属性を示すデータであり、例えば、個人情報のデータベースであれば、各氏名（要素データ）に対応する年齢、性別、趣味等が該当する。
【００１９】
・  データ提供者Aは、ｓ個の第１キュービット列部分を保存し、さらにｓ個の第２キュービット列部分をサンプリング者Bに送信する。
・  サンプリング者Bは、送られてきた各第２キュービット列を観測する。これにより、各第２キュービット列の量子状態は、それぞれいずれかの属性データを示す量子状態に縮退し、サンプリング者Bは、縮退した属性データを得る。また、この第２キュービット列と絡み合いにある第１キュービット列は、この縮退した属性データに対応する要素データを示す量子状態に縮退する。
・  サンプリング者Bは、各属性データにサンプリング情報（サンプリング関数）αを適用し、各属性データに対応する要素データのサンプル数（取得数）を求める。ここで「サンプリング情報」とは、属性データから、それに対応する要素データの取得数を特定するための情報を意味し、例えば、属性データを変数ｙ（属性関数ｆの値域）とし、それに対応する要素データの取得数をｚ（非負整数値）とした場合において、ｚ＝α（ｙ）を満たす関数（サンプリング関数α）である。すなわち、サンプリング情報αは、例えば、「趣味がサッカー」「趣味が野球」「趣味がつり」という３つの属性データに対し、「趣味がサッカー」である人の要素データ取得数、「趣味が野球」である人の要素データ取得数、及び「趣味がつり」である人の要素データ取得数を与えるものである。
【００２０】
・  次に、サンプリング者Bは、属性データごとに、観測値が当該属性データとなった第２キュービット列を、求めたサンプル数分だけ選択する。具体的には、例えば、属性データごとに、該当する第２キュービット列に対応するキュービット列番号（１,２,…,ｓ）を選択する。このように選択されたキュービット列番号は、データ提供者Aに送られる。
・  データ提供者Aは、受け取ったキュービット列番号に対応する第１キュービット列をサンプリング者Bに送信する。
・  サンプリング者Bは、送信された第１キュービット列を観測することにより、必要とする属性データに対応する要素データ（例えば、趣味が野球（属性データ）である人の電話番号（要素データ））を必要数（サンプル数）分だけ取得できる。
【００２１】
〔詳細〕
次に、本形態の詳細について説明する。
＜全体構成＞
図１は、本形態におけるサンプル抽出システム１の構成を例示したブロック図である。
図１に例示するように、本形態のサンプル抽出システム１は、データを提供するデータ提供装置１０、及び当該データ提供装置１０からデータを取得するサンプリング装置３０を有しており、これらは量子通信路４０及び古典通信路５０によって、それぞれ情報通信可能なように接続されている。
【００２２】
ここで量子通信路４０とは、量子情報の伝達が可能な通信路を意味する。例えば、光子をキュービットとして使用する場合には、光ファイバ等がこの量子通信路４０に該当する。また、古典通信路５０とは、通常のビットデータを伝送する通信路を意味する。例えば、電話回線やインターネット等のアナログ、デジタル通信路がこの古典通信路５０に該当する。
また、図１における実線の矢印は量子情報の流れを示し、１点鎖線の矢印は古典情報の流れを示す（後述する図５、図９、図１５においても同様。）。ここで、「量子情報」とは、“０”と“１”のみならず“０”と“１”の任意の重ね合わせ状態を取ることができるような量子力学的な状態で表される情報を意味する。また、「古典情報」とは、“０”と“１”からなる２進数の「ビット」を基本単位とするような古典力学的な状態で表される情報を意味する。
【００２３】
＜データ提供装置＞
図１に例示するように、本形態のデータ提供装置１０は、各種演算を量子アルゴリズムに従って実行する量子コンピュータであり、インタフェース部１１、要素集合記憶部１２、属性設定情報記憶部１３、パラメータ記憶部１４、キュービット生成部１５、要素量子化部１６、属性量子化部１７、量子記憶部１８、量子出力部１９、古典入力部２０、検索部２１、制御部２２及びプログラムメモリ２３を有している。
ここで、キュービット生成部１５、要素量子化部１６、属性量子化部１７、量子記憶部１８、量子出力部１９及び検索部２１は、量子情報を取り扱う装置であり、インタフェース部１１、要素集合記憶部１２、属性設定情報記憶部１３、パラメータ記憶部１４、古典入力部２０、制御部２２及びプログラムメモリ２３は、古典情報のみを取り扱う装置である。なお、ハードウェアの具体例については後述する。また、データ提供装置１０の制御処理は、プログラムメモリ２３に格納されたプログラムを制御部２２において実行させることにより実現される。なお、制御部２２の制御処理に係る古典情報の流れは図示していない。
【００２４】
＜サンプリング装置＞
図１に例示するように、本形態のサンプリング装置３０は、インタフェース部３１、サンプリング情報記憶部３２、量子入力部３３、観測部３４、キュービット列選択部３５、古典出力部３６、制御部３７及びプログラムメモリ３８を有している。
ここで、量子入力部３３及び観測部３４は、量子情報を取り扱う装置であり、インタフェース部３１、サンプリング情報記憶部３２、キュービット列選択部３５、古典出力部３６、制御部３７及びプログラムメモリ３８は、古典情報のみを取り扱う装置である。なお、ハードウェアの具体例については後述する。また、サンプリング装置３０の制御処理は、プログラムメモリ３８に格納されたプログラムを制御部３７において実行させることにより実現される。なお、制御部３７の制御処理に係る古典情報の流れは図示していない。
【００２５】
＜処理動作＞
次に、本形態におけるサンプル抽出システム１の処理動作について説明する。
＜前処理＞
まず、データ提供装置１０のインタフェース部１１において、要素の集合Ｘ、属性設定情報ｆ及び正整数のパラメータｍ，ｎ，ｓの入力を受け付け、要素の集合Ｘを要素集合記憶部１２に格納し、属性設定情報ｆを属性設定情報記憶部１３に格納し、パラメータｍ，ｎ，ｓをパラメータ記憶部１４に格納する。
ここで、要素の集合Ｘとは、データ提供装置１０が提供するデータベースを構成する複数の要素データｘの集合を意味する。なお、この例の要素データｘは、０≦ｘ≦２ｎ−１（１０進数表記）の範囲にある整数である。
図２は、要素集合記憶部１２に格納された要素データｘを例示した概念図である。ここで、（ａ）は、要素データ（ｘ）１２ａの集合が０≦ｘ≦２ｎ−１（１０進数表記）の整数全体である場合の例であり、（ｂ）は、要素データ（ｘ）１２ｂの集合が０≦ｘ≦２ｎ−１（１０進数表記）の離散値の集合である場合の例である。なお、図２では、２進数で要素データｘの値を示している。
【００２６】
＜サンプル抽出処理＞
次に、本形態におけるサンプル抽出処理について説明する。
図３は、本形態におけるサンプル抽出処理（量子アルゴリズム）を説明するためのフローチャートである。以下、このフローチャートに従い、本形態におけるサンプル抽出処理について説明する。
［ステップＳ１］
まず、データ提供装置１０の制御部２２において、カウント値ｉに１を代入する。
［ステップＳ２］
次に、データ提供装置１０のキュービット生成部１５において、パラメータ記憶部１４からパラメータｍ，ｎ，ｓを取得し、第１キュービット列（ｎ個のキュービットからなるキュービット列）と第２キュービット列（ｍ個のキュービットからなるキュービット列）からなる第３キュービット列（「第１キュービット列とそれに対応する第２キュービット列とからなる第３キュービット列」に相当）を、複数（ｓ列）生成する。すなわち、キュービット生成部１５において、（ｎ＋ｍ）×ｓ個のキュービットを生成し、これらを第１キュービット列と第２キュービット列からなる第３キュービット列ごとに分ける。そして、キュービット生成部１５は、全てのキュービットを“０”に初期化する。なお、この初期化はキュービット列の生成と同時に行われることとしてもよい。
【００２７】
図４は、このように生成されたキュービット列を説明するための概念図である。
図４に例示するように、生成されたキュービット列は、ａｊ１,ａｊ２,ａｊ３,…,ａｊｎ（ｊ∈（１,２,３,…,ｓ））のｎ個のキュービット１０１からなる第１キュービット列（ａ）１００と、ｂｊ１,ｂｊ２,ｂｊ３,…,ｂｊｍのｍ個のキュービット２０１からなる第２キュービット列（ｂ）２００とを有している。そして、これら第１キュービット列（ａ）１００と第２キュービット列（ｂ）２００により、ｊ列目（ｊ∈（１,２,３,…,ｓ））の第３キュービット列（ａ,ｂ）３００を構成している。なお、図４は各キュービット間の位置関係を示すものではない（後述の図５〜図１１も同様）。
【００２８】
［ステップＳ３］
次に、要素量子化部１６において、キュービット生成部１５からｉ列目（ｉ∈（１,２,３,…,ｓ））の第３キュービット列（ａ,ｂ）３００を取得し、要素集合記憶部１２から全要素データｘを取得する。そして、要素量子化部１６は、取得した第３キュービット列（ａ,ｂ）３００を構成する第１キュービット列（ａ）１００の量子状態を、取得した全要素データｘの重ね合わせ状態とする。すなわち、要素量子化部１６は、第１キュービット列（ａ）１００の量子操作を行い、その量子状態を、要素の集合Xの要素全体を表現する数の重ね合わせ状態にする。
【００２９】
図５は、この要素量子化部１６における機能構成を概念的に例示した図である。
図５に例示するように、要素量子化部１６は、量子操作制御部１６ａと量子操作部１６ｂを有している。量子操作制御部１６ａは、要素集合記憶部１２から抽出した全要素データｘ（要素の集合X）に基づき量子操作部１６ｂを制御する。また、量子操作部１６ｂには、量子状態が｜０＞であるｎ個のキュービット（ａｊ１,ａｊ２,ａｊ３,…,ａｊｎ）１０１からなる第１キュービット列（ａ）１００が入力される。そして、量子操作部１６ｂは、量子操作制御部１６ａからの制御に基づき、この第１キュービット列（ａ）１００の量子状態を全要素データｘの重ね合わせ状態とする（キュービット（ａｊ１’,ａｊ２’,ａｊ３’,…,ａｊｎ’）からなる第１キュービット列（ａ’）１００）。なお、量子状態が｜０＞であるｍ個のキュービット（ｂｊ１,ａｊ２,ｂｊ３,…,ｂｊｍ）２０１からなる第２キュービット列（ｂ）２００は、そのまま出力される。
【００３０】
｛ステップＳ３の具体例１｝
図６は、要素データｘの集合が、０以上２ｎ−１以下（１０進数表記）の整数全体である場合（図２の（ａ）に示した要素データ（ｘ）１２ａ）における、量子操作部１６ｂの量子操作を例示したブロック図である。
この場合、量子操作部１６ｂは、入力された各キュービット（ａｊ１,ａｊ２,ａｊ３,…,ａｊｎ）１０１−１〜ｎの量子状態に対してウォルシューアダマール（Walsh-Hadamard）変換を作用させる素子（ウォルシューアダマール変換部（Ｈ）１６ｂａ）を、ｎ個並列に配列した量子回路を構成する。
【００３１】
ここで使用する「Walsh-Hadamard変換H」とは、１個のキュービットに対する変換行列Hが、
【数１】
2005242625.tif 000003
と表されるユニタリ変換である。すなわち、１個のキュービットの量子状態が
φ=c1|0>+c2|1>  （c12+c22=1）
である場合、このキュービットにWalsh-Hadamard変換Hを施すと、その量子状態φ’は、
φ’=c3|0>+c4|1>  （c32+c42=1）
【数２】
2005242625.tif 000004
となる。すなわち、入力｜０＞に対しては（ｃ１＝１、ｃ２＝０）、｜０＞と｜１＞の振幅が等しい重ね合わせ状態（ｃ３＝ｃ４＝１／√２）を出力し、入力｜１＞に対しては（ｃ１＝０、ｃ２＝１）、｜０＞と｜１＞の振幅の絶対値が等しく符号が異なる重ね合わせ状態（ｃ３＝１／√２、ｃ４＝−１／√２）を出力する。
【００３２】
図６の各ウォルシューアダマール変換部（Ｈ）１６ｂａに、量子状態｜０＞のキュービット（ａｊ１,ａｊ２,ａｊ３,…,ａｊｎ）１０１−１〜ｎがそれぞれ入力された場合、各ウォルシューアダマール変換部（Ｈ）１６ｂａは、各キュービット（ａｊ１,ａｊ２,ａｊ３,…,ａｊｎ）１０１−１〜ｎの量子状態を１／√２（｜０＞＋｜１＞）と変換する。従って、この変換後のキュービット（ａｊ１’,ａｊ２’,ａｊ３’,…,ａｊｎ’）１０１−１〜ｎからなる第１キュービット列（ａ’）１００の量子状態φ’は、１／√２（｜０＞＋｜１＞）・１／√２（｜０＞＋｜１＞）・・・１／√２（｜０＞＋｜１＞）の２項展開、すなわち、
φ’=1/√(2n)(｜000…000＞+｜000…001＞＋｜000…010＞＋…＋｜111…111＞)
となる。これは、変換後の第１キュービット列（ａ’）１００の量子状態φ’が、図２の（ａ）に示した要素データ（ｘ）１２ａの全要素の重ね合わせ状態となっていることを意味している。このように、要素データｘの集合が、０以上２ｎ−１以下（１０進数表記）の整数全体である場合、Walsh-Hadamard変換Hを適用することにより、容易にそれらの重ね合わせ状態を作成できる。
【００３３】
図７は、この重ね合わせ状態を概念的に示した図である。
図７に例示するように、変換後の第１キュービット列（ａ’）１００を構成する各キュービット（ａｊ１’）１０１−ｋ（ｋ∈（１,２,…,ｎ））の量子状態は、要素データｘ＝(０００…０００)２, (０００…００１)２,…,(１１１…１１１)２のそれぞれ先頭からｋ番目のビットに対応する量子状態の重ね合わせ状態となっている。
｛ステップＳ３の具体例２｝
図８は、ｎ＝３で、要素データｘの集合が(０００)２,(０１０)２, (１１０)２, (１１１)２である場合（離散的な整数である場合）における、量子操作部１６ｂの量子操作を例示したブロック図である。
【００３４】
この場合、量子操作部１６ｂは、入力された量子状態に対し、ウォルシューアダマール変換を行って出力するウォルシューアダマール変換部（Ｈ）１６ｂｂと、Ｒｘ（π）の回転変換を行って出力する回転部１６ｂｃ,１６ｂｄと、Ｒｙ（π／２）の回転変換を行って出力する回転部１６ｂｅ,１６ｂｇと、Ｒｚ（π）の回転変換を行って出力する回転部１６ｂｆ,１６ｂｈと、制御ＮＯＴ（ＣＮＯＴ）演算を行うＣＮＯＴ部１６ｂｉ,１６ｂｊ,１６ｂｋ,１６ｂｍ,１６ｂｎを構成する。
【００３５】
ここで、Ｒｘ（θ）,Ｒｙ（θ）,Ｒｚ（θ）はそれぞれ以下のような変換を意味する。
【数３】
2005242625.tif 000005
すなわち、例えば、量子状態φ=c1|0>+c2|1>に対し、Ｒｘ（π）の回転変換を行うと、その量子状態φ’は、
φ’=c3|0>+c4|1>  （c32+c42=1）
【数４】
2005242625.tif 000006
となる。
【００３６】
なお、「ｉ」は虚数単位を意味し、「ｅ」は自然対数の底を示している。また、ウォルシューアダマール変換Ｈは、H≡Ｒｚ（π）・Ｒｙ（π／２）によって構成できる。なお、量子力学上、ある量子状態に絶対値１の複素数をかけたものは、全て同じ量子状態を示している（例えば「M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Chapter 7 Physical Realization, pp.15」参照。）。
第１キュービット列（ａ）１００（φ＝｜０００＞）を構成するキュービット（ａｊ１：φ＝｜０＞）１０１−１は、ウォルシューアダマール変換部（Ｈ）１６ｂｂに入力し、キュービット（ａｊ２：φ＝｜０＞）１０１−２は、ＣＮＯＴ部１６ｂｉの目標（ターゲット）ビットとなり、キュービット（ａｊ３：φ＝｜０＞）１０１−３は、ＣＮＯＴ部１６ｂｋの目標ビットとなる。
【００３７】
ウォルシューアダマール変換部（Ｈ）１６ｂｂの出力キュービットは、ＣＮＯＴ部１６ｂｉの制御（コントロール）ビットとして機能した後、回転部１６ｂｃに入力し、回転部１６ｂｃの出力キュービットは、ＣＮＯＴ部１６ｂｊ,１６ｂｆの制御ビットとして機能した後、回転部１６ｂｄに入力する。そして、回転部１６ｂｄの出力キュービットは、ＣＮＯＴ部１６ｂｋ,１６ｂｍの制御ビットとして機能した後、出力される（キュービットａｊ１’)。
ＣＮＯＴ部１６ｂｉの出力キュービットは、ＣＮＯＴ部１６ｂｊの目標ビットとなり、ＣＮＯＴ部１６ｂｊの出力キュービットは、回転部１６ｂｅに入力する。回転部１６ｂｅの出力キュービットは、ＣＮＯＴ部１６ｂｎの目標ビットとなり、ＣＮＯＴ部１６ｂｎの出力キュービットは、回転部１６ｂｆに入力し、その出力キュービットがキュービットａｊ２’として出力される。
ＣＮＯＴ部１６ｂｋの出力キュービットは、回転部１６ｂｇに入力し、その出力キービットは、ＣＮＯＴ部１６ｂｍの目標ビットとなる。また、ＣＮＯＴ部１６ｂｍの出力キュービットは、回転部１６ｂｈに入力し、その出力キュービットがキュービットａｊ３’として出力される。
【００３８】
そして、このように出力されたキュービット（ａｊ１’, ａｊ２’, ａｊ３’）からなる第１キュービット列の量子状態φ’は、
φ’≡1/2(|000>+|010>+|110>+|111>)
となっている。これは、要素データｘの集合(０００)２,(０１０)２, (１１０)２, (１１１)２の重ね合わせ状態を示している。なお、この量子状態φ’の「振幅」は１／２とはならないが、前述のように、量子力学上、ある量子状態に絶対値１の複素数をかけたものは、全て同じ量子状態を示している。つまり、この量子状態φ’は、「振幅」が１／２の量子状態と等しい。
なお、ここで例示した要素データｘ以外の重ね合わせ状態も、１つのキュービットに対する回転変換と、２つのキュービットに対する制御ＮＯＴ操作を組み合わせることにより実現できることが知られている（例えば「Barenco, Bennett, Cleve, DiVincenzo, Margolus, Shor, Sleater, Smolin, Weinfurter, Elementary gates for quantum computation, Physical Review A 52:3457-3467, 1995」参照。）。
【００３９】
［ステップＳ４］
ステップＳ３の後、要素量子化部１６は、要素データの重ね合わせ状態とした第１キュービット列（ａ’）１００と、何ら操作していない第２キュービット列（ｂ）２００と、からなる第３キュービット列（ａ’,ｂ）３００を属性量子化部１７に送る。属性量子化部１７は、属性設定情報記憶部１３から属性設定情報ｆを抽出し、第２キュービット列（ｂ）２００の量子状態を、第１キュービット列（ａ’）１００の量子状態の属性設定情報ｆによる写像を示す量子状態に変換する。すなわち、属性設定情報ｆを用い、第２キュービット列（ｂ）２００の量子状態を、第１キュービット列（ａ’）１００が示す要素データｘに対応する属性データｙの重ね合わせ状態とする（第２キュービット列（ｂ’）２００）。また、この操作により、第１キュービット列（ａ’）１００と第２キュービット列（ｂ’）２００を、第３キュービット列（ａ’,ｂ’）３００ごとに、各要素データｘと各属性データｙの対応に応じた絡み合いの状態とする。すなわち、第２キュービット列（ｂ’）２００がある属性データの量子状態に縮退すると、第１キュービット列（ａ’）１００は、この属性データに対応する要素データの量子状態に縮退する。
【００４０】
なお、この絡み合いの状態は、各要素データｘと各属性データｙが一対一で対応しているわけではない。すなわち、例えば、１つの属性データｙ１に対し、複数の要素データｘ１,ｘ２,ｘ３が対応している場合もある。この場合、第２キュービット列（ｂ’）２００が属性データｙ１の量子状態に縮退すると、第１キュービット列（ａ’）１００は、全要素データの重ね合わせ状態から要素データｘ１,ｘ２,ｘ３の重ね合わせ状態に縮退する。また、同様に、要素データと属性データが１対多や多対多で対応している場合もある。
【００４１】
図９は、この属性量子化部１７における機能構成を概念的に例示した図である。
図９に例示するように、属性量子化部１７は、量子操作制御部１７ａと量子操作部１７ｂを有している。量子操作部１７ｂには、ｎ個のキュービット（ａｊ１’,ａｊ２’,ａｊ３’,…,ａｊｎ’）１０１からなる第１キュービット列（ａ’）１００と、ｍ個のキュービット（ｂｊ１,ａｊ２,ｂｊ３,…,ｂｊｍ）２０１からなる第２キュービット列（ｂ）２００と、からなる第３キュービット列（ａ’,ｂ）３００が入力される。また、量子操作制御部１７ａは、属性設定情報記憶部１３から抽出した属性設定情報ｆに基づき量子操作部１７ｂを制御し、量子操作部１７ｂは上述のような量子操作を行う。そして、量子操作部１７ｂは、ｎ個のキュービット（ａｊ１’,ａｊ２’,ａｊ３’,…,ａｊｎ’）１０１からなる第１キュービット列（ａ’）１００と、量子操作されたｍ個のキュービット（ｂｊ１’,ａｊ２’,ｂｊ３’,…,ｂｊｍ’）２０１からなる第２キュービット列（ｂ’）２００とを出力する。
【００４２】
［ステップＳ５］
次に、制御部２２において、カウント値ｉがｓであるか否かを判断する。ここでｉ＝ｓであればステップＳ７に進み、ｉ＝ｓでなければステップＳ６に進む。
［ステップＳ６］
制御部２２においてｉ←ｉ＋１を計算し、ステップＳ３に進む。
［ステップＳ７］
この時点では、同じ量子状態の第３キュービット列（ａ’,ｂ’）３００がｓ組生成されている。図１０は、このようなｓ組の第３キュービット列（ａ’,ｂ’）３００を概念的に例示した図である。図１０に例示するように、この時点では、ｎ個のキュービット（ａｊ１’,ａｊ２’,ａｊ３’,…,ａｊｎ’）１０１からなる第１キュービット列（ａ’）１００と、ｍ個のキュービット（ｂｊ１’,ａｊ２’,ｂｊ３’,…,ｂｊｍ’）２０１からなる第２キュービット列（ｂ’）２００と、からなる第３キュービット列（ａ’,ｂ’）３００が、ｓ列生成されている。そして、第１キュービット列（ａ’）１００と第２キュービット列（ｂ）２００は、第３キュービット列（ａ’,ｂ’）３００ごとに絡み合いの状態となっている。
【００４３】
このように生成された各第１キュービット列（ａ’）１００（「第２キュービット列と絡み合いの状態となった第１キュービット列」に相当）は、量子記憶部１８に送られ（例えば、その量子状態が）格納される。なお、この際、各第１キュービット列（ａ’）１００には、サンプル番号ｓｎが付与され、各サンプル番号ｓｎと各第１キュービット列（ａ’）１００が対応付けられる（図１１）。
図１２は、サンプル番号ｓｎと、第１キュービット列（ａ’）１００の量子状態が示す要素データｘと、第２キュービット列（ｂ’）２００が示す属性データｆ（ｘ）との関係を例示した表である。
【００４４】
この図に示すように、第１キュービット列（ａ’）１００は、｜０００…０００＞,｜０００…００１＞,…,｜１１１…１１１＞の要素データｘの重ね合わせ状態にあり、第２キュービット列（ｂ’）２００は、｜１００…１００＞,｜０１０…０１１＞,…,｜０１０…１０１＞の属性データｆ（ｘ）の重ね合わせ状態にある。そして、各要素データｘと属性データｆ（ｘ）は、相互に対応している（例えば、要素データ｜０００…０００＞は、属性データ｜１００…１００＞に対応している）。そして、このような第１キュービット列（ａ’）１００と第２キュービット列（ｂ’）２００の組ごとにサンプル番号ｓｎが付されている。
【００４５】
［ステップＳ８］
また、属性量子化部１７において生成された第２キュービット列（ｂ’）２００（「属性データの重ね合わせ状態となった第２キュービット列」に相当）は、量子出力部１９に送られ、量子出力部１９（「第１量子出力部」に相当）は、これらの第２キュービット列（ｂ’）２００を、量子通信路４０を通じてサンプリング装置３０に送信（出力）する。すなわち、ｍ×ｓ個のキュービットが送信される。なお、この第２キュービット列（ｂ’）２００の送信は、サンプリング装置３０側で、送られた第２キュービット列（ｂ’）２００とサンプル番号ｓｎの対応がとれるように行われる。例えば、サンプル番号ｓｎの順番に第２キュービット列（ｂ’）２００を送信し、サンプリング装置３０側で受信した順番を第２キュービット列（ｂ’）２００のサンプル番号ｓｎと判断する等である。
【００４６】
［ステップＳ９］
サンプリング装置３０は、量子入力部３３（「第１量子入力部」に相当）において、送られた第２キュービット列（ｂ’）２００の入力を受け付ける。入力された全第２キュービット列（ｂ’）２００は、観測部３４に送られる。
［ステップＳ１０］
観測部３４（「第１観測部」に相当）は、送られた各第２キュービット列を１つずつ観測する。この観測により、各第２キュービット列は、それぞれ何れかの属性データを示す量子状態に縮退する。また、この縮退により、データ提供装置１０の量子記憶部１８に格納されている各第１キュービット列（ａ’）１００も対応する要素データｘの量子状態に縮退する。
【００４７】
図１３は、この観測後における、サンプル番号ｓｎと、第１キュービット列（ａ’）１００の量子状態が示す要素データｘと、第２キュービット列（ｂ’）２００が示す属性データｆ（ｘ）との関係を例示した表である。
図１３の例の場合、観測によって、例えば、サンプル番号ｓｎ＝１に対応する第２キュービット列（ｂ’）２００が｜０１０…０１１＞の量子状態に縮退しており、それに対応する第１キュービット列（ａ’）１００が｜０００…００１＞＋｜０００…０１１＞の重ね合わせ状態に縮退している。また、例えば、サンプル番号ｓｎ＝２に対応する第２キュービット列（ｂ’）２００が｜１００…１００＞の量子状態に縮退しており、それに対応する第１キュービット列（ａ’）１００が｜０００…０１０＞に縮退している。その他のサンプル番号ｓｎに対応する第１キュービット列（ａ’）１００及び第２キュービット列（ｂ’）２００も同様に縮退している。
【００４８】
［ステップＳ１１］
次に、キュービット列選択部３５において、サンプリング情報記憶部３２からサンプリング情報αを読み出し、各属性データｆ（ｘ）に対する非負整数値α（ｆ（ｘ））を計算する。なお、この非負整数値の算出に用いる属性データｆ（ｘ）は、観測部３４の観測結果でもよく、また、あらかじめ図示していないメモリに格納しておいたデータでもよい。
図１４は、このように算出された非負整数値α（ｆ（ｘ））を例示した表である。
図１４の例では、属性データｆ（ｘ）＝｜１００…１００＞に対し、非負整数値α（ｆ（ｘ）＝２００が、属性データｆ（ｘ）＝｜０１０…０１１＞に対し、非負整数値α（ｆ（ｘ）＝１００が、属性データｆ（ｘ）＝｜１１１…０１１＞に対し、非負整数値α（ｆ（ｘ）＝２０が、というように非負整数値α（ｆ（ｘ））が求められている。
【００４９】
次に、キュービット列選択部３５は、求めた非負整数値α（ｆ（ｘ））が示す個数分だけ、その属性データｆ（ｘ）に縮退した第２キュービット列（ｂ’）２００を選択する。すなわち、観測部３４の観測値である属性データ（ｙ）を参照し、各属性データｆ（ｘ）ごとに、サンプリング情報によって特定される要素データｘの取得数分α（ｆ（ｘ））だけ、観測部３４における観測値が当該属性データとなった第２キュービット列（ｂ’）２００を選択する。
例えば、図１４の例の場合、キュービット列選択部３５は、観測部３４の観測値である属性データ（ｙ）を参照し、属性データｆ（ｘ）が｜１００…１００＞に縮退した第２キュービット列（ｂ’）２００をα（ｆ（ｘ））＝２００個特定し、属性データｆ（ｘ）が｜０１０…０１１＞に縮退した第２キュービット列（ｂ’）２００をα（ｆ（ｘ））＝１００個特定し、属性データｆ（ｘ）が｜１１１…０１１＞に縮退した第２キュービット列（ｂ’）２００をα（ｆ（ｘ））＝２０個特定し、…、属性データｆ（ｘ）が｜０１０…１０１＞に縮退した第２キュービット列（ｂ’）２００をα（ｆ（ｘ））＝１００個特定する。なお、α（ｆ（ｘ））＝０となる属性データｆ（ｘ）（例えば、｜０００…１０１＞等）に縮退した第２キュービット列（ｂ’）２００は選択されない。よって、ここで選択される第２キュービット列（ｂ’）２００は、第２キュービット列（ｂ’）２００全体の部分集合となる。
【００５０】
キュービット列選択部３５は、選択した第２キュービット列（ｂ’）２００を特定するサンプル番号を要求サンプル番号ｓｎ’として古典出力部３６に送る。なお、この要求サンプル番号ｓｎ’は、特定した第２キュービット列（ｂ’）２００と絡み合いの状態にある第１キュービット列（ａ’）１００をも特定する情報である。また、要求サンプル番号ｓｎ’の集合は、サンプル番号ｓｎ全体｛１,２,…,ｓ｝の部分集合となる。
［ステップＳ１２］
次に、古典出力部３６において、この要求サンプル情報ｓｎ’を、古典通信路５０を通じ、データ提供装置１０に送信（出力）する。
［ステップＳ１３］
データ提供装置１０は、古典入力部２０において、サンプリング装置３０から送信された要求サンプル情報ｓｎ’の入力を受け付け（受信し）、検索部２１に送る。
【００５１】
［ステップＳ１４］
検索部２１は、この要求サンプル情報ｓｎ’によって特定される全ての第１キュービット列（ａ’）１００を選択する。すなわち、検索部２１は、送られた全ての要求サンプル情報ｓｎ’と一致するサンプル番号ｓｎに対応する第１キュービット列（ａ’）１００を、量子記憶部１８から選択する。そして、検索部２１は、選択した第１キュービット列（ａ’）１００を量子出力部１９に送る。
［ステップＳ１５］
量子出力部１９（「第２量子出力部」に相当）は、検索部２１から送られた第１キュービット列（ａ’）１００を、量子通信路４０を通じて、サンプリング装置３０に出力（送信）する。
【００５２】
［ステップＳ１６］
サンプリング装置３０は、量子入力部３３（「第２量子入力部」に相当）において、これら第１キュービット列（ａ’）１００の入力を受け付け（受信し）、それらを観測部３４に送る。
［ステップＳ１７］
観測部３４は、送られた第１キュービット列（ａ’）１００を観測し、その観測結果である要素データｘをインタフェース部３１に送る。
［ステップＳ１８］
インタフェース部３１は、この要素データｘを出力する。
【００５３】
＜実施例＞
次に、本実施の形態に基づく具体的な実施例を説明する。
ここで、要素の集合X＝｛０,１,…,７｝、属性関数（属性設定情報）ｆ（ｘ）＝|ｘ−３|（ｃｏｓ（πｘ／２））２、パラメータｓ＝４,ｎ＝３,ｍ＝２、サンプリング関数（サンプリング情報）αを｛０，１，２，３｝→｛１，１，０，１｝とする。なお、この実施例では１０進数表記を用いる。
なお、以下に示す［前処理］以降の各ステップは、図３に示したフローチャートに対応するものである。
［前処理］
まず、要素の集合Ｘ＝｛０,１,…,７｝をデータ提供装置１０の要素集合記憶部１２に格納し、属性関数ｆ（ｘ）＝|ｘ−３|（ｃｏｓ（πｘ／２））２を属性設定情報記憶部１３に格納し、パラメータｓ＝４,ｎ＝３,ｍ＝２をパラメータ記憶部１４に格納する。
【００５４】
［ステップＳ１］
制御部２２においてｉに１を代入する。
［ステップＳ２］
キュービット生成部１５において、（ｎ＝３個のキュービットからなる第１キュービット列）＋（ｍ＝２個のキュービットからなる第２キュービット列）からなる第３キュービット列をｓ＝４列生成する（図４）。
［ステップＳ３］
要素量子化部１６において、各第１キュービット列に対し、図６に示したようにWalsh-Hadamard変換を適用し、要素データｘ∈（０,１,…,７）全ての重ね合わせ状態を生成する。
【００５５】
［ステップＳ４］
属性量子化部１７において、属性関数ｆ（ｘ）＝|ｘ−３|（ｃｏｓ（πｘ／２））２を用い、各第２のキュービット列に対し、属性データｆ（ｘ）（ｘ∈（０,１,…,７））全ての重ね合わせ状態を生成する。このときの各第３キュービット列の量子状態は、１／２√２（｜０，３＞＋｜１，０＞＋｜２，１＞＋｜３，０＞＋｜４，１＞＋｜５，０＞＋｜６，３＞＋｜７，０＞）である。ここで｜β，γ＞のβは、第１キュービット列の量子状態が示す要素データｘを示しており、γは、第２キュービット列の量子状態が示す属性データｆ（ｘ）を示している。そして、｜β，γ＞は、ｘ＝βの量子状態の第１キュービット列とｆ（β）＝γの量子状態の第２キュービット列とが絡み合いの状態にあることを示している。そして、｜β１，γ１＞＋｜β２，γ２＞は、｜β１，γ１＞の量子状態と、｜β２，γ２＞の量子状態が重ね合わせ状態にあることを示している。
その後、ステップＳ５の判断でｉ＝１であるため、ステップＳ６でｉ←１＋１＝２とされた後ステップＳ３に戻る。その後、ステップＳ３〜Ｓ５の処理を２回繰り返したところでステップＳ７に進む。
【００５６】
［ステップＳ７］
量子記憶部１８に第１キュービット列を格納する。
［ステップＳ８］
量子出力部１９において、ｓ組の第２キュービット列を、サンプリング装置３０に送信する。
［ステップＳ９］
サンプリング装置３０の量子入力部３３において、ｓ組の第２キュービット列を受信する。
［ステップＳ１０］
観測部３４において、ｓ組の第２キュービット列を観測する。この例の場合、この観測により、｛０，１，２，３｝がそれぞれ、１／２、１／４、０、１／４の確率で得られる。
【００５７】
［ステップＳ１１］
キュービット列選択部３５において、サンプリング関数α（｛０，１，２，３｝→｛１，１，０，１｝）に従い、第２キュービット列の観測結果が０となったものを１個、１となったものを１個、２となったものを０個、３となったものを１個選択する。ここで、第２キュービット列の観測結果が０となった第２キュービット列のサンプル番号ｓｎが１であり、観測結果が１となった第２キュービット列のサンプル番号ｓｎが３であり、観測結果が３となった第２キュービット列のサンプル番号ｓｎが４であったとする。これらのサンプル番号ｓｎの集合｛１，３，４｝は、サンプル番号ｓｎ全体の集合｛１，２，３，４｝の部分集合である。そして、この部分集合｛１，３，４｝を要求サンプル番号ｓｎ’とする。
【００５８】
［ステップＳ１２］
古典出力部３６において、要求サンプル番号ｓｎ’＝｛１，３，４｝をデータ提供装置１０に送信する。
［ステップＳ１３］
データ提供装置１０は、この要求サンプル番号ｓｎ’＝｛１，３，４｝を受信する。
［ステップＳ１４］
検索部２１において、量子記憶部１８から、要求サンプル番号ｓｎ’＝｛１，３，４｝に対応する第１キュービット列を選択する。
【００５９】
［ステップＳ１５］
選択された各第１キュービット列を、量子出力部１９からサンプリング装置３０に送信する。
［ステップＳ１６］
サンプリング装置３０の量子入力部３３において、各第１キュービット列を受信する。
［ステップＳ１７］
受信された各第１キュービット列を、観測部３４において観測する。
［ステップＳ１８］
インタフェース部３１から観測結果（要素データ）を出力する。
【００６０】
〔本形態の特徴〕
以上のような処理を実行することで、サンプリング装置３０を使用するサンプリング者は、サンプリング関数αをデータ提供者に与えずにサンプリングを行うことができる。また、データ提供装置１０を使用するデータ提供者は、サンプリング者のサンプリングに必要ない要素に関する情報をサンプリング者に送る必要がない。
これにより、データ提供者及びサンプリング者が互いに相手に与える情報を最小限に抑えつつ、データ提供者からサンプリング者への情報提供を行うことができる。
【００６１】
〔ハードウェア構成〕
最後に、本形態におけるハードウェア構成について説明する。
本形態におけるキュービットの生成、初期化、重ね合わせ状態の生成、属性設定情報ｆの計算による絡み合い状態の生成、量子状態の保存、観測等は、すべて量子コンピュータによって実現できる。量子コンピュータの実現する物理系としては、例えば、液体中の各スピンを用いる方法（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）、イオントラップを用いる方法（J. I. Cirac and P. Zoller, Quantum computations with cold trapped ions, Physical Review Letter 74;4091, 1995）、量子ドット中の電子スピンを用いる方法（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-cooperpair box, Nature 393, 786-788, 1999）、光子を用いる方法（Y. Nakamura, M. Kitagawa, K. Igeta, In 3-rd Proc. Asia-Pacific Phys. Comf., World Scientific, Singapore, 1988）等を例示できる。また、それぞれの物理系に対する量子コンピュータの実現方法については、「M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Chapter 7 Physical Realization」に詳しい。
【００６２】
以下に、本形態のデータ提供装置１０及びサンプリング装置３０を実現するための具体的なハードウェア構成について例示する。
＜キュービット生成部＞
図１５は、本形態におけるキュービット生成部１５の構成を例示したブロック図である。
図１５のキュービット生成部１５は、キュービットとして光子を用いる場合の例であり、パラメトリックダウンコンバージョン（ＰＤＣ：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.」等参照。）により、単一光子を生成する。
【００６３】
この図に例示するように、この例のキュービット生成部１５は、レーザ出射部１５ａ、非線形結晶１５ｂ、吸収部１５ｃ、検出部１５ｄ及びレーザ制御部１５ｅを有している。
ここで、レーザ出射部１５ａは、ポンプ光４００を出射するレーザ装置であり、例えば、アルゴンイオンレーザ（０．３５１μｍ単一周波数ＣＷレーザ）等を出射するアルゴンイオンレーザ装置等である。また、非線形結晶１５ｂは、例えば、KDP、ADP、RDA、CDA、LiNbO3、LiIO3、Ba2NaNb5O15、Ag3AsS3、AgGaS2、KTP、BBO、LBO等であり、吸収部１５ｃには、例えば、ポンプ光４００の周波数は良く吸収し、単一光子４０１の周波数の光を散乱しにくいものを用いる。また、検出部１５ｄは、例えば、光電子増倍管、ストリークカメラ、フォトダイオード又はアバランシェフォトダイオード等の光子計数領域で用いることのできる検出器である。さらに、レーザ制御部１５ｅは、公知のＣＰＵに所定のプログラムを実行させることにより構成されるものである。
【００６４】
レーザ制御部１５ｅは、制御信号をレーザ出射部１５ａに送り、レーザ出射部１５ａは、この制御信号に応じてポンプ光４００を出射する。レーザ出射部１５ａから出射されポンプ光４００は、非線形結晶１５ｂへ入射し、非線形結晶１５ｂ中で、その結晶に固有の確率で、入射した光の周波数と異なる２つの光子へと変換される。この過程はパラメトリック蛍光過程とよばれ、２つの光子はパラメトリック蛍光と呼ばれる。一方のパラメトリック蛍光は単一光子４０１として出力され、他方のパラメトリック蛍光は参照光子４０２として検出部１５ｄに入射する。また、非線形結晶１５ｂ中で分割されなかったポンプ光４００は吸収部１５ｃに吸収される。
【００６５】
ここで、検出部１５ｄにおける参照光子４０２の検出により、単一光子４０１の出射を確認し、この単一光子４０１を１つのキュービットとして取り扱う。そして、キュービット生成部１５は、レーザ制御部１５ｅに入力されたパラメータｍ，ｎ，ｓに応じたレーザ制御部１５ｅの制御に従い、同様な処理を（ｎ＋ｍ）×ｓ回繰り返すことにより、図４に例示したｓ列の第３キュービット列３００を初期化した状態で生成する。
＜要素量子化部＞
量子操作制御部１６ａ（図５）は、例えば、公知のＣＰＵに所定のプログラムを実行させることにより構成される。
【００６６】
また、光子をキュービットとして用いる場合、量子操作部１６ｂを構成するウォルシューアダマール変換部１６ｂａ、１６ｂｂや回転部１６ｂｆ、１６ｂｈのＲｚ回転機能（図６，図８）は、例えば、位相シフタ等を用いて実現できる。なお、位相シフタとしては、例えば、制御電圧によって通過光の位相を制御できる電気光学効果変調器（例えば、ファラデーローテータ、ＬｉＮｂＯ３などの結晶の電気光学効果を利用した変調器等）を用いることができる。また、ウォルシューアダマール変換部１６ｂａ、１６ｂｂや回転部１６ｂｅ、１６ｂｇのＲｙ回転機能は、例えば、ビームスプリッター等を用いて実現できる。さらに、回転部１６ｂｃ、１６ｂｄのＲｘ回転機能は、例えば、Ｒｚ回転機能を実現する位相シフタ等と、Ｒｙ回転機能を実現するビームスプリッター等を組み合わせることにより実現できる。また、ＣＮＯＴ部１６ｂｉ〜１６ｂｎは、例えば、「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」記載のPittman et al. 方式によって実現できる。
【００６７】
＜属性量子化部＞
属性量子化部１７のハードウェア構成部品は、要素量子化部１６と同じである。ただし、各ハードウェア構成部品が、属性設定情報ｆにしたがって配置・構成される点が異なる。
光子をキュービットとして用いる場合、属性量子化部１７は、要素量子化部１６の量子操作部１６ｂと同様、ウォルシューアダマール変換部や回転部のＲｚ回転機能、Ｒｙ回転機能などにより構成される。そして、これらの構成要素を、属性設定情報ｆに応じて配置し、第１キュービット列１００と第２キュービット列２００を同時に入射させ、これらを絡み合いの状態にすることにより、属性量子化部１７が実現できる。
【００６８】
＜量子記憶部＞
量子記憶部１８は、例えば、量子ドット内の電子準位、核スピン、あるいは超伝導体内部の電荷（クーパー対）量をキュービットとして用いてデータを保存する装置等を用いて実現できる（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、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）。
【００６９】
＜観測部＞
光子をキュービットとして用いる場合、観測部３４は、例えば、光電子増倍管、ストリークカメラ、フォトダイオード又はアバランシェフォトダイオード等の光子計数領域で用いることのできる検出器を用いて実現できる。
＜その他＞
インタフェース部１１，３１は、例えば、キーボード、データ入力ポート等の公知の入力装置であり、要素集合記憶部１２、属性設定情報記憶部１３、パラメータ記憶部１４、サンプリング情報記憶部３２及びプログラムメモリ２３，３８は、RAM（Random Access Memory）、ROM（Read Only Memory）等の古典情報を記憶する公知のメモリである。また、制御部２２，３７、レーザ制御部１５ｅ及び量子操作制御部１６ａは、公知のCPU（Central Processing Unit）を中心に構成される制御素子である。
【００７０】
〔プログラム〕
次に、プログラムメモリ２３、３８に格納されたプログラムについて説明する。
プログラムメモリ２３に格納されたプログラムは、データ提供装置１０の制御に必要な処理をコンピュータ（古典的計算機）に実行させるためのプログラムである。すなわち、このプログラムが制御部２２に読み込まれ、この制御部２２と協同して働くことにより、データ提供装置１０の制御に必要な処理が実行される。ここで、「データ提供装置１０の制御に必要な処理」とは、前述したレーザ制御部１５ｅや量子操作制御部１６ａによる制御処理や、制御部２２によるデータ提供装置１０全体の制御処理を意味する。つまり、このプログラムは、例えば、核スピンがキュービットに用いられる場合には、核スピンに当てる電磁波の周波数や時間の制御をコンピュータに実行させるためのプログラムや、データ提供装置１０全体の制御処理をコンピュータに実行させるためのプログラムを意味する。また、光子がキュービットに用いられる場合には、量子計算に必要な各光学素子の特性（例えば、ミラーの角度や位相シフタの制御電圧等）の制御をコンピュータに実行させるためのプログラムや、データ提供装置１０全体の制御処理をコンピュータに実行させるためのプログラムを意味する。
【００７１】
また、プログラムメモリ３８に格納されたプログラムは、サンプリング装置３０の制御に必要な処理をコンピュータに実行させるためのプログラムである。すなわち、このプログラムが制御部３７に読み込まれ、この制御部３７と協同して働くことにより、サンプリング装置３０の全体制御に必要な処理が実行される。
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００７２】
また、このようなプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このようなプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
このように流通するプログラムを実行するデータ提供装置１０やサンプリング装置３０は、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己のプログラムメモリ２３、３８に格納する。そして、処理の実行時、制御部２２，３４は、自己のプログラムメモリ２３、３８に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このようなプログラムの別の実行形態として、制御部２２，３４が可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、制御部２２，３４にサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。
【００７３】
なお、本発明は上述の実施の形態に限定されるものではない。例えば、本形態では量子通信路４０や古典通信路５０を通じて情報通信を行うこととしたが、量子情報や古典情報を、記録媒体を介してやり取りすることとしてもよい。また、属性設定情報やサンプリング情報は「関数」という概念に限定されるものではなく、例えば対応テーブル等であってもよい。さらに、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、各機能構成が同一筐体内にあるとは限らない。
【図面の簡単な説明】
【００７４】
【図１】本形態におけるサンプル抽出システムの構成を例示したブロック図。
【図２】要素集合記憶部に格納された要素データを例示した概念図。
【図３】本形態におけるサンプル抽出処理を説明するためのフローチャート。
【図４】生成されたキュービット列を説明するための概念図。
【図５】要素量子化部における機能構成を概念的に例示した図。
【図６】要素データの集合が、０以上２ｎ−１以下の整数全体である場合における、量子操作部の量子操作を例示したブロック図。
【図７】要素データの全要素の重ね合わせ状態を概念的に示した図。
【図８】量子操作部の量子操作を例示したブロック図。
【図９】属性量子化部における機能構成を概念的に例示した図。
【図１０】生成されたｓ組の第３キュービット列を概念的に例示した図。
【図１１】第２キュービット列と絡み合いの状態にある第１キュービット列が量子記憶部１８に格納された様子を概念的に例示した図。
【図１２】サンプル番号と、第１キュービット列の量子状態が示す要素データと、第２キュービット列が示す属性データとの関係を例示した表。
【図１３】観測後における、サンプル番号と、第１キュービット列の量子状態が示す要素データと、第２キュービット列が示す属性データとの関係を例示した表。
【図１４】サンプリング情報αによって算出された非負整数値を例示した表。
【図１５】本形態におけるキュービット生成部の構成を例示したブロック図。
【符号の説明】
【００７５】
１  サンプル抽出システム
１０  データ提供装置
３０  サンプリング装置
【図１】
2005242625.tif 000007
【図２】
2005242625.tif 000008
【図３】
2005242625.tif 000009
【図４】
2005242625.tif 000010
【図５】
2005242625.tif 000011
【図６】
2005242625.tif 000012
【図７】
2005242625.tif 000013
【図８】
2005242625.tif 000014
【図９】
2005242625.tif 000015
【図１０】
2005242625.tif 000016
【図１１】
2005242625.tif 000017
【図１２】
2005242625.tif 000018
【図１３】
2005242625.tif 000019
【図１４】
2005242625.tif 000020
【図１５】
2005242625.tif 000021