論文の概要: Solving Constrained Combinatorial Optimization Problems with Variational Quantum Imaginary Time Evolution

• arxiv url: http://arxiv.org/abs/2504.12607v1
• Date: Thu, 17 Apr 2025 03:09:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-18 14:36:25.672342
• Title: Solving Constrained Combinatorial Optimization Problems with Variational Quantum Imaginary Time Evolution
• Title（参考訳）: 変分量子イマジナリー時間進化を用いた制約付き組合せ最適化問題の解法
• Authors: Xin Wei Lee, Hoong Chuin Lau,
• Abstract要約: 本稿では,VarQITEが従来の手法に比べて平均最適性ギャップを著しく小さくすることを示す。 ハミルトニアンのスケーリングにより、最適化コストをさらに削減し、収束を加速できることを実証する。
• 参考スコア（独自算出の注目度）: 4.266376725904727
• License:
• Abstract: Solving combinatorial optimization problems using variational quantum algorithms (VQAs) has emerged as a promising research direction. Since the introduction of the Quantum Approximate Optimization Algorithm (QAOA), numerous variants have been proposed to enhance its performance. QAOA was later extended to the Quantum Alternating Operator Ansatz (QAOA+), which generalizes the initial state, phase-separation operator, and mixer to address constrained problems without relying on the standard Quadratic Unconstrained Binary Optimization (QUBO) formulation. However, QAOA+ often requires additional ancilla qubits and a large number of multi-controlled Toffoli gates to prepare the superposition of feasible states, resulting in deep circuits that are challenging for near-term quantum devices. Furthermore, VQAs are generally hindered by issues such as barren plateaus and suboptimal local minima. Recently, Quantum Imaginary Time Evolution (QITE), a ground-state preparation algorithm, has been explored as an alternative to QAOA and its variants. QITE has demonstrated improved performance in quantum chemistry problems and has been applied to unconstrained combinatorial problems such as Max-Cut. In this work, we apply the variational form of QITE (VarQITE) to solve the Multiple Knapsack Problem (MKP), a constrained problem, using a Max-Cut-tailored ansatz. To the best of our knowledge, this is the first attempt to address constrained optimization using VarQITE. We show that VarQITE achieves significantly lower mean optimality gaps compared to QAOA and other conventional methods. Moreover, we demonstrate that scaling the Hamiltonian coefficients can further reduce optimization costs and accelerate convergence.
• Abstract（参考訳）: 変分量子アルゴリズム(VQA)を用いた組合せ最適化問題の解法が有望な研究方向として浮上している。 量子近似最適化アルゴリズム (QAOA) を導入して以来、その性能を高めるために多くの変種が提案されている。 QAOAは後に量子交互演算子 Ansatz (QAOA+) に拡張され、これは初期状態、位相分離演算子、ミキサーを一般化し、標準の準非制約二元最適化(QUBO)の定式化に頼ることなく制限された問題に対処した。 しかしQAOA+は、実現可能な状態の重ね合わせを準備するために、しばしば追加のアンシラ量子ビットと多数の多制御トフォリゲートを必要とする。 さらに、VQAは一般に不毛の高原や極小の局所性ミニマのような問題によって妨げられている。 近年,QAOAとその変種に代わる基底状態準備アルゴリズムであるQuantum Imaginary Time Evolution (QITE)が検討されている。 QITEは量子化学問題において改善された性能を示しており、Max-Cutのような制約のない組合せ問題にも適用されている。 そこで本研究では,QITE (VarQITE) の変分形式を用いて,制約付き問題であるMKP(Multiple Knapsack Problem)をMax-Cut-tailored ansatzを用いて解く。 我々の知る限りでは、これはVarQITEを使って制約付き最適化に対処する最初の試みである。 本稿では,VarQITEがQAOAや他の手法と比較して平均最適性ギャップを著しく低くすることを示す。 さらに、ハミルトン係数のスケーリングにより、最適化コストをさらに削減し、収束を加速できることを示す。

関連論文リスト

• Non-Variational Quantum Random Access Optimization with Alternating Operator Ansatz [3.5773675235837974]
  量子ランダムアクセス最適化(QRAO)は、量子最適化の空間要求を減らすために提案されている。 インスタンスに依存しない'固定'パラメータは優れた性能を示し、変分パラメータ最適化の必要性を排除した。 本研究は,早期のフォールトトレラント量子コンピュータ上でのQRAOの実践的実行の道を開くものである。
  論文  参考訳（メタデータ） (2025-02-06T18:25:31Z)
• Quantum Relaxation for Solving Multiple Knapsack Problems [7.003282322403712]
  組合せ問題はビジネスにおいて共通の課題であり、特定の制約の下で最適なソリューションを見つける必要がある。 本研究では,制約付き最適化問題に対するハイブリッド量子古典法について検討する。 提案手法は、可換写像によって定義される局所量子ハミルトニアンの緩和に依存する。
  論文  参考訳（メタデータ） (2024-04-30T11:40:07Z)
• Solving Combinatorial Optimization Problems with a Block Encoding Quantum Optimizer [0.0]
  Block ENcoding Quantum (BEQO) は、ブロック符号化を用いてコスト関数を表現するハイブリッド量子ソルバである。 以上の結果から,BENQOはQAOAよりも有意に優れた性能を示し,VQEと各種のパフォーマンス指標を比較検討した。
  論文  参考訳（メタデータ） (2024-04-22T10:10:29Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• How Much Entanglement Do Quantum Optimization Algorithms Require? [0.0]
  ADAPT-QAOA施行時に発生する絡みについて検討した。 この柔軟性を漸進的に制限することにより、初期におけるより多くの絡み合いエントロピーが、後段におけるより速い収束と一致していることが分かる。
  論文  参考訳（メタデータ） (2022-05-24T18:00:02Z)
• 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)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。 これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。 本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
  論文  参考訳（メタデータ） (2022-02-17T18:59:20Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。 本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。 Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
  論文  参考訳（メタデータ） (2021-05-06T17:59:38Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。 また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
  論文  参考訳（メタデータ） (2020-09-15T18:17:27Z)
• 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)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  QAOA(Quantum Approximate Optimization Algorithm)のようなハイブリッド量子古典アルゴリズムは、短期量子コンピュータを実用的に活用するための最も奨励的なアプローチの1つである。 このようなアルゴリズムは通常変分形式で実装され、古典的な最適化法と量子機械を組み合わせて最適化問題の優れた解を求める。 本研究では,クロスエントロピー法を用いてランドスケープを形作り,古典的パラメータがより容易により良いパラメータを発見でき,その結果,性能が向上することを示す。
  論文  参考訳（メタデータ） (2020-03-11T13:52:41Z)

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

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