特許ウォッチ

公開番号2024058604
公報種別公開特許公報(A)
公開日2024-04-25
出願番号2023170172
出願日2023-09-29
発明の名称量子コンピュータを用いた浅い回路上での最適化問題の解法
出願人富士通株式会社
代理人個人,個人
主分類G06N 10/60 20220101AFI20240418BHJP(計算;計数)
要約【課題】量子コンピュータを用いた浅い回路上での最適化問題の解法を提供する。
【解決手段】コンピューティング環境100において、システム102の動作は、現実世界の最適化問題に関連付けられたノード・ベースのグラフを含む入力を受信することと、ノード・ベースのグラフからエッジのサブセットを除去することによって疎グラフを生成することと、疎グラフに基づいて量子コンピュータ上で量子回路の演算子を定式化することと、最適化問題のためのコスト関数を定式化することと、量子コンピュータ上で量子回路を動作させて結果を生成し、結果を使用してコスト関数の値を推定し、値に基づいて演算子のパラメータを更新することを含む動作の集合を実行することと、コスト関数の推定された値が所定の閾値に近づくまで、更新されたパラメータを使用して動作の集合の実行を繰り返すことによって、最適化問題の最終的な解を生成することと、を含む。
【選択図】図1
特許請求の範囲【請求項１】
現実世界の最適化問題に関連付けられたノード・ベースのグラフを含む入力を受領する段階と；
前記ノード・ベースのグラフからエッジのサブセットを除去することによって疎グラフを生成する段階と；
前記疎グラフに基づいて量子コンピュータ上で量子回路の演算子を定式化する段階と；
前記現実世界の最適化問題のためのコスト関数を定式化する段階と；
動作の集合であって：
前記量子コンピュータ上で前記量子回路を動作させて結果を生成し；
前記結果を使用して前記コスト関数の値を推定し；
前記値に基づいて前記量子回路において前記演算子のパラメータを更新することを含む、動作の集合を実行する段階と；
前記コスト関数の推定された値が事前定義された閾値に近づくまで、更新されたパラメータを使用して動作の前記集合の実行を繰り返すことによって、前記現実世界の最適化問題の最終的な解を生成する段階とを含む、
方法。
続きを表示（約 1,500 文字）【請求項２】
前記現実世界の最適化問題は、グラフ・ベース最適化問題であり、前記ノード・ベースのグラフは、前記ノード・ベースのグラフの複数のノード間の関係を、前記複数のノードのノード対の間のエッジを通じて記述する、請求項１に記載の方法。
【請求項３】
前記グラフ・ベースの最適化問題は、最大カット問題である、請求項２に記載の方法。
【請求項４】
超大規模集積（VLSI）チップ設計タスクの2層ビア最小化問題に関連する入力データとしてチップの一過性のルーティング・データを受領する段階と；
前記一過性のルーティング・データに基づいて前記チップについてのレイアウト・グラフを構築する段階と；
前記レイアウト・グラフに基づいて、前記2層ビア最小化問題を最大カット問題として定式化する段階とをさらに含み、
前記ノード・ベースのグラフは前記レイアウト・グラフであり、前記コスト関数は前記最大カット問題についての目的関数をエンコードし、前記最終的な解は前記最大カット問題の解であり、前記レイアウト・グラフが最小の総ビアをもつ2つのグラフに分割されるような前記チップのレイアウト割り当てを含む、
請求項１に記載の方法。
【請求項５】
データ・クラスタリング問題に関連付けられた入力データとして、データセットのデータポイントに対応する属性および前記データポイント間の類似性メトリックを受領する段階と；
前記類似性メトリックおよび前記属性に基づいて、前記データポイントのすべての対についての隣接行列を生成する段階であって、
前記隣接行列は、前記データセットの前記データポイントの重み付けされた無向グラフ表現を定義する、段階と；
前記データ・クラスタリング問題を、前記隣接行列に基づく最小‐最大カット問題として定式化する段階であって、
前記ノード・ベースのグラフは、前記データポイントの前記重み付けされた無向グラフ表現であり、
前記コスト関数は、前記最小‐最大カット問題についての目的関数をエンコードし、
前記最終的な解は、前記最小‐最大カット問題の解であり、前記データポイントの、クラスターの集合への分割を含む、
請求項１に記載の方法。
【請求項６】
前記ノード・ベースのグラフは、重み付けされたグラフまたは重み付けされていないグラフである、請求項１に記載の方法。
【請求項７】
前記疎グラフは、グラフ近似関数、ヒューリスティック、または確率的グラフ疎化関数を使用することによって生成される、請求項１に記載の方法。
【請求項８】
前記入力は、前記ノード・ベースのグラフの疎化のためのターゲット比をさらに含み、
前記サブセット内のエッジの数と前記ノード・ベースのグラフ内の前記エッジの数との比が前記ターゲット比以下になるように、前記エッジの前記サブセットが除去される、
請求項１に記載の方法。
【請求項９】
前記量子回路は、前記演算子のための量子論理ゲートの集合と、前記演算子および前記量子論理ゲートがその上で動作するように構成されているキュービットの集合とを含む量子近似最適化アルゴリズム（QAOA）回路である、請求項１に記載の方法。
【請求項１０】
キュービットの前記集合は、前記疎グラフの少なくとも1つのノード対に対応する、請求項１に記載の方法。
（【請求項１１】以降は省略されています）
発明の詳細な説明【技術分野】
【０００１】
本開示で論じられる実施形態は、量子コンピュータを使用して浅い回路上で最適化問題を解くことに関する。
続きを表示（約 1,400 文字）【背景技術】
【０００２】
近い将来の量子デバイス上での組み合わせ最適化は、量子の利点を実証するための有望な経路でありうる。しかしながら、これらのデバイスの能力は、高い雑音または誤り率によって制約されることがある。量子近似最適化アルゴリズム（Quantum Approximate Optimization Algorithm、QAOA）は、近い将来の量子デバイスを使用して最適化における量子の利点を実証するための有望な候補アルゴリズムである。しかしながら、ハードウェアの接続性の制限に起因して、ハードウェア接続性と整列されないことがありうるグラフについては、目的関数をエンコードする位相演算子を実装するために、追加のゲートが必要とされることがある。多くのグラフ・ベースの最適化問題について、従来のQAOAアプローチは、最適化のために所望されるよりも多くの量子資源を利用することがある。
【０００３】
本開示において特許請求される主題は、何らかの欠点を解決する実施形態、または上述したような環境においてのみ動作する実施形態に限定されない。むしろ、この背景は、本開示で説明されるいくつかの実施形態が実施されうる1つの例示的な技術領域を示すために提供されるにすぎない。
【発明の概要】
【課題を解決するための手段】
【０００４】
本開示のある側面によれば、動作は、現実世界の最適化問題に関連付けられたノード・ベースのグラフを含む入力を受信することと、前記ノード・ベースのグラフからエッジのサブセットを除去することによって疎グラフを生成することとを含みうる。動作は、前記疎グラフに基づいてゲート・ベースの量子コンピュータ上で量子回路の演算子を定式化することと、前記現実世界の最適化問題のためのコスト関数を定式化することとをさらに含みうる。動作は、ゲート・ベース量子コンピュータ上で量子回路を動作させて結果を生成し、前記結果を使用して前記コスト関数の値を推定し、前記値に基づいて前記演算子のパラメータを更新することを含みうる、動作の集合を実行することをさらに含みうる。動作は、前記コスト関数の推定された値が所定の閾値に近づくまで、更新されたパラメータを使用して動作の前記集合の実行を繰り返すことによって、前記現実世界の最適化問題の最終的な解を生成することをさらに含んでいてもよい。
【０００５】
実施形態の目的および利点は、少なくとも、特許請求の範囲において特に指摘される要素、特徴、および組み合わせによって実現および達成される。
【０００６】
前述の一般的な説明および以下の詳細な説明の両方は、例として与えられ、説明的であり、特許請求される本発明を限定するものではない。
【図面の簡単な説明】
【０００７】
例示的な実施形態は、添付の図面の使用を通じて追加の特異性および具体性および詳細をもって記載および説明される。
【０００８】
量子コンピュータを使用して浅い回路上で最適化問題を解くための例示的なコンピューティング環境を表す図である。
【０００９】
量子コンピュータを使用して浅い回路上で最適化問題を解くための例示的な方法のフローチャートである。
【００１０】
量子コンピュータを使用して浅い回路上でビア最小化問題を解くための例示的な動作を示す図である。
（【００１１】以降は省略されています）

関連特許