論文の概要: 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倍以上速くなった。
関連論文リスト
- Feedback-Based Quantum Strategies for Constrained Combinatorial Optimization Problems [0.6554326244334868]
我々は、フィードバックベースの量子アルゴリズムフレームワークを拡張し、無効な設定(IC)制約と呼ばれるより広範な制約のクラスに対処する。
本稿では、スラック変数を必要とせずに直接IC制約に対処する、フィードバックベースの量子アルゴリズムに適した代替手法を提案する。
これらの方法はスラック変数の必要性を排除し、量子回路の深さと必要な量子ビットの数を大幅に削減する。
論文 参考訳（メタデータ） (2025-02-20T08:57:28Z) - Solving QUBOs with a quantum-amenable branch and bound method [0.3749861135832072]
本研究では,2次非制約二項最適化問題に対して,古典分枝および有界解法について記述し,実験的に検証する。
本稿では,Isingモデルに対して提案した文献から,低コストで実装可能なバウンダリを利用する。
本稿では,ソルバ性能向上に使用される高性能コンピューティングとオペレーション研究の様々な技術について詳述する。
論文 参考訳（メタデータ） (2024-07-29T17:13:01Z) - Qubit-efficient quantum combinatorial optimization solver [0.0]
そこで我々は,候補ビット解をより少ない量子ビットの絡み合った波動関数にマッピングすることで,制限を克服する量子ビット効率のアルゴリズムを開発した。
このアプローチは、短期的な中間スケールと将来のフォールトトレラントな小規模量子デバイスに有効である。
論文 参考訳（メタデータ） (2024-07-22T11:02:13Z) - 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 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) - A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
本稿では,ロバストフィッティングのためのハイブリッド量子古典アルゴリズムを提案する。
私たちのコアコントリビューションは、整数プログラムの列を解く、新しい堅牢な適合式である。
実際の量子コンピュータを用いて得られた結果について述べる。
論文 参考訳（メタデータ） (2022-01-25T05:59:24Z) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。
3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
論文 参考訳（メタデータ） (2021-08-03T17:49:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。