論文の概要: Geometry-Informed Polynomial Time Quantum Approximation Schemes for Constrained Optimisation
- arxiv url: http://arxiv.org/abs/2608.01121v2
- Date: Wed, 05 Aug 2026 14:00:56 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-06 14:48:43.060297
- Title: Geometry-Informed Polynomial Time Quantum Approximation Schemes for Constrained Optimisation
- Title（参考訳）: 幾何インフォーマルな多項式時間量子近似スキームによる制約付き最適化
- Authors: Chinonso Onah, Kristel Michielsen,
- Abstract要約: 制約強化QAOAに対する有限深度および有限ショット保証を構築した。
本稿では,これらの条件付き保証を保ちつつ,保持された候補セットと古典処理コストを問題サイズの1つのパワーで削減するヘビーヒッターQAOAを紹介する。
IBM Eagle r3プロセッサのハードウェア実験は、100以上の論理変数を持つインスタンスをカバーするか、テストされたQOptlib参照ツアーを全て改善する。
- 参考スコア（独自算出の注目度）: 0.2578242050187029
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: When does a noisy quantum sampler yield an end-to-end polynomial-time optimization algorithm with performance guarantees? Building on finite-depth and finite-shot guarantees for Constraint-Enhanced QAOA, we show that inverse-polynomial ideal probability on the optimal set, together with independent sampling, polynomial-time feasibility repair, and scoring, produces an exact-hit fully polynomial randomized approximation scheme, which we call an FPRASq. This guarantee survives device noise within an instance-dependent window. For effective circuit depth linear in the product of layer count and problem size, preserving an inverse-depth fraction of the ideal optimal mass increases the required shot complexity by one power of the problem size. Beyond this window, deterministic repair guarantees feasibility and provides an instance-dependent approximation guarantee whenever the induced objective inflation is controlled. The resulting NP-HQ algorithm fits the Chen-Cotler-Huang-Li oracle model. On any NP-hard kernel-admissible promise family, reproducing its inverse-polynomial optimal overlap with a polynomial-time classical sampler would imply that NP is contained in BPP, even with identical repair and perfect access to the constraint structure. Thus, the separation lies in generating the sampling distribution. We further introduce Heavy-Hitter QAOA, which preserves these conditional guarantees while reducing the retained candidate set and classical post-processing cost by one power of the problem size. Hardware experiments on IBM Eagle r3 processors cover instances with up to one hundred logical variables and match or improve every tested QOptlib reference tour.
- Abstract（参考訳）: 雑音のある量子サンプリング器は、性能保証付きエンドツーエンド多項式時間最適化アルゴリズムをいつ得られるか?
制約強化QAOAの有限深さおよび有限ショット保証に基づいて、最適集合上の逆多項式的理想確率と独立サンプリング、多項式時間実現可能性修復およびスコアリングが、FPRASqと呼ばれる完全多項式ランダム化近似スキームを生成することを示す。
この保証は、インスタンス依存ウィンドウ内でデバイスノイズを継続する。
層数と問題サイズの積における有効回路深さの線形化のために、理想的な最適質量の逆深さの分数を保存することは、問題サイズの1つのパワーによって要求されるショットの複雑さを増大させる。
この窓の向こうでは、決定論的修復が実現可能性を保証するとともに、誘導された客観的インフレーションが制御されるたびに、インスタンス依存の近似を保証する。
NP-HQアルゴリズムはChen-Cotler-Huang-Li Oracleモデルに適合する。
NP-ハードなカーネル許容公約族では、逆多項式の最適重なりを多項式時間古典的なサンプリング器で再現すると、NPがBPPに含まれており、同じ修復と制約構造への完全なアクセスがあることを意味する。
したがって、分離はサンプリング分布の生成に関係している。
さらに、これらの条件付き保証を保ちつつ、保持された候補セットと古典的な後処理コストを問題サイズの1つのパワーで削減するヘビーヒッターQAOAを導入する。
IBM Eagle r3プロセッサのハードウェア実験は、100以上の論理変数を持つインスタンスをカバーし、テスト済みのQOptlib参照ツアーにマッチまたは改善する。
関連論文リスト
- Efficient Fourier-Based Linear Combination of Unitaries and Applications in Quantum Optimization [0.7009487789080343]
複雑な量子回路を近似する枠組みとして, アンシラフリーなユニタリ結合(LCU)について検討する。
フーリエに基づくLCU構造は, 対角および非対角ユニタリの広いクラスを効率的に分解することを示した。
論文 参考訳（メタデータ） (2026-05-18T18:05:08Z) - Iterative Optimization with Partial Convergence Guarantees on Neutral Atom Quantum Computers [0.0]
Lp-Qutsは、NAQCサンプルラーを古典的な切断平面アルゴリズムに統合するハイブリッド量子古典的フレームワークである。
我々は、Lp-Qutsを古典最適化フレームワークに効果的に組み込んで、量子資源を減らした準最適解を提供する方法を示す。
論文 参考訳（メタデータ） (2026-03-30T19:12:21Z) - Global Optimization for Parametrized Quantum Circuits [3.558201566667322]
トレーニング可能なパラメータを一定数有する量子回路の実践的なクラスのトレーニングについて検討する。
我々の主な成果は、完全にランダム化された近似スキーム (FPRAS) である。
変分アルゴリズムにおける標準的なハイブリッド量子古典的トレーニングとは異なり、我々の手法は計算を2つの異なる段階に分けている。
論文 参考訳（メタデータ） (2026-03-23T09:49:40Z) - BandPO: Bridging Trust Regions and Ratio Clipping via Probability-Aware Bounds for LLM Reinforcement Learning [49.25750348525603]
BandPOは、信頼領域を動的で確率対応のクリッピング間隔に投影する統一理論演算子であるBandに取って代わる。
BandPOはカノニカルクリッピングやClip-Higherより一貫して優れ,エントロピー崩壊の軽減が図られている。
論文 参考訳（メタデータ） (2026-03-05T08:03:05Z) - Tensor Network Assisted Distributed Variational Quantum Algorithm for Large Scale Combinatorial Optimization Problem [19.046113542182436]
組合せ最適化問題の解法として分散変分量子アルゴリズム(DVQA)を提案する。
DVQAの重要な革新は、複雑な長距離の絡み合いに頼ることなく、変数間の依存関係を保存するために、切り詰められた高階特異値分解を使用することである。
実験的に、DVQAはシミュレーションの最先端性能を達成し、ポートフォリオ最適化のためにWu Kong量子コンピュータで実験的に検証されている。
論文 参考訳（メタデータ） (2026-01-20T13:31:02Z) - Harmonic Path Integral Diffusion [0.4527270266697462]
本稿では,連続多変量確率分布から抽出する新しい手法を提案する。
本手法では,状態空間の起点を中心とするデルタ関数を$t=0$とし,ターゲット分布に$t=1$で変換する。
これらのアルゴリズムは他のサンプリング手法、特にシミュレートおよびパス積分サンプリングと対比し、解析制御、精度、計算効率の点でそれらの利点を強調した。
論文 参考訳（メタデータ） (2024-09-23T16:20:21Z) - Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time
Guarantees [56.848265937921354]
逆強化学習(IRL)は報酬関数と関連する最適ポリシーを回復することを目的としている。
IRLの多くのアルゴリズムは本質的にネスト構造を持つ。
我々は、報酬推定精度を損なわないIRLのための新しいシングルループアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-10-04T17:13:45Z) - Structural Estimation of Markov Decision Processes in High-Dimensional
State Space with Finite-Time Guarantees [39.287388288477096]
本研究では,実施行動と訪問状態の観測可能な履歴に基づいて,人間エージェントによる動的決定の構造モデルの推定作業を検討する。
この問題には固有のネスト構造があり、内部問題では与えられた報酬関数に対する最適ポリシーが特定され、外部問題では適合度の測定が最大化される。
本研究では,高次元状態空間を扱うための有限時間保証付き単一ループ推定アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-10-04T00:11:38Z) - A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
本稿では,ロバストフィッティングのためのハイブリッド量子古典アルゴリズムを提案する。
私たちのコアコントリビューションは、整数プログラムの列を解く、新しい堅牢な適合式である。
実際の量子コンピュータを用いて得られた結果について述べる。
論文 参考訳（メタデータ） (2022-01-25T05:59:24Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。