(57)【要約】  ＮＰ完全問題３ＳＡＴ、および、ＮＰ完全問題３ＳＡＴへ単純化されることができる他のコンピュータ計算問題を解くための方法。量子力学演算は、有限数の量子力学ビット、すなわち、「キュービット」が存在すると仮定されると、与えられた３ＳＡＴ問題を解く状態における確率を集中させる方式で、有限数の量子力学ビット、すなわち、「キュービット」に対して実行される。確率の集中は、１つの密度行列を別の密度行列へマッピングする非可逆的な演算を含めるように、量子計算の従来の可逆的モデルを一般化することによって達成される。
2018530849.tif 000002
【特許請求の範囲】
【請求項１】
非可逆的な量子計算を実行するための方法であって、
ユニタリ演算を実行するステップと、
挿入演算を実行するステップと、
削除演算を実行するステップと
のうちの１つまたは複数を含む方法。
【請求項２】
請求項１に記載の方法であって、
第１のビットの状態において、論理演算の出力、または、論理演算として表現可能な任意の特性をエンコードするステップと、
１つまたは複数の他のビットの状態を制御するために、前記第１のビットの前記状態を使用するステップと、
前記第１のビットの前記状態を記憶し、削除し、またはさらに修正するステップと
をさらに含む方法。
【請求項３】
量子コンピュータであって、
前記量子コンピュータにインストールされ、解状態における確率を集中させるように構成されたアルゴリズムと、
第１の密度行列を第２の密度行列へマッピングする量子コンピュータ機能と、
明確に定義された逆を有しない前記マッピング関数と
を含む量子コンピュータ。
【請求項４】
論理式を満たす状態または状態のセットにおける確率を集中させる、量子系における状態のための確率分布を変更するための方法。
【請求項５】
請求項４に記載の方法であって、
デシメーションゲートのアイデンティティ、特定のデシメーションゲートに対応するデシメーション角度、異なるゲートのためのアプリケーションの順序、または、前記特定のデシメーションゲートが適用される回数等のパラメータが、反復間で変動する、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
[0001]本特許出願は、２０１５年１１月２日に出願された米国仮特許出願第６２／２４９，４３８号の利益を主張する、２０１６年９月１２日に出願された米国特許出願第１５／２６３，２４０号の利益を主張し、また、２０１５年９月１１日に出願された米国仮特許出願第６２／２１７，４３２号の利益も主張し、これらはともに、参照によって本明細書に組み込まれる。
【０００２】
[0002]本発明は、一般に、コンピュータ計算に関し、特に、量子コンピュータ計算に関する。
【背景技術】
【０００３】
[0003]量子コンピュータは、有限量子力学系に対して、所望される特性を有する状態を占有させるために、有限量子力学系に対して、物理的な変換を実行することによってコンピュータ計算問題を解く。１または０の値を決定論的に得る必要のある古典的ビットに対する演算とは異なり、量子コンピュータは、任意の２つの状態の重ね合わせに存在することができる量子力学的な「キュービット」に対して演算する。量子コンピュータは、いくつかのコンピュータ計算問題、とりわけ重要なのは、他の量子系のシミュレーションを、古典的なコンピュータよりもはるかに高速に解くことができることが知られている。しかしながら、著しいスピードアップが可能である問題の類は、まだ知られていない。
【０００４】
[0004]クローズ（clause）あたり３変数であるブーリアン充足可能性問題、すなわち３ＳＡＴは、連言標準形、すなわち「ＣＮＦ」における命題論理式
（ｘ∨ｘ２∨¬ｘ４）∧（ｘ２∨¬ｘ３∨¬ｘ５）Λ．．．    （１）
が真であると評価する方式で真または偽になるブーリアン変数ｘ１，ｘ２，ｘ３．．．のセットの割当からなる。ここで、同一クローズ内の変数（ｘｎ）またはその否定（¬ｘｎ）は、ＯＲ（∨）演算子とリンクされる一方、異なるクローズは、ＡＮＤ（∧）演算子によってリンクされる。割当は、この問題を解くために、すべてのクローズを満たさねばならない。
【０００５】
[0005]３ＳＡＴは、ＮＰ完全となることがコンピュータ科学においてよく知られている［８，４］。これは、その解が、多項式時間（クラス「ＮＰ」）においてチェックされることができる任意の問題が、多項式時間において、３ＳＡＴ問題へ単純化されることができる特性を有することを意味する。したがって、３ＳＡＴのための多項式時間解は、多項式時間におけるＮＰにおける任意の問題を解くためにも同様に使用されることができるであろう。古典的なコンピュータにおけるアルゴリズムは、多項式時間におけるＮＰ完全問題を解くことができないと信じられるが証明されておらず、これが真であるか否かの疑問は、数学における最も有名な問題のうちの１つである［３］。
【０００６】
[0006]ここで、単純化は、第２のインスタンスに対する解が、第１のインスタンスの解へマッピングされることができる方式で、１つの問題のインスタンスからの、別の問題のインスタンスへのマッピングからなる。コンピュータ計算問題は、問題パラメータのリストに加えて、問題に対する解が満たさねばならない特性のステートメントからなる［４］。問題のインスタンスは、すべての問題パラメータのための特定の値を指定することによって取得される。
【０００７】
[0007]コンピュータ問題のための解法アルゴリズムは、特定のインスタンスが解を有するか否かを判定するか、または、何も存在しないが必ずしも解を生成する必要はないことを証明する。建設的な解法アルゴリズムは、いくつかの解が存在すると仮定して、少なくとも１つの有効な解を生成する。確率論的解法アルゴリズムは、従来、通常は１／３であると選択される、０と１／２との間のある値εよりも大きくない誤差の確率を有する解が存在するか否かを判定する。確率論的アルゴリズムは、与えられたインスタンスが、解を有するかまたは有さない確実性を高めるために、何度も実行されることができる。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
[0008]本発明は、量子力学系において、非可逆的な物理的な変化を引き起こす新たなタイプの量子コンピュータと、論理的に意味のある方式で、この系の状態を変化させる、物理的な変換のセット、すなわち「ゲート」と、量子確率を、興味のあるいくつかの３ＳＡＴ問題を解決することができない物理的な状態から、興味のあるいくつかの３ＳＡＴ問題を解決する状態または状態のセットへ転送させるアルゴリズムとを備える。少なくとも１つの解状態が存在すると仮定すると、アルゴリズムは、総非解確率を、指数関数的に減少させ、これによって、解状態を占有する確率は、恣意的に１に近くなる。
【０００９】
[0009]新たなタイプの量子コンピュータ、それが活用する量子ゲート、および、解状態における確率を集中させるためのアルゴリズムはすべて、オリジナルの波動関数を復元する明確に定義された逆演算を有するという観点において可逆的でなければならない、コンピュータによって実行される任意の演算を保持する従来の量子コンピュータ計算の主義から発している。明確化のために、新たなタイプのコンピュータは、「非可逆的」量子コンピュータと呼ばれるであろう。従来の量子コンピュータにおけるように、１つの波動関数を別の波動関数へマッピングすることではなく、非可逆的量子コンピュータは、１つの密度行列を別の密度行列へマッピングする。名前によって示されるように、このマッピングは、明確に定義された逆演算を有しないことがあり得る。
【００１０】
[0010]この目的を達成するための一般的なアプローチは、ポピュレーションを、任意の初期状態から、興味のあるいくつかの３ＳＡＴ問題を満たす状態または状態のセットへ、非コヒーレントに転送させることである。これは、ポピュレーションを、個々の論理的なクローズを達成しない状態から、これらクローズを満たす状態へ転送させるデシメーションゲート、実質的には、誤り訂正ループを構築することによって達成される。疑似コードでは、このアルゴリズムは、
for each clause in the problem do
Encode the satisfaction of the clause in a temporary scratch bit
if the clause is not satisfied then
Use the scratch bit to perform a controlled rotation of the variables in the clause
end if
Clean up temporary scratch bits by measurement.
end for
として記述されることができる。
【００１１】
[0011]本明細書において、制御された回転は、特定のクローズを達成しない状態のためのポピュレーション喪失をもたらす。多くのクローズを達成しない状態は、ほんの少数を達成しない状態、および、ポピュレーションシンクとして動作するすべてのクローズを満たす解状態よりも、より迅速にポピュレーションを失う。
【００１２】
[0012]量子コンピュータは、有限量子力学系を物理的に変換することによって動作するので、本明細書で説明されたすべての方法は、量子力学状態準備の手段として２次的な用途を有する。これは、所望される物理的効果を観察するために、指定された初期状態における波動関数を準備することがしばしば必要である物理科学において価値を有する。
【課題を解決するための手段】
【００１３】
[0013]本発明のより完全な理解のために、以下の詳細説明および添付図面に対する参照がなされる。
【図面の簡単な説明】
【００１４】
【図１】[0014]挿入演算が、興味のある系１を、所望される状態において準備され、系内において既に存在するビットともつれていない新たなビット２へ結合する図である。
【図２】[0015]削除演算が、Ｎ×Ｎの密度行列３を、（Ｎ−１）×（Ｎ−１）部分行列上へ投影する選択されたビットの状態を測定する図である。ここで、破線は、何らかの軸に沿った測定結果を示す。
【図３】[0016]単一のビット回転演算子が、ｙ＾（「Ａ＾」（「Ａ」は任意の文字）は、「Ａ」の上に「^」が付されたものを表現している。以下同様。）軸の周りに単一のビット４を回転させる図である。ここで、直線矢印は、ブロッホ球体のｘｚ平面内の問題のビットの状態を示す一方、曲線矢印は、回転の方向を示す。真は、状態｜＋ｚ＞と一致するように選択される一方、偽は、｜−ｚ＞となるように選択される。この図におけるｚ軸およびｘ軸の方位は、他の図においても同様に使用される。
【図４】[0017]２ビット回転演算子が、ｙ軸の周りのビット６の回転を制御するために、所望される軸上へのビット５の投影を使用する図である。ここで、ｚ＾軸上への状態５の正の投影が、ビット６を、ｙ＾軸の周りを反時計回りに回転させる。
【図５】[0018]２ビット回転演算子が、ｙ軸の周りのビット６の回転を制御するために、所望される軸上へのビット５の投影を使用する図である。ここで、ｚ＾軸上への状態５の負の投影が、ビット６を、ｙ＾軸の周りを時計回りに回転させる。
【図６】[0019]測定演算子が、所望される軸上への状態３の投影を測定し、測定された値に対応する固有状態へ状態３を投影する図である。ここで、破線は、測定の軸を示す。
【図７】[0020]自己制御された回転ゲートＳＣＲＯＴのための量子回路図である。
【図８】[0021]自己制御された回転ゲートＳＣＲＯＴが、ｙ＾軸の周りの自己の回転を制御するために、所望される軸上へのビットの投影を使用する図である。Ｉでは、ｚ＾軸上への制御ビットの正の投影が、角度π／２までのスクラッチビット８の反時計回りの回転を引き起こす。ＩＩでは、ｘ＾軸上へのスクラッチビットの正の投影が、制御ビットを、反時計回りに回転させる。ＩＩＩでは、スクラッチビットの状態が、ｘ＾に直交する軸に沿って測定され、制御ビットにおける非可逆的な演算を生成する。測定は、「真の軸」ｘ＾に直交する軸に沿っているので、この情報は、制御ビットの状態に関する情報を生成しない。
【図９】[0022]自己制御された回転ゲートＳＣＲＯＴが、ｙ＾軸の周囲の自己の回転を制御するために、所望される軸上へのビットの投影を使用する図である。Ｉでは、ｚ＾軸上への制御ビットの負の投影が、角度π／２までのスクラッチビット８の時計回りの回転を引き起こす。ＩＩでは、ｘ＾軸上へのスクラッチビットの負の投影が、制御ビットを、時計回りに回転させる。ＩＩＩでは、スクラッチビットの状態が、ｘ＾に直交する軸に沿って測定され、制御ビットにおける非可逆的な演算を生成する。測定は、「真の軸」ｘ＾に直交する軸に沿っているので、この情報は、制御ビットの状態に関する情報を生成しない。
【図１０】[0023]ＱＯＲゲートのための量子回路図である。
【図１１】[0024]ＱＯＲゲートが、スクラッチビット１１の状態を制御するために、制御ビット９および１０の状態を使用し、これによって、９または１０が真であれば、ビット１１の最終状態が真となり、それ以外であれば偽となる図である。スクラッチビット１２は、一時的なスクラッチビットであり、偶数または奇数の制御ビットが真であるかを判定するために使用される。Ｉでは、９および１０の状態が、ビット１１および１２の回転を制御する。ＩＩでは、−＾ｚ軸における１２の投影が、ビット１１の回転を制御する。ＩＩＩでは、ビット１１の状態が、πまで回転される。ＩＶでは、ビット１２の状態が、ｘ＾軸に沿って測定され、奇数または偶数の制御ビットが真であるかに関する情報を生成しない。
【図１２】[0025]ＱＯＲゲートが、スクラッチビット１１の状態を制御するために、制御ビット９および１０の状態を使用し、これによって、９または１０が真であれば、ビット１１の最終状態が真となり、それ以外であれば偽となる図である。スクラッチビット１２は、一時的なスクラッチビットであり、偶数または奇数の制御ビットが真であるかを判定するために使用される。Ｉでは、９および１０の状態が、ビット１１および１２の回転を制御する。ＩＩでは、−＾ｚ軸における１２の投影が、ビット１１の回転を制御する。ＩＩＩでは、ビット１１の状態が、πまで回転される。ＩＶでは、ビット１２の状態が、ｘ＾軸に沿って測定され、奇数または偶数の制御ビットが真であるかに関する情報を生成しない。
【図１３】[0026]ＱＯＲゲートが、スクラッチビット１１の状態を制御するために、制御ビット９および１０の状態を使用し、これによって、９または１０が真であれば、ビット１１の最終状態が真となり、それ以外であれば偽となる図である。スクラッチビット１２は、一時的なスクラッチビットであり、偶数または奇数の制御ビットが真であるかを判定するために使用される。Ｉでは、９および１０の状態が、ビット１１および１２の回転を制御する。ＩＩでは、−＾ｚ軸における１２の投影が、ビット１１の回転を制御する。ＩＩＩでは、ビット１１の状態が、πまで回転される。ＩＶでは、ビット１２の状態が、ｘ＾軸に沿って測定され、奇数または偶数の制御ビットが真であるかに関する情報を生成しない。
【図１４】[0027]ＱＡＮＤゲートのための量子回路図である。
【図１５】[0028]ＱＡＮＤゲートが、スクラッチビット１５の状態を制御するために、制御ビット１３および１４の状態を使用し、これによって、１３または１４が真であれば、ビット１５の最終状態が真となり、それ以外であれば偽となる図である。スクラッチビット１６は、一時的なスクラッチビットであり、偶数または奇数の制御ビットが真であるかを判定するために使用される。Ｉでは、１３および１４の状態が、ビット１５および１６の回転を制御する。ＩＩでは、−＾ｚ軸における１６の投影が、ビット１５の回転を制御する。ＩＩＩでは、ビット１５の状態が、πまで回転される。ＩＶでは、ビット１６の状態が、ｘ＾軸に沿って測定され、奇数または偶数の制御ビットが真であるかに関する情報を生成しない。
【図１６】[0029]ＱＡＮＤゲートが、スクラッチビット１５の状態を制御するために、制御ビット１３および１４の状態を使用し、これによって、１３および１４が真であれば、ビット１５の最終状態が真となり、それ以外であれば偽となる図である。スクラッチビット１６は、一時的なスクラッチビットであり、偶数または奇数の制御ビットが真であるかを判定するために使用される。Ｉでは、１３および１４の状態が、ビット１５および１６の回転を制御する。ＩＩでは、−＾ｚ軸における１６の投影が、ビット１５の回転を制御する。ＩＩＩでは、ビット１５の状態が、πまで回転される。ＩＶでは、ビット１６の状態が、ｘ＾軸に沿って測定され、奇数または偶数の制御ビットが真であるかに関する情報を生成しない。
【図１７】[0030]ＱＡＮＤゲートが、スクラッチビット１５の状態を制御するために、制御ビット１３および１４の状態を使用し、これによって、１３および１４が真であれば、ビット１５の最終状態が真となり、それ以外であれば偽となる図である。スクラッチビット１６は、一時的なスクラッチビットであり、偶数または奇数の制御ビットが真であるかを判定するために使用される。Ｉでは、１３および１４の状態が、ビット１５および１６の回転を制御する。ＩＩでは、−＾ｚ軸における１６の投影が、ビット１５の回転を制御する。ＩＩＩでは、ビット１５の状態が、πまで回転される。ＩＶでは、ビット１６の状態が、ｘ＾軸に沿って測定され、奇数または偶数の制御ビットが真であるかに関する情報を生成しない。
【図１８】[0031]ＱＡＮＤＯＲゲートのための量子回路図である。
【図１９】[0032]ＱＡＮＤＯＲゲートが、スクラッチビット１９の状態を制御するために、制御ビット１７および１８の状態を使用し、これによって、１７および１８が真であれば、１９の最終状態は真となり、１７および１８が偽であれば偽となり、それ以外であれば、真と偽との重ね合わせとなる図である。スクラッチビット２０は、一時的なスクラッチビットであり、偶数または奇数の制御ビットが真であるかを判定するために使用される。Ｉでは、１７および１８の状態が、ビット１９および２０の回転を制御する。ＩＩでは、−＾ｚ軸における２０の投影が、ビット１９の回転を制御する。ＩＩＩでは、ビット１９の状態が、πまで回転される。ＩＶでは、ビット２０の状態が、ｘ＾軸に沿って測定され、奇数または偶数の制御ビットが真であるかに関する情報を生成しない。
【図２０】[0033]ＱＡＮＤＯＲゲートは、スクラッチビット１９の状態を制御するために、制御ビット１７および１８の状態を使用し、これによって、１７および１８が真であれば、１９の最終状態が真となり、１７および１８が偽であれば偽となり、それ以外であれば真と偽との重ね合わせとなる図である。スクラッチビット２０は、一時的なスクラッチビットであり、偶数または奇数の制御ビットが真であるかを判定するために使用される。Ｉでは、１７および１８の状態が、ビット１９および２０の回転を制御する。ＩＩでは、−＾ｚ軸における２０の投影が、ビット１９の回転を制御する。ＩＩＩでは、ビット１９の状態が、πまで回転される。ＩＶでは、ビット２０の状態が、ｘ＾軸に沿って測定され、奇数または偶数の制御ビットが真であるかに関する情報を生成しない。
【図２１】[0034]ＱＡＮＤＯＲゲートが、スクラッチビット１９の状態を制御するために、制御ビット１７および１８の状態を使用し、これによって、１７および１８が真であれば、１９の最終状態が真となり、１７および１８が偽であれば偽となり、それ以外であれば真と偽との重ね合わせとなる図である。スクラッチビット２０は、一時的なスクラッチビットであり、偶数または奇数の制御ビットが真であるかを判定するために使用される。Ｉでは、１７および１８の状態が、ビット１９および２０の回転を制御する。ＩＩでは、−＾ｚ軸における２０の投影が、ビット１９の回転を制御する。ＩＩＩでは、ビット１９の状態が、πまで回転される。ＩＶでは、ビット２０の状態が、ｘ＾軸に沿って測定され、奇数または偶数の制御ビットが真であるかに関する情報を生成しない。
【図２２】[0035]ＱＸＯＲゲートのための量子回路図である。
【図２３】[0036]ＱＸＯＲゲートが、スクラッチビット２３の状態を制御するために、制御ビット２１および２２の状態を使用し、これによって、２１  ＸＯＲ  ２２が真であれば、真となり、それ以外であれば偽となる図である。Ｉでは、ｚ＾軸上への２１の正の投影が、πまで反時計回りに回転させる。ＩＩでは、ｚ＾軸上への２２の正の投影が、πまで反時計回りに回転させる。ＩＩＩでは、ｚ＾軸上への負の投影を生成するために、πまで反時計回りに回転する。
【図２４】[0037]ＱＸＯＲゲートが、スクラッチビット２３の状態を制御するために、制御ビット２１および２２の状態を使用し、これによって、２１  ＸＯＲ  ２２が真であれば真となり、それ以外であれば偽となる図である。Ｉでは、ｚ＾軸上への２１の正の投影が、２３を、πまで反時計回りに回転させる。ＩＩでは、ｚ＾軸上への２２の負の投影が、２３の正味の回転を起こさせない。ＩＩＩでは、ｚ＾軸上への正の投影を生成するために、２３が、πまで反時計回りに回転する。
【図２５】[0038]ＱＸＯＲゲートが、スクラッチビット２３の状態を制御するために、制御ビット２１および２２の状態を使用し、これによって、２１  ＸＯＲ  ２２が真であれば真となり、それ以外であれば偽となる図である。Ｉでは、ｚ＾軸上への２１の負の投影が、２３の正味の回転を起こさせない。ＩＩでは、ｚ＾軸上への２２の負の投影が、２３の正味の回転を起こさせない。ＩＩＩでは、ｚ＾軸上への負の投影を生成するために、２３がπまで反時計回りに回転する。
【図２６】[0039]３ＯＲゲートのための量子回路図である。
【図２７】[0040]入力ビット２４、２５または２５のうちのいずれかが真であり、それ以外が偽であれば、真であるビットを生成するために、３ＯＲゲートが、２つのＱＯＲゲートを組み合わせる図である。ここで、入力として２４および２５を使用するＱＯＲゲートは、出力ビット２７を生成する。第２のＱＯＲゲートが、出力ビット２８を生成するために、２７および２６を使用する。一時的なスクラッチビット２７は、２４および２５の状態に関する情報が所望されないのであれば、真の軸へ、または、２４および２５の状態に関する部分的な測定を実行するために別の軸へ直交した測定によって削除されることができる。
【図２８】[0041]合成ゲートが、入力としてビット２９および３０の状態を取り、出力としてビット３１を生成する図である。入力ビットは、可変ビット、または、他のゲートの出力である。合成ゲートにおける使用後、入力ビットの状態は、削除され得るか、または、さらなる使用のために維持され得る。
【図２９】[0042]ＤＥＣゲートのための量子回路図である。
【図３０】[0043]ＤＥＣゲートが、いくつかのクローズを満たさない状態のポピュレーションをデシメートする。可変ビット３２、３３および３４は、図２７に図示される３ＯＲゲートによって、スクラッチビット３５および３６の状態を制御する。ビット３６の状態はその後、制御された回転（破線）によって、可変ビットの状態を回転するために使用される。クローズが満たされるのであれば、可変ビットは回転されない。クローズが満たされないのであれば、可変ビットは、デシメーション角度θまで回転される。スクラッチビット３５および３６は、削除され得るか、または、さらなる使用のために維持され得る。
【発明を実施するための形態】
【００１５】
Ｉ．イントロダクションおよび環境
[0044]要求されるように、本発明の詳細な態様が、本明細書において開示される。しかしながら、開示された態様は、さまざまな形式で具体化され得る、本発明の単なる典型例であることが理解されるべきである。したがって、本明細書において開示された具体的な構成および機能的な詳細は、限定としてではなく、単に、特許請求の範囲のための基礎として、および、実際に適切に詳述された構成に本発明をどのように適用するのかを当業者へ教示するための代表的な基礎として理解されるべきである。
【００１６】
[0045]ある専門用語が、以下の説明において、参照における利便性のみのために使用され、限定することはない。前記専門用語は、具体的に述べられる用語、その派生語、および類似の意味を持つ用語を含むであろう。
【００１７】
ＩＩ．非可逆的量子コンピュータ計算
[0046]１９８５年、Ｄｅｕｔｓｃｈ［１，２］は、１ビットおよび２ビットの演算子の小さなセット、すなわち「ゲート」は、Ｎ個のキュービットにおける任意のユニタリ演算が、これらゲートのみからなる量子回路によって任意の精度へ近似されることができるという点において普遍的であることを示した。
【００１８】
[0047]ユニタリ演算子Ｕは、その逆関数がそのエルミート共役に等しい
Ｕ†Ｕ＝ＵＵ†＝Ｉ    （２）
という特性を有する。ここで、Ｕ†は、エルミート共役であり、Ｉは、アイデンティティである。ユニタリ演算子は、別の波動関数
ψ’＝Ｕψ    （３）
を生成するために、波動関数に対して、または、別の密度行列
ρ’＝ＵρＵ†    （４）
を生成するために、密度行列に対して作用し得る。
【００１９】
[0048]「普遍的」という名前によって示されるように、従来の量子コンピュータ計算の主要原理は、いずれのコンピュータ計算も、所望される初期状態において準備され得る波動関数へ適用されるユニタリ演算からなることである。たとえば、［１１］１７１頁（「・・・普遍的であるゲートの小さなセットが存在する。すなわち、いかなる量子コンピュータ計算も、これらゲートの観点から表現されることができる。」）、または［９］３６頁（「（測定ゲートを除いて）量子コンピュータは、それらのマジックを実行するために非可逆的に動作しなければならないので、量子コンピュータは一般に、入力レジスタと出力レジスタとの両方とともに動作するように設計されている。・・コンピュータ計算処理は一般に、入力レジスタおよび出力レジスタにおけるｎ＋ｍに加えて、多くのＱビットを必要とするであろうが、我々は、今、ｆのコンピュータ計算を、入力および出力レジスタのｎ＋ｍ個のＱビットへ、ユニタリ変換Ｕｆを適用する以外に何もしないものとして見て、これら追加のＱビットを無視するものとする。」）をご覧頂きたい。
【００２０】
[0049]以下に説明されるアルゴリズムは、新たなタイプの量子コンピュータである「非可逆的」量子コンピュータにおいて実行される。その名前によって示されるように、非可逆的コンピュータは、初期密度行列を、原理的には、系の初期状態を復元するために反転されることができない最終的な密度行列へマッピングする演算を実行する。これは、明確に定義された逆関数Ｕ†を有する従来の「可逆的」量子コンピュータによって実行されるユニタリ演算子Ｕと対照的である。可逆性と非可逆性との相違は、熱力学のコンテキストにおいて１世紀以上認識された基本的な物理的相違である［１２］。
【００２１】
[0050]物理学の基本式は可逆的であるが、環境の役割を演じる別の系とのインタラクトすることを許容することによって、興味のある系について、非可逆的な演算が実行され得る［１３］。２つの系がインタラクトすると、系の状態は、環境の状態ともつれるようになり、これによって、２つの系の状態は、独立して説明されることができなくなる。系を単独で記述する単純化された密度行列は、すべての環境的な自由度にわたりトレースすることによって、系および環境をともに記述する密度行列から取得されることができる。
【００２２】
【数１】
2018530849.tif 000003
【００２３】
ここで、添字「ｅ」は環境の状態を、「ｓ」は系の状態を、「ｓｅ」は、環境に結合された系の状態を示す。一般に、このように、環境的な自由度にわたるトレースは、最終的な単純化された密度行列が与えられたと仮定すると、初期密度行列をユニークに復元することができない非可逆的な変換による環境とのインタラクション前に、系の密度行列に関連する、単純化された密度行列を生成するであろう。
【００２４】
[0051]対照的に、従来の量子コンピュータは、初期状態を復元する可逆的な変換が存在する手法で、興味のある系においてＵに対して任意のユニタリ演算を実行する。任意のユニタリ演算後の系の状態は、
【００２５】
【数２】
2018530849.tif 000004
【００２６】
によって与えられる。興味のある系が、周囲環境のような別の系とインタラクトするのであれば、コンピュータ計算は、追加の系の状態が、興味のある系の状態ともつれていないことを維持する方式で実行され［１１，９］、これによって、密度行列は、
【００２７】
【数３】
2018530849.tif 000005
【００２８】
の前と、計算
【００２９】
【数４】
2018530849.tif 000006
【００３０】
の後との両方において、系密度行列と環境密度行列との積へ分離されることができる。
[0052]系および環境のために密度行列は、このように記述されることができるので、環境の状態にわたるトレースは、
【００３１】
【数５】
2018530849.tif 000007
【００３２】
を生成する。
[0053]ここで、最終的な単純化された密度行列は、ユニタリ変換によって、初期密度行列へ関連付けられ、初期の系を復元するために明確に定義された逆演算が存在する。
【００３３】
【数６】
2018530849.tif 000008
【００３４】
[0054]可逆的な量子演算は、系に加えて環境の最終状態が、系の状態と、環境の状態とに分離されることができる非可逆的な量子演算の特別なケースであることが理解されることができる。
【００３５】
[0055]非可逆性を達成するために、２つの新たな演算が必要とされる。図１に図示される挿入演算は、ユーザによって選択された初期状態において、興味のある系におけるビットと以前にもつれていない新たなキュービットを導入する。これは、Ｎ×Ｎ密度行列を、（Ｎ＋１）×（Ｎ＋１）密度行列上へ投影する。図２に図示される削除演算Ｄは、系におけるキュービットの状態を測定する。これは、測定されたキュービットを、測定演算子の固有状態上へ投影し、Ｎ×Ｎ密度行列を、（Ｎ−１）×（Ｎ−１）部分行列上へ投影する。所望されるのであれば、削除されたビットは、問題へ直ちに再挿入されることができ、密度行列のサイズを一定に維持する。
【００３６】
[0056]削除の第２の方法は、系全体を、削除されたビットｄと、残りの系ｓとに分離することからなり、削除されたビットを、その状態を測定することなく、削除後、そのままにする。系ｓにおける任意の測定を実行することは、その後、削除されたビットの状態にわたってトレースすることになるであろう。この削除の方法は、系の状態に関する情報を生成しないが、削除されたビットを、系のビットともつれたままにし、削除されたビットを、アルゴリズムにおける後半において、再挿入されることを不適格にする。
【００３７】
[0057]挿入演算と削除演算との両方は、興味のある系におけるビット数を変化させる演算を許容することによって、量子コンピュータの機能を形式上拡張する。しかしながら、可逆的量子コンピュータ計算と非可逆的量子コンピュータ計算との相違は、形式的ではなく、物理的である。式９および式５によって示されるように、非可逆的コンピュータ計算は、初期密度行列を復元するために興味のある系に含まれていない情報を必要とする一方、可逆的コンピュータ計算は、系に含まれる情報のみを使用して反転されることができる。
【００３８】
[0058]したがって、系を記述するために必要とされるもの以上の冗長ビットを導入し、周囲の環境の状態ともつれていない系の状態を維持することを目的として、迅速な測定を実行する量子誤り訂正は、挿入演算および削除演算の使用に関わらず、可逆的コンピュータ計算の例である。反対に、系に加えて環境のための密度行列が、系を記述する密度行列と、環境を記述する密度行列のとの積へ分離されることができないのであれば、ｎ個の系とｍ個の環境ビットとをもつれさせるユニタリ演算を実行することは、非可逆的コンピュータ計算を表す。系密度行列への非可逆的な変化を達成するための自然な非コヒーレンス処理を使用することは、系と環境とをもつれさせるユニタリ演算が、ユーザによって誘導された演算ではなく、自然の処理によって生じる第２のケースの特定の例である。
【００３９】
ＩＩＩ．回転および測定ゲート
[0059]量子ゲートは、いくつかの所望される物理的な変化を達成させるために、興味のある系におけるビットのいくつかの部分集合へ適用される一連の量子演算である。非可逆的ゲートは、たとえば、多数の初期状態が、いくつかの最終状態へマッピングされ得るように、系のオリジナルの状態を復元することが可能ではない追加の特性を有する。これは、多くの潜在的な状態が、興味のある問題を解くような所望される特性を有する状態の部分集合よりも指数関数的に大きくなり得る３ＳＡＴのコンテキストにおいて、特に所望される特性である。
【００４０】
[0060]個々の量子ビットを表すための一般的な手法は、ブロッホ球体の表面へ２つの状態系をマッピングすることである。選択されたいくつかの軸上への量子ビットの投影、または、その軸の周囲の回転が、パウリスピン演算子
【００４１】
【数７】
2018530849.tif 000009
【００４２】
【数８】
2018530849.tif 000010
【００４３】
および
【００４４】
【数９】
2018530849.tif 000011
【００４５】
を用いてなされることができる。
[0061]一般に、量子ビットは、ブロッホ球体における任意のベクトルへマッピングされ得るが、このアルゴリズムの好適な実施は、常にｘｚ面へ含まれるビットを利用するので、単一のビットが、ｙ軸の周囲のみを回転されるようになる。他の極角度によってエンコードされた情報は、このアルゴリズムのために必要とされないので、量子誤り訂正のような他の目的のために使用されることは自由である。量子ビットは、ｚ＾軸において正の投影を有するのであれば、真であり、負の投影を有するのであれば、偽であるとして選択される。
【００４６】
ａ．１ビットおよび２ビット回転ゲート
[0062]ビットｎは、図３において図解されるように、単一ビット演算子
【００４７】
【数１０】
2018530849.tif 000012
【００４８】
によって、ｘｚ平面において回転される。
[0063]軸ｉ上へのビットｎの投影は、２つのビット演算子によってビットｍを回転するために使用されることができる。
【００４９】
【数１１】
2018530849.tif 000013
【００５０】
ここで、符号の選択は、Ｘｎまたは¬Ｘｎの値が、回転を制御するために使用されるかに依存する。軸ｉにおける正の投影は、図４に図示される反時計回りの回転を引き起こす一方、負の投影は、図５に図示される時計回りの回転を引き起こす。
【００５１】
[0064]そうではないと述べられていないのであれば、このドキュメントにおいて定義された演算子およびゲートは、変数の不在以外の変数の状態が、制御パラメータとして動作するように定義されるであろう。変数の不在を制御パラメータとして使用することがより便利であれば、これは、指数関数の内部の符号の変化によって達成されることができる。
【００５２】
[0065]表記における単純化のために、制御された回転演算子
【００５３】
【数１２】
2018530849.tif 000014
【００５４】
を定義することが有用である。ここで、ビットｍは、ビットｎが、軸ｉにおいて正の投影を有するのであれば、角度θまで回転され、ビットｎが、この軸において負の投影を有するのであれば、不変のままである。
【００５５】
[0066]式１６の
【００５６】
【数１３】
2018530849.tif 000015
【００５７】
演算子は、物理的に実現することが困難であり得るので、制御された回転は、平面外回転を使用して実施するために、より簡単であり得る。ｘ軸の周囲の回転を
【００５８】
【数１４】
2018530849.tif 000016
【００５９】
として定義すると、式１６は、
【００６０】
【数１５】
2018530849.tif 000017
【００６１】
として記述されることもできる。
[0067]条件付き回転の第２のバリエーションは、制御ビットが偽である場合、回転を実行し、制御ビットが真である場合、ターゲットビットを無回転のままにすることである。
【００６２】
【数１６】
2018530849.tif 000018
【００６３】
を定義すると、
【００６４】
【数１７】
2018530849.tif 000019
【００６５】
を理解されることが可能であり得る。
ｂ．測定ゲート
[0068]軸ｉ上へのビットｎの投影は、投影演算子
【００６６】
【数１８】
2018530849.tif 000020
【００６７】
を使用して、スピン行列
σｉ（θ，φ）＝ｃｏｓ（θ）σｚ＋ｓｉｎ（θ）ｃｏｓ（φ）σｘ＋ｓｉｎ（θ）ｓｉｎ（φ）σｙ    （２１）
の固有状態｜γ＞上へ投影することによって、測定される。ここで、γｉは、固有状態｜γｉ＞に関連付けられた固有値である。この演算子は、図６において図解される。
【００６８】
[0069]量子力学の法則に従うと、軸ｉ上へのビットｎの投影を測定することは、ビットが、測定演算子の固有状態、ここでは、測定されている軸に沿った正（｜γｉ＞＝｜１／２＞）または負（｜γｉ＞＝｜−１／２＞）の固有状態を占有することを強要する。測定されているビットの状態が、他のビットの状態ともつれているのであれば、この測定は、問題となっているビットの状態に関する部分的な情報を与え得る。反対に、いくつかの場合には、測定の軸は、他のビットの状態に関する情報を与えないように選択されることができる。ここで、「部分的な測定」は、１つまたは複数のビットの状態に関するいくつかの情報が収集されるが、それらの量子状態をユニークに決定するための十分な情報ではないことを意味する。
【００６９】
ＩＶ．非可逆的ゲート
[0070]以下に定義される非可逆的ゲートの一般的な設計は、真である（｜＋ｚ＞）ように初期化された一時的なスクラッチビットを導入し、その後、論理表現が真であると評価するのであれば、ビットが、いくつかの軸において正の投影を有し、論理表現が偽であると評価するのであれば、ビットが、同じ軸上へ負の投影を有することができるように量子演算を実行することである。この軸は、「真の軸」と命名される。その後、スクラッチビットの状態は、新たなゲートへの入力として、または、問題における他の変数の回転を制御するために使用されることができる。もはや必要とされない場合、スクラッチビットに含まれる情報は、真の軸に直交する測定によって破壊される。
【００７０】
[0071]ここで、どの軸が、「真の軸」として使用されるかの選択は、完全に任意である。しかしながら、これに直交する軸に沿ったスクラッチビットを測定する選択は、物理的に意味がある。真の軸に対して角度θで方位付けられた軸上へのビットの投影を測定することは、θ＝π／２の場合における無情報から、θ＝０の場合における完全な情報まで変動する、論理的な表現が満たされているか否かに関する部分的な情報を生成する。したがって、このセクションで定義されたすべての非可逆的ゲートは、スクラッチビットの状態が、真の軸に対して角度θ≠π／２で方位付けられた軸に沿って測定されるという一般論を有する。
【００７１】
[0072]このモデルからの別の物理的に意味のある派生は、式が真であると評価するのであれば、スクラッチビットを、状態｜α＞へ投影し、式が偽であると評価するのであれば、状態｜β＞上へ投影することである。ここで、｜α＞および｜β＞は、直交しない。この場合、真の軸を定義することは可能ではない。しかしながら、スクラッチビットの状態は、密度行列に対して非可逆的な演算を生成するような手法で、新たなゲートへの入力として、または、問題における他の変数に対して作用するために使用され得る。
【００７２】
ａ．ＱＣＯＰＹゲート
[0073]量子コピーゲートは、初期状態｜＋ｚ＞において新たなビットｓを導入し、既存のビットｃの状態を複写できるように、新たなビットｓを回転させる。
【００７３】
【数１９】
2018530849.tif 000021
【００７４】
ｂ．ＱＮＯＴゲート
[0074]量子ＮＯＴゲートは、初期状態｜＋ｚ＞において新たなビットｓを導入し、既存のビットｃに対して全く反対になるように、新たなビットｓを回転させる。
【００７５】
【数２０】
2018530849.tif 000022
【００７６】
ｃ．自己制御された回転
[0075]一時的なスクラッチビットの使用は、ビットの状態が、それ自身の回転の制御を、または、条件付きの回転の使用を可能にする。軸ｉ上への自身の投影に従うビットｎの回転は、真であるように初期化されたスクラッチビットｓを導入し、自己制御された回転を生成するために、２つの２ビット回転および測定を適用することによって達成されることができる。
【００７７】
【数２１】
2018530849.tif 000023
【００７８】
[0076]ここで、ビットｎの状態は、状態ｎのビットを回転するために使用されるスクラッチビットを回転するために使用される。ビットｎが元々真であれば、第１のステップ後、スクラッチビットの状態は、｜＋ｘ＞であり、これによって、第２のステップは、角度θまでビットを回転するようになる。ビットｎが元々偽であれば、第１のステップは、スクラッチビットを、｜−ｘ＞へ回転させ、第２のステップは、ビットｎを−θまで回転させる。ビットｎの状態が、ｘ軸−「真の軸」−上へのスクラッチビットの投影においてエンコードされると、ｚ軸のように、これに直交する軸に沿った測定が、ビットｎの状態に関するいずれの情報も測定することなく、回転を、非可逆的にする。このゲートは、量子回路図とともに、自己制御されたビットが、制御軸において正の投影および負の投影をそれぞれ有する場合における個々のビットの進展を図示する図７、図８、および図９において図解される。
【００７９】
[0077]密度行列演算として記述されると、最初の２つのステップは、
【００８０】
【数２２】
2018530849.tif 000024
【００８１】
と
【００８２】
【数２３】
2018530849.tif 000025
【００８３】
とをマッピングする。ここで、状態の順序は、｜ｓ，ｎ＞＝｜＋ｚ，＋ｚ＞，｜＋ｚ、−ｚ＞，｜−ｚ，＋ｚ＞，｜−ｚ，−ｚ＞である。ｚ＾軸に沿ってスクラッチビットを測定することは、上左または下右の２×２の部分行列のいずれかを選択する。測定の結果に関わらず、ビットｎは、ｚ軸上に正の投影を有するのであれば、角度θまで回転され、負の投影を有するのであれば、−θまで回転される。ｚ＾ではなく、軸ｉ＾＝ｃｏｓ（φ）ｘ＾＋ｓｉｎ（φ）ｚ＾上への投影によるビットの回転の制御は、
【００８４】
【数２４】
2018530849.tif 000026
【００８５】
によって達成される。
ｄ．非可逆的量子ＯＲゲート
[0078]より洗練された状態操作は、論理演算の出力を、スクラッチビットの状態へエンコードすることによって可能とされる。
【００８６】
【数２５】
2018530849.tif 000027
【００８７】
を定義する。ここで、真であるように初期化された第２のスクラッチビットは、制御ビットのいずれかまたは両方が真であれば真であり続け、それ以外は、偽へ回転される。以前に述べたように、変数の不在は、適切な符号変化のセットによって、スクラッチビットの状態を制御するために使用されることができる。その測定前に、ｚ＾軸上へのスクラッチビットｓ１の投影は、偶数または奇数の入力変数ｃ１およびｃ２が真であるかをエンコードする。１つだけが真であれば、ｓ２が、さらにπ／２まで回転され、これによって、ＴＴ、ＴＦ、およびＦＴは、ｚ＾軸上への、ｓ２のための同じ投影を生成する。以前に述べたように、変数の不在は、適切な符号変化のセットによって、スクラッチビットの状態を制御するために使用されることができる。このゲートは、量子回路図と、両入力ビットが真、一方が真で他方が偽、および両方とも偽、それぞれの場合における個々のビットの進展とを図示する図１０、図１１、図１２、および図１３に図解される。表０．１は、ＱＯＲゲートの前と、このゲートの適用後であるが任意のスクラッチビットの測定前との両方の変数およびスクラッチビットの状態を与える。
【００８８】
[0079]量子ＮＯＲゲートは、スクラッチビットの最終回転を省くことによって発見される。
【００８９】
【数２６】
2018530849.tif 000028
【００９０】
【表１】
2018530849.tif 000029
【００９１】
ｅ．非可逆的量子ＡＮＤゲート
[0080]ＱＯＲゲートに類似の方法を使用して、非可逆的ＡＮＤゲートは、π／２から−π／２までＳＣＲゲートの角度を変化させることによって取得されることができる。
【００９２】
【数２７】
2018530849.tif 000030
【００９３】
このゲートは、量子回路図と、両入力ビットが真、一方が真で他方が偽、および両方とも偽、それぞれの場合における個々のビットの進展とを図示する図１４、図１５、図１６、および図１７に図解される。
【００９４】
[0081]量子ＮＡＮＤゲートは、スクラッチビットの最終回転を省くことによって発見される。
【００９５】
【数２８】
2018530849.tif 000031
【００９６】
ｆ．ＡＮＤおよびＯＲキャラクタを組み合わせた非可逆的ゲートＡＮＤＯＲゲート
[0082]ＡＮＤおよびＯＲのキャラクタを組み合わせるゲートは、ＳＣＲゲートの角度を、−π／２とπ／２との間で連続的に変化させることによって取得されることができる。
【００９７】
【数２９】
2018530849.tif 000032
【００９８】
このゲートは、量子回路図と、両入力ビットが真、一方が真で他方が偽、および両方とも偽、それぞれの場合のための個々のビットの進展とを図示する図１８、図１９、図２０、および図２１に図解される。ここで、真であるように初期化されたスクラッチビットは、両入力が真であれば、真であり続け、両入力が偽であれば、偽へフリップする。一方の入力が真であり、他方が偽であれば、スクラッチビットは、真と偽との重ね合わせを占有するであろう。
【００９９】
｜ｓ＞＝ｃｏｓ（π／４−θ／２）｜＋ｚ＞＋ｓｉｎ（π／４−θ／２）｜−ｚ＞    （３４）
[0083]ＱＡＮＤＯＲと同じ手法でＮＡＮＤおよびＮＯＲキャラクタを組み合わせるゲートは、スクラッチビットの最終回転を省くことによって発見されることができる。
【０１００】
【数３０】
2018530849.tif 000033
【０１０１】
ｇ．非可逆的量子ＸＯＲゲート
[0084]ＱＯＲおよびＱＡＮＤのゲートに類似した方法を使用して、非可逆的ＸＯＲゲートが、
【０１０２】
【数３１】
2018530849.tif 000034
【０１０３】
によって取得されることができる。
[0085]このゲートは、量子回路図と、両入力ビットが真、一方が真で他方が偽、および両方とも偽、それぞれの場合のための個々のビットの進展とを図示する図２２、図２３、図２４、および図２５において図解される。
【０１０４】
[0086]量子ＸＮＯＲゲートは、スクラッチビットの最終回転を省くことによって取得される。
【０１０５】
【数３２】
2018530849.tif 000035
【０１０６】
【表２】
2018530849.tif 000036
【０１０７】
ｈ．非可逆的量子３ＯＲゲート
[0087]２つのＱＯＲゲートと中間的なスクラッチビットとを使用することによって、特定の量子状態が、３つの可変論理クローズを満たすか否かを、第２のスクラッチビットがエンコードすることが可能となる。
【０１０８】
【数３３】
2018530849.tif 000037
【０１０９】
両スクラッチビットを真になるように初期化し、クローズが満たされるのであれば、ｓ２は真のままであり、それ以外は、偽へ回転される。このゲートは、図２６および図２７において概略的に図示される。より一般的に、ＱＯＲ、ＱＡＮＤ、およびＱＡＮＤＯＲのゲートの出力をつなぐことによって、図２８に図解されている合成ゲートを生成する。変数ｍ１またはｍ２が真であるかをエンコードするビットｓ１は、式３８におけるように、
【０１１０】
【数３４】
2018530849.tif 000038
【０１１１】
とのｘ＾軸上への投影によって削除されることができるか、または、その後の論理演算における使用のために維持されることができる。表０．２は、任意の回転を適用する前と、回転の適用後であるが任意のスクラッチビットの測定前との両方の変数およびスクラッチビットの状態を与える。
【０１１２】
ｉ．非可逆的量子デシメーションゲート
[0088]３ＳＡＴ問題は、この問題におけるすべてのクローズを満たす状態によってのみ解決される。３ＯＲゲートは、スクラッチビットｓ２の状態における特定のクローズの充足をエンコードするので、クローズＭに含まれるすべての変数のための条件付き回転ゲートによって、クローズを満たしていない任意の状態のためのポピュレーションの漸進的なデシメーションを達成するために使用されることができる。
【０１１３】
【数３５】
2018530849.tif 000039
【０１１４】
クローズが満たされるのであれば、変数Ｘｍ１，Ｘｍ２およびＸｍ３の状態は影響されない。満たされないのであれば、各変数は、ｙ軸の周囲を角度θまで回転される。各変数の状態を、その逆の値へ回転させることによって、このデシメーション演算子は、オリジナル状態のポピュレーションを低減し、クローズＭにおける変数を除いて、オリジナルの状態と同一である状態のポピュレーションを増加させる。ｘ＾軸に沿ってスクラッチビットを測定することによって、クローズの充足に関するいずれの情報を与えることもなく、このポピュレーション転送を非可逆的にする。このゲートは、図２９および図３０に図解される。
【０１１５】
[0089]測定後、スクラッチビットの状態にわたってトレースした場合、特定のスクラッチビットの状態が、ブラ側およびケット側において異なるすべての項を総和するとゼロになるであろう。
【０１１６】
【数３６】
2018530849.tif 000040
【０１１７】
を記述すると、
【０１１８】
【数３７】
2018530849.tif 000041
【０１１９】
および
【０１２０】
【数３８】
2018530849.tif 000042
【０１２１】
が理解されることができる。
[0090]特に、スクラッチビットｓ４を測定することは、交差項
【０１２２】
【数３９】
2018530849.tif 000043
【０１２３】
【数４０】
2018530849.tif 000044
【０１２４】
【数４１】
2018530849.tif 000045
【０１２５】
等を不要にする。ここで、ケット側は、このクローズを満たす初期状態によって生じ、ブラ側は、ＤＥＣ演算子によって初期状態｜ＦＦＦ＞の回転から生じるが、その逆もあり得る。状態｜ＦＦＦ＞は、ｓ４＝Ｆを生成する唯一の状態であるので、デシメーションゲートの条件付き回転によって生じるすべての交差項は、単純化された密度行列へのゼロ寄与を与える。
【０１２６】
[0091]デシメーション手順の簡単な例は、単一の変数の状態をフリップするために、デシメーション手順を利用することによって例示される。ここで、状態｜α＞は、特定のクローズについて真であるように評価する一方、状態｜α’＞は、偽であるように評価する。｜α＞および｜α’＞は、変数ｍの状態を除いて同一である。クローズの充足は、スクラッチ変数の状態においてエンコードされるので、３ＯＲ演算子後であるが条件付き回転前の密度行列は、状態順序｜Ｔ，α＞，｜Ｔ，α’＞，｜Ｆ，α＞，｜Ｆ，α’＞を用いて
【０１２７】
【数４２】
2018530849.tif 000046
【０１２８】
と記述されることができる。
[0092]スクラッチビットの状態が、ＣＲｓ→ｍに従って可変ビットｘｍの状態を回転させるために使用される場合、密度行列は、
【０１２９】
【数４３】
2018530849.tif 000047
【０１３０】
となる。
[0093]α’からαへのポピュレーションの転送は、演算子
【０１３１】
【数４４】
2018530849.tif 000048
【０１３２】
によって完了され、
【０１３３】
【数４５】
2018530849.tif 000049
【０１３４】
を生成するために、ｚ＾、「真の軸」に直行する軸に沿ったスクラッチビットの状態を測定する。ここで、ポピュレーションの転送は、α’の初期ポピュレーションと回転角度とに依存するが、非対角コヒーレンス項ραα’またはρα’αに依存しない。この回転角度は、初期状態ポピュレーションがデシメートされる程度を制御するので、「デシメーション角度」とも称され得る。
【０１３５】
[0094]最後に、スクラッチビットの状態にわたってトレースすることは、新たな単純化された密度行列
【０１３６】
【数４６】
2018530849.tif 000050
【０１３７】
を生成する。ここで、ポピュレーションの転送は、α’の初期ポピュレーションと回転角度とに依存するが、非対角コヒーレンス項ραα’またはρα’αに依存しない。
ｊ．非可逆的グローバルデシメーションゲート
[0095]このデシメーション手順は、グローバルデシメーションゲート
【０１３８】
【数４７】
2018530849.tif 000051
【０１３９】
を生成するために、問題における各クローズへ適用されることができる。ここで、
【０１４０】
【数４８】
2018530849.tif 000052
【０１４１】
は、クローズがデシメートされる順序を与え、θＭは、クローズＭのためのデシメーション角度を与える。構築によって、すべてのクローズを満たす状態は、ＳＡＴＤＥＣによって変化されない一方、すべての非解状態は、少なくとも１つのクローズによってデシメートされる。
【０１４２】
Ｖ．３ＳＡＴを解くためのアルゴリズム
[0096]上記で定義したように、ＳＡＴＤＥＣゲートの適用は、興味のある３ＳＡＴ問題におけるすべての論理クローズに対応するデシメートＤＥＣゲートを適用することに相当する。
【０１４３】
[0097]単一のＳＡＴＤＥＣの適用による状態ｓの確率の変化は、
【０１４４】
【数４９】
2018530849.tif 000053
【０１４５】
によって与えられる。ここで、転送行列Ｔは、クローズの順序と、関連付けられた回転角度
【０１４６】
【数５０】
2018530849.tif 000054
【０１４７】
にパラメータ的に依存する。ポピュレーションの転送はｓｉｎ２（θ）として進むので、それは、先頭順序へ向かって、デシメーション角度における二次方程式である。平衡への収束の速度は、最も遅い固有ベクトルの減衰によって与えられる。Ｔｓ’→ｓは非対称であるので、その固有ベクトルは、直交ではない。
【０１４８】
[0098]総確率の維持は、非ゼロの固有値を有するいずれの固有状態も、ゼロトレースを有さねばならないことを意味する一方、すべてのｓについてＰｓ≦１との制約は、すべての非ゼロの固有値が負でなければならないことを意味する。解状態ｓ＊は決してデシメートされないので、すべてのｓについて、
【０１４９】
【数５１】
2018530849.tif 000055
【０１５０】
である。
[0099]少なくとも１つの解状態ｓ＊が存在すると仮定すると、すべての固有ベクトルＴｓ→ｓ’が、少なくとも１つの解状態を含む必要がある。問題を解かない固有ベクトルλ→（「Ａ→」（「Ａ」は任意の文字）は、「Ａ」の上に「→」が付されたものを表現している。以下同様。）に含まれる各状態ｓは、少なくとも１つのクローズを失わねばならず、クローズ外の変数についてｓに等しく、クローズ内の変数についてｓ＊に等しいように定義された状態ｓ’上へのデシメーションアルゴリズムによって投影されねばならない。ｓ’が解ではないのであれば、いくつかのクローズを失い、新たなクローズ外の変数についてｓ’に等しく、新たなクローズ内の変数についてｓ＊に等しいｓ’’上へ投影されねばならない。有限数のクローズのために、この手順は、ｓ＊または他のいくつかの解状態で、終了せねばならない。特に、非解状態のみからなるゼロ固有値を有する固有ベクトルは存在しない。
【０１５１】
ａ．平衡への収束
[0100]デシメーションアルゴリズムのための収束の速度は、小さな固有値を有する固有ベクトルの存在によって制限される。θ０を、興味のある問題におけるクローズに対応する最小のデシメーション角度とする。迅速に減衰する固有ベクトルが、
【０１５２】
【数５２】
2018530849.tif 000056
【０１５３】
に相当、または、それよりも大きなλを有し、緩慢に減衰する固有ベクトルが、
【０１５４】
【数５３】
2018530849.tif 000057
【０１５５】
を有するように定義する。そのような固有値のための最小の大きさは存在しないが、λが小さいとの要件は、緩慢に減衰する固有ベクトルをユニークに決定する。固有値方程式
【０１５６】
【数５４】
2018530849.tif 000058
【０１５７】
として式５１を記述すると、すべてのｓ’についてＴｓ→ｓ’＝０ではないのであれば、すなわち、ｓが解状態ではないのであれば、
【０１５８】
【数５５】
2018530849.tif 000059
【０１５９】
は、Ｔｓ→ｓ’に対して無視できる。
[0101]緩慢に減衰する固有ベクトルのための非解状態のポピュレーションは、すべての非解状態ｓおよびｓ’について
【０１６０】
【数５６】
2018530849.tif 000060
【０１６１】
を設定し、ΣｓＰｓ＝１を要求することによって発見されることができる。この固有ベクトルのための解状態のポピュレーションは、すべての解状態ｓ＊について
【０１６２】
【数５７】
2018530849.tif 000061
【０１６３】
を設定し、すべてのｓ＊に対する
【０１６４】
【数５８】
2018530849.tif 000062
【０１６５】
と、
【０１６６】
【数５９】
2018530849.tif 000063
【０１６７】
とを要求することによって発見される。解が存在しなれば、式５３は、非解状態のための平衡確率分布を定義する。
[0102]緩慢に減衰する固有状態のための確率分布は、デシメーション角度θ→の選択によって決定されるので、緩慢に減衰する確率のボトルネックは、ＳＡＴＤＥＣの各反復においてθ→を変化させることによって中断されることができる。この確率分布は、非常に緩慢に減衰し得るので、「疑似平衡分布」と称されるであろう。
【０１６８】
[0103]疑似平衡固有ベクトルは、２つのステップにおいて発見されることができる。第１に、式５３が、非解ポピュレーションについて解かれ、ΣｓＰｓ＝１になるように規格化される。解状態のためのポピュレーションは、すべての解状態ｓ＊のために
【０１６９】
【数６０】
2018530849.tif 000064
【０１７０】
を設定し、すべてのｓ＊に対する
【０１７１】
【数６１】
2018530849.tif 000065
【０１７２】
と、
【０１７３】
【数６２】
2018530849.tif 000066
【０１７４】
とを要求することによって発見され、これによって、多く固有分散がトレースなしとなる。
[0104]
【０１７５】
【数６３】
2018530849.tif 000067
【０１７６】
という条件は、緩慢に減衰する固有分布のための確率分布をユニークに決定するので、対偶もまた真であり、式５３および式５５によって決定されるもの以外の任意の非解固有分布は、
【０１７７】
【数６４】
2018530849.tif 000068
【０１７８】
に相当するか、またはそれよりも大きな減衰速度を有さねばならない。
ｂ．非解確率の減衰
[0105]デシメーション角度
【０１７９】
【数６５】
2018530849.tif 000069
【０１８０】
の所与の選択のためにＳＡＴＤＥＣを繰り返し適用することは、確率分布を、２つの時間スケールにおいて進展させる。所与の時間における確率分布は、固有分布にわたる総和
【０１８１】
【数６６】
2018530849.tif 000070
【０１８２】
として記述されることができる。ここで、Ｖ→は、式５３および式５５によって定義される疑似平衡固有分布であり、Ｗ→ｎは、残りの固有分布であり、減衰速度は、
【０１８３】
【数６７】
2018530849.tif 000071
【０１８４】
に相当するか、または、それよりも大きい。同じ転送行列を繰り返し適用した結果、迅速な「ブローオフ」となる。ここでは、迅速に減衰する固有分布に含まれる非解確率が、解状態のセットへ迅速に転送され、その後、長期間の停滞となり、ここでは、非解確率が疑似平衡分布へ接近し、結果として、解状態への緩慢な転送となる。
【０１８５】
[0106]疑似均衡分布の緩慢な減衰は、異なるクローズに対応するデシメーション角度を変動させることによって促進されることができる。緩慢に減衰する固有分布は、式５３によってθ→によって決定されるので、θ→を非断熱的に変動させることは、オリジナルの疑似平衡分布を新たな固有ベースへ投影し、ここでは、疑似平衡分布は、実質的に異なり得る。Ｖ→（１）が、転送行列Ｔ（１）のための緩慢に減衰する固有分布であり、Ｖ→（２）が緩慢であり、
【０１８６】
【数６８】
2018530849.tif 000072
【０１８７】
が転送行列Ｔ（２）のための迅速に減衰する固有分布であり、
【０１８８】
【数６９】
2018530849.tif 000073
【０１８９】
であれば、転送行列Ｔ（１）からＴ（２）への変化は、係数Ａｎがゼロに減衰すると、第２のブローオフとなる。
[0107]係数ＡＶは、緩慢に減衰する固有分布の減衰速度をゼロとして近似することによって発見されることができ、これによって、
Ｔ（１）Ｖ（１）＝Ｖ（１）    （５８）
Ｔ（２）Ｖ（２）＝Ｖ（２）    （５９）
となる。
ΔＴ＝Ｔ（２）−Ｔ（１）およびΔＶ＝Ｖ（２）−Ｖ（１）とし、これによって、式５７は、
【０１９０】
【数７０】
2018530849.tif 000074
【０１９１】
と記述されることができる。
Ｔ（２）の固有ベースで、ポピュレーション差分
【０１９２】
【数７１】
2018530849.tif 000075
【０１９３】
を展開すると、それは、
【０１９４】
【数７２】
2018530849.tif 000076
【０１９５】
に従い、これによって、Ｖ→（１）およびＶ→（２）が最も相違する場合、ブローオフが最大になる。
ｃ．前後反復
[0108]緩慢に減衰する固有分布からポピュレーションを転送させるための単純な手順は、ＳＡＴＤＥＣの１つの反復のため、特定のクローズに対応するデシメーション角度をランダムに変動させ、その後、次の反復のため、オリジナルの転送行列を復元するために、オリジナルのデシメーション角度へ戻すことである。Ｔ（１）＝Ｔ（θ→（１））を、すべてのクローズＣのための設定
θ→（１）［Ｃ］＝θ０    （６３）
に対応する転送行列とし、Ｔ（２）＝Ｔ（θ→（２））とする。ここで、
θ→（２）［Ｃ］＝θ０（１＋ησＣ）    （６４）
であり、σＣは、等しい確率で１または−１になるように選択される。
【０１９６】
[0109]個々のクローズＣによる転送行列の積として、転送行列Ｔ＝ΠＣＴ（Ｃ）を記述し、Ｔ（Ｃ）は、θＣにおける二次方程式であることに注目されたい。
【０１９７】
【数７３】
2018530849.tif 000077
【０１９８】
[0110]転送行列におけるこの変化による、緩慢に減衰する固有分布のための状態ｓのためのポピュレーションにおける変化は、
【０１９９】
【数７４】
2018530849.tif 000078
【０２００】
のように記述されることができ、ここで、ΔＶ（Ｃ）は、Ｔ（Ｃ）における一次訂正オフセット変化である一方、ΔＶ（Ｒ）は、新たな疑似平衡分布が式５３に従うことを強要する残りの訂正である。
【０２０１】
[0111]先頭順序に対する、デシメーション角度における小さな変化による状態ｓのためのポピュレーションにおける変化は、
【０２０２】
【数７５】
2018530849.tif 000079
【０２０３】
を設定することによって発見され、これによって、２倍小さな項
【０２０４】
【数７６】
2018530849.tif 000080
【０２０５】
を無視した後、
【０２０６】
【数７７】
2018530849.tif 000081
【０２０７】
となる。
式６６からこれら項を引くことによって、残りの訂正
【０２０８】
【数７８】
2018530849.tif 000082
【０２０９】
のための線形系を生成する。ここで、右手側は、期待値０を有する。
[0112]前後反復の第２のステップは、すべてのデシメーション角度を、オリジナルの値へ戻し、これによって、
ΔＴ（Ｃ）→−ΔＴ（Ｃ）    （７０）
および
ΔＶ→→−ΔＶ→    （７１）
となり、緩慢に減衰する固有分布Ｖ→（２）が、Ｔ（１）の固有ベースへ投影されるようになる。
【０２１０】
[0113]ポピュレーションは、緩慢に減衰する固有分布から、迅速に減衰する固有分布へ転送されるので、転送行列への両変化とも、総非解確率の損失となる。第２の転送後、緩慢に減衰する固有分布の係数は
【０２１１】
【数７９】
2018530849.tif 000083
【０２１２】
によって与えられる。
[0114]
【０２１３】
【数８０】
2018530849.tif 000084
【０２１４】
および
【０２１５】
【数８１】
2018530849.tif 000085
【０２１６】
で、
【０２１７】
【数８２】
2018530849.tif 000086
【０２１８】
になるものとする。その後、
【０２１９】
【数８３】
2018530849.tif 000087
【０２２０】
となる。σＣおよびσＣ’は、平均値０を有する独立したランダムな変数であるので、
【０２２１】
【数８４】
2018530849.tif 000088
【０２２２】
および
【０２２３】
【数８５】
2018530849.tif 000089
【０２２４】
であり、ここで、
【０２２５】
【数８６】
2018530849.tif 000090
【０２２６】
は、状態ｓによって失われたクローズの数であり、これによって、すべての非解状態について、ＮｓＣ≧１となる。これから、期待値
【０２２７】
【数８７】
2018530849.tif 000091
【０２２８】
に従い、前後の反復サイクルによる、緩慢に減衰する固有分布からのポピュレーションの喪失は、ユーザ制御されたパラメータηによって制御される。
【０２２９】
【数８８】
2018530849.tif 000092
【０２３０】
を選択することは、すべての非解確率が、
【０２３１】
【数８９】
2018530849.tif 000093
【０２３２】
に対して大きい時間スケールにおいて減衰することを保証する。
ＶＩ．前後反復の作用例
[0115]前後反復の単純な例は、｜ＴＴＴ＞が唯一の解である３変数３ＳＡＴ問題を解くことによって取得される。これは、表０．３のクローズ０〜６についてＤＥＣ演算を実行することに対応する。｜ＴＴＴ＞以外の各状態は、単一のクローズを失い、θＣにおける先頭順序へ、ポピュレーションを、単一の変数がフリップされている３つの状態へ転送させることによってデシメートされる。すべてのクローズについて、θＣ＝θ０＝０．１を選択し、θにおける先頭順序へ項を含めることは、転送行列
【０２３３】
【数９０】
2018530849.tif 000094
【０２３４】
を生成し、ここで、状態順序は、表０．３から取られる。この転送行列の固有値および固有分布は、表０．４によって与えられる。
【０２３５】
【表３】
2018530849.tif 000095
【０２３６】
【表４】
2018530849.tif 000096
【０２３７】
[0116]η＝０．２およびσ→＝（１，１，１，１，−１，−１，−１）を設定することは、転送行列を、
【０２３８】
【数９１】
2018530849.tif 000097
【０２３９】
へ変化させ、ここで、固有値および固有分布は、表０．５によって与えられる。
【０２４０】
【表５】
2018530849.tif 000098
【０２４１】
[0117]表０．４と表０．５との両方において、Ｖ→（１）およびＶ（２）の減衰速度は、
【０２４２】
【数９２】
2018530849.tif 000099
【０２４３】
に対して小さい一方、固有分布Ｗ→ｎの減衰速度は、この値に相当するか、それよりも大きい。
[0118]Ｔ（１）からＴ（２）へ転送行列を変化させることは、Ｖ（１）を、新たな固有ベース
【０２４４】
【数９３】
2018530849.tif 000100
【０２４５】
へ投影する。迅速に減衰する固有分布Ｗ→ｎの係数が、ゼロへ減衰すると、オリジナルの転送行列への復帰は、Ｖ（２）を、オリジナルの固有ベース
【０２４６】
【数９４】
2018530849.tif 000101
【０２４７】
へ投影し、これによって、前後反復後、Ｖ→（１）の係数は、１．００５＊．９５６＝０．９６〜１−η２となる。
ａ．アルゴリズム実行時間
[0119]迅速に減衰する固有ベクトルは、
【０２４８】
【数９５】
2018530849.tif 000102
【０２４９】
またはそれよりも大きい順序で、固有値を有することを思い出し、
【０２５０】
【数９６】
2018530849.tif 000103
【０２５１】
を選択すると、総解確率αを達成するために必要とされるＳＡＴＤＥＣ反復の数は、約
【０２５２】
【数９７】
2018530849.tif 000104
【０２５３】
である。各反復が、クローズ毎に、一定数の演算を必要とするので、アルゴリズムのための実行時間は、全体として、問題におけるクローズの数と線形的にスケールする。
[0120]ｚ＾軸に沿った変数に対応する各ビットの投影を測定し、｜＋ｚ＞が真に対応し、｜−ｚ＞が負に対応し、興味のある３ＳＡＴ問題への潜在的な解を生成することを思い出されたい。これは、古典的なコンピュータを使用して、訂正のために簡単にチェックされることができる。この問題は解くことが可能ではないのであれば、潜在的な解は、常に、無効となるであろう。この問題は解くことが可能であれば、この手順は、確率αを有する有効な解と、確率１−αを有する無効な解とを生成するであろう。確率論的なアルゴリズムの慣習に従って、１−α≦１／３となるように、Ｎｉｔｅｒａｔｉｏｎｓを選択することが必要である。
【０２５４】
ＶＩＩ．既存アルゴリズムへの比較
ａ．Ｓｃｈｏｎｉｎｇアルゴリズムとの比較
[0121]上述したアルゴリズムは、Ｓｃｈｏｎｉｎｇの確率論的な古典的アルゴリズム［１４］の趣旨に類似する。Ｓｃｈｏｎｉｎｇアルゴリズムでは、各変数の値が、最初に、ランダムに選択される。その後、各クローズの充足がテストされ、任意のクローズの欠陥は、クローズ内の変数のうちの１つの状態をランダムにフリップすることによって対処される。３Ｎｖ個のクローズをテストした後、割当を満たしていることが発見されないのであれば、この処理は、新たなランダムな初期状態を使用して再開される。
【０２５５】
[0122]２つのアルゴリズム間の相違は、演算されている系の量子性質から生じる。現在のアルゴリズムにおいて、系は、多くの異なる状態の非コヒーレントな重ね合わせからなる一方、古典的アルゴリズムは、一度に単一の状態を占有するように制約される。Ｓｃｈｏｎｉｎｇのアルゴリズムは、すべてのデシメーション演算後、真の軸に沿った各変数ビットの状態を測定することによってエミュレートされることができ、これによって、系に対して、単一の状態を占有させる。現在のアルゴリズムは、初期状態から、すべての確率を転送させる訳ではないので、測定によってフォローされるデシメーションのステップは、可変ビットのうちの１つが変化するまで反復されねばならない。
【０２５６】
[0123]ここで、測定の動作は、基本的に、アルゴリズムの振舞いを変化させる。失敗した各クローズをブランチポイントとして取り扱い、現在のアルゴリズムは、すべてのブランチに沿った初期状態を占有する確率のフラクションを転送させる一方、Ｓｃｈｏｎｉｎｇアルゴリズムは、ランダムに選択された単一のブランチに沿った確率全体を転送させる。コンピュータ科学の言語では、現在のアルゴリズムは、解状態を求めて並列的な幅優先探索を実行しているが、Ｓｃｈｏｎｉｎｇアルゴリズムは、ランダム化された深さ優先探索、すなわち、ランダムウォークを実行する。
【０２５７】
[0124]現在のアルゴリズムにおける単一のＤＥＣゲートによるポピュレーションのフローは、すべてのランダムウォークと、状態を占有する初期確率と特定のウォークを採用する確率とによって重み付けられたすべての可能な初期状態とを総和することによって、古典的にエミュレートされることができる。しかしながら、この古典的なエミュレーションアルゴリズムは、非常に非効率的である。量子アルゴリズムは、ＤＥＣゲートを実施するために、一定数の演算を必要とする一方、古典的アルゴリズムは、
【０２５８】
【数９８】
2018530849.tif 000105
【０２５９】
個のすべての初期状態にわたる総和を必要とする。したがって、多項式時間量子アルゴリズムの存在は、多項式時間古典エミュレーションアルゴリズムの存在を示唆しない。
ｂ．固定ポイント量子探索との比較
[0125]上述されたアルゴリズムは、ポピュレーションが、離れることなく、解状態へ転送されることができるという特性を有する。解状態は、すべてのクローズを満たすので、固定ポイントの反復である。概念的に、これは、問題を満たすソース状態｜ｓ＞と解状態｜ｓ＊＞とからなる２ｄサブ空間において、ソース状態｜ｓ＞を回転させるために単一のオラクルビットが使用されるＴｕｌｓｉらの固定ポイント量子探索アルゴリズム［５，１５，１０，７，６］に類似する。［１５］に記載されているように、固定ポイント探索は、空間を定義する問題に状態が残っている限り、アルゴリズムが最後まで実行されず、早期の反復における不完全な変換による任意のエラーが、後続する反復によってワイプアウトされた場合であっても、ターゲット状態に向かって進展するように初期状態が保証されているという好ましい特性を有する。しかしながら、既存の固定ポイント探索は、非固定ポイントアルゴリズムに対して、いままで、速度の利点を提案していない。［１５］は、古典的探索に相当する実行時間を生成する一方、［１０］の実行時間は、Ｇｒｏｖｅｒ探索アルゴリズムの
【０２６０】
【数９９】
2018530849.tif 000106
【０２６１】
実行時間特性、ここで、ｎは状態の総数、から、減衰パラメータの変動を伴う古典的探索の
【０２６２】
【数１００】
2018530849.tif 000107
【０２６３】
へ連続的に変動する。
[0126]有効な解が、問題における各クローズを満たさねばならない条件である、順序付けられていないデータベース探索の一般的な場合のために利用可能ではない３ＳＡＴへ特有の情報を活用することによって、本アルゴリズムは、既存の固定ポイントアルゴリズムとは異なる。それは、問題全体の充足をエンコードするために、単一のオラクルビットを使用するのではなく、個々のクローズの充足をエンコードする多数のビットを活用する。ソース状態からターゲット状態へダイレクトにポピュレーションを転送させるのではなく、デシメーション演算子は、特定のクローズを失う状態をデポピュレートするように動作し、クローズに含まれる変数によってのみ異なる他の状態へポピュレーションを転送させる。このように、ポピュレーションの流れは、興味のある問題を満たす状態のための幅優先探索を模擬する。解状態へのポピュレーションの究極的な転送は、間接的にのみ生じ、多くの異なる経路による、多くの中間状態への転送を含み得る。個々のクローズを失うことによるデポピュレーションの速度は、演繹的な最大値を持たない、ユーザ制御されたパラメータである。
【０２６４】
[0127]これら区別の各々は、順序付けられていないデータベースの純粋な探索に対して、３ＳＡＴによって提供された追加問題特有の情報によって生じ、集合的に、収束時間における相違を考慮する。式５２および同伴する議論に図示されるように、個々のクローズの失敗によって喪失されたポピュレーションの最小フラクションは、非解ポピュレーション分布の減衰のための重要な時間スケールを定義する。固有分布が、これよりもより緩慢に減衰する条件は、緩慢に減衰する疑似平衡固有分布をユニークに定義する。「前後反復」では、個々のクローズの失敗によって喪失されたポピュレーションのフラクションを変動させることは、迅速に減衰する固有分布上へ、緩慢に減衰する疑似平衡分布を投影し、これによって、ポピュレーションが、解状態のセットへ転送される速度を増加させる。
【０２６５】
[0128]本発明のいくつかの実施形態および／または態様が、図示および説明されたが、本発明は、それに限定されず、他のさまざまな実施形態および態様を包含することが理解されるべきである。
【０２６６】
ここまで本発明を説明してきたが、新たなものとして特許請求され、特許証によって保護されることが所望されるものは、以下の通りである。
【図１】
2018530849.tif 000108
【図２】
2018530849.tif 000109
【図３】
2018530849.tif 000110
【図４】
2018530849.tif 000111
【図５】
2018530849.tif 000112
【図６】
2018530849.tif 000113
【図７】
2018530849.tif 000114
【図８】
2018530849.tif 000115
【図９】
2018530849.tif 000116
【図１０】
2018530849.tif 000117
【図１１】
2018530849.tif 000118
【図１２】
2018530849.tif 000119
【図１３】
2018530849.tif 000120
【図１４】
2018530849.tif 000121
【図１５】
2018530849.tif 000122
【図１６】
2018530849.tif 000123
【図１７】
2018530849.tif 000124
【図１８】
2018530849.tif 000125
【図１９】
2018530849.tif 000126
【図２０】
2018530849.tif 000127
【図２１】
2018530849.tif 000128
【図２２】
2018530849.tif 000129
【図２３】
2018530849.tif 000130
【図２４】
2018530849.tif 000131
【図２５】
2018530849.tif 000132
【図２６】
2018530849.tif 000133
【図２７】
2018530849.tif 000134
【図２８】
2018530849.tif 000135
【図２９】
2018530849.tif 000136
【図３０】
2018530849.tif 000137
【手続補正書】
【提出日】平成30年5月14日(2018.5.14)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
非可逆的な量子計算を実行するための方法であって、
ユニタリ演算と、挿入演算と、削除演算とを含む群から選ばれた１つまたは複数の演算を実行するステップと、
各々が複数の状態を有する複数のビットを設けるステップと、
論理演算の出力として表現可能な特性か、または、論理演算として表現可能な任意の特性を、第１のビットの状態においてエンコードするステップと、
前記第１のビットの状態を用いて、１つまたは複数の他のビットの状態を制御するステップと、
前記第１のビットの状態を記憶するか、削除するか、または、修正するステップと
のうちの１つまたは複数を含む方法。
【請求項２】
量子系における状態に対する確率分布を変更するための方法であって、前記方法は、論理式を満足する１つの状態または状態のセットに確率を集中させ、前記方法において、デシメーションゲートのアイデンティティ、特定のデシメーションゲートに対応するデシメーション角度、異なるゲートのためのアプリケーションの順序、または、前記特定のデシメーションゲートが適用される回数等のパラメータが、反復間で変動する、方法。
【請求項３】
量子コンピュータであって、
前記コンピュータにインストールされたアルゴリズムであって、前記アルゴリズムは、確率を解状態に集中させるように構成されたアルゴリズムと、
第１密度行列を第２密度行列にマッピングする量子コンピュータ機能と、
明確に定義された逆を有さない前記マッピングの関数と、
系を単独で記述する前記第２密度行列であって、該第２密度行列は、前記系及び環境をともに記述する前記第１行列から、アルゴリズム
【数１】
2018530849.tif 000138
を用いてすべての環境的な自由度にわたりトレースすることによって取得され、ここで、添字「ｅ」は前記環境の状態を示し、添字「ｓ」は前記系の状態を示し、添字「ｓｅ」は、前記環境に結合された前記系の状態を示す、前記第２密度行行列と
を含む量子コンピュータ。
【国際調査報告】
2018530849.tif 000139
2018530849.tif 000140
2018530849.tif 000141