量子最適化

QuEraの256量子ビットの量子コンピューターは、さまざまな産業に関連する特定の最適化問題を解くことができる。このような最適化問題のひとつに、最大独立集合問題（MIS）がある。グラフの最大独立集合とは、どの頂点も連結していない（例えば辺を共有していない）、可能な限り最大の頂点の部分集合のことである。このような集合を見つけることはNP困難な問題である。一般的なグラフでは、近似解でさえ古典的なアルゴリズムでは効率的な解析が不可能な場合がある。多くの産業問題は、店舗立地のためのフットプリント最適化のようなMIS問題として定式化することができる（このアプリケーションノートを参照）。

幅広い最適化問題のエンコード

MISの解は、ここで説明するように、関連する他の最適化問題の解を生じさせることができる。量子サンプリング、量子メモリ符号化、量子機械学習、量子断熱アルゴリズム（QAA）や量子近似最適化アルゴリズム（QAOA）のような変分最適化など、様々なアルゴリズム技術を用いて、我々のマシンは他の様々な問題を解くことができる：

アンテナ配置

最小頂点カバー

最小支配集合

グラフ・カラーリング

重み付きグラフの重み付き最大独立集合は、特定の原子のエネルギーを他の原子よりも増加させることによって、アナログの中性原子量子コンピュータ上で符号化することもできる。ここで説明するように、これはさらなる最適化問題を引き起こす。

二次無制約バイナリ最適化(QUBO)

整数分解

巧みな符号化によって、これらの問題は、より大きなグラフ上のMIS問題にも変換することができ、その規模は量子ビット数の最大2乗に比例する。

中性原子アレイから量子コンピュータを作る

最大独立集合を見つける

リュードベリ遮断効果とは、近接した2つの中性原子が同時にリュードベリ状態に励起されるときに起こる量子現象である。この効果を利用して、グラフの最大独立集合（MIS）を求めることができる。このプロセスでは、グラフを中性原子の配列にエンコードする。このエンコーディングは、グラフの辺を共有する2つの頂点が、互いにリュードベリ遮断半径内にある2つの原子に対応するように行われる。系の全エネルギーを最大数の原子を励起するのに十分な高さまで上げることで、系全体の状態は最大独立集合に対応する。解は、原子の状態（励起状態か否か）を測定することによって決定される。励起された原子群がMISを表す。

画像A：リュードベリ封鎖に制約された励起原子の最大集合。

画像B：赤でハイライト：グラフの最大独立集合（どの頂点も辺を共有しないような頂点の最大部分集合）。

効率的なソリューション

中性原子プロセッサでMIS問題を解くには、原子の自然な振る舞いを利用するため、最小限のオーバーヘッドで済む。対象とするグラフがユニットディスクグラフ（UDG）であれば、256個の量子ビット上に256個の変数を持つMIS問題をエンコードすることができる。あるグラフに対しては、アナログ中性原子プロセッサが効率的にMISを見つけることができる。最適化問題を解く標準的なアルゴリズムである古典的なシミュレーテッド・アニーリングと比較すると、正確に定義されたグラフの集合では、問題の大きさに応じて中性原子プロセッサの方が有利にスケールすることがわかる。性能の詳細については、この結果の出版物（）、またはこのブログ記事をお読みください。

MISの産業応用

アンテナ配置
（最大独立セット）

通信サービスのカバレッジを最大化するには、特定のエリア内にアンテナを高密度に配置する必要がある。しかし、信号の干渉はこの目的にとって難題である。カバーエリアは重複してはならず、アンテナ間の最小距離規制は政府機関によってしばしば課される。すべての配置候補地の中で、最適なアンテナ配置は、2つのカバーエリアが交差しない最大独立集合に対応します。この問題は、各アンテナに付加された「重み」を最大化することで拡張することができ、この「重み」は、総カバレッジエリアや顧客数などの変数を表すことができる。これらの原理は、IoTアプリケーションのセンサー配置や、店舗や配送センターの戦略的配置のためのフットプリント最適化など、関連する課題にも適用できる。

ポートフォリオ最適化（最大閥）

In the financial industry, optimizing portfolios of assets, such as stocks or bonds, can enhance returns. Generally, Maximum Independent Sets (MISs) and their complement, maximum cliques, are valuable for deriving nontrivial insights into the correlation properties of large datasets. This information can guide strategies for hedging and diversification. One can construct a 'market graph,' where stocks correspond to vertices and vertices are connected when their correlations, θ_ij, exceed a threshold, Θ. For instance, setting θ_ij<Θ<0 and searching for graph cliques generates collections of mutually anti-correlated assets, maximizing returns while minimizing risk. Conversely, cliques obeying the limit θ_ij>Θ>0 generate portfolios of positively-correlated assets whose prices move in tandem, as might occur for assets within the same market.

5Gネットワーク（最小支配集合）

5Gアーキテクチャは、携帯電話間やネットワーク接続された自動車間など、デバイス間（D2D）通信ネットワークへの利用が増加している。これは、混雑したコンサートや密集した高速道路交通のようなシナリオに特に関連している。このようなネットワークのノードは、隣接する自律走行車が情報を交換するときに見られるように、ブルートゥースなどの近距離プロトコルを使って互いに通信することができる。あるいは、コンサート来場者が写真をアップロードするときのように、セルタワーの広範な無線ネットワークに接続することもできる。
しかし、すべてのノードをセルタワーの広範なネットワークに接続すると、過負荷になる可能性がある。この問題を軽減するために、ノードのサブセットをゲートウェイノードとして選択し、これらのノードだけをセルネットワークに接続することができます。そして、その地域の他のすべてのノードは、範囲内のゲートウェイノードへの直接接続を通じて、より広範なインターネットに接続することができ、それによってセルタワーの帯域幅を管理可能なレベルまで減らすことができる。