(57)【要約】  系および方法は、複数のキュービットを空間的構造に選択的に配置して、量子コンピューター計算問題をエンコードすることに関する。種々の量子コンピューター計算問題をエンコードするために例示的な配置技術が適用され得る。複数のキュービットは、種々の駆動技術により最終状態に駆動され得る。量子コンピューター計算問題に対する正確なまたはおよその解を同定するために最終状態が測定され得る。
2021536610.tif 000002
【特許請求の範囲】
【請求項１】
複数のキュービットを空間的構造に選択的に配置して、量子コンピューター計算問題をエンコードする工程、ここで、各キュービットは、量子コンピューター計算問題における頂点(vertex)に対応し、キュービットの空間的近接は、量子コンピューター計算問題におけるエッジ(edge)を示す；
複数のキュービットを初期状態に初期化する工程；
一定でない(variable)持続時間および一定でない光学的位相を有する共鳴光パルスのシーケンスを複数のキュービットの少なくともいくつかに適用することにより、複数のキュービットを最終状態に駆動する工程、ここで、最終状態は、量子コンピューター計算問題に対する解を含む；ならびに
最終状態において、複数のキュービットの少なくともいくつかを測定する工程、
を含む、方法。
【請求項２】
空間的構造は、1次元、2次元または3次元のキュービットのアレイを含む、請求項１記載の方法。
【請求項３】
エンコードされた量子コンピューター計算問題は、重み無し最大独立集合問題(unweighted maximum independent set problem)、重み付き最大独立集合問題(maximum-weight independent set problem)、最大クリーク問題(maximum clique problem)、および最小頂点被覆問題(minimum vertex cover problem)の1つ以上を含む、請求項１記載の方法。
【請求項４】
重み付き最大独立集合問題における重みは、光シフトを複数のキュービットの少なくともいくつかに適用することにより、エンコードされる、請求項３記載の方法。
【請求項５】
複数のキュービットの最終状態は、エンコードされた重み無し最大独立集合問題に対する解、エンコードされた重み付き最大独立集合問題に対する解、エンコードされた最大クリーク問題に対する解、およびエンコードされた最小頂点被覆問題に対する解の1つ以上を含む、請求項３記載の方法。
【請求項６】
量子コンピューター計算問題に対する解は、量子コンピューター計算問題に対するおよその解を含む、請求項１記載の方法。
【請求項７】
複数のキュービットを、複数の頂点キュービットおよび複数のアンシラリー(ancillary)キュービットを含む空間的構造に選択的に配置し、該複数のキュービットの空間的近接を使用して量子コンピューター計算問題をエンコードする工程、ここで、各頂点キュービットは、量子コンピューター計算問題における頂点に対応し、アンシラリーキュービットのサブセットは、量子コンピューター計算問題におけるエッジに対応する；
該複数のキュービットを初期状態に初期化する工程；
該複数のキュービットを最終状態に駆動する工程、ここで、該最終状態は、量子コンピューター計算問題に対する解を含む；ならびに
最終状態において該複数のキュービットの少なくともいくつかを測定する工程、
を含む、方法。
【請求項８】
複数のキュービットを最終状態に駆動する工程は、一定または一定でないラビ周波数Ωおよび一定または一定でない離調(detuning)Δを有する光パルスを該複数のキュービットの少なくともいくつかに適用することを含む、請求項７記載の方法。
【請求項９】
光パルスを複数のキュービットの少なくともいくつかに適用することは、離調
【数１】
2021536610.tif 000784
を有する少なくとも1つの光パルスをコーナー頂点(corner vertex)またはジャンクション頂点(junction vertex)を含む頂点キュービットに適用すること；および
離調
【数２】
2021536610.tif 000785
を有する少なくとも1つの光パルスを、頂点キュービットに連結されるエッジ上の頂点キュービットに近接するiアンシラリーキュービットの各々に適用することをさらに含む、請求項８記載の方法。
【請求項１０】
光パルスを複数のキュービットの少なくともいくつかに適用することは、光シフトを該複数のキュービットの少なくともいくつかのうちの選択されたキュービットに適用することをさらに含む、請求項９記載の方法。
【請求項１１】
複数のキュービットを最終状態に駆動する工程は、一定でない持続時間および一定でない光学的位相を有する共鳴光パルスのシーケンスを、該複数のキュービットの少なくともいくつかに適用することを含む、請求項７記載の量子コンピューター計算方法。
【請求項１２】
複数のキュービットを複数の頂点キュービットおよび複数のアンシラリーキュービットに配置することは、複数のキュービットをグリッド(grid)に配置することを含む、請求項７記載の方法。
【請求項１３】
エンコードされた量子コンピューター計算問題は、重み無し最大独立集合問題、重み付き最大独立集合問題、最大クリーク問題、および最小頂点被覆問題の1つ以上を含む、請求項７記載の方法。
【請求項１４】
重み付き最大独立集合問題の重みは、光シフトを複数のキュービットに適用することによりエンコードされる、請求項１３記載の方法。
【請求項１５】
複数のキュービットの最終状態は、エンコードされた重み無し最大独立集合問題に対する解、エンコードされた重み付き最大独立集合問題に対する解、エンコードされた最大クリーク問題に対する解、およびエンコードされた最小頂点被覆問題に対する解の1つ以上を含む、請求項１３記載の方法。
【請求項１６】
量子コンピューター計算問題をエンコードする前に量子コンピューター計算問題中の少なくとも2つの頂点の番号付け替えをさらに含む、請求項７記載の方法。
【請求項１７】
量子コンピューター計算問題に対する解は、量子コンピューター計算問題に対するおよその解を含む、請求項７記載の方法。
【請求項１８】
複数のキュービットを空間的構造に選択的に配置し、量子コンピューター計算問題をエンコードする工程、ここで、各キュービットは、量子コンピューター計算問題中の頂点に対応する；
該複数のキュービットを初期状態に初期化する工程；
該複数のキュービットを最終状態にストロボ的に駆動する工程、ここで、最終状態は、量子コンピューター計算問題に対する解を含む；および
最終状態において該複数のキュービットの少なくともいくつかを測定する工程、
を含む、方法。
【請求項１９】
複数のキュービットを最終状態にストロボ的に駆動する工程は、光パルスを連続的かつ選択的にある順序で複数のキュービットのサブセットに適用することを含み、光パルスの該順序は、量子コンピューター計算問題のグラフ構造に対応する、請求項１８記載の方法。
【請求項２０】
複数のキュービットを最終状態に駆動する工程は、一定または一定でないラビ周波数Ωおよび一定または一定でない離調Δを有する光パルスを該複数のキュービットの少なくともいくつかに適用することを含む、請求項１８記載の方法。
【請求項２１】
複数のキュービットを最終状態に駆動する工程は、一定でない持続時間および一定でない光学的位相を有する共鳴光パルスのシーケンスを該複数のキュービットの少なくともいくつかに適用することを含む、請求項１８記載の方法。
【請求項２２】
エンコードされた量子コンピューター計算問題は、重み無し最大独立集合問題、重み付き最大独立集合問題、最大クリーク問題、および最小頂点被覆問題の1つ以上を含む、請求項１８記載の方法。
【請求項２３】
重み付き最大独立集合問題における重みは、光シフトを複数のキュービットに適用することによりエンコードされる、請求項２２記載の方法。
【請求項２４】
複数のキュービットの最終状態は、エンコードされた重み無し最大独立集合問題に対する解、エンコードされた重み付き最大独立集合問題に対する解、エンコードされた最大クリーク問題に対する解、およびエンコードされた最小頂点被覆問題(minimum vertex cover)に対する解の1つ以上を含む、請求項２２記載の方法。
【請求項２５】
量子コンピューター計算問題をエンコードする前に、量子コンピューター計算問題の少なくとも2つの頂点の番号付け替えをさらに含む、請求項１８記載の方法。
【請求項２６】
量子コンピューター計算問題に対する解は、量子コンピューター計算問題に対するおよその解を含む、請求項１８記載の方法。
【請求項２７】
量子コンピューター計算問題をエンコードするために、複数のキュービットを配置する工程；
qレベルの光パルスのシーケンスを複数のキュービットに適用する工程、ここで、該qレベルの光パルスは、少なくともq変動性パラメーター(variational parameter)の第1の組およびq変動性パラメーターの第2の組を含む；
複数のキュービットの1つ以上の状態を測定する工程；
複数のキュービットの1つ以上の少なくともいくつかの測定された状態に基づいて、qレベルの光パルスのq変動性パラメーターの第1の組およびq変動性パラメーターの第2の組を最適化する工程；
qレベルの光パルスのq最適化変動性パラメーターの第1の組およびq最適化変動性パラメーターの第2の組に少なくとも基づいて、pレベルの光パルスのp変動性パラメーターの第1の組およびp変動性パラメーターの第2の組を最適化する工程、ここで、q<p；ならびに
最終状態において該複数のキュービットの少なくともいくつかを測定する工程、
を含む、方法。
【請求項２８】
pレベルの光パルスのp変動性パラメーターの第1の組およびp変動性パラメーターの第2の組を最適化する工程は、pレベルの光パルスのp変動性パラメーター開始値の第1の組およびp変動性パラメーター開始値の第2の組をコンピューター計算することをさらに含む、請求項２７記載の方法。
【請求項２９】
p>1においてpレベルの光パルスのp変動性パラメーター開始値の第1の組をコンピューター計算することは、qレベルの光パルスのq変動性パラメーターの第1の組の、複数のk周波数成分へのフーリエ変換を実施すること、ここで、k周波数成分の各々は、振幅
【数３】
2021536610.tif 000786
を有する；および
振幅
【数４】
2021536610.tif 000787
に基づいて、pレベルの光パルスのp変動性パラメーター開始値の第1の組をコンピューター計算すること、を含む、請求項２８記載の方法。
【請求項３０】
p>1においてpレベルの光パルスのp変動性パラメーター開始値の第2の組をコンピューター計算することは、qレベルの光パルスのq変動性パラメーターの第2の組を複数のk周波数成分へのフーリエ変換を実施すること、ここで、k周波数成分の各々は、振幅
【数５】
2021536610.tif 000788
を有する；および
振幅
【数６】
2021536610.tif 000789
に基づいて、pレベルの光パルスのp変動性パラメーター開始値の第2の組をコンピューター計算すること、を含む請求項２８記載の方法。
【請求項３１】
pレベルの光パルスのp変動性パラメーター開始値の第1の組およびp変動性パラメーター開始値の第2の組をコンピューター計算することは：
qレベルの光パルスのq変動性パラメーターの第1の組に基づいてpレベルの光パルスのp変動性パラメーター開始値の第1の組を外挿すること;および
qレベルの光パルスのq変動性パラメーターの第2の組に基づいてpレベルの光パルスのp変動性パラメーター開始値の第2の組を外挿すること、
を含む、請求項２８記載の方法。
【請求項３２】
pレベルの光パルスのシーケンスを、p最適化変動性パラメーターの第1の組およびp最適化変動性パラメーターの第2の組を有する複数のキュービットに適用することをさらに含む方法であって、最終状態において複数のキュービットの少なくともいくつかを測定する工程は、pレベルの光パルスのシーケンスを複数のキュービットに適用した後に、該複数のキュービットの少なくともいくつかを測定することを含む、請求項２７記載の方法。
【請求項３３】
エンコードされた量子コンピューター計算問題は、MaxCut問題を含み、複数のキュービットの最終状態は、MaxCut問題に対する解を含む、請求項２７記載の方法。
【請求項３４】
エンコードされた量子コンピューター計算問題は、最大独立集合問題を含み、複数のキュービットの最終状態は、最大独立集合問題に対する解を含む、請求項２７記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
本願は、2018年8月31日に出願された発明の名称「QUANTUM OPTIMIZATION FOR MAXIMUM INDEPENDENT SET USING RYDBERG ATOM ARRAYS」の米国仮出願第62/725,874号に対する優先権の利益を主張し、該出願の開示はその全体において参照により本明細書に援用される。
【０００２】
著作権注意
本特許開示は、著作権保護を必要とする資料を含み得る。著作権所有者は、米国特許商標庁の特許ファイルまたは記録に現われる場合、特許文書または特許開示のいずれかによる複写再生に対して異議を有さないが、そうでない場合、任意および全ての著作権を保有する。
【０００３】
連邦政府後援研究または開発に関する陳述
本発明は、国立科学基金により授与された助成金番号1506284、PHY-1125846、およびPHY-1521560;米国空軍科学研究局により授与されたFA9550-17-1-0002;ならびに米国防衛省/海軍研究局により授与されたN00014-15-1-2846の元の政府援助によりなされた。政府は、本発明において一定の権利を有する。
【０００４】
技術分野
本特許は、量子コンピューター計算に関し、より具体的には、量子コンピューター計算のための原子のアレイの調製および進展（evolve）に関する。
【背景技術】
【０００５】
背景
量子シミュレーターとしての、完全に制御されたコヒーレントな多体量子系は、強く相互に関係した量子系および量子もつれの役割について特有の洞察を提供し得、平衡から離れていても、物質の新しい状態の実現および研究を可能にし得る。これらの系はまた、量子情報処理装置の実現のための基礎を形成する。かかる処理装置の基本的構築ブロックは、いくつかのカップリングされたキュービットの系において示されてきたが、コヒーレントにカップリングされたキュービットの数を増加させて現代の古典的な機械が及ばないタスクを実施することは、困難である。さらに、現存する系は、完全な量子ダイナミクス（fully quantum dynamics）を達成するために、コヒーレンスおよび/または量子非線形性を欠いている。
【０００６】
中性原子は、表題「NEUTRAL ATOM QUANTUM INFORMATION PROCESSOR」のPCT出願番号PCT/US18/42080においてより詳細に記載されるように、大規模量子系のための構築ブロックとして働き得る。該大規模量子系は、環境から十分に分離され得、長持ちする量子記憶を可能にする。該大規模量子系の内部および運動状態の初期化、制御、および読出しは、過去40年にわたって開発された共鳴方法により達成される。多くの同一の原子を有するアレイは、単一原子の光学的制御を維持しつつ、迅速に集合され得る。これらのボトムアップ式アプローチは、蒸発式冷却（evaporative cooling）により調製された極低温原子を負荷した光学的格子が関与する方法に補完的であり、一般的に、数μｍの原子分離を生じる。原子間の制御可能な相互作用は、これらのアレイを量子シミュレーションおよび量子情報処理に使用するために導入され得る。これは、高度に励起されたリュードベリ状態に対するコヒーレントなカップリングにより達成され得、該リュードベリ状態は、強く長距離の相互作用を示す。このアプローチは、迅速な多キュービット量子ゲート、250スピンまでを有するイジング型スピンモデルの量子シミュレーション、およびメソスコピックアンサンブル（mesoscopic ensemble）における集合的挙動の研究などの多くの適用のための強力な基盤を提供する。かかるリュードベリ励起に関連する短いコヒーレンス時間および比較的低いゲート忠実度は、意欲をかきたてる（challenging）。この不完全なコヒーレンスは、量子シミュレーションの質を制限し得、中性原子量子情報処理の見通しを曇らせ得る。制限されたコヒーレンスは、単一の単離された原子キュービットのレベルでも明らかになる。
【０００７】
PCT/US18/42080は、量子コンピューター計算のための例示的な方法および系を記載する。これらの系および方法は、まず、個々の原子を捕捉すること、および例えば聴覚光学ディフレクターを使用して、該個々の原子を、複数の原子の特定の幾何学的配置（configuration）に配置することを含み得る。個々の原子のこの正確な配置は、量子コンピューター計算問題のエンコードを補助する。次いで、１つ以上の配置された原子は、リュードベリ状態に励起され得、該リュードベリ状態は、アレイ中の原子間の相互作用を生じさせ得る。その後、系は、制御された環境下で進展し得る。最後に、エンコードされた問題に対する解を観測するために、原子の状態を読出し得る。さらなる例としては、原子の集合されたアレイの高い忠実度およびコヒーレントな制御を提供することが挙げられる。
【発明の概要】
【０００８】
概要
1つ以上の態様において、方法は、複数のキュービットを空間的構造に選択的に配置して、量子コンピューター計算問題をエンコードすること、ここで、各キュービットは、量子コンピューター計算問題における頂点（vertex）に対応し、キュービットの空間的近接は、量子コンピューター計算問題のエッジ（edge）を示す;複数のキュービットを初期状態に初期化すること;一定でない（variable）持続時間および一定でない光学的位相を有する共鳴光パルスのシーケンスを複数のキュービットの少なくともいくつかに適用することにより、複数のキュービットを最終状態に駆動すること、ここで、最終状態は、量子コンピューター計算問題に対する解を含む;ならびに最終状態において、複数のキュービットの少なくともいくつかを測定すること、を含む。
【０００９】
1つ以上の態様において、空間的構造は、１次元、２次元または３次元のキュービットのアレイを含む。
【００１０】
1つ以上の態様において、エンコードされた量子コンピューター計算問題は、重み無し最大独立集合問題（unweighted maximum independent set problem）、重み付き最大独立集合問題（maximum-weight independent set problem）、最大クリーク問題（maximum clique problem）、および最小頂点被覆問題（minimum vertex cover problem）の１つ以上を含む。
【００１１】
1つ以上の態様において、重み付き最大独立集合問題における重みは、光シフトを複数のキュービットの少なくともいくつかに適用することにより、エンコードされる。
【００１２】
1つ以上の態様において、複数のキュービットの最終状態は、エンコードされた重み無し最大独立集合問題に対する解、エンコードされた重み付き最大独立集合問題に対する解、エンコードされた最大クリーク問題に対する解、およびエンコードされた最小頂点被覆問題に対する解の１つ以上を含む。
【００１３】
1つ以上の態様において、量子コンピューター計算問題に対する解は、量子コンピューター計算問題に対するおよその解を含む。
【００１４】
1つ以上の態様において、方法は、複数のキュービットを、複数の頂点キュービットおよび複数のアンシラリー(ancillary)キュービットを含む空間的構造に選択的に配置し、該複数のキュービットの空間的近接を使用して量子コンピューター計算問題をエンコードすること、ここで、各頂点キュービットは、量子コンピューター計算問題における頂点に対応し、アンシラリーキュービットのサブセットは、量子コンピューター計算問題のエッジに対応する;該複数のキュービットを初期状態に初期化すること;該複数のキュービットを最終状態に駆動すること、ここで、該最終状態は、量子コンピューター計算問題に対する解を含む;ならびに最終状態において該複数のキュービットの少なくともいくつかを測定すること、を含む。
【００１５】
1つ以上の態様において、複数のキュービットを最終状態に駆動することは、一定または一定でないラビ周波数Ωおよ
び一定または一定でない離調（detuning）
【数Ａ】
2021536610.tif 000003
を有する光パルスを該複数のキュービットの少なくともいくつかに適用することを含む。
【００１６】
1つ以上の態様において、光パルスを複数のキュービットの少なくともいくつかに適用することは、離調
【数Ｂ】
2021536610.tif 000004
を有する少なくとも１つの光パルスをコーナー頂点（corner vertex）またはジャンクション頂点（junction vertex）を含む頂点キュービットに適用すること;および離調
【数Ｃ】
2021536610.tif 000005
を有する少なくとも１つの光パルスを、頂点キュービットに連結されるエッジ上の頂点キュービットに近接するiアンシラリーキュービットの各々に適用することをさらに含む。
【００１７】
1つ以上の態様において、光パルスを複数のキュービットの少なくともいくつかに適用することは、光シフトを該複数のキュービットの少なくともいくつかのうちの選択されたキュービットに適用することをさらに含む。
【００１８】
1つ以上の態様において、複数のキュービットを最終状態に駆動することは、一定でない持続時間および一定でない光学的位相を有する共鳴光パルスのシーケンスを、該複数のキュービットの少なくともいくつかに適用することを含む。
【００１９】
1つ以上の態様において、複数のキュービットを複数の頂点キュービットおよび複数のアンシラリーキュービットに配置することは、複数のキュービットをグリッド（grid）に配置することを含む。
【００２０】
1つ以上の態様において、エンコードされた量子コンピューター計算問題は、重み無し最大独立集合問題、重み付き最大独立集合問題、最大クリーク問題、および最小頂点被覆問題の１つ以上を含む。
【００２１】
1つ以上の態様において、重み付き最大独立集合問題の重みは、光シフトを複数のキュービットに適用することによりエンコードされる。
【００２２】
1つ以上の態様において、複数のキュービットの最終状態は、エンコードされた重み無し最大独立集合問題に対する解、エンコードされた重み付き最大独立集合問題に対する解、エンコードされた最大クリーク問題に対する解、およびエンコードされた最小頂点被覆問題に対する解の１つ以上を含む。
【００２３】
1つ以上の態様において、該方法は、量子コンピューター計算問題をエンコードする前に量子コンピューター計算問題中の少なくとも２つの頂点の番号付け替えをさらに含む。
【００２４】
1つ以上の態様において、量子コンピューター計算問題に対する解は、量子コンピューター計算問題に対するおよその解を含む。
【００２５】
1つ以上の態様において、方法は、複数のキュービットを空間的構造に選択的に配置し、量子コンピューター計算問題をエンコードすること、ここで、各キュービットは、量子コンピューター計算問題中の頂点に対応する;該複数のキュービットを初期状態に初期化すること;該複数のキュービットを最終状態にストロボ的に駆動すること、ここで、最終状態は、量子コンピューター計算問題に対する解を含む;および最終状態において該複数のキュービットの少なくともいくつかを測定すること、を含む。
【００２６】
1つ以上の態様において、複数のキュービットを最終状態にストロボ的に駆動することは、光パルスを連続的かつ選択的にある順序で複数のキュービットのサブセットに適用することを含み、光パルスの該順序は、量子コンピューター計算問題のグラフ構造に対応する。
【００２７】
1つ以上の態様において、複数のキュービットを最終状態に駆動することは、一定または一定でないラビ周波数Ωおよび一定または一定でない離調
【数Ｄ】
2021536610.tif 000006
を有する光パルスを該複数のキュービットの少なくともいくつかに適用することを含む。
【００２８】
1つ以上の態様において、複数のキュービットを最終状態に駆動することは、一定でない持続時間および一定でない光学的位相を有する共鳴光パルスのシーケンスを該複数のキュービットの少なくともいくつかに適用することを含む。
【００２９】
1つ以上の態様において、エンコードされた量子コンピューター計算問題は、重み無し最大独立集合問題、重み付き最大独立集合問題、最大クリーク問題、および最小頂点被覆問題の１つ以上を含む。
【００３０】
1つ以上の態様において、重み付き最大独立集合問題における重みは、光シフトを複数のキュービットに適用することによりエンコードされる。
【００３１】
1つ以上の態様において、複数のキュービットの最終状態は、エンコードされた重み無し最大独立集合問題に対する解、エンコードされた重み付き最大独立集合問題に対する解、エンコードされた最大クリーク問題に対する解、およびエンコードされた最小頂点被覆問題（minimum vertex cover）に対する解の１つ以上を含む。
【００３２】
1つ以上の態様において、該方法は、量子コンピューター計算問題をエンコードする前に、量子コンピューター計算問題の少なくとも２つの頂点の番号付け替えをさらに含む。
【００３３】
1つ以上の態様において、量子コンピューター計算問題に対する解は、量子コンピューター計算問題に対するおよその解を含む。
【００３４】
1つ以上の態様において、方法は、量子コンピューター計算問題をエンコードするために、複数のキュービットを配置すること;qレベルの光パルスのシーケンスを複数のキュービットに適用すること、ここで、該qレベルの光パルスは、少なくともq変動性パラメーター（variational parameter）の第1の組およびq変動性パラメーターの第2の組を含む;複数のキュービットの１つ以上の状態を測定すること;複数のキュービットの１つ以上の少なくともいくつかの測定された状態に基づいて、qレベルの光パルスのq変動性パラメーターの第1の組およびq変動性パラメーターの第2の組を最適化すること;qレベルの光パルスのq最適化変動性パラメーターの第1の組およびq最適化変動性パラメーターの第2の組に少なくとも基づいて、pレベルの光パルスのp変動性パラメーターの第1の組およびp変動性パラメーターの第2の組を最適化すること、ここで、q<p;ならびに最終状態において該複数のキュービットの少なくともいくつかを測定すること、を含む。
【００３５】
1つ以上の態様において、pレベルの光パルスのp変動性パラメーターの第1の組およびp変動性パラメーターの第2の組を最適化することは、pレベルの光パルスのp変動性パラメーター開始値の第1の組およびp変動性パラメーター開始値の第2の組をコンピューター計算することをさらに含む。
【００３６】
1つ以上の態様において、p>1においてpレベルの光パルスのp変動性パラメーター開始値の第1の組をコンピューター計算することは、qレベルの光パルスのq変動性パラメーターの第1の組の、複数のk周波数成分へのフーリエ変換を実施すること、ここで、k周波数成分の各々は、振幅
【数１】
2021536610.tif 000007
を有する;および振幅
【数２】
2021536610.tif 000008
に基づいて、pレベルの光パルスのp変動性パラメーター開始値の第1の組をコンピューター計算すること、を含む。
【００３７】
1つ以上の態様において、p>1においてpレベルの光パルスのp変動性パラメーター開始値の第2の組をコンピューター計算することは、qレベルの光パルスのq変動性パラメーターの第2の組の、複数のk周波数成分へのフーリエ変換を実施すること、ここで、k周波数成分の各々は、振幅
【数３】
2021536610.tif 000009
を有する:および振幅
【数４】
2021536610.tif 000010
に基づいて、pレベルの光パルスのp変動性パラメーター開始値の第2の組をコンピューター計算すること、を含む。
【００３８】
1つ以上の態様において、pレベルの光パルスのp変動性パラメーター開始値の第1の組およびp変動性パラメーター開始値の第2の組をコンピューター計算することは、qレベルの光パルスのq変動性パラメーターの第1の組に基づいてpレベルの光パルスのp変動性パラメーター開始値の第1の組を外挿すること;およびqレベルの光パルスのq変動性パラメーターの第2の組に基づいて pレベルの光パルスのp変動性パラメーター開始値の第2の組を外挿すること、を含む。
【００３９】
1つ以上の態様において、該方法は、pレベルの光パルスのシーケンスを、p最適化変動性パラメーターの第1の組およびp最適化変動性パラメーターの第2の組を有する複数のキュービットに適用することをさらに含み、最終状態において複数のキュービットの少なくともいくつかを測定することは、pレベルの光パルスのシーケンスを複数のキュービットに適用した後に、該複数のキュービットの少なくともいくつかを測定することを含む。
【００４０】
1つ以上の態様において、エンコードされた量子コンピューター計算問題は、MaxCut問題を含み、複数のキュービットの最終状態は、MaxCut問題に対する解を含む。
【００４１】
1つ以上の態様において、エンコードされた量子コンピューター計算問題は、 最大独立集合問題を含み、複数のキュービットの最終状態は、最大独立集合問題に対する解を含む。
【図面の簡単な説明】
【００４２】
図面の簡単な説明
開示された主題の種々の目的、特徴、および利点は、以下の図面と関連して考慮された場合に、開示された主題の以下の詳細な説明に関してより十分に理解され得、該図面において、同様の参照番号は、同様の要素を示す。
【図１】図1A〜1Eは、いくつかの態様によるキュービットのアレイを使用して最適化問題をエンコードしかつそれに対する解を見出すための例示的な図解を示す。
【図２Ａ】図2Aは、いくつかの態様による頂点およびアンシラリーキュービットの配置を示し、特徴づける。
【図２Ｂ】図2Bは、いくつかの態様による頂点およびアンシラリーキュービットの配置を示し、特徴づける。
【図３】図3A〜3Bは、いくつかの態様によるランダムUDグラフ上のMISに対する古典的な分岐限定（branch and bound）アルゴリズムの性能を示すグラフである。
【図４】図4A〜4Dは、いくつかの態様によるランダムUDグラフのMISに対する量子アルゴリズムの性能を示すグラフである。
【図５】図5は、いくつかの態様による例示的なランダム単位円グラフ（unit disk graph）である。
【図６】図6は、いくつかの態様による断熱的時間スケールTLZを抽出するための方法を示すグラフである。
【図７】図7A〜7Cは、いくつかの態様による断熱的時間スケールTLZの局面を示すグラフである。
【図８】図8は、いくつかの態様による近似比（approximation ratio）rに関する量子アルゴリズムについての状態図（phase diagram）である。
【図９】図9は、いくつかの態様によるリュードベリ問題の挙動を示す図示およびグラフである。
【図１０】図10A〜10Bは、いくつかの態様による最大次数（maximum degree）3の平面グラフのグリッド表示および単位円グラフへの変換である。
【図１１】図11A〜11Cは、いくつかの態様による非最近傍（non-nearest-neighbor）相互作用を考慮した最大次数3の平面グラフのグリッド表示である。
【図１２Ａ−Ｅ】図12AおよびEは、いくつかの態様による有効スピンモデル（effective spin model）への変換のグリッド表示である。
【図１２Ｂ】図12Bは、いくつかの態様による有効スピンモデルへの変換のグリッド表示である。
【図１２Ｃ】図12Cは、いくつかの態様による有効スピンモデルへの変換のグリッド表示である。
【図１２Ｄ】図12Dは、いくつかの態様による有効スピンモデルへの変換のグリッド表示である。
【図１３】図13A〜13Bは、いくつかの態様による局所的な非最大独立集合配置およびドメイン壁（domain wall）の図示である。
【図１４Ａ】図14Aは、いくつかの態様によるp-レベルQAOAアルゴリズムの概略図である。
【図１４Ｂ】図14Bは、いくつかの態様による例示的なMaxCut問題の図示である。
【図１５Ａ−Ｂ】図15A〜15Bは、いくつかの態様によるQAOA最適変動性パラメーターを示すグラフである。
【図１５Ｃ−Ｈ】図15C〜15Hは、いくつかの態様によるQAOA最適変動性パラメーターを示すグラフである。
【図１６Ａ−Ｂ】図16A〜16Bは、いくつかの態様による開示されたヒューリスティック（heuristic）戦略の態様と腕ずくの方法（brute force method）の態様の比較を示すグラフである。
【図１６Ｃ−Ｄ】図16C〜16Dは、いくつかの態様によるQAOAの平均性能を示すグラフである。
【図１７Ａ−Ｃ】図17A〜17Cは、いくつかの態様によるQAと比べてのQAOAの性能を示すプロットである。
【図１７Ｄ−Ｅ】図17D〜17Eは、いくつかの態様によるQAと比べてのQAOAの性能を示すプロットである。
【図１７Ｆ−Ｈ】図17F〜17Hは、いくつかの態様によるQAと比べてのQAOAの性能を示すプロットである。
【図１７Ｉ−Ｊ】図17I〜17Jは、いくつかの態様によるQAと比べてのQAOAの性能を示すプロットである。
【図１８Ａ−Ｂ】図18A〜18Bは、いくつかの態様によるQAOAの非断熱的局面を示すグラフおよび図示である。
【図１８Ｃ−Ｆ】図18C〜18Fは、いくつかの態様によるQAOAの非断熱的局面を示すグラフおよび図示である。
【図１９】図19は、いくつかの態様によるQAOAのモンテカルロシミュレーションの結果を示すグラフである。
【図２０Ａ−Ｅ】図20A〜20Eは、いくつかの態様による例示的な頂点番号付け替え技術およびリュードベリ実行（Rydberg implementation）を示すグラフおよび図示である。
【図２０Ｆ】図20Fは、いくつかの態様による例示的な頂点番号付け替え技術およびリュードベリ実行を示すグラフおよび図示である。
【図２１】図21A〜21Fは、いくつかの態様によるQAOA最適変動性パラメーターを示すグラフである。
【図２２】図22は、いくつかの態様によるFOURIER[q, R]ヒューリスティック戦略の２つの変形の概略図である。
【図２３】図23は、いくつかの態様による種々のヒューリスティック戦略の間の比較を示すグラフである。
【図２４Ａ】図24Aは、いくつかの態様によるQAOAおよびQAについての解に対するエネルギースペクトルおよび時間を示すグラフである。
【図２４Ｂ】図24Bは、いくつかの態様によるQAOAおよびQAについての解に対するエネルギースペクトルおよび時間を示すグラフである。
【図２４Ｃ】図24Cは、いくつかの態様によるQAOAおよびQAについての解に対するエネルギースペクトルおよび時間を示すグラフである。
【図２５Ａ】図25Aは、いくつかの態様による例示的な瞬間的な固有状態集団およびカップリングを示すグラフである。
【図２５Ｂ】図25Bは、いくつかの態様による例示的な瞬間的な固有状態集団およびカップリングを示すグラフである。
【発明を実施するための形態】
【００４３】
詳細な説明
最適化アルゴリズムは、特定の問題について特定の基準が与えられた場合に、最良の解を見出すために使用される。組合せ最適化は、有限の組の解が与えられた場合に、問題に対する最適な解を同定することを含む。量子最適化は、個々の原子の2Dアレイなどの量子多体系の制御された動力学を使用することにより、組合せ最適化問題を解くための技術であり、該個々の原子の各々は、「キュービット」または「スピン」と言われ得る。量子アルゴリズムは、かかる問題をスピンモデルなどのプログラム可能な量子系の古典的な基底状態にエンコードすることにより、困難な最適化問題を組合せ的に解き得る。次いで、量子アルゴリズムは、系をこの基底状態に駆動するために、量子進展を使用するように設計され、その結果、その後の測定は、解を明らかにする。換言すれば、問題は、キュービットを所望の相互作用を有する所望の配置に配置することによりエンコードされ得、該所望の相互作用は、最適化問題により示される束縛（constraint）をエンコードする。適切にエンコードされた場合、多体系の基底状態は、最適化問題に対する解を含む。従って、問題は、進展過程により多体系をその基底状態に駆動することにより、解かれ得る。
【００４４】
理論に拘束されることなく、キュービット間の相互作用の完全な制御を仮定すると、非決定論的多項式（nondeterministic polynomial）(「NP」)-完全最適化問題をかかる系の基底状態にエンコードするのは可能である。しかし、ほとんどの実現において、全ての相互作用が、十分にプログラム可能というわけではない。代わりに、かかる相互作用は、局在していること（locality）、幾何学的結合性、または制御可能性などであるがこれらに限定されない特異的な物理的実現の特性により決定され、該特性は、効率的に実現され得る問題の種類を束縛するか、またはそれらの実現のために実質的なオーバーヘッド（overhead）が必要とされることを意味するかのいずれかである。従って、量子最適化アルゴリズムの理解および評価における難題の１つは、物理系における特異的およびより大きな種類の組合せ問題を、効率的かつ自然な方法でエンコードするための方法を設計することを含む。
【００４５】
いくつかの実行において、量子最適化は、(1)キュービットの対の間の特定の型および強さの相互作用が与えられた場合に、量子系において個々のキュービットの位置を制御することにより、問題をエンコードすること、ならびに(2)進展過程により量子系におけるキュービットの動力学を操ること、その結果、それらの進展した最終状態は、最適化問題に対する解を提供する、を含み得る。キュービットの動力学を最適化問題に対する基底状態解へと操ることは、量子アニーリングアルゴリズム(QAA)における断熱的原理などであるがこれらに限定されない複数の異なるプロセス、または量子近似最適化アルゴリズム(QAOA)などであるがこれらに限定されないより一般的な変動性アプローチにより達成され得る。かかるアルゴリズムは、古典的なコンピューターの能力を超えるコンピューター的に困難な問題に取り組み得る。しかし、これらのアルゴリズムのヒューリスティックな性質は、それらの実際の性能を予測することに難題を課し、実験的な試験を必要とする。さらに、かかる系は、それらの十分な一般性において（in their full generality）、上記した実際の束縛のために、実行するのが非効率的かつ困難であり、最適化問題のサブセットのみに使用され得る。
【００４６】
本開示のいくつかの局面は、プログラム可能なアレイにキュービットを配置するための系および方法に関し、該キュービットは、効率的な方法でより広い組の最適化問題をエンコードするかまたは近似的にエンコードし得る。いくつかの態様において、近接する「アンシラリー」キュービットの偶数の鎖は、例えば図2Aに関してより詳細に記載されるように、アンシラリーキュービットの鎖を用いて遠いキュービットを連結することにより、遠いキュービットの間の相互作用をエンコードするために使用される。本開示を通じてより詳細に記載されるように、「アンシラリー」キュービットのこれらの鎖は、他の頂点キュービットではなく特定の「頂点」キュービットの間の相互作用をエンコードするために使用され得、エッジにより連結されることを意図されない２つの頂点キュービットの間の長距離の相互作用の強さを低減するために使用され得る。いくつかの態様において、長距離の相互作用の効果は、特定のキュービットの間の相互作用を選択的に制御するために、離調パラメーターを選択された制御技術に導入することによりさらに低減され得る。例えば、コーナーおよびジャンクションキュービットについて、本開示に記載される離調パターンは、長距離の相互作用の効果を低減し得、その結果、系の基底状態は、エンコードされた問題に対する最適な解である。本明細書に記載される技術は、単純な単位円グラフを超えるより大きな組の最適化問題の効率的なエンコードを可能にし得る。
【００４７】
本開示のいくつかのさらなるまたは代替的な局面は、励起を含むキュービットの内部状態をコヒーレントに操作するための系および方法に関する。いくつかの態様において、エンコードされた問題を進展させ最適な(または近似的に最適な)解を見出すために使用され得る技術が、開示される。例えば、本開示の態様は、量子近似最適化アルゴリズム(「QAOA」)を実施するための最適変動性パラメーターおよび戦略に関し、そのうちいくつかの態様は、例えば、図14Aに関して記載される。例えば、態様は、古典的なフィードバックループのためのヒューリスティックを含み、これは、腕ずくのQAOA実行の性能を改善し得る。いくつかの態様において、これらの戦略は、現存するアルゴリズム以下である場合、少なくとも同様に実施される。本開示のいくつかの局面は、MaxCut組合せ問題を解くためにQAOAを使用する実行に焦点を合わせているが、開示された技術は、それに限定されない。
【００４８】
例示的な最適化問題およびエンコード
いくつかの態様において、特定の型の最適化問題は、キュービットの配置を用いてエンコードされ得る。例えば、図1A〜1Eは、いくつかの態様によるキュービットのアレイを使用して最適化問題に対する解をエンコードするおよび見出すための例示的な図解を示す。図1Aは、いくつかの態様による単位円グラフ上のリュードベリブロッケード機構（Rydberg blockade mechanism）および最大独立集合の局面を示す。本開示に記載される技術を使用して解かれ得る１つの例示的な最適化問題は、最大独立集合(「MIS」)問題である。グラフGが頂点VおよびエッジEを有すると仮定すると、独立集合は、対がエッジにより連結されていない頂点のサブセットとして、画定され得る。図1Aは、102、104などの頂点を有する例示的なグラフを示す。頂点102、104は、エッジ106などのエッジを介して連結され得る。MIS問題のコンピューター的タスクは、最大独立集合(MIS)と呼ばれる最大のかかる集合を見出すことである。図1Aのグラフに示されるように、最大独立集合は、102などの黒の頂点を介して示され、これらのどれも連結されていない。図1Aの例において、最大独立集合のサイズは、6である。MISのサイズが任意のグラフGについての所定の整数aより大きいかどうかを決定することは、周知のNP-完全問題（NP-complete problem）である。さらに、MISのサイズを近似することでさえ、NP-困難問題（NP-hard problem）である。いくつかの態様において、MIS問題はまた、最大クリーク問題および最小頂点被覆問題と同等である。従って、MIS問題に対する解は、対応する最大クリーク問題および最小頂点被覆問題に対する解を構成する。
【００４９】
理論に拘束されることなく、図1Aの態様は、単位円(「UD」)グラフと言われ得る。UDグラフは、頂点が2D面に配置され、それらの対の距離が単位長rよりも小さい場合連結される幾何学的グラフである。換言すれば、UDグラフは、互いから距離r以内の任意の２つの頂点がエッジにより連結される、例えば、頂点102、104がエッジ106を介して連結されるグラフである。頂点108は、頂点102、104から遠すぎてエッジを用いてそれと連結できない。UDグラフ上のMIS問題(UD-MIS)は、なおNP-完全であり、種々の工業分野における例えば、ワイヤレスネットワーク設計からマップラべリング（map labelling）までにわたる実際の状況を見出すために使用され得る。
【００５０】
いくつかの態様において、MIS問題は、スピン-1/2と各頂点
【数５】
2021536610.tif 000011
を結びつけることにより、エネルギー最小化問題として定式化され得る。図1Aに示されるもののような頂点は、経時的に変化するラビ周波数Ωおよび離調Δを有するもの(図1Dおよび1Eに示される)などの駆動シーケンスの後に、各キュービットの状態|1>がエネルギー的に好まれ、近くの頂点もまた状態|1>にある場合は別であり、この場合、１つの頂点が状態|0>に遷移することがエネルギー的に好まれるように調製され得る。理論に限定されることなく、かかる系のハミルトニアン(「HP」)は、以下のように表され得る:
【数６】
2021536610.tif 000012
式中、スピン-1/2系は、状態|0>および|1>を各頂点に割り当て、nv=|1>υ<1|であり、Δは、スピン上の離調であり、Uは、エッジ(
【数７】
2021536610.tif 000013
)により連結される２つのスピン(
【数８】
2021536610.tif 000014
)の両方が状態|1>にある場合のエネルギーペナルティーである。最初に、全ての頂点を、|0>状態に調製し得る。駆動により、少なくともいくつかの頂点を|1>状態に遷移させる。Δ>0について、HPは、キュービットが状態
【数８−１】
2021536610.tif 000015
にあることを好む。しかし、U>Δである場合、２つのキュービット、uおよびvが同時に状態
【数８−２】
2021536610.tif 000016
にあることは、これらがエッジ
【数９】
2021536610.tif 000017
により連結される場合、エネルギー的に好ましくない。従って、HPの各基底状態は、最大独立集合中の頂点に対応するキュービットが状態
【数９−１】
2021536610.tif 000018
にあり、全ての他のキュービットが状態
【数９−２】
2021536610.tif 000019
にある構成を示す。
【００５１】
図1Cは、いくつかの態様による弱い駆動Ω<<ΔおよびΔ>0の極限における２つの隣接する頂点の間の原子間相互作用ポテンシャルを示すグラフである。経時的に離調およびラビ周波数を変更することにより、系を初期状態から最終状態へと変更する量子進展が生じ得、該最終状態は、エンコードされた問題に対する解(または１つ以上の近似解)を含み得る。上記したように、かかる条件下では、rB(リュードベリブロッケード半径)よりも近いキュービットについて、キュービットの１つが|0>状態にとどまることがエネルギー的に好ましい。例えば、U>Δ>0である場合、ハミルトニアンHPは、スピンの対がエッジにより連結され(即ち、リュードベリ半径以内)ない限り、各スピンが状態|1(にあることをエネルギー的に好む。従って、ハミルトニアンHPの基底状態において、MIS中の頂点のみが、状態|1(にある。かかる状態は、MIS-状態と言われ得、HPは、MIS-ハミルトニアンと言われ得る。いくつかの態様において、MISのNP-完全決定問題は、HPの基底状態エネルギーが-αΔより低いかどうかを決定することになる。
【００５２】
いくつかの態様において、量子アニーリングアルゴリズム(「QAA」)は、初期状態から最終状態へと量子状態を進展させるために使用され得、該最終状態は、最適化問題に対する解をエンコードする。例えば、単純なQAAは、横磁場（transverse field）
【数１０】
2021536610.tif 000020
（式中、σx=|0><1|+|1><0|）を追加することにより実行され得、該横磁場は、異なるスピン配置間での量子トンネル現象（quantum tunneling）を誘導する。図1Bは、いくつかの態様によるスピン状態間の遷移を示す。例えば、ラビ周波数Ωと標識された矢印は、例えば、
【数１１】
2021536610.tif 000021
を有するレーザービームにより制御されるスピン状態|0>および|1>の間の遷移を記載する。離調Δ<0である場合、ハミルトニアンHPの基底状態は、全てのキュービットが|0>状態にあるトリビアルな状態である。離調Δ>0である場合、HPの基底状態は、状態|1>にあるキュービットがMISを形成するMIS状態である。例えば図1Eおよび1Dのそれぞれに示されるように時間依存的様式でΩおよびΔをゆっくり変更することにより、全てのキュービットが|0>にあるトリビアルな基底状態(Δ<0、Ω=0)は、MISをエンコードする最終状態(Δ>0、Ω=0)に断熱的に連結され得、キュービットは最適化問題に対する解に残る。一般的に、かかる手順は、本開示を通じてより詳細に議論されるように、消滅する（vanishing）エネルギーギャップにわたる遷移を含み得ることに留意のこと。シミュレーションの例示的かつ非限定的な態様は、表題「ランダムUD-MISのための量子アニーリング」の節により詳細に下記される。
【００５３】
いくつかの態様において、MIS問題は、個々の原子間のリュードベリ相互作用を使用して実行され得る。例えば、PCT/US18/42080により詳細に議論されるように、図1Aに示されるもののようなグラフは、２準位キュービットを使用して実行され得、該キュービットの状態は、いくつかの態様により図1Bに示される。光ピンセットを使用して、原子(キュービット)を、１次元、２次元および３次元でさえの十分にプログラム可能なアレイに個々にかつ決定論的に配置し得る。かかる系は、いわゆるリュードベリブロッケード機構を介して相互作用する個々に捕捉され均一に励起された中性原子を使用し得る。各原子は、内部基底状態|0>および高度に励起された長持ちするリュードベリ状態|1>を有するキュービット
【数１２】
2021536610.tif 000022
を実現し、これは、外部のレーザー場によりコヒーレントに操作され得る。２つの原子の両方がこのリュードベリ状態にあり、リュードベリブロッケード半径以内にある場合、該２つの原子は、強いファンデルワールス相互作用を介して相互作用し、これは、エネルギー的に好ましくない。これは、以下により詳細に説明するように、頂点としてキュービットを使用しリュードベリ半径により設定される円サイズを使用してUD-MIS問題をエンコードすることを可能にし得る。図9は、UD-MIS問題に対する例示的な解を示し、ここで、いくつかの態様により、いくつかのキュービット904は、内部基底状態|0>に見いだされ、他のキュービット902は、長持ちするリュードベリ状態|1>に見いだされる。
【００５４】
理論に限定されることなく、かかる系の態様の進展を支配するハミルトニアンは、以下のように表され得る:
【数１３】
2021536610.tif 000023
式中、
【数１４】
2021536610.tif 000024
は、キュービットvの位置
【数１５】
2021536610.tif 000025
でのラビ周波数およびレーザー離調である。個々の操作が可能であるが、かかる系はまた、例えば、
【数１６】
2021536610.tif 000026
である均一な駆動レーザーを用いて実行され得る。演算子
【数１７】
2021536610.tif 000027
は、キュービットvがリュードベリ状態にある場合に、キュービットvのコヒーレントなスピンフリップおよび
【数１８】
2021536610.tif 000028
計数（count）を生じ得る。いくつかの態様において、等方性リュードベリ状態について、原子間相互作用強度は、相対的原子距離xにのみ依存し、
【数１９】
2021536610.tif 000029
により与えられ、式中、Cは定数である。短い距離での強い相互作用は、図1Cに示されるように、２つのキュービットが、リュードベリブロッケード半径
【数２０】
2021536610.tif 000030
以内にある場合に、同時に状態|1>にあることをエネルギー的に妨げ、いくつかの態様によるいわゆるブロッケード機構を生じる。これは、リュードベリハミルトニアンHRydとUD-MIS問題に対する解の間の関連を提供し得る。換言すれば、リュードベリブロッケードは、リュードベリ半径(rB)以内の近接するキュービットをエネルギー的に好ましくするが、両方をリュードベリ状態|1>にはさせない。UDグラフにおいてと同様に、この構成のいくつかの態様において、キュービットは、リュードベリブロッケード半径より短い距離だけ分離された場合、両方が状態|1>に見出され得ない。
【００５５】
MIS-ハミルトニアンHPは、古典的な極限Ωv=0において、リュードベリハミルトニアンHRydといくつかの特徴を共有する。いくつかの態様において、例えば、任意のグラフがHPに許容される場合、主な相違点は、対の相互作用の達成可能な連結性（connectivity）にある。リュードベリブロッケード機構に最も密接に関連する特別な限られた種類のグラフを考慮し得る。これらのいわゆる単位円(UD)グラフは、頂点が面における座標に割り当てられ得、単位距離r以内にある頂点の対のみがエッジにより連結される場合、上記されるように構築される。従って、単位距離rは、HRydにおけるリュードベリブロッケード半径rBと類似の役割を果たす。換言すれば、キュービットの空間的近接は、UD-MIS問題中のエッジをエンコードするために使用される。MISは、かかる単位円グラフに制限されている場合でさえ、NP-完全である。本開示の態様は2D問題およびキュービットの2D配置を議論するが、当業者は、本開示に基づいて、本明細書に記載される問題エンコードの局面が、１次元構造または３次元構造などの他の空間的構造に適用可能であることを理解する。
【００５６】
理論に拘束されることなく、重み付き最大独立集合問題は、MIS問題であり、ここで、各頂点vが重み
【数２１】
2021536610.tif 000031
を有し、これは、等式1の同種の重みΔと置き換えたものである。重み付き最大独立集合問題は、最大の重みの合計和を有する独立集合を見出すことである。いくつかの態様実行において、これらの重み
【数２２】
2021536610.tif 000032
は、対応する光シフトを各キュービットに適用することにより、エンコードされ得る。いくつかの態様において、これらの光シフトは、共鳴から離れた（off-resonant）レーザービームまたは空間的光変調器により作製されるACシュタルクシフトであり得る。
【００５７】
例示的なキュービット配置および離調
リュードベリ相互作用は、リュードベリ半径を越えると有意に減衰するが、図1Aに示すように、102および108などの遠いキュービットの間になお長距離の相互作用テール（interaction tail）がある。相互作用テールは、単独でも集合でも、図1Dおよび1Eに示すものなどの駆動の後に、系が解にあることが見出される可能性を低減し得る。従って、図1Aに示すものなどの実行が、常に完璧にNP-完全MIS問題をエンコードするわけではない場合がある。さらに、図1Aに関して記載される技術を使用してエンコードされ得るNP-完全問題の範囲は、単位円に関連するものに限定される。
【００５８】
いくつかの態様において、これらの問題の１つ以上は、２次元における原子位置およびレーザーパラメーターを、リュードベリハミルトニアンHRydの低エネルギー領域が、最大次数3を有する平面グラフ上で(NP-完全)MIS-ハミルトニアンHPに単純化されるように、選択することにより解かれ得る。本開示のいくつかの局面において、反強磁性秩序は、リュードベリブロッケード機構のために、正の離調においてアンシラリーキュービットの(準)1Dスピン鎖の基底状態にあることが見出され得る。かかる構成は、ブロッケード束縛を遠い頂点キュービットの間で効果的に送り得る。本開示の他の局面において、離調パターン[Δv]は、基底状態スピン構成を変えることなく、所望されない長距離の相互作用の効果を排除するために導入され得る。いくつかの態様は、NP-完全問題の捕捉された中性原子のアレイの基底状態における効率的なエンコードを可能にする。理論に拘束されることなく、かかる態様における2Dアレイ中のリュードベリ相互作用原子の基底状態エネルギーは、NP-困難(およびΩv=0である場合、NP-完全)である。
【００５９】
アンシラリーキュービットを用いる例示的なキュービット配置
図2Aおよび2Bに関して記載されるように、NP-完全問題は、「頂点」キュービットの間でエッジを実行する（implement）「アンシラリー」キュービットまたは頂点を用いてエンコードされ得、ここで、いくつかの態様により、頂点キュービットは、3の最大次数を有する。例えば、図2Aに示されるように、複数の頂点キュービット202、204、212、214、および216は、グラフにおいて配置され得る。頂点キュービット202および204などの頂点キュービットの対の間のエッジは、偶数のアンシラリーキュービット206を使用して実行され得、それらの各々は、単位長rだけ分離される。この技術は、最大次数3を有する平面グリッドグラフをUDグラフに埋め込む（embed）ために使用され得る。例えば、最大次数3を有する平面グラフは、いくつかの態様により図2Aに示されるように、偶数のアンシラリー頂点を各エッジに沿って導入することにより、グリッド(グリッド単位gを有する)
【数２３】
2021536610.tif 000033
に効率的に埋め込まれ得、UDグラフGに変換され得る。UD半径
【数２４】
2021536610.tif 000034
は、各エッジに沿ったアンシラリー頂点の直線密度（linear density）に比例したパラメーターkにより決定され得る。いくつかの態様によると、各頂点を形成する相互作用がほぼ等しい強さであることを確実にするにするために、任意の所定のエッジに沿ってほぼ同じ密度のアンシラリーキュービットを実行することが望ましい。
【００６０】
頂点キュービット202および204の例において、頂点キュービット202は、最も左のアンシラリーキュービット206と、まるでそれが頂点キュービット204であるかのように相互作用し得、頂点キュービット204は、最も右のアンシラリーキュービット206と、まるでそれが頂点キュービット202であるかのように相互作用し得る。この様式において、エッジは、リュードベリ半径の外側の頂点キュービットの間でかつ単位円グラフとして純粋に実行できない様式で実行され得る。さらに、図1Aに関して議論したもののような単位円グラフにおいて、いくつかの頂点をエッジにより連結される同じ距離だけ分離させ(例えば、頂点キュービット202、204)、一方で、同じ距離だけ分離される他の頂点をエッジにより連結しない(例えば、頂点キュービット212、214)ことは可能ではないが、かかる構成は、本開示に記載されるアンシラリー頂点を使用して実現され得る。
【００６１】
例示的な離調パターン
いくつかの態様において、MISグラフが図2Aに示されるように実行される場合、リュードベリ相互作用のテールは、コーナーおよびジャンクションの近傍を除いて、キュービット間の相互作用に影響を及ぼさず、そこでは、アンシラリーキュービットのアレイは、ある角度をなす。頂点キュービット202は、例示的なコーナーであり、頂点キュービット216は、例示的なジャンクションである。図2Bに関してより詳細に記載されるように、キュービットの駆動の間の離調パターンは、相互作用テールの効果を相殺するために、これらの構造の周りで調整され得る。
【００６２】
図2Bは、いくつかの態様によるかかる離調パターンの例を示す。図2Bの挿入図は、図2A中の頂点キュービット216などの3の次数を有する頂点キュービット216を示し、これは、第１の方向において、近接するアンシラリーキュービット222、224であり、第２の方向において、232、234であり、第３の方向において、242、244である。図2Bは、垂直(水平)方向に沿って離調Δcを有する頂点キュービットから距離jにあるキュービットの離調
【数２５】
2021536610.tif 000035
をプロットする。図2Bに示されるように、離調
【数２６】
2021536610.tif 000036
は、各アンシラリーキュービット(例えば、PCT/US18/42080に記載される個々のアドレシング（addressing）技術を使用して)個々にアドレシングされ得、相互作用テールの効果を排除する様式で設定され得る。例えば、離調
【数２７】
2021536610.tif 000037
は、範囲
【数２８】
2021536610.tif 000038
かつ十分に大きなkで選択され得る。いくつかの態様において、離調は、この範囲内で任意に選択され得る。かかる離調は、長距離の相互作用の所望されない効果を相殺し得る。かかる条件下では、HRydの基底状態において(Ωv=0で)、アンシラリーキュービットの各アレイは、|0>と|1>の間で交替する(せいぜい１つのドメイン壁を有する)秩序だった構成にある。これは、Ωv=0についてのHRyd(2)の基底状態が、Gに対するMISハミルトニアン(1)の基底状態と同時に生じることを確実にする。個々のアンシラリーキュービットについての離調のこの摂動は、全体的な（global）駆動パターンの複数の異なる型(本開示を通じてより詳細に記載されるQAAおよびQAOAなど)を用いて、MISに対する解が何であるかの前もっての知識なしに、実施され得る。さらに、G上のMISのサイズは、アンシラリー頂点の数の半分まで、
【数２９】
2021536610.tif 000039
上のMISのサイズと同一であるので、MIS問題がアンシラリー頂点を使用して実行される場合、リュードベリハミルトニアン(2)の基底状態を見出すことはなおNP-困難である。
【００６３】
いくつかの態様において、実行は、単位円グラフを超えて、より一般的なグラフまで拡張され得る。かかる実行は、「ストロボ的」実行と言われ得、これは、図2Aに関して記載されるアンシラリーキュービットを用いずに実行される任意のグラフを含み得る。例えば、いくつかの態様において、種々の光学的技術が、これらの系にアドレシングされ得る問題の種類を拡張するために使用され得る。１つの例示的なアプローチは、キュービットを基底-リュードベリキュービットエンコードではなく超微細基底状態（hyperfine ground state）にエンコードすること、およびリュードベリSおよびP状態などの種々の種類をリュードベリ状態へと選択的に励起すること(例えば、キュービットの個々のアドレシングを用いて)を含む。この例において、異なるパリティーSおよびPを有するリュードベリ状態間の強く長距離の双極性相互作用は、その複数の隣接体（neighbor）により制御される単一キュービットの回転を効率的に実現するために使用され得る。例えば、リュードベリSおよびP状態は、多キュービット-制御回転を実現するために使用され得る。回転(またはキュービットフリップ)は、量子状態を初期状態から最終MIS-状態に進展させるために使用され得る。これらの相互作用を制御することにより、例えば、２つのキュービットが、エッジにより連結される場合に、両方ともリュードベリ状態にあるように進展しないことを確実にすることにより、系の進展が独立集合の束縛を破らないことを確実にすることが可能である。いくつかの例において、所定の(中央)キュービットの全ての隣接体は、状態
【数３０】
2021536610.tif 000040
からS-状態に選択的に励起され得る。その後、中央キュービットの２つの超微細状態の間とリュードベリP-状態における中間段階との２段階遷移は、多キュービット-制御回転を実行し得る。トロタライズド（Trotterized）時間進展(例えば、全ハミルトニアン進展を小さな不連続な段階に分割すること)と合わせると、これらの技術は、UDグラフを超えるための手段を提供し、任意のグラフ上のMIS問題に対する種々の量子最適化アルゴリズムを実行する。いくつかの態様において、この技術は、図2Aに描かれるものよりも広い範囲のグラフを含み得る任意のグラフを実行し得る。いくつかの態様において、「ストロボ的実行」(キュービットのリュードベリ状態への選択的かつ連続的な励起)は、多キュービット-制御回転の実行を可能にする。この選択的な励起は、グラフ構造に従った制御された回転を容易にし得、該グラフ構造は、単位円幾何構造に必ずしも限定されない。
【００６４】
例示的な古典的および量子アルゴリズムの比較
いくつかの態様によると、量子コンピューター計算を用いて解を見出すことが標準的なコンピューター計算アプローチに対して大きな改善を示すUD-MIS問題の型を同定することが望ましい。古典的および量子アルゴリズムの両方の数値的シミュレーションは、量子アルゴリズムがUD-MISに十分に適合する型（regime）および系サイズを同定するために使用され得る。１つの態様において、N個の頂点を、ランダムに密度ρで、サイズL×Lの2Dボックス（ここで、
【数３１】
2021536610.tif 000041
およびUD半径r=1）中に配置することにより構築されるランダムUDグラフ上のMISが考察され得る。この問題の困難さは、頂点密度に依存し得る:密度が、浸透閾域（percolation threshold）
【数３２】
2021536610.tif 000042
未満である場合、グラフは、連結されない有限のクラスターに分解され、効率的な多項式時間アルゴリズム（polynomial time algorithm）を可能にする。反対の極限において、例えば、密度が非常に大きい、
【数３３】
2021536610.tif 000043
である場合、問題は、既知の最良のパッキング比が
【数３４】
2021536610.tif 000044
である(連続的な)2D面における円の最密充填（closest packing）に本質的になる。
【００６５】
図3A〜3Bは、いくつかの態様による例示的な古典的な最適化アルゴリズムの性能を示す。特に、それは、いくつかの密度領域において、古典的なアルゴリズムが最適化問題を解くことが困難であり、正確に解くために指数関数的な時間を必要とすることを示す。これらの型において、量子利点（quantum advantage）は、他の型よりも有益である。図4A〜4Dは、いくつかの態様による量子アルゴリズム(QAAおよびQAOAの両方)の対応する性能を示す。スモール-サイズシミュレーションを用いた実行によると、図4A〜4Dは、QAOAが問題を迅速に解き得、QAAに勝り得ることを示す。図4A〜4Dは、いくつかの態様による特定の型についての量子利点を示す。より具体的には、図3Aは、古典的な最適化アルゴリズムの性能を示すグラフであり、いくつかの態様による分岐限定アルゴリズムに焦点を合わせている。CPU時間においてMISを見出すためのメジアン運転時間Trunは、所定の数(垂直軸)および密度(水平軸)でビン（bin）について示される。図3Aに示される例示的な統計は、データ点あたり50のグラフから得られた。破線は、上記した浸透閾域を示し、これは、この場合において、
【数３５】
2021536610.tif 000045
であることが示される。図3Aに見られ得るように、Nおよびρのパラメーター空間の特定の型において、問題は、例えば、運転時間が大きいので、古典的な最適化アルゴリズムが解くのは困難である。
【００６６】
図3Bは、いくつかの態様によるNの関数として運転時間Trunを示すグラフである。
【数３６】
2021536610.tif 000046
について多項式スケーリング（polynomial scaling）があるが、中間密度ρ〜７において、運転時間は、N〜150頂点を超えると、系サイズと指数関数的な依存性を示す。この指数関数的な依存性は、任意の所定の数Nについて最悪の場合および典型的な例の両方において見られ得る。ρ〜7において、古典的なアルゴリズムは、しばしば、Odysseyコンピューター計算クラスター(ハーバード大学により運営される)の単一のノード（node）において、24時間のCPU時間以内に
【数３７】
2021536610.tif 000047
について解を見出すことができなかったことに留意のこと。より一般的な非-UDグラフについて、古典的なアルゴリズムのこの制限は、
【数３８】
2021536610.tif 000048
で観察される。比較のために、エッジ確率p=0.05を有するErdoes-Renyiグラフに対する性能もまた示され、類似した指数関数的な運転時間を示す。エラーバーは、100のグラフの中の5番目および95番目の百分位数値である。図3Bは、古典的なアルゴリズムが特定のサイズ(例えば、〜N=400)の問題を解くのに長時間 (例えば、24時間)かかり得ることを示す。これは、問題が古典的に解くにはトリビアルではないように、問題サイズを試験量子アルゴリズムに通知する。
【００６７】
図4Aおよび4Bは、いくつかの態様によるランダムUDグラフ上のMISに対する量子アルゴリズムの性能を示すグラフである。図4Aは、いくつかの態様による断熱的時間スケールTLZに関する量子断熱的アルゴリズムについての困難さの図であり、垂直軸上のNに対して水平軸上に密度ρをプロットしている。例えば、図4Aは、上記したMISアニーリングハミルトニアンHD+HPを用い、
【数３９】
2021536610.tif 000049
としてパラメーターを掃引（sweep）した断熱的QAAの数値的シミュレーションの結果を示す。
【００６８】
極限
【数４０】
2021536610.tif 000050
が観察され得、そこでは、動力学が独立集合部分空間に限られ、系サイズN〜40キュービットまでの数値的シミュレーションを可能にする。縞パターンに平行な傾斜した破線は、最適な円パッキングに対応する。十分に連結された領域は、トリビアルに
【数４１】
2021536610.tif 000051
を有する。断熱性に必要とされるLandau-Zener時間スケールTLZは、数値的結果を、基底状態確率
【数４２】
2021536610.tif 000052
の予想される長時間挙動にフィッティングすることにより抽出され得る。例えば、大きなTについてPMISをフィッティングさせTLZを抽出することが可能である。図4Aは、浸透閾域ρ=1.436での、問題を解くのに容易な型からそうではない型までの明確な遷移を示す。高い密度で、MISのサイズは、最適パッキング問題に対する関係のために、
【数４３】
2021536610.tif 000053
により決定され得る。これは、また、図4A中の縞パターンにより見られ得るTLZに反映される。指数関数的なヒルベルト空間サイズは、数値的シミュレーションを制限し、古典的なアルゴリズムのスケーリングとの決定的な比較を困難を超えるものにする。いくつかの実行において、有限のコヒーレンス時間は、量子断熱的経路に沿った基底状態と第１励起状態の間のエネルギーギャップに対応する最小エネルギーギャップ
【数４４】
2021536610.tif 000054
の指数関数的なスケーリングを伴う断熱的アルゴリズムの性能をさらに制限し得る。
【００６９】
いくつかのアプローチが、これらの潜在的な制限の克服を試みるために実行され得る。かかるアプローチは、ギャップを利用できるようにする（open up）ためのヒューリスティックス、QAAにおける非断熱（diabatic）(非断熱的)遷移の使用、および下記で検討されるQAOAなどの変動性量子アルゴリズムを含む。図4Bは、いくつかの態様によるシミュレートされた非断熱的QAAについてのPMISであるMISを見出す確率を示すグラフである。いくつかの態様において、TLZおよびPMISは、類似した情報を運び得、大きなT(断熱的な型において)について、
【数４５】
2021536610.tif 000055
により関係付けられる。図4Aは、例示的な断熱的な型(大きなT)を示し、図4Bは、例示的な非断熱的な型(短いT)を示す。例えば、図4Bは、単一のTについての単一掃引(図4Aに示されるように、合計時間Tについての複数回の掃引ではない)を示し、これは、短いアニーリング時間
【数４６】
2021536610.tif 000056
での等式（Eq.）(3)におけるプロフィール（profile）を有する例示的な短時間極限(例えば、非断熱的)である。図4Bは、MIS状態との実質的な重複が、進展時間
【数４７】
2021536610.tif 000057
で得られ得、成功確率は、断熱的困難さの図に定性的に類似することを示す。これらの結果は、非断熱的アニーリングが、特に、最小スペクトルギャップ
【数４８】
2021536610.tif 000058
が小さい場合に有利であり得るという観察と一致する。いくつかの態様において、ギャップが小さい場合(他のエネルギースケールと比べて)、量子断熱的アルゴリズムを走らせるために長いコヒーレンス時間(例えば、
【数４９】
2021536610.tif 000059
）が必要とされ得る。
【００７０】
本開示を通じて記載されるように、ファンデルワールス相互作用を介して相互作用するスピンの多体問題とコンピューター的複雑性理論の直接の関連を利用することが可能である。かかるスピンの位置に対する個々の制御により、NP-完全最適化問題がかかる量子系に直接エンコードされる。この結果は、3の最大次数を有する平面グラフ上のMISからの簡略化から得られ得る。中性原子を捕捉および操作するための技術と組み合わせての本開示に記載される技術に基づく量子オプティマイザー（quantum optimizers）は、NP-困難な最適化問題を、従来のコンピューター計算技術に対する改善として扱い得る。
【００７１】
例示的な量子アルゴリズム
上記で議論したように、上記した「アンシラリー」キュービット技術を使用しようとしまいといずれにせよ、量子系の位置を使用して組合せ問題をエンコードした後、次の段階は、組合せ問題に対する解である基底状態を生成する様式で、系を進展させることである。いくつかの例は、QAAおよびQAOAを含む。
【００７２】
QAOA
いくつかの態様において、QAOAは、本開示に記載されるもののような量子最適化問題に適用され得る。例えば、(レベルpの)QAOAは、p共鳴パルスのシーケンスを、最初に調製される状態における異なる（varying）持続時間tkおよび光学的位相φkの全てのキュービット(または本開示により詳細に記載されるように、特定のキュービットに対するいくつかの離調およびエネルギー調整を有する)に適用することからなり得る。これは、変動性波動関数
【数５０】
2021536610.tif 000060
を生じ得る。理論に拘束されることなく、本開示は、いくつかのさらなるまたは代替的な最適化パラメーター(γ, β)を記載し、これは、いくつかの態様において、以下の表題MISに対するQAOAの節により詳細に記載されるように、持続時間tkおよび光学的位相φkに関連し得る。
【００７３】
得られた量子状態は、コンピューターベースで測定され得、次いで、最適化に使用され得る。例えば、変動性パラメーターtkおよびφkは、この量子状態における
【数５１】
2021536610.tif 000061
の測定からの古典的なフィードバックループにおいて最適化され得る。この最適化の例は、以下により詳細に記載される。
【００７４】
QAOAの性能は、選択された古典的な最適化ルーチンに一部依存する。かかる技術の例示的な実行を説明する前に、いくつかの態様において、古典的なコンピューター計算技術に対する改善を示すQAOAの性能を示し得る。例えば、図4Cは、例示的なグラフの例G0(N=32および独立集合空間次元dimIS=17734、ρ=2.4および
【数５２】
2021536610.tif 000062
)において、最適化QAOAと量子 アニーリングを比較し、該例について、いくつかの態様によると、断熱的時間スケールは、およそ
【数５３】
2021536610.tif 000063
であると観測され得る。図4Cに示されるように、QAOAは、デプス（depth）
【数５４】
2021536610.tif 000064
(即ち、40未満の共鳴パルス)でO(1)成功確率を達成し、それにより、有意により短い進展時間
【数５５】
2021536610.tif 000065
を示し、例外的に良好な変動性状態を示し、これは、アルゴリズムがエンコードされた問題を解くのに効果的であることを示し得る。そして、以下でより詳細に議論されるが、これは、また、大きな系に対するQAOAの実行に反映される。しかし、通常の数値解析（numerical analytics）を使用して評価され得る例示的な系サイズについて、測定射影ノイズと関連する変動は、MISサイズが、より小さなpであっても、古典的な最適化ルーチンの間に容易に見出され得ることを意味し得る。いくつかの態様において、この「測定射影ノイズ」は、測定中のノイズではない。例えば、各測定は、コンフィギュレーション空間（configuration space）を生じ得る。オブザーバブルの期待値を評価し、QAOA最適化を実施するために、測定は、複数回繰り返される必要がある。小さな系サイズについて、測定結果は、多くの最適化の前にMISをヒット（hit）し得、なぜなら、各測定はMISを生じる高い確率を有するからである。
【００７５】
図4Dは、いくつかの態様によるグラフG0に対する種々の量子アルゴリズムのシミュレートされた性能を示す。例えば、図4Dは、G0に対するシミュレートされたQAOAおよびQAAについてのM測定後に見出された真のMISと最大の独立集合の間の平均差を示す。図4Dに示されるように、ヒューリスティックアンサツ（ansatz）法およびランダム推測法を用いたQAOAの両方を示す。かかる結果を得るために、QAOAについてのシミュレーションを、射影測定からのサンプリングを含むモンテカルロシミュレーション技術を用いて実施した。最大の測定された独立集合のサイズを、測定数の関数としてプロットする(モンテカルロ軌跡（trajectory）にわたって平均した)。tkおよびφkについてヒューリスティック アンサツを適切に選択することにより、QAOA(p=3で)により、〜102〜103測定後に既にMISが見出される。これは、古典的な最適化ルーチンの一部として、
【数５６】
2021536610.tif 000066
を正確に評価するために必要な測定数と同等である。この性能は、非断熱的アニーリング時間T=1/Ω0、10/Ω0、100/Ω0について上記等式3により記載される掃引(およびΔ0/Ω0=6)を用いたQAAの繰り返しのラン（run）と比較され得る。この小さな系サイズについて、QAOAは、アニーリング時間T〜10/Ω0での非断熱的QAAとして同様に実施される。
【００７６】
上記で説明したように、QAOAは、変動性パラメーターの組に従って、量子状態を調製する量子処理装置である。測定出力 (各キュービットの測定されたキュービット状態
【数５７】
2021536610.tif 000067
など)を使用し、次いで、パラメーターは、例えば、古典的なコンピューターを介して最適化され得、閉鎖ループ内の量子機械にフィードバックされ得る。QAOAにおいて、状態は、2p変動性パラメーターにより特定されるp-レベル回路により調製される。換言すれば、各パルスは、２つのパラメーター
【数５８】
2021536610.tif 000068
を有し、式中、kは1〜pである。最小の回路デプス(p=1)であっても、QAOAは、トリビアルでない証明可能な性能利益(例えば、単純な古典的なアルゴリズムよりも良好な性能)を有するが、古典的なコンピューターによっては効率的にシミュレートされ得ない。
【００７７】
しかし、
【数５９】
2021536610.tif 000069
であるQAOAについては、本当にほとんどわかっていない。１つの障害は、非凸状高次元パラメーター分野（landscape）における効率的な最適化が困難であることにある。パラメーター最適化を実施するための建設的なアプローチがなければ、ハイブリッドアルゴリズムの任意の潜在的な利点は失われ得る。さらに、QAOAは、それが、断熱的量子アニーリング(即ち、断熱的アルゴリズム)を近似する能力のために
【数６０】
2021536610.tif 000070
の極限において成功することが示され得るが、
【数６１】
2021536610.tif 000071
の場合のその性能は、ほとんど調査されていない。
【００７８】
QAOAについての例示的なパラメーター最適化
本開示の局面は、QAOA変動性パラメーターを効率的に最適化するための技術を詳述する。いくつかの例において、キュービットの組が特定の配置にあると仮定すると、QAOAは、一連の操作をキュービットに適用することにより進行し、各操作は、少なくとも２つの変動性パラメーターを有する。キュービットの進展した状態が測定され、それは、変動性パラメーターを調整するために、最適化ルーチン(古典的なアルゴリズムなど)にフィードバックされる。次いで、プロセスは、キュービットの測定された状態がエンコードされた問題に対する解またはその近似であることが決定されるまで、キュービットに対して繰り返される。いくつかの態様において、古典的な最適化ルーチンのための技術が開示される。これらの技術は、既知の全体的な最適物（optimum）を典型的に生じ、性能に勝るために2O(p)回の腕ずくの最適化ランを一般的に必要とするという意味において、準最適である。本開示の局面は、また、かかる最適化技術を用いたQAOAの実行を開示し、例えば、例は、MaxCut問題を解くために古典的なアルゴリズムに対して潜在的な利点を示す数百のリュードベリ-相互作用をする原子の2D物理的アレイを含む。
【００７９】
上記で議論したように、多くの実世界の問題は、組合せ最適化問題として表現され（frame）得る。いくつかの態様において、N-ビットバイナリー弦（binary string）
【数６２】
2021536610.tif 000072
上で一般的に画定され得る問題があり、ここで、目標は、所定の古典的な目的関数（objective function）
【数６３】
2021536610.tif 000073
を最大化する弦（string）を決定することである。近似最適化アルゴリズムは、所望の近似比
【数６４】
2021536610.tif 000074
を達成する弦
【数６５】
2021536610.tif 000075
を見出すことを意図する。
【００８０】
量子近似最適化アルゴリズム(QAOA)は、これらの組合せ最適化問題に取り組み得る量子アルゴリズムである。問題をエンコードするために、古典的な目的関数は、各バイナリー変数ziを量子スピン
【数６６】
2021536610.tif 000076
に昇格（promote）させることにより、量子問題ハミルトニアンに転換され得る：
【数６７】
2021536610.tif 000077
【００８１】
図14Aは、いくつかの態様による例示的なQAOAアルゴリズムのフロー図である。図14Aに示されるように、量子回路は、入力
【数６８】
2021536610.tif 000078
を取り込み、
【数６９】
2021536610.tif 000079
のp-レベルの組(1440, . . .,1450)を交互に適用する。いくつかの態様において、
【数７０】
2021536610.tif 000080
は、系の進展の2つの異なる型を示し、これらは、レーザーパルスにより物理的に誘導され得る。パラメーター
【数７１】
2021536610.tif 000081
は、各進展がどれほど長く生じるかを定量し得る。これらのレベルの各々は、変動性パラメーター1480に適用され、該変動性パラメーター1480は、p-レベルの組の各々の間で異なり得る。次いで、出力は、1460で関数
【数７２】
2021536610.tif 000082
に関して測定される。いくつかの態様において、出力は、スピン状態の重ね合わせである。測定された場合、系は、これらのスピン状態の１つに崩壊し、その結果、測定結果は、単一のスピン構成であり得る。いくつかの態様において、期待値
【数７３】
2021536610.tif 000083
は、スピン構成の関数であるが、この構成においてハミルトニアンHCを評価した場合に到達されかつ複数の実験的ランについて平均した数であり、次いで、該数は、オプティマイザー1470(古典的な最適化関数であり得る)に供給され、該オプティマイザー1470は、
【数７４】
2021536610.tif 000084
を最大化する組において各レベル1440, . . ., 1450についてパラメーター
【数７５】
2021536610.tif 000085
を計算する。次いで、これらのパラメーター
【数７６】
2021536610.tif 000086
は、次のイテレーション(例えば、フィードバックループとして)のために変動性パラメーター1480として提供される。変動性パラメーター1480は、pレベルの組における各レベル1440, . . .,1450で異なり得ることに留意のこと。次いで、入力
【数７７】
2021536610.tif 000087
は、再度提供され、プロセスは繰り返される。いくつかの態様において、複数のイテレーションの後、測定1460は、エンコードされた問題に対する解とみなされ得る。
【００８２】
図14Aに記載されるp-レベルQAOAについて、量子処理装置は、状態
【数７８】
2021536610.tif 000088
に初期化され得る。問題ハミルトニアンHC(1442, 1452)および混合ハミルトニアン
【数７９】
2021536610.tif 000089
は、制御された持続時間を交互に(p回)適用され、変動性波動関数:
【数８０】
2021536610.tif 000090
を生じ、これは、2p個のパラメーターγiおよびβi
【数８１】
2021536610.tif 000091
(pレベルの組における各レベルについて１つ)によりパラメーター化される。この変動性状態における期待値HCは、以下：
【数８２】
2021536610.tif 000092
のように決定され得、これは、コンピューターベースにおける量子系の繰り返しの測定1460および平均をとることにより同定され得る(例えば、現存する測定技術を使用して測定され得る２つの直交するスピン構成
【数８３】
2021536610.tif 000093
を用いる)。
【００８３】
一旦、測定1460が実施されると、結果(例えば、多くのHCにわたって平均をとることにより決定される計算された
【数８４】
2021536610.tif 000094
)は、オプティマイザー1470、例えば、古典的なコンピューターにフィードバックされ得、
【数８５】
2021536610.tif 000095
【００８４】
いくつかの態様においてQAOAの性能は、近似比:
【数８６】
2021536610.tif 000096
に基づいてベンチマークテストされ得る。
【００８５】
いくつかの態様において、rは、QAOAにより提供される解がどれほど良好かを特徴づける。r値が高いほど、解は良好である。
【００８６】
いくつかの態様において、理論に拘束されることなく、このQAOAフレームワークは、一般的な組合せ最適化問題に適用され得る。１つの例において、MaxCutと呼ばれる原型的な問題が考慮され得る。
【００８７】
図14Bは、いくつかの態様によるMaxCut問題の例を示す。MaxCut問題は、入力グラフG=(V, E)について記載され得る。ここで、V=[1, 2, . . . , N]は、頂点の組(アップスピンおよびダウンスピン1492A、1492B、1492C、1494A、1494Bとして示される)を示し、
【数８７】
2021536610.tif 000097
は、エッジの組(実線および点線を用いて示される)であり、式中、
【数８８】
2021536610.tif 000098
の重みである。例えば、２つのアップスピン1492A、1492Bを連結するエッジは、w13の重みを有する。MaxCutの目標は、以下の目的関数:
【数８９】
2021536610.tif 000099
を最大化することであり、ここで、エッジ
【数９０】
2021536610.tif 000100
は、スピン
【数９１】
2021536610.tif 000101
が逆整列した場合かつ場合のみに、重みwijと共に寄与する。例えば、曲がった破線は、整列したエッジw13およびw25を除いた逆整列したスピンの全てのエッジを通るカットを示す。
【００８８】
例示的な組合せ問題
本開示の態様はd-正則グラフ上のMaxCutを議論し、該グラフでは、全ての頂点は正確にd個の他の頂点に連結されるが、本開示に基づいて、当業者は、本明細書に記載されるQAOAの局面は、他の型のグラフ上のMaxCut問題、最大独立集合問題、および他のものなどであるがこれらに限定されない他の型の組合せ問題に適用可能であることを理解する。２つの型のd-正則MaxCutグラフが考慮される:(1)重み無しd-正則グラフ(udR)、ここで、全てのエッジは、等しい重み
【数９２】
2021536610.tif 000102
を有する;および(2)重み付きd-正則グラフ(wdR)、ここで、重み
【数９３】
2021536610.tif 000103
は、[0,1]からランダムに一律に（uniformly）選択される(他の態様において、区間（interval）[0,1]以外の他の重みが選択され得るが)。
【００８９】
全てのグラフに対するMaxCutについて
【数９４】
2021536610.tif 000104
または上記で議論する重み無し3正則グラフ(「u3R」)に限られる場合に
【数９５】
2021536610.tif 000105
の最小近似比を保証するアルゴリズムを設計することは、NP-困難である。
【００９０】
いくつかの態様によると、QAOAは、いくつかの利益をもたらす。特定の場合について、該QAOAは、p=1の場合に、保証された最小近似比を達成する。さらに、いくつかの合理的な複雑性-理論的仮定下で、QAOAは、p=1の場合でも任意の古典的なコンピューターによって効率的にシミュレートされ得ず、このことは、候補アルゴリズムを、「量子超越性（quantum supremacy）」、即ち、量子コンピューターが、従来のコンピューターにはできない計算を実施する能力に役立たせる。QAOAがその一例であり得る動的進展の方形パルス（square-pulse）(「バンバン（bang-bang）」)アンサツは、一定の量子コンピューター計算時間を仮定すると、最適であり得る。一般的に、QAOAの性能は、pが増大するにつれて改善し得、p→∞の場合にr→1を達成し、なぜなら、該QAOAの性能は、トロタリゼーション（Trotterization）を介して断熱的量子アニーリングを近似し得るからである。この単調さは、該QAOAを、その性能が運転時間の増大と共に低下し得る量子アニーリングよりも魅力的にする。
【００９１】
QAOAのいくつかの態様は単純な記述を有するが、現在p=1を超えて多くは理解されていない。u2Rグラフ上のMaxCutの例示的な問題(1D反強磁性リングなど)について、QAOAは、数値的証拠により決定された場合、
【数９６】
2021536610.tif 000106
を生じ得る。n項目（item）の間のグローバー非構造検索問題（unstructured search problem）などの別の例において、QAOAは、
【数９７】
2021536610.tif 000107
を有する標的状態を見出し得、定常因子内で最適クエリ複雑性（optimal query complexity）を達成し得る。いくつかの態様において、より一般的な問題について、単純な腕ずくのアプローチは、各パラメーターをO(ポリ(N))グリッド点へと不連続にする（discretizing）ことにより使用され得る。しかし、この技術は、レベルpでNO(p)の可能性の検査を必要とし、これにより、pが大きくなるにつれて、典型的なコンピューターを使用して計算することが非実用的になり得る。従って、本開示の態様は、
【数９８】
2021536610.tif 000108
について、QAOAパラメーターの効率的な最適化およびアルゴリズムの理解を扱う。
【００９２】
パラメーター最適化のための例示的なヒューリスティックス
本開示のいくつかの態様は、変動性パラメーターを最適化するための技術に関する。以下により詳細に記載されるように、最適パラメーターにおけるパターンは、最適変動性パラメーターをより迅速に同定するためのヒューリスティック最適化戦略を開発するために利用され得る。以下に記載されるいくつかの例において、レベルp QAOAについて同定されるパラメーターは、レベル-(p+1) QAOAについてパラメーターをより迅速に最適化するために使用され得、それにより、最適化のための良好な開始点を生じ得る。これらの技術は、腕ずくの技術に対する改善を提供する。いくつかの態様において、任意のq<pに関してレベル-q QAOAについて同定されるパラメーターは、レベルp QAOAについてパラメーターをより迅速に最適化するために使用され得る。さらに、いくつかの例は、u3Rおよびw3Rのランダムに生成された例を議論するが、類似した結果は、これらの技術を、u4Rおよびw4Rグラフ、ならびにランダムな重みを有する完全グラフ（complete graph）(またはシェリングトン-カークパトリックスピングラス問題に適用する場合に、見出され得る。これらの他の例示的なu3R、w3R、u4R、およびw4Rグラフは、正則グラフであり、これは、例えば、各頂点が同じ数の隣接体(それぞれ3または4)を有することを意味する。文字uおよびwは、ヒトが、それぞれ重み無しまたは重み付きグラフと考えるかどうかを言い得る。いくつかの態様において、これらのグラフは、試験サンプルとして有用である。本明細書において同定される最適パラメーターにおけるパターンは、準-最適解をO(poly(p))回効率的に見出し得る例示的なヒューリスティック戦略を開発するために使用される。
【００９３】
いくつかの態様において、対称性によるパラメーター空間内の縮退を排除することが可能である。例えば、一般的に、QAOAは、HBおよびHCの両方が実数値であるので、時間反転対称性
【数９９】
2021536610.tif 000109
を有し得る。MaxCutに適用されるQAOAについて、
【数１００】
2021536610.tif 000110
は、回路を通じて交換可能であるのでさらなる
【数１０１】
2021536610.tif 000111
対称性が存在し得る。さらに、udRグラフ上のMaxCut問題の構造は、dが偶数である場合、
【数１０２】
2021536610.tif 000112
であるので、冗長性（redundancy）を生成し得る。これらの対称性は、一般に
【数１０３】
2021536610.tif 000113
に制限することを可能にする。
【００９４】
いくつかの態様において、腕ずくのアプローチを使用して、頂点数
【数１０４】
2021536610.tif 000114
を有するランダムu3Rおよびw3Rグラフ上のMaxCutについての最適QAOAパラメーターを数値的に調査することが可能である。各グラフの例および所定のレベルpについて、パラメーター空間におけるランダム開始点(シード)が選択され得、ブロイデン-フレッチャー-ゴールドファーブ-シャノ(「BFGS」)などの勾配ベースの最適化アルゴリズムは、このシードから開始して局所最適
【数１０５】
2021536610.tif 000115
を見出すために使用され得る。いくつかの態様において、局所最適は、パラメーター
【数１０６】
2021536610.tif 000116
の所定の選択について、結果が、パラメーター
【数１０７】
2021536610.tif 000117
の値がわずかに変化する場合に、常に悪化する場合を言い得る。しかし、かかる局所最適について、結果は、これらのパラメーターの値が、その代わりに、劇的に変化する場合、良好になり得る。従って、最適は、局所最適と言われ得、全体的な最適とは言われ得ない。いくつかの態様において、各グラフについて、最適化が初期開始パラメーターに近いパラメーターのみを捜すものなどの局所最適化法により、変動性パラメーターを最適化し、解が局所最適に達することが可能である。この局所最適化は、十分に多くの異なるシードを用いて繰り返され得、全体的な最適
【数１０８】
2021536610.tif 000118
を見出し得る。いくつかの態様において、全体的な最適は、パラメーターのより良好な選択がない場合を言い得る。全体的な最適は、グラフ毎に変化し得る。最適パラメーター
【数１０９】
2021536610.tif 000119
の縮退は、上記で議論される対称性を使用して(例えば、等しい
【数１１０】
2021536610.tif 000120
のいくつかの(別個の)値を見出すことにより、なぜなら、これらは、正確に同じ結果を導き、従って、個々に考える必要はないからである)、低減され得る。いくつかの例示的な例において、全体的な最適は、これらの対称性まで非縮退であり得る。
【００９５】
いくつかの態様において、最適パラメーター
【数１１１】
2021536610.tif 000121
を同定するプロセスは、種々の頂点数Nを有する100個のu3Rおよびw3Rグラフなどのさらなるランダムグラフについて繰り返され得、これは、最適パラメーター
【数１１２】
2021536610.tif 000122
の１つ以上のパターンを引き出し得る。１つの例において、最適
【数１１３】
2021536610.tif 000123
は、各イテレーション
【数１１４】
2021536610.tif 000124
は、滑らかに減少する傾向にあり得る。例えば、図15A〜15Bは、いくつかの態様によるレベルp=7での16-頂点重み無し3-正則(u3R)グラフ上のMaxCutの例示的な例について得られた最適QAOAパラメーター
【数１１５】
2021536610.tif 000125
の例示的な例を示す。図15A〜15Bに示されるように、レベルp=7についてのパラメーターは、各イテレーションiについて滑らかに推移する（transition）。
【００９６】
図15C〜15Hは、いくつかの態様によるイテレーションiの関数として、
【数１１６】
2021536610.tif 000126
についての16-頂点u3Rグラフ(図15A〜15Bをプロットするために使用される例など)の40の例の最適パラメーターをプロットすることにより可視化されたパラメーターパターンを示す。各破線は、１つの特定のグラフの例についてのパラメーターを連結する。各例および各pについて、古典的なBFGS最適化アルゴリズムを、104ランダムシード(開始点)から最良のパラメーターを保持しつつ使用した。類似したパターンがw3Rグラフについて見出され得、これは、以下により詳細に議論される。さらに、いくつかの例において、所定の種類のグラフについて、pが変化する場合に、最適パラメーターが観測され得、同じ範囲の値がほぼ占有され得る。これは、以下により詳細に議論されるように、最適化において利用され得る最適QAOAパラメーターにおけるパターンを示す。ランダムシードの数がそれに従って増大する場合、類似したパターンが、
【数１１７】
2021536610.tif 000127
までのパラメーターについて見出される。
【００９７】
図21A〜21Fは、いくつかの態様による
【数１１８】
2021536610.tif 000128
に関する16-頂点重み付き3-正則(w3R)グラフの40例についての最適QAOAパラメーター
【数１１９】
2021536610.tif 000129
を示すグラフを示す。各破線は、１つの特定のグラフの例についてのパラメーターを連結する。各例示的な例および各pについて、BFGSアルゴリズムは、104ランダム開始点から最適化するために使用され、最良のパラメーターは、
【数１２０】
2021536610.tif 000130
として保持される。図21A〜21Fは、図15C〜15Hにおける重み無しグラフの結果に類似する。重み付きグラフについての
【数１２１】
2021536610.tif 000131
のスプレッド（spread）は、図15C〜15Hに示す重み無しグラフについてのものより広い。いくつかの態様において、これは、ランダムな重みが、サブグラフ（subgraph）型の数を効果的に増大させるからである。さらに、重み無しグラフと比べての重み付きグラフについての
【数１２２】
2021536610.tif 000132
のより大きな値は、各キュービットが経験する有効平均場強度を介して理解され得る。
【００９８】
特に、小さなデプスにおいても、このパラメーターパターンは、いくつかの態様におけるHCが徐々にオンになり、HBが徐々にオフになる断熱的量子アニーリングを思い出させ得る。しかし、以下により詳細に議論されるように、QAOAの機構は、断熱的原理を超えることが示され得る。さらに、いくつかの態様において、最適パラメーターは、多くの異なる例にわたって小さなスプレッドを有し得る。これは、目的関数
【数１２３】
2021536610.tif 000133
が全てのエッジから距離
【数１２４】
2021536610.tif 000134
離れている頂点を含むサブグラフに対応する項の和であり得るからであり得る。小さなpにおいて、Fpに入り、最適パラメーターを効果的に決定し得るわずか数個の関連するサブグラフ型がある。
【数１２５】
2021536610.tif 000135
の場合に一定の有限のpで、関連するサブグラフ型がランダムグラフに現れる確率は、一定の有理数（fraction）に近づき得る。これは、最適パラメーター
【数１２６】
2021536610.tif 000136
の分布が、この極限において一定の値の組に収束し得ることを意味する。
【００９９】
いくつかの態様において、上記で観察される最適パラメーターパターンは、一般的に、パラメーター
【数１２７】
2021536610.tif 000137
の基礎となるゆっくり変化する連続的な曲線があることを示し得る。いくつかの態様において、この曲線は、各レベルpからp+1へとわずかにのみ変化する。これらの観察に基づいて、QAOAの新たなパラメーター化および限定されることなく、「FOURIER」と言われ得るヒューリスティック最適化戦略が使用され得る。いくつかの態様において、ヒューリスティック戦略は、良好な開始点を生じることにより、レベルpでの最適パラメーターからの情報を使用し、レベルp+1での最適化を補助する。このヒューリスティックは、QAOAパラメーターの全体的な最適物を必ずしも見出さないが、該ヒューリスティックは、O(poly(p))回において、2O(p)回の腕ずくのランを用いてのみ超えられ得る準-最適物を生じ得る。いくつかの有益な態様において、これは、p=1以外の（beyond）QAOAの性能および機構の評価を容易にする。
【０１００】
いくつかの態様において、QAOAは、最適QAOAパラメーター
【数１２８】
2021536610.tif 000138
がそれらの指数iの滑らかな関数であるように見えるという観察に基づいて再パラメーター化され得る。QAOAパラメーターの代替的な表示は、実数のフーリエ関連変換を使用して実行され得、これは、必要なパラメーターの数に簡略化し得る。2pパラメーター
【数１２９】
2021536610.tif 000139
を使用する代わりに、FOURIERは、2qパラメーター
【数１３０】
2021536610.tif 000140
を代わりに使用し得、ここで、個々の要素
【数１３１】
2021536610.tif 000141
は、以下の変換:
【数１３２】
2021536610.tif 000142
により
【数１３３】
2021536610.tif 000143
の関数として記述される。
【０１０１】
いくつかの態様において、これらの変換は、離散サイン/コサイン変換と言われ得、ここで、ukおよびvkは、
【数１３４】
2021536610.tif 000144
のそれぞれについてのk番目の周波数成分の振幅と解釈され得る。
【数１３５】
2021536610.tif 000145
の場合、この新たなパラメーター化は、レベルpでの全ての可能なQAOAプロトコルを記述し得る。
【０１０２】
FOURIER 戦略の態様は、レベルp=1で開始し、レベルp=1について腕ずくのものなどの最適化関数を使用して最適化し、次いで、レベルpでの最適物を使用してレベルp+1についての開始点を決定することにより、作動する（work）。開始点は、最適化パラメーター
【数１３６】
2021536610.tif 000146
から外挿されたレベルpからの周波数成分の最適化振幅
【数１３７】
2021536610.tif 000147
を再度使用し、レベルp+1についてパラメーター
【数１３８】
2021536610.tif 000148
を同定することにより生じ得る。これは、pが増大する間繰り返され得る。
【０１０３】
いくつかの態様は、この戦略のいくつかの変形を含み、その例は、p-レベルQAOAを最適化することについて、FOURIER[q, R]およびINTERPと言われる。限定されることなく、変形の１つの態様は、２つの整数パラメーターqおよびRを特徴とするFOURIER[q, R]と言われ得る。第１の整数qは、パラメーター
【数１３９】
2021536610.tif 000149
において許容される最大周波数成分と言われ得、これは、kの最大値であり得る。q=pである場合、p-レベルQAOAの最大の羃（full power）が使用され得る。しかし、最適パラメーター
【数１４０】
2021536610.tif 000150
の滑らかさは低周波数成分のみが重要であることを意味するので、qが、pから独立しているがそれより小さな一定の定数であり、その結果、パラメーターの数がQAOA回路デプスが増大する場合でも束縛される場合を考慮することも可能である。
【０１０４】
いくつかの態様において、第２の整数Rは、局所最適をより良好なものへと逃すために、パラメーターに追加された制御されたランダム摂動の数と言われ得る。例えば、最適化パラメーター
【数１４１】
2021536610.tif 000151
が、初期値p=1について局所最適にあるが全体的な最適ではないと同定された場合、摂動は、増大するpの値について該局所最適にのみに焦点を合わせることを避けるために導入され得る。本開示で議論される例示的な結果は、FOURIER[q, R]戦略（式中、そうではないと述べられない限り、q=pおよびR=10）を実行するが、選択などは制限しない。
【０１０５】
qがq=pであるように選択される態様において、戦略は、qがpに束縛されずに増大するので、
【数１４２】
2021536610.tif 000152
と示され得る。この戦略の
【数１４３】
2021536610.tif 000153
変形の態様において、開始点は、ゼロ振幅で開始されるより高い周波数成分をレベルpでの最適に追加することにより、レベルp+1について生成される。例えば、いくつかの態様により図22に示されるように、レベルp-1での最適化変動性パラメーター2212
【数１４４】
2021536610.tif 000154
から、開始点2222A
【数１４５】
2021536610.tif 000155
は、
【数１４６】
2021536610.tif 000156
に従って生成される。
【数１４７】
2021536610.tif 000157
2222Aを開始点として使用することにより、BFGS最適化ルーチンは、レベルpについての局所最適2224B
【数１４８】
2021536610.tif 000158
を得るために実施され得る。これは、プロセスが続く場合、pの次のレベルに対する出力である。
【０１０６】
いくつかの態様において、この技術に対する改善は、図22にも示される戦略
【数１４９】
2021536610.tif 000159
を用いて得られ得る。いくつかの態様において、戦略
【数１５０】
2021536610.tif 000160
は、最適に及ばない局所最適で行き詰まり（stick）得る。従って、
【数１５１】
2021536610.tif 000161
で実施されるようなその開始点の摂動により、
【数１５２】
2021536610.tif 000162
で既に見られたQAOAの性能が大いに改善され得る。
【０１０７】
図22に示されるように、技術は、いくつかの態様によりレベルp-1で開始する。
【数１５３】
2021536610.tif 000163
のいくつかの態様において、戦略
【数１５４】
2021536610.tif 000164
に従った最適化に加えて、p-レベルQAOAが、R+1特別（extra）開始点から最適化され得、このうちRは、ランダム摂動をレベルp-1で見出される全ての局所最適
【数１５５】
2021536610.tif 000165
の最良のものに追加することにより生成される。特に、p-レベルQAOAの各例について、およびr=0, 1, . . . , Rについて、最適化は、
【数１５６】
2021536610.tif 000166
（式中、
【数１５７】
2021536610.tif 000167
は、平均0ならびに
【数１５８】
2021536610.tif 000168
により与えられる分散を有する正規分布から得られるランダムな数を含む:
【数１５９】
2021536610.tif 000169
）から開始され得る。
【０１０８】
かかる態様において、摂動の強さに対応する自由パラメーター（free parameter）
【数１６０】
2021536610.tif 000170
がある。試行錯誤から生じるいくつかの非限定的な例において、
【数１６１】
2021536610.tif 000171
と設定することにより、良好な結果を生じ得る。この
【数１６２】
2021536610.tif 000172
の選択は、そうではないと述べられない限り、本開示において仮定される。しかし、当業者は、
【数１６３】
2021536610.tif 000173
特定の実行に依存して必要に応じて使用され得ることを理解する。
【０１０９】
いくつかの態様において、さらなる戦略が、上記されるパラメーターパターンを利用するために使用され得る。１つの例示的な戦略は、より低いレベルのQAOAでの最適パラメーターの線形補間（linear interpolation）を使用し得、より高いレベルについての開始点を生成し得、これは、限定されることなく、「INTERP」と言われ得る。INTERPおよびFOURIER戦略の両方は、本開示を通じて議論される例について効果的であり、他にも同様に適用可能である。FOURIERは、ランダムな摂動が導入された場合により良好な最適物を見出すことにおいてその性能にわずかな有効性（edge）を示したが、当業者は、本開示から、INTERPがまた、QAOAを改善する効率的な様式であり、さらなる利益を提供し得ることを理解する。FOURIER[q, R]およびINTERPの態様は、以下により詳細に記載される。しかし、機械学習の使用などのさらなる技術が、本開示により企図される。さらに、本開示の局面において、ヒューリスティック戦略は、レベル-(p-1)QAOAで見出される最適変動性パラメーターを使用して、レベルp QAOAでの初期変動性パラメーターを見出すが、当業者は、任意のm<pについてレベル-mで見出される最適変動性パラメーターが、レベルp QAOAでの初期変動性パラメーターを設計するために使用され得ることを理解する。
【０１１０】
FOURIER戦略のいくつかの変形において、周波数成分qの数は、一定である。これらの変形は、全ての
【数１６４】
2021536610.tif 000174
パラメーターが第１q成分で切り捨てられ得る場合を除いて、上記で議論されるq=pの場合の戦略と同様に扱われ得る。例えば、FOURIER[q,0]戦略を用いてレベル
【数１６５】
2021536610.tif 000175
でQAOAを最適化する場合、さらにより高い周波数成分は追加されず、開始点は、
【数１６６】
2021536610.tif 000176
で開始する。
【０１１１】
INTERPと言われる最適化戦略のいくつかの態様において、線形補間は、QAOAを最適化するための開始点を生じるために使用され得、最適化ルーチンは、レベルpをイテレーション的に（iteratively）増大させ得る。しかし、本議論の目的のために、pは、FOURIER戦略についての議論においてp-1と同じであるとみなされるべきであり、これは、このことが、単に、どこでアルゴリズムを開始するかについての記号論（semantics）の問題であるからである。いくつかの態様において、これは、パラメーター
【数１６７】
2021536610.tif 000177
の形態（shape）が
【数１６８】
2021536610.tif 000178
の形態に非常に類似するという観察に基づく。所定の例について、QAOAは、p=1から開始し、局所最適パラメーター
【数１６９】
2021536610.tif 000179
を得、かつpからp+1へと漸増させることにより、イテレーション的に最適化される。レベルp+1についてパラメーターを最適化するために、レベルpからの最適化パラメーターを使用して、
【数１６９−１】
2021536610.tif 000180
について、
【数１７０】
2021536610.tif 000181
（式中、iは、ベクトルのi番目の要素を示す）に従って、開始点
【数１７１】
2021536610.tif 000182
を生じる。ここで、
【数１７２】
2021536610.tif 000183
は、パラメーターベクトル
【数１７３】
2021536610.tif 000184
についての式は、
【数１７４】
2021536610.tif 000185
の交換の後、上記と同じであり得る。
【数１７５】
2021536610.tif 000186
から開始する場合、BFGS最適化ルーチン(または任意の他の最適化ルーチン)は、(p+1)-レベルQAOAについて局所最適
【数１７６】
2021536610.tif 000187
を得るために実施され得る。最終的に、pは、１だけ増加され得、同じプロセスは、標的レベルに到達するまで、繰り返され得る。
【０１１２】
いくつかの態様において、INTERP戦略は、また、局所最適に行き詰まり得る。INTERPに摂動を追加することは、補助となり得るが、いくつかの態様において、 FOURIERを用いた場合ほどは効果的であり得ない。これは、最適パラメーターが滑らかであるので生じ得、
【数１７７】
2021536610.tif 000188
が相関する様式で改変され、このことは、最適化が局所最適をより容易に逃れることを可能にし得る。しかし、類似した摂動ルーチンが企図される。
【０１１３】
上記で議論したように、本開示に記載されるヒューリスティックアプローチは、腕ずくのQAOA技術に対する有意な改善を構成する。例示的な実行の非限定的な比較は、以下の節で以下に議論される。
【０１１４】
本開示に基づいて、当業者は、開示されたヒューリスティック戦略が複数の技術的基盤に対して実行され得ることを理解する。表題「例示的なQAOA実行」の以下の節において、MaxCut問題は、例として考慮されるが、それは、他の興味深い問題を解くためにも適用され得る。
【０１１５】
量子系を用いた例示的な実行
いくつかの態様において、大きなサイズの問題は、量子系に対する実行に適している。かかる実行(リュードベリ原子を用いて相互作用範囲および例を低減すること)の２つの局面は、以下により詳細に議論される。
【０１１６】
まず、相互作用範囲を低減することに関して、いくつかの量子実行において、上記で議論したように、各頂点は、キュービットにより示され得る。大きな問題サイズについて、一般的なグラフをエンコードすることに対する主な難題は、(キュービットの間の)相互作用パターンの必要な範囲および融通性（versatility）である。ランダムグラフを1Dまたは2D幾何構造を伴う物理的実行に埋め込む（embed）ことは、非常に長距離の相互作用を必要とし得る。グラフ頂点を再標識することにより、相互作用の必要な範囲を低減することが可能である。理論に拘束されることなく、これは、グラフバンド幅問題（graph bandwidth problem）として定式化され得る:N頂点を有するグラフG=(V, E)を仮定すると、頂点番号付けは、頂点から別個の整数への全単射マップである
【数１７８】
2021536610.tif 000189
頂点番号付けのバンド幅
【数１７９】
2021536610.tif 000190
これは、(1Dにおける)最長エッジの長さと理解され得る。次いで、グラフバンド幅問題は、全ての頂点番号付けの中から最小バンド幅、即ち、B(G)=minfBf(G) を見出すことであり;即ち、それは、頂点番号付け替えにより最長エッジの長さを最小化することである。
【０１１７】
一般的に、最小グラフバンド幅を見出すことは、NP-困難であるが、良好なヒューリスティックアルゴリズムが、グラフバンド幅を低減するために開発されてきた。図20A〜20Eは、いくつかの態様によるバンド幅低減の単純な例を示す。図20A、20Bは、5-頂点グラフを用いた頂点番号付け替えを示す。図20Eは、各N=400の1000個のランダム3-正則グラフについてのグラフバンド幅の柱状グラフを示す。カットヒル-マッキーアルゴリズムを使用して、グラフバンド幅は、約
【数１８０】
2021536610.tif 000191
まで低減され得る。これは、1Dにおいて極めて長い相互作用範囲（interaction range）をなお必要とし得るが、バンド幅問題は、また、より高い次元まで一般化され得る。2D配置において、相互作用の半径は、N=400の3-正則グラフについて
【数１８１】
2021536610.tif 000192
であると考えられ得、これは、量子デバイスについて可能である。図20Cおよび20Dは、１つの例示的なグラフについての頂点番号付け替えの前後の隣接マトリックス（adjacency matrix）の散在するパターンを示す。この例示的な例において、頂点番号付け替え技術は、MaxCut問題に適用されるが、当業者は、本開示に基づいて、同じ技術が最大独立集合問題などの他の組合せ最適化問題に使用され得ることを理解する。
【０１１８】
いくつかの態様において、一般的な構築物（general construction）は、さらなる物理的キュービットおよびゲージ束縛（gauge constraint）を含めることにより、任意の長距離の相互作用を局所場にエンコードするために使用され得る。いくつかの幾何学的構造を示す特別なグラフに制限することも可能である。例えば、単位円グラフは、2D面における幾何学的グラフであり、ここで、頂点は、単位距離以内にある場合にのみ、エッジにより連結される。これらのグラフは、2D物理的実行にエンコードされ得、MaxCut問題は、単位円グラフ上でなおNP-困難である。
【０１１９】
いくつかの態様において、QAOAの上記議論は、基盤と独立しており、任意の最新の基盤に適用可能である。例示的な基盤は、中性リュードベリ原子、捕捉されたイオン、および超伝導キュービットを含む。以下の議論は、リュードベリ励起を介して相互作用する中性原子を伴うQAOAの実行に焦点を合わせ、そこでは、高い-忠実度のもつれが最近示されているが、他の実行が企図される。
【０１２０】
いくつかの態様において、所定のグラフに従って個々の原子の間の相互作用の制御を実行することが可能である。いくつかの態様において、この様式では、どの型の問題が解かれるかを制御することが可能である。相互作用は問題を特定し得るので、相互作用を制御することは、問題を制御するための１つの方法である。上記により詳細に議論されるように、例示的なリュードベリ実行において、各原子における超微細基底状態は、キュービット状態
【数１８２】
2021536610.tif 000193
状態は、相互作用を誘導するためにリュードベリレベル
【数１８３】
2021536610.tif 000194
に励起され得る。キュービット回転項
【数１８４】
2021536610.tif 000195
は、整調可能な（tunable）持続時間を伴う全体的な駆動ビームにより実行され得る。相互作用項
【数１８５】
2021536610.tif 000196
は、一般的なグラフについてストロボ的に実行され得;これは、図20Fに示されるように、リュードベリ-ブロッケード制御ゲートにより実現され得る。例えば、図20Fは、リュードベリ-ブロッケード制御ゲートを使用して相互作用項
【数１８６】
2021536610.tif 000197
を実行するためのプロトコルを示す。例えば、図20Fは、第１に、π-パルスを制御キュービットに適用し、第２に、カップリング強度Ωおよび離調Δを有するパルスを標的キュービットに適用し、かつこのパルスを制御キュービット上で別のπ-パルスを用いて追跡することにより、相互作用項の特定の成分をどのように実現するかを示す。第２のステップについて適切なゲート時間、例えば、
【数１８７】
2021536610.tif 000198
を選択することにより、リュードベリレベル
【数１８８】
2021536610.tif 000199
に集団は、蓄積され得ない。整調可能なカップリング強度Ωおよび離調Δを用いて、相互作用時間
【数１８９】
2021536610.tif 000200
を制御することが可能である。
【０１２１】
カップリング強度
【数１９０】
2021536610.tif 000201
、およびゲート時間を、単一-キュービット回転と一緒に制御することにより、
【数１９１】
2021536610.tif 000202
を実行することが可能であり、これは、次いで、各相互作用対について繰り返され得る。この様式において、どの対が相互作用するべきであるかを選択すること、および、従って、どの問題が解かれるべきであるかを制御することが可能である。いくつかの態様において、リュードベリブロッケード機構のさらなる利点は、多キュービット集合的ゲートを並行して実施するその能力である。これは、２-キュービット操作段階の数を、エッジの数から頂点の数Nまで低減させ得、これは、〜N2エッジを有する密なグラフについてN倍の低減を意味する。リュードベリ相互作用の減少は２つのキュービットが相互作用し得る距離を制限し得るが、興味深いサイズのMaxCut問題は、上記で議論したように、単位円グラフ上の頂点番号付け替えまたは該単位円グラフに焦点を合わせることにより、なお実行され得る。さらに、本開示で議論されるアンシラリー頂点を実行することは、相互作用の長さを増大させるために使用され得る。
【０１２２】
理論に拘束されることなく、いくつかの態様において、400-頂点正則グラフの一般的問題について、相互作用範囲は、2Dにおいて大体5原子であり得る。これは、2μmの最小-原子間分離を仮定することにより決定され得、これは、10μmの相互作用半径を意味し、これは、高いリュードベリレベルを用いて実現され得る。高い-忠実度制御を有するカップリング強度
【数１９２】
2021536610.tif 000203
(リュードベリレベル寿命により制限される)の例を仮定すると、２-キュービットゲート当たりの誤りは、ほぼ
【数１９３】
2021536610.tif 000204
になり得る。400-頂点の3-正則グラフについて、レベル
【数１９４】
2021536610.tif 000205
のQAOAは、中性原子の2Dアレイを用いて実行され得る。パルス整形（pulse-shaping）などの進んだ制御技術は、かかる系においてQAOAの能力を増大させる。さらに、QAOAは、リュードベリ原子を用いた現存する実行に存在する欠陥（imperfection）のいくつかに敏感ではあり得ない。
【０１２３】
以下の節は、本開示のさらなる例および態様を調査する。本開示は、本明細書に記載される理論により限定されず、該理論は、単に、本開示のいくつかの態様の基礎をなす操作原理のいくつかの局面の例示を意味する。
【０１２４】
ランダムUD-MISのための量子アニーリング
いくつかの態様において、量子アニーリングアルゴリズム(QAA)などの量子最適化アルゴリズムは、ランダムUD-MIS問題のために使用され得る。上記で議論したように、ランダム単位円(UD)グラフ上の最大独立集合問題は、本開示により企図される問題のほんの１つの型である。UDグラフを伴うQAAについて、ランダムUDグラフは、２つのパラメーター:頂点の数Nおよび2D頂点密度ρによりパラメーター化され得る。図5に示されるように、単位距離は、r=1であることが採用され得、頂点は、
【数１９５】
2021536610.tif 000206
である。特に、図5は、N=40、ρ=1.5、|MIS|=14、および93エッジを有するランダム単位円グラフの例を示す。理論に拘束されることなく、密度ρを有するランダムUDグラフについて、平均頂点次数（vertex degree）は、およそπρである。有限-サイズ境界効果を最小化するために、周期的境界条件が、本開示で議論される数値的シミュレーションにおけるUDグラフについて使用される。しかし、かかる条件は不要である。
【０１２５】
上記で議論したように、MISについてのQAAは、以下のハミルトニアン:
【数１９６】
2021536610.tif 000207
を使用して実施され得る。
【０１２６】
QAAは、まず、全てのキュービットを時間t=0で|0>に初期化することにより設計され得、これは、Δ(t=0)<0およびΩ(t=0)=0(U>0の場合)の場合に、HQA(t=0)の基底状態である。次いで、パラメーターは、例えば、まず、Ω(t)を非-ゼロ値にオンし、Δ(t)を正の値まで掃引し、最後に、再度Ω(t)をオフすることにより、変更され得る。理論に拘束されることなく、本開示を通じて議論される例示的なアニーリングプロトコルは、
【数１９７】
2021536610.tif 000208
により特定され得る。
【０１２７】
時間進展が十分に遅い場合、断熱定理（adiabatic theorem）により、系は、瞬間的な基底状態を経て進み得、最後に、MIS問題に対する解になり得る。Ω0=1はエネルギーの単位と考えられ得、Δ0/Ω0=6に固定することが可能であり、これは、非限定的な例において、非断熱的遷移を最小化するための良好な比として同定される。
【０１２８】
いくつかの態様において、量子アニーリングは、N個の頂点および密度ρを有するランダム単位円グラフ上で調査され得る。いくつかの態様において、
【数１９８】
2021536610.tif 000209
の極限において、非独立集合は、大きなエネルギーペナルティーにより押しのけられ（pushed away）、無視され得る。いくつかの実行において、これは、リュードベリ相互作用エネルギーが他のエネルギースケールによりもかなり強い極限に対応し得る。理論に拘束されることなく、この極限におけるいくつかの例において、波動関数は、本明細書で議論される例示的な数値的シミュレーションにおいて、
【数１９９】
2021536610.tif 000210
などの全ての独立集合の部分空間に制限され得、これは、
【数２００】
2021536610.tif 000211
であるので、N〜50までのかなりより大きな系サイズへのアクセスを可能にする。まず、ある例において、全ての独立集合の部分空間は、古典的なアルゴリズム、ブロン-カーボッシュアルゴリズムにより見出され得、次いで、等式18におけるハミルトニアンは、全ての独立集合の部分空間に射影され得る。時間依存的ハミルトニアンを用いた動力学は、総シミュレーション時間tを十分に小さな不連続の時間ステップτに分割することにより、シミュレートされ得、各小さな時間ステップにおいて、打ち切った（truncated）テーラー級数近似を用いたスケーリングアンドスクエアリング法（scaling and squaring method）を使用して、完全な進展演算子を形成せずに時間進展を実施し得る。
【０１２９】
いくつかの態様において、断熱的量子アニーリングを良好に実施するための例示的な時間スケールが、調査され得る。いくつかの例において、この時間スケールは、最小スペクトルギャップ∈gapにより支配され得、ここで、必要なラン時間は、
【数２０１】
2021536610.tif 000212
であり得る。しかし、最小スペクトルギャップは、最終基底状態が高度に縮退している場合、不明瞭であるとみなされ得、なぜなら、状態が瞬間的な励起状態とカップリングすることが可能であるからであるが、それは、該状態が、最終的に、基底状態に戻る限りのことである。例示的な一般的なグラフについて、多くの別個の最大独立集合が存在し得る(HPの基底状態は、高度に縮退し得る)。従って、最小ギャップを見出す代わりに、異なるアプローチが断熱的な時間スケールを抽出するために採られ得る。
【０１３０】
いくつかの態様において、断熱的極限において、最終基底状態集団(縮退を含む)は、ランダウ-ゼナー式
【数２０２】
2021536610.tif 000213
（式中、aは定数であり、TLZは、断熱的時間スケールである）
の形式を採り得る。非縮退の場合の態様において、
【数２０３】
2021536610.tif 000214
を有することが典型的である。より一般的な場合において、時間スケールTLZは、この式にフィッティングすることにより抽出され得る。しかし、いくつかの例において、単純な指数関数的な形式は、
【数２０４】
2021536610.tif 000215
である断熱的極限においてのみ維持される。従って、各グラフの例について、等式が維持されるように最小Tを捜すことが可能である。例えば、Tは、PMIS>0.9であるような最小T*が見出されるまで、(Tmin=5から)イテレーション的に適応的に（adaptively）2倍になり得、そこでは、いくつかの態様において、時間進展がランダウ-ゼナー型にあると仮定することが可能である。次いで、動力学は、別の３つの時点1.5T*、2T*、および2.5T*についてシミュレートされ得、その後、最後に、T*〜2.5T*の等式にフィッティングし得、時間スケールTLZを抽出し得る。
【０１３１】
フィッティングは、いくつかの例において、ほとんどの例について効果的であることが示された。例えば、図6は、断熱的時間スケールTLZを抽出するための
【数２０５】
2021536610.tif 000216
へのランダウ-ゼナーフィッティングを示す。ここで、N=10、20、30、40を有する４つのランダム単位円グラフがプロットされる。各例示的な例について、最初のTは、PMIS(T)>0.9であるようにイテレーション的に見出され、T*と示される。次いで、フィッティングは、４つの点T*、1.5T*、2T*、2.5T*に対して実施され、時間スケールTLZが抽出される。適合度（goodness-of-fit）R2<0.99であるいくつかのグラフを脱落させることが可能である。いくつかの態様において、この手順は、各Nおよびρでの30個までのグラフの例についてTLZを抽出するために実施され得る。これらから、メジアンが得られ得、該メジアンは、上記した図4AにプロットされるようなTLZに関する完全な状態図を生じるために使用され得る。
【０１３２】
図7A〜7Cは、いくつかの一定の密度での断熱的時間スケールTLZを示す。より具体的には、図7A〜7Cは、N=46までの系サイズに関するQAAについてシミュレートされた200個のランダム単位円グラフを示す。図7Aは、メジアンTLZをプロットし、図7Bおよび7Cは、ρ=0.8およびρ=3に関する個々の例についてTLZをプロットする。図7A〜7Cは、いくつかの一定の密度ρ=0.8(浸透閾域より下)およびρ=3(浸透閾域より上)でのNを有するTLZのスケーリング（scaling）を示す。図7Aは、いくつかの態様によるρ=0.8とρ=3の間の明確な分離を示す。しかし、Nのスケーリングは、不明確であり、これは、有限サイズ効果により得る:
【数２０６】
2021536610.tif 000217
は、スケーリングを示すためのより良好な条件であり得る。図7Bおよび7Cは、また、各例についてTLZのスプレッドを示す。いくつかの例示的な困難な例は、典型的な例より有意に長いTLZを必要とするが、ρ=3、
【数２０７】
2021536610.tif 000218
について平均してTLZ>10でさえあることが見られ得る。
【０１３３】
上記で議論されるいくつかの態様は、例示的なアルゴリズムがMISを正確に解く能力に主に焦点を合わせているが、例えば、できる限り大きな独立集合を見出すという意味において、アルゴリズムがMISを近似的に解き得るかどうかを同定することも可能である。いくつかの例示的な量子アルゴリズムについて、理論に拘束されることなく、近似比rが、近似の性能を評価するために使用され得る。例えば、状態
【数２０８】
2021536610.tif 000219
を出力する量子アルゴリズム(量子アニーラーなど)について、
【数２０９】
2021536610.tif 000220
は、MISのサイズである）を記述することが可能である。換言すれば、rは、出力量子状態を測定することにより見出される平均独立集合サイズの最大独立集合サイズに対する比を定量し得る。図8は、いくつかの態様による一定の時間T=10/Ω0でNおよびρあたり30個のグラフの例を平均した量子アニーリング(上記で議論される図4Bと同じ例)をシミュレートすることにより、近似比rに関して例示的な類似した状態図を示す。垂直の破線は、
【数２１０】
2021536610.tif 000221
での浸透比（percolation ratio）に対応し、傾斜した破線は、最適円パッキングに対応する。図8は、図4Bに関して上記で議論される基底状態集団と定性的に同じ特徴を示すが、有限サイズ効果は、大きな密度にて小さな不連続の|MIS|値のためにより強い。
【０１３４】
UDグラフを超える任意のグラフ構造に対する一般化
ストロボ的進展
上記で議論したように、UD模範（paradigm）を超えての、グラフG=(V, E)に対するMIS問題を扱うための上記で議論される例示的な実行を一般化することが可能である。
【０１３５】
いくつかの態様において、UD模範に関して上記で議論される量子アルゴリズムは、ハミルトニアン
【数２１１】
2021536610.tif 000222
を用いた進展を含む。U>>|Ω|,|Δ|である例示的な態様において、動力学は、独立集合空間HISに効果的に制限され得る。理論に拘束されることなく、一般的なグラフ構造に対応するハミルトニアンを用いたかかる進展を生じるためのいくつかの態様において、時間進展演算子のトロタライズドバージョンが考慮され得る:
【数２１２】
2021536610.tif 000223
（式中、時間区間[0,T]は、
【数２１３】
2021536610.tif 000224
であるように、分割され、時間tjを画定する）。ここで、Dmaxは、グラフの最大次数を示し得る。各U(tj)は、以下
【数２１４】
2021536610.tif 000225
のように、さらにトロタライズされ得る。
【０１３６】
換言すれば、それは、項
【数２１５】
2021536610.tif 000226
の積に分割され得、ここで、各々は、１つのスピンvの進展と関連する。ここで、
【数２１６】
2021536610.tif 000227
の隣接体を示し得る。U→∞極限において、これは、
【数２１７】
2021536610.tif 000228
として記述され得ることに留意のこと。
【０１３７】
これは、原子
【数２１８】
2021536610.tif 000229
の単純な単一キュービット回転であり、いくつかの態様において、
【数２１９】
2021536610.tif 000230
であることを条件とする。隣接体の少なくとも１つが、状態
【数２２０】
2021536610.tif 000231
は進展し得ない。
【０１３８】
キュービット超微細エンコードを使用した実行
いくつかの態様において、キュービットの特定の対またはサブセットの間の相互作用を特定するために、量子系のさらなる制御を追加することが望ましい。個々に制御される中性原子を用いて対応する動力学を実行するための１つの例示的なアプローチは、内部原子基底状態マニホールド（manifold）中の２つの(相互作用しない)超微細状態にエンコードされたキュービット状態
【数２２１】
2021536610.tif 000232
を利用し得る。換言すれば、他の形式のグラフを実行する場合、キュービットの個々の対(またはセット)の間の所望の相互作用により、イテレーションすることが可能である。
【０１３９】
いくつかの態様において、原子は、距離gを有する2D正方格子の点に配置され得る。単一ステップ
【数２２２】
2021536610.tif 000233
上のvの隣接体に対応する原子uが、状態
【数２２３】
2021536610.tif 000234
へと選択的に励起され得る。いくつかの態様において、グリッド長
【数２２４】
2021536610.tif 000235
のいずれもがこのプロセスの間に相互作用しないように、選択され得る。次いで、原子vは、例えば、物理的操作などであるがこれに限定されないユニタリー操作を用いて、超微細マニホールド中での単一キュービット回転が実現されるように駆動され得、該物理的操作は、決定論的に実施され得、例えば、
【数２２５】
2021536610.tif 000236
は、原子vの２つの超微細キュービット状態をカップリングさせ、
【数２２６】
2021536610.tif 000237
にあるかどうかを数える（count））
を用いた進展に対応する量子状態進展を引き起こすレーザーを用いて原子を駆動することである。いくつかの態様において、この回転を実現するために、リュードベリP-状態を通した遷移を介して原子vの２つの超微細状態
【数２２７】
2021536610.tif 000238
をカップリングさせ得る個々にアドレシングされた（addressed）２段階励起が使用され得る(例えば、まず、第１のレーザーパルスを用いて原子を、状態
【数２２８】
2021536610.tif 000239
からリュードベリP状態に励起すること、および次いで、第２のレーザーパルスを用いてその状態を、リュードベリP状態から状態
【数２２９】
2021536610.tif 000240
に変更することにより)。いくつかの態様において、全ての原子uが、状態
【数２３０】
2021536610.tif 000241
にある場合、このプロセスは乱され得ないが、次いで、隣接体の少なくとも１つがリュードベリS状態である場合、強いS-P相互作用がブロッケード機構を生じ得、該ブロッケード機構は、キュービットvの回転を妨げ、従って、正確に等式23を実現する。いくつかの態様において、これは、一方ではリュードベリS-状態にある２つの原子についてのブロッケード半径と、他方ではS-Pブロッケード半径の異なるスケールの相互作用長を必要とし得、なぜなら、これらの２つの相互作用は、原子の分離と異なって比例する（scale）からであることに留意のこと:S-P相互作用は、1/x3として減衰し(ほぼ1/x6に比例するS-S相互作用よりかなり遅い)、これは、高い忠実度を有する集合的ゲートの実行を可能にする。従って、量子最適化を、単位円グラフよりも一般的であるグラフ上のMIS問題に適用することが可能である。
【０１４０】
単位円グラフについての最大独立集合
理論に拘束されることなく、この節は、本開示に記載される技術に従って解かれ得る単位円グラフ上のMIS問題のいくつかの局面を扱う。図5は、いくつかの態様による円508により示される、頂点502、504を有する単位円グラフを示し、該頂点が互いに半径r以内にある場合、該頂点のいくつかは、エッジ506により連結される。問題は、
【数２３１】
2021536610.tif 000242
のエネルギーの最小化として定式化され得る。この問題は、該問題を最大次数3の平面グラフ上でMISから簡略化することによりNP-完全であると証明され得る。いくつかの態様において、本明細書で議論されるリュードベリハミルトニアン(等式2)と関連するコンピューター的複雑性の分析が類似した簡略化に基づくので、以下の定理およびその証明を検討することは、有益であり得る:単位円グラフ上のMISは、NP-完全である。
【０１４１】
理論に拘束されることなく、この定理は、以下のように証明され得る:(1)最大次数3を有する平面グラフ上のMISは、NP-完全である。(2)頂点Vおよびエッジεを有し、最大次数3を有する平面グラフ
【数２３２】
2021536610.tif 000243
領域を使用して、その頂点が整数座標にあり、そのエッジが整数iおよびj、ならびにグリッド間隔
【数２３３】
2021536610.tif 000244
上の線セグメントを連結することにより引かれるような様式で、平面に埋め込まれ得る。(3)ヒトは、
【数２３４】
2021536610.tif 000245
の各エッジ[u, v]を、頂点VおよびエッジEを有するUDグラフG=(V, E)が構築され得るような様式で、アンシラリー頂点の偶数2ku,vを有する経路により入れ替え得る。
【数２３５】
2021536610.tif 000246
を有することを立証することは、簡単である。
【０１４２】
いくつかの態様において、この定理は、HUDの基底状態エネルギーが-α'Δよりも低いかどうかを決定することがNP-完全であることを示す。いくつかの態様において、この定理の証明における変換は、2D面中のアンシラリー頂点の実際の位置を完全には決定しない。いくつかの態様において、この変換の要件と一致する特定の配置が、特定され得る。一旦リュードベリ相互作用が考慮されると、キュービットの各対の間の相互作用強度は、原子の距離を考慮に入れた様式で、一定であり得る。
【０１４３】
いくつかの態様において、グラフ
【数２３６】
2021536610.tif 000247
のエッジ[u, v]がグリッド上に埋め込まれたと仮定すると、このエッジの長さは、
【数２３７】
2021536610.tif 000248
はグリッド単位長である）
により示され得る。まず、アンシラリー頂点が、エッジに沿って
【数２３８】
2021536610.tif 000249
グリッド点に配置され得、該エッジを長さ
【数２３９】
2021536610.tif 000250
セグメントに分割し得る。整数
【数２４０】
2021536610.tif 000251
が選択され得、等しく間隔を空けた2kアンシラリー頂点が、各セグメントに沿って配置され得、該セグメントを、等しい長さ
【数２４１】
2021536610.tif 000252
の2k+1個の断片に分割し得る。いくつかの態様において、変則（irregular）頂点が、各エッジ上のアンシラリースピンの数が偶数であることを確実にするように、使用され得る。しかし、いくつかの態様において、各エッジ上のスピンの総数は、異なり得る。
【数２４２】
2021536610.tif 000253
が偶数であるである場合、１つのセグメントが選択され得、このセグメントの中央に近い
【数２４３】
2021536610.tif 000254
アンシラリー頂点が、決定されるべきいくつかの整数
【数２４４】
2021536610.tif 000255
アンシラリー頂点と入れ替えられ得る。かかるセグメントは、「変則セグメント」と言われ得、変則セグメントの中央の頂点は、変則頂点と言われ得る。いくつかの態様において、これらの例外は、アンシラリー頂点が解かれるべき問題の性質を変更することなく独立集合束縛を移すことを確実にするために、各エッジ
【数２４５】
2021536610.tif 000256
に沿ったアンシラリー頂点の総数2ku,vが偶数であることを確実にするように作られる。この配置に従うと、アンシラリー頂点の最近傍距離は、dまたはDのいずれかであり得る。単位円半径をr=D+0+に設定することにより、単位円グラフGが生じ得る。頂点の位置は、
【数２４６】
2021536610.tif 000257
により標識され得る。いくつかの態様において、配置は、自由に選択されたパラメーターkおよび
【数２４７】
2021536610.tif 000258
に依存する。従って、本開示を通じて記載されるように、困難な問題は、単位円グラフを形成する頂点の配置に対するMIS問題に変換され得る。
【０１４４】
理論に拘束されることなく、いくつかの態様により、この様式において構築された単位円グラフの型上の最大独立集合のいくつかの特性は、注目され得る。まず、いくつかの態様において、G上の最大独立集合は、
【数２４８】
2021536610.tif 000259
上の最大独立集合が唯一のものであったとしても、一般的に縮退している。G上のMIS-状態の特定の組、例えば、頂点Vに対する
【数２４９】
2021536610.tif 000260
の特性が考慮され得る。理論に拘束されることなく、かかる状態が常に存在し得ることを調べるために、
【数２５０】
2021536610.tif 000261
から以下のように構築される:２つのキュービットの状態が、２つの頂点
【数２５１】
2021536610.tif 000262
に対応すると仮定した場合、uが状態
【数２５２】
2021536610.tif 000263
にある(またはその逆)場合、2ku,vアンシラリー頂点は、(反強磁性的に)秩序だった状態においてuおよびvを連結するエッジ上に配置され得、該秩序だった状態において、キュービットは、状態
【数２５３】
2021536610.tif 000264
に交互にある。他の場合において、uおよびvの両方が状態
【数２５４】
2021536610.tif 000265
にある場合、アンシラリー頂点は、類似した秩序だった状態に配置され得る。この後者の態様の場合、例えば、２つの隣接するキュービットの両方が状態
【数２５５】
2021536610.tif 000266
にある例の態様において、ドメイン壁が導入され得る。エッジに沿ったこのドメイン壁の位置は、無関係である。両方の場合において、エッジに沿った2ku,v個のアンシラリー頂点の半分は、状態
【数２５６】
2021536610.tif 000267
にある。従って、上記定理により、このプロセスを
【数２５７】
2021536610.tif 000268
から構築される状態は、G上のMIS-状態である。
【０１４５】
理論に拘束されることなく、いくつかの態様により、エッジが90°の角度で交わる点の周囲のこれらのMIS-状態の構造は、さらに特定され得る。かかる点は、3個のエッジが図2Aにおける点216などの頂点で交わるジャンクション、または図2Aにおける202などのコーナーのいずれかであり得る。各コーナーまたはジャンクションに近いキュービットが秩序だっている(例えば、１つおきの頂点が状態
【数２５８】
2021536610.tif 000269
にある状態において)ようなMIS-状態
【数２５９】
2021536610.tif 000270
がある。例えば、全てのコーナーおよびジャンクションについて、距離
【数２６０】
2021536610.tif 000271
以内の全ての頂点が、ドメイン壁を有さない２つの可能な秩序だった構成の１つにあるような最大独立集合が存在する。理論に拘束されることなく、これは、いくつかの態様において、上記議論から、エッジ
【数２６１】
2021536610.tif 000272
に沿った任意のドメイン壁の位置が無関係であることに注目することにより、たどられる。例えば、任意のドメイン壁は、グリッド点上の任意の頂点に対するその距離が
【数２６２】
2021536610.tif 000273
に沿って動かされ得る。ドメイン壁を動かす可能性は、例えば、下記表題リュードベリ問題のNP-完全性の節において議論される完全なリュードベリ問題（full Rydberg problem）の議論においても利用される。
【０１４６】
コーナーおよびジャンクションについてのモデル離調
理論に拘束されることなく、上記簡略化のリュードベリ相互作用を使用する実行への適用を示すために、単純なモデルを実行して、いくつかの実行の局面を説明し得る。このモデルは、特定の頂点の扱いを含むがこれに限定されない本開示の態様のいくつかの局面および利益を示すために使用され得る。例えば、UDグラフについてのMIS-ハミルトニアンHUDに類似したハミルトニアンが、単位円半径を超える相互作用を導入して考慮され得る。リュードベリ系における状況に類似して、これらのさらなる相互作用は、基底状態の変化を生じ得るエネルギーシフトを生じ得、従って、MISのエンコードを無効にする（invalidate）。換言すれば、かかるさらなる相互作用は、エンコードされたMIS問題の基底状態を、MIS問題に対する解とミスマッチ（mismatch）であるものにし得る。この問題を解くために、局所離調が、さらなる相互作用を相殺するために使用され得る。
【０１４７】
理論に拘束されることなく、モデルの態様は、
【数２６３】
2021536610.tif 000274
により与えられ得る。W=0およびΔv=Δについて、Hmodelは、等式25に記載されるハミルトニアンHUDに簡略化され得る。W>0について、該Hmodelは、単位円半径rを超える相互作用を含み、従って、リュードベリハミルトニアンに対する一次近似として考慮され得る。
【０１４８】
いくつかの態様において、単位円グラフGに対応する表題「単位円グラフについての最大独立集合」の節において記載されるキュービット配置の場合、および
【数２６４】
2021536610.tif 000275
の場合において、ほとんどのキュービットは、G上のそれらの隣接体とのみ相互作用し、例外は、コーナー(図2Aにおけるキュービット202など)またはジャンクション(図2Aにおけるキュービット216など)に近いキュービットである。かかる幾何学的配置において、G上の隣接しないいくつかのキュービットは、強さW>0でもって相互作用する。いくつかの態様において、これらの相互作用は、MIS-ハミルトニアンHPと比べて、基底状態を変化させる。
【０１４９】
図11A〜11Cは、いくつかの態様による単位円グラフに対応する頂点配置の例を示し、ここで、モデルHmodel(等式26)の基底状態は、最大独立集合に対応しない。図11Aにおけるこのグラフ上の最大独立集合は、頂点1106および1156などの黒の頂点により示される。頂点1102、1104、1152などの白の頂点は、別の独立集合を示し、そのサイズは、１つの頂点による最大独立集合のサイズより小さい。Wが大きすぎる場合、コーナー1102およびジャンクション1152に近い対角線（diagonal）1130、1160上のさらなる相互作用は、MIS-状態を嫌い（disfavor）;代わりに、黒のキュービットが状態
【数２６５】
2021536610.tif 000276
にある状態が基底状態となる。本開示を通じて記載されるように、この問題は、コーナーおよびジャンクションのそれぞれについて、図11Bおよび11Cに示されるような問題のある構造において局所的に離調を変化させることにより、解かれ得る。
【０１５０】
いくつかの態様において、HUDのMIS-状態が有限のWであってもHmodelの基底状態にとどまるような離調パターンΔvを見出すことが望ましい。換言すれば、グラフのMIS解をグラフの他の解よりもエネルギー的に好ましくする(即ち、それを系の基底状態にカップリングさせる)離調パターンを見出すことが望ましい。いくつかの態様において、関連するキュービット配置について、HUDとHmodelの相互作用は、コーナーおよびジャンクションの周囲においてのみ異なる。従って、Δvは、個々におよび別々に考慮され得るこれらの構造を除いて全ての場所で(例えば、全てのキュービットについて)、Δv=Δに設定され得る。
【０１５１】
表題「単位円グラフについての最大独立集合」の節において上記で議論したような図11Bに示されるコーナーに関するいくつかの態様において、コーナーキュービット1102およびその２つの隣接体1106が、以下の２つの秩序だった構成の１つにあるような少なくとも１つのMIS-状態
【数２６６】
2021536610.tif 000277
が存在する:コーナーキュービット1102が状態
【数２６７】
2021536610.tif 000278
または、コーナーキュービット1102が状態
【数２６８】
2021536610.tif 000279
は、第１の頂点が状態
【数２６９】
2021536610.tif 000280
にある３つの頂点の状態である。離調は、これらの２つの構成のみがHmodelの基底状態に関連するような様式で、これらの３つのキュービットについて選択され得る。即ち、離調は、全ての可能なキュービット構成のエネルギーが、コーナー上のキュービットを01010または10101などであるがこれらに限定されない２つの秩序だった状態の１つに配置することにより常に低下され得るように、特定され得る。いくつかの態様において、これは、コーナーキュービット1102の離調が
【数２７０】
2021536610.tif 000281
であるように選択され、その２つの隣接体1106の離調が
【数２７１】
2021536610.tif 000282
であるように選択された場合に、達成され得る。ここで、
【数２７２】
2021536610.tif 000283
は自由に選択され得る(トリビアルな束縛Δv<Uまで、ここで、Uは、非常に近い２つの頂点についての相互作用の強さである)。いくつかの態様において、異なる
【数２７３】
2021536610.tif 000284
を選択することについていくつかの利点があり得、本明細書に記載される値は、例として議論される。いくつかの態様において、離調のこの選択は、３つのキュービット上の２つの秩序だった構成の間のエネルギー差をΔまで回復させ、これは、状態
【数２７４】
2021536610.tif 000285
にあるさらなる頂点キュービットに対応する。理論に拘束されることなく、トリビアルな定数(および下記で議論するジャンクションからの寄与)まで、HmodelおよびHUDは、各コーナーが上記秩序だった構成の１つにある全ての状態で同一である。これは、特に、HUDの１つの基底状態を含み、これは、MIS-状態に対応する。いくつかの態様によると、この型のものではない全ての状態は、構造（construction）によりHmodelに関してより高いエネルギーを有する。
【０１５２】
図11Cに関するいくつかの態様において、ジャンクションは、類似した離調技術を用いて扱われ得る。理論に拘束されることなく、中央キュービット1152が状態
【数２７５】
2021536610.tif 000286
にあるか、または中央キュービット1152が状態
【数２７６】
2021536610.tif 000287
にあるような少なくとも１つのMISが存在する。次数-3ジャンクションキュービット1152の離調(ΔJと示される)は、ΔJ=Δ+W+3εとして選択され得、その３つの隣接体1156の離調(ΔN'と示される)は、ΔN'=Δ+W+εとして選択され得る。いくつかの態様において、この選択は、ジャンクション上の２つの秩序だった状態の１つを、任意の他の状態よりもエネルギー的に好ましくし、それらのエネルギー差を正確に2Δまで回復させる。本開示に基づいて、εの他の値が選択され得ることを理解すべきである。
【０１５３】
いくつかの態様において、上記した離調パターンを使用することにより、HUDおよびHmodelの作用は、非限定的な理論的目的のために、少なくとも１つのMIS-状態について同一である。さらに、いくつかの態様は、選択された離調が任意の他の構成のエネルギーを低下させないことを確実にする。従って、Hmodelの基底状態は、HUDの基底状態であり、対応する単位円グラフ上のMIS問題をエンコードし、その結果、該基底状態がMIS問題に対する解である。
【０１５４】
リュードベリ問題のNP-完全性
理論に拘束されることなく、いくつかの態様において、上記した離調モデルは、リュードベリハミルトニアンの場合に適用され得、それにより、Ωv=0の場合にHRydの基底状態エネルギーが所定の閾域未満であるかどうかを決定することがNP-完全であることを示し、ここで、原子は、少なくとも２次元において任意に配置され得る。主な思想は類似しているが、無限範囲のリュードベリ相互作用は、より多くの説明を正当化する（warrant）。
【０１５５】
上記したように、いくつかの態様において、長さおよび相互作用スケールを分離する離調パターンを適用することが可能である。これは、近くにあるキュービット間の相互作用を、グラフG上で大いに離れているキュービット間の相互作用から切り離し得るように、リュードベリ相互作用が迅速に減衰することを一部の理由として可能である。例えば、遠いキュービット間の相互作用は、十分大きなkが選択される場合、無視され得る。かかる態様において、系の個々の部分構造は、理論の目的のために、別々に扱われ得る。
【０１５６】
いくつかの態様において、リュードベリハミルトニアンの低エネルギー領域は、かなりより単純な有効スピンモデルにマップされ得る。例えば、キュービットのクラスターは、２つの構成のみが各クラスターに関連するように、特定の離調パターンを用いてアドレシングされ（address）得る。いくつかの態様において、得られた有効擬スピン（pseudo-spin）は、MISハミルトニアンにより記述される。これは、リュードベリハミルトニアンの基底状態がMIS解であるように、MIS問題を、最大次数3を有する平面グラフにエンコードすることを可能にする。この節における議論は、有効モデルに対するマッピングの詳細を証明する。
【０１５７】
まず、長さスケールの分離に関して、リュードベリ相互作用は、冪乗則として距離と共に減衰し得、従って、相互作用が存在するのを終わる長さスケールを画定しない。それにも関わらず、いくつかの態様において、例示的なキュービット配置は、２つの長さスケールを導入する:(1)２つのキュービットの間の最接近距離d、および(2)グリッド長g。これらの長さスケールは、因子（factor）g=d(2k+1)により分離され、該因子は、平面グラフ
【数２７７】
2021536610.tif 000288
の単位円グラフGへの変換において任意に選択され得る。かかる実行を伴ういくつかの態様において、「近い」キュービット間の相互作用は、例えば、本開示に記載されるように十分に大きなkが選択される場合、「遠い」キュービット間の相互作用から分離され得る。
【０１５８】
系における最接近キュービットは、距離dだけ離れ、従って、
【数２７８】
2021536610.tif 000289
の強さで相互作用する。これは、エネルギー
【数２７９】
2021536610.tif 000290
からGへの変換を特定するパラメーターkの選択に依存する。
【０１５９】
理論に拘束されることなく、２つのキュービットは、それらのxまたはy座標が少なくともg(グリッド長)だけ異なる場合、「遠い」と記述され得る。単一キュービットと全ての遠いキュービットとの相互作用エネルギーは:
【数２８０】
2021536610.tif 000291
により上方が束縛され（upper bounded）得る。
【０１６０】
いくつかの態様において、この束縛は、キュービットが2D面における各可能なキュービット位置(即ち、全てのグリッド線に沿って)で状態
【数２８１】
2021536610.tif 000292
に配置され得る系を考慮することにより、誘導され得る。Edistは、かかる系における単一キュービットと上記の意味で遠い全ての他のキュービットの相互作用エネルギーである。これは、任意のグラフにおける単一キュービットと全ての遠いキュービットの最大相互作用エネルギーに対する上方束縛であり、該任意のグラフ自体は、
【数２８２】
2021536610.tif 000293
は、リーマンゼータ関数である）
により上方束縛され得る。いくつかの態様において、d/g=1/(2k+1)であるので、スピンと全ての遠いスピンとの相互作用エネルギーは、
【数２８３】
2021536610.tif 000294
として比例し得る。平面における元の平面グラフ
【数２８４】
2021536610.tif 000295
領域を用いてなされ得るので、スピンの総数は、
【数２８５】
2021536610.tif 000296
として比例し得る。従って、いくつかの態様において、互いに関して遠いスピンの全ての対の間の相互作用の寄与は、
【数２８６】
2021536610.tif 000297
により束縛され得る。いくつかの態様において、kは、これらの寄与が無視され得るように、十分に大きく選択され得る。かかる態様において、基底状態は、長距離の相互作用のために変化しない。必要なkは問題サイズ|V｜に関して多項式的に比例し得ることに留意のこと。
【０１６１】
有効スピンモデル
以下により詳細に記載されるように、理論に拘束されることなく、有効スピンモデルは、対応するリュードベリハミルトニアンの基底状態が
【数２８７】
2021536610.tif 000298
の最大独立集合を直接明らかにするように、最大次数3の各平面グラフ
【数２８８】
2021536610.tif 000299
原子の配置が同定され得、離調パターンが適用され得ることを示すために、開発され得る。さらに、理論に拘束されることなく、
【数２８９】
2021536610.tif 000300
の基底状態エネルギーがいくつかの閾域より低いかどうかを決定することがNP-完全であることが見られ得る。さらに、理論に拘束されることなく、特定の配置を擬スピンとして扱い、いくつかの態様の局面の非限定的な議論を単純化することが可能である。
【０１６２】
上記で議論されるモデルに類似したいくつかの態様において、単位円半径を超える相互作用(例えば、相互作用テール)は、問題があり得る。例えば、より長距離の相互作用は、上記したエンコードされたMIS問題を有する系の基底状態を、MIS解と異なるようにさせ得る。これらの相互作用は、次数3の頂点、例えば、図2Aにおける頂点キュービット216またはコーナー、例えば、図2Aにおける頂点キュービット202の近くで（close to）、より顕著であり得る。
【０１６３】
いくつかの態様において、本開示を通じて議論されるように、これらの複雑さを扱うために、長さおよび相互作用スケールが、これらの構造を単離し、これらを個々に制御するために、分離され得る。例えば、本開示で議論されるいくつかのグラフについて、種々の「特別な」頂点が定義され得る。整数グリッド座標を有するものまたは変則頂点であるもののいずれかに対応し得る特別な頂点がある。従って、特別な頂点は、
【数２９０】
2021536610.tif 000301
をUDグラフGに変換するために導入された頂点のサブセットも含む。図12Aは、いくつかの態様による最大次数3を有しグリッドに埋め込まれている平面グラフ
【数２９０−１】
2021536610.tif 000302
の例を示す。図12Aの平面グラフは、上記で議論したようにエッジキュービットを用いて連結され得る頂点キュービット1202A、1202Bを含む。
【０１６４】
図12Bは、いくつかの態様によるk=7および
【数２９１】
2021536610.tif 000303
を有する図12Aのグラフを実行するスピン配置を示す。iと示される各特別な頂点について、各レッグ（leg）にiおよびその2q隣接体を含む頂点の組Aiが画定され得る。qの値は、
【数２９２】
2021536610.tif 000304
であるように選択され得る。
【０１６５】
図12Bは、領域Aiを示し、これは、特別な頂点およびq=1の値を有する各レッグ上のそれらの2q隣接体に対応する。領域A1、A4、A6およびA9は、コーナーと言われ得、領域A3、A7、およびA11は、ジャンクションと言われ得る。領域A12は、オープンレッグ（open leg）と言われ得、領域A2、A5、A8、A10、A13およびA14は、直線セグメント上の特別な頂点と言われ得る。領域A10およびA14は、変則領域(例えば、頂点間の間隔が他の領域と異なるもの)と言われ得る。スピンモデルにおいて、各領域Aiは、隣接する擬スピンと相互作用する擬スピンsiにより示され得る。換言すれば、特定の領域におけるスピンは、擬スピンとして集合され（aggregate）得、これは、以下により詳細に説明するように、基底状態における特定の数の状態に制限される。２つの擬スピン状態は、Aiにおける２つの秩序だった構成に対応する。si=0およびsi=1と示されるこれらの２つの構成は、特別なスピンiが状態
【数２９３】
2021536610.tif 000305
にあり、Aiにおける全ての他のスピンが対応する完璧に秩序だった状態にある状態に対応する。各領域Aiについて、擬スピンsiが画定され得、
【数２９４】
2021536610.tif 000306
と示される)について計算され得る。状態
【数２９５】
2021536610.tif 000307
にあるAiにおけるスピンの数は、擬スピン状態siにより直接決定され得、これは、該数が、si+miq(ここで、mは、特別な頂点iの次数を示す)により与えられるからであることに留意のこと。図12Bに示されるように、集合Bi,jは、AiおよびAjを連結する経路に沿った頂点として画定され得る。かかる態様において、構築物Bi,jは、偶数の頂点を含む。異なる型の擬スピンAおよびBの基底状態は、表題「低エネルギーでの挙動」の節に関してより詳細に記載される。例えば、図12Dは、基底状態構成において見られ得るアンシラリースピンの直線セグメントに沿った3つの可能な頂点の配置を示す。図12Eは、いくつかの態様によるグラフ
【数２９６】
2021536610.tif 000308
に対応する有効スピンモデルを示す。
【０１６６】
理論に拘束されることなく、本開示を通じて記載される長さおよび相互作用スケールの分離により、２つのスピンuおよびvの間の相互作用は、これらが同じ集合
【数２９７】
2021536610.tif 000309
に属するか、または、近接する集合
【数２９８】
2021536610.tif 000310
に属する場合にのみ関連する。他の全ての相互作用項は、
【数２９９】
2021536610.tif 000311
のように消える寄与を与える。理論に拘束されることなく、総エネルギーは、
【数３００】
2021536610.tif 000312
として記述され得る。ここで、
【数３０１】
2021536610.tif 000313
は、Xにのみスピンを考慮した場合の系のエネルギーを与え、
【数３０２】
2021536610.tif 000314
は、２つの領域XおよびY中のスピンの間の相互作用エネルギーを定量する。和
【数３０３】
2021536610.tif 000315
は、Aiが空でない集合Bi,jによりAjに連結されるようにiおよびjを繰り返し、因子1/2は、二重計数を相殺する。
【０１６７】
いくつかの態様において、領域AiおよびBi,j中のいくつかのスピンの構成のみが系全体の基底状態を構築することに関連するように、離調Δvの適切な選択を適用することが可能である。いくつかのかかる構成において、基底状態についての候補として、指数関数的に多くの構成ではなく、いくつかの構成のみを考慮することが可能である。例えば、以下により詳細に議論されるように、かかる態様において、図12Cに示す領域Ai中の２つのスピンの構成のみが関連する。さらに、かかる態様において、いくつかの態様により、図12Dに示されるように、各領域Bi,j中の４つのスピンの構成のみが関連する。さらに、これらの構成は、擬スピン状態siおよびsjにより完全に決定され得る。si=1およびsj=0(またはその逆)である場合、Bi,jが完璧に秩序だった状態にある場合に、総エネルギーが最小化される。si=sj=0またはsi=sj=1である場合、最小のエネルギー状態もまた、秩序だっているが、単一ドメイン壁が領域Bi,jの中央にある。理論に拘束されることなく、これらの構成についてのエネルギー
【数３０４】
2021536610.tif 000316
により示され得、これは、
【数３０５】
2021536610.tif 000317
に留意のこと）
を生じる。Bi,jにおける状態
【数３０６】
2021536610.tif 000318
におけるスピンの数は、bi,j-sisj(ここで、2bi,jはBi,jにおけるスピンの数を与える)として記述され得る。相互作用エネルギー
【数３０７】
2021536610.tif 000319
の上記組み合わせの全てについて定数であり得る。
【０１６８】
いくつかの態様において、
【数Ｅ−１】
2021536610.tif 000320
の基底状態を含む関連のある構成領域領域における総エネルギーは、擬スピン(pseudo-spin)についての有効スピンモデル：
【数Ｅ−２】
2021536610.tif 000321
により与えられ得、ここで和
【数Ｅ−３】
2021536610.tif 000322
は、(二重に計数することなく)擬スピンの近接するペアを繰り返す。有効離調
【数Ｅ−４】
2021536610.tif 000323
(例えば擬スピンに対して、正常スピンに対する離調と同様の効果を有する離調)が導入され得、擬スピン相互作用
【数Ｅ−５】
2021536610.tif 000324
は、
【数Ｅ−６】
2021536610.tif 000325
により与えられ得る。
【０１６９】
いくつかの態様において、離調パターン
【数Ｅ−７】
2021536610.tif 000326
は、有効擬スピン離調および相互作用が均一
【数Ｅ−８】
2021536610.tif 000327
であり、
【数Ｅ−９】
2021536610.tif 000328
を満足するように選択され得る。いくつかの態様において、これらのパラメーターが上述の等式を満足するように選択される場合、リュードベリハミルトニアンの問題は、MISの問題と同等に処理され得る。長期の訂正がいくつかの小さい定数
【数Ｅ−１０】
2021536610.tif 000329
により束縛されることを確実にするために、
【数Ｅ−１１】
2021536610.tif 000330
は、
【数Ｅ−１２】
2021536610.tif 000331
であるように選択され得る。ξは、選択された離調パターンに基づいてコンピューター計算され得る。
【０１７０】
等式32におけるこの有効スピンモデルは、
【数Ｅ−１３】
2021536610.tif 000332
に対する元のMIS問題に戻って関連付けられ得る。理論に拘束されることなく、この有効スピンモデルの態様は、図12A〜12Eに関してより詳細に議論される偶数
【数Ｅ−１４】
2021536610.tif 000333
の頂点の弦でそれぞれのエッジ
【数Ｅ−１５】
2021536610.tif 000334
を置き換えることにより、
【数Ｅ−１６】
2021536610.tif 000335
から得られるグラフ
【数Ｅ−１７】
2021536610.tif 000336
に対するMIS問題に正確に対応する。これらのさらなる頂点は、表題「単位円グラフについての最大独立集合」の節における上述の議論に対する完全な類推において
【数Ｅ−１８】
2021536610.tif 000337
の最大独立集合の間に正確な対応を与える独立集合の束縛を移送する。
【０１７１】
そのため、最大次数3のそれぞれの平面グラフ
【数Ｅ−１９】
2021536610.tif 000338
について、
【数Ｅ−２０】
2021536610.tif 000339
原子の構成が同定され得、離調パターンは、対応するリュードベリハミルトニアンの基底状態が
【数Ｅ−２１】
2021536610.tif 000340
の最大独立集合を直接明らかにするように適用され得る。したがって、理論に拘束されることなく、
【数Ｅ−２２】
2021536610.tif 000341
の基底状態エネルギーがいくつかの閾値よりも低くなるかどうかを決定することがNP完全であると見られ得る。第1に、
【数Ｅ−２３】
2021536610.tif 000342
の基底状態は古典的な記述を有するので、この質問はNPにある。また、最大次数3の平面グラフである
【数Ｅ−２４】
2021536610.tif 000343
上のMISのサイズが≧aであるかどうかを決定することのNP完全問題からの簡略化のために。
【数Ｅ−２５】
2021536610.tif 000344
と推定する
【数Ｅ−２６】
2021536610.tif 000345
のMISのサイズが≧aである場合、
【数Ｅ−２７】
2021536610.tif 000346
の基底状態エネルギーは、
【数Ｅ−２８】
2021536610.tif 000347
である。
【数Ｅ−２９】
2021536610.tif 000348
のMISのサイズが≦a-1である場合、
【数Ｅ−３０】
2021536610.tif 000349
の基底状態エネルギーは、
【数Ｅ−３１】
2021536610.tif 000350
である。いくつかの態様において、
【数Ｅ−３２】
2021536610.tif 000351
を選択することにより、
【数Ｅ−３３】
2021536610.tif 000352
の基底状態エネルギーが
【数Ｅ−３４】
2021536610.tif 000353
である場合およびその場合にのみ、
【数Ｅ−３５】
2021536610.tif 000354
のMISは、≧aのサイズを有する。
【０１７２】
低エネルギーでの挙動
理論に拘束されることなく、リュードベリハミルトニアンの基底状態の局面の態様は以下に記載される。リュードベリハミルトニアンの例示的局面は、より低いエネルギーで、基底状態は、エンコードされた問題に対するMIS解に対応することを示す。したがって、例示的実行において、問題が適切にエンコードされる場合、対応するキュービットをより低いエネルギー状態に遷移することにより、エンコードされた問題に対する解に対応する基底状態における系が生じ得る。理論に拘束されることなく、かかる遷移の議論は、以前の節に議論される「擬スピン」を参照することにより補助され得る。
【０１７３】
いくつかの態様において、
【数Ｅ−３６】
2021536610.tif 000355
の基底状態は、それぞれのスピンの離調が本明細書に記載される技術に従って選択される場合に、関連のあるUDグラフ上の最大独立集合に対応する。最大独立集合は、独立性の特性を破ることなく頂点が付加され得ない(例えば2つの近接する頂点の両方が状態|1>であり得ない)独立集合をいう。最も大きな最大独立集合は最大の独立集合である。かかる集合に対応する構成のために、2つの近接するスピンは状態|1>にあり得ず(独立性)、全てのその近接体が状態|0>にある場合、スピンは状態|0>にはあり得ない(最大性(maximality))。
【０１７４】
リュードベリハミルトニアンのいくつかの態様において、全ての頂点上の離調
【数Ｅ−３７】
2021536610.tif 000356
が
【数Ｅ−３８】
2021536610.tif 000357
(式中、
【数Ｅ−３９】
2021536610.tif 000358
は
【数Ｅ−４０】
2021536610.tif 000359
上で近接する2つの頂点の間の最大ユークリッド距離である)に従う限りは、系が
【数Ｅ−４１】
2021536610.tif 000360
の基底状態にある場合、
【数Ｅ−４２】
2021536610.tif 000361
上の近接する2つの頂点は同時に状態|1>にはあり得ない。
【０１７５】
図13Aは、いくつかの態様による、次数3の頂点でのキュービットのグラフの一部を示す。グラフは、キュービット1302A、1302B、1304、1306および1310を含む。図13Bは、いくつかの態様による、次数3の2つの頂点を有する同様のグラフを示す。図13Bは、次数3の頂点1314、1324、およびキュービット1312A、1312B、1316、1318、1320、1322A、1322B、1326、1328、1330を示す。MISハミルトニアンについてΔ>0は、スピンが状態|1>および従って基底状態の最大性にあることをエネルギー的に好むのに十分であるが、これは必ずしもリュードベリハミルトニアンについて真実ではない。これは一部に、本開示を通じて議論される長距離相互作用のためである。この場合、エネルギー利得
【数Ｅ−４３】
2021536610.tif 000362
は、スピン
【数Ｅ−４４】
2021536610.tif 000363
の相互作用エネルギーと関連するエネルギーコストを超える必要があり、全ての他のスピンは状態|1>である。最大性を保証する必要とされる離調を決定するために、(
【数Ｅ−４５】
2021536610.tif 000364
上の)近接体が全て状態|0>にある(図13A中のキュービット1306または図13B中のキュービット1316および1326などの)スピン
【数Ｅ−４６】
2021536610.tif 000365
の相互作用エネルギーは、系の残りに束縛され得る。束縛を得るために、寄与(contribution)へのエネルギーは、遠いスピン(
【数Ｅ−４７】
2021536610.tif 000366
により束縛される、等式29参照)、および残りの「近い」スピン
【数Ｅ−４８】
2021536610.tif 000367
からの寄与から分割され得る。後者の近いスピンからの寄与は、スピン
【数Ｅ−４９】
2021536610.tif 000368
(1306、1316、1326)が次数3の頂点1304に直接近接している場合に最大である。
【数Ｅ−５０】
2021536610.tif 000369
である限り、2つの近接するスピンは同時に状態|1>にあり得ることはないので、それは、
【数Ｅ−５１】
2021536610.tif 000370
により上方(upper)で束縛され得る。第1の項は、同じグリッドライン上のスピン(図13Aにおけるキュービット1304、1310および図13Bにおけるキュービット1314、1320または1324、1330など)とのスピン
【数Ｅ−５２】
2021536610.tif 000371
の最大相互作用に対応し、一方で第2の項は、2つの垂直なグリッドライン上のスピン(図13Aにおける1302A、1302Bまたは図13Bにおける1312A、1312B、1322A、1322Bなど)との相互作用を束縛する。
【０１７６】
図13Aに示される構成は、いくつかの態様による、3つのキュービット(1304、1306)が同じ状態|0>にある非最大独立集合構成に対応する。離調がグリッド上に埋め込まれる
【数Ｅ−５３】
2021536610.tif 000372
は、図13Bに示される構成は、直線のセグメントに沿った2つのドメイン壁1318、1328を有する別の非最大独立集合構成である。以下により詳細に議論されるように、2つのドメイン壁を併合させることにより(すなわち1つのみのドメイン壁が存在するように直線のセグメントに沿ってスピンをフリップすることにより)、もう1つのスピンが状態|1>にある欠陥を有さない構成を得ることが可能である。これらの2つの構成の間の相互作用エネルギーの増加は、
【数Ｅ−５４】
2021536610.tif 000373
により束縛され得、ここで1つのドメイン壁を有する状態は、最も低いエネルギー構成である。したがって、頂点1314、1324などの2つの特別な頂点を連結する任意の所定のセグメントについて、多くて1つのドメイン壁を含むことがエネルギー的に好ましい。
【０１７７】
そのため、いくつかの態様において、リュードベリハミルトニアンの基底状態中のスピンの構成は、
【数Ｅ−５５】
2021536610.tif 000374
である場合に、関連のあるUDグラフ(最近傍の近接体の間のエッジ)上の最大独立集合に対応する。
【０１７８】
直線のセグメント
図13Bは、いくつかの態様による、例示的な直線のセグメントの擬スピンを示す。以下に説明されるように、かかるセグメントは、図12Dに示される最大で3つの状態において見られ得る。
【０１７９】
【数Ｅ−５６】
2021536610.tif 000375
上のスピンは、いわゆる2つ(それ以上ではない)の近接するスピンが状態|0>にあるドメイン壁まで、スピンが状態|0>および|1>に交互にある構成などのある秩序だった構成にある。
【数Ｅ−５７】
2021536610.tif 000376
上のMIS構成は、いくつかの態様により、図13Bにおける1314、1324などの2つの特別な頂点
【数Ｅ−５８】
2021536610.tif 000377
を連結するスピンの任意のアレイ上に多くて1つのかかるドメイン壁を有する。リュードベリ系の基底状態がこの特性を守ることを確実にするために、離調は十分に大きく選択され得る。例えば、かかる直線のセグメントが
【数Ｅ−５９】
2021536610.tif 000378
のドメイン壁を有するある秩序だった状態にあることを仮定すると、2つのかかるドメイン壁(1318、1328)が合される場合、さらなるスピン
【数Ｅ−６０】
2021536610.tif 000379
は、状態|0>から状態|1>へとフリップされ得、総エネルギーへの単一粒子の寄与が
【数Ｅ−６１】
2021536610.tif 000380
だけ低下される。相互作用エネルギーにおける対応する差は、ドメイン壁の距離に伴って増大し、例えば図13Bに示されるように、2つのドメイン壁が最初に、2つのジャンクションを連結するセグメントの反対の末端にある場合に差は最大である。これは
【数Ｅ−６２】
2021536610.tif 000381
により束縛され得、ここで
【数Ｅ−６３】
2021536610.tif 000382
である。
【０１８０】
いくつかの態様により、この束縛は、図13Bを参照して理解され得、ここで0ドメイン壁構成は、真ん中のバー1340(すなわちドメイン壁の間)上の秩序だったスピンを1原子左にシフトさせ、次いで右のジャンクションの次にあるスピンを状態|1>にフリップすることにより、2つのドメイン壁を有するものから得られ得る。したがって、第1の和は、H形状の真ん中のバーと側方との間の相互作用に対応し、最後の和は、新たにフリップされたスピンからの追加の(extra)相互作用である。したがって、(
【数Ｅ−６４】
2021536610.tif 000383
について)
【数Ｅ−６５】
2021536610.tif 000384
である場合に、直線のセグメントに沿って2つの近接するドメイン壁を併合させることが好ましい。
【０１８１】
そのため、
【数Ｅ−６６】
2021536610.tif 000385
について、リュードベリハミルトニアンの基底状態は、1セグメント当たり多くて1ドメイン壁を有する、2つの特別な頂点を連結する全てのセグメント上で秩序だてられる。これは図12Dを参照してなされる低エネルギー領域の分析を構造
【数Ｅ−６７】
2021536610.tif 000386
の3つのみの構成に制限することが可能であるという仮定を正当化する。第1の構成において、全てのスピンは、構造
【数Ｅ−６８】
2021536610.tif 000387
のいずれかの末端上で異なる状態に交互になる。第2の構成において、構造
【数Ｅ−６９】
2021536610.tif 000388
のいずれかの末端上のスピン状態は、間に1つのドメイン壁を伴って0に等しい。第3の構成において、構造
【数Ｅ−７０】
2021536610.tif 000389
のいずれかの末端のスピン状態は、間に1つのドメイン壁を伴って1に等しい。全てのこれらのスピンについての離調は、上述の範囲内で等しくなるように設定され得、これは
【数Ｅ−７１】
2021536610.tif 000390
により表示され得る。
【０１８２】
以下に、それぞれのレグ(leg)上で頂点
【数Ｅ−７２】
2021536610.tif 000391
の近接体からなる特別な構造
【数Ｅ−７３】
2021536610.tif 000392
の態様をより詳細に記載する。この議論は、1つのレグ当たり多くて1つのドメイン壁を有する
【数Ｅ−７４】
2021536610.tif 000393
において秩序だった状態に制限され得る。離調パターンは、任意のかかるドメイン壁が、構造
【数Ｅ−７５】
2021536610.tif 000394
の中からスピン
【数Ｅ−７６】
2021536610.tif 000395
からエネルギー的に押しのけられるように、
【数Ｅ−７７】
2021536610.tif 000396
においてスピンについて選択され得る。理論に拘束されることなく、かかる離調により、
【数Ｅ−７８】
2021536610.tif 000397
上の2つのみの秩序だった状態は、基底状態について考慮される必要がある。
【０１８３】
コーナー
図12Cの態様に示されるものなどの、擬スピンとしてまとめて処理され得るコーナー頂点および2つのレグ上のスピンが最初に考慮される。
【数Ｅ−７９】
2021536610.tif 000398
と一致する離調パターンは、2つのみの構成が低いエネルギー領域において(例えば基底状態について)関連があるように適用され得る。コーナーにわたり、
【数Ｅ−８０】
2021536610.tif 000399
によりそれぞれ示され得るコーナースピンの状態|0>または|1>に対応する2つの秩序だった状態がある。
【０１８４】
いくつかの態様において、コーナースピンが状態|0>にある場合、ドメイン壁が形成され得、ここでレグの1つの上でコーナーから
【数Ｅ−８１】
2021536610.tif 000400
の距離の2つのスピンは状態|0>にある。ドメイン壁は、スピン
【数Ｅ−８２】
2021536610.tif 000401
の状態をフリップすることにより1単位(すなわち
【数Ｅ−８３】
2021536610.tif 000402
)だけ移動され得る。相互作用エネルギーはこのプロセスで増加する。その量は、式中
【数Ｅ−８４】
2021536610.tif 000403
である、
【数Ｅ−８５】
2021536610.tif 000404
により束縛され得る。
【０１８５】
理論に拘束されることなく、この束縛は以下のように理解され得る。効果的に、1つのスピン励起は、1つの部位だけコーナーの方に移動される。同じレグ上の全てのスピンを伴うこの励起の相互作用エネルギーは、低減され(
【数Ｅ−８６】
2021536610.tif 000405
の場合など)、従って0により上方に束縛されるが、他のレグ上の全てのスピンを伴う相互作用エネルギーは増加する。このレグ上の任意の欠陥はこの相互作用エネルギーを減少させるので、他のレグ上の全てのスピンが完全に秩序だった状態である場合にエネルギーは最大化され得、等式39において束縛を与える。
【０１８６】
このプロセスにおいて相互作用エネルギーは増加し得るが、単一粒子項から総エネルギーへの寄与は、
【数Ｅ−８７】
2021536610.tif 000406
だけ変化する。離調の選択に応じて、これは、コーナースピンから離れて1単位だけドメイン壁を移動させることがエネルギー的に好ましいように、エネルギー利得をもたらし得る。したがって、それぞれのレグ上の最初の
【数Ｅ−８８】
2021536610.tif 000407
スピンが完全に秩序だった状態にある場合、コーナースピンが状態|0>であり、スピンについての離調が
【数Ｅ−８９】
2021536610.tif 000408
を満たす場合に、エネルギーは最小化される。
【数Ｅ−９０】
2021536610.tif 000409
【０１８７】
同様に、コーナースピンが状態|1>にある場合、それぞれのレグ上の最初の
【数Ｅ−９１】
2021536610.tif 000410
スピンが完全に秩序だった場合にあり、離調が
【数Ｅ−９２】
2021536610.tif 000411
を満たし、式中
【数Ｅ−９３】
2021536610.tif 000412
であれば、エネルギーは最小化される。
【０１８８】
等式40、41の条件は、選択(
【数Ｅ−９４】
2021536610.tif 000413
について)
【数Ｅ−９５】
2021536610.tif 000414
により満足され得る。
【０１８９】
いくつかの態様において、これらの和は、収束性(convergent)であり、数値的に効率的に評価され得る。
【数Ｅ−９６】
2021536610.tif 000415
は、
【数Ｅ−９７】
2021536610.tif 000416
とともに単調に減少し、大きな
【数Ｅ−９８】
2021536610.tif 000417
について
【数Ｅ−９９】
2021536610.tif 000418
に達する。さらに、このシーケンスにおける
【数Ｅ−１００】
2021536610.tif 000419
の最大値は、
【数Ｅ−１０１】
2021536610.tif 000420
と評価され得る。そのため、コーナーのレグに沿った離調が必要な範囲内にあるように、
【数Ｅ−１０２】
2021536610.tif 000421
を選択することが可能である。
【０１９０】
上述の離調パターンおよび選択
【数Ｅ−１０３】
2021536610.tif 000422
により、基底状態構成は必ず、コーナー構造を形成する
【数Ｅ−１０４】
2021536610.tif 000423
スピンが2つの秩序だった状態の1つであるようなものである。これらの状態は、コーナースピンの対応する状態(|0>および|1>)に従って、
【数Ｅ−１０５】
2021536610.tif 000424
として標識され得る。
【０１９１】
等式43、44における選択は、
【数Ｅ−１０６】
2021536610.tif 000425
と示されるコーナースピンの離調を除き全てのスピン上の離調を固定することに注意。これは、基底状態についての2つの関連のある構成の間の相対エネルギー
【数Ｅ−１０７】
2021536610.tif 000426
を調整することを可能にする。理論に拘束されることなく、この差を計算するために、量
【数Ｅ−１０８】
2021536610.tif 000427
は、2つのスピン構成の間の相互作用エネルギーの差
【数Ｅ−１０９】
2021536610.tif 000428
として定義され得る。
【０１９２】
同様に、理論に拘束されることなく、単一粒子項のために2つの構成のエネルギーの差(
【数Ｅ−１１０】
2021536610.tif 000429
)は：
【数Ｅ−１１１】
2021536610.tif 000430
として計算され得る。
【０１９３】
コーナー構造
【数Ｅ−１１２】
2021536610.tif 000431
について、これは
【数Ｅ−１１３】
2021536610.tif 000432
と評価され得、コーナースピンの離調により十分に調整され得る。したがって、いくつかの態様において、コーナー構造は、2つのみの構成を有するものとして処理され得る。
【０１９４】
ジャンクション
いくつかの態様において、図13Aに示されるものなどのジャンクションは、コーナーと同様の方法で処理され得る。例えば、ジャンクションでのスピンおよび近接するスピンは、擬スピンとして処理され得る。いくつかの態様により、ジャンクションのレグ上の離調パターンは、基底状態においてジャンクションが2つの秩序だった構成の1つのみであり得るようにドメイン壁をジャンクションから押しのけることがエネルギー的に好ましくあるように選択され得る。この方法において、ジャンクションはまた、3方向ジャンクション頂点の状態により画定される多くて2つの状態により記述され得る。
【０１９５】
第1に、いくつかの態様により、状態|0>であり得る図13Aにおける次数3の頂点1304などの中心スピンを参照して、3つのレグは
【数Ｅ−１１４】
2021536610.tif 000433
により言及され得、ここで具体化のために、
【数Ｅ−１１５】
2021536610.tif 000434
は同じグリッドライン上にあり(例えば頂点1302A、1302Bから続くスピンに対応する)、
【数Ｅ−１１６】
2021536610.tif 000435
は、グリッドラインに垂直である(例えば頂点1306から続くスピンに対応する)。中心頂点からの距離
【数Ｅ−１１７】
2021536610.tif 000436
でレグ
【数Ｅ−１１８】
2021536610.tif 000437
上の2つの頂点が状態|0>にあり、そのためにドメイン壁を形成する状況において、このドメイン壁を頂点から離して1単位押すために、頂点
【数Ｅ−１１９】
2021536610.tif 000438
の状態はフリップされる必要がある。いくつかの態様において、それを行うために必要な相互作用エネルギーは
【数Ｅ−１２０】
2021536610.tif 000439
により束縛される。この束縛は、レグ
【数Ｅ−１２１】
2021536610.tif 000440
上にドメイン壁が存在するかどうか(またはそのどこ)に関係なく適用され得ることに注意。同様に、レグ
【数Ｅ−１２２】
2021536610.tif 000441
上のドメイン壁をコーナーから1単位だけ押すために必要な相互作用エネルギーは、
【数Ｅ−１２３】
2021536610.tif 000442
により束縛され得る。
【０１９６】
他の場合において、すなわち中心頂点が状態|1>にある場合、同様の束縛が見られ得る。中心頂点から距離
【数Ｅ−１２４】
2021536610.tif 000443
でレグ
【数Ｅ−１２５】
2021536610.tif 000444
上の2つの頂点が状態|0>にある場合、頂点
【数Ｅ−１２６】
2021536610.tif 000445
の状態がフリップされる場合、すなわちドメイン壁が中心から1単位だけ押しのけられる場合、相互作用エネルギーは増加する。そのため、レグ
【数Ｅ−１２７】
2021536610.tif 000446
上でドメイン壁を1単位だけ押すために必要な相互作用エネルギーは、
【数Ｅ−１２８】
2021536610.tif 000447
により束縛され得る。この束縛は、レグ
【数Ｅ−１２９】
2021536610.tif 000448
上のスピンの構成とは独立して有効(valid)であり得る。レグ
【数Ｅ−１３０】
2021536610.tif 000449
上のドメイン壁を中心から1単位だけ押すために必要な相互作用エネルギーは、
【数Ｅ−１３１】
2021536610.tif 000450
により束縛され得る。
【０１９７】
そのため、いくつかの態様において、エネルギーを最小化する状態は、離調パターンが
【数Ｅ−１３２】
2021536610.tif 000451
について
【数Ｅ−１３３】
2021536610.tif 000452
を満たし、
【数Ｅ−１３４】
2021536610.tif 000453
である場合に、それぞれのレグ上の最初の
【数Ｅ−１３５】
2021536610.tif 000454
スピン上に任意のドメイン壁を含み得ない。ここで
【数Ｅ−１３６】
2021536610.tif 000455
はレグσ上の
【数Ｅ−１３７】
2021536610.tif 000456
番目のスピンの離調を示す。理論に拘束されることなく、これは、以下：
【数Ｅ−１３８】
2021536610.tif 000457
により達成され得、式中
【数Ｅ−１３９】
2021536610.tif 000458
である。上述の選択のために、このシーケンスにおける
【数Ｅ−１４０】
2021536610.tif 000459
の最大値は、
【数Ｅ−１４１】
2021536610.tif 000460
と評価し得る。したがって、ジャンクション
【数Ｅ−１４２】
2021536610.tif 000461
のレグ上の全ての離調は、範囲
【数Ｅ−１４３】
2021536610.tif 000462
内にある。そのため、それらの全てが許容される範囲
【数Ｅ−１４４】
2021536610.tif 000463
内にあるように
【数Ｅ−１４５】
2021536610.tif 000464
を選択することが可能である。いくつかの態様において、さらなる選択
【数Ｅ−１４６】
2021536610.tif 000465
により、2つのみの秩序だった構成が基底状態に関連することが見られ得る。
【０１９８】
コーナー構造の状況と類似して、
【数Ｅ−１４７】
2021536610.tif 000466
と示されるジャンクションスピンの離調は、ジャンクションの2つの関連のある構成の間の相対的なエネルギーを調整するために使用され得る。理論に拘束されることなく、この構造における2つのスピン構成の相互作用エネルギーにおける差は、
【数Ｅ−１４８】
2021536610.tif 000467
により与えられ得、これは、
【数Ｅ−１４９】
2021536610.tif 000468
と評価され得る。同様に、単一粒子項のために2つの構成のエネルギーにおける差は、
【数Ｅ−１５０】
2021536610.tif 000469
として計算され得、これは
【数Ｅ−１５１】
2021536610.tif 000470
と評価され得る。そのため、理論に拘束されることなく、量
【数Ｅ−１５２】
2021536610.tif 000471
は、
【数Ｅ−１５３】
2021536610.tif 000472
として記述され得る。
【０１９９】
他の特別な頂点
理論に拘束されることなく、いくつかの態様は、コーナーおよびジャンクションでの頂点に加えて、上述の他の特別な頂点を含む。これらは、次数1の頂点(開放端、図12Bにおける
【数Ｅ−１５４】
2021536610.tif 000473
など)、同じグリッドライン上の2つのレグを有するグリッド点上の頂点(直線の構造、図12Bにおける
【数Ｅ−１５５】
2021536610.tif 000474
など)、および不規則な頂点(図12Bにおける
【数Ｅ−１５６】
2021536610.tif 000475
など)である。これらの特別な頂点は、以下により詳細に記載されるように擬スピンとして処理され得る。以前の2節における分析は、全てのかかる頂点について反復され得、それにより、これら2つが2つの状態の1つであると記述され得ることが示される。
【０２００】
開放端.  いくつかの態様において、エネルギーは、離調がかかる開放レグ上のスピンについて一定である場合、開放レグの末端でスピンから離れてドメイン壁が移動される場合に低下され得る。そのため、擬スピン状態は、開放レグの末端でのスピンに近接する
【数Ｅ−１５７】
2021536610.tif 000476
スピン上の2つの秩序だった構成に制限され得る。理論に拘束されることなく、かかる開放レグの2つの状態の間のエネルギーの差は、
【数Ｅ−１５８】
2021536610.tif 000477
により示され得、ここで
【数Ｅ−１５９】
2021536610.tif 000478
は次数1の頂点に対応するスピンについての離調である。後者に近接する
【数Ｅ−１６０】
2021536610.tif 000479
スピン上の均一な離調は、
【数Ｅ−１６１】
2021536610.tif 000480
と等しくなるように選択され得る。
【０２０１】
直線の構造.  いくつかの態様において、規則的な特別な頂点について、基底状態についての関連のある構成は、レグ上の全ての
【数Ｅ−１６２】
2021536610.tif 000481
スピンについての離調を
【数Ｅ−１６３】
2021536610.tif 000482
として選択することにより2つの秩序だった状態に制限され得る。この選択により、潜在的なドメイン壁を隣り合う近接領域に移動させることがエネルギー的に好ましい。理論に拘束されることなく、エネルギー差は：
【数Ｅ−１６４】
2021536610.tif 000483
により示され、ここで
【数Ｅ−１６５】
2021536610.tif 000484
は特別な頂点の離調を示す。
【０２０２】
不規則な構造.  いくつかの態様において、不規則な頂点は、直線の構造と同一に処理され得る。不規則な頂点に近いスピンの間隔は、他の場所のものよりもわずかに大きいため(例えば不規則な構造は、それぞれのエッジ上のアンシラリー頂点の数が等しくなることを確実にするために、頂点の間の間隔が、通常の構造におけるものよりも大きくなる構造として画定され得るため)、不規則な構造の離調が
【数Ｅ−１６６】
2021536610.tif 000485
よりも大きい場合、任意のドメイン壁は自然に、不規則な構造から押しのけられる。したがって、2つのみの秩序だった構成が基底状態に関連する。対応するエネルギー差は、(アンシラリー頂点がどのように構成されるかを示し得る)φの全ての選択について数値的に評価され得る。大きなφ(および
【数Ｅ−１６７】
2021536610.tif 000486
の極限において、等式60におけるものと同じ解析的表現を得ることが可能である。
【０２０３】
有効エネルギー
いくつかの態様において、擬スピンの有効離調
【数Ｅ−１６８】
2021536610.tif 000487
(基底状態における制限された(limited)状態の集合を有するように記述され得る上述の直線のセグメント、コーナー、ジャンクションおよび他の特別な頂点など)およびそれらの有効相互作用エネルギー
【数Ｅ−１６９】
2021536610.tif 000488
を決定することが可能である。いくつかの態様において、擬スピンの有効離調および有効相互作用を知ることにより、有効に解決される問題のエンコードが可能になる。
【０２０４】
有効相互作用
いくつかの態様において、かつ理論に拘束されることなく、直線のセグメント、コーナー、ジャンクションおよび他の特別な頂点に関する上述の議論は、基底状態を説明するためのそれぞれの領域
【数Ｅ−１７０】
2021536610.tif 000489
において4つのみのスピン構成が関連するという概念に頼り得る。これらは、近接する領域
【数Ｅ−１７１】
2021536610.tif 000490
におけるスピンの4つのあり得る構成に対応する。例えば、
【数Ｅ−１７２】
2021536610.tif 000491
における離調が均一である
【数Ｅ−１７３】
2021536610.tif 000492
に設定され、
【数Ｅ−１７４】
2021536610.tif 000493
(またはその逆)の場合、最小のエネルギー構成は、
【数Ｅ−１７５】
2021536610.tif 000494
の場合は、
【数Ｅ−１７６】
2021536610.tif 000495
上の完全に秩序だった状態に対応するべきである(
【数Ｅ−１７７】
2021536610.tif 000496
)。任意の他の構成は少なくとも2個のドメイン壁を必要とする。第2に、
【数Ｅ−１７８】
2021536610.tif 000497
の場合、状態|1>の
【数Ｅ−１７９】
2021536610.tif 000498
スピンを有する秩序だった構成における
【数Ｅ−１８０】
2021536610.tif 000499
におけるスピンおよび1つのドメイン壁を配置することによりエネルギーは低下され得る。このドメイン壁の位置は、
【数Ｅ−１８１】
2021536610.tif 000500
までエネルギーを変化させないので、異なるドメイン壁構成の間の区別が必要ない。最終的に、
【数Ｅ−１８２】
2021536610.tif 000501
の場合、最小のエネルギー構成は、
【数Ｅ−１８３】
2021536610.tif 000502
の場合は、同様に、1つのドメイン壁を有する秩序だった構成により達成される。ドメイン壁の位置は関連し得ないが、
【数Ｅ−１８４】
2021536610.tif 000503
スピンのみがこの状態において状態|1>にある。
【０２０５】
理論に拘束されることなく、いくつかの態様において、これらの異なる関連のある構成の間の関連のあるエネルギーの差は、
【数Ｅ−１８５】
2021536610.tif 000504
として容易に計算され得る。
【０２０６】
【数Ｅ−１８６】
2021536610.tif 000505
が連結されない場合、これは0であり得る。その他に(else)、
【数Ｅ−１８７】
2021536610.tif 000506
であるので、この項は、大きな
【数Ｅ−１８８】
2021536610.tif 000507
の極限において
【数Ｅ−１８９】
2021536610.tif 000508
とは独立し、
【数Ｅ−１９０】
2021536610.tif 000509
と評価する。
【０２０７】
同様に、
【数Ｅ−１９１】
2021536610.tif 000510
は、
【数Ｅ−１９２】
2021536610.tif 000511
として計算され得る。
【０２０８】
したがって、いくつかの態様において、擬スピンの間の有効相互作用
【数Ｅ−１９３】
2021536610.tif 000512
は、
【数Ｅ−１９４】
2021536610.tif 000513
と記述され得る。
【０２０９】
かかる態様において、有効相互作用は、連結構造における離調
【数Ｅ−１９５】
2021536610.tif 000514
の選択のみに依存し、それにより問題を特定するための有効相互作用の制御が可能になる。
【０２１０】
有効離調
いくつかの態様において、擬スピンについての有効離調は、
【数Ｅ−１９６】
2021536610.tif 000515
により与えられ得、式中
【数Ｅ−１９７】
2021536610.tif 000516
は、特別な頂点の次数
【数Ｅ−１９８】
2021536610.tif 000517
(すなわち、コーナー頂点および直線の構造について
【数Ｅ−１９９】
2021536610.tif 000518
、ジャンクションについて
【数Ｅ−２００】
2021536610.tif 000519
および開放レグについて
【数Ｅ−２０１】
2021536610.tif 000520
)である。
【数Ｅ−２０２】
2021536610.tif 000521
の値は、スピン
【数Ｅ−２０３】
2021536610.tif 000522
の離調の選択により十分に調整され得る。これは、均一な有効離調
【数Ｅ−２０４】
2021536610.tif 000523
が擬スピンの全ての4つの型について使用され得るように選択され得る。これは
【数Ｅ−２０５】
2021536610.tif 000524
により達成され得る。
【０２１１】
これは、
【数Ｅ−２０６】
2021536610.tif 000525
と適合性であり、有効スピンモデルの実現は
【数Ｅ−２０７】
2021536610.tif 000526
と適合性である。いくつかの態様において、この不等式が満足される場合、有効モデルの解は、解決が困難な問題の解と一致し得る。
【０２１２】
例示的QAOA実行
いくつかの態様において、さらなる考察が、本開示に記載されるQAOA技術の実行に関連する。しかしながら、QAOAの枠組みは一般的であり、組合せ最適化問題を解くための種々の技術的プラットフォームに適用され得る。
【０２１３】
有限の測定試料
いくつかの態様において、有限の精度は、不連続の値のみを採り得る有限の多くの測定結果を平均することにより得られ得るので、量子ゆらぎ(射影雑音など)は、有限の精度を生じ得る。そのため、測定コストと最適化の質の間に兼ね合い(trade-off)があり得：良好な最適を見出すことは、多くの測定の犠牲を払って良好な精度を必要とし得る。さらに、目的関数値における大きな変動は、より多くの測定を要求し得るが、最適に近いMaxCut構成を見出す機会の向上を補助し得る。
【０２１４】
理論に拘束されることなく、例示として、測定射影雑音(measurement projection noize)の効果を、いくつかの例示的グラフ上のQAOAの充分なモンテカルロシミュレーションにより説明し得、ここで目的関数は、その誤りが閾値未満になるまで反復される射影測定により評価される。この数値的シミュレーションの例示的な実行の詳細は、表題「測定射影雑音による例示的シミュレーション」の節において議論される。
【０２１５】
図19は、いくつかの態様による、図18Bにおいて試験される例示的な例における測定射影雑音を説明するQAOAのモンテカルロシミュレーションを示す。シミュレーションされたQAOAは、小さなサイズの例について見出された既知の最適に基づいて、初期パラメーターの教育された(educated)選択を使用して、
【数Ｅ−２０８】
2021536610.tif 000527
のいずれかのレベルで開始する開示されたFOURIERヒューリスティックの態様により最適化される。近似比
【数Ｅ−２０９】
2021536610.tif 000528
は、
【数Ｅ−２１０】
2021536610.tif 000529
番目の測定から追跡され、
【数Ｅ−２１１】
2021536610.tif 000530
回の測定の後に見出された最小の取るに足らない(fractional)誤り
【数Ｅ−２１２】
2021536610.tif 000531
をプロットし、多くのモンテカルロ実現に対して平均する。実線および破線は、
【数Ｅ−２１３】
2021536610.tif 000532
のそれぞれで
【数Ｅ−２１４】
2021536610.tif 000533
の教育された推測で開始するFOURIER戦略を用いて最適化されるQAOAに対応し、局所的最適を見出した後に
【数Ｅ−２１５】
2021536610.tif 000534
を1だけ増加する。局所的最適は、新たな候補パラメーターベクトルノルムが0.01未満だけ変化する場合、または平均
【数Ｅ−２１６】
2021536610.tif 000535
が0.1未満だけ変化する場合に見出されると推定され得る。破-点線は、
【数Ｅ−２１７】
2021536610.tif 000536
でランダムに推測される
【数Ｅ−２１８】
2021536610.tif 000537
で開始して最適化されたQAOAに対応し、局所的最適を見出した後に
【数Ｅ−２１９】
2021536610.tif 000538
を1だけ増加する。3つの標識された点線は、QAを和
【数Ｅ−２２０】
2021536610.tif 000539
回反復して走らせ、出力状態に対する測定を実施することの結果である。
【０２１６】
図19に示されるように、QAOAは、約10〜102回の測定においてMaxCut解を見出し得、中間レベル(
【数Ｅ−２２１】
2021536610.tif 000540
)での開示される最適化の開始の態様は、最低レベル(
【数Ｅ−２２２】
2021536610.tif 000541
)での開始よりも良好である。比較において、
【数Ｅ−２２３】
2021536610.tif 000542
で開始する初期パラメーターのランダムな選択を伴ういくつかの態様は、より悪く実施され、103〜104回の測定がなされるまでMaxCut解を見出すことに失敗する。さらに、QAOAを種々のアニーリング時間を用いるQAと比較する場合、アニーリング時間
【数Ｅ−２２４】
2021536610.tif 000543
の選択がまさにこの例におけるQAOAと同様になされ得るようである。それにも関わらず、いくつかの態様において、レベル
【数Ｅ−２２５】
2021536610.tif 000544
でQAOAを走らせることは、コヒーレント時間が制限される場合に
【数Ｅ−２２６】
2021536610.tif 000545
でのQAよりもなお有利である。
【０２１７】
この例示的シミュレーションは、小さなサイズの例に限定されるが、QAOAおよびQAの良好な性能は、一般的なアニーリングスケジュールからの小さいが有意な基底状態集団により複雑にされ得る。目的関数の十分に正確な推定を得るために102回の測定が採られ得るので、
【数Ｅ−２２７】
2021536610.tif 000546
の基底状態確率は、多くのパラメーター最適化なしで基底状態を見出し得ることを意味する。いくつかの態様において、102〜103キュービットを有するより大きな問題サイズについて、最適化なしの一般的なQAOA/QAプロトコルからの基底状態確率は、系のサイズに伴い指数関数値的に減少し得るが、最適化の測定コストは、問題のサイズに伴って単に多項式的に増加する。ここで結果は、パラメーターパターンおよび開示されるヒューリスティック戦略が、最適化を強化して、基底状態の発見の確率を有意に増加させるQAOAの実際的な実行における実施目的に有用なガイドラインであることを示す。
【０２１８】
大きな問題サイズのための実行
量子機械によりMaxCut問題に対する解を実行することは、量子コヒーレント時間およびグラフ連結性により制限され得る。いくつかの態様において、コヒーレント時間に関して、QAOAは高度に有利であり：QAOAならびにその短いおよび中間のデプスの回路パラメーター化の混成の性質は、QAOAを量子デバイスに有用にする。さらに、QAOAは一般的に、小さなスペクトルギャップにより制限されず、これは、興味深い問題がコヒーレント時間内に解決され得る(または少なくとも近似される)ことを示す。
【０２１９】
ヒューリスティック的最適化QAOAの性能
ヒューリスティックス態様と腕ずくの間の比較
いくつかの態様により、例示的なヒューリスティック戦略と例示的な腕ずくのアプローチの非限定的な比較を評価し得る。例えば、図16Aは、いくつかの態様による、16頂点w4Rグラフの例示的な例におけるQAOAの最適化のための例示的なFOURIERヒューリスティックおよび腕ずくの(BF)アプローチの間の比較を示す。
【数Ｅ−２２８】
2021536610.tif 000547
が近似比である
【数Ｅ−２２９】
2021536610.tif 000548
の値を、対数線形尺度に対してQAOAレベル
【数Ｅ−２３０】
2021536610.tif 000549
の関数としてプロットする。腕ずくの点は、1000のランダムに作成された開始点から最適化することにより得られ、10回のかかる実現に対して平均される。低い
【数Ｅ−２３１】
2021536610.tif 000550
で、例示的なFOURIERヒューリスティック戦略を、1000回の腕ずくのランうちの最良のものとまさに同様に行い、両方は全体的な最適を見出し得る。一方で、腕ずくの戦略の平均性能は、開示されるヒューリスティックスよりもかなり悪い。これは、QAOAパラメーター分野(landscape)は高度に非凸状であり得、低品質の非縮退局所的最適により満たされ得ることを示す。
【数Ｅ−２３２】
2021536610.tif 000551
の場合、例示的なFOURIERヒューリスティックは最良の腕ずくのランよりも性能が優れている。
【０２２０】
いくつかの態様により、例示的なFOURIERヒューリスティックスと同じまたはそれより良い近似比を有する最適を見出すために必要とされる腕ずくのランの数を推定するために、図16Bに示されるように40000までのランを有する16頂点u3Rおよびw3Rグラフの40の例に対して、腕ずくの最適化を実施した。特に、図16Bは、16頂点u3Rおよびw3Rグラフの40の例について、例示的なFOURIERヒューリスティックと同様に良好な近似比を得るために必要とされる腕ずくのランのメジアン数を示す。対数線形尺度を使用して、結果に指数関数曲線を適合する。エラーバーは5および95番目の百分位数である。図16Bにおいて、例示的なFOURIERヒューリスティックに勝つ(beat)ために必要とされる腕ずくのランのメジアン数は、
【数Ｅ−２３３】
2021536610.tif 000552
と指数関数値的に比例することが示される。そのため、開示されるヒューリスティックスの態様は、QAOAについての良好なパラメーターを見出すために必要なリソースにおいて劇的な向上を提供する。過大な数の腕ずくのランにより検証されるように、ヒューリスティックスはしばしば全体的な最適を見出す。
【０２２１】
本開示において議論されるほとんどの例は、数値的シミュレーションにおいて勾配ベース法(gradient-based method)(BFGS)を使用するが、開示されるヒューリスティック戦略と共に非勾配ベースアプローチ、例えばネルダーミード法が使用され得る。勾配ベース最適化を使用するための選択は、いくつかの実行において勾配ベース最適化を用いてより速くなるシミュレーション速度により動機づけられ得る。他の態様において、他の手順が使用され得る。
【０２２２】
典型的な例におけるQAOAの性能
考究中の開示されるヒューリスティック最適化戦略の態様を使用して、多くのグラフの例に対する中間の
【数Ｅ−２３４】
2021536610.tif 000553
レベルのQAOAの性能を試験し得る。例えば、頂点数
【数Ｅ−２３５】
2021536610.tif 000554
を有する多くのランダムに作成される例のu3Rおよびw3Rグラフを考慮して、レベル
【数Ｅ−２３６】
2021536610.tif 000555
についての最適なQAOAパラメーターを見出すために開示されるFOURIER戦略の態様を使用することが可能である。以下の議論において、QAOAの性能を評価するために取るに足らない誤り(fractional error)
【数Ｅ−２３７】
2021536610.tif 000556
を使用する。
【０２２３】
一例において、重み無しのグラフの場合、特にu3Rグラフを考慮し得る。例えば、図16Cおよび16DはQAOAのレベル
【数Ｅ−２３８】
2021536610.tif 000557
の関数として、取るに足らない誤り
【数Ｅ−２３９】
2021536610.tif 000558
をプロットする。図16Cおよび16Dに示される例示的な結果は、u3Rグラフ(図16C)およびw3Rグラフ(図16D)の100までのランダムな例に開示されるヒューリスティックFOURIER最適化戦略の態様を適用することにより得られた。異なる形状を有する線は、異なる系のサイズ
【数Ｅ−２４０】
2021536610.tif 000559
についての平均に適合された線に対応し、ここでモデル関数は重み無しグラフについて
【数Ｅ−２４１】
2021536610.tif 000560
であり、重み付きグラフについて
【数Ｅ−２４２】
2021536610.tif 000561
である。挿入図は、系のサイズ
【数Ｅ−２４３】
2021536610.tif 000562
に対する適合パラメーター
【数Ｅ−２４４】
2021536610.tif 000563
の従属性(dependence)を示す。
【０２２４】
図16Cに示されるように、平均において、
【数Ｅ−２４５】
2021536610.tif 000564
は、いくつかの態様において、
【数Ｅ−２４６】
2021536610.tif 000565
に伴って指数関数値的に減衰するように思われる。試験された例は、
【数Ｅ−２４７】
2021536610.tif 000566
である系のサイズ
【数Ｅ−２４８】
2021536610.tif 000567
を有するu3Rグラフであったので、かかる態様は、取るに足らない誤りが約10-2未満になる事実上全てのシナリオにおいて、MaxCut状態を準備した(prepare)ことに注意。理論に拘束されることなく、この良好な性能は、特に最適化されたパラメーターが図15C〜15Hに見られるパターンのものである場合に、トロタライズド量子アニーリングとして、QAOAを解釈することにより理解され得、ここで初期化は、
【数Ｅ−２４９】
2021536610.tif 000568
の基底状態にあり、次いで系は、滑らかに減少(および増加)する持続時間と共に、
【数Ｅ−２５０】
2021536610.tif 000569
により進展する。個々のパラメーターは
【数Ｅ−２５１】
2021536610.tif 000570
であり、
【数Ｅ−２５２】
2021536610.tif 000571
下の進展時間に対応し得るので、同等の総アニーリング時間
【数Ｅ−２５３】
2021536610.tif 000572
は、レベル
【数Ｅ−２５４】
2021536610.tif 000573
にほぼ比例し得る。
【数Ｅ−２５５】
2021536610.tif 000574
が
【数Ｅ−２５６】
2021536610.tif 000575
よりもかなり長く、ここで
【数Ｅ−２５７】
2021536610.tif 000576
は、(例えばスペクトルギャップが小さい場合に走らせるために長い時間Tを必要とすることにより、量子アニーリングアルゴリズム(QAA)の適用を支配し得る)最小スペクトルギャップである場合、量子アニーリングは、断熱的原理によりMaxCutに対する正確な解(
【数Ｅ−２５８】
2021536610.tif 000577
の基底状態)を見出し得、Landau-Zenerの式により予想されるように指数関数値的に小さい取るに足らない誤りを達成し得る。いくつかの態様において、数値的に、これらのu3Rの例の最小のギャップは、量子アニーリングを走らせる場合に、
【数Ｅ−２５９】
2021536610.tif 000578
のようであることが決定され得る。したがって、QAOAはこれらの大きなギャップの例について断熱的な機構により
【数Ｅ−２６０】
2021536610.tif 000579
の基底状態を準備し得るので、QAOAが、例示的な態様を平均して指数関数値的に小さい取るに足らない誤りを達成し得ることは驚くべきことではない。それにも関わらず、この指数関数値的な挙動は、ギャップが小さいいくつかの困難な例について破壊され得る。
【０２２５】
図16Dに示されるように、w3Rグラフの場合、いくつかの態様により、取るに足らない誤りは
【数Ｅ−２６１】
2021536610.tif 000580
として比例するように思われる。いくつかの態様において、引き伸ばされた指数関数値的な比例は平均的な意味において真であるが、個々の例は非常に異なる挙動を有する。対応する最小ギャップ
【数Ｅ−２６２】
2021536610.tif 000581
が大きい簡単な例について、取るに足らない誤りの指数関数値的な比例が見られ得る。最小ギャップが小さいより困難な例について、取るに足らない誤りは、
【数Ｅ−２６３】
2021536610.tif 000582
が増加する場合にさらに減少する前に、中間pでプラトーに達する。これらの困難な例は、以下の表題「断熱的機構、量子アニーリングおよびQAOA」の節においてより詳細に議論される。注意すべきことに、ランダムに作成された例に対して平均される場合、取るに足らない誤りは、引き伸ばされた指数関数(strended-exponential function)により顕著に十分に適合される。
【０２２６】
QAOAの態様の平均的な性能のこれらの結果は、有限のサイズの効果の考慮にも関わらず顕著である。図16C、16Dの挿入図に示されるように、減衰定数
【数Ｅ−２６４】
2021536610.tif 000583
は、系のサイズ
【数Ｅ−２６５】
2021536610.tif 000584
に依存するように思えるが、本開示に示される例示的な有限サイズのシミュレーションは、正確な比例を最終的には決定し得ない。いくつかの態様において、傾向が
【数Ｅ−２６６】
2021536610.tif 000585
の系のサイズに続く場合、QAOAは、正確な解を見出すことが実行不可能な領域(regime)において、他の公知のアルゴリズムよりも良好にまたはそれと同等に、興味深いMaxCutの例を解くことに実際に有用である(すなわちQAOAは有効量子近似体(approximator)である)。QAOAがいくつかの最も悪い場合のグラフについて失敗したとしても、QAOAがランダムに選択された大きな系のサイズのグラフに対して十分に機能する場合は、QAOAは依然として、実際に有用であり得る。
【０２２７】
ヒューリスティックスの間の比較
本開示において提唱される種々のヒューリスティック戦略の態様の間の性能の差は、14頂点w3Rグラフの例示的な例に対して試験され得る。図23に示されるように、いくつかの態様により、本明細書に開示されるINTERPおよびFOURIER[∞、0]戦略の例示的な態様は、本質的に同じ性能を有する(大きな
【数Ｅ−２６７】
2021536610.tif 000586
でのほとんど見えない小さな変動を除く)。これは、いくつかの態様において、両方の戦略がレベル
【数Ｅ−２６８】
2021536610.tif 000587
での最適の滑らかな変形に基づいてレベル
【数Ｅ−２６９】
2021536610.tif 000588
を最適化するための開始点を作成することを考慮することにより説明され得る。さらに、FOURIER[∞、10]戦略は、レベル
【数Ｅ−２７０】
2021536610.tif 000589
で開始するINTERPおよびFOURIER[∞、0]よりも性能が優れている。顕著なことに、QAOAパラメーターの数を
【数Ｅ−２７１】
2021536610.tif 000590
に制限した場合であっても、FOURIER[
【数Ｅ−２７２】
2021536610.tif 000591
]戦略は、低い
【数Ｅ−２７３】
2021536610.tif 000592
で他のヒューリステクックスの性能に密接に適合し、大きな
【数Ｅ−２７４】
2021536610.tif 000593
で
【数Ｅ−２７５】
2021536610.tif 000594
ヒューリスティックに勝つ。これは、最適なQAOAパラメーターは実際に、小さな次元の集合体内に存在し得ることを示唆する。そのため、中間の
【数Ｅ−２７６】
2021536610.tif 000595
レベルQAOAのための最適化は、開示されるパラメーター化(
【数Ｅ−２７７】
2021536610.tif 000596
)を使用することにより劇的に単純化され得る。
【０２２８】
断熱的機構、量子アニーリングおよびQAOA
以前の節では、近似比
【数Ｅ−２７８】
2021536610.tif 000597
に関するランダムなグラフの例に対するMaxCutについてのQAOAの態様の性能を議論した。近似最適化については有用であるが、QAOAは、しばしばレベル
【数Ｅ−２７９】
2021536610.tif 000598
が増加する場合、高い確率でMaxCut構成-問題の全体的最適を見出し得る。この節において、開示されるアルゴリズムの例示的態様の効率は、MaxCut構成を見出し、該開示されるアルゴリズムと量子アニーリングを比較するために示される。いくつかの態様において、QAOAは、量子アニーリングにおける最小ギャップにより必ずしも制限されず、QAOAに断熱的制限を克服させる運転の際の機構(mechanism of work)が説明される。
【０２２９】
QAOAと量子アニーリングの比較
QAOAの前のものである量子アニーリング(QA)は、組合せ最適化問題を解決するために使用され得る。理論に拘束されることなく、
【数Ｅ−２８０】
2021536610.tif 000599
を最大化するMaxCut構成、以下の単純なQAプロトコルを見出すことが考慮され得：
【数Ｅ−２８１】
2021536610.tif 000600
であり、ここで
【数Ｅ−２８２】
2021536610.tif 000601
は、総アニーリング時間である。初期状態は、
【数Ｅ−２８３】
2021536610.tif 000602
の基底状態、すなわち
【数Ｅ−２８４】
2021536610.tif 000603
であるように調整され得る。最終ハミルトニアンの基底状態
【数Ｅ−２８５】
2021536610.tif 000604
は、
【数Ｅ−２８６】
2021536610.tif 000605
においてエンコードされるMaxCut問題の解に対応し得る。断熱的QAにおいて、アルゴリズムは、瞬間の基底状態をアニーリング経路に沿って維持するために断熱的原理に頼り得、最終的に基底状態を見出すことによりコンピューター計算問題を解決する。高い成功の確率を確実にするために、アルゴリズムのラン時間は典型的に
【数Ｅ−２８７】
2021536610.tif 000606
として比例し、ここで
【数Ｅ−２８８】
2021536610.tif 000607
は最小スペクトルギャップである。結果的に、断熱的QAは、
【数Ｅ−２８９】
2021536610.tif 000608
が極端に小さくなる例について非効率的になる。これらのグラフの例は、断熱的QAについての困難な例と称され得る。
【０２３０】
完全に断熱的な領域を超えるいくつかの態様において、しばしば成功確率(基底状態集団
【数Ｅ−２９０】
2021536610.tif 000609
)とラン時間(アニーリング時間
【数Ｅ−２９１】
2021536610.tif 000610
)の間に兼ね合いがあり：アルゴリズムは、高い成功確率を得るために長いアニーリング時間で走らされ得るか、または少なくとも1回解を見出すためにより短い時間で複数回走らされ得るかのいずれかである。最良のバランスを決定するために使用され得る1つの測定規準は、時間-対-解(TTS)と称され得る：
【数Ｅ−２９２】
2021536610.tif 000611
。
【０２３１】
【数Ｅ−２９３】
2021536610.tif 000612
は、状態調製および測定時間などの非アルゴリズム的オーバーヘッドを無視して、標的確率
【数Ｅ−２９４】
2021536610.tif 000613
(本開示において99%と採られる)で基底状態を少なくとも1回見出すために必要とされる時間を測定し得る。Landau-Zener式当たり
【数Ｅ−２９５】
2021536610.tif 000614
の場合の断熱的領域は、
【数Ｅ−２９６】
2021536610.tif 000615
と独立する
【数Ｅ−２９７】
2021536610.tif 000616
を生じ得る。いくつかの場合において、より短いTTSを得るためにQAを非断熱的に走らせることがより良くあり得る。最良のアニーリング時間
【数Ｅ−２９８】
2021536610.tif 000617
を選択することにより、断熱性に関係なく、QAの最小アルゴリズムラン時間として
【数Ｅ−２９９】
2021536610.tif 000618
が決定され得る。理論に拘束されることなく、ベンチマークテストする目的のために、QAOAについて同様の非限定的測定規準が画定され得る。変動性パラメーター
【数Ｅ−３００】
2021536610.tif 000619
は、ハミルトニアン
【数Ｅ−３０１】
2021536610.tif 000620
のそれぞれ下で進展される時間とみなされ得る。いくつかの態様において、変動性パラメーターの和は総「アニーリング」時間と解釈され得るので、
【数Ｅ−３０２】
2021536610.tif 000621
と定義され得、ここで
【数Ｅ−３０３】
2021536610.tif 000622
は、最適なpレベルQAOAプロトコルの後の基底状態集団である。この量は、最適なパラメーターを見出すことにおいてオーバーヘッドを考慮することを必要としない。
【数Ｅ−３０４】
2021536610.tif 000623
は、アルゴリズムをベンチマークでテストするために使用され得るが、実際の実験ラン時間として直接採用されるべきではない。
【０２３２】
アルゴリズムの例を比較するために、
【数Ｅ−３０５】
2021536610.tif 000624
は、多くのランダムグラフの例についてコンピューター計算され得る。
【数Ｅ−３０６】
2021536610.tif 000625
それぞれの偶数の頂点数について、w3Rグラフの1000個の例を作成する。図17A〜17Eは、いくつかの態様による、それぞれの例示的な例についての量子アニーリングにおける
【数Ｅ−３０７】
2021536610.tif 000626
と最小ギャップ
【数Ｅ−３０８】
2021536610.tif 000627
と頂点サイズNの間の関係のプロットである。図17A〜17Eについて、最大カットオフ
【数Ｅ−３０９】
2021536610.tif 000628
は、
【数Ｅ−３１０】
2021536610.tif 000629
=10、12、14、16、18のそれぞれについて
【数Ｅ−３１１】
2021536610.tif 000630
=50、50、40、35、30であるように採用される。破線は、Landau-Zenerにより予想される
【数Ｅ−３１２】
2021536610.tif 000631
の断熱的QAラン時間に対応する。例示的なランダムグラフのほとんどは、大きなギャップ(
【数Ｅ−３１３】
2021536610.tif 000632
)を有する。最適TTSは、これらのグラフについて、
【数Ｅ−３１４】
2021536610.tif 000633
minのLandau-Zener予想に従うように観察され得る。いくつかの態様において、これは、QAOAの準断熱的パラメーター化は、
【数Ｅ−３１５】
2021536610.tif 000634
が合理的に大きい場合に最良であり得ることを示す。しかしながら、多くの例示的なグラフは、非常に小さいギャップ(
【数Ｅ−３１６】
2021536610.tif 000635
)を示し、そのため、断熱的進展のために非常に長いラン時間を必要とする。いくつかのグラフについて、
【数Ｅ−３１７】
2021536610.tif 000636
は10-8程に小さくなり、これは断熱的進展は、
【数Ｅ−３１８】
2021536610.tif 000637
のラン時間を必要とすることを意味し得る。それにもかかわらず、QAOAは、断熱的QAよりも早くこれらの困難な例について解を見出し得る。顕著なことに、いくつかの態様において、
【数Ｅ−３１９】
2021536610.tif 000638
は、極度に小さいギャップを有する多くのグラフについて、ギャップに独立するように思われ、多数の桁だけ断熱的TTS(Landau-Zener線)に勝つ。したがって、TTSの指数関数値的な向上は、断熱的QAが指数関数値的に小さいギャップにより制限される場合、非断熱的機構により可能になる。
【０２３３】
同様に、QAについて、最適アニーリング時間
【数Ｅ−３２０】
2021536610.tif 000639
は、小さなギャップのグラフについて断熱的な制限内にある必要はない。図17F〜17Jは、いくつかの態様による、それぞれのランダムグラフの例についての
【数Ｅ−３２１】
2021536610.tif 000640
を示す。QAOAの態様は、破線より下の例についてQAよりも性能が優れる。QAOA TTSとQA TTSの間の(ピアソンの)相関係数は、
【数Ｅ−３２２】
2021536610.tif 000641
である。図17F〜17Jに示されるように、それぞれのグラフの例について、
【数Ｅ−３２３】
2021536610.tif 000642
の間には強い相関があり得る。理論に拘束されることなく、これは、QAOAは、遅い断熱的進展がより良いかまたは速い断熱的進展がより良いかに関わらず、最適なアニーリングスケジュールを利用していることを示唆する。理論に拘束されることなく、表題「断熱的機構を超える：ケース試験」の以下の節において、図17A〜17Hにおいて観察された結果および断熱的規範を超えるQAOAの機構の局面を説明するための非限定的な例が調べられる。
【０２３４】
断熱的機構を超える：ケース試験
QAOAの挙動を理解するために、断熱的QAについて困難であるグラフの例を、より詳細に扱い得る。例えば、QAOAおよび断熱的QAの態様が断熱的制限をどのように克服し得るかを説明するために代表的な例を使用する。18Aに図示されるように、QAOAは、QAにおいて非常に小さいグラフにより引き起こされる困難さを回避するために、反交差で非断熱的(diabatic)遷移を利用することを学習し得る。図18Aは、QAOAおよび内挿されたアニーリング経路が、非断熱的遷移(小さい破線)により小さな最小ギャップ制限をどのように克服し得るかの概略図を示す。ナイーブな(naive)断熱的量子アニーリング経路は、反交差の点(大きい破線)を通過する励起した状態をもたらす。
【０２３５】
図18Bは、いくつかの態様による、小さな最小スペクトルギャップ
【数Ｅ−３２４】
2021536610.tif 000643
を有する、
【数Ｅ−３２５】
2021536610.tif 000644
=14を有する重み付き3の正則グラフの代表的な例を示す。例えば、図18Bは、等式69により与えられる量子アニーリング経路に沿った小さな最小スペクトルギャップを有する重み付き3の正則グラフの例を示す。例として、最適MaxCut構成は、2つの頂点型(円および四角)により示され、実線(破線)は、切断(非切断)エッジである。この例について、困難な例である量子アニーリングプロセスがシミュレートされ得る。理論に拘束されることなく、図18Cは、いくつかの態様による、異なるアニーリング時間
【数Ｅ−３２６】
2021536610.tif 000645
の間のプロセスの終了時点での基底状態および低い励起状態の集団を示す。実線は、基底状態集団についてのLandau-Zener式
【数Ｅ−３２７】
2021536610.tif 000646
をたどり、ここでcは適合パラメーターである。最小ギャップは非常に小さくあり得るので、断熱的条件は、
【数Ｅ−３２８】
2021536610.tif 000647
であることを必要とする。基底状態集団についてのLandau-Zener式
【数Ｅ−３２９】
2021536610.tif 000648
は、本明細書において議論される正確な数値的シミュレーションと十分に適合し、ここでcは適合パラメーターである。しかしながら、アニーリング時間
【数Ｅ−３３０】
2021536610.tif 000649
で基底状態集団中に「バンプ(bump)」がある。かかる時間スケールで、動力学は非断熱的であるとみなされ得；これは「非断熱的バンプ」と称され得る。この現象は、他の最適化問題の量子アニーリングにおいても観察されている。
【０２３６】
いくつかの態様において、この困難な例に対してQAOAをシミュレートすることも可能である。上述のように、QAOAは、基底状態重複の代わりにエネルギーを最適化し得るが、実質的な基底状態集団は依然として、多くの困難なグラフについても得られ得る。いくつかの態様により、開示されるFOURIERヒューリスティック戦略の例示的態様を使用して、出力状態の種々の低エネルギー状態集団は、図18Dに示される異なるレベル
【数Ｅ−３３１】
2021536610.tif 000650
について示される。より具体的に、図18Dは、異なるレベル
【数Ｅ−３３２】
2021536610.tif 000651
でQAOAを使用して、低い励起状態の集団を示す。図18Dに示される最適化において例示的なFOURIERヒューリスティック戦略を使用する。かかる態様において、QAOAは、小さな
【数Ｅ−３３３】
2021536610.tif 000652
で非断熱的バンプと同様の基底状態集団を達成し得、
【数Ｅ−３３４】
2021536610.tif 000653
後に実質的な増加が起こる。
【０２３７】
理論に拘束されることなく、QAOAの態様の機構をよりよく理解するためおよびQAとの比較を行うために、QAOAパラメーターは、滑らかなアニーリング経路として解釈され得る。変動性パラメーターの和は、上述のように総アニーリング時間、すなわち
【数Ｅ−３３５】
2021536610.tif 000654
であると解釈され得る。滑らかなアニーリング経路は、QAOA最適パラメーターから
【数Ｅ−３３６】
2021536610.tif 000655
と構築され得、ここで
【数Ｅ−３３７】
2021536610.tif 000656
は、それぞれの時間間隔
【数Ｅ−３３８】
2021536610.tif 000657
の中間点にあるように選択され得る。境界条件
【数Ｅ−３３９】
2021536610.tif 000658
および他の中間時間
【数Ｅ−３４０】
2021536610.tif 000659
での線形内挿により、QAOAパラメーターは、十分に画定されたアニーリング経路に変換され得る。いくつかの態様により、図18Eに示されるように、この変換は、
【数Ｅ−３４１】
2021536610.tif 000660
=40でQAOA最適パラメーターに適用され得る。アニーリング時間パラメーターは、
【数Ｅ−３４２】
2021536610.tif 000661
と記述され得、ここで
【数Ｅ−３４３】
2021536610.tif 000662
である。平坦な上方の点線は、ギャップが、点
【数Ｅ−３４４】
2021536610.tif 000663
であるその最小にある反交差の位置を標識する。挿入図は、
【数Ｅ−３４５】
2021536610.tif 000664
=40についての元のQAOA最適パラメーター
【数Ｅ−３４６】
2021536610.tif 000665
を示す。いくつかの態様により、図18Fに示されるように、このアニーリング経路により、量子アニーリングプロセスの間中に瞬間の固有状態集団をたどることが可能である。特に、図18Fは、図18Eで与えられるアニーリング経路下の瞬間の固有状態集団を示す。瞬間の基底状態および第1の励起状態は反交差の点で交換されることに注意。断熱的QAとは対照的に、状態集団は、反交差の点の前に、基底状態から漏れて第1の励起状態に蓄積し、ここでギャップは、その最小にある。反交差での非断熱的遷移を使用して、2つの状態は集団を交換し得、大きな基底状態集団は最後に得られる。構築されたアニーリング経路からの最終的な状態の集団は、例えばトロタライズ化および内挿のためにQAOAのものとはわずかに異なり得るが、理論に拘束されることなく、基礎をなす機構は同じものとして解釈され得、これは図18Cに見られる非断熱的バンプの原因であるともみなされ得る。上述の等式において使用される変換に加えて、QAOAパラメーターからアニーリング経路を構築するために他の規範が使用され得、定性的特徴は変化するようには思われない。
【０２３８】
理論に拘束されることなく、これらの結果は、QAOAは、断熱的定理により設定される制限を克服し得る器用に最適化された非断熱的QA経路に密接に関連することを示す。最適化を通して、QAOAは、良好なアニーリング経路を見出し得、基底状態集団を高めるために非断熱的遷移を利用し得る。これは、
【数Ｅ−３４７】
2021536610.tif 000666
が断熱的アルゴリズムにより必要とされる時間よりも有意に短くあり得ることの図17A〜17Eにおける観察を説明する。一方、図17H〜17Jに見られるように、
【数Ｅ−３４８】
2021536610.tif 000667
は、
【数Ｅ−３４９】
2021536610.tif 000668
と強力に相関し得：QAOAは、特定の問題の例について何が最良のルートであるかに応じて断熱的であり得るかまたは断熱的であり得ない良好なアニーリング経路を見出し得る。
【０２３９】
図18Fに示されるように、これらの例示的な特定の例についてのQAOAの有効動力学は、限定されることなく、以下の節においてより詳細に議論される有効二準位系により理解され得る。一般的に、エネルギースペクトルはより複雑であり得、動力学は、図18Aにおいて単純な概略図により説明され得ない多くの励起状態を含み得る。それにもかかわらず、QAOAは、より複雑な場合であっても、開示されるヒューリスティック最適化戦略により、適切な経路を見出し得る。
【０２４０】
非断熱的バンプの有効少数レベルの理解
理論に拘束されることなく、この節は、有効少数レベルの動力学による、図18Cに関して先に議論された非断熱的バンプの機構を解明する。量子アニーリングの間の中間の動力学は、瞬間の固有状態の基底
【数Ｅ−３５０】
2021536610.tif 000669
を使用して理解され得、ここで
【数Ｅ−３５１】
2021536610.tif 000670
である。
【０２４１】
この規定において時間進展状態を
【数Ｅ−３５２】
2021536610.tif 000671
として展開すると、シュレディンガー方程式は、
【数Ｅ−３５３】
2021536610.tif 000672
と記述され得、ここで表記法中の
【数Ｅ−３５４】
2021536610.tif 000673
および時間依存性は、便宜上省略する。等式に
【数Ｅ−３５５】
2021536610.tif 000674
をかけると、シュレディンガー方程式は、
【数Ｅ−３５６】
2021536610.tif 000675
となり、ここで位相を固有ベクトル
【数Ｅ−３５７】
2021536610.tif 000676
に吸収させることにより
【数Ｅ−３５８】
2021536610.tif 000677
が採られる。マトリックスの形態で記載すると、
【数Ｅ−３５９】
2021536610.tif 000678
であることが見られ得、ここで基底状態エネルギーは(係数の位相に吸収させることにより)
【数Ｅ−３６０】
2021536610.tif 000679
であり、
【数Ｅ−３６１】
2021536610.tif 000680
は
【数Ｅ−３６２】
2021536610.tif 000681
番目の励起状態から基底状態への瞬間のエネルギーギャップである。時間進展は、
【数Ｅ−３６３】
2021536610.tif 000682
を有する初期基底状態から開始し、励起状態へのカップリングを防ぐ断熱的状態は、
【数Ｅ−３６４】
2021536610.tif 000683
である。
【０２４２】
第1の同等性は等式76に由来し得る。これは標準的な断熱的状態
【数Ｅ−３６５】
2021536610.tif 000684
を生じ得る。先に議論されるように、いくつかのグラフについての最小ギャップは極めて小さくあり得るので、断熱的制限は実際的ではないことがある。しかしながら、断熱性を破るがわずかな励起状態のみが動力学に有効に含まれるように十分に長い適切なラン時間
【数Ｅ−３６６】
2021536610.tif 000685
を選択することが可能である。これは、非断熱的バンプが作動する領域であり、等式79を第1の少数の基底状態に切断することにより動力学が理解され得る。
【０２４３】
例として、図25Aは、いくつかの態様による、第1の少数の状態の瞬間の固有状態集団をプロットする。特に、図25Aは、図18Bにおける例示的グラフについて、等式69により与えられる線形傾斜量子アニーリング経路に沿って瞬間の固有状態集団をプロットする。アニーリング時間は
【数Ｅ−３６７】
2021536610.tif 000686
であるように選択され得、これは、図18Cにおいて非断熱的バンプが起こる時間に対応し得る。図25Aは、完全ヒルベルト空間を用いてシミュレートされるが、有効ことに、シミュレーションが等式79における第1の少数の基底状態に制限される場合に同じ動力学が生じる。
【０２４４】
図25Bは、いくつかの態様による、瞬間の基底状態と低い励起状態の間のカップリングの強度を示す。プロットされた量は(等式80において説明されるように)断熱性の度合いを測定する。図25Aと25Bを比較することにより、
【数Ｅ−３６８】
2021536610.tif 000687
が、時間進展により、反交差の前に断熱的状態を破ることを見ることが可能であり：集団は第1の励起状態に漏れて、反交差の後に基底状態になる。したがって、非断熱的バンプについての
【数Ｅ−３６９】
2021536610.tif 000688
の時間尺度は、集団を基底状態から漏れさせることと過剰な集団の漏れを抑制することの間の微妙なバランスを示し、理論に拘束されることなく、一定の時間尺度の範囲でなぜこれが起こるのかが説明される。
【０２４５】
例示的なグラフの例および時間-対-解
先の節において、断熱的最小ギャップが小さい例示的な代表的なグラフの例は、図18Bを参照して考慮された。いくつかの態様により、図24A において、QA経路に沿ったグラフについての低いエネルギースペクトルが見られ得る。より具体的に、図24Aは、図18Bに与えられるグラフの例についてのアニーリング経路に沿った低い励起状態(基底状態エネルギー
【数Ｅ−３７０】
2021536610.tif 000689
から測定される)の例示的なエネルギースペクトルを示す。パリティ演算子
【数Ｅ−３７１】
2021536610.tif 000690
の下で不変の状態などの、この例において基底状態にカップリングされ得る状態のみが示される。挿入図は、対数尺度における基底状態からのエネルギーギャップを示す。ハミルトニアン
【数Ｅ−３７２】
2021536610.tif 000691
は
【数Ｅ−３７３】
2021536610.tif 000692
と交換可能であり、初期状態は
【数Ｅ−３７４】
2021536610.tif 000693
不変である：
【数Ｅ−３７５】
2021536610.tif 000694
ので、図24Aの態様に示されるように、パリティ演算子
【数Ｅ−３７６】
2021536610.tif 000695
下で不変である固有状態のみが示される。
【０２４６】
図24Bおよび24Cは、同じグラフについてのTTSQAおよびTTSQAOAを図示する。特に、図24Bは、同じグラフの例についての線形傾斜量子アニーリングプロトコルについての時間-対-解TTSQAを示す。この態様において、長時間極限におけるTTSは、アニーリング時間Tから独立するLandau-Zener式により予想される線をたどる。図24Cは、それぞれの反復デプス
【数Ｅ−３７７】
2021536610.tif 000696
でのQAOAについてのTTSを示す。QAについて、
【数Ｅ−３７８】
2021536610.tif 000697
を有する非断熱的進展は、断熱的進展より数桁も短いTTSを生じる。また、断熱的制限におけるTTSは、アニーリング時間
【数Ｅ−３７９】
2021536610.tif 000698
から独立し、Landau-Zener式
【数Ｅ−３８０】
2021536610.tif 000699
に従う。QAOAについて、FOURIER[∞、10]ヒューリスティック戦略の例示的な態様は、
【数Ｅ−３８１】
2021536610.tif 000700
まで数値的シミュレーションを実行し、
【数Ｅ−３８２】
2021536610.tif 000701
をコンピューター計算するために使用される。この特定の図について、
【数Ｅ−３８３】
2021536610.tif 000702
は起こるが、いくつかの態様において、より深い回路デプスでの最適化オーバーヘッドおよび誤り蓄積のために、
【数Ｅ−３８４】
2021536610.tif 000703
でQAOAを走らせることがより好ましくあり得る。図24Cに示されるTTSQAOAにおける明白な不連続なジャンプは、2つの理由により説明され得る
【数Ｅ−３８５】
2021536610.tif 000704
における対応するジャンプのためである：第1は、開示されるヒューリスティック戦略の態様は、全体的な最適を見出すことが保証されず、ランダム摂動が局所的な最適のアルゴリズム回避(escape)を補助し得、基底状態集団においてジャンプを生じ；第2に、全てのレベル
【数Ｅ−３８６】
2021536610.tif 000705
について全体的な最適が見出される場合であっても、QAOAの目的関数は基底状態集団ではなくエネルギーであるので、
【数Ｅ−３８７】
2021536610.tif 000706
において不連続性が依存としてあり得る。
【０２４７】
シミュレーション技術
測定射影雑音を伴うシミュレーションの詳細
実際の量子デバイス上でQAOAを走らせる場合、目的関数は多くの測定結果を平均することにより評価され得、結果的に、その精度は、いくつかの態様において、量子揺らぎからのいわゆる測定射影雑音により制限され得る。この効果は、実際の測定の完全モンテカルロシミュレーションを実施することにより説明され得、ここでシミュレートされた量子プロセッサは、
【数Ｅ−３８８】
2021536610.tif 000707
回の測定を平均することにより得られる目的関数の近似値のみを出力し：
【数Ｅ−３８９】
2021536610.tif 000708
であり、ここで
【数Ｅ−３９０】
2021536610.tif 000709
は、コンピューター計算基礎において
【数Ｅ−３９１】
2021536610.tif 000710
を測定することにより得られる
【数Ｅ−３９２】
2021536610.tif 000711
番目の測定結果に対応するランダム変数であり、
【数Ｅ−３９３】
2021536610.tif 000712
は古典的な目的関数である。
【数Ｅ−３９４】
2021536610.tif 000713
であることに注意。例示的なシミュレーションにおいて、有限の精度
【数Ｅ−３９５】
2021536610.tif 000714
は、平均の累積標準誤りが標的精度レベルξ未満に下がるまでのサンプリング測定により達成され得る。すなわち、古典的最適化装置により要求される
【数Ｅ−３９６】
2021536610.tif 000715
のそれぞれの評価について、実施される測定の数
【数Ｅ−３９７】
2021536610.tif 000716
は、以下の基準により設定される：
【数Ｅ−３９８】
2021536610.tif 000717
。
【０２４８】
いくつかの態様において、
【数Ｅ−３９９】
2021536610.tif 000718
であることが予想され得る。有限なサンプルサイズを用いて、明らかになり得る問題を扱うために、それぞれの目的関数の評価について少なくとも10回の測定が実施される(
【数Ｅ−４００】
2021536610.tif 000719
10)。
【０２４９】
QAOAパラメーターを最適化するために使用される古典的最適化アルゴリズムに関して、一般的に、古典的最適化アルゴリズムはイテレーション的に、いくつかの所定のパラメーター点
【数Ｅ−４０１】
2021536610.tif 000720
からの情報を使用して、目的関数のより大きな値
【数Ｅ−４０２】
2021536610.tif 000721
を生じる新たなパラメーター点
【数Ｅ−４０３】
2021536610.tif 000722
を見出す。アルゴリズムを終結させるために、いくつかの停止基準が設定され得る。いくつかの態様において、2までが使用され得る：第1に、目的関数における変化が
【数Ｅ−４０４】
2021536610.tif 000723
である場合に、アルゴリズムが終結するように目的関数の許容性
【数Ｅ−４０５】
2021536610.tif 000724
が設定され得る。第2に、ステップ許容性δはまた、新たなパラメーター点が以前のものに非常に近接する場合
【数Ｅ−４０６】
2021536610.tif 000725
にアルゴリズムが終結するように設定され得る。BFGSなどの勾配ベース最適化アルゴリズムについて、δはまた、有限差分法：
【数Ｅ−４０７】
2021536610.tif 000726
を介して勾配を推定するために増分サイズとして使用され得る。本明細書において議論されるシミュレーションにおいて、BFGSアルゴリズムは、MATLAB R2017bの標準ライブラリーにおけるfminuncとして実行される。
【０２５０】
上記のアプローチを使用して、精度パラメーター
【数Ｅ−４０８】
2021536610.tif 000727
および開始点の種々の選択により、いくつかの例示的な例についての測定射影雑音を用いてQAOAを最適化する実験をシミュレートすることが可能である。図19において試験される例示的な代表例について
【数Ｅ−４０９】
2021536610.tif 000728
である。シミュレートされた実験のそれぞれのランは、
【数Ｅ−４１０】
2021536610.tif 000729
のいずれかのレベルのQAOAで開始し、開示されるFOURIER[∞、0]ヒューリスティック戦略の態様を使用してQAOAの増加レベルを最適化することを続ける。QAOA最適化の開始点は、ランダムに選択され得る(
【数Ｅ−４１１】
2021536610.tif 000730
で開始する場合)か、または(
【数Ｅ−４１２】
2021536610.tif 000731
で)小さいサイズの例からの最適パラメーターを使用して教育された推測に基づいて選択され得るかのいずれかである。具体的に、図19において試験される例についての教育された推測から得られる開始点は、レベル
【数Ｅ−４１３】
2021536610.tif 000732
で
【数Ｅ−４１４】
2021536610.tif 000733
であり、レベル
【数Ｅ−４１５】
2021536610.tif 000734
で
【数Ｅ−４１６】
2021536610.tif 000735
である。それぞれのかかるランについて、全ての測定の履歴は、
【数Ｅ−４１７】
2021536610.tif 000736
番目の測定後に見出される最大のカット
【数Ｅ−４１８】
2021536610.tif 000737
が計算され得るように追跡され得る。それぞれの実験は、異なる擬似乱数生成シード(pseudo-random number generation seed)を用いて500回反復され、それらの履歴に対して平均が取られる。
【０２５１】
数値的シミュレーションの速度を上げるための技術
いくつかの態様において、QAOAおよびQAの両方について数値的シミュレーションの速度を上げるためにいくつかの技術が利用され得る。
【０２５２】
例えば、第1に、ハミルトニアン中に存在する対称性が使用され得る。一般的なグラフに対するMaxCutについて、
【数Ｅ−４１９】
2021536610.tif 000738
の両方と交換可能である対称性演算子のみは、パリティ演算子
【数Ｅ−４２０】
2021536610.tif 000739
であり、そのために
【数Ｅ−４２１】
2021536610.tif 000740
がなされ、ここでHQA(s)は、量子アニーリングハミルトニアン等式69である。パリティ演算子は、2つの固有値+1および-1を有し得、それぞれは全ヒルベルト空間の半分を有する。QAOAおよびQAの両方についての初期状態は正の領域にあり、すなわち
【数Ｅ−４２２】
2021536610.tif 000741
である。したがって、任意の動力学は、正のパリティ領域のままでなければならない。
【数Ｅ−４２３】
2021536610.tif 000742
は、
【数Ｅ−４２４】
2021536610.tif 000743
の固有ベクトルの基底において書き直され得、ヒルベルト空間は、正のパリティ領域において作動することにより
【数Ｅ−４２５】
2021536610.tif 000744
低減され得る。
【０２５３】
QAについて、時間依存ハミルトニアンを含む動力学は、総シミュレーション時間
【数Ｅ−４２６】
2021536610.tif 000745
を十分に小さな不連続な時間Tに分割し、それぞれの時間ステップを順次実行することによりシミュレートされ得る。それぞれの小さなステップで、クリロフ部分空間射影法(Krylov subspace projection method)または打ち切りテイラー級数近似(truncated Taylor series approximation)のいずれかを使用して、完全な進展演算子を形成することなく、状態を進展させることが可能である。本明細書において議論されるシミュレーションにおいて、小さな時間ステップについてクリロフ部分空間法よりもわずかに速く走るように思われるので、打ち切りテイラー級数近似と共にスケーリングスクエアリング法(scaling and squaring method)が使用される。
【０２５４】
QAOAについて、いくつかの態様において、動力学は、演算子
【数Ｅ−４２７】
2021536610.tif 000746
の特別な形態のためにより効率的な方法で実行され得る。作業は、標準的な
【数Ｅ−４２８】
2021536610.tif 000747
基底において実行され得る。したがって、
【数Ｅ−４２９】
2021536610.tif 000748
は対角マトリックスとして記述され得、
【数Ｅ−４３０】
2021536610.tif 000749
の行為はベクトル演算として実行され得る。
【数Ｅ−４３１】
2021536610.tif 000750
について、時間進展演算子は、
【数Ｅ−４３２】
2021536610.tif 000751
として簡略化され得る。
【０２５５】
そのため、
【数Ｅ−４３３】
2021536610.tif 000752
の行為はまた、疎マトリックス
【数Ｅ−４３４】
2021536610.tif 000753
を明示的に形成することなく、
【数Ｅ−４３５】
2021536610.tif 000754
個の連続ベクトル操作として実行され得、その両方がシミュレーション速度を向上し、メモリを節約する。また、変動性パラメーターの最適化において、勾配は、有限差分法を使用する代わりに解析的に計算され得る。
【数Ｅ−４３６】
2021536610.tif 000755
レベルQAOAについて、勾配のコンピューター計算のコストを
【数Ｅ−４３７】
2021536610.tif 000756
低減する、傾斜パルス形成(gradient ascent pulse engineering) (GRAPE)法と同様の技術も使用され得る。最終的に、開示されるFOURIER戦略の態様の例示的なシミュレーションにおいて、目的関数の勾配は、新たなパラメーター
【数Ｅ−４３８】
2021536610.tif 000757
に関して計算され得る。いくつかのマトリックス
【数Ｅ−４３９】
2021536610.tif 000758
について、
【数Ｅ−４４０】
2021536610.tif 000759
であるので、それらの勾配も
【数Ｅ−４４１】
2021536610.tif 000760
を介して関連し得る。
【０２５６】
MISについてのQAOA
この節では、いくつかの態様による、最大独立集合問題を解決するための量子近似最適化アルゴリズムをシミュレートするための例示的な技術が議論される。
【０２５７】
量子近似最適化アルゴリズム
理論に拘束されることなく、いくつかの態様において、所定のグラフ
【数Ｅ−４４２】
2021536610.tif 000761
上でMISを見出すための問題を仮定すると、MISについての
【数Ｅ−４４３】
2021536610.tif 000762
レベルQAOAは、以下のステップからなる変動性アルゴリズムであり得る：
【０２５８】
(i)
【数Ｅ−４４４】
2021536610.tif 000763
における量子状態の初期化。
【０２５９】
(ii)  変動性波動関数：
【数Ｅ−４４５】
2021536610.tif 000764
の調製、ここで
【数Ｅ−４４６】
2021536610.tif 000765
である。パラメーター
【数Ｅ−４４７】
2021536610.tif 000766
は、変動性状態を特定する。
【０２６０】
(iii) 
【数Ｅ−４４８】
2021536610.tif 000767
の測定。
【０２６１】
3つのステップ(i)〜(iii)は、
【数Ｅ−４４９】
2021536610.tif 000768
を最小化するために、反復され得、変動性パラメーターの古典的最適化と合わされ得る。
【０２６２】
代替的公式化
いくつかの態様において、
【数Ｅ−４５０】
2021536610.tif 000769
である場合、変動性検索は、アルゴリズムが、MIS候補として直接除外され得る状態を調べる必要がないように、独立集合により張られる部分空間
【数Ｅ−４５１】
2021536610.tif 000770
に限定され得る。この極限において、
【数Ｅ−４５２】
2021536610.tif 000771
と記述することが可能であり、ここで
【数Ｅ−４５３】
2021536610.tif 000772
は独立集合部分空間
【数Ｅ−４５４】
2021536610.tif 000773
への射影体である。
【数Ｅ−４５５】
2021536610.tif 000774
による進展は、
【数Ｅ−４５６】
2021536610.tif 000775
軸の周りの個々のスピンの単純な回転まで簡略化し得る。
【数Ｅ−４５７】
2021536610.tif 000776
であるので、等式86における
【数Ｅ−４５８】
2021536610.tif 000777
により生成される全てのユニタリーを、ユニタリーが初期状態に対して(トリビアルに)作用するまで最も右側に交換することが可能である。したがって、状態
【数Ｅ−４５９】
2021536610.tif 000778
を
【数Ｅ−４６０】
2021536610.tif 000779
として書き直すことが可能であり、ここで以下の
【数Ｅ−４６１】
2021536610.tif 000780
が同定され得る。
【０２６３】
したがって、先に与えられるQAOAの公式化のいくつかの態様は、
【数Ｅ−４６２】
2021536610.tif 000781
について等式90と同等であり得る。
【０２６４】
本開示の局面は、量子アルゴリズムが、必要とされるアンシラリーキュービットの数に限定されないが、必要とされる量子回路のさらなるデプス等を含み得る、最小リソースおよび実行オーバーヘッドを有するコヒーレント量子オプティマイザーによりコンピューター計算的に困難な問題を解くために実行され得ることを示す。
【０２６５】
本開示の局面は、NP完全組合せ最適化問題が、キュービットの間の望ましくない相互作用を考慮した場合でも、量子系において正確にエンコードされ得ることを示す。
【０２６６】
本開示の局面は、量子アルゴリズムが、一定でない持続時間および一定でない光学的位相を有する光パルスを、複数のキュービットの少なくともいくつかに適用することにより実行され得ることを示す。
【０２６７】
本開示の局面は、ヒューリスティック最適化戦略が、パラメーターの多くの初期推測を使用する腕ずくのアプローチにより必要とされる
【数Ｅ−４６３】
2021536610.tif 000782
リソースなしで、
【数Ｅ−４６４】
2021536610.tif 000783
回で、変動性量子アルゴリズムにおける準最適変動性パラメーターを見出し得ることを示す。
【０２６８】
本開示の局面は、量子近似最適化アルゴリズムが、消滅スペクトルギャップに関連する難題を克服するために非断熱的機構を利用することを示す。
【０２６９】
本開示の局面は、組合せ最適化問題の頂点の番号付け替えが、量子系に、より広範囲の部類の問題の例を実行させることを示す。
【図１】
2021536610.tif 000790
【図２−１】
2021536610.tif 000791
【図２−２】
2021536610.tif 000792
【図３】
2021536610.tif 000793
【図４】
2021536610.tif 000794
【図５】
2021536610.tif 000795
【図６】
2021536610.tif 000796
【図７】
2021536610.tif 000797
【図８】
2021536610.tif 000798
【図９】
2021536610.tif 000799
【図１０】
2021536610.tif 000800
【図１１】
2021536610.tif 000801
【図１２−１】
2021536610.tif 000802
【図１２−２】
2021536610.tif 000803
【図１２−３】
2021536610.tif 000804
【図１２−４】
2021536610.tif 000805
【図１３】
2021536610.tif 000806
【図１４】
2021536610.tif 000807
【図１５−１】
2021536610.tif 000808
【図１５−２】
2021536610.tif 000809
【図１６−１】
2021536610.tif 000810
【図１６−２】
2021536610.tif 000811
【図１７−１】
2021536610.tif 000812
【図１７−２】
2021536610.tif 000813
【図１７−３】
2021536610.tif 000814
【図１７−４】
2021536610.tif 000815
【図１８−１】
2021536610.tif 000816
【図１８−２】
2021536610.tif 000817
【図１９】
2021536610.tif 000818
【図２０−１】
2021536610.tif 000819
【図２０−２】
2021536610.tif 000820
【図２１】
2021536610.tif 000821
【図２２】
2021536610.tif 000822
【図２３】
2021536610.tif 000823
【図２４−１】
2021536610.tif 000824
【図２４−２】
2021536610.tif 000825
【図２４−３】
2021536610.tif 000826
【図２５−１】
2021536610.tif 000827
【図２５−２】
2021536610.tif 000828
【国際調査報告】
2021536610.tif 000829
2021536610.tif 000830
2021536610.tif 000831