特許ウォッチ

公開番号2025009933
公報種別公開特許公報(A)
公開日2025-01-20
出願番号2024099942
出願日2024-06-20
発明の名称キュービット・ルーティング
出願人富士通株式会社
代理人個人,個人
主分類G06N 10/20 20220101AFI20250109BHJP(計算;計数)
要約【課題】キュービット・ルーティングを提供する。
【解決手段】方法は、第1のノードおよび第2のノードがそれぞれ第1のキュービットおよび第2のキュービットを表すグラフを取得することを含みうる。本方法は、一つまたは複数のエッジに沿った第1のキュービットと第2のキュービットの間の候補経路を生成することを含んでいてもよく、各候補経路は、第1のノードと第2のノードの間のターゲット・ノードに到達する経路を指定する。本方法は、複数の経路ペアについてスコアを計算することを含んでいてもよく、それぞれのスコアは、それぞれの経路ペアが、ターゲット・エッジを介してどのくらい効率的に第1のノードを第2のノードにルーティングするかを示す。スコアは、量子回路の動作が実行される順序に基づいて重み付けされてもよく、より早期の動作がより後期の動作よりも大きな重みを与えられる。本方法は、ターゲット・エッジを介して第1のノードを第2のノードにルーティングするための最高のスコアに対応する経路ペアを選択することを含みうる。
【選択図】図6
特許請求の範囲【請求項１】
複数のノードおよび複数のエッジを含むグラフを取得する段階であって、前記複数のノードのうちの第1のノードが量子回路の第1のキュービットを表し、前記複数のノードのうちの第2のノードが前記量子回路の第2のキュービットを表す、段階と；
前記複数のエッジのうちの一つまたは複数のエッジに沿って前記第1のノードと前記第2のノードとの間の第1の候補経路のセットを生成する段階であって、前記第1の候補経路のセットにおける各第1の候補経路は、前記第1のノードと前記第2のノードとを直接接続するターゲット・エッジにおいて互いに隣接して到達するように前記第1のノードおよび前記第2のノードがそれに沿って移動する経路を指定する、段階と；
複数の第1の経路ペアについて第1のスコアを計算する段階であって、それぞれの第1のスコアは、前記複数の第1の経路ペアの各第1の経路ペアが前記ターゲット・エッジを介して前記第1のノードを前記第2のノードにどれくらい効率的にルーティングするかを示し、
前記複数の第1の経路ペアのうちの特定の第1の経路ペアは、特定の第1の候補経路と、前記第1のキュービットと前記第2のキュービットとの間の、前記特定の第1の候補経路上にある特定のターゲット・エッジとを含み、
前記第1のスコアは、前記第1のキュービットおよび前記第2のキュービットを含む前記量子回路の動作が実行される順序に関して重み付けされ、より早期の動作がより後期の動作よりも大きな重みを与えられる、
段階と；
前記ターゲット・エッジを介して前記第1のノードを前記第2のノードにルーティングするための最も高い第1のスコアに対応する前記第1の経路ペアを選択する段階とを含む、
方法。
続きを表示（約 3,700 文字）【請求項２】
第3のキュービットに対応する第3のノードおよび第4のキュービットに対応する第4のノードを識別する段階であって、前記第3のキュービットおよび前記第4のキュービットは、前記第1のキュービットおよび前記第2のキュービットによって実行される第1の動作の後に第2の動作を実行するように構成される、段階と；
前記グラフの前記エッジのうちの一つまたは複数に沿って前記第3のノードと前記第4のノードとの間の第2の候補経路のセットを生成する段階であって、前記第2の候補経路のセットにおける各第2の候補経路が、前記第3のノードと前記第4のノードとの間のターゲット・エッジに到達するために前記第3のノードおよび前記第4のノードがそれに沿って移動する経路を指定する、段階と；
複数の第2の経路ペアについて第2のスコアを計算する段階であって、それぞれの第2のスコアは、前記複数の第2の経路ペアの各第2の経路ペアが前記ターゲット・エッジを介して前記第3のノードを前記第4のノードにどのくらい効率的にルーティングするかを示す、段階と；
前記ターゲット・エッジを介して前記第3のノードを前記第4のノードにルーティングするための最も高い第2のスコアに対応する前記第2の経路ペアを選択する段階とをさらに含む、
請求項１に記載の方法。
【請求項３】
前記量子回路の最後の動作において使用されるキュービットに関連付けられたノードがルーティングされるまで、請求項２に記載の方法の段階を繰り返すことをさらに含む、請求項２に記載の方法。
【請求項４】
前記候補経路のセットのうちの特定の候補経路を生成することは：
A）前記第1のノードに対応する第1のノード位置および前記第2のノードに対応する第2のノード位置を決定する段階と；
B）前記第1のノードに直接接続された第5のノードを識別する段階であって、前記第5のノードは、前記第1のノード位置に隣接する第5のノード位置を有する、段階と；
C）前記第5のノード位置が前記第1のノード位置よりも前記第2のノード位置に近いかどうかを判定する段階と；
D）前記第5のノード位置が前記第1のノード位置よりも前記第2のノード位置に近いと判定することに応答して、前記第1のノード位置を前記第5のノード位置として設定する段階と；
E）前記第1のノード位置が前記第2のノード位置に隣接するまで、段階B）、C）、およびD）を逐次反復的に繰り返す段階とを含む、
請求項１に記載の方法。
【請求項５】
前記複数の第1のペアについて前記第1のスコアを計算することは、前記第1のノードおよび前記第2のノードが関係する前記量子回路の前記動作が実行されるようにスケジュールされている順序と、前記第1のノードおよび前記第2のノードをルーティングした後の前記量子回路の後続の動作に関わるノード間の距離とに基づく、請求項１に記載の方法。
【請求項６】
前記複数の第1のペアについて前記第1のスコアを計算することは、
TIFF
2025009933000013.tif
19
170
と表され、
δ
G
(e,p)は、特定の第1のスコアを表し；
S(g
i
,e,p)は、特定の候補経路pを通じて第1のノードg
i
を第2のノードeにルーティングするために使用されるスワップ・ゲートの数を表し；
λ
w(gk)
は、前記量子回路の前記動作が実行されるようにスケジュールされている順序に基づく優先因子を表し；
d
gi,e,p
(g
k
)は、前記特定の候補経路に沿って前記第1のノードを前記第2のノードにルーティングした後のノード間の距離を表す、
請求項５に記載の方法。
【請求項７】
実行されることに応答して、システムに動作を実行させる命令を記憶するように構成された一つまたは複数の非一時的なコンピュータ可読記憶媒体であって、前記動作は：
複数のノードおよび複数のエッジを含むグラフを取得する段階であって、前記複数のノードのうちの第1のノードが量子回路の第1のキュービットを表し、前記複数のノードのうちの第2のノードが前記量子回路の第2のキュービットを表す、段階と；
前記複数のエッジのうちの一つまたは複数のエッジに沿って前記第1のノードと前記第2のノードとの間の第1の候補経路のセットを生成する段階であって、前記第1の候補経路のセットにおける各第1の候補経路は、前記第1のノードと前記第2のノードとを直接接続するターゲット・エッジにおいて互いに隣接して到達するように前記第1のノードおよび前記第2のノードがそれに沿って移動する経路を指定する、段階と；
複数の第1の経路ペアについて第1のスコアを計算する段階であって、それぞれの第1のスコアは、前記複数の第1の経路ペアの各第1の経路ペアが前記ターゲット・エッジを介して前記第1のノードを前記第2のノードにどれくらい効率的にルーティングするかを示し、
前記複数の第1の経路ペアのうちの特定の第1の経路ペアは、特定の第1の候補経路と、前記第1のキュービットと前記第2のキュービットとの間の、前記特定の第1の候補経路上にある特定のターゲット・エッジとを含み、
前記第1のスコアは、前記第1のキュービットおよび前記第2のキュービットを含む前記量子回路の動作が実行される順序に関して重み付けされ、より早期の動作がより後期の動作よりも大きな重みを与えられる、
段階と；
前記ターゲット・エッジを介して前記第1のノードを前記第2のノードにルーティングするための最も高い第1のスコアに対応する前記第1の経路ペアを選択する段階とを含む、
一つまたは複数の非一時的なコンピュータ可読記憶媒体。
【請求項８】
前記動作が：
第3のキュービットに対応する第3のノードおよび第4のキュービットに対応する第4のノードを識別する段階であって、前記第3のキュービットおよび前記第4のキュービットは、前記第1のキュービットおよび前記第2のキュービットによって実行される第1の動作の後に第2の動作を実行するように構成される、段階と；
前記グラフの前記エッジのうちの一つまたは複数に沿って前記第3のノードと前記第4のノードとの間の第2の候補経路のセットを生成する段階であって、前記第2の候補経路のセットにおける各第2の候補経路が、前記第3のノードと前記第4のノードとの間のターゲット・エッジに到達するために前記第3のノードおよび前記第4のノードがそれに沿って移動する経路を指定する、段階と；
複数の第2の経路ペアについて第2のスコアを計算する段階であって、それぞれの第2のスコアは、前記複数の第2の経路ペアの各第2の経路ペアが前記ターゲット・エッジを介して前記第3のノードを前記第4のノードにどのくらい効率的にルーティングするかを示す、段階と；
前記ターゲット・エッジを介して前記第3のノードを前記第4のノードにルーティングするための最も高い第2のスコアに対応する前記第2の経路ペアを選択する段階とをさらに含む、
請求項７に記載の一つまたは複数の非一時的なコンピュータ可読記憶媒体。
【請求項９】
前記量子回路の最後の動作において使用されるキュービットに関連付けられたノードがルーティングされるまで、請求項８に記載の方法の段階を繰り返すことをさらに含む、請求項８に記載の一つまたは複数の非一時的なコンピュータ可読記憶媒体。
【請求項１０】
前記候補経路のセットのうちの特定の候補経路を生成することは：
A）前記第1のノードに対応する第1のノード位置および前記第2のノードに対応する第2のノード位置を決定する段階と；
B）前記第1のノードに直接接続された第5のノードを識別する段階であって、前記第5のノードは、前記第1のノード位置に隣接する第5のノード位置を有する、段階と；
C）前記第5のノード位置が前記第1のノード位置よりも前記第2のノード位置に近いかどうかを判定する段階と；
D）前記第5のノード位置が前記第1のノード位置よりも前記第2のノード位置に近いと判定することに応答して、前記第1のノード位置を前記第5のノード位置として設定する段階と；
前記第1のノード位置が前記第2のノード位置に隣接するまで、段階B）、C）、およびD）を逐次反復的に繰り返すことを含む、
請求項７に記載の一つまたは複数の非一時的なコンピュータ可読記憶媒体。
（【請求項１１】以降は省略されています）
発明の詳細な説明【技術分野】
【０００１】
本開示は、概括的には、キュービット・ルーティングのシステムおよび方法に関する。
続きを表示（約 1,400 文字）【背景技術】
【０００２】
量子コンピュータは、情報を1、0、または1と0同時として表すことができるキュービット（「キュービット」）を使用することができる。量子コンピュータは、最適化問題、整数因数分解、シミュレーション・モデル化、および／またはデータ解析などのいくつかのタイプの計算を、古典的なコンピューティング・システムよりも効率的に、および／またはより正確に実行することができる。しかしながら、既存の量子コンピュータは、限られた数のキュービットしか含まず、その結果、いくつかの計算的に要求の厳しいタスクを実行することができないか、またはその用途に好適でないため、既存の量子コンピュータは、ノイズのある中規模量子（noisy intermediate-scale quantum、NISQ）デバイスとして分類されうる。
【０００３】
本開示において請求される主題は、何らかの欠点を解決する実施形態、または、上述したような環境においてのみ動作する実施形態に限定されない。むしろ、この背景は、本開示に記載されたいくつかの実施形態が実施されうる1つの例示的な技術分野を示すためにのみ提供される。
【発明の概要】
【課題を解決するための手段】
【０００４】
ある実施形態のある側面によれば、方法は、第1のノードおよび第2のノードがそれぞれ第1のキュービットおよび第2のキュービットを表すグラフを取得することを含みうる。本方法は、一つまたは複数のエッジに沿った第1のキュービットと第2のキュービットの間の候補経路を生成することを含んでいてもよく、各候補経路は、第1のノードと第2のノードの間のターゲット・ノードに到達する経路を指定する。本方法は、複数の経路ペアについてスコアを計算することを含んでいてもよく、それぞれのスコアは、それぞれの経路ペアが、ターゲット・エッジを介してどのくらい効率的に第1のノードを第2のノードにルーティングするかを示す。スコアは、量子回路の動作が実行される順序に基づいて重み付けされてもよく、より早期の動作がより後期の動作よりも大きな重みを与えられる。本方法は、ターゲット・エッジを介して第1のノードを第2のノードにルーティングするための最高のスコアに対応する経路ペアを選択することを含みうる。
【０００５】
実施形態の目的および利点は、少なくとも、特許請求の範囲において具体的に指摘される要素、特徴、および組み合わせによって実現され、達成される。上記の一般的な記述および以下の詳細な記述はいずれも、説明するものであって、特許請求される発明を制約するものではないことが理解される。
【図面の簡単な説明】
【０００６】
例示的実施形態は、添付の図面を通して、さらなる特異性および詳細さをもって記述され、説明される。
【０００７】
本開示の一つまたは複数の実施形態による、初期キュービット・マッピングが決定されうる例示的な動作環境の図である。
【０００８】
量子コンピューティング・システムのキュービットを表す第1の例示的なグラフを示す。
【０００９】
量子コンピューティング・システムのキュービットを表す第2の例示的なグラフを示す。
【００１０】
本開示の一つまたは複数の実施形態による、初期キュービット・マッピングを決定する例示的方法のフローチャートである。
（【００１１】以降は省略されています）

関連特許