(57)【要約】【［要約】］  制約問題は、少なくとも１つのゲート、および、少なくとも１つの制約を付けられた入力、または、少なくとも１つの制約を付けられた出力を、または、少なくとも１つの制約を付けられた入力と少なくとも１つの制約を付けられた出力との組み合わせを、備えるデジタル回路として表され得る。行列は、少なくとも１つのゲートの各々について生成され得る。制約行列が、少なくとも１つの制約を付けられた入力、少なくとも１つの制約を付けられた出力、または、少なくとも１つの制約を付けられた入力と少なくとも１つの制約を付けられた出力との組み合わせについて生成される。少なくとも１つのゲートの各々についての各行列と制約行列との組み合わせを備える最終的な行列が生成され得る。最終的な行列は、量子コンピュータによって利用可能なエネルギー表現に翻訳され得る。エネルギー表現のエネルギーはｑ−ビット出力を生成するために最小化され得、制約問題の結果はｑ−ビット出力に基づいて決定され得る。
2017515195.tif 000002
【特許請求の範囲】
【請求項１】
量子プロセッサへの入力のために制約問題を形式化し、前記制約問題を解決する方法であって、
従来のプロセッサ、量子プロセッサ、または、それらの組み合わせを用いて、前記制約問題を、少なくとも１つのゲート、および、少なくとも１つの制約された入力、少なくとも１つの制約された出力、または、少なくとも１つの制約された入力と少なくとも１つの制約された出力との組み合わせを備えたデジタル回路として表現することと、
前記従来のプロセッサ、前記量子プロセッサ、または、前記それらの組み合わせを用いて、前記少なくとも１つのゲートの各々について行列を出力することと、
前記従来のプロセッサ、前記量子プロセッサ、または、前記それらの組み合わせを用いて、前記少なくとも１つの制約された入力、前記少なくとも１つの制約された出力、または、少なくとも１つの制約された入力と少なくとも１つの制約された出力との前記組み合わせについて制約行列を出力することと、
前記従来のプロセッサ、前記量子プロセッサ、または、前記それらの組み合わせを用いて、前記少なくとも１つのゲートの各々についての各行列と前記制約行列との組み合わせを備える最終的な行列を出力することと、
前記従来のプロセッサ、前記量子プロセッサ、または、前記それらの組み合わせを用いて、前記最終的な行列を、前記量子プロセッサによって使用可能なエネルギー表現に翻訳することと、
量子ビット（ｑ−ビット）出力を生成するために、前記量子プロセッサを用いて、前記エネルギー表現のエネルギーを最小化することと、
前記従来のプロセッサ、前記量子プロセッサ、または、前記それらの組み合わせを用いて、前記ｑ−ビット出力に基づいて前記制約問題の結果を決定することと、
を備えた方法。
【請求項２】
前記翻訳することは、前記最終的な行列をハミルトニアンエネルギー行列として解釈することを備える、請求項１に記載の方法。
【請求項３】
前記ハミルトニアンエネルギー行列は、スピングラスハミルトニアンエネルギー行列を備える、請求項２に記載の方法。
【請求項４】
前記ハミルトニアンエネルギー行列は、前記ハミルトニアンエネルギー行列における行と列のエントリとして、前記少なくとも１つの制約された入力の各々、前記少なくとも１つの制約された出力の各々、または、少なくとも１つの制約された入力と少なくとも１つの制約された出力の組み合わせの各々を表す、請求項２に記載の方法。
【請求項５】
前記従来のプロセッサ、前記量子プロセッサ、または、前記それらの組み合わせを用いて、前記ハミルトニアンエネルギー行列を、前記ハミルトニアンエネルギー行列のエネルギーを最小化するために用いられる前記量子プロセッサのために好適な形式に変換することを更に備える、請求項２に記載の方法。
【請求項６】
前記表現することは、更に、前記デジタル回路の中の複数の中間出力の各々にラベルを割り当てることを備える、請求項１に記載の方法。
【請求項７】
前記表現することは、更に、前記少なくとも１つのゲートの各々にラベルを割り当てることを備える、請求項１に記載の方法。
【請求項８】
前記デジタル回路は、ユニバーサルゲートの組から選択された少なくとも１つの２入力論理ゲートを備える、請求項１に記載の方法。
【請求項９】
ユニバーサルゲートの前記組は、ＡＮＤ（論理積）とＯＲ（論理和）の、入力の一方または両方での選択的なＮＯＴ（否定）機能性との全ての２入力組み合わせによって形成された８つの２入力ゲートを備える、請求項８に記載の方法。
【請求項１０】
前記デジタル回路は、入力上の制約が満足されるとき値は真になる少なくとも１つのサブ回路を備え、前記サブ回路の出力は真となるよう制約される、請求項１に記載の方法。
【請求項１１】
前記従来のプロセッサ、前記量子プロセッサ、または、前記それらの組み合わせを用いて、前記デジタル回路を、前記少なくとも１つのゲート、および、前記少なくとも１つの制約された入力、前記少なくとも１つの制約された出力、または、少なくとも１つの制約された入力と少なくとも１つの制約された出力との前記組み合わせについてのデータを備えるテーブルに変換することを更に備える、請求項１に記載の方法。
【請求項１２】
前記少なくとも１つのゲートの各々について前記行列を出力することは、
前記ゲートについて置換行列を計算することと、
前記ゲートのゲートタイプに基づいてゲート行列を選ぶことと、
前記ゲートについての前記行列を形成するために、前記置換行列の転置、前記ゲート行列、および、前記置換行列を乗じることと、
を備える、請求項１に記載の方法。
【請求項１３】
前記最終的な行列を出力することは、
回路行列を作成するために、前記少なくとも１つのゲートの各々についての各々の行列を合算することと、
前記制約行列を前記回路行列に加えることと、
を備える、請求項１に記載の方法。
【請求項１４】
前記量子プロセッサは断熱量子計算を用いる、請求項１に記載の方法。
【請求項１５】
前記デジタル回路は、暗号学的関数、暗号化アルゴリズム、または、巡回セールスマン問題を表現する、請求項１に記載の方法。
【請求項１６】
前記暗号学的関数は一方向性関数である、請求項１５に記載の方法。
【請求項１７】
量子コンピュータへの入力のために制約問題を形式化し、前記制約問題を解決するためのシステムであって、
前記システムは、従来のコンピュータと前記量子コンピュータとを備え、
前記従来のコンピュータは、
前記制約問題を、少なくとも１つのゲート、および、少なくとも１つの制約された入力、少なくとも１つの制約された出力、または、少なくとも１つの制約された入力と少なくとも１つの制約された出力との組み合わせを備えたデジタル回路として表現することと、
前記少なくとも１つのゲートの各々について行列を出力することと、
前記少なくとも１つの制約された入力、前記少なくとも１つの制約された出力、または、少なくとも１つの制約された入力と少なくとも１つの制約された出力との前記組み合わせについて制約行列を出力することと、
前記少なくとも１つのゲートの各々についての各行列と前記制約行列との組み合わせを備える最終的な行列を出力することと、
前記最終的な行列を、前記量子コンピュータによって使用可能なエネルギー表現に翻訳することと、
を行うように構成され、
前記量子コンピュータは、
量子ビット（ｑ−ビット）出力を生成するために、前記エネルギー表現のエネルギーを最小化すること、
を行うように構成され、
前記従来のプロセッサは、更に、前記ｑ−ビット出力に基づいて前記制約問題の結果を決定することを行うよう構成される、
システム。
【請求項１８】
前記翻訳することは、前記最終的な行列をハミルトニアンエネルギー行列として解釈することを備える、請求項１７に記載のシステム。
【請求項１９】
前記ハミルトニアンエネルギー行列は、スピングラスハミルトニアンエネルギー行列を備える、請求項１８に記載のシステム。
【請求項２０】
前記ハミルトニアンエネルギー行列は、前記ハミルトニアンエネルギー行列における行と列のエントリとして、前記少なくとも１つの制約された入力の各々、前記少なくとも１つの制約された出力の各々、または、少なくとも１つの制約された入力と少なくとも１つの制約された出力の組み合わせの各々を表す、請求項１８に記載のシステム。
【請求項２１】
前記従来のプロセッサは、前記ハミルトニアンエネルギー行列を、前記ハミルトニアンエネルギー行列のエネルギーを最小化するために用いられる前記量子コンピュータのために好適な形式に変換することを行うよう更に構成される、請求項１８に記載のシステム。
【請求項２２】
前記表現することは、更に、前記デジタル回路の中の複数の中間出力の各々にラベルを割り当てることを備える、請求項１７に記載のシステム。
【請求項２３】
前記表現することは、更に、前記少なくとも１つのゲートの各々にラベルを割り当てることを備える、請求項１７に記載のシステム。
【請求項２４】
前記デジタル回路は、ユニバーサルゲートの組から選択された少なくとも１つの２入力論理ゲートを備える、請求項１７に記載のシステム。
【請求項２５】
ユニバーサルゲートの前記組は、ＡＮＤ（論理積）とＯＲ（論理和）の、入力の一方または両方での選択的なＮＯＴ（否定）機能性との全ての２入力組み合わせによって形成された８つの２入力ゲートを備える、請求項２４に記載のシステム。
【請求項２６】
前記デジタル回路は、入力上の制約が満足されるとき値は真になる少なくとも１つのサブ回路を備え、前記サブ回路の出力は真となるよう制約される、請求項１７に記載のシステム。
【請求項２７】
前記従来のプロセッサは、前記デジタル回路を、前記少なくとも１つのゲート、および、前記少なくとも１つの制約された入力、前記少なくとも１つの制約された出力、または、少なくとも１つの制約された入力と少なくとも１つの制約された出力との前記組み合わせについてのデータを備えるテーブルに変換することを更に備える、請求項１７に記載のシステム。
【請求項２８】
前記少なくとも１つのゲートの各々について前記行列を出力することは、
前記ゲートについて置換行列を計算することと、
前記ゲートのゲートタイプに基づいてゲート行列を選ぶことと、
前記ゲートについての前記行列を形成するために、前記置換行列の転置、前記ゲート行列、および、前記置換行列を乗じることと、
を備える、請求項１７に記載のシステム。
【請求項２９】
前記最終的な行列を出力することは、
回路行列を作成するために、前記少なくとも１つのゲートの各々についての各々の行列を合算することと、
前記制約行列を前記回路行列に加えることと、
を備える、請求項１７に記載のシステム。
【請求項３０】
前記量子コンピュータは断熱量子計算を用いる、請求項１７に記載のシステム。
【請求項３１】
前記デジタル回路は、暗号学的関数、暗号化アルゴリズム、または、巡回セールスマン問題を表現する、請求項１７に記載のシステム。
【請求項３２】
前記暗号学的関数は一方向性関数である、請求項３１に記載のシステム。
【請求項３３】
量子コンピュータであって、
制約問題を、少なくとも１つのゲート、および、少なくとも１つの制約された入力、少なくとも１つの制約された出力、または、少なくとも１つの制約された入力と少なくとも１つの制約された出力との組み合わせを備えたデジタル回路として表現することと、
前記少なくとも１つのゲートの各々について行列を出力することと、
前記少なくとも１つの制約された入力、前記少なくとも１つの制約された出力、または、少なくとも１つの制約された入力と少なくとも１つの制約された出力との前記組み合わせについて制約行列を出力することと、
前記少なくとも１つのゲートの各々についての各行列と前記制約行列との組み合わせを備える最終的な行列を出力することと、
前記最終的な行列を、前記量子コンピュータによって使用可能なエネルギー表現に翻訳することと、
量子ビット（ｑ−ビット）出力を生成するために、前記エネルギー表現のエネルギーを最小化することと、
前記ｑ−ビット出力に基づいて前記制約問題の結果を決定することと、
を行うよう構成される量子コンピュータ。
【請求項３４】
前記翻訳することは、前記最終的な行列をハミルトニアンエネルギー行列として解釈することを備える、請求項３３に記載の量子コンピュータ。
【請求項３５】
前記ハミルトニアンエネルギー行列は、スピングラスハミルトニアンエネルギー行列を備える、請求項３４に記載の量子コンピュータ。
【請求項３６】
前記ハミルトニアンエネルギー行列は、前記ハミルトニアンエネルギー行列における行と列のエントリとして、前記少なくとも１つの制約された入力の各々、前記少なくとも１つの制約された出力の各々、または、少なくとも１つの制約された入力と少なくとも１つの制約された出力の組み合わせの各々を表す、請求項３４に記載の量子コンピュータ。
【請求項３７】
前記量子コンピュータは、前記ハミルトニアンエネルギー行列を、前記ハミルトニアンエネルギー行列のエネルギーを最小化するために用いられる前記量子コンピュータのために好適な形式に変換することを行うよう更に構成される、請求項３４に記載の量子コンピュータ。
【請求項３８】
前記表現することは、更に、前記デジタル回路の中の複数の中間出力の各々にラベルを割り当てることを備える、請求項３３に記載の量子コンピュータ。
【請求項３９】
前記表現することは、更に、前記少なくとも１つのゲートの各々にラベルを割り当てることを備える、請求項３３に記載の量子コンピュータ。
【請求項４０】
前記デジタル回路は、ユニバーサルゲートの組から選択された少なくとも１つの２入力論理ゲートを備える、請求項３３に記載の量子コンピュータ。
【請求項４１】
ユニバーサルゲートの前記組は、ＡＮＤ（論理積）とＯＲ（論理和）の、入力の一方または両方での選択的なＮＯＴ（否定）機能性との全ての２入力組み合わせによって形成された８つの２入力ゲートを備える、請求項４０に記載の量子コンピュータ。
【請求項４２】
前記デジタル回路は、入力上の制約が満足されるとき値は真になる少なくとも１つのサブ回路を備え、前記サブ回路の出力は真となるよう制約される、請求項３３に記載の量子コンピュータ。
【請求項４３】
前記量子コンピュータは、前記デジタル回路を、前記少なくとも１つのゲート、および、前記少なくとも１つの制約された入力、前記少なくとも１つの制約された出力、または、少なくとも１つの制約された入力と少なくとも１つの制約された出力との前記組み合わせについてのデータを備えるテーブルに変換することを更に備える、請求項３３に記載の量子コンピュータ。
【請求項４４】
前記少なくとも１つのゲートの各々について前記行列を出力することは、
前記ゲートについて置換行列を計算することと、
前記ゲートのゲートタイプに基づいてゲート行列を選ぶことと、
前記ゲートについての前記行列を形成するために、前記置換行列の転置、前記ゲート行列、および、前記置換行列を乗じることと、
を備える、請求項３３に記載の量子コンピュータ。
【請求項４５】
前記最終的な行列を出力することは、
回路行列を作成するために、前記少なくとも１つのゲートの各々についての各々の行列を合算することと、
前記制約行列を前記回路行列に加えることと、
を備える、請求項３３に記載の量子コンピュータ。
【請求項４６】
前記量子コンピュータは断熱量子計算を用いる、請求項３３に記載の量子コンピュータ。
【請求項４７】
前記デジタル回路は、暗号学的関数、暗号化アルゴリズム、または、巡回セールスマン問題を表現する、請求項３３に記載の量子コンピュータ。
【請求項４８】
前記暗号学的関数は一方向性関数である、請求項４７に記載の量子コンピュータ。
【発明の詳細な説明】
【関連出願】
【０００１】
［0001］ 本開示は、２０１４年３月１２日に出願された、「Ｍｅｔｈｏｄ ｆｏｒ Ｓｏｌｖｉｎｇ Ｄｉｇｉｔａｌ Ｌｏｇｉｃ Ｃｏｎｓｔｒａｉｎｔ Ｐｒｏｂｌｅｍｓ Ｖｉａ Ａｄｉａｂａｔｉｃ Ｑｕａｎｔｕｍ Ｃｏｍｐｕｔａｔｉｏｎ」と題された米国仮出願第６１／９５２，０４９番号からの優先権を主張し、その全体が参照によってこの中に組み込まれる。
【図面の簡単な説明】
【０００２】
【図１】［0002］  図１は、本発明の実施形態に係る従来のコンピュータと量子コンピュータを備えるシステムを示す。
【図２】[0003] 図２は、本発明の実施形態に係るゲートタイプのテーブルを示す。
【図３ａ】[0004] 図３ａは、本発明の実施形態に係るプロセスフロー図を示す。
【図３ｂ】［0005］ 図３ｂは、本発明の実施形態に係るプロセスフロー図を示す。
【図４】［0006］ 図４は、本発明の実施形態に係る正規の形式の加算回路を示す。
【図５】［0007］ 図５は、本発明の実施形態に係る番号付けされた中間出力をもった加算回路を示す。
【図６】［0008］ 図６は、本発明の実施形態に係る番号付けされたゲートをもった加算回路を示す。
【図７】［0009］ 図７は、本発明の実施形態に係るテーブルとして加算回路を示す。
【図８】［0010］ 図８は、本発明の実施形態に係るＧ１１のための例示の置換行列を示す。
【図９】［0011］ 図９は、本発明の実施形態に係るＧ１１のための例示のゲート行列を示す。
【図１０】［0012］ 図１０は、本発明の実施形態に係るＧ１１のための最終的な行列計算を示す。
【図１１】［0013］ 図１１は、本発明の実施形態に係る回路全体のための行列を示す。
【図１２】［0014］ 図１２は、本発明の実施形態に係る制約行列を示す。
【図１３】［0015］ 図１３は、本発明の実施形態に係る追加された制約を有する回路行列を示す。
【詳細な説明】
【０００３】
［0016］ 多くの実用的な最適化問題は、従来のコンピュータとアルゴリズムで解決するには計算的にコストが高い。これらの最適化問題は、ある値が最小化または最大化されるように、または、制約の組が満たされるように、変数の組のための値を見つけることを必要とする。これらの問題は、当技術において、ＮＰ困難問題と呼ばれる。例えば、スケジューリング問題、リソース利用問題、および、ルーティングの問題は、全て、そのようなすべてのＮＰ困難問題の例であり得る。これらの制約の形と含まれる変数の性質は異なり得るが、それらは全て、ビットに作用するブール関数（または、回路）として表され得る。問題が従来のコンピュータによる解釈に適した論理回路として表されている場合であっても、欠けている情報を見つけることは計算的にコストが高く、および／または、質的に不可能であり得る（例えば、出力のみが知られており、入力が求められる一方向性関数）。
【０００４】
［0017］ この中に記載されたシステムおよび方法は、量子コンピューティングを介して２値変数との任意のブール関数を含む制約または最適化問題を解くために使用され得る。量子コンピュータが解を見つけることができるように、問題と任意の制約は、量子コンピュータへの入力として使用可能な形式に変換され得る。形式はエネルギー表現であり得、量子コンピュータは、解を見つけるために、エネルギー表現におけるエネルギーを最小化し得る。例えば、入力は、ハミルトニアン行列の最低エネルギー状態が問題の解を表すように、断熱量子コンピュータによる評価に適したハミルトニアン行列であり得る。問題は、制約のセットとともにデジタル論理回路として表すことができる。制約は、定義された値（例えば、問題のための既知の、または、所望の入力または出力）であり得、いくつかの実施形態では、制約は単一ビット制約であってよい。１つまたはそれより多くの入力、１つまたはそれより多くの出力、１つまたはそれより多くの入力と１つまたはそれより多くの出力との組合せが制約され得る。回路が正規形式に変換されることができ、ｑ−ビット（quantum bits：量子ビット）が各回路パスに割り当てられ得、回路を表す行列が生成され得、制約が行列を低減するために適用され得、最も低いエネルギー状態が量子コンピュータを介して見出され得、結果の状態が元の問題に照らして解釈され得る。従って、この中に記載されたシステムおよび方法を適用することにより、論理回路として表すことができる任意の問題が、量子コンピュータを用いて評価され得る。
【０００５】
［0018］ いくつかの実施形態は、問題定義（例えば、論理回路と制約）を受け入れ、必要とされる翻訳を実行し、結果を解釈することができる、従来のコンピュータおよび関連ソフトウェアを含み得る。そのような実施形態は、また、エネルギー最小化を実行することができる量子コンピュータ（例えば、断熱量子コンピュータまたは他の量子コンピュータ）を含み得る。
【０００６】
［0019］ 図１は、本発明の実施形態に係る従来のコンピュータ２０と量子コンピュータ３０を備えるシステム１０を示す。従来のコンピュータ２０は、ビットを用いて算術および／または論理演算を実行することができる任意のプログラム可能なデジタルマシンまたは複数のマシンであってよい。いくつかの実施形態では、従来のコンピュータ２０は、１つまたはそれより多くのプロセッサ２２、メモリ２４、データ記憶装置２６、および／または、他の一般的に知られているか、または、新規の構成要素を含み得る。これらの構成要素は、物理的に、または、ネットワークまたは無線リンクを介して、接続され得る。従来のコンピュータ２０は、また、上記の構成要素の動作を指示することができるソフトウェアを含み得る。
【０００７】
［0020］ 従来のコンピュータ２０は、いくつかの実施形態では、ネットワークまたは複数のネットワークを介して互いに連結された複数の従来のコンピュータを備えてもよい。ネットワークは、完全にまたは部分的に相互接続された複数の従来のコンピュータおよび／または量子コンピュータであってよく、ここにおいて、従来のコンピュータおよび／または量子コンピュータのいくつかまたは全てが互いに通信することが可能である。従来のコンピュータおよび／または量子コンピュータ間の接続は、ある場合には有線接続（例えば、イーサネット（登録商標）、同軸ケーブル、光、または、他の有線の接続を介して）されてもよく、または、無線接続（例えば、Ｗｉ−Ｆｉ、ＷｉＭａｘ、または、他の無線接続）であってもよいことが、通常の技量を有する者により理解される。従来のコンピュータおよび／または量子コンピュータの間の接続は、ＴＣＰ等のコネクション型プロトコル、または、ＵＤＰ等のコネクションレス型プロトコルを含む、任意のプロトコルを使用することができる。少なくとも２つの従来のコンピュータおよび／または量子コンピュータがデータを交換するのに経由する任意の接続は、ネットワークベースであることができる。
【０００８】
［0021］ 量子コンピュータ３０は、ｑ−ビットを使用して算術および／または論理演算を行うことができる、任意のプログラム可能な量子マシンおよび／または複数のマシンであり得る。いくつかの実施形態において、量子コンピュータ３０は、１つまたがそれより多くの量子プロセッサ３２、量子メモリ３４、および／または、他の一般的に知られているか、または、新規の構成要素を備え得る。これらの構成要素は、物理的に、または、ネットワークまたは無線リンクを介して、接続され得る。量子コンピュータ３０は、また、上記の構成要素の動作を指示することができるソフトウェアを備え得る。量子コンピュータ３０は、いくつかの実施形態では、ネットワークまたは複数のネットワークを介して互いに連結された複数の量子コンピュータを備えてもよい。量子コンピュータ３０は従来のコンピュータ２０に連結され得、従って、量子コンピュータ３０と従来のコンピュータ２０はデータを交換し得る。他のタイプの量子コンピュータがいくつかの実施形態（例えば、２次無制約２値計画（Quadratic Unconstrained Binary Optimization：ＱＵＢＯ））モデルにおいて用いられ得るが、この中で検討される例で使用される量子コンピュータ３０は、を用いる量子コンピュータ）の他のタイプは、イジングモデル（Ising model）を用いた断熱量子コンピュータである。
【０００９】
［0022］ 論理回路と１組の制約付き入力および／または出力として表現された問題を量子コンピュータによって分析することができる形式に変換することによって、いくつかまたは全ての入力が未知であるＮＰ困難（NP-hard）問題（例えば、出力のみが利用可能である一方向性関数）が解かれ得る。例えば、以下の図２−１３に関連して検討される例に加え、この中に記載されるシステムおよび方法は、様々な異なるシステムに関連付けられた問題を解くために適用され得る。このような問題は、ハッシュ関数が回路として定義され、ハッシュ関数の出力が制限されるＳＨＡ−１（セキュアハッシュアルゴリズム）等の暗号学的ハッシュ関数のためのプレイメージを見つけること、アルゴリズムが回路として定義され、制約が暗号文と鍵のビットのサブセットを含むＡＥＳ（advanced encryption standard）等の暗号アルゴリズムの平文を計算すること、および、製造や配送を含む様々な問題に適用されることができる巡回セールスマン問題（traveling salesman problem）等の計算コストの高い他の問題を含み得る。
【００１０】
［0023］ 解決されるべき問題は、まず、回路の入力、出力、または、入力と出力の両方のある組み合わせのいずれかに適用される単一ビット制約の組と共に、デジタル回路としての表現に変換されることである。制約は、入力、出力、または、それら２つの組み合せに適用され得るから、この中に記載されるシステムおよび方法は、通常のゲート論理を量子コンピューティングでの使用に適した形式に変換するため、並びに、探索、逆（inversion）、または、他の一般的制約充足問題（general constraint satisfaction problems）を実行するために使用されてもよい。例えば、量子コンピューティング環境内で通常のデジタル論理をエミュレートするために、入力が特定され（制約され）、出力が見つけられ得る。代替的に、出力の組を充足する入力の組を探索するために、出力が特定され（制約され）、入力が見つけられ得る。多くの利用ケースは、いくつかの入力といくつかの出力の両方が特定され（制約され）得る。下の例は、検討の中でのデジタル回路として２ビット全加算器を使用し、第１の入力を２であると特定し、出力を５であると特定し、第２の入力が３であるべきであることを発見したいと望むとする。これは、開示された問題解決プロセスを示す簡略化された例であり、当業者は、任意の論理、入力、および／または、出力が使用され得ることを理解するであろう。プロセスの具体的な実用的用途は、単純な例が提示された後で検討される。
【００１１】
［0024］ 図２は、本発明の実施形態に係るゲートタイプのテーブル１００を示す。ゲートのいくつかの組は、全ての可能な回路がその組からのゲートの組み合わせで作られ得ることを意味し、機能的に完全であり得る。例えば、ゲートの機能的に完全な１つの組は、「ａｎｄ（論理積）」と「ｎｏｔ（否定）」ゲートを備え得る。本明細書に記載された例示の回路の目的のために、機能的に完全である、ゲートの特定の組が定義され、それは「正準ゲート（canonical gates）」と呼ばれる。正準ゲートの例示の組についての名前１０１−１０８、シンボル１１１−１１８、および、真理値テーブル１２１−１２８が、以下でより詳細に記載される各ゲートについてのエネルギー表現（例えば、エネルギー行列１３１−１３８）と共に、図２に示される。いくつかの実施形態では、ゲートの他の組が使用されてもよい。
【００１２】
[0025] 図３ａは、本発明の実施形態に係る制約システムを解くハイレベルのプロセス２００を示す。図３ｂは、本発明の実施形態に係るプロセス２００の具体的な実装３００を示す。以下に記載されるこれらのプロセス２００／３００に関連した例では、いくつかの動作は、従来のコンピュータ２０によって実行されるものとして記載され、他の動作は、量子コンピュータ３０によって実行されるものとして記載される。この技術に通常の技量を有する者は、リストされた動作が、いくつかの実施形態において、従来のコンピュータ２０または量子コンピュータ３０のいずれかによって行われてもよいことを理解する。量子コンピュータ３０のみが全体のプロセス２００を実行するために使用される実施形態が可能である。従来のコンピュータ２０のみが全体のプロセス２００を実行するために使用される実施形態が可能である。
【００１３】
［0026］ デジタル回路は、従来のコンピュータ２０によって、正準ゲート２０５のみを備える形式に変換され、いくつかの実施形態では、結果の回路が従来のコンピュータ２０により最適化され得る。例えば、デジタル回路を含むＶｅｒｉｌｏｇ（ヴェリログ）ファイルは、図３ｂに示されるように、Ｙｏｓｙｓ等の編集ツールに入力され得る（３０５）。最適化は、線形ゲートの組み合わせを、単一または一組の非線形ゲートの中に組み合わせることによって起こる。また、最適化は、制約が入力の１つとして与えられるゲートを除くことによって起こってもよい。電気工学およびコンピュータ科学の技術分野で周知の他の最適化も適用され得る。例えば、Ｖｅｒｉｌｏｇソースファイルは、Ｙｏｓｙｓ内部表現３１０に変換され得る。そして、Ｙｏｓｙｓエディタが、最適化を適用する（例えば、非動作の回路分岐または他の未使用の要素を除くこと、ブール演算ツリーを統合すること、同じセルを合併すること、一定入力をもった要素を除くおよび／または単純化すること、等によって）（３１５）。機能的に完全なゲートの様々な組の間で回路を変換することは、例えば、電気工学の技術分野で周知のプロセスの任意のものを用いて行うことができる。
【００１４】
［0027］ 図４は、本発明の実施形態に係る、その正準ゲート４００への変換後の２ビット加算器を示す。この例では、Ｖ１とＶ２は、それぞれ、第１の数のｌｏｗおよびｈｉｇｈビットであり、Ｖ３とＶ４は、それぞれ、第２の数のｌｏｗおよびｈｉｇｈビットであり、Ｖ５、Ｖ６、および、Ｖ７は、ｌｏｗビットからｈｉｇｈビットまでの２つの数字の合計のビットである。また、各入力と出力は、固有の番号（Ｖ１−Ｖ７）を与えられている。図３ｂに示されるように、従来のコンピュータ２０は、入力を通じてループし（３２０）、１で始めて（即ち、この例ではＶ１）、各入力をラベル付けする（３２５）。
【００１５】
［0028］ 図３ａに戻って、最初の番号で始まり最も高い入力または出力番号に続くように、固有の番号が、従来のコンピュータ２０によって、最終出力ではないゲートロジックの各中間出力に割り当てられ得る（２１０）。これらの中間のラベルの特定の順序は任意でよいが、プロセスの残りの部分を通じて一貫して存続する。図３ｂに示されるように、従来のコンピュータ２０は出力を通じてループし（３３０）、先のラベル付け動作の後、カウンタにある次の番号で始めて、各出力をラベル付けし得る（３３５）。図５は、本発明の実施形態に係る、中間出力番号が割り当てられた後の２ビット加算器５００を示す。
【００１６】
［0029］ 図３ａに戻ると、固有の番号は、番号１で始まって、従来のコンピュータ２０により各ゲート２１５に割り当てられ得る。図３ｂに示されるように、従来のコンピュータ２０は、ゲートを通じてループし（３４０）、１で始めて、各ゲートにラベル付けする（３４５）。従来のコンピュータ２０は、また、先のラベル付け動作の後にカウンタにある次の番号で始めて、各ゲート出力にラベル付けし得る（３５０）。ここでも、特定の順序は任意でよいが、プロセスの残りの部分で一貫して存続する。図６は、本発明の実施形態に係る、ゲート番号が割り当てられた後のフィードフォワード加算器を示す。
【００１７】
[0030] 図３ａに戻ると、回路の表現が、従来のコンピュータ２０によって、テーブル形式に変換され得る（２２０）。この変換を達成するために、各ゲートは、順番に考慮され得、以下の要素が決定され得る：
・  ゲートの番号 
・  ゲートのタイプ 
・  ゲートの第１の入力の番号 
・  ゲートの第２入力の番号 
・  ゲートの出力の番号
【００１８】
［0031] 入力および出力に関連付けられた番号を見つける場合、Ｖ＃とＴ＃が同様に処理され得る（即ち、一次入力と出力、並びに、中間出力が、全て、接合番号付けスキームの一部であり得る）。得られたデータポイントは、テーブル内に配置され得る。図７は、本発明の実施形態に係るテーブル形式７００におけるフィードフォワード加算器を示す。例えば、図７において、ゲートＧ１１の番号は１１で、そのタイプはＡＰＰで、その第１の入力は１０で、その第２の入力は１５で、その出力は１７である。
【００１９】
［0032］ 図３ａに戻り、行列が、従来のコンピュータ２０により各ゲートについて生成される。各ゲート行列は、入力、出力、および、中間出力の合計より１大きい次元（例えば、１８）をもった、正方であり得る。この文献の残りにおいて行列の記述を簡略化するために、入力、出力、および、中間出力の合計はＮとしてラベル付けされる。ゲートについて行列を計算するために、置換行列が計算され得、ゲート行列検索が行われ得、最終的な行列が形成され得る。
【００２０】
［0033］ 図８は、本発明の実施形態に係るＧ１１のための置換行列８００である。行列を計算するために、４×（Ｎ＋１）行列が、全てゼロに初期化され得、次の要素が１に設定され得る：
・  （１，１）
・  （２， Ｉｎ １ ＋ １）、ここで、Ｉｎ １（入力１）は、問題になっているゲートについて２２０で生成されたテーブルにおいて検出された番号である
・  （３， Ｉｎ ２ ＋ １）、ここで、Ｉｎ ２（入力２）は、問題になっているゲートについて２２０で生成されたテーブルで検出された番号である
・  （４， Ｏｕｔ ＋ １）、ここで、Ｏｕｔ（出力）は、問題になっているゲートについて２２０で生成されたテーブルで見つけられた数である。
【００２１】
[0034] ４×（Ｎ＋１）行列は、２入力と正準ゲートの組における任意のデジタルゲートへの１出力、プラス、「常時１」のビットが、常にある故に用いられ得る。
【００２２】
［0035］ 図７のテーブル７００によれば、ゲートＧ１１について、以下の行列要素が１に設定され得る：
・  （１，１）
・  （２，１０＋１）＝（２，１１）
・  （３，１５＋１）＝（３，１６）
・  （４，１８＋１）＝（４，１９）
【００２３】
［0036］ 結果、Ｇ１１のための置換行列８００が、図８に示される。
【００２４】
［0037］ 図９は、本発明の実施形態に係るＧ１１のためのゲート行列９００である。ゲート行列検索を行うために、問題になっているゲートについての好適なゲート行列が選ばれ得る。この行列は、例えば、図２のゲートタイプ１００のテーブルに従ったゲートのタイプに基づいて選ばれ得る。具体的には、ゲートの各タイプについて、好適なゲート行列１３１−１３８が、図２における真理値テーブル１２１−１２８の右に示される。従って、タイプＡＰＰであるゲートＧ１１について、図９に示されるように、第１のゲート行列１３１が選択され得る。
【００２５】
［0038］ 図１０は、本発明の実施形態に係るＧ１１についての最終的な行列計算１０００である。最終的な行列を形成するために、置換行列の転置、ゲート行列、および、再度、置換行列が、順番に乗算され得る。即ち、Ｍ＝ＰΛＴ Ｇ Ｐ。これは、図１０において、ゲートＧ１１について示される。
【００２６】
［0039］ 図３ａに戻って、行列は、各ゲートについて生成され得（２２５）、従って、ゲートあたり１つの行列を生成する。各ゲートが行列を有する場合、行列は、従来のコンピュータ２０によって合算され得る（２３０）。例示の回路について、結果の行列１１００が図１１に示される。
【００２７】
［0040］ 図３ａに戻って、行列は、入力と出力上の制約を特定するために、従来のコンピュータ２０によって変更され得る（２３５）。全て０に初期化された（Ｎ＋１）×（Ｎ＋１）の大きさの制約行列Ｃが構築され得る。１の値に制約されるべき各入力または出力について、（１， ｘ＋１）と（ｘ＋１， １）が−１に設定され得、ここで、ｘ は、入力または出力のインデックスである。０の値に制約されるべき各入力または出力について、（１， ｘ＋１）と（ｘ＋１， １）が＋１に設定され得、ここで、ｘ は、入力または出力のインデックスである。従って、例示の加算回路の第１の入力が２であり、出力が５であることを必要とするために、制約の以下の組が適用される： 
・  Ｖ１＝０ 
・  Ｖ２＝１
・  Ｖ５＝１ 
・  Ｖ６＝０ 
・  Ｖ７＝１
【００２８】
［0041］ これらの例示の制約は、図１２に示された行列１２００によって表される。
【００２９】
［0042］ 制約の仕様を完了する（２３５）ために、制約行列は、従来のコンピュータ２０により回路行列に加えられ得、例えば、図１３に示される最終的な行列１３００に帰結する。
【００３０】
[0043] 最終的な行列の生成は、また、図３ｂに示されたように進み得る。制約は、ファイルから、制約行列Ｃに読み込まれる（３５５）。この時点で最終的な行列Ｆがまだ計算されないが、最終的な行列Ｆが作成され得る（３６０）。従来のコンピュータ２０は、ゲートを通じてループし得（３６５）、各置換行列Ｐを生成し（３７０）、ゲート行列Ｇを生成する（３７５）。置換行列の転置、ゲート行列、および、再び置換行列が、順番に乗算され得る（３８０）。このプロセスが全てのゲートについて完了すると、制約行列は、回路行列に加算され得る（３８５）。
【００３１】
［0044］ 図３ａに戻って、最終的な行列は、ハミルトニアン行列として解釈される（２４０）、または、他のエネルギーの表現として解釈されることができる。最終的な行列は、ハミルトニアン行列として解釈されて、低エネルギー状態を計算することができるシステムに入力として提供され得る。このモデルでは、Ｎ＋１のｑ−ビットと仮定する。各Qビットの場合は、ｑ−ビットについて、そのｑ−ｂｉｔの状態は、スピンアップ（spin up）（＋１）またはスピンダウン（spin down）（−１）のいずれかであり得る。各ｑ−ビットの状態をＳｉと呼び、ちょうど計算された最終的な行列をＭとすると、システムの総エネルギーは、以下のように定義され得る：
【００３２】
［0045］
【数１】
2017515195.tif 000003
【００３３】
［0046］ ハミルトニアン行列が、従来のコンピュータ20によって、使用される特定の量子コンピュータのために好適な形式に変換され得る。断熱量子コンピュータがスピングラスモデル（spin glass model)を使用している場合、変換は不要である。この例では、ハミルトニアン行列は、量子コンピュータ３０に入るための適切な形態（即ち、問題の適切なエネルギーの表現）であるが、この技術に通常の知識を有する者は、他のエネルギーの表現がいくつかの実施形態において使用され得ることを理解するであろう。例えば、最終的な行列は、ｑ−ビットの演算の組、量子ゲートの組、量子ゲート演算の組、または、量子コンピュータ３０によって使用される任意の他の形式として解釈され得る。いくつかの実施形態において（例えば、ＱＵＢＯ実施形態）において、各ｑ−ビットは、スピンアップまたはスピンダウンの代わりに、＋１または０であってよい。
【００３４】
[0047] ハミルトニアン行列または他のエネルギー表現のエネルギーは、量子コンピュータ３０によって最小化され得（２４５）、出力ｑ−ビット、Ｓｉは、従来のコンピュータ２０によって量子コンピュータ３０から取り出され得る。例えば、図３ｂに示されるように、最終的な行列Ｆについての最小エネルギーベクトルが見出される（３９０）。
【００３５】
［0048］ 図３ａに戻ると、その後、結果は、従来のコンピュータによって解釈され得る。＋１または−１のいずれかであり得る各ｑ−ビット出力は、最初のｑ−ビットの値、Ｓ１によって乗じられ得る。最初のｑ−ｂｉｔは無視され得る。図３ｂに示されるように、最小エネルギーベクトルは、制約のない値として解釈され得る（３９５）。回路の所望の入力または出力についての値を見出すために、各入力または出力インデックス ｎ について、出力ｑ−ビット、Ｓｎ＋１が検査される。ｑ−ビットが＋１である場合、入力または出力が１の値を有すると結論付けることができる。ｑ−ビットが−１の場合、入力または出力が０の値を有すると結論付けることができる。
【００３６】
［0049］ 上記の例は、特定の問題解決のシナリオのための図３のプロセス２００を示。この技術に通常の技量を有する者は、同じプロセス２００が、任意の最適化または制約問題に適用され得ること、および、回路、テーブル、行列、エネルギー状態、等は異なり得るが、プロセス２００が同様の方法で実施され得ることを理解するであろう。
【００３７】
［0050］ 例えば、図３ａのプロセス２００は、ＳＨＡ−１暗号学的ハッシュ関数または他のハッシュ関数のプレイメージを見つけるために適用され得る。この例では、ハッシュ関数は、正準ゲートを用いる回路に変換されることができ（２０５）、ラベル付けされ（２１０−２１５）、テーブル形式に変換され（２２０）、行列に変換される（２２５−２３０）。出力は制約され得（例えば、ハッシュ関数の既知の出力に）、制約が付けられた出力が行列に適用される（２３５）。最終的な行列が解釈され得（２４０）、最小エネルギー状態が見出され（２４５）、解釈された結果が、ハッシュ関数についてのプレイメージを明らかにし得る（２５０）。
【００３８】
［0051］ 別の例では、図３ａのプロセス２００は、ＡＥＳ暗号化アルゴリズムや他の暗号アルゴリズムの平文を見出すために適用することができる。この例では、暗号化アルゴリズムは、正準ゲートを用いた回路に変換され（２０５）、ラベル付けされ（２１０−２１５）、テーブル形式に変換され（２２０）、行列に変換され得る（２２５−２３０）。制約が定義され（例えば、鍵のビットの既知のサブセットと出力暗号文）、制約は行列に適用される（２３５）。最終的な行列が解釈され（２４０）、最小エネルギー状態が見出され（２４５）、解釈された結果が暗号化アルゴリズムについての平文を明らかにし得る（２５０）。
【００３９】
［0052］ また、図３ａのプロセス２００は、巡回セールスマン問題に適用されることができる。例えば、正準ゲートをもった回路が場所の組と場所間の巡回距離を定義し得る。回路はラベル付けされ（２１０−２１５）、テーブル形式に変換され（２２０）、行列に変換され得る（２２５−２３０）。制約は、両方が回路への入力であり得る、訪問するべき場所の組と、全ての訪問のために割り当てられた総時間を含み得る。制約入力が行列に適用され得る（２３５）。最終的な行列が解釈され得（２４０）、最小エネルギー状態が見出され得（２４５）、解釈された結果が、１つまたはそれより多くの可能なルートを含み得るか、または、割り当てられた時間でどの経路も可能でない場合、どの経路も可能でないとの表示を含み得る（２５０）。どの経路も可能でない場合、制約が、場所のより小さいリストに、または、増加された割り当て時間に変更され得る。
【００４０】
[0053] 様々な実施形態が上述されているが、それらは、限定ではなく、例として提示されていることが理解されるべきである。形態および具体例における様々な変更が、趣旨や範囲から逸脱することなく、それらの中になされ得ることが、当技術に技量を有する者には明らかである。事実上、上記記載を読んだ後、いかに代替の実施形態を実装するかは、当技術に技量を有する者には明らかであろう。
【００４１】
［0054］ 加えて、機能性や利点を強調して示す任意の図は、例示のみを目的として提示されていることを理解すべきである。開示された方法およびシステムは、各々、示されるもの以外の方法でそれらが利用され得るように十分に適応性があり、構成可能である。
【００４２】
[0055] 「少なくとも１つ（at least one）」の用語は、多くの場合、明細書、特許請求の範囲、および、図面においてしばしば使用されるが、「ａ」、「ａｎ」、「ｔｈｅ」、「ｓａｉｄ（前記）」等の用語も、明細書、特許請求の範囲、および、図面において、「少なくとも１つ（at least one）」または「前記少なくとも１つ（the at least one）」を意味する。
【００４３】
［0056］ 最後に、「ｍｅａｎｓ ｆｏｒ（〜のための手段）」または「ｓｔｅｐ ｆｏｒ（〜のためのステップ）」との明示的な用語を含む特許請求の範囲の請求項のみが、米国特許法１１２条（ｆ）項に基づく解釈をされることが出願人の意図である。「ｍｅａｎｓ ｆｏｒ」または「ｓｔｅｐ ｆｏｒ」の文言を明示的に含まない特許請求の範囲の請求項は、米国特許法１１２条（ｆ）項に基づく解釈をされるべきではない。
【図１】
2017515195.tif 000004
【図２】
2017515195.tif 000005
【図３ａ】
2017515195.tif 000006
【図３ｂ】
2017515195.tif 000007
【図４】
2017515195.tif 000008
【図５】
2017515195.tif 000009
【図６】
2017515195.tif 000010
【図７】
2017515195.tif 000011
【図８】
2017515195.tif 000012
【図９】
2017515195.tif 000013
【図１０】
2017515195.tif 000014
【図１１】
2017515195.tif 000015
【図１２】
2017515195.tif 000016
【図１３】
2017515195.tif 000017
【国際調査報告】
2017515195.tif 000018