TOP特許意匠商標
特許ウォッチ Twitter
公開番号2025075210
公報種別公開特許公報(A)
公開日2025-05-15
出願番号2023186209
出願日2023-10-31
発明の名称量子探索アルゴリズム及び方法
出願人KDDI株式会社,学校法人東京理科大学,学校法人 芝浦工業大学
代理人個人,個人
主分類G06N 10/60 20220101AFI20250508BHJP(計算;計数)
要約【課題】量子計算機上で制約条件を有する組合せ最適化問題の実行可能解を探索する際に、制約条件を満たした全ての実行可能解を分割統治法により少ない計算量で探索する。
【解決手段】最適化問題解決アルゴリズム1は初期化部10、空間分割部20及び統合部30を主要な構成とする。初期化部10は、実行可能解に係る全ての組み合わせ状態を表現する全空間(初期状態)の演算子を用意する。空間分割部20は、組合せ最適化問題がもつ制約条件を複数のサブ問題に分割するために、探索範囲の全空間を表現する演算子を制約条件ごとに複数の部分空間に分割する。統合部30は、分割されたそれぞれの演算子を適当な回数分だけ同様に埋め込み、計算処理を行って測定を行う。
【選択図】図1
特許請求の範囲【請求項1】
組合せ最適化問題の実行可能解を分割統治法により量子計算機上で探索する量子探索アルゴリズムにおいて、
組合せ最適化問題の全ての組み合わせ状態を表現する量子状態の全空間を用意する初期化部と、
前記全空間を組合せ最適化問題の制約条件ごとに複数の部分空間に分割する空間分割部と、
前記部分空間の量子状態毎に量子探索を同時に実行した結果を統合する統合部とを含むことを特徴とする量子探索アルゴリズム。
続きを表示(約 880 文字)【請求項2】
前記量子探索がグローバーアルゴリズムを用いたグローバー探索であってオラクル演算子及びグローバー拡散演算子を交互に作用させることを繰り返し、
前記空間分割部が全空間をN分割すると、前記統合部では前記オラクル演算子及びグローバー拡散演算子がそれぞれN分割され、N個の各部分空間に対して同時に探索が実行されることを特徴とする請求項1に記載の量子探索アルゴリズム。
【請求項3】
前記組合せ最適化問題が2つの制約条件をもつ巡回セールスマン問題であると、前記オラクル演算子において解を回転させる際の位相θを-π/2としたことを特徴とする請求項2に記載の量子探索アルゴリズム。
【請求項4】
前記組合せ最適化問題が巡回セールスマン問題であり、
各制約条件をQUBOで定式化して量子計算機のイジングモデルと等価化することを特徴とする請求項1ないし3のいずれかに記載の量子探索アルゴリズム。
【請求項5】
量子計算機が、組合せ最適化問題の実行可能解を分割統治法により量子計算機上で探索する量子探索方法において、
組合せ最適化問題を制約条件ごとに複数のサブ問題に分割し、
前記サブ問題ごとに量子探索を同時に実行した結果を統合することを特徴とする量子探索方法。
【請求項6】
前記量子探索がグローバーアルゴリズムを用いたグローバー探索であってオラクル演算子及びグローバー拡散演算子を交互に作用させることを繰り返し、
前記組合せ最適化問題を制約条件ごとにN個のサブ問題に分割すると、前記オラクル演算子及びグローバー拡散演算子がそれぞれN分割され、N個のサブ問題に対して同時に探索が実行されることを特徴とする請求項5に記載の量子探索方法。
【請求項7】
前記組合せ最適化問題が2つの制約条件をもつ巡回セールスマン問題であると、前記オラクル演算子において解を回転させる際の位相θを-π/2としたことを特徴とする請求項6に記載の量子探索方法。

