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株式会社
支柱及び設置方法
1日前
KDDI株式会社
情報処理装置及び情報処理方法
今日
KDDI株式会社
情報処理装置及び情報処理方法
27日前
KDDI株式会社
光ニューラルネットワーク装置
1日前
KDDI株式会社
画像フィルタ装置及びプログラム
12日前
KDDI株式会社
通信装置、無線デバイス及びプログラム
12日前
KDDI株式会社
情報処理装置、情報処理方法及びプログラム
6日前
KDDI株式会社
情報処理装置、情報処理方法及びプログラム
26日前
KDDI株式会社
情報処理装置、情報処理方法及びプログラム
26日前
KDDI株式会社
情報処理装置、情報処理方法及びプログラム
19日前
KDDI株式会社
情報処理装置、情報処理方法及びプログラム
12日前
KDDI株式会社
情報処理装置、情報処理方法及びプログラム
12日前
KDDI株式会社
画像復号装置、画像復号方法及びプログラム
28日前
KDDI株式会社
情報処理装置、情報処理方法及びプログラム
今日
KDDI株式会社
映像復号装置、映像復号方法及びプログラム
5日前
KDDI株式会社
情報処理装置、情報処理方法及び情報処理システム
15日前
KDDI株式会社
暗号システム、暗号化装置、復号装置及びプログラム
1日前
KDDI株式会社
情報処理システム、情報処理方法及び情報処理装置。
19日前
KDDI株式会社
報酬設定装置、報酬設定方法、及び報酬設定プログラム
5日前
KDDI株式会社
効率的なデータの転送のための制御装置、制御方法、及びプログラム
20日前
KDDI株式会社
効率的なセル・サーチを行う基地局、無線端末、通信方法及びプログラム
12日前
KDDI株式会社
効率的なセル・サーチを行う基地局、無線端末、通信方法及びプログラム
12日前
KDDI株式会社
メッセージ配信装置、メッセージ配信方法、及びメッセージ配信プログラム
6日前
KDDI株式会社
情報処理装置及び情報処理方法
今日
KDDI株式会社
情報処理装置及び情報処理方法
27日前
KDDI株式会社
効率的にページングを行う基地局、ネットワーク装置、通信方法、及びプログラム
6日前
KDDI株式会社
デュアル・コネクティビティにおける輻輳を抑制する基地局、制御方法、及びプログラム
今日
KDDI株式会社
ポイント管理装置及びポイント管理方法
19日前
KDDI株式会社
情報処理装置、情報処理方法及びプログラム
26日前
KDDI株式会社
情報処理装置、情報処理方法及びプログラム
26日前
KDDI株式会社
画像復号装置、画像復号方法及びプログラム
5日前
KDDI株式会社
情報処理装置、情報処理方法及びプログラム
4日前
KDDI株式会社
情報処理装置、情報処理方法及びプログラム
今日
KDDI株式会社
情報処理装置、情報処理方法及び情報処理システム
15日前
KDDI株式会社
情報処理システム、情報処理方法及び情報処理装置。
19日前
KDDI株式会社
規制セルを含んだセル間のハンドオーバの適切な制御のための、基地局装置、制御方法、およびプログラム
今日
続きを見る