(57)【要約】【課題】  ｆ（ｘ）＝ｆ（ｘ∧ｓ）又はｇ（ｘ）＝ｇ（ｘ∨ｓ）という不変性を持つ未知の関数、ｎ−ｂｉｔ列ｓのＨａｍｍｉｎｇ重みが与えられている場合において、前記関数に適当な入力値を与えその出力値からｓを求める問題を解く量子計算方法を提供する。【解決手段】  それぞれがｎ個の二状態系から成る第１及び第２のレジスタの全てのｑｕｂｉｔを初期化する工程と、前記第１レジスタにＨａｄａｍａｒｄ変換を作用させて均一な重ね合わせ状態を構成する工程と、ユニタリ変換を前記第１及び第２レジスタに作用させて、当該第１レジスタが｜ｘ＞のとき当該第２レジスタが｜ｆ（ｘ）＞又は｜ｇ（ｘ）＞となるような量子もつれ合いを二つのレジスタ間に生じさせ、再度、当該第１レジスタにＨａｄａｍａｒｄ変換を作用させて、当該第１レジスタを基底｛｜ｘ＞：ｘ∈｛０，１｝n｝で観測し、その観測値からｓを求める。【選択図】  図１
2006048441.tif 000002
【特許請求の範囲】
【請求項１】
ｆ：｛０，１｝n→｛０，１｝n又はｇ：｛０，１｝n→｛０，１｝nでｆ（ｘ）＝ｆ（ｘ∧ｓ）又はｇ（ｘ）＝ｇ（ｘ∨ｓ）という不変性を持つ未知の関数がブラックボックスとして与えられていて、且つ、ｎ−ｂｉｔ列ｓのＨａｍｍｉｎｇ重みが与えられているとして、前記ブラックボックスに適当な入力値を与えてその出力値から前記ｓを算出する量子計算方法であって、
それぞれがｎ個の二状態系（ｑｕｂｉｔ）｛｜０＞，｜１＞｝から成る第１及び第２のレジスタの全てのｑｕｂｉｔを｜０＞状態に初期化する工程と、
前記第１レジスタにＨａｄａｍａｒｄ変換を作用させて均一な重ね合わせ状態を構成する工程と、
前記ブラックボックスｆ又はｇに相当するユニタリ変換を前記第１及び第２レジスタに作用させて、当該第１レジスタが｜ｘ＞のとき当該第２レジスタが｜ｆ（ｘ）＞又は｜ｇ（ｘ）＞となるような量子もつれ合いを二つのレジスタ間に生じさせ、再度、前記第１レジスタにＨａｄａｍａｒｄ変換を作用させて、当該第１レジスタを基底｛｜ｘ＞：ｘ∈｛０，１｝n｝で観測し、その観測値からｓを算出する工程と
を備えることを特徴とする量子計算方法。
【請求項２】
ｆ：｛０，１｝n→｛０，１｝nでｆ（ｘ）＝ｆ（ｘ∧ｓ）という不変性を持つ未知の関数がブラックボックスとして与えられていて、且つ、ｎ−ｂｉｔ列ｓのＨａｍｍｉｎｇ重みがｗｔ（ｓ）＝ｍと与えられているとして、前記ｓを算出する量子計算方法であって、
一回目の量子計算方法の試行を行う工程と、
該工程でｎ−ｂｉｔ列ｋが得られたとして、ｗｔ（ｋ）＝ｍならばｓ＝ｋ、ｗｔ（ｋ）＜ｍならばｋをｋoldとして再度量子計算方法の試行を行い、新たに得られたｎ−ｂｉｔ列をｋnewとし、ｋ＝ｋold∨ｋnewとして、ｗｔ（ｋ）＝ｍならばｓ＝ｋ、ｗｔ（ｋ）＜ｍならば再度試行を行う、という過程をｗｔ（ｋ）＝ｍになるまで繰り返すことによって、ｎ−ｂｉｔ列ｓを算出する工程と
を更に備えることを特徴とする請求項１に記載の量子計算方法。
【請求項３】
ｇ：｛０，１｝n→｛０，１｝nでｇ（ｘ）＝ｇ（ｘ∨ｓ）という不変性を持つ未知の関数がブラックボックスとして与えられていて、且つ、ｎ−ｂｉｔ列ｓのＨａｍｍｉｎｇ重みがｗｔ（ｓ）＝ｎ−ｍと与えられているとして、前記ｓを算出する量子計算方法であって、
一回目の量子計算方法の試行を行う工程と、
該工程でｎ−ｂｉｔ列ｋが得られたとして、
2006048441.tif 000138
ならば
2006048441.tif 000139
、
2006048441.tif 000140
ならばｋをｋoldとして再度量子計算方法の試行を行い、新たに得られたｎ−ｂｉｔ列をｋnewとし、
2006048441.tif 000141
として、
2006048441.tif 000142
ならば
2006048441.tif 000143
、
2006048441.tif 000144
ならば再度試行を行う、という過程を
2006048441.tif 000145
になるまで繰り返すことによって、ｎ−ｂｉｔ列ｓを算出する工程と
を更に備えることを特徴とする請求項１に記載の量子計算方法。
【請求項４】
互いに離れた場所にある二者が量子通信回線によって量子情報を交換しながら互いに協力し合って演算を行うものであって、前者はｆ：｛０，１｝n→｛０，１｝n又はｇ：｛０，１｝n→｛０，１｝nでｆ（ｘ）＝ｆ（ｘ∧ｓ）又はｇ（ｘ）＝ｇ（ｘ∨ｓ）という不変性を持つ未知の関数がブラックボックスとして与えられており、後者にはｎ−ｂｉｔ列ｓのＨａｍｍｉｎｇ重みが与えられていて、後者が適当な量子状態にある複数のｑｕｂｉｔを前者に送り、前者はその複数のｑｕｂｉｔの状態を与えられたブラックボックスで変換して後者に送り返し、後者はそのｑｕｂｉｔを観測して前記ｓを算出する分散量子計算実行方法であって、
前者は各自ｎ−ｑｕｂｉｔから成るレジスタを２つ用意する工程と、
両者は全てのｑｕｂｉｔを｜０＞状態に初期化する工程と、
後者は自分のｎ−ｑｕｂｉｔにＨａｄａｍａｒｄ変換を作用させて均一な重ね合わせ状態を構成して、それを前者に送る工程と、
前者は後者から受け取ったｎ−ｑｕｂｉｔを第１レジスタ、自分の用意したｎ−ｑｕｂｉｔを第２レジスタとし、前のブラックボックスｆ又はｇに相当するユニタリ変換を第１、第２レジスタに作用させて、第１レジスタが｜ｘ＞のとき第２レジスタが｜ｆ（ｘ）＞又は｜ｇ（ｘ）＞となるような量子もつれ合いを二つのレジスタ間に生じさせ、第１レジスタのｎ−ｑｕｂｉｔを後者に送り返す工程と、
後者は受け取ったｎ−ｑｕｂｉｔに再度Ｈａｄａｍａｒｄ変換を作用させて基底｛｜ｘ＞：ｘ∈｛０，１｝n｝で観測し、その観測値からｓを算出する工程と、
を有することを特徴とする分散量子計算実行方法。
【請求項５】
前者にｆ：｛０，１｝n→｛０，１｝nでｆ（ｘ）＝ｆ（ｘ∧ｓ）という不変性を持つ未知の関数がブラックボックスとして与えられていて、且つ、後者にｎ−ｂｉｔ列ｓのＨａｍｍｉｎｇ重みがｗｔ（ｓ）＝ｍと与えられているとして、前者、後者の間で量子情報をやり取りすることで、後者が前記ｓを算出する分散量子計算実行方法であって、
一回目の試行で後者がｎ−ｂｉｔ列ｋを得たとして、ｗｔ（ｋ）＝ｍならばｓ＝ｋ、ｗｔ（ｋ）＜ｍならばｋをｋoldとして二回目の試行を実行し、新たに後者が得たｎ−ｂｉｔ列をｋnewとし、ｋ＝ｋold∨ｋnewとして、ｗｔ（ｋ）＝ｍならばｓ＝ｋ、ｗｔ（ｋ）＜ｍならば再度試行を行う、という過程をｗｔ（ｋ）＝ｍになるまで繰り返すことによって、後者がｎ−ｂｉｔ列ｓを算出する工程と
を更に有することを特徴とする請求項４に記載の分散量子計算実行方法。
【請求項６】
前者にｇ：｛０，１｝n→｛０，１｝nでｇ（ｘ）＝ｇ（ｘ∨ｓ）という不変性を持つ未知の関数がブラックボックスとして与えられていて、且つ、後者にｎ−ｂｉｔ列ｓのＨａｍｍｉｎｇ重みがｗｔ（ｓ）＝ｎ−ｍと与えられているとして、前者、後者の間で量子情報をやり取りすることで、後者が前記ｓを算出する分散量子計算実行方法であって、
一回目の試行で後者がｎ−ｂｉｔ列ｋを得たとして、
2006048441.tif 000146
ならば
2006048441.tif 000147
、
2006048441.tif 000148
ならばｋをｋoldとして二回目の試行を実行し、新たに後者が得たｎ−ｂｉｔ列をｋnewとし、
2006048441.tif 000149
として、
2006048441.tif 000150
ならば
2006048441.tif 000151
、
2006048441.tif 000152
ならば再度試行を行う、という過程を
2006048441.tif 000153
になるまで繰り返すことによって、後者がｎ−ｂｉｔ列ｓを算出する工程と
を更に有することを特徴とする請求項４に記載の分散量子計算実行方法。
【請求項７】
一方は複数のｑｕｂｉｔに対するユニタリ変換を実行する技術を持っているが、他方は１−ｑｕｂｉｔに対するユニタリ変換を実行する技術しか持っていない２者が、協力し合って演算を行うことを特徴とする請求項５又は請求項６に記載の分散量子計算実行方法。
【請求項８】
請求項２又は３の量子計算方法を利用することによって、複数のｑｕｂｉｔから成るコントロール部及びターゲット部を持つ量子ｃｏｎｔｒｏｌゲートにおいて、コントロール部のいくつかのｑｕｂｉｔが他のｑｕｂｉｔと相互作用出来ないという不具合を持つ際に、不具合を持つｑｕｂｉｔを効率的に特定することを特徴とする量子ゲート故障診断方法。
【請求項９】
請求項５乃至７のいずれか一つの分散量子計算実行方法を利用することによって、前者の保持する複数のｑｕｂｉｔから成るコントロール部及びターゲット部を持つ量子ｃｏｎｔｒｏｌゲートにおいて、コントロール部のいくつかのｑｕｂｉｔが他のｑｕｂｉｔと相互作用出来ないという不具合を持つ際に、前者、後者間で量子情報をやり取りすることで、後者が前者の保持する量子ゲートの、不具合を持つｑｕｂｉｔを効率的に特定することを特徴とする量子ゲート故障診断方法。
【請求項１０】
ｆ：｛０，１｝n→｛０，１｝n又はｇ：｛０，１｝n→｛０，１｝nでｆ（ｘ）＝ｆ（ｘ∧ｓ）又はｇ（ｘ）＝ｇ（ｘ∨ｓ）という不変性を持つ未知の関数がブラックボックスとして与えられていて、且つ、ｎ−ｂｉｔ列ｓのＨａｍｍｉｎｇ重みが与えられているとして、前記ブラックボックスに適当な入力値を与えてその出力値から前記ｓを算出する量子計算装置であって、
それぞれがｎ個の二状態系（ｑｕｂｉｔ）｛｜０＞，｜１＞｝から成る第１及び第２のレジスタと、
前記第１及び第２のレジスタの全てのｑｕｂｉｔを｜０＞状態に初期化する手段と、
前記第１レジスタにＨａｄａｍａｒｄ変換を作用させて均一な重ね合わせ状態を構成する手段と、
前記ブラックボックスｆ又はｇに相当するユニタリ変換を前記第１及び第２レジスタに作用させて、当該第１レジスタが｜ｘ＞のとき当該第２レジスタが｜ｆ（ｘ）＞又は｜ｇ（ｘ）＞となるような量子もつれ合いを二つのレジスタ間に生じさせ、再度、当該第１レジスタにＨａｄａｍａｒｄ変換を作用させて、当該第１レジスタを基底｛｜ｘ＞：ｘ∈｛０，１｝n｝で観測し、その観測値からｓを算出する手段と
を備えることを特徴とする量子計算装置。
【請求項１１】
ｆ：｛０，１｝n→｛０，１｝nでｆ（ｘ）＝ｆ（ｘ∧ｓ）という不変性を持つ未知の関数がブラックボックスとして与えられていて、且つ、ｎ−ｂｉｔ列ｓのＨａｍｍｉｎｇ重みがｗｔ（ｓ）＝ｍと与えられているとして、前記ｓを算出する量子計算装置であって、
一回目の量子計算方法の試行を行う手段と、
該工程でｎ−ｂｉｔ列ｋが得られたとして、ｗｔ（ｋ）＝ｍならばｓ＝ｋ、ｗｔ（ｋ）＜ｍならばｋをｋoldとして再度量子計算方法の試行を行い、新たに得られたｎ−ｂｉｔ列をｋnewとし、ｋ＝ｋold∨ｋnewとして、ｗｔ（ｋ）＝ｍならばｓ＝ｋ、ｗｔ（ｋ）＜ｍならば再度試行を行う、という過程をｗｔ（ｋ）＝ｍになるまで繰り返すことによって、ｎ−ｂｉｔ列ｓを算出する手段と
を更に備えることを特徴とする請求項１０に記載の量子計算装置。
【請求項１２】
ｇ：｛０，１｝n→｛０，１｝nでｇ（ｘ）＝ｇ（ｘ∨ｓ）という不変性を持つ未知の関数がブラックボックスとして与えられていて、且つ、ｎ−ｂｉｔ列ｓのＨａｍｍｉｎｇ重みがｗｔ（ｓ）＝ｎ−ｍと与えられているとして、前記ｓを算出する量子計算装置であって、
一回目の量子計算方法の試行を行う手段と、
該手段でｎ−ｂｉｔ列ｋが得られたとして、
2006048441.tif 000154
ならば
2006048441.tif 000155
、
2006048441.tif 000156
ならばｋをｋoldとして再度量子計算方法の試行を行い、新たに得られたｎ−ｂｉｔ列をｋnewとし、
2006048441.tif 000157
として、
2006048441.tif 000158
ならば
2006048441.tif 000159
、
2006048441.tif 000160
ならば再度試行を行う、という過程を
2006048441.tif 000161
になるまで繰り返すことによって、ｎ−ｂｉｔ列ｓを算出する手段と
を更に備えることを特徴とする請求項１０に記載の量子計算装置。
【請求項１３】
互いに離れた場所にある二つの量子計算機が量子通信回線によって量子情報を交換しながら互いに協力し合って演算を行うものであって、前者量子計算機はｆ：｛０，１｝n→｛０，１｝n又はｇ：｛０，１｝n→｛０，１｝nでｆ（ｘ）＝ｆ（ｘ∧ｓ）又はｇ（ｘ）＝ｇ（ｘ∨ｓ）という不変性を持つ未知の関数がブラックボックスとして与えられており、後者量子計算機にはｎ−ｂｉｔ列ｓのＨａｍｍｉｎｇ重みが与えられていて、後者量子計算機が適当な量子状態にある複数のｑｕｂｉｔを前者量子計算機に送り、前者量子計算機はその複数のｑｕｂｉｔの状態を与えられたブラックボックスで変換して後者量子計算機に送り返し、後者量子計算機はそのｑｕｂｉｔを観測して前記ｓを算出する分散量子計算実行装置であって、
前者量子計算機はｎ−ｑｕｂｉｔから成るレジスタを２つと、
両者の量子計算機は全てのｑｕｂｉｔを｜０＞状態に初期化する手段と、
後者量子計算機は自分のｎ−ｑｕｂｉｔにＨａｄａｍａｒｄ変換を作用させて均一な重ね合わせ状態を構成して、それを前者量子計算機に送る手段と、
前者量子計算機は後者量子計算機から受け取ったｎ−ｑｕｂｉｔを第１レジスタ、自分の用意したｎ−ｑｕｂｉｔを第２レジスタとし、前のブラックボックスｆ又はｇに相当するユニタリ変換を第１、第２レジスタに作用させて、第１レジスタが｜ｘ＞のとき第２レジスタが｜ｆ（ｘ）＞又は｜ｇ（ｘ）＞となるような量子もつれ合いを二つのレジスタ間に生じさせ、第１レジスタのｎ−ｑｕｂｉｔを後者量子計算機に送り返す手段と、
後者量子計算機は受け取ったｎ−ｑｕｂｉｔに再度Ｈａｄａｍａｒｄ変換を作用させて基底｛｜ｘ＞：ｘ∈｛０，１｝n｝で観測し、その観測値からｓを算出する手段と、
を有することを特徴とする分散量子計算実行装置。
【請求項１４】
前者量子計算機にｆ：｛０，１｝n→｛０，１｝nでｆ（ｘ）＝ｆ（ｘ∧ｓ）という不変性を持つ未知の関数がブラックボックスとして与えられていて、且つ、後者量子計算機にｎ−ｂｉｔ列ｓのＨａｍｍｉｎｇ重みがｗｔ（ｓ）＝ｍと与えられているとして、前者量子計算機、後者量子計算機の間で量子情報をやり取りすることで、後者量子計算機が前記ｓを算出する分散量子計算実行装置であって、
一回目の試行で後者量子計算機がｎ−ｂｉｔ列ｋを得たとして、ｗｔ（ｋ）＝ｍならばｓ＝ｋ、ｗｔ（ｋ）＜ｍならばｋをｋoldとして二回目の試行を実行し、新たに後者量子計算機が得たｎ−ｂｉｔ列をｋnewとし、ｋ＝ｋold∨ｋnewとして、ｗｔ（ｋ）＝ｍならばｓ＝ｋ、ｗｔ（ｋ）＜ｍならば再度試行を行う、という過程をｗｔ（ｋ）＝ｍになるまで繰り返すことによって、後者量子計算機がｎ−ｂｉｔ列ｓを算出する手段と
を更に有することを特徴とする請求項１３に記載の分散量子計算実行装置。
【請求項１５】
前者量子計算機にｇ：｛０，１｝n→｛０，１｝nでｇ（ｘ）＝ｇ（ｘ∨ｓ）という不変性を持つ未知の関数がブラックボックスとして与えられていて、且つ、後者量子計算機にｎ−ｂｉｔ列ｓのＨａｍｍｉｎｇ重みがｗｔ（ｓ）＝ｎ−ｍと与えられているとして、前者量子計算機、後者量子計算機の間で量子情報をやり取りすることで、後者量子計算機が前記ｓを算出する分散量子計算実行装置であって、
一回目の試行で後者量子計算機がｎ−ｂｉｔ列ｋを得たとして、
2006048441.tif 000162
ならば
2006048441.tif 000163
、
2006048441.tif 000164
ならばｋをｋoldとして二回目の試行を実行し、新たに後者量子計算機が得たｎ−ｂｉｔ列をｋnewとし、
2006048441.tif 000165
として、
2006048441.tif 000166
ならば
2006048441.tif 000167
、
2006048441.tif 000168
ならば再度試行を行う、という過程を
2006048441.tif 000169
になるまで繰り返すことによって、後者量子計算機がｎ−ｂｉｔ列ｓを算出する手段と
を更に有することを特徴とする請求項１３に記載の分散量子計算実行装置。
【請求項１６】
一方の量子計算機は複数のｑｕｂｉｔに対するユニタリ変換を実行する技術を持っているが、他方の量子計算機は１−ｑｕｂｉｔに対するユニタリ変換を実行する技術しか持っていない２つの量子計算機が、協力し合って演算を行うことを特徴とする請求項１４又は請求項１５に記載の分散量子計算実行装置。
【請求項１７】
請求項２又は３の量子計算方法を利用することによって、複数のｑｕｂｉｔから成るコントロール部及びターゲット部を持つ量子ｃｏｎｔｒｏｌゲートにおいて、コントロール部のいくつかのｑｕｂｉｔが他のｑｕｂｉｔと相互作用出来ないという不具合を持つ際に、不具合を持つｑｕｂｉｔを効率的に特定する量子ゲート故障診断装置。
【請求項１８】
請求項５乃至７の分散量子計算実行方法を利用することによって、前者量子計算機の保持する複数のｑｕｂｉｔから成るコントロール部及びターゲット部を持つ量子ｃｏｎｔｒｏｌゲートにおいて、コントロール部のいくつかのｑｕｂｉｔが他のｑｕｂｉｔと相互作用出来ないという不具合を持つ際に、前者量子計算機、後者量子計算機間で量子情報をやり取りすることで、後者量子計算機が前者量子計算機の保持する量子ゲートの、不具合を持つｑｕｂｉｔを効率的に特定する量子ゲート故障診断装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、量子計算技術に関する。
【背景技術】
【０００２】
量子コンピュータの研究は、１９８０年代にＲ．Ｐ．Ｆｅｙｎｍａｎが、量子系を効率的にシミュレートするには量子力学の原理を積極的に利用したコンピュータが必要であると主張したことが始まりとされている（非特許文献１、２、３）。その後、Ｄ．Ｄｅｕｔｓｃｈによって現在の形の量子コンピュータが定式化された（非特許文献４、５）。量子コンピュータが注目を集めた理由は、量子コンピュータがいくつかの特別な問題を従来の古典コンピュータよりも効率的に解くことが分かったからである。そのような問題と量子アルゴリズムの代表的な例としては、Ｄｅｕｔｓｃｈ−Ｊｏｚｓａのアルゴリズム、Ｓｉｍｏｎのアルゴリズム、Ｓｈｏｒのアルゴリズム、Ｇｒｏｖｅｒのアルゴリズム等が挙げられる（非特許文献６、７、８、９）。（Ｓｈｏｒのアルゴリズムは、巨大な整数の素因数分解、及び、離散対数問題を量子コンピュータが多項式時間で解決することを示した。古典コンピュータでこれらの問題を多項式時間内に解く方法は見付かっていない。量子計算アルゴリズムの総合的な解説としては非特許文献１０、１１がある。）これらのアルゴリズムは、量子力学の重ね合わせと干渉、量子もつれ合い、不確定性を効果的に使っている。
【０００３】
Ｓｉｍｏｎのアルゴリズムは、次のような問題を取り扱っている。
【０００４】
［問題］
関数ｆ：｛０，１｝n→｛０，１｝nがｂｌａｃｋ  ｂｏｘ（ｏｒａｃｌｅ）として与えられているとする。ｆは、次の二つの場合のうちのどちらかであることが保証されているとする。
１．全ての｛ｆ（ｘ）：ｘ∈｛０，１｝n｝は互いに異なっていて、ｆはｏｎｅ−ｔｏ−ｏｎｅ  ｆｕｎｃｔｉｏｎである。
２．ある（０．．．０）でない未知のｎ−ｂｉｔ列ｓが与えられていて、ｆ（ｘ）＝ｆ（ｙ）となるのはｘ＝ｙ又は
2006048441.tif 000003
のとき、且つ、そのときに限る。（ｆはｔｗｏ−ｔｏ−ｏｎｅ  ｆｕｎｃｔｉｏｎである。）
ｆが第１の場合か第２の場合かを判別し、もし第２の場合ならばｓを求めよ（ただし、
2006048441.tif 000004
はｂｉｔ毎のｍｏｄｕｌｏ  ２の加算（ｂｉｔｗｉｓｅ  ｅｘｃｌｕｓｉｖｅ−ｏｒ）を表す）。
【０００５】
上の問題を、ｂｌａｃｋ  ｂｏｘ（ｏｒａｃｌｅ）ｆへのｑｕｅｒｙをできるだけ少なくして解きたいとする。古典的には少なくとも平均でＯ（２n）個のｑｕｅｒｙが必要である。（より正確に述べると、誤り確率がある有限一定の値を上限として抑えられる、所定の古典的確率的コンピュータ（ｃｌａｓｓｉｃａｌ  ｂｏｕｎｄｅｄ−ｅｒｒｏｒ  ｐｒｏｂａｂｉｌｉｓｔｉｃ  ｃｏｍｐｕｔａｔｉｏｎ）でこの問題を解くには、指数関数オーダーの個数のｑｕｅｒｙが必要ということである。）Ｓｉｍｏｎの量子アルゴリズムは、この問題を平均でｎの多項式程度の個数のｑｕｅｒｙで解く。
【０００６】
Ｓｉｍｏｎのアルゴリズムは、関数ｆの持つ周期を探し出すアルゴリズムである。各ｘ∈｛０，１｝nに対してｆ（ｘ）がどのような値を取るかという局所的な情報は無視され、周期ｓという関数ｆの大域的な情報のみが上手く取り出される。Ｓｉｍｏｎのアルゴリズムのこの性質をさらに発展させたものが、Ｓｈｏｒの素因数分解、離散対数問題アルゴリズムである。
【０００７】
Ｂ．Ｍ．ＴｅｒｈａｌとＪ．Ａ．Ｓｍｏｌｉｎはｂｉｎａｒｙ  ｓｅａｒｃｈ  ｐｒｏｂｌｅｍを一個のｑｕｅｒｙで解く量子アルゴリズムを示した（非特許文献１２）。この問題に対する古典アルゴリズムのｑｕｅｒｙ数の下限はｌｏｇ2ｎである（ｎはオラクルに入力するｂｉｔ列の長さとする）。
【０００８】
Ｓｉｍｏｎの量子アルゴリズムは
2006048441.tif 000005
という不変性を持つ関数ｆのオラクルを使って、多項式時間でｓを求める。これに対して、古典コンピュータはｓを求めるのに指数関数時間を必要とする。しかし、Ｓｉｍｏｎのアルゴリズムの計算時間は期待値で評価されている。従って、非常に小さな確率ではあるが、Ｓｉｍｏｎのアルゴリズムでｓを求めるのに、指数関数時間がかかってしまう場合も有り得る。Ｇ．ＢｒａｓｓａｒｄとＰ．Ｈｏｙｅｒ、Ｔ．ＭｉｈａｒａとＳ．Ｃ．Ｓｕｎｇは、最悪の場合でも必ず多項式時間でＳｉｍｏｎの問題を解く量子アルゴリズムについて議論している（非特許文献１３、１４、１５）。
【非特許文献１】Ｒ．Ｐ．Ｆｅｙｎｍａｎ，‘Ｓｉｍｕｌａｔｉｎｇ  ｐｈｙｓｉｃｓ  ｗｉｔｈ  ｃｏｍｐｕｔｅｒｓ’，  Ｉｎｔ．  Ｊ．  Ｔｈｅｏｒ．  Ｐｈｙｓ．  ２１，  ４６７−４８８  （１９８２）．
【非特許文献２】Ｒ．Ｐ．Ｆｅｙｎｍａｎ，‘Ｑｕａｎｔｕｍ  ｍｅｃｈａｎｉｃａｌ  ｃｏｍｐｕｔｅｒｓ’，  Ｆｏｕｎｄ．  Ｐｈｙｓ．  １６，  ５０７−５３１  （１９８６）．
【非特許文献３】Ｒ．Ｐ．Ｆｅｙｎｍａｎ，  Ｆｅｙｎｍａｎ  ｌｅｃｔｕｒｅｓ  ｏｎ  ｃｏｍｐｕｔａｔｉｏｎ  （Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ  Ｐｕｂｌｉｓｈｉｎｇ  Ｃｏｍｐａｎｙ，  Ｉｎｃ．，  Ｒｅａｄｉｎｇ，  Ｍａｓｓａｃｈｕｓｅｔｔｓ，  １９９６）．
【非特許文献４】Ｄ．Ｄｅｕｔｓｃｈ，‘Ｑｕａｎｔｕｍ  ｔｈｅｏｒｙ，  ｔｈｅ  Ｃｈｕｒｃｈ−Ｔｕｒｉｎｇ  ｐｒｉｎｃｉｐｌｅ  ａｎｄ  ｔｈｅ  ｕｎｉｖｅｒｓａｌ  ｑｕａｎｔｕｍ  ｃｏｍｐｕｔｅｒ’，  Ｐｒｏｃ．  Ｒ．  Ｓｏｃ．  Ｌｏｎｄｏｎ，  Ｓｅｒ．  Ａ  ４００，  ９１−１１７  （１９８５）．
【非特許文献５】Ｄ．Ｄｅｕｔｓｃｈ，‘Ｑｕａｎｔｕｍ  ｃｏｍｐｕｔａｔｉｏｎａｌ  ｎｅｔｗｏｒｋｓ’，  Ｐｒｏｃ．  Ｒ．  Ｓｏｃ．  Ｌｏｎｄｏｎ，  Ｓｅｒ．  Ａ  ４２５，  ７３−９０  （１９８９）．
【非特許文献６】Ｄ．Ｄｅｕｔｓｃｈ  ａｎｄ  Ｒ．Ｊｏｚｓａ，‘Ｒａｐｉｄ  ｓｏｌｕｔｉｏｎ  ｏｆ  ｐｒｏｂｌｅｍｓ  ｂｙ  ｑｕａｎｔｕｍ  ｃｏｍｐｕｔａｔｉｏｎ’，  Ｐｒｏｃ．  Ｒ．  Ｓｏｃ．  Ｌｏｎｄｏｎ，  Ｓｅｒ．  Ａ  ４３９，  ５５３−５５８  （１９９２）．
【非特許文献７】Ｄ．Ｒ．Ｓｉｍｏｎ，‘Ｏｎ  ｔｈｅ  ｐｏｗｅｒ  ｏｆ  ｑｕａｎｔｕｍ  ｃｏｍｐｕｔａｔｉｏｎ’，  ＳＩＡＭ  Ｊ．  Ｃｏｍｐｕｔ．  ２６，  １４７４−１４８３  （１９９７）．
【非特許文献８】Ｐ．Ｗ．Ｓｈｏｒ，‘Ｐｏｌｙｎｏｍｉａｌ−ｔｉｍｅ  ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ｐｒｉｍｅ  ｆａｃｔｏｒｉｚａｔｉｏｎ  ａｎｄ  ｄｉｓｃｒｅｔｅ  ｌｏｇａｒｉｔｈｍｓ  ｏｎ  ａ  ｑｕａｎｔｕｍ  ｃｏｍｐｕｔｅｒ’，  ＳＩＡＭ  Ｊ．  Ｃｏｍｐｕｔ．  ２６，  １４８４−１５０９  （１９９７）．
【非特許文献９】Ｌ．Ｋ．Ｇｒｏｖｅｒ，‘Ｑｕａｎｔｕｍ  ｍｅｃｈａｎｉｃｓ  ｈｅｌｐｓ  ｉｎ  ｓｅａｒｃｈｉｎｇ  ｆｏｒ  ａ  ｎｅｅｄｌｅ  ｉｎ  ａ  ｈａｙｓｔａｃｋ’，  Ｐｈｙｓ．  Ｒｅｖ．  Ｌｅｔｔ．  ７９，  ３２５−３２８  （１９９７）．
【非特許文献１０】Ａ．Ｅｋｅｒｔ  ａｎｄ  Ｒ．Ｊｏｚｓａ，‘Ｑｕａｎｔｕｍ  ｃｏｍｐｕｔａｔｉｏｎ  ａｎｄ  Ｓｈｏｒ’ｓ  ｆａｃｔｏｒｉｎｇ  ａｌｇｏｒｉｔｈｍ’，  Ｒｅｖ．  Ｍｏｄ．  Ｐｈｙｓ．  ６８，  ７３３−７５３  （１９９６）．
【非特許文献１１】Ｄ．Ａｈａｒｏｎｏｖ，‘Ｑｕａｎｔｕｍ  ｃｏｍｐｕｔａｔｉｏｎ’，  ｉｎ  Ａｎｎｕａｌ  Ｒｅｖｉｅｗｓ  ｏｆ  Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｐｈｙｓｉｃｓ  ＩＶ，  ｅｄｉｔｅｄ  ｂｙ  Ｄ．  Ｓｔａｕｆｆｅｒ，  （Ｗｏｒｌｄ  Ｓｃｉｅｎｔｉｆｉｃ  Ｐｕｂｌｉｓｈｉｎ  Ｃｏｍｐａｎｙ，  Ｓｉｎｇａｐｏｒｅ，  １９９９），  ｐｐ．  ２５９−３４６．
【非特許文献１２】Ｂ．Ｍ．Ｔｅｒｈａｌ  ａｎｄ  Ｊ．Ａ．Ｓｍｏｌｉｎ，‘Ｓｉｎｇｌｅ  ｑｕａｎｔｕｍ  ｑｕｅｒｙｉｎｇ  ｏｆ  ａ  ｄａｔａｂａｓｅ’，  Ｐｈｙｓ．  Ｒｅｖ．  Ａ  ５８，  １８２２−１８２６  （１９９８）．
【非特許文献１３】Ｇ．Ｂｒａｓｓａｒｄ  ａｎｄ  Ｐ．Ｈｏｙｅｒ，‘Ｏｎ  ｔｈｅ  ｐｏｗｅｒ  ｏｆ  ｅｘａｃｔ  ｑｕａｎｔｕｍ  ｐｏｌｙｎｏｍｉａｌ  ｔｉｍｅ’，  ＬＡＮＬ  ｅ−ｐｒｉｎｔ  ｑｕａｎｔ−ｐｈ／９６１２０１７．
【非特許文献１４】Ｇ．Ｂｒａｓｓａｒｄ  ａｎｄ  Ｐ．Ｈｏｙｅｒ，‘Ａｎ  ｅｘａｃｔ  ｑｕａｎｔｕｍ  ｐｏｌｙｎｏｍｉａｌ−ｔｉｍｅ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  Ｓｉｍｏｎ’ｓ  ｐｒｏｂｌｅｍ’，  ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ５ｔｈ  Ｉｓｒａｅｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  ｔｈｅ  Ｔｈｅｏｒｙ  ｏｆ  Ｃｏｍｐｕｔｉｎｇ  Ｓｙｓｔｅｍｓ  （ＩＳＴＣＳ  ’９７），  （Ｒａｍａｔ−Ｇａｎ，  Ｉｓｒａｅｌ，  Ｊｕｎｅ  １７−１９，  １９９７），  ｐｐ．  １２−２３．
【非特許文献１５】Ｔ．Ｍｉｈａｒａ  ａｎｄ  Ｓ．Ｃ．Ｓｕｎｇ，‘Ａ  ｑｕａｎｔｕｍ  ｐｏｌｙｎｏｍｉａｌ  ｔｉｍｅ  ａｌｇｏｒｉｔｈｍ  ｉｎ  ｗｏｒｓｔ  ｃａｓｅ  ｆｏｒ  Ｓｉｍｏｎ’ｓ  ｐｒｏｂｌｅｍ’，  ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ９ｔｈ  ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ，  ＩＳＡＡＣ  ’９８，  Ｔａｅｊｏｎ，  Ｋｏｒｅａ，  Ｄｅｃｅｍｂｅｒ  １９９８，  ｅｄｉｔｏｒｓ：  Ｋ．−Ｙ．  Ｃｈｗａ  ａｎｄ  Ｏ．Ｈ．  Ｉｂａｒｒａ，  （Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  ｖｏｌ．  １５３３，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ  Ｈｅｉｄｅｌｂｅｒｇ，  １９９８，  ｐｐ．  ２２９−２３６）．
【非特許文献１６】浅野孝夫、今井浩、「計算とアルゴリズム  −計算機の科学−」、オーム社、１９８６．
【非特許文献１７】Ｃ．Ｍ．Ｇｏｌｄｉｅ  ａｎｄ  Ｒ．Ｇ．Ｅ．Ｐｉｎｃｈ，  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  ｔｈｅｏｒｙ，  Ｌｏｎｄｏｎ  Ｍａｔｈｅｍａｔｉｃａｌ  Ｓｏｃｉｅｔｙ  Ｓｔｕｄｅｎｔ  Ｔｅｘｔｓ  ２０  （Ｃａｍｂｒｉｄｇｅ  Ｕｎｉｖｅｒｓｉｔｙ  Ｐｒｅｓｓ，  Ｃａｍｂｒｉｄｇｅ，  １９９１），  Ｓｅｃ．  １．４，  Ｅｘｅｒｃｉｓｅ  ５．
【非特許文献１８】Ｂ．Ｍ．Ｔｅｒｈａｌ  ａｎｄ  Ｊ．Ａ．Ｓｍｏｌｉｎ，‘Ｓｉｎｇｌｅ  ｑｕａｎｔｕｍ  ｑｕｅｒｙｉｎｇ  ｏｆ  ａ  ｄａｔａｂａｓｅ’，  Ｐｈｙｓ．  Ｒｅｖ．  Ａ  ５８，  １８２２−１８２６  （１９９８）．
【発明の開示】
【発明が解決しようとする課題】
【０００９】
計算機の研究分野には、オラクル問題と呼ばれる一群の問題がある。これは、ある未知の関数がｂｌａｃｋ  ｂｏｘ（ｏｒａｃｌｅ）として与えられていると仮定して、このオラクルに適当な入力を与えて、オラクルから返される出力により、未知の関数の性質を調べよ、という問題である。計算効率の観点からすると、なるべく少ない個数の入力で、未知の関数の性質を得ることが望ましい。
【００１０】
このようなオラクル問題は、単なる計算機理論上の抽象的な問題であるだけでなく、実際に技術的な計算をする際、しばしば現れる。例えば、
2006048441.tif 000006
という命題論理式が与えられているとする。この時、Ｐ（ｘ1，ｘ2，ｘ3）＝１となる、（ｘ1，ｘ2，ｘ3）∈｛０，１｝3の組が存在するかどうか判定せよ、という問題を考えてみる。これは、命題論理式の充足可能性に関する問題と呼ばれている（この例は、非特許文献１６によった）。
【００１１】
この場合、最も素朴な解法は、８通りある全ての（ｘ1，ｘ2，ｘ3）∈｛０，１｝3の組を、一つずつ順番にＰ（ｘ1，ｘ2，ｘ3）に代入して、Ｐ（ｘ1，ｘ2，ｘ3）＝１をみたす変数の組があるかどうか探すという方法である。これにより、例えば（ｘ1，ｘ2，ｘ3）＝（１，０，０）のとき、命題がみたされることが分かる。このとき、Ｐ（ｘ1，ｘ2，ｘ3）をオラクルと考えると、この問題はオラクル問題の一種と言えることが分かる。
【００１２】
Ｐ（ｘ1，ｘ2，ｘ3）が式（ａ）のように具体的な数式として与えられているのに、これをオラクルと見なすのは、一見、不合理のようにも思える。式（ａ）の例では、Ｐ（ｘ1，ｘ2，ｘ3）の形は比較的単純で、その式の形から直接的又は解析的に、Ｐ（ｘ1，ｘ2，ｘ3）＝１をみたす変数の組が存在するかどうかが判断できるかもしれない。しかし、変数の数が多く、且つ、Ｐ（ｘ1，．．．，ｘn）が複雑な形をしていれば、式の形から命題論理式を充足する変数の組を逆算することが非常に難しくなり、実際上Ｐ（ｘ1，．．．，ｘn）をオラクルと見なすしかない場合も有り得る。例えば、
2006048441.tif 000007
のように、ｎ変数ｘ1，．．．，ｘn∈｛０，１｝nに対して、３個ずつの変数を∨でつなげた式を、さらに∧でつなげた論理式では、充足可能性問題はＮＰ−完全問題であることが知られている。
【００１３】
もう一つの例として、量子コンピュータで使われるｃｏｎｔｒｏｌゲートが正しく動作しているかを調べる問題を考える。（実験室、工場で構成したｃｏｎｔｒｏｌゲートが実際に正しく動作しているかを確認する作業は、現実社会では必ず必要となる工程である。）量子コンピュータでは次の式で与えられるｃｏｎｔｒｏｌゲートＵfがよく使われる。
2006048441.tif 000008
ただし、ｘ，ｙ∈｛０，１｝n、ｆ：｛０，１｝n→｛０，１｝nとする。Ｕfは、ｎ−ｑｕｂｉｔから成る第１レジスタをコントロール（ｃｏｎｔｒｏｌ）部に、ｎ−ｑｕｂｉｔから成る第２レジスタをターゲット（ｔａｒｇｅｔ）部に持つ量子ゲートである。
【００１４】
このような量子ゲートを物理的に構成するには、例えば、量子ドット、超伝導状態にあるクーパー対、ｃａｖｉｔｙ−ＱＥＤ等の技術を利用した方法が提案されている。しかし、これらの方法はどれも高度な技術を必要としており、実験室、工場等で、実際に量子ゲートを製作した場合、デバイスの製作プロセス、レーザー照射や電流注入による制御過程等で、予想できないミスが生じ易い。このため、動作の不完全な量子ゲートが出来上がってしまうこともしばしばである。従って、作成した量子ゲートの動作を検証することは、産業上、必要な作業と言える。
【００１５】
今、Ｕfが上手く動作しておらず、第１レジスタの一番目のｑｕｂｉｔが他のｑｕｂｉｔと相互作用していないとする。この不完全なゲートＵf'を次のように定義する、
2006048441.tif 000009
ただし、ｘ，ｙ∈｛０，１｝n、ｆ’：｛０，１｝n→｛０，１｝nとなる。さらに、ｆ’（ｘ）はｎ−ｂｉｔ列ｘの一番目のｂｉｔに依存しないので、関数ｆ’は、∀ｘ∈｛０，１｝nに対して、
2006048441.tif 000010
ただし、ｓ＝０１…１という不変性を持つ。
【００１６】
今、不完全なｃｏｎｔｒｏｌゲートＵf'が与えられていて、コントロール（ｃｏｎｔｒｏｌ）部のどのｑｕｂｉｔが他のｑｕｂｉｔと相互作用しないのか分からないとする。（これは、ｎ−ｂｉｔ列ｓが未知ということを意味する。）そこで、Ｕf'のコントロール（ｃｏｎｔｒｏｌ）部である第１レジスタに適当な量子状態を入力し、Ｕf'を動作させて、その出力から、故障しているｑｕｂｉｔを見つけ出すことにする。（ｓを求めることに相当する。）Ｕf'の動作が正確に分かっていないので、これはオラクルと見なせる。よって、以上の過程は、オラクル問題として定式化できる。
【００１７】
Ｕf'の作用する第１レジスタのｑｕｂｉｔ数ｎが非常に大きな数の場合、不具合のあるｑｕｂｉｔを見付け出す作業は煩雑なものとなる。従って、なるべく少ない入力の回数で、不具合のあるｑｕｂｉｔを検出することは、産業上重要な課題といえる。Ｕf'に入力する第１レジスタの状態は、
2006048441.tif 000011
ただし、ｘ∈｛０，１｝nのような、単なる論理基底状態の場合や、
2006048441.tif 000012
のように、複雑な重ね合わせ状態の場合が考えられる。式（ｆ）のような状態を入力することは、オラクルに古典的なｑｕｅｒｙを与えていることに相当する。一方、式（ｇ）のような状態を入力することは、オラクルに量子的なｑｕｅｒｙを与えていることに相当する。
【００１８】
以上の考察から、ｆ（ｘ∧ｓ）＝ｆ（ｘ）という不変性を持つ関数がｂｌａｃｋ  ｂｏｘ（ｏｒａｃｌｅ）として与えられたとして、なるべく少ないｑｕｅｒｙ数でｓを求める量子計算方法を考えることは、産業上、重要であることが理解される。また、これに類似した問題として、ｇ（ｘ∨ｓ）＝ｇ（ｘ）という不変性を持つ関数がｂｌａｃｋ  ｂｏｘ（ｏｒａｃｌｅ）として与えられたとして、なるべく少ないｑｕｅｒｙ数でｓを求めよという問題が考えられる。
【００１９】
本明細書では、第一の問題として、ｆ：｛０，１｝n→｛０，１｝nで、ｆ（ｘ∧ｓ）＝ｆ（ｘ）という不変性を持つ関数がｂｌａｃｋ  ｂｏｘ（ｏｒａｃｌｅ）として与えられているとして、ｓを求めよ、という問題について検討する。ただし、ｓがどのようなｂｉｔ列かは知らないが、ｓのＨａｍｍｉｎｇ重みはｗｔ（ｓ）＝ｍとして与えられているとする（∧は二つのｎ−ｂｉｔ列の、ｂｉｔ毎のＡＮＤ操作とする。また、１≦ｍ≦ｎ−１とする。後で示されることだが、ｆは２n-m−ｔｏ−ｏｎｅ  ｆｕｎｃｔｉｏｎとなっている。）。
【００２０】
また、本明細書では、第二の問題として、ｇ：｛０，１｝n→｛０，１｝nで、ｇ（ｘ∨ｓ）＝ｇ（ｘ）という不変性を持つ関数がｂｌａｃｋ  ｂｏｘ（ｏｒａｃｌｅ）として与えられているとして、ｓを求めよ、という問題について検討する。ただし、ｓがどのようなｂｉｔ列かは知らないが、ｓのＨａｍｍｉｎｇ重みはｗｔ（ｓ）＝ｎ−ｍとして与えられているとする（∨は二つのｎ−ｂｉｔ列の、ｂｉｔ毎のＯＲ操作とする。また、１≦ｍ≦ｎ−１とする。後で示されることだが、ｇは２n-m−ｔｏ−ｏｎｅ  ｆｕｎｃｔｉｏｎとなっている。）。
【００２１】
以上の問題を、できるだけ少ないｂｌａｃｋ  ｂｏｘ（ｏｒａｃｌｅ）へのｑｕｅｒｙ数で、解くことについて検討する。本発明は、所定の古典アルゴリズムより少ないｑｕｅｒｙ数で問題を解く量子計算方法及び装置を提供することを目的とする。
【００２２】
また、本明細書では、第三の問題として、互いに遠く離れた場所にある二つの量子計算機（ＡｌｉｃｅとＢｏｂ）が量子通信回線によって量子情報を交換しながら互いに協力し合って問題を解く場合について検討する。Ａｌｉｃｅ，Ｂｏｂが解く問題は次のようなものである。即ち、Ａｌｉｃｅにはｆ：｛０，１｝n→｛０，１｝n又はｇ：｛０，１｝n→｛０，１｝nでｆ（ｘ）＝ｆ（ｘ∧ｓ）又はｇ（ｘ）＝ｇ（ｘ∨ｓ）という不変性を持つ未知の関数がブラックボックス（オラクル）として与えられているとし、Ｂｏｂにはｎ−ｂｉｔ列ｓのＨａｍｍｉｎｇ重みが与えられているとする。Ｂｏｂがｓを求めるのにはどうすれば良いか。
【００２３】
以上の問題を、できるだけ少ないＡｌｉｃｅ、Ｂｏｂ間の通信回数で、解くことについて検討する。ただし、Ａｌｉｃｅは、オラクルによる操作以外、どのような演算操作も行わないとする。本発明は、所定の古典アルゴリズムより少ないｑｕｅｒｙ数で問題を解く量子計算方法及び装置を提供することを目的とする。
【００２４】
さらに、第四の問題として、第一、第二、第三の問題で考え出される量子計算方法を、ｃｏｎｔｒｏｌゲートの不具合を調べることに利用する方法について検討する。
【課題を解決するための手段】
【００２５】
上記第一、第二の問題を解くため、本願発明は、ｎ個の二状態系（ｑｕｂｉｔ）｛｜０＞，｜１＞｝から成るレジスタを二つ用意し、２ｎ個全てのｑｕｂｉｔを｜０＞状態に初期化し、第１レジスタにＨａｄａｍａｒｄ変換を作用させて均一な重ね合わせ状態を構成し、前のブラックボックスｆ又はｇに相当するユニタリ変換を第１、第２レジスタに作用させて、第１レジスタが｜ｘ＞のとき第２レジスタが｜ｆ（ｘ）＞又は｜ｇ（ｘ）＞となるような量子もつれ合いを二つのレジスタ間に生じさせ、再度、第１レジスタにＨａｄａｍａｒｄ変換を作用させて、第１レジスタを基底｛｜ｘ＞：ｘ∈｛０，１｝n｝で観測し、その観測値からｓを求める量子計算方法を用いることを特徴とする。
【００２６】
また、上記第一の問題の、ｆ（ｘ∧ｓ）＝ｆ（ｘ）という不変性を持つ関数ｆに関する問題を解くため、本願発明は、一回目の量子計算方法の試行でｎ−ｂｉｔ列ｋが得られたとして、ｗｔ（ｋ）＝ｍならばｓ＝ｋ、ｗｔ（ｋ）＜ｍならばｋをｋoldとして二回目の試行（量子計算方法）を実行し、新たに得られたｎ−ｂｉｔ列をｋnewとし、ｋ＝ｋold∨ｋnewとして、ｗｔ（ｋ）＝ｍならばｓ＝ｋ、ｗｔ（ｋ）＜ｍならば再度試行を行う、という過程をｗｔ（ｋ）＝ｍになるまで繰り返すことによって、ｎ−ｂｉｔ列ｓを求めることを特徴とする。
【００２７】
また、上記第二の問題の、ｇ（ｘ∨ｓ）＝ｇ（ｘ）という不変性を持つ関数ｇに関する問題を解くため、本願発明は、一回目の量子計算方法の試行でｎ−ｂｉｔ列ｋが得られたとして、
2006048441.tif 000013
ならば
2006048441.tif 000014
、
2006048441.tif 000015
ならばｋをｋoldとして二回目の試行（量子計算方法）を実行し、新たに得られたｎ−ｂｉｔ列をｋnewとし、
2006048441.tif 000016
として、
2006048441.tif 000017
ならば
2006048441.tif 000018
、
2006048441.tif 000019
ならば再度試行を行う、という過程を
2006048441.tif 000020
になるまで繰り返すことによって、ｎ−ｂｉｔ列ｓを求めることを特徴とする。
【００２８】
また、上記第三の問題を解くため、本願発明は、ＡｌｉｃｅとＢｏｂは各自ｎ−ｑｕｂｉｔから成るレジスタを用意し、二人は２ｎ個全てのｑｕｂｉｔを｜０＞状態に初期化し、Ｂｏｂは自分のｎ−ｑｕｂｉｔにＨａｄａｍａｒｄ変換を作用させて均一な重ね合わせ状態を構成して、それをＡｌｉｃｅに送り、ＡｌｉｃｅはＢｏｂから受け取ったｎ−ｑｕｂｉｔを第１レジスタ、自分の用意したｎ−ｑｕｂｉｔを第２レジスタとし、前のブラックボックスｆ又はｇに相当するユニタリ変換を第１、第２レジスタに作用させて、第１レジスタが｜ｘ＞のとき第２レジスタが｜ｆ（ｘ）＞又は｜ｇ（ｘ）＞となるような量子もつれ合いを二つのレジスタ間に生じさせ、第１レジスタのｎ−ｑｕｂｉｔをＢｏｂに送り返し、Ｂｏｂは受け取ったｎ−ｑｕｂｉｔに再度Ｈａｄａｍａｒｄ変換を作用させて基底｛｜ｘ＞：ｘ∈｛０，１｝n｝で観測し、その観測値からｓを求める分散量子計算を行うことを特徴とする。
【００２９】
さらに、Ａｌｉｃｅにｆ：｛０，１｝n→｛０，１｝nでｆ（ｘ）＝ｆ（ｘ∧ｓ）という不変性を持つ未知の関数がブラックボックス（オラクル）として与えられていて、且つ、Ｂｏｂにｎ−ｂｉｔ列ｓのＨａｍｍｉｎｇ重みがｗｔ（ｓ）＝ｍと与えられているとして、Ａｌｉｃｅ、Ｂｏｂの間で量子情報をやり取りすることで、Ｂｏｂがｓを求めよ、という問題を解くため、本出願の発明は、一回目の試行でＢｏｂがｎ−ｂｉｔ列ｋを得たとして、ｗｔ（ｋ）＝ｍならばｓ＝ｋ、ｗｔ（ｋ）＜ｍならばｋをｋoldとして二回目の試行を実行し、新たにＢｏｂが得たｎ−ｂｉｔ列をｋnewとし、ｋ＝ｋold∨ｋnewとして、ｗｔ（ｋ）＝ｍならばｓ＝ｋ、ｗｔ（ｋ）＜ｍならば再度試行を行う、という過程をｗｔ（ｋ）＝ｍになるまで繰り返すことによって、Ｂｏｂがｎ−ｂｉｔ列ｓを求めることを特徴とする。
【００３０】
さらに、Ａｌｉｃｅにｇ：｛０，１｝n→｛０，１｝nでｇ（ｘ）＝ｇ（ｘ∨ｓ）という不変性を持つ未知の関数がブラックボックス（オラクル）として与えられていて、且つ、Ｂｏｂにｎ−ｂｉｔ列ｓのＨａｍｍｉｎｇ重みがｗｔ（ｓ）＝ｎ−ｍと与えられているとして、Ａｌｉｃｅ、Ｂｏｂの間で量子情報をやり取りすることで、Ｂｏｂがｓを求めよ、という問題を解くため、本出願の発明は、一回目の試行でＢｏｂがｎ−ｂｉｔ列ｋを得たとして、
2006048441.tif 000021
ならば
2006048441.tif 000022
、
2006048441.tif 000023
ならばｋをｋoldとして二回目の試行を実行し、新たにＢｏｂが得たｎ−ｂｉｔ列をｋnewとし、
2006048441.tif 000024
として、
2006048441.tif 000025
ならば
2006048441.tif 000026
、
2006048441.tif 000027
ならば再度試行を行う、という過程を
2006048441.tif 000028
になるまで繰り返すことによって、Ｂｏｂがｎ−ｂｉｔ列ｓを求めることを特徴とする。
【００３１】
また、本発明の分散量子計算実行方法では、一方は複数のｑｕｂｉｔに対するユニタリ変換を実行する技術を持っているが、他方は１−ｑｕｂｉｔに対するユニタリ変換を実行する技術しか持っていないペアが、協力し合って問題を解くことを特徴とする。
【００３２】
本発明の量子ゲート故障診断方法は、上記第四の問題を解決するために、前述の本発明の量子計算方法、分散量子計算実行方法を用いて、ｃｏｎｔｒｏｌゲートの不具合を調べることを特徴とする。
【発明の効果】
【００３３】
本発明の量子計算方法（アルゴリズム）は、ｆ：｛０，１｝n→｛０，１｝nでｆ（ｘ）＝ｆ（ｘ∧ｓ）という不変性を持つ関数がｂｌａｃｋ  ｂｏｘ（ｏｒａｃｌｅ）として与えられていて、且つ、ｗｔ（ｓ）＝ｍが与えられた場合、平均でおよそ（２＋ｌｏｇ2ｍ）個のｑｕｅｒｙでｓを見出す。特に、ｗｔ（ｓ）＝１の場合、ｓを見出すのに必要な平均ｑｕｅｒｙ数は正確に２である。
【００３４】
一方、古典コンピュータでこの問題を解く場合、ｑｕｅｒｙ数の期待値の下限は、ｗｔ（ｓ）＝１ならば
2006048441.tif 000029
、ｗｔ（ｓ）＝ｎ−１ならば（１／２）［ｎ＋１−（２／ｎ）］＋１で与えられる。従って、ｗｔ（ｓ）＝１及びｗｔ（ｓ）＝ｎ−１の場合は、本発明の量子アルゴリズムが、所定の古典アルゴリズムよりも効率的である。このように本発明の量子アルゴリズムは計算量を低く抑えるという点で効果がある。
【００３５】
また、本発明の量子アルゴリズムは、ｇ：｛０，１｝n→｛０，１｝nでｇ（ｘ）＝ｇ（ｘ∨ｓ）という不変性を持つ関数がｂｌａｃｋ  ｂｏｘ（ｏｒａｃｌｅ）として与えられていて、且つ、ｗｔ（ｓ）＝ｎ−ｍが与えられた場合、平均でおよそ（２＋ｌｏｇ2ｍ）個のｑｕｅｒｙでｓを見出す。特に、ｗｔ（ｓ）＝ｎ−１の場合、ｓを見出すのに必要な平均ｑｕｅｒｙ数は正確に２である。
【００３６】
一方、古典コンピュータでこの問題を解く場合、ｑｕｅｒｙ数の期待値の下限は、ｗｔ（ｓ）＝ｎ−１の場合
2006048441.tif 000030
、ｗｔ（ｓ）＝１の場合（１／２）［ｎ＋１−（２／ｎ）］＋１で与えられる。従って、ｗｔ（ｓ）＝ｎ−１及びｗｔ（ｓ）＝１の場合は、本発明の量子アルゴリズムが、所定の古典アルゴリズムよりも効率的である。このように本発明の量子アルゴリズムは計算量を低く抑えるという点で効果がある。
【００３７】
また、本発明の量子計算アルゴリズムは、状態の重ね合わせと干渉、量子もつれ合いを使っており、量子アルゴリズムと呼ぶのにふさわしい性質を持っている。さらに、本発明の量子計算アルゴリズムは、オラクルとして与えられた関数（ｆ又はｇ）の局所的性質を無視して、関数の大域的性質のみを効率的に取り出すことができる。これは古典アルゴリズムには見られない性質である。
【００３８】
また、本発明の分散量子計算実行方法では、地理的に遠く離れた二つの量子コンピュータ（ＡｌｉｃｅとＢｏｂ）が、少ない量子情報の交換によって、Ａｌｉｃｅに与えられたオラクルの性質をＢｏｂが調べる（ｆ（ｘ）＝ｆ（ｘ∧ｓ）又はｇ（ｘ）＝ｇ（ｘ∨ｓ）という不変性を持つ未知の関数のｓをＢｏｂが求める）ことを可能にする。
【００３９】
また、本発明の分散量子計算実行方法では、一方は複数のｑｕｂｉｔに対するユニタリ変換を実行する技術を持っているが、他方は１−ｑｕｂｉｔに対するユニタリ変換を実行する技術しか持っていないペアが、協力し合って問題を解くことができる。
【００４０】
また、本発明の量子ゲート故障診断方法では、与えられたｃｏｎｔｒｏｌゲートの、コントロール部（第１レジスタ）のいくつかのｑｕｂｉｔが他のｑｕｂｉｔと相互作用出来ないという不具合がある際に、この不具合のあるｑｕｂｉｔを効率的に特定することができる。
【００４１】
本出願に係る第１の発明は、ｆ：｛０，１｝n→｛０，１｝n又はｇ：｛０，１｝n→｛０，１｝nでｆ（ｘ）＝ｆ（ｘ∧ｓ）又はｇ（ｘ）＝ｇ（ｘ∨ｓ）という不変性を持つ未知の関数がブラックボックス（オラクル）として与えられていて、且つ、ｎ−ｂｉｔ列ｓのＨａｍｍｉｎｇ重みが与えられているとして、このブラックボックスに適当な入力値を与えてその出力値からｓを求める問題を解くために、ｎ個の二状態系（ｑｕｂｉｔ）｛｜０＞，｜１＞｝から成るレジスタを二つ用意し、２ｎ個全てのｑｕｂｉｔを｜０＞状態に初期化し、第１レジスタにＨａｄａｍａｒｄ変換を作用させて均一な重ね合わせ状態を構成し、前のブラックボックスｆ又はｇに相当するユニタリ変換を第１、第２レジスタに作用させて、第１レジスタが｜ｘ＞のとき第２レジスタが｜ｆ（ｘ）＞又は｜ｇ（ｘ）＞となるような量子もつれ合いを二つのレジスタ間に生じさせ、再度、第１レジスタにＨａｄａｍａｒｄ変換を作用させて、第１レジスタを基底｛｜ｘ＞：ｘ∈｛０，１｝n｝で観測し、その観測値からｓを求める量子計算アルゴリズムを実現することができる。
【００４２】
本出願に係る第２の発明は、ｆ：｛０，１｝n→｛０，１｝nでｆ（ｘ）＝ｆ（ｘ∧ｓ）という不変性を持つ未知の関数がブラックボックス（オラクル）として与えられていて、且つ、ｎ−ｂｉｔ列ｓのＨａｍｍｉｎｇ重みがｗｔ（ｓ）＝ｍと与えられているとして、ｓを求めよ、という問題を解く量子アルゴリズムにおいて、一回目の量子アルゴリズムの試行でｎ−ｂｉｔ列ｋが得られたとして、ｗｔ（ｋ）＝ｍならばｓ＝ｋ、ｗｔ（ｋ）＜ｍならばｋをｋoldとして二回目の試行（量子アルゴリズム）を実行し、新たに得られたｎ−ｂｉｔ列をｋnewとし、ｋ＝ｋold∨ｋnewとして、ｗｔ（ｋ）＝ｍならばｓ＝ｋ、ｗｔ（ｋ）＜ｍならば再度試行を行う、という過程をｗｔ（ｋ）＝ｍになるまで繰り返すことによって、ｎ−ｂｉｔ列ｓを求めることを特徴とする量子計算アルゴリズムを実現することができる。
【００４３】
本出願に係る第３の発明は、ｇ：｛０，１｝n→｛０，１｝nでｇ（ｘ）＝ｇ（ｘ∨ｓ）という不変性を持つ未知の関数がブラックボックス（オラクル）として与えられていて、且つ、ｎ−ｂｉｔ列ｓのＨａｍｍｉｎｇ重みがｗｔ（ｓ）＝ｎ−ｍと与えられているとして、ｓを求めよ、という問題を解く量子アルゴリズムにおいて、一回目の量子アルゴリズムの試行でｎ−ｂｉｔ列ｋが得られたとして、
2006048441.tif 000031
ならば
2006048441.tif 000032
、
2006048441.tif 000033
ならばｋをｋ＝ｋoldとして二回目の試行（量子アルゴリズム）を実行し、新たに得られたｎ−ｂｉｔ列をｋ＝ｋnewとし、
2006048441.tif 000034
として、
2006048441.tif 000035
ならば
2006048441.tif 000036
、
2006048441.tif 000037
ならば再度試行を行う、という過程を
2006048441.tif 000038
になるまで繰り返すことによって、ｎ−ｂｉｔ列ｓを求めることを特徴とする量子計算アルゴリズムを実現することができる。
【００４４】
本出願に係る第４の発明は、互いに遠く離れた場所にある二つの量子計算機（ＡｌｉｃｅとＢｏｂ）が量子通信回線によって量子情報を交換しながら互いに協力し合って問題を解く際に、Ａｌｉｃｅにはｆ：｛０，１｝n→｛０，１｝n又はｇ：｛０，１｝n→｛０，１｝nでｆ（ｘ）＝ｆ（ｘ∧ｓ）又はｇ（ｘ）＝ｇ（ｘ∨ｓ）という不変性を持つ未知の関数がブラックボックス（オラクル）として与えられていて、Ｂｏｂにはｎ−ｂｉｔ列ｓのＨａｍｍｉｎｇ重みが与えられているとして、Ｂｏｂが適当な量子状態にある複数のｑｕｂｉｔをＡｌｉｃｅに送り、Ａｌｉｃｅはその複数のｑｕｂｉｔの状態を与えられたブラックボックスで変換してＢｏｂに送り返し、Ｂｏｂはそのｑｕｂｉｔを観測してｓを求める問題を解くために、ＡｌｉｃｅとＢｏｂは各自ｎ−ｑｕｂｉｔから成るレジスタを用意し、二人は２ｎ個全てのｑｕｂｉｔを｜０＞状態に初期化し、Ｂｏｂは自分のｎ−ｑｕｂｉｔにＨａｄａｍａｒｄ変換を作用させて均一な重ね合わせ状態を構成して、それをＡｌｉｃｅに送り、ＡｌｉｃｅはＢｏｂから受け取ったｎ−ｑｕｂｉｔを第１レジスタ、自分の用意したｎ−ｑｕｂｉｔを第２レジスタとし、前のブラックボックスｆ又はｇに相当するユニタリ変換を第１、第２レジスタに作用させて、第１レジスタが｜ｘ＞のとき第２レジスタが｜ｆ（ｘ）＞又は｜ｇ（ｘ）＞となるような量子もつれ合いを二つのレジスタ間に生じさせ、第１レジスタのｎ−ｑｕｂｉｔをＢｏｂに送り返し、Ｂｏｂは受け取ったｎ−ｑｕｂｉｔに再度Ｈａｄａｍａｒｄ変換を作用させて基底｛｜ｘ＞：ｘ∈｛０，１｝n｝で観測し、その観測値からｓを求める分散量子計算実行方法を実現することができる。
【００４５】
本出願に係る第５の発明は、Ａｌｉｃｅにｆ：｛０，１｝n→｛０，１｝nでｆ（ｘ）＝ｆ（ｘ∧ｓ）という不変性を持つ未知の関数がブラックボックス（オラクル）として与えられていて、且つ、Ｂｏｂにｎ−ｂｉｔ列ｓのＨａｍｍｉｎｇ重みがｗｔ（ｓ）＝ｍと与えられているとして、Ａｌｉｃｅ、Ｂｏｂの間で量子情報をやり取りすることで、Ｂｏｂがｓを求めよ、という問題を解く状況において、一回目の試行でＢｏｂがｎ−ｂｉｔ列ｋを得たとして、ｗｔ（ｋ）＝ｍならばｓ＝ｋ、ｗｔ（ｋ）＜ｍならばｋをｋoldとして二回目の試行を実行し、新たにＢｏｂが得たｎ−ｂｉｔ列をｋnewとし、ｋ＝ｋold∨ｋnewとして、ｗｔ（ｋ）＝ｍならばｓ＝ｋ、ｗｔ（ｋ）＜ｍならば再度試行を行う、という過程をｗｔ（ｋ）＝ｍになるまで繰り返すことによって、Ｂｏｂがｎ−ｂｉｔ列ｓを求めることを特徴とする分散量子計算実行方法を実現することができる。
【００４６】
本出願に係る第６の発明は、Ａｌｉｃｅにｇ：｛０，１｝n→｛０，１｝nでｇ（ｘ）＝ｇ（ｘ∨ｓ）という不変性を持つ未知の関数がブラックボックス（オラクル）として与えられていて、且つ、Ｂｏｂにｎ−ｂｉｔ列ｓのＨａｍｍｉｎｇ重みがｗｔ（ｓ）＝ｎ−ｍと与えられているとして、Ａｌｉｃｅ、Ｂｏｂの間で量子情報をやり取りすることで、Ｂｏｂがｓを求めよ、という問題を解く状況において、一回目の試行でＢｏｂがｎ−ｂｉｔ列ｋを得たとして、
2006048441.tif 000039
ならば
2006048441.tif 000040
、
2006048441.tif 000041
ならばｋをｋoldとして二回目の試行を実行し、新たにＢｏｂが得たｎ−ｂｉｔ列をｋnewとし、
2006048441.tif 000042
として、
2006048441.tif 000043
ならば
2006048441.tif 000044
、
2006048441.tif 000045
ならば再度試行を行う、という過程を
2006048441.tif 000046
になるまで繰り返すことによって、Ｂｏｂがｎ−ｂｉｔ列ｓを求めることを特徴とする分散量子計算実行方法を実現することができる。
【００４７】
本出願に係る第７の発明は、一方は複数のｑｕｂｉｔに対するユニタリ変換を実行する技術を持っているが、他方は１−ｑｕｂｉｔに対するユニタリ変換を実行する技術しか持っていないペアが、協力し合って問題を解くことを特徴とする分散量子計算実行方法を実現することができる。
【００４８】
本出願に係る第８の発明は、本発明の量子計算アルゴリズム実行装置を利用することによって、複数のｑｕｂｉｔから成るコントロール部及びターゲット部を持つ量子ｃｏｎｔｒｏｌゲートにおいて、コントロール部のいくつかのｑｕｂｉｔが他のｑｕｂｉｔと相互作用出来ないという不具合を持つ際に、不具合を持つｑｕｂｉｔを効率的に特定する量子ゲート故障診断方法を実現することができる。
【００４９】
本出願に係る第９の発明は、本発明の分散量子計算実行方法を利用することによって、Ａｌｉｃｅの保持する複数のｑｕｂｉｔから成るコントロール部及びターゲット部を持つ量子ｃｏｎｔｒｏｌゲートにおいて、コントロール部のいくつかのｑｕｂｉｔが他のｑｕｂｉｔと相互作用出来ないという不具合を持つ際に、Ａｌｉｃｅ、Ｂｏｂ間で量子情報をやり取りすることで、ＢｏｂがＡｌｉｃｅの保持する量子ゲートの、不具合を持つｑｕｂｉｔを効率的に特定する量子ゲート故障診断方法を実現することができる。
【発明を実施するための最良の形態】
【００５０】
各実施形態の構成は次の通りである。即ち、第１実施形態では、本発明で議論される問題を定義し、それに対する量子アルゴリズムを書き下す。さらに、そのアルゴリズムがどのようにして問題を解くかを述べる。第２実施形態では、第１実施形態で示された量子アルゴリズムのオラクルに対するｑｕｅｒｙ数の期待値を評価する。第３実施形態では、第１実施形態で定義された問題に対する所定の古典アルゴリズムのｑｕｅｒｙ数の期待値の下限を、ｗｔ（ｓ）＝１及びｗｔ（ｓ）＝ｎ−１の場合について調べる。第４実施形態では、２≦ｗｔ（ｓ）≦ｎ−２の場合について、二つの典型的な古典アルゴリズムのｑｕｅｒｙ数の期待値を調べる。第５実施形態では、ＯＲ−マスクに対して不変な関数を調べる量子アルゴリズムを議論する。第６実施形態では、第１実施形態で示された量子アルゴリズムを、遠く離れた二つのコンピュータが情報を交換し合うことによって協力して問題を解く分散量子計算実行方法（分散コンピューティング）に応用する方法について述べる。第７実施形態では、第１実施形態で示された量子アルゴリズム及び第６実施形態で示された量子分散コンピューティングを利用して、ｃｏｎｔｒｏｌゲートの不具合を調べる方法を説明する。
【００５１】
［第１実施形態］
本実施形態では、全体を通じて議論する問題を与え、それに対する量子アルゴリズムを示し、そして、その量子アルゴリズムがどのように問題を解くかを説明する。
【００５２】
まず、次の準備をする。所定の二つのｎ−ｂｉｔ列∀ａ，ｂ∈｛０，１｝nを考える。（ａ＝ａ1ａ2．．．ａnとして、ａi∈｛０，１｝  ｆｏｒ  ｉ＝１，．．．，ｎということ。ｂについても同様とする。）ａ，ｂのｂｉｔ毎のＡＮＤ操作（ｂｉｔｗｉｓｅ  ＡＮＤ）をｃ＝ａ∧ｂ∈｛０，１｝nと書き、ｃのｉ番目の成分をｃi＝ａiｂi  ｆｏｒ  ｉ＝１，．．．，ｎと定義する。ａ，ｂのｂｉｔ毎のＯＲ操作（ｂｉｔｗｉｓｅ  ＯＲ）をｃ＝ａ∨ｂ∈｛０，１｝nと書き、ｃのｉ番目の成分をｃi＝ｍａｘ（ａi，ｂi）  ｆｏｒ  ｉ＝１，．．．，ｎと定義する。また、ａ，ｂのｂｉｔ毎のｅｘｃｌｕｓｉｖｅ−ｏｒ操作（ｂｉｔｗｉｓｅ  ｅｘｃｌｕｓｉｖｅ−ｏｒ）を
2006048441.tif 000047
と書き、ｃのｉ番目の成分をｃi＝ａi＋ｂi（ｍｏｄｕｌｏ  ２）  ｆｏｒ  ｉ＝１，．．．，ｎと定義する。さらに、ａ，ｂの内積を、
2006048441.tif 000048
（ｍｏｄｕｌｏ  ２）と定義する。また、ａ中のｂｉｔ値‘１’の立っている桁の全個数をａのＨａｍｍｉｎｇ重みと呼び、ｗｔ（ａ）で表す。（明らかに、０≦ｗｔ（ａ）≦ｎである。）ａの各ｂｉｔを
2006048441.tif 000049
と反転させたものを
2006048441.tif 000050
と書く。全てのｂｉｔ値が‘０’であるｎ−ｂｉｔ列をｓ0又は太字の０（＝０．．．０）、全てのｂｉｔ値が‘１’であるｎ−ｂｉｔ列をｓ1又は太字の１（＝１．．．１）と表すことにする。この時、
2006048441.tif 000051
，
2006048441.tif 000052
が成り立つ。
【００５３】
ｑｕｂｉｔと呼ばれる二状態系｛｜０＞，｜１＞｝をいくつか用意し、これら複数のｑｕｂｉｔから成る系の上の状態を考える。量子計算とは、この系の状態に、連続的にユニタリ変換、観測を行うことである。次の二つのユニタリ変換を定義する。一つ目はＨａｄａｍａｒｄ変換Ｈで、１−ｑｕｂｉｔに対して次のように作用する。
2006048441.tif 000053
2006048441.tif 000054
は、ｎ−ｑｕｂｉｔの状態｜ｘ＞＝｜ｘ1＞．．．｜ｘn＞（ｘ∈｛０，１｝n）を次のように変換する、
2006048441.tif 000055
二つ目は関数ｆ：｛０，１｝n→｛０，１｝nのオラクルを表すユニタリ演算子Ｕfで、次のように作用する。
2006048441.tif 000056
ただし、∀ｘ，ｙ∈｛０，１｝nとする。
【００５４】
問題を次のように定義する。
【００５５】
［問題］
関数ｆ：｛０，１｝n→｛０，１｝nが与えられていて、ｆ（ｘ）＝ｆ（ｙ）となるのは、ｙ＝ｘ又はｙ＝ｘ∧ｓのとき、且つ、そのときに限るとする。ｗｔ（ｓ）＝ｍは与えられているが、ｓがどのようなｂｉｔ列かは知らないとする。ｓを求めよ。
【００５６】
この問題では、ｗｔ（ｓ）＝０ならばｓ＝ｓ0、ｗｔ（ｓ）＝ｎならばｓ＝ｓ1であることが即座に分かる。従って、これらの場合は除くことにする。（ｓ≠ｓ0，ｓ1）後で説明するが、実は関数ｆは２n-m−ｔｏ−ｏｎｅ  ｆｕｎｃｔｉｏｎとなっている。
以下の量子アルゴリズムを考える。
【００５７】
［アルゴリズム］
１．ｎ−ｑｕｂｉｔから成る二つのレジスタを用意し、各ｑｕｂｉｔを
2006048441.tif 000057
に初期化しておく。状態
2006048441.tif 000058
が得られる。
【００５８】
２．第１レジスタのｎ個のｑｕｂｉｔ各々にＨａｄａｍａｒｄ変換Ｈを作用させる。式（２）により、次の状態が得られる、
2006048441.tif 000059
（ここで簡単のため、第２レジスタの
2006048441.tif 000060
を
2006048441.tif 000061
と書いた）。
【００５９】
３．与えられたｂｌａｃｋ  ｂｏｘ（ｏｒａｃｌｅ）Ｕfを作用させて、第１レジスタのｘの値に応じて第２レジスタにｆ（ｘ）を書き込む。これにより、次の状態が得られる、
2006048441.tif 000062
。
【００６０】
４．再び第１レジスタのｎ個のｑｕｂｉｔの各々にＨａｄａｍａｒｄ変換Ｈを作用させる。次の状態を得る、
2006048441.tif 000063
。
【００６１】
５．第１レジスタを、論理ケットベクトル（ｌｏｇｉｃａｌ  ｋｅｔ  ｖｅｃｔｏｒｓ）｛｜ｘ＞：ｘ∈｛０，１｝n｝を基底として観測する。｜ｋ＞が得られたとする。ｗｔ（ｋ）＝ｍならばｓ＝ｋとする。ｗｔ（ｋ）＜ｍならば、再度、第１ステップから第４ステップの操作を行い、第１レジスタを観測する。一回目の観測で得られたｋをｋoldと書き、二回目の観測で得られたｂｉｔ列をｋnewとして、
2006048441.tif 000064
を求める。ｗｔ（ｋ）＝ｍならばｓ＝ｋとする。ｗｔ（ｋ）＜ｍならば再びｋをｋoldとして、第１ステップから第４ステップの操作を行いｋnewを得て、ｋ＝ｋold∨ｋnewを作る。これらの過程をｗｔ（ｋ）＝ｍとなるまで繰り返す。ｗｔ（ｋ）＝ｍのときｓ＝ｋでｓを得たことになる。
【００６２】
上に示したアルゴリズムによってｓが得られる理由を説明する。まず、次の点に注目する。ｆ（ｘ）＝ｆ（ｙ）となるのは、ｙ＝ｘ又はｙ＝ｘ∧ｓのとき、且つ、そのときに限られていて、また、ｗｔ（ｓ）＝ｍが与えられている。よって、ｆは２n-m−ｔｏ−ｏｎｅ  ｆｕｎｃｔｉｏｎである。これは、ｂｉｔ列ｓの‘０’の桁の総数が（ｎ−ｍ）で、関数ｆはその（ｎ−ｍ）個の桁の値に依存しないからである。従って、２n個のｆの入力ｘ∈｛０，１｝nは、ｆ（ｘ）の値によって２m個の組に分類される。各組に含まれるｘの個数が２n-mとなる。
【００６３】
これより、式（５）で示される、アルゴリズムの第３ステップ終了後のレジスタは次のように書き換えられる、
2006048441.tif 000065
式（８）でｂｉｔ列ｌは、ｓのｂｉｔ値‘０’が立っている桁は‘０’、ｓのｂｉｔ値‘１’が立っている桁は‘０’又は‘１’がランダムに割り当てられる。従ってｌは２m種類ある。また、ｂｉｔ列ａは、
2006048441.tif 000066
のｂｉｔ値‘０’が立っている桁は‘０’、
2006048441.tif 000067
のｂｉｔ値‘１’が立っている桁は‘０’又は‘１’がランダムに割り当てられる。（言い換えると、ｂｉｔ列ａは、ｓのｂｉｔ値‘１’が立っている桁は‘０’、ｓのｂｉｔ値‘０’が立っている桁は‘０’又は‘１’がランダムに割り当てられる。）従ってａは２n-m種類ある。
【００６４】
次に、式（８）に、アルゴリズムの第４ステップとして、第１レジスタの各ｑｕｂｉｔにＨを作用させる。ここで、第１レジスタの
2006048441.tif 000068
について考える。ｎ−ｂｉｔ列ｓのｂｉｔ値‘０’が立っている桁を左端に、ｂｉｔ値‘１’が立っている桁を右端に寄せるように、ｎ個のｑｕｂｉｔを置換して順序を変えることにする。Ｈは各ｑｕｂｉｔに独立に作用するので、このような置換は議論の本質を変えることはない。
2006048441.tif 000069
は次のように書き換えられる、
2006048441.tif 000070
ただし、ｌ’はｎ−ｂｉｔ列ｌを置換した後、左端の（ｎ−ｍ）個のｂｉｔ値‘０’を取り除いたものである。｜ａ＞は（ｎ−ｍ）−ｑｕｂｉｔ状態、｜ｌ’＞はｍ−ｑｕｂｉｔ状態となる。
【００６５】
式（９）の状態に
2006048441.tif 000071
を作用させる。式（２）より、先頭の（ｎ−ｍ）−ｑｕｂｉｔ状態
2006048441.tif 000072
は｜０＞n-mに変換されることが分かる。従って、式（９）は次の状態に変換される、
2006048441.tif 000073
式（１０）の状態のｑｕｂｉｔを置換して元の順序にすると、第１、第２レジスタ全体として次の状態が得られる、
2006048441.tif 000074
。
【００６６】
次に、第１レジスタを｛｜ｘ＞：ｘ∈｛０，１｝n｝基底によって測定する。これにより、ｂｉｔ列ｋ、ただし、ｋ＝ｙ∧ｓ，ｙ∈｛０，１｝nが得られる。ｋは２m種類あって、そのうちのどれが得られるかは全くランダムである。ｋは、ｂｉｔ列ｓのｂｉｔ値‘１’の立っている桁に‘０’か‘１’がランダムに割り当てられ、ｂｉｔ列ｓのｂｉｔ値‘０’が立っている桁は‘０’となっている。従って、アルゴリズムを繰り返して何度もｋを観測し、それらを式（７）のようにｂｉｔ毎のＯＲ操作で足し合わせていくと、いつかはｓが得られるはずである。式（１１）では、第１レジスタのｂｉｔ値はｋの情報にのみ依存し、ｌに関する情報は位相の部分に押しやられたことに注意する。
【００６７】
以上、説明した量子アルゴリズムの動作を次の具体例で見てみる。ｎ＝３，ｓ＝１１０，ｗｔ（ｓ）＝２とする。ｆはｔｗｏ−ｔｏ−ｏｎｅ  ｆｕｎｃｔｉｏｎになる。そこで、ｆ：｛０，１｝3→｛０，１｝2と定義しても構わない。入力値ｘ∈｛０，１｝3は、次の四つの組に分けられる、
2006048441.tif 000075
。
【００６８】
初期状態｜０００＞｜００＞を用意して第１レジスタに
2006048441.tif 000076
を作用させると、次の状態が得られる、
2006048441.tif 000077
これにオラクルＵfを作用させて次の状態を得る、
2006048441.tif 000078
さらに、第１レジスタに
2006048441.tif 000079
を作用させると次の状態が得られる、
2006048441.tif 000080
。
【００６９】
第１レジスタを観測すると｜０００＞，｜０１０＞，｜１００＞，｜１１０＞の四種類のベクトルがランダムに得られる。例えば一回目の試行でｂｉｔ列ｋ(1)＝０１０が得られたとする。ｗｔ（ｓ）＝２であることは、あらかじめ分かっている。ｗｔ（ｋ(1)）＝１よりｓ≠ｋ(1)と分かる。そこで二回目の試行を行い、ｋ(2)＝１００を得たとする。ここでｋ＝ｋ(1)∨ｋ(2)＝１１０とすると、ｗｔ（ｋ）＝２よりｓ＝ｋ＝１１０と分かる。
【００７０】
［第２実施形態］
本実施形態では、第１実施形態で示した量子アルゴリズムの取るｑｕｅｒｙ数の期待値を評価する。また、この量子アルゴリズムの持ついくつかの特有の性質についても議論する。
【００７１】
まず、この量子アルゴリズムでのｑｕｅｒｙ数の期待値を調べることにする。後で示すことだが、ｑｕｅｒｙ数の期待値はｂｉｔ列ｓのＨａｍｍｉｎｇ重みｗｔ（ｓ）＝ｍには依存するが、ｑｕｂｉｔの全個数ｎには依存しない。そこで、ｑｕｅｒｙ数の期待値をＴQ（ｍ）と書くことにする。ＴQ（ｍ）の下付き添え字Ｑはｑｕａｎｔｕｍを表している。
【００７２】
まず、ｗｔ（ｓ）＝ｍ＝１の場合について調べる。ｓ＝１０．．．０と仮定しても、今後の議論の一般性は失われない。アルゴリズムの第４ステップ終了後の状態は式（１１）より、
2006048441.tif 000081
となる。
【００７３】
第１レジスタを観測し、｜０．．．０＞が得られたらアルゴリズムをもう一度やり直し、｜ｓ＞＝｜１０．．．０＞が得られたら終了となる。よって、
2006048441.tif 000082
ところで、次の公式が存在する、
2006048441.tif 000083
よって、ＴQ（１）＝２を得る。この結果から分かるようにＴQ（１）はｎに依存しない。このことは一般のｍ（１≦∀ｍ≦ｎ−１）についても成立する。
【００７４】
ＴQ（１）は次の方法でも求めることが出来る。式（１６）で表される状態において観測を行うと、｜０．．．０＞及び｜ｓ＞＝｜１０．．．０＞がそれぞれ確率１／２で得られる。｜０．．．０＞が観測された場合、ｓに関する情報は何も得られず、再度、アルゴリズムを繰り返すことになる。よって、ｓが得られるまでのｑｕｅｒｙの平均回数は［１＋ＴQ（１）］となる。一方、｜ｓ＞＝｜１０．．．０＞が観測された場合、一回のｑｕｅｒｙでｓが得られたことになる。これらの考察から次の式が得られる、
2006048441.tif 000084
これより、ＴQ（１）＝２が得られる。
【００７５】
次に、ｗｔ（ｓ）＝ｍ＝２の場合について考える。ｓ＝１１０．．．０としても一般性は失われない。この場合、アルゴリズムの第５ステップで第１レジスタを観測すると、式（１１）より、ｋ＝０００．．．０，  ０１０．．．０，  １００．．．０，  １１０．．．０の四つのｂｉｔ列がそれぞれ確率１／４で得られる。今の場合、３番目からｎ番目のｂｉｔ  ｋ3，．．．，ｋnは常に‘０’なので、先頭の二つのｂｉｔ  ｋ1，ｋ2にのみ注目する。ｋ1，ｋ2は、それぞれ確率１／２で‘０’か‘１’かのどちらかを独立且つランダムに取る。そして、ｋi＝０（ｉ＝１，２）ならばｓiは確定せず試行を再び繰り返すことになる。ｋi＝１（ｉ＝１，２）ならばｓi＝１で確定する。
【００７６】
ＴQ（２）を求める。ＴQ（１）を求める際、二通りの方法を示した。ここでは、それら二つのうちの後の方法を使うことにする。一回目の試行で（ｋ1，ｋ2）＝（０，０），（０，１），（１，０），（１，１）がそれぞれ確率１／４で得られる。（０，０）が得られた場合、ｓに関する情報は何も得られず、再試行することになる。ｓが得られるまでのｑｕｅｒｙ数の期待値は［１＋ＴQ（２）］となる。（０，１）又は（１，０）が得られた場合、ｓの二つあるｂｉｔ値‘１’のうちの一つが決定されたことになる。ｓが得られるまでのｑｕｅｒｙ数の期待値は［１＋ＴQ（１）］となる。（１，１）が得られたら、ｓは一回のｑｕｅｒｙで決定されたことになる。以上の考察から、ＴQ（２）は次のように表される、
2006048441.tif 000085
ＴQ（１）＝２を使うと、ＴQ（２）＝８／３が得られる。
【００７７】
一般のｍに対して、次の式が成立する、
2006048441.tif 000086
ただし、ＴQ（０）＝０とする。この式を使って、ＴQ（１）＝２，ＴQ（２）＝８／３，ＴQ（３）＝２２／７と、ｍ＝１から順に求めて行く。以上の考察から、ＴQ（ｍ）がｎに依存しないのは明らかである。
【００７８】
上の式（２１）からＴQ（ｍ）の閉じた式（ｃｌｏｓｅｄ  ｆｏｒｍ）を求めるのは難しい。そこで、次のようにＴQ（ｍ）を粗く見積もることにする。ｗｔ（ｓ）＝ｍが非常に大きな値の場合を考える。簡単のためｓ＝１．．．１０．．．０としても一般性は失われない。（ｓi＝１  ｆｏｒ  ｉ＝１，．．．，ｍ，  ａｎｄ  ｓi＝０  ｆｏｒ  ｉ＝ｍ＋１，．．．，ｎで１≪ｍ＜ｎとしている。）アルゴリズム第５ステップの観測で得られるｂｉｔ列は、集合｛ｋ：ｋi∈｛０，１｝  ｆｏｒ  ｉ＝１，．．．，ｍ，  ａｎｄ  ｋi＝０  ｆｏｒ  ｉ＝ｍ＋１，．．．，ｎ｝の要素のどれか一つである。
【００７９】
先頭のｍ個のｂｉｔに注目すると、各ｂｉｔは独立に確率１／２で‘０’又は‘１’の値をランダムに取る。ｋi＝１（ｉ＝１，．．．，ｍ）が出ればｓi＝１と確定、ｋi＝０（ｉ＝１，．．．，ｍ）が出ればｓiは決まらず再度試行する。
【００８０】
ここで、ｍ＝２tと仮定する。第一回目の試行で２t個のｂｉｔのうちのおよそ半分の約２t-1個のｂｉｔが‘１’として観測され、ｓのｂｉｔとして決定される。第二回目の試行で、決定されていない残りの約２t-1個のｂｉｔのうちのおよそ半分である約２t-2個のｂｉｔが観測で‘１’を取り、ｓのｂｉｔとして決定される。この過程を繰り返すとｔ回の試行後、決定されていない残されたｂｉｔはおよそ１個となる。ところで、１個のｂｉｔを決定するのに必要な試行回数の平均値はＴQ（１）＝２で与えられている。よって、ＴQ（２t）〜ｔ＋２を得る。これは、
2006048441.tif 000087
という近似式を推測させる。
【００８１】
図２は、第１実施形態で示した量子アルゴリズムで必要なｑｕｅｒｙ数の期待値をプロットして線で結んだグラフである。横軸はｂｉｔ列ｓのＨａｍｍｉｎｇ重みｗｔ（ｓ）＝ｍ、縦軸はｑｕｅｒｙ数の期待値Ｔを表している。ｍもＴも無次元量である。グラフではｍの範囲を１≦ｍ≦５００としている。実線は式（２１）で得られる厳密なＴQ（ｍ）を表している。破線は式（２２）で与えられるＴQ（ｍ）の近似式を表している。ここで議論した量子アルゴリズムでのｓを得るのに必要な平均ｑｕｅｒｙ数は、ＴQ（ｍ）〜（ｌｏｇ  ｍ）と評価して良いことが分かる。
【００８２】
これまで議論して来た量子アルゴリズムは、次の二つの特徴を持つ。まず第一の特徴は次のようなものである。この量子アルゴリズムは、関数ｆの不変性を定めるｂｉｔ列ｓについての情報を与えてくれるが、各入力ｘに対してｆ（ｘ）がどんな値を取るかについては何も教えない（たとえ、第２レジスタを観測しても分からない）。
【００８３】
第１実施形態でｎ＝３，ｓ＝１１０，ｗｔ（ｓ）＝ｍ＝２の場合の関数ｆの具体的な例を示した。入力ｘ∈｛０，１｝3は式（１２）に従って、ｆ（ｘ）の値によって四つの組に分類される。この組み分けの仕方はｓによって決められるもので、関数ｆの大域的な性質と呼ぶべきものである。一方、ｆ（ｘ）がどの値を取るか、式（１２）の例ではｆ（０００），ｆ（０１０），ｆ（１００），ｆ（１１０）が｛０，１｝2の要素のどれを取るかは、関数ｆの局所的な性質と呼ぶべきものである。関数ｆは、これらの大域的な性質と局所的な性質の二つによって定義されている。
【００８４】
そして、ここで議論した量子アルゴリズムは、関数ｆの大域的な情報のみを上手く取り出している。このような性質は、他の量子アルゴリズムでも見られる。
【００８５】
第二の特徴は次のようなものである。今考えている量子アルゴリズムを量子ゲートのネットワークで書き下すと、Ｓｉｍｏｎのアルゴリズムと同じになる。（図１を参照のこと。図１は、第１実施形態の量子アルゴリズムとＳｉｍｏｎのアルゴリズムに共通する量子ゲートネットワークを表した図である。時間は、図の左側から右側へ流れるとする。横線一本一本が各ｑｕｂｉｔを表す。上側の一かたまりの横線が第１レジスタ、下側の一かたまりの横線が第２レジスタを表す。Ｈと書かれてある四角形は式（１）のＨａｄａｍａｒｄ変換、Ｕfと書かれてある四角形は式（３）のオラクルを表す。）異なるのは問題の設定、つまり、オラクルｆの性質のみである。ここで議論されている量子アルゴリズムではｆ（ｘ∧ｓ）＝ｆ（ｘ）という関数を扱っているのに対して、Ｓｉｍｏｎのアルゴリズムでは
2006048441.tif 000088
という関数を扱っている。
【００８６】
図１を見ると、今考えている量子アルゴリズムは（２ｎ＋１）個の量子ゲートを使っているように見える。しかし、２ｎ個のＨａｄａｍａｒｄ変換は、初期状態、観測基底を変更することで取り除くことが出来る。従って、図１で必要な量子ゲートは本質的にオラクルＵf一個のみである。
【００８７】
［第３実施形態］
第１実施形態で示した量子アルゴリズムが古典アルゴリズムよりも効率的であることを示すには、所定の古典アルゴリズムのｑｕｅｒｙ数の下限を知る必要がある。しかし、これは一般に容易ではない。この節では、ｗｔ（ｓ）＝１とｗｔ（ｓ）＝ｎ−１の二つの特別な場合について考える。これらの場合では、所定の古典アルゴリズムのｑｕｅｒｙ数の下限を求めることができる。
【００８８】
［ｗｔ（ｓ）＝１の場合］
まず、ｗｔ（ｓ）＝ｍ＝１の場合について考える。次の古典アルゴリズムが考えられる。簡単のためｎ＝２tとして議論を進める。次のｔ個のｎ−ｂｉｔ列を定義しておく、
2006048441.tif 000089
ａl（ｌ＝１，．．．，ｔ）は２l-1個のｂｉｔ値‘０’と２l-1個のｂｉｔ値‘１’が交互に並んだものである。
【００８９】
ｂｉｔ列ｓ＝（ｓi）は次の手順で決定される。まず、ｆ（ｓ0）とｆ（ａ(t)）を求める。ｆ（ｓ0）＝ｆ（ａ(t)）ならば、ｓに含まれる唯一のｂｉｔ値‘１’はｎ−ｂｉｔ列の左半分のどこかに存在する。すなわち、ｓi＝δij，１≦ｊ≦ｎ／２となる。一方、ｆ（ｓ0）≠ｆ（ａ(t)）ならば、ｓに含まれる唯一のｂｉｔ値‘１’はｎ−ｂｉｔ列の右半分のどこかに存在する。すなわち、ｓi＝δij，（ｎ／２）＋１≦ｊ≦ｎとなる。
【００９０】
ここで、議論を簡単にするために、ｆ（ｓ0）＝ｆ（ａ(t)）と仮定する。次に、ｆ（ａ(t-1)）を求める。ｆ（ｓ0）＝ｆ（ａ(t-1)）ならば、ｓの唯一のｂｉｔ値‘１’は、ｎ−ｂｉｔ列を四等分した部分のうちの最も左側の部分の中に存在することになる。すなわち、ｓi＝δij，１≦ｊ≦ｎ／４となる。一方、ｆ（ｓ0）≠ｆ（ａ(t-1)）ならば、ｓの唯一のｂｉｔ値‘１’は、ｎ−ｂｉｔ列を四等分した部分のうちの左から二番目の部分の中に存在することになる。すなわち、ｓi＝δij，（ｎ／４）＋１≦ｊ≦ｎ／２となる。
【００９１】
以上の過程を繰り返して、ｓの唯一のｂｉｔ値‘１’の位置を特定する。このように、二分探索法（ｂｉｎａｒｙ  ｓｅａｒｃｈ）を使えば、ｓを（ｔ＋１）個のｑｕｅｒｙで求めることができる。例えばｓ＝１０．．．０の場合、ｆ（ｓ0）＝ｆ（ａ(t)）＝．．．＝ｆ（ａ(1)）が得られる。ｓ＝０１０．．．０の場合、ｆ（ｓ0）＝ｆ（ａ(t)）＝．．．＝ｆ（ａ(2)）≠ｆ（ａ(1)）が得られる。
【００９２】
一般のｎでは、必要なｑｕｅｒｙ数は、
2006048441.tif 000090
で与えられる。ただし、所定の実数ｘに対して
2006048441.tif 000091
は、ｊ−１＜ｘ≦ｊをみたす唯一の整数ｊを表すとする。
【００９３】
この二分探索法が古典アルゴリズムとしては最も効率的であることを示す。今考えている問題を解くのに必要なｑｕｅｒｙ数の、情報理論的な下限を求めることにする（ここでの議論は、いわゆる「偽コイン問題」（ｃｏｉｎ−ｗｅｉｇｈｉｎｇ  ｐｒｏｂｌｅｍ）の応用になっている（非特許文献１７，１８）。「偽コイン問題」とは、何枚かの正しいコインの中に偽コインが混じっていて、天秤のできるだけ少ない回数の使用で、それらを見分ける問題のことである。）。
【００９４】
考え得る関数ｆの種類の数を考えてみる。まず、ｆの不変性ｆ（ｘ∧ｓ）＝ｆ（ｘ）及びｗｔ（ｓ）＝ｍ＝１より、ｆは２n-1−ｔｏ−ｏｎｅ  ｆｕｎｃｔｉｏｎであることに注意する。（このことは第１実施形態で説明した。）従って、ｆをｆ：｛０，１｝n→｛０，１｝と再定義しても構わない。このときｆは上への写像（ｏｎｔｏ−ｍａｐｐｉｎｇ）となっている。ｎ−ｂｉｔ列ｓは、ｗｔ（ｓ）＝１より、ｎ通りある。また、関数ｆの定義域｛０，１｝nは次の二つの組に分けられる、
2006048441.tif 000092
Ｘ0，Ｘ1の要素数は共に２n-1個である。集合Ｘ0の代表要素をｓ0＝０．．．０、集合Ｘ1の代表要素をｓとする。次の関係が成立する、
2006048441.tif 000093
ｆの値域｛０，１｝を考えると、ｆ（ｓ0）＝０，ｆ（ｓ）＝１という場合と、ｆ（ｓ0）＝１，ｆ（ｓ）＝０という場合の二通りが考えられる。以上の議論から関数ｆは２ｎ種類あると考えられる。
【００９５】
これら２ｎ種類の関数が等しい確率
2006048441.tif 000094
で出現するとする。このとき、問題の持つ情報量（エントロピー）Ｓは、
2006048441.tif 000095
で与えられる。一方、一回のｑｕｅｒｙで得られる情報量（エントロピー）Ａは、ｆ（ｘ）（ｘ∈｛０，１｝n）の取り得る値が０又は１の二通りで、どちらの生起確率も１／２ずつとすると、
2006048441.tif 000096
で与えられる。従って、問題を解くのに必要なｑｕｅｒｙ数の下限は、
2006048441.tif 000097
で与えられる。
【００９６】
式（３０）のｑｕｅｒｙ数は、前の式（２４）の二分探索法のｑｕｅｒｙ数と一致する。従って、前の二分探索法は古典アルゴリズムとしては最良と分かる。一方、第１実施形態で与えられた量子アルゴリズムでは、ｓを求めるのに必要なｑｕｅｒｙ数の期待値は正確にＴQ（１）＝２であった。これより、第１実施形態の量子アルゴリズムは所定の古典アルゴリズムより効率的であると言える。
【００９７】
ここで次の点に注意する。式（２８）は、今考えている問題の持つ情報量（１＋ｌｏｇ2ｎ）であることを表している。ところで、関数ｆの大域的情報であるｂｉｔ列ｓはｎ種類考えられる。一方、関数ｆの局所的性質であるｆ（ｓ0），ｆ（ｓ）がそれぞれ０，１のどちらの値を取るかは、二通りが考えられる。従って、関数ｆの大域的情報量はｌｏｇ2ｎ、局所的情報量はｌｏｇ2２＝１となる。
【００９８】
もしｓだけを知りたいのならば、必要なｑｕｅｒｙ数の下限は
2006048441.tif 000098
となると考えられる。しかし、古典アルゴリズムでは大域的情報と局所的情報とを切り離すことができないのである。（局所的情報のみを古典アルゴリズムで取り出すことはできない。）よって、ｑｕｅｒｙ数の下限は（１＋
2006048441.tif 000099
）となる。
【００９９】
［ｗｔ（ｓ）＝ｎ−１の場合］
次にｗｔ（ｓ）＝ｍ＝ｎ−１の場合について考える。この場合、ｆ（ｘ∧ｓ）＝ｆ（ｘ）という条件は、次のように書き換えられる、
2006048441.tif 000100
ｆ（ｘ）はｔｗｏ−ｔｏ−ｏｎｅ  ｆｕｎｃｔｉｏｎである。このことは、第１実施形態のｎ＝３，ｓ＝１１０，ｗｔ（ｓ）＝２の例における式（１２）を見ても明らかである。
【０１００】
この場合、最良の古典アルゴリズムは次のようなものである。
2006048441.tif 000101
をみたすｂｉｔ列
2006048441.tif 000102
はｎ種類ある。これらｎ種類のｂｉｔ列を順番に式（３１）に従って試していくのである。これは、逐次検索法（ｓｅｑｕｅｎｔｉａｌ  ｓｅａｒｃｈ）である。
【０１０１】
次のｎ個のｎ−ｂｉｔ列を定義する、
2006048441.tif 000103
ただし、ｂ(i)＝（ｂ(i)j）＝（δij）  ｆｏｒ  ｉ，ｊ＝１，．．．，ｎはＨａｍｍｉｎｇ重みが１のｎ種類のｂｉｔ列である。
【０１０２】
まず、ｆ（ｓ0）を求める。次に、ｆ（ｂ(1)）を求めて、ｆ（ｂ(1)）＝ｆ（ｓ0）ならば
2006048441.tif 000104
を得る。ｆ（ｂ(1)）≠ｆ（ｓ0）ならば、次に、ｆ（ｂ(2)）を求める。このように、ｉ＝１，２，３，．．．の順にｆ（ｂ(i)）を評価して、ｆ（ｂ(i)）＝ｆ（ｓ0）ならばｓ＝
2006048441.tif 000105
とする。
【０１０３】
ｓを求めるのに必要なｑｕｅｒｙ数の期待値を求める。ｗｔ（ｓ）＝ｎ−１をみたすｎ種類のｎ−ｂｉｔ列ｓの、どれもが等しい確率で発生すると仮定する。ｓ＝０１．．．１ならばｑｕｅｒｙ数は２、ｓ＝１０１．．．１ならばｑｕｅｒｙ数は３となる。また、ｓ＝１．．．１０の場合、ｆ（ｂ(n-1)）≠ｆ（ｓ0）よりｓは決定され、ｑｕｅｒｙ数はｎとなる。よって、平均ｑｕｅｒｙ数は、
2006048441.tif 000106
となる。
【０１０４】
一方、第１実施形態で示した量子アルゴリズムでは必要なｑｕｅｒｙ数は、式（２２）より、
2006048441.tif 000107
で与えられる。従って、この場合、第１実施形態に示した量子アルゴリズムは所定の古典アルゴリズムよりも効率的であると言える。
【０１０５】
［第４実施形態］
第３実施形態ではｗｔ（ｓ）＝１及びｗｔ（ｓ）＝ｎ−１の場合の古典アルゴリズムのｑｕｅｒｙ数の下限を求め、第１実施形態の量子アルゴリズムが、どんな古典アルゴリズムよりも少ないｑｕｅｒｙ数で問題を解くことを示した。しかし、２≦ｗｔ（ｓ）≦ｎ−２の場合、古典アルゴリズムのｑｕｅｒｙ数の下限を求めることは難しい。そこで、本実施形態では、代表的と思われる二つの古典アルゴリズムのｑｕｅｒｙ数を評価し、量子アルゴリズムのそれと比較することにする。
【０１０６】
［二分探索法（ｂｉｎａｒｙ  ｓｅａｒｃｈ）の応用］
まず、第一の古典アルゴリズムとして次のものを考える。第３実施形態では、ｗｔ（ｓ）＝１の場合、二分探索法（ｂｉｎａｒｙ  ｓｅａｒｃｈ）が古典アルゴリズムとしては最良であることを示した。この方法を応用する。つまり、ｗｔ（ｓ）＝ｍ（≧２）として、二分探索法をｍ回繰り返しｓ中のｂｉｔ値‘１’を一個ずつ見付けて行くのである。
【０１０７】
次の事実を使う。ｓは、ｗｔ（ｓ）＝ｍのｎ−ｂｉｔ列であること以外、全くの未知であるとする。ｕ＝（ｕi）を次のようなｎ−ｂｉｔ列とする、
2006048441.tif 000108
ｆ（ｓ0）とｆ（ｕ）を比較して、
１．もしｆ（ｓ0）＝ｆ（ｕ）ならば、ｓl+1＝ｓl+2＝．．．＝ｓn＝０となる。
２．もしｆ（ｓ0）≠ｆ（ｕ）ならば、ｓl+1，ｓl+2，．．．，ｓnの少なくともどれか一つは値‘１’を取る。（ｓi＝１  ｆｏｒ  ｓｏｍｅ  ｉ∈｛ｌ＋１，ｌ＋２，．．．，ｎ｝．）
具体的には次のようにしてｓを決定する。簡単のためｎ＝２tとする。まずｆ（ｓ0）を求める。次にｆ（ｕ(1)）を求める。ただし、ｕ(1)＝（ｕ(1)i）は次のように与えられるとする、
2006048441.tif 000109
もしｆ（ｓ0）＝ｆ（ｕ(1)）ならば、ｓ(n/2)+1＝ｓ(n/2)+2＝．．．＝ｓn＝０、つまり、全てのｂｉｔ値‘１’はｂｉｔ列ｓの左半分に存在する。一方、もしｆ（ｓ0）≠ｆ（ｕ(1)）ならば、少なくともｓ(n/2)+1，ｓ(n/2)+2，．．．，ｓnのどれか一つは値‘１’を取る、すなわち、少なくとも一つのｂｉｔ値‘１’がｂｉｔ列ｓの右半分に存在することになる。
【０１０８】
ここでｆ（ｓ0）＝ｆ（ｕ(1)）としよう。この場合、ｕ(2)＝（ｕ(2)i）、ただし、
2006048441.tif 000110
を定義して、ｆ（ｓ0）とｆ（ｕ(2)）を比較する。これにより、少なくとも一個のｂｉｔ値‘１’が、ｂｉｔ列ｓを四等分した部分の左から一番目か二番目のどちらに存在するかが分かる。
【０１０９】
一方、ｆ（ｓ0）≠ｆ（ｕ(1)）の場合、ｕ(2)＝（ｕ(2)i）、ただし、
2006048441.tif 000111
を定義して、ｆ（ｓ0）とｆ（ｕ(2)）を比較する。これより、少なくとも一個のｂｉｔ値‘１’が、ｂｉｔ列ｓを四等分した部分の左から三番目か四番目のどちらに存在するかが分かる。
【０１１０】
この過程を繰り返せば、１＋ｔ＝１＋ｌｏｇ2ｎ個のｑｕｅｒｙで、ｂｉｔ列ｓ中のある一個のｂｉｔ値‘１’の位置を特定できる。（これは二分探索法になっている。）ｂｉｔ列ｓはｗｔ（ｓ）＝ｍより、ｍ個のｂｉｔ値‘１’を含んでいる。この中の一個のｂｉｔ値‘１’が上の手順で特定されたとする。すると、問題は（ｎ−１）−ｂｉｔ列中の（ｍ−１）個のｂｉｔ値‘１’を決定するというものに縮小される。
【０１１１】
例えば、ｂｉｔ列ｓの右端の成分がｓn＝１で与えられていて、これが最初に特定されたとしよう。ｓの二つ目のｂｉｔ値‘１’は次のようにして特定できる。式（３６）の代わりにｕ’(1)＝（ｕ’(1)i）を次のように定義する、
2006048441.tif 000112
これはｕ’(1)＝０．．．０１．．．１０という形をしている。ｓn＝１が特定されたことを受けて、ｎ番目の成分を‘０’として、残り（ｎ−１）個の成分の約半分をｂｉｔ値‘０’に、約半分をｂｉｔ値‘１’にしたのがｕ’(1)である。
【０１１２】
もしｆ（ｓ0）＝ｆ（ｕ’(1)）ならば、ｓ(n/2)+1＝ｓ(n/2)+2＝．．．＝ｓn-1＝０となり、（ｍ−１）個のｂｉｔ値‘１’はｂｉｔ列の左半分、一番目からｎ／２番目の成分の中に含まれることになる。一方、もしｆ（ｓ0）≠ｆ（ｕ’(1)）ならば、ｓ(n/2)+1，ｓ(n/2)+2，．．．，ｓn-1の中のどれかに少なくとも一個のｂｉｔ値‘１’が含まれていることになる。
【０１１３】
このようにｓの未知の（ｎ−１）個のｂｉｔに対して二分探索法を実行すれば、
2006048441.tif 000113
個のｑｕｅｒｙでｓの二回目のｂｉｔ値‘１’が決定される。よって、この古典アルゴリズムでｓを求めるのに必要なｑｕｅｒｙ数をＴnCB（ｍ）と書くことにすると、
2006048441.tif 000114
が成り立つ。ＴnCB（ｍ）の下付き添え字ＣＢはｃｌａｓｓｉｃａｌとｂｉｎａｒｙを表している。また、式（４０）によれば
2006048441.tif 000115
で、式（２４）に一致することに注意する。
【０１１４】
［逐次検索法（ｓｅｑｕｅｎｔｉａｌ  ｓｅａｒｃｈ）の変形］
次に第二の古典アルゴリズムとして以下のものを考える。第３実施形態では、ｗｔ（ｓ）＝ｎ−１の場合、逐次検索法（ｓｅｑｕｅｎｔｉａｌ  ｓｅａｒｃｈ）が古典アルゴリズムとしては最良であることを示した。この方法を応用する。式（３２）で定義したｎ個のｎ−ｂｉｔ列｛ｂ(i)：ｉ＝１，．．．，ｎ｝を再び使う。
【０１１５】
まずｆ（ｓ0）を求める。次にｆ（ｂ(1)）を求めて、もしｆ（ｂ(1)）＝ｆ（ｓ0）ならばｂｉｔ列ｓの第１成分ｓ1は‘０’（ｓ1＝０）、もしｆ（ｂ(1)）≠ｆ（ｓ0）ならばｓ1＝１となる。このように、
2006048441.tif 000116
としてｉ＝１，２，．．．，ｎの順にｆ（ｂ(i)）を評価して、ｂｉｔ列ｓの成分を１番目から順に決定して行く。ｗｔ（ｓ）＝ｍがあらかじめ与えられているので、例えばｂｉｔ列ｓ中にｍ個のｂｉｔ値‘１’が現れたら、その時点でｓは決定されたことになる。
【０１１６】
このアルゴリズムでの、ｗｔ（ｓ）＝ｍの場合のｑｕｅｒｙ数の期待値をＴnCS（ｍ）と表すことにする。ＴnCS（ｍ）の下付き添え字ＣＳはｃｌａｓｓｉｃａｌとｓｅｑｕｅｎｔｉａｌを表している。ＴnCS（ｍ）の性質については、次のことがすぐに分かる。明らかにＴnCS（ｍ）≦ｎである。（と言うのも、ｗｔ（ｓ）＝ｍが与えられているので、ｆ（ｓ0），ｆ（ｂ(1)），．．．と始めて、ｆ（ｂ(n-1)）を求めた時点で、ｓが完全に決定されるので。）また、ＴnCS（ｍ）＝ＴnCS（ｎ−ｍ）が成立する。これは、ｗｔ（ｓ）＝ｍのｂｉｔ列ｓを決定するということは、ｍ個のｂｉｔ値‘１’を特定することであると同時に、（ｎ−ｍ）個のｂｉｔ値‘０’を特定することでもあるからである。また、
2006048441.tif 000117
はすでに式（３３）で得られている。
【０１１７】
具体例としてＴnCS（２）を計算してみる。ｗｔ（ｓ）＝２となるｓは
2006048441.tif 000118
通りある。上記のアルゴリズムで最も少ないｑｕｅｒｙ数で決定されるｓはｓ＝１１０．．．０である。この場合、必要なｑｕｅｒｙ数は３である。ｑｕｅｒｙ数４で決定できるｓは、ｓ＝１０１０．．．０とｓ＝０１１０．．．０の二通りがある。このように、３≦ｌ≦ｎ−２として、ｑｕｅｒｙ数ｌで決定できるｓは（ｌ−２）通りある。
【０１１８】
ところがｑｕｅｒｙ数（ｎ−１）で決定できるｓは、これらとは事情が異なる。まず、１０．．．０１００，  ０１０．．．０１００，  ．．．，  ０．．．０１１００で与えられる、最後の３−ｂｉｔが‘１００’のｂｉｔ列が（ｎ−３）個ある。また０．．．０１１も（ｎ−１）個のｑｕｅｒｙで決定される。（０．．．０１１は、最初の（ｎ−２）個のｂｉｔ値‘０’が特定された時点で全体が決定される。）よって、ｑｕｅｒｙ数（ｎ−１）で決定されるｓは［（ｎ−３）＋１］通りある。
【０１１９】
また、ｑｕｅｒｙ数ｎで決定されるｓは次のように数える。まず、１０．．．０１０，  ０１０．．．０１０，  ．．．，  ０．．．０１１０で与えられる最後の２−ｂｉｔが‘１０’のｂｉｔ列が（ｎ−２）個ある。また、１０．．．０１，  ０１０．．．０１，  ．．．，  ０．．．０１０１で与えられる最後の２−ｂｉｔが‘０１’のｂｉｔ列（ｎ−２）個もｎ個のｑｕｅｒｙで決定される。よって、ｑｕｅｒｙ数ｎで決定されるｓは［（ｎ−２）＋（ｎ−２）］通りある。
【０１２０】
よって、
2006048441.tif 000119
同様の考察から、一般に、
2006048441.tif 000120
が得られる。式（４４）のＴnCS（ｍ）は、式（４２）のＴnCS（ｎ−１）、式（４３）のＴnCS（２）と一致する。また、式（４４）はＴnCS（ｍ）＝ＴnCS（ｎ−ｍ）という関係をみたす。
【０１２１】
図３に、第１実施形態で定義された問題（ｎ＝２００，１≦ｍ≦１９９）を、量子アルゴリズム、古典アルゴリズムで解いた場合の、平均ｑｕｅｒｙ数をプロットして線で結んだグラフを示す。横軸をｂｉｔ列ｓのＨａｍｍｉｎｇ重みｗｔ（ｓ）＝ｍ、縦軸をｑｕｅｒｙ数の期待値Ｔとしている。ｍもＴも無次元量である。また、縦軸Ｔは対数スケールが取られている。太い実線は式（２１）で与えられるＴQ（ｍ）（量子アルゴリズム）、細い実線は式（４０）で与えられるＴnCB（ｍ）（二分探索アルゴリズムの応用）、細い破線は式（４４）で与えられるＴnCS（ｍ）（逐次検索アルゴリズムの変形）を表している。
【０１２２】
図３は、２≦ｗｔ（ｓ）≦ｎ−２の領域において、第１実施形態で示した量子アルゴリズムが、本実施形態で議論した二つの古典アルゴリズム（二分探索法の応用、逐次検索法の変形）よりも効率的であることを示している。
【０１２３】
［第５実施形態］
これまでの問題は、ｆ（ｘ∧ｓ）＝ｆ（ｘ）という関数ｆのオラクルを使ってｓを求めよというものだった。これに似た問題として、ｇ（ｘ∨ｓ）＝ｇ（ｘ）という関数ｇのオラクルを使ってｓを求めよというのが考えられる。（ＯＲ−マスクに対して不変な関数の性質を調べよという問題となる。）問題を明示的に書き下すと次のようになる。
【０１２４】
関数ｇ：｛０，１｝n→｛０，１｝nが与えられていて、ｇ（ｘ）＝ｇ（ｙ）となるのは、ｙ＝ｘ又はｙ＝ｘ∨ｓのとき、且つ、そのときに限るとする。ｗｔ（ｓ）＝ｎ−ｍは与えられているが、ｓがどのようなｂｉｔ列かは知らないとする。ｓを求めよ。
【０１２５】
ｗｔ（ｓ）＝０，ｎの場合、この問題は自明となるので、ｓ≠ｓ0，ｓ1とする。ｇは２n-m−ｔｏ−ｏｎｅ  ｆｕｎｃｔｉｏｎである。
【０１２６】
上の問題も、これまで議論して来たのと同様の量子アルゴリズムで解くことができる。第１実施形態で示したアルゴリズムの第１から第４ステップを行う。まず次のことに注目する。
ｇ（ｘ）＝ｇ（ｙ）となるのは、ｙ＝ｘ又はｙ＝ｘ∨ｓのとき、且つ、そのときに限られていて、また、ｗｔ（ｓ）＝ｎ−ｍが与えられている。よって、ｇは２n-m−ｔｏ−ｏｎｅ  ｆｕｎｃｔｉｏｎである。これは、ｂｉｔ列ｓのｂｉｔ値‘１’の桁の総数が（ｎ−ｍ）で、関数ｇはその（ｎ−ｍ）個の桁の値に依存しないからである。従って２n個のｇへの入力ｘ∈｛０，１｝nは、ｇ（ｘ）の値によって２m個の組に分けられ、各組に含まれるｘの個数は２n-mとなる。
【０１２７】
これより、式（５）で示される、第３ステップ終了後のレジスタは次のように書き換えられる、
2006048441.tif 000121
上の式でｂｉｔ列ｌは、
2006048441.tif 000122
のｂｉｔ値‘０’が立っている桁は‘０’、
2006048441.tif 000123
のｂｉｔ値‘１’が立っている桁は‘０’又は‘１’がランダムに割り当てられる。従ってｌは２m種類ある。また、ｂｉｔ列ａはｓのｂｉｔ値‘０’が立っている桁は‘０’、ｓのｂｉｔ値‘１’が立っている桁は‘０’又は‘１’がランダムに割り当てられる。従ってａは２n-m種類ある。
【０１２８】
次に、アルゴリズムの第４ステップとして、式（４５）の第１レジスタの各ｑｕｂｉｔに独立にＨａｄａｍａｒｄ変換Ｈを作用させる。第１レジスタのｎ−ｑｕｂｉｔ状態
2006048441.tif 000124
に対して、ｎ−ｂｉｔ列ｓのｂｉｔ値‘１’が立っている桁を左端に、ｂｉｔ値‘０’が立っている桁を右端に寄せるように、ｎ個のｑｕｂｉｔを置換することを考える。すると第１レジスタは式（９）のように書き換えられる。Ｈａｄａｍａｒｄ変換Ｈは｜ａ＞の重ね合わせを
2006048441.tif 000125
に変換する。よって、式（４５）は次の状態に変換される、
2006048441.tif 000126
。
【０１２９】
次に第１レジスタを｛｜ｘ＞：ｘ∈｛０，１｝n｝基底によって測定する。これにより、ｂｉｔ列ｋ、ただし、
2006048441.tif 000127
，ｙ∈｛０，１｝nを得る。ｋは２m種類あって、そのうちのどれが得られるかは全くランダムである。
2006048441.tif 000128
は、ｂｉｔ列ｓのｂｉｔ値‘０’が立っている桁に‘０’か‘１’がランダムに割り当てられ、ｂｉｔ列ｓのｂｉｔ値‘１’が立っている桁は‘１’となっている。従って、アルゴリズムを繰り返して何度も
2006048441.tif 000129
を求め、それらをｂｉｔ毎のＡＮＤ操作で足し合わせていくと、いつかはｓが得られるはずである。（得られたｋに対して、
2006048441.tif 000130
ならば
2006048441.tif 000131
とする。
2006048441.tif 000132
ならば、このｋをｋoldとして、再度試行を実行して新しい観測値ｋnewを得て、
2006048441.tif 000133
とする。この過程を繰り返すのである。）
この量子アルゴリズムでｓを得るのに必要なｑｕｅｒｙ数の期待値は、ｆ（ｘ∧ｓ）＝ｆ（ｘ）の場合の議論で得られた式（２１）で定義されるＴQ（ｍ）で与えられるのは明らかである。また、ｓを得るための古典アルゴリズムについても、ｆ（ｘ∧ｓ）＝ｆ（ｘ）の場合と同様の議論で展開できる。
【０１３０】
［第６実施形態］
本実施形態では、第１実施形態で示した量子アルゴリズムを、互いに遠く離れた場所にある二つの計算機が通信し合うことによって協力して問題を解く、分散コンピューティングに応用することを考える。
【０１３１】
ＡｌｉｃｅとＢｏｂは、互いに遠く離れた場所にいて、各自、計算機を持っており、また、両者は通信回線でつながれている状況を考える。二人は協力し合って、次の問題を解くとする。
【０１３２】
Ａｌｉｃｅに、関数ｆ：｛０，１｝n→｛０，１｝nがｂｌａｃｋ  ｂｏｘ（ｏｒａｃｌｅ）として与えられているとする。ただし、関数ｆは、ｆ（ｘ）＝ｆ（ｙ）となるのは、ｙ＝ｘ又はｙ＝ｘ∧ｓのとき、且つ、そのときに限る、という性質を持つとする。Ｂｏｂは、ｗｔ（ｓ）＝ｍであることは知っているが、ｓがどのようなｂｉｔ列かは知らないとする。Ｂｏｂがｓを求めるには、どうすれば良いか。
【０１３３】
ＢｏｂはＡｌｉｃｅに関数ｆへの入力を通信回線で送り、ＡｌｉｃｅはＢｏｂにその出力を返す。Ｂｏｂは得られた出力からｓを求めるとする。なるべく少ない通信回数でｓを求めたいとする。また、Ａｌｉｃｅは、ｂｌａｃｋ  ｂｏｘ（ｏｒａｃｌｅ）を操作する以外、どんな演算操作もしてくれないとする。
【０１３４】
Ａｌｉｃｅ，Ｂｏｂ間での、関数ｆの入出力の一往復を、一回の通信回数と数えることにすると、これは、第１，２，３，４実施形態で議論したオラクルへの一回のｑｕｅｒｙに相当することが分かる。従って、これまで考えて来たｑｕｅｒｙ数の評価が、そのまま通信回数の評価に使える。
【０１３５】
まず、Ａｌｉｃｅ，Ｂｏｂが共に古典コンピュータを持っていて、また、二人は古典情報しかやり取りできない場合を考える。これは、古典コンピュータで第１実施形態で示した問題を解くことに相当する。このときのｑｕｅｒｙ数は、第３，４実施形態で評価した。
【０１３６】
第３実施形態によれば、Ｂｏｂがｓを得るのに必要な通信回数の期待値の下限は、ｗｔ（ｓ）＝１ならば
2006048441.tif 000134
、ｗｔ（ｓ）＝ｎ−１ならば（１／２）［ｎ＋１−（２／ｎ）］＋１〜Ｏ（ｎ）で与えられる。これらの下限値を実現する方法も、第３実施形態で示された通りである。オラクルに与えられるｑｕｅｒｙとなるｂｉｔ列（式（２３）や式（３２）のｂｉｔ列）を、ＢｏｂがＡｌｉｃｅに通信回線で送り、Ａｌｉｃｅはその出力をＢｏｂに返せば良い。
【０１３７】
２≦ｗｔ（ｓ）≦ｎ−２の場合については、第４実施形態により、以下のことが言える。Ｂｏｂが第４実施形態の［二分探索法（ｂｉｎａｒｙ  ｓｅａｒｃｈ）の応用］の方法を採用した場合、ｓを求めるのに必要な通信回数の期待値は、式（４０）のＴnCB（ｍ）で与えられる。Ｂｏｂが第４実施形態の［逐次検索法（ｓｅｑｕｅｎｔｉａｌ  ｓｅａｒｃｈ）の変形］の方法を採用した場合、ｓを求めるのに必要な通信回数の期待値は、式（４４）のＴnCS（ｍ）で与えられる。
【０１３８】
次に、Ａｌｉｃｅ，Ｂｏｂが共に量子コンピュータを持っていて、また、二人は量子情報のやり取りできる場合を考える。これは、量子コンピュータで第１実施形態で示した問題を解くことに相当する。Ａｌｉｃｅ，Ｂｏｂは、第１実施形態で示した量子アルゴリズムを使ってｓを求めることができる。
【０１３９】
この量子アルゴリズムでは、式（４），（５），（６）のように、二つのｎ−ｑｕｂｉｔレジスタが使われた。そこで、第１レジスタをＢｏｂが、第２レジスタをＡｌｉｃｅが持つことにするのである。Ｂｏｂは重ね合わせ状態をＡｌｉｃｅに量子回線で送る。Ａｌｉｃｅは、Ｂｏｂからのｑｕｂｉｔ（第１レジスタ）と元々自分の持っていたｑｕｂｉｔ（第２レジスタ）を合わせて、オラクルのユニタリ変換を作用させる。そして、Ｂｏｂへｑｕｂｉｔを返すのである。
【０１４０】
Ａｌｉｃｅ，Ｂｏｂの手続きは以下のように書き下せる。
１．Ａｌｉｃｅ，Ｂｏｂは各自ｎ−ｑｕｂｉｔから成るレジスタを用意し、各ｑｕｂｉｔを｜ｓ0＞に初期化する。二人は、それぞれ状態｜ｓ0＞nを得る。
【０１４１】
２．Ｂｏｂは、手元のｎ個のｑｕｂｉｔ各々にＨａｄａｍａｒｄ変換Ｈを作用させ、それらをＡｌｉｃｅに送る。Ａｌｉｃｅは、Ｂｏｂから受け取ったｑｕｂｉｔを第１レジスタ、自分の持っていたｑｕｂｉｔを第２レジスタとする。これにより、Ａｌｉｃｅは式（４）の状態を得る。
【０１４２】
３．Ａｌｉｃｅは、与えられたｂｌａｃｋ  ｂｏｘ（ｏｒａｃｌｅ）Ｕfを作用させて、第１レジスタのｘの値に応じて第２レジスタにｆ（ｘ）を書き込む。これにより、Ａｌｉｃｅは式（５）の状態を得る。
【０１４３】
４．Ａｌｉｃｅは、第１レジスタをＢｏｂに送る。Ｂｏｂは受け取ったｎ個のｑｕｂｉｔの各々に再びＨａｄａｍａｒｄ変換Ｈを作用させる。
【０１４４】
５．Ｂｏｂは手元のｎ−ｑｕｂｉｔを、論理ケットベクトル（ｌｏｇｉｃａｌ  ｋｅｔ  ｖｅｃｔｏｒｓ）｛｜ｘ＞：ｘ∈｛０，１｝n｝を基底として観測する。｜ｋ＞が得られたとする。ｗｔ（ｋ）＝ｍならばｓ＝ｋとする。ｗｔ（ｋ）＜ｍならば、再度、第１ステップから第４ステップの操作を行い、ｎ−ｑｕｂｉｔを観測する。一回目の観測で得られたｋをｋoldと書き、二回目の観測で得られたｂｉｔ列をｋnewとして、ｋ＝ｋold∨ｋnewを求める。ｗｔ（ｋ）＝ｍならばｓ＝ｋとする。ｗｔ（ｋ）＜ｍならば再びｋをｋoldとして、第１ステップから第４ステップの操作を行いｋnewを得て、ｋ＝ｋold∨ｋnewを作る。これらの過程をｗｔ（ｋ）＝ｍとなるまで繰り返す。ｗｔ（ｋ）＝ｍのときｓ＝ｋでｓを得たことになる。
【０１４５】
上の手続きでは、ＡｌｉｃｅはオラクルＵfのみ、ＢｏｂはＨａｄａｍａｒｄ変換Ｈのみを作用させていることに注意する。
【０１４６】
第２実施形態より、上の方法でＢｏｂがｓを得るのに必要な通信回数の期待値は、式（２１）のＴQ（ｍ）で与えられることが分かる。さらに、式（２２）より、ＴQ（ｍ）は、およそ２＋ｌｏｇ2ｍ〜Ｏ（ｌｏｇｍ）と近似できる。
【０１４７】
以上の考察から、ＡｌｉｃｅとＢｏｂが共同で問題を解く場合、ｗｔ（ｓ）＝１及びｗｔ（ｓ）＝ｎ−１のときは、二人は量子コンピュータ及び量子通信回線を使った方が、古典コンピュータ及び古典通信回線を使うよりも、通信回数を低く抑えられることが分かる。
【０１４８】
ここで説明した量子アルゴリズムを使った分散コンピューティングには、次の利点もある。上で述べたように、この分散コンピューティングの方法では、Ａｌｉｃｅは複数のｑｕｂｉｔにまたがる変換Ｕfを作用させるが、Ｂｏｂは１−ｑｕｂｉｔの変換であるＨａｄａｍａｒｄ変換Ｈのみを実行する。一般に、複数のｑｕｂｉｔに対するユニタリ変換は、１−ｑｕｂｉｔに対するユニタリ変換よりも、実現が難しいと考えられている。
【０１４９】
このように、一方は高度なユニタリ変換を実行する技術を持っているが、他方は簡単なユニタリ変換を実行する技術しか持っていないペアが、協力し合って問題を解く場合、上で説明した分散コンピューティングの方法は有効である。
【０１５０】
これまでの問題は、ｆ（ｘ∧ｓ）＝ｆ（ｘ）という関数ｆのオラクルを使ってｓを求めよというものだった。これに似た問題として、第５実施形態では、ｇ（ｘ∨ｓ）＝ｇ（ｘ）という関数ｇのオラクルを使ってｓを求めよというのを考えた。（ＯＲ−マスクに対して不変な関数の性質を調べよという問題となる。）このような問題を分散コンピューティングで解く場合も、これまでとほぼ同様の議論が成立する。
【０１５１】
［第７実施形態］
本実施形態では、第１実施形態で示した量子アルゴリズム及び第６実施形態で示した量子分散コンピューティングを、ｃｏｎｔｒｏｌゲートの故障診断に利用する方法について説明する。
【０１５２】
量子コンピュータで使われるｃｏｎｔｒｏｌゲートが正しく動作しているかを調べる問題を考える。次の式で与えられるｃｏｎｔｒｏｌゲートＵfを考える、
2006048441.tif 000135
ただし、ｘ，ｙ∈｛０，１｝n、ｆ：｛０，１｝n→｛０，１｝nとする。Ｕfは、ｎ−ｑｕｂｉｔから成る第１レジスタをコントロール（ｃｏｎｔｒｏｌ）部に、ｎ−ｑｕｂｉｔから成る第２レジスタをターゲット（ｔａｒｇｅｔ）部に持つ量子ゲートである。Ｕfをネットワークの図で表すと図４のようになる。
【０１５３】
Ｕfのような、複数のｑｕｂｉｔ上でのユニタリ変換を実現する量子ゲートを、物理的に構成するには高度な技術が必要と考えられている。今、このＵfが上手く動作しておらず、第１レジスタの一番目のｑｕｂｉｔが他のｑｕｂｉｔと相互作用していないとする。この不完全なゲートＵf'を次のように定義する、
2006048441.tif 000136
ただし、ｘ，ｙ∈｛０，１｝n、ｆ’：｛０，１｝n→｛０，１｝nとなる。Ｕf'をネットワークの図で表すと図５のようになる。
【０１５４】
ｆ’（ｘ）はｎ−ｂｉｔ列ｘの一番目のｂｉｔに依存しないので、関数ｆ’は、∀ｘ∈｛０，１｝nに対して、
2006048441.tif 000137
ただし、ｓ＝０１…１という不変性を持つ。
【０１５５】
今、不完全なｃｏｎｔｒｏｌゲートＵf'が与えられていて、コントロール（ｃｏｎｔｒｏｌ）部のどのｑｕｂｉｔが他のｑｕｂｉｔと相互作用しないのか分からないとする。（これは、ｎ−ｂｉｔ列ｓが未知ということを意味する。）そこで、Ｕf'のコントロール（ｃｏｎｔｒｏｌ）部である第１レジスタに適当な量子状態を入力し、Ｕf'を動作させて、その出力から、故障しているｑｕｂｉｔを見つけ出すことにする。（ｓを求めることに相当する。）Ｕf'の動作が正確に分かっていないので、これはオラクルと見なせる。よって、この問題は、第１実施形態で示した量子アルゴリズム及び第６実施形態で示した量子分散コンピューティングで、効率よく解決できるはずである。
【０１５６】
与えられた不完全なゲートＵf'において、コントロール（ｃｏｎｔｒｏｌ）部のいくつのｑｕｂｉｔが他のｑｕｂｉｔと相互作用しないかが、あらかじめ分かっているとし、それを（ｎ−ｍ）個とする。これは、ｗｔ（ｓ）＝ｍが前もって与えられているということに相当する（不具合のあるｑｕｂｉｔがどれか、はっきり分かっていないのに、不具合のあるｑｕｂｉｔの総数はあらかじめ分かっているというのは、一見すると、問題設定として不自然のように感じられるかもしれない。しかし、このような状況は、現実の実験室ではしばしば起こり得る。例えば、ｃｏｎｔｒｏｌゲートの試作をすでに何回も行っていて、どれくらいの確率でｑｕｂｉｔの相互作用に不具合が生じるかが、経験的に分かっていれば、相互作用をしないｑｕｂｉｔの全個数が推定可能である。）。
【０１５７】
そこで、第１実施形態で示した量子アルゴリズムを適用し、Ｕf'にｑｕｅｒｙを与えて観測を行う。必要なｑｕｅｒｙ数の期待値は、式（２１）のＴQ（ｍ）で与えられる。さらに、式（２２）より、ＴQ（ｍ）は、およそ２＋ｌｏｇ2ｍ〜Ｏ（ｌｏｇ  ｍ）と近似できる。コントロール（ｃｏｎｔｒｏｌ）部のいくつのｑｕｂｉｔに不具合が生じているか分からない場合、Ｏ（ｌｏｇ  ｎ）個程度のｑｕｅｒｙを与えてｓを推測し、これによって不具合のあるｑｕｂｉｔを推定するのは有効な方法である。
【０１５８】
また、ＡｌｉｃｅがＵf'を持っていて、Ａｌｉｃｅから遠く離れた地点にいるＢｏｂが量子通信回線を通して、Ｕf'の不具合のあるｑｕｂｉｔを探す場合、第６実施形態で示した量子分散コンピューティングの方法が適用できる。これにより、Ｂｏｂは少ない通信回数でＵf'の不具合を検知できる。
尚、第１実施形態〜第７実施形態においては、量子計算方法、分散量子計算実行方法、及び、それらを利用した量子ゲート故障診断方法について述べたが、本発明にはそれらの工程を手段として備えた量子計算装置、分散量子計算実行装置、及び、量子ゲート故障診断装置も含まれる。
【図面の簡単な説明】
【０１５９】
【図１】第１実施形態の量子アルゴリズムとＳｉｍｏｎのアルゴリズムに共通する量子ゲートネットワークを表した図である。
【図２】第１実施形態で示した量子アルゴリズムで必要なｑｕｅｒｙ数の期待値をプロットして線で結んだグラフを示す図である。
【図３】第１実施形態で定義された問題（ｎ＝２００， １≦ｍ≦１９９）を、量子アルゴリズム、古典アルゴリズムで解いた場合の、平均ｑｕｅｒｙ数をプロットして線でつないだグラフを示す図である。
【図４】第７実施形態の、ｃｏｎｔｒｏｌゲートを示す図である。
【図５】第７実施形態の、ｎ−ｑｕｂｉｔから成る第１レジスタの一番目のｑｕｂｉｔが他のｑｕｂｉｔと相互作用出来ず不具合を生じている、ｃｏｎｔｒｏｌゲートを示す図である。
【図１】
2006048441.tif 000170
【図２】
2006048441.tif 000171
【図３】
2006048441.tif 000172
【図４】
2006048441.tif 000173
【図５】
2006048441.tif 000174