論文の概要: Efficient Internal Strategies in Quantum Relaxation based Branch-and-Bound
- arxiv url: http://arxiv.org/abs/2405.00935v1
- Date: Thu, 2 May 2024 01:28:52 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-03 18:14:01.360741
- Title: Efficient Internal Strategies in Quantum Relaxation based Branch-and-Bound
- Title(参考訳): 量子緩和に基づくブランチ・アンド・バウンドにおける効率的な内部戦略
- Authors: Hiromichi Matsuyama, Wei-hao Huang, Kohji Nishimura, Yu Yamashiro,
- Abstract要約: 我々は、量子緩和に基づくブランチ・アンド・バウンド(QR-BnB)を開発する。
QR-BnBは、量子緩和をブランチ・アンド・バウンドフレームワークに組み込む方法である。
パウリ作用素の期待値による変数選択戦略は、素数選択よりも収束性が高いことを示す。
- 参考スコア(独自算出の注目度): 1.3499500088995464
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A combinatorial optimization problem is to find an optimal solution under the constraints. This is one of the potential applications for quantum computers. Quantum Random Access Optimization (QRAO) is the quantum optimization algorithm that encodes multiple classical variables into a single qubit to construct a quantum Hamiltonian, thereby reducing the number of qubits required. The ground energy of the QRAO Hamiltonian provides a lower bound on the original problem's optimal value before encoding. This property allows the QRAO Hamiltonian to be used as a relaxation of the original problem, and it is thus referred to as a quantum relaxed Hamiltonian. In the Branch-and-Bound method, solving the relaxation problem plays a significant role. In this study, we developed Quantum Relaxation based Branch-and-Bound (QR-BnB), a method incorporating quantum relaxation into the Branch-and-Bound framework. We solved the MaxCut Problem and the Travelling Salesman Problem in our experiments. In all instances in this study, we obtained the optimal solution whenever we successfully computed the exact lower bound through quantum relaxation. Internal strategies, such as relaxation methods and variable selection, influence the convergence of the Branch-and-Bound. Thus, we have further developed the internal strategies for QR-BnB and examined how these strategies influence its convergence. We show that our variable selection strategy via the expectation value of the Pauli operators gives better convergence than the naive random choice. QRAO deals with only unconstrained optimization problems, but QR-BnB can handle constraints more flexibly because of the Branch-and-Bound processes on the classical computing part. We demonstrate that in our experiments with the Travelling Salesman Problem, the convergence of QR-BnB became more than three times faster by using the information in the constraints.
- Abstract(参考訳): 組合せ最適化問題は制約の下で最適解を見つけることである。
これは量子コンピュータの潜在的な応用の1つである。
量子ランダムアクセス最適化(英: Quantum Random Access Optimization、QRAO)は、量子ハミルトニアンを構成するために複数の古典変数を1つの量子ビットにエンコードする量子最適化アルゴリズムである。
QRAOハミルトニアンの基底エネルギーは、符号化する前に元の問題の最適値に低い境界を与える。
この性質により、QRAOハミルトニアンは元の問題の緩和として用いることができ、したがって量子緩和ハミルトニアンと呼ばれる。
ブランチ・アンド・バウンド法では、緩和問題を解くことが重要な役割を果たす。
本研究では,分枝結合フレームワークに量子緩和を組み込む手法である分枝結合法(QR-BnB)を開発した。
我々は,MaxCut問題とトラベリングセールスマン問題を実験で解決した。
この研究のすべての事例において、量子緩和による正確な下界の計算に成功するたびに最適な解を得た。
緩和法や変数選択のような内部戦略は分岐境界の収束に影響を与える。
そこで我々はQR-BnBの内部戦略をさらに発展させ,これらの戦略が収束にどのように影響するかを検討した。
パウリ作用素の期待値による変数選択戦略は、素数選択よりも収束性が高いことを示す。
QRAOは制約のない最適化問題にのみ対処するが、QR-BnBは古典的な計算部分のブランチ・アンド・バウンド処理のためにより柔軟に制約を処理できる。
トラベリングセールスマン問題を用いた実験では,制約情報を用いてQR-BnBの収束が3倍以上速くなった。
関連論文リスト
- Qubit-efficient quantum combinatorial optimization solver [0.0]
そこで我々は,候補ビット解をより少ない量子ビットの絡み合った波動関数にマッピングすることで,制限を克服する量子ビット効率のアルゴリズムを開発した。
このアプローチは、短期的な中間スケールと将来のフォールトトレラントな小規模量子デバイスに有効である。
論文 参考訳(メタデータ) (2024-07-22T11:02:13Z) - Bayesian Optimization Priors for Efficient Variational Quantum Algorithms [0.0]
量子コンピュータは現在、量子量子アルゴリズム(VQA)と呼ばれる量子古典的なアプローチで問題を解決している。
本稿では,時間当たりのショット数を削減できる基本計算最適化のためのハイブリッドフレームワークを提案する。
この2つの特徴を用いて,提案手法がVQA内でのシミュレーション実装を統計的に上回っていることを示す。
論文 参考訳(メタデータ) (2024-06-20T18:00:12Z) - Quantum Relaxation for Solving Multiple Knapsack Problems [7.003282322403712]
組合せ問題はビジネスにおいて共通の課題であり、特定の制約の下で最適なソリューションを見つける必要がある。
本研究では,制約付き最適化問題に対するハイブリッド量子古典法について検討する。
提案手法は、可換写像によって定義される局所量子ハミルトニアンの緩和に依存する。
論文 参考訳(メタデータ) (2024-04-30T11:40:07Z) - Quantum Bayesian Optimization [64.58749619145908]
本稿では,量子ガウスプロセスアップパー信頼度境界(Q-GP-UCB)アルゴリズムを提案する。
O(polylog T) は古典的設定における Omega(sqrt(T)) の左下限よりもかなり小さい。
線形核を持つQ-GP-UCBは、新しい信頼楕円体解析により、量子線形 UCB アルゴリズムよりも小さな後悔を実現する。
論文 参考訳(メタデータ) (2023-10-09T03:10:42Z) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。
提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
論文 参考訳(メタデータ) (2023-04-18T11:57:15Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳(メタデータ) (2022-12-06T22:01:49Z) - Constrained Optimization via Quantum Zeno Dynamics [23.391640416533455]
量子ゼノダイナミクスを用いて、不等式を含む複数の任意の制約で最適化問題を解く手法を提案する。
量子最適化のダイナミクスは、フォールトトレラントな量子コンピュータ上の制約内部分空間に効率的に制限できることを示す。
論文 参考訳(メタデータ) (2022-09-29T18:00:40Z) - Constrained Quantum Optimization for Extractive Summarization on a
Trapped-ion Quantum Computer [13.528362112761805]
本稿では,量子ハードウェアの制約を保存する量子最適化アルゴリズムの,これまでで最大の実行方法を示す。
我々は、最大20キュービットと2キュービットゲート深さ最大159の量子進化を制限するXY-QAOA回路を実行する。
本稿では,アルゴリズムのトレードオフと,短期量子ハードウェア上での実行に対する影響について論じる。
論文 参考訳(メタデータ) (2022-06-13T16:21:04Z) - QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines [81.4597482536073]
量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。
量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。
提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
論文 参考訳(メタデータ) (2022-05-24T03:49:10Z) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。
3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
論文 参考訳(メタデータ) (2021-08-03T17:49:09Z) - Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。
その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
論文 参考訳(メタデータ) (2021-06-24T20:16:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。