特許ウォッチ

公開番号2025102526
公報種別公開特許公報(A)
公開日2025-07-08
出願番号2023220030
出願日2023-12-26
発明の名称量子計算方法、量子計算システム、及びプログラム
出願人学校法人早稲田大学
代理人弁理士法人ドライト国際特許事務所
主分類G06N 10/60 20220101AFI20250701BHJP(計算;計数)
要約【課題】コヒーレンス時間の限られた量子デバイスを用いて効率よく組合せ最適化問題を解く。
【解決手段】制約を有する組合せ最適化問題を複数のスピン変数で表されるイジングモデルを用いて解くために、量子デバイスは、イジングモデルの量子ゆらぎの強さを表すパラメータであるアニーリングパスにしたがって量子アニーリングを実行して、複数のスピン変数の量子状態を生成し(102)、量子状態の確率分布を生成する(104)。古典コンピュータは、量子状態を表す解に基づいて、制約を満たさない非実行可能解を制約を満たす実行可能解に変換する後処理を実行して(106)、後処理後の新たな確率分布を計算し(108)、新たな確率分布に基づいてイジングモデルのエネルギー期待値を計算し(110)、エネルギー期待値が小さくなるようにアニーリングパスを新たなアニーリングパスに更新する(112)。
【選択図】図1

特許請求の範囲【請求項１】
制約を有する組合せ最適化問題を複数のスピン変数で表されるイジングモデルを用いて解くための量子計算方法であって、
量子デバイスにより、前記イジングモデルの量子ゆらぎの強さを表すパラメータであるアニーリングパスにしたがって量子アニーリングを実行することにより、前記複数のスピン変数の量子状態を生成し、
前記量子デバイスにより、前記量子状態の確率分布を生成し、
古典コンピュータにより、前記量子状態を表す解に基づいて、前記制約を満たさない非実行可能解を前記制約を満たす実行可能解に変換する後処理を実行して、前記後処理後の新たな確率分布を計算し、
前記古典コンピュータにより、前記新たな確率分布に基づいて前記イジングモデルのエネルギー期待値を計算し、
前記古典コンピュータにより、前記エネルギー期待値が小さくなるように前記アニーリングパスを新たなアニーリングパスに更新する、量子計算方法。
続きを表示（約 940 文字）【請求項２】
前記エネルギー期待値が収束するまで、前記量子状態の生成、前記確率分布の生成、前記後処理、前記エネルギー期待値の計算、及び前記アニーリングパスの更新のプロセスを繰り返すことにより、前記組合せ最適化問題の最適解を求める、請求項１に記載の量子計算方法。
【請求項３】
前記後処理は局所最適化手法に基づいて実行される、請求項１に記載の量子計算方法。
【請求項４】
制約を有する組合せ最適化問題を複数のスピン変数で表されるイジングモデルを用いて解くための量子計算システムであって、
前記イジングモデルの量子ゆらぎの強さを表すパラメータであるアニーリングパスにしたがって量子アニーリングを実行することにより、前記複数のスピン変数の量子状態を生成し、前記量子状態の確率分布を生成する量子デバイスと、
前記量子状態を表す解に基づいて、前記制約を満たさない非実行可能解を前記制約を満たす実行可能解に変換する後処理を実行して、前記後処理後の新たな確率分布を計算し、前記新たな確率分布に基づいて前記イジングモデルのエネルギー期待値を計算し、前記エネルギー期待値が小さくなるように前記アニーリングパスを新たなアニーリングパスに更新する古典コンピュータと、
を備える、量子計算システム。
【請求項５】
制約を有する組合せ最適化問題を複数のスピン変数で表されるイジングモデルを用いて解くための量子計算方法を量子デバイスと併用して古典コンピュータに実行させるためのプログラムであって、
前記量子デバイスによる量子アニーリングの実行により、前記複数のスピン変数の量子状態の確率分布が生成されると、前記量子状態を表す解に基づいて、前記制約を満たさない非実行可能解を前記制約を満たす実行可能解に変換する後処理を実行して、前記後処理後の新たな確率分布を計算し、
前記新たな確率分布に基づいて前記イジングモデルのエネルギー期待値を計算し、
前記エネルギー期待値が小さくなるように、前記量子アニーリングのパラメータであるアニーリングパスを新たなアニーリングパスに更新するステップを有するプログラム。

