特許ウォッチ

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

発明の詳細な説明【技術分野】
【０００１】
本発明は、量子計算機上で組合せ最適化問題の実行可能解を探索する量子探索アルゴリズム及び方法に係り、特に、組合せ最適化問題の制約条件を満たした全ての実行可能解を分割統治法により高速に探索する量子探索アルゴリズム及び方法に関する。
続きを表示（約 1,600 文字）【背景技術】
【０００２】
分割統治アルゴリズムは、ある問題を複数の小さなサブ問題に分割し、それぞれのサブ問題を独立に解いた後、その結果を組み合わせて元の問題の解を求める近似アルゴリズムであり、組み合わせ最適化問題などの大規模な問題に対して使われる手法の一つである。
【０００３】
非特許公報１では、代表的な組み合わせ最適化問題である巡回セールスマン問題（TSP）を分割統治アルゴリズムで解くための手法が提案されている。具体的には、初めに都市の集合を重複しない部分集合にそれぞれ分割し、各集合は他の分割された集合から独立して解くことができる部分問題とみなす。各部分問題を解くために２段階のアプローチが用いられる。
【０００４】
第1段階では、各集合に対して局所探索アルゴリズムを適用することで初期解が得られる。第２段階では、反復法を用いて初期解を改良することで最適解または最適解に近い解が得られる。そして各部分問題を解いた後、K-opt法を用いて各部分問題の解を元の問題に結合する。この２段階のアプローチとK-opt法の手法とを用いることで、これまでよりも大規模な巡回セールスマン問題を効率的に解くことができる。
【０００５】
一方で、量子コンピュータには組み合わせ最適化問題のような大規模な問題を高速に解くことが期待されている。量子探索アルゴリズムは、量子コンピュータを用いて古典コンピュータよりも解を探索する計算量を削減するアルゴリズムである。
【０００６】
量子探索アルゴリズムを用いて組合せ最適化を高速に解く手法として、非特許公報２には、組み合わせ最適化問題である巡回セールスマン問題の最適解を古典ハイブリッド量子探索アルゴリズムで解く手法が提示されている。
【０００７】
このアルゴリズムは、入力値に任意の一つの実行可能解の経路情報を入れると、それに対応した経路コストを算出できる。非特許文献２の量子探索アルゴリズムでは、任意の解の位相をπ回転するオラクル演算子を使用するグローバーアルゴリズムを拡張し、経路コスト分回転させるコストオラクル演算子及びグローバーの拡散行列を使用し、入力状態に全ての実行可能解を入力することで最小コストの経路状態を増幅させることができる。
【先行技術文献】
【非特許文献】
【０００８】
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).
【発明の概要】
【発明が解決しようとする課題】
【０００９】
古典計算機上で動作する分割統治アルゴリズムを量子計算機上に実装することは容易ではない。これは古典計算機と量子計算機とは仕組みがまったく異なることに起因する。古典計算機では、与えられた問題が連続的に実行した命令によって処理される。例えば、古典計算機では２つの数字を足し算する場合、一つずつの演算を実行して足し算を行う。
【００１０】
これに対して、量子計算機では量子ビットを使用して複数の入力状態が同時に処理される。そのため、古典計算機のように足し算をするために一連の演算を行うのではなく、足し算の結果を得るための一つの演算を行うことになる。
（【００１１】以降は省略されています）

関連特許