発明の詳細な説明【技術分野】
【0001】
本発明は、量子計算機上で組合せ最適化問題の実行可能解を探索する量子探索アルゴリズム及び方法に係り、特に、組合せ最適化問題の制約条件を満たした全ての実行可能解を分割統治法により高速に探索する量子探索アルゴリズム及び方法に関する。
続きを表示(約 1,600 文字)【背景技術】
【0002】
分割統治アルゴリズムは、ある問題を複数の小さなサブ問題に分割し、それぞれのサブ問題を独立に解いた後、その結果を組み合わせて元の問題の解を求める近似アルゴリズムであり、組み合わせ最適化問題などの大規模な問題に対して使われる手法の一つである。
【0003】
非特許公報1では、代表的な組み合わせ最適化問題である巡回セールスマン問題(TSP)を分割統治アルゴリズムで解くための手法が提案されている。具体的には、初めに都市の集合を重複しない部分集合にそれぞれ分割し、各集合は他の分割された集合から独立して解くことができる部分問題とみなす。各部分問題を解くために2段階のアプローチが用いられる。
【0004】
第1段階では、各集合に対して局所探索アルゴリズムを適用することで初期解が得られる。第2段階では、反復法を用いて初期解を改良することで最適解または最適解に近い解が得られる。そして各部分問題を解いた後、K-opt法を用いて各部分問題の解を元の問題に結合する。この2段階のアプローチとK-opt法の手法とを用いることで、これまでよりも大規模な巡回セールスマン問題を効率的に解くことができる。
【0005】
一方で、量子コンピュータには組み合わせ最適化問題のような大規模な問題を高速に解くことが期待されている。量子探索アルゴリズムは、量子コンピュータを用いて古典コンピュータよりも解を探索する計算量を削減するアルゴリズムである。
【0006】
量子探索アルゴリズムを用いて組合せ最適化を高速に解く手法として、非特許公報2には、組み合わせ最適化問題である巡回セールスマン問題の最適解を古典ハイブリッド量子探索アルゴリズムで解く手法が提示されている。
【0007】
このアルゴリズムは、入力値に任意の一つの実行可能解の経路情報を入れると、それに対応した経路コストを算出できる。非特許文献2の量子探索アルゴリズムでは、任意の解の位相をπ回転するオラクル演算子を使用するグローバーアルゴリズムを拡張し、経路コスト分回転させるコストオラクル演算子及びグローバーの拡散行列を使用し、入力状態に全ての実行可能解を入力することで最小コストの経路状態を増幅させることができる。
【先行技術文献】
【非特許文献】
【0008】
K. Srinivasan et al. "Solving for large-scale travelling salesman problem with divide-and-conquer strategy", SCIS & ICIS (2010).
D. Koch et al. "Gaussian Amplitude Amplification for Quantum Pathfinding", Entropy 24, no. 7: 963 (2022).
【発明の概要】
【発明が解決しようとする課題】
【0009】
古典計算機上で動作する分割統治アルゴリズムを量子計算機上に実装することは容易ではない。これは古典計算機と量子計算機とは仕組みがまったく異なることに起因する。古典計算機では、与えられた問題が連続的に実行した命令によって処理される。例えば、古典計算機では2つの数字を足し算する場合、一つずつの演算を実行して足し算を行う。
【0010】
これに対して、量子計算機では量子ビットを使用して複数の入力状態が同時に処理される。そのため、古典計算機のように足し算をするために一連の演算を行うのではなく、足し算の結果を得るための一つの演算を行うことになる。
(【0011】以降は省略されています)

特許ウォッチbot のツイートを見る
この特許をJ-PlatPatで参照する

関連特許

KDDI株式会社
アンテナ指向装置
18日前
KDDI株式会社
アンテナ指向装置
18日前
KDDI株式会社
共通鍵の長さを通知する装置
1か月前
KDDI株式会社
光増幅器及び光通信システム
25日前
KDDI株式会社
光増幅器及び光通信システム
15日前
KDDI株式会社
情報処理装置及び情報処理方法
24日前
KDDI株式会社
量子探索アルゴリズム及び方法
29日前
KDDI株式会社
情報処理装置及び情報処理方法
1か月前
KDDI株式会社
情報処理装置及び情報処理方法
2日前
KDDI株式会社
音響測位装置、方法及びプログラム
29日前
KDDI株式会社
256ビットルート鍵を利用する装置
1か月前
KDDI株式会社
無線アクセスネットワークの制御装置
17日前
KDDI株式会社
無線アクセスネットワークの制御装置
17日前
KDDI株式会社
演算装置、演算方法及び演算プログラム
15日前
KDDI株式会社
情報処理方法、プログラム及び情報処理装置
4日前
KDDI株式会社
情報処理装置、情報処理方法及びプログラム
1か月前
KDDI株式会社
情報処理装置、情報処理方法及びプログラム
1日前
KDDI株式会社
情報処理装置、情報処理方法及びプログラム
1か月前
KDDI株式会社
情報処理装置、情報処理方法及びプログラム
1日前
KDDI株式会社
情報処理装置、情報処理方法及びプログラム
1か月前
KDDI株式会社
情報処理方法、プログラム及び情報処理装置
17日前
KDDI株式会社
情報処理方法、プログラム及び情報処理装置
4日前
KDDI株式会社
情報処理装置、情報処理方法及びプログラム
1か月前
KDDI株式会社
画像復号装置、画像復号方法及びプログラム
3日前
KDDI株式会社
メッセージ認証コードの長さを通知する装置
1か月前
KDDI株式会社
5Gネットワークの制御プレーンにおける監視
1か月前
KDDI株式会社
偏向デバイス、基地局装置及びそれらでの方法
1か月前
KDDI株式会社
情報処理装置、情報処理方法及び情報処理システム
16日前
KDDI株式会社
情報集約装置、情報集約方法及び情報集約プログラム
29日前
KDDI株式会社
リスク分析装置、リスク分析方法及びリスク分析プログラム
1か月前
KDDI株式会社
秘密計算システム、ユーザ端末、演算サーバ及びプログラム
25日前
KDDI株式会社
強度の異なるアルゴリズムの2つの優先リストを備える基地局
1か月前
KDDI株式会社
移動通信ネットワークのネットワークノード、サーバ及びプログラム
1か月前
KDDI株式会社
飛行体及び接触方法
14日前
KDDI株式会社
ネットワーク装置、ユーザ端末、通信方法及びコンピュータプログラム
1か月前
KDDI株式会社
情報処理装置及び情報処理方法
24日前
続きを見る