論文の概要: 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倍以上速くなった。

関連論文リスト

• Branch-and-bound digitized counterdiabatic quantum optimization [39.58317527488534]
  分岐とバウンドのアルゴリズムは、厳密な下界を得るために目的関数の緩和に依存する凸最適化問題を効果的に解く。 本稿では,緩和困難に対処する分枝・分枝・分枝・分枝・分枝対応量子最適化法 (BB-DCQO) を提案する。
  論文  参考訳（メタデータ） (2025-04-21T18:19:19Z)
• Solving Constrained Combinatorial Optimization Problems with Variational Quantum Imaginary Time Evolution [4.266376725904727]
  本稿では,VarQITEが従来の手法に比べて平均最適性ギャップを著しく小さくすることを示す。 ハミルトニアンのスケーリングにより、最適化コストをさらに削減し、収束を加速できることを実証する。
  論文  参考訳（メタデータ） (2025-04-17T03:09:37Z)
• A Quantum Constraint Generation Framework for Binary Linear Programs [0.0]
  量子コンピュータを用いたバイナリ線形プログラミング(BLP)のための新しい手法を提案する。 量子最適化アルゴリズム(ハイブリッドまたは量子専用)は現在、ICPのためのスタンドアロンの解法である。 本研究では,任意の量子最適化アルゴリズムを量子情報古典制約生成フレームワークにラップする。
  論文  参考訳（メタデータ） (2025-03-27T07:24:33Z)
• A Comparative Study of Quantum Optimization Techniques for Solving Combinatorial Optimization Benchmark Problems [4.266376725904727]
  本稿では,NP-hard問題に対する量子最適化手法の評価を目的とした,包括的なベンチマークフレームワークを提案する。 本フレームワークは,多次元クナップサック問題(MDKP),最大独立集合(MIS),二次割当問題(QAP),市場シェア問題(MSP)など,主要な課題に重点を置いている。
  論文  参考訳（メタデータ） (2025-03-15T13:02:22Z)
• Bayesian Quantum Amplitude Estimation [49.1574468325115]
  本稿では,量子振幅推定のための雑音対応ベイズアルゴリズムであるBAEを紹介する。 我々は,BAEがハイゼンベルク限界推定を達成し,他の手法と比較した。
  論文  参考訳（メタデータ） (2024-12-05T18:09:41Z)
• 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)
• 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 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)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。 その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
  論文  参考訳（メタデータ） (2021-06-24T20:16:02Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。