発明の詳細な説明【技術分野】
【０００１】
本発明は、制約のある組合せ最適化問題を解法するための量子計算方法、量子計算システム、及びプログラムに関する。
続きを表示（約 2,900 文字）【背景技術】
【０００２】
組合せ最適化問題とは、多数の組合せの中から最も良い組合せを選ぶために、制約条件のもとで目的関数を最小化又は最大化する変数の組合せを求める問題である。組合せ最適化問題は、一般に、量子アニーラやゲート型量子コンピュータなどの量子デバイス上でのイジングモデルの基底状態探索問題に変換される。近年、制約のある大規模な組合せ最適化問題を解法するための様々な量子アルゴリズムが提案されている（例えば、非特許文献１、非特許文献２、及び非特許文献３参照）。
【先行技術文献】
【非特許文献】
【０００３】
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann, “A Quantum Approximate Optimization Algorithm,” arXiv:1411.4028 (2014).
Shunji Matsuura, Samantha Buck, Valentin Senicourt, and Arman Zaribafiyan, “Variationally scheduled quantum simulation,” Phys. Rev. A vol. 103, 052435 (2021).
Michiya Kuramata, Ryota Katsuki, and Kazuhide Nakata, “Larger sparse quadratic assignment problem optimization using quantum annealing and a bit-flip heuristic algorithm,” in 2021 IEEE 8th International Conference on Industrial Engineering and Applications (ICIEA), 2021, pp. 556-565.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ノイズの影響により、量子デバイスがエラーなく量子アルゴリズムを実行することができる時間（コヒーレンス時間）には上限がある。しかしながら、従来の量子アルゴリズムを用いて大規模な組合せ最適化問題を解くためには非常に長い時間がかかるという課題がある。
【０００５】
本発明は、上記課題に鑑みてなされたものであり、コヒーレンス時間の限られた量子デバイスを用いて効率よく組合せ最適化問題を解く量子計算方法、量子計算システム、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明に係る量子計算方法は、制約を有する組合せ最適化問題を複数のスピン変数で表されるイジングモデルを用いて解くための量子計算方法であって、量子デバイスにより、イジングモデルの量子ゆらぎの強さを表すパラメータであるアニーリングパスにしたがって量子アニーリングを実行することにより、複数のスピン変数の量子状態を生成し、量子デバイスにより、量子状態の確率分布を生成し、古典コンピュータにより、量子状態を表す解に基づいて、制約を満たさない非実行可能解を制約を満たす実行可能解に変換する後処理を実行して、後処理後の新たな確率分布を計算し、古典コンピュータにより、新たな確率分布に基づいてイジングモデルのエネルギー期待値を計算し、古典コンピュータにより、エネルギー期待値が小さくなるようにアニーリングパスを新たなアニーリングパスに更新する。
【０００７】
本発明に係る量子計算システムは、制約を有する組合せ最適化問題を複数のスピン変数で表されるイジングモデルを用いて解くための量子計算システムであって、イジングモデルの量子ゆらぎの強さを表すパラメータであるアニーリングパスにしたがって量子アニーリングを実行することにより、複数のスピン変数の量子状態を生成し、量子状態の確率分布を生成する量子デバイスと、量子状態を表す解に基づいて、制約を満たさない非実行可能解を制約を満たす実行可能解に変換する後処理を実行して、後処理後の新たな確率分布を計算し、新たな確率分布に基づいてイジングモデルのエネルギー期待値を計算し、エネルギー期待値が小さくなるようにアニーリングパスを新たなアニーリングパスに更新する古典コンピュータと、を備える。
【０００８】
本発明に係るプログラムは、制約を有する組合せ最適化問題を複数のスピン変数で表されるイジングモデルを用いて解くための量子計算方法を量子デバイスと併用して古典コンピュータに実行させるためのプログラムであって、量子デバイスによる量子アニーリングの実行により、複数のスピン変数の量子状態の確率分布が生成されると、量子状態を表す解に基づいて、制約を満たさない非実行可能解を制約を満たす実行可能解に変換する後処理を実行して、後処理後の新たな確率分布を計算し、新たな確率分布に基づいてイジングモデルのエネルギー期待値を計算し、エネルギー期待値が小さくなるように、量子アニーリングのパラメータであるアニーリングパスを新たなアニーリングパスに更新するステップを有する。
【発明の効果】
【０００９】
本発明によれば、量子デバイスがアニーリングパスにしたがって量子アニーリングを実行して量子状態の確率分布を生成した後、古典コンピュータが、非実行可能解を実行可能解に変換する後処理を実行し、後処理後の量子状態の新たな確率分布に基づいてエネルギー期待値が小さくなるようにアニーリングパスを更新するようにした。これにより、アニーリングパスが最適化され、コヒーレンス時間の限られた量子デバイスを用いて効率良く組合せ最適化問題を解くことが可能となる。
【図面の簡単な説明】
【００１０】
本実施形態に係る量子計算方法を表すフローチャートである。
２個のスピン変数で表される制約付き組合せ最適化問題において非実行可能解を実行可能解に変換する後処理を説明するための模式図である。
後処理による確率分布の変化を説明するための模式図である。
３種類のアニーリングスケジュール（連続、線形、離散）を表す模式図である。
異なるアニーリング時間に対する連続スケジュールでの最適なアニーリングパスを表すグラフである。
複数の制約が互いに独立である例を説明するための模式図である。
複数の制約が互いに独立ではない例を説明するための模式図である。
複数の制約が互いに独立ではないときの後処理手法の一例を表す模式図である。
本実施形態に係る量子計算システムの構成を示すブロック図である。
図８に示す古典コンピュータのハードウェア構成を示すブロック図である。
グラフ分割問題の一例を表す模式図である。
【発明を実施するための形態】
（【００１１】以降は省略されています）

関連特許