論文の概要: Choco-Q: Commute Hamiltonian-based QAOA for Constrained Binary Optimization
- arxiv url: http://arxiv.org/abs/2503.23941v1
- Date: Mon, 31 Mar 2025 10:47:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-01 14:34:38.866913
- Title: Choco-Q: Commute Hamiltonian-based QAOA for Constrained Binary Optimization
- Title（参考訳）: Choco-Q: 制約付きバイナリ最適化のためのハミルトンベースの通勤QAOA
- Authors: Debin Xiang, Qifan Jiang, Liqiang Lu, Siwei Tan, Jianwei Yin,
- Abstract要約: 本稿では,制約付きバイナリ最適化問題に対する形式的で普遍的なフレームワークであるChoco-Qを提案する。
Choco-Qの主な革新は、通勤ハミルトニアンをドライバーハミルトニアンとして埋め込むことであり、その結果より一般的な符号化形式が作られる。
我々の分解法は線形時間だけを要し、エンドツーエンドの加速を実現している。
- 参考スコア（独自算出の注目度）: 13.521769871808537
- License:
- Abstract: Constrained binary optimization aims to find an optimal assignment to minimize or maximize the objective meanwhile satisfying the constraints, which is a representative NP problem in various domains, including transportation, scheduling, and economy. Quantum approximate optimization algorithms (QAOA) provide a promising methodology for solving this problem by exploiting the parallelism of quantum entanglement. However, existing QAOA approaches based on penalty-term or Hamiltonian simulation fail to thoroughly encode the constraints, leading to extremely low success rate and long searching latency. This paper proposes Choco-Q, a formal and universal framework for constrained binary optimization problems, which comprehensively covers all constraints and exhibits high deployability for current quantum devices. The main innovation of Choco-Q is to embed the commute Hamiltonian as the driver Hamiltonian, resulting in a much more general encoding formulation that can deal with arbitrary linear constraints. Leveraging the arithmetic features of commute Hamiltonian, we propose three optimization techniques to squeeze the overall circuit complexity, including Hamiltonian serialization, equivalent decomposition, and variable elimination. The serialization mechanism transforms the original Hamiltonian into smaller ones. Our decomposition methods only take linear time complexity, achieving end-to-end acceleration. Experiments demonstrate that Choco-Q shows more than 235$\times$ algorithmic improvement in successfully finding the optimal solution, and achieves 4.69$\times$ end-to-end acceleration, compared to prior QAOA designs.
- Abstract（参考訳）: 制約付き二元最適化は,交通,スケジューリング,経済など,各分野における代表的NP問題である制約を満たす目的を最小化あるいは最大化するための最適課題を見つけることを目的としている。
量子近似最適化アルゴリズム(QAOA)は、量子絡み合いの並列性を利用してこの問題を解決するための有望な方法論を提供する。
しかし、刑期やハミルトンのシミュレーションに基づく既存のQAOAアプローチでは、制約を完全にエンコードすることができないため、成功率が極めて低く、長い検索遅延が発生する。
本稿では、制約付きバイナリ最適化問題の形式的および普遍的なフレームワークであるChoco-Qを提案し、全ての制約を包括的にカバーし、現在の量子デバイスに高いデプロイ性を示す。
Choco-Q の主な革新は、可換ハミルトニアンをドライバーハミルトニアンとして埋め込むことであり、従って任意の線形制約に対処できるより一般的なエンコーディングの定式化をもたらす。
可換ハミルトニアンの算術的特徴を生かして、ハミルトニアン直列化、等価分解、変数除去を含む回路全体の複雑さを緩和する3つの最適化手法を提案する。
直列化機構は、元のハミルトニアンをより小さなハミルトニアンに変換する。
我々の分解法は線形時間だけを要し、エンドツーエンドの加速を実現している。
実験により、Choco-Q は最適解の発見に成功して 235$\times$ アルゴリズムの改善を示し、従来の QAOA 設計と比較して 4.69$\times$ エンド・ツー・エンド・アクセラレーションを達成した。
関連論文リスト
- Q-CHOP: Quantum constrained Hamiltonian optimization [2.7022651232296946]
量子制約ハミルトン最適化(Q-CHOP)と呼ばれる制約付き最適化のための新しい量子アルゴリズムを提案する。
基本的な考え方は、常にハミルトンの制約を強制し、実現可能な状態の部分空間への進化を制限することである。
ペナルティ項を用いた制約付き一般用アダバティックアルゴリズムに対して,Q-CHOPをベンチマークした。
論文 参考訳（メタデータ） (2024-03-08T20:03:59Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Fermionic Quantum Approximate Optimization Algorithm [11.00442581946026]
制約付き最適化問題を解くためのフェルミオン量子近似最適化アルゴリズム(FQAOA)を提案する。
FQAOAは、フェルミオン粒子数保存を用いて、QAOAを通して本質的にそれらを強制する制約問題に対処する。
制約付きハミルトニアン問題に対して、運転者ハミルトニアンを設計するための体系的なガイドラインを提供する。
論文 参考訳（メタデータ） (2023-01-25T18:36:58Z) - Symmetric Tensor Networks for Generative Modeling and Constrained
Combinatorial Optimization [72.41480594026815]
ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。
これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。
本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
論文 参考訳（メタデータ） (2022-11-16T18:59:54Z) - Algorithm for Constrained Markov Decision Process with Linear
Convergence [55.41644538483948]
エージェントは、そのコストに対する複数の制約により、期待される累積割引報酬を最大化することを目的としている。
エントロピー正規化ポリシーとベイダの二重化という2つの要素を統合した新しい双対アプローチが提案されている。
提案手法は(線形速度で)大域的最適値に収束することが示されている。
論文 参考訳（メタデータ） (2022-06-03T16:26:38Z) - 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) - FastHare: Fast Hamiltonian Reduction for Large-scale Quantum Annealing [17.830687420962512]
非分離群の概念を導入し、最適解において同じ値を得るハミルトニアンにおいて、量子ビットの部分集合として定義される。
FastHareは、反復的に、非分離群を単一のキュービットに検出し、マージする。
これは、ユーザ定義パラメータの$alpha$に対して$O(alpha n2)$のみの証明可能な最悪のケースタイムの複雑さ内で行われる。
論文 参考訳（メタデータ） (2022-05-10T16:20:21Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳（メタデータ） (2021-10-20T02:57:21Z) - Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
時間に依存しない深さの量子回路を生成するための構成的アルゴリズムを提案する。
一次元横フィールドXYモデルにおけるアンダーソン局在化を含む、モデルの特殊クラスに対するアルゴリズムを強調する。
幅広いスピンモデルとフェルミオンモデルに対して正確な回路を提供するのに加えて、我々のアルゴリズムは最適なハミルトニアンシミュレーションに関する幅広い解析的および数値的な洞察を提供する。
論文 参考訳（メタデータ） (2021-04-01T19:06:00Z) - Constructing Driver Hamiltonians for Optimization Problems with Linear
Constraints [0.0]
我々は、線形制約を持つハミルトニアンの可換性について推論するための単純で直感的なフレームワークを開発する。
ユニタリ作用素はエルミート作用素の指数関数であるため、これらの結果は量子交互作用素アンザッツフレームワークにおけるミキサーの構成にも適用できる。
論文 参考訳（メタデータ） (2020-06-22T06:47:50Z) - An adaptive quantum approximate optimization algorithm for solving
combinatorial problems on a quantum computer [0.0]
量子近似最適化アルゴリズム(QAOA)は、最適化問題を解くハイブリッド変分量子古典アルゴリズムである。
我々は,QAOAの反復バージョンを開発し,特定のハードウェア制約に適応することができる。
アルゴリズムをMax-Cutグラフのクラス上でシミュレートし、標準QAOAよりもはるかに高速に収束することを示す。
論文 参考訳（メタデータ） (2020-05-20T18:00:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。