論文の概要: Towards Exponential Quantum Improvements in Solving Cardinality-Constrained Binary Optimization
- arxiv url: http://arxiv.org/abs/2603.14744v1
- Date: Mon, 16 Mar 2026 02:30:52 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-17 16:19:36.003585
- Title: Towards Exponential Quantum Improvements in Solving Cardinality-Constrained Binary Optimization
- Title（参考訳）: 双対最適化の解法における指数量子的改善に向けて
- Authors: Haomu Yuan, Hanqing Wu, Kuan-Cheng Chen, Bin Cheng, Crispin H. W. Barnes,
- Abstract要約: 本稿では,Grover をベースとした量子アルゴリズムを提案する。
二次目的のために、我々の手法は、$Oleft(sqrtbinomnkfracn6k3/2 sqrtM2 right)$2次オラクルへのクエリと$Oleft(fracn6k3/22right)$古典的オーバーヘッドを達成する。
- 参考スコア（独自算出の注目度）: 6.264051440120738
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Cardinality-constrained binary optimization is a fundamental computational primitive with broad applications in machine learning, finance, and scientific computing. In this work, we introduce a Grover-based quantum algorithm that exploits the structure of the fixed-cardinality feasible subspace under a natural promise on solution existence. For quadratic objectives, our approach achieves ${O}\left(\sqrt{\frac{\binom{n}{k}}{M}}\right)$ Grover rotations for any fixed cardinality $k$ and degeneracy of the optima $M$, yielding an exponential reduction in the number of Grover iterations compared with unstructured search over $\{0,1\}^n$. Building on this result, we develop a hybrid classical--quantum framework based on the alternating direction method of multipliers (ADMM) algorithm. The proposed framework is guaranteed to output an $ε$-approximate solution with a consistency tolerance $ε+ δ$ using at most $ {O}\left(\sqrt{\binom{n}{k}}\frac{n^{6}k^{3/2} }{ \sqrt{M}ε^2 δ}\right)$ queries to a quadratic oracle, together with ${O}\left(\frac{n^{6}k^{3/2}}{ε^2δ}\right)$ classical overhead. Overall, our method suggests a practical use of quantum resources and demonstrates an exponential improvements over existing Grover-based approaches in certain parameter regimes, thereby paving the way toward quantum advantage in constrained binary optimization.
- Abstract（参考訳）: カーディナリティ制約付きバイナリ最適化は、機械学習、ファイナンス、科学計算に広く応用された基本的な計算プリミティブである。
本研究では,Groverをベースとした量子アルゴリズムを提案する。
二次目的に対して、我々の手法は、任意の固定濃度$k$に対して${O}\left(\sqrt {\frac {\binom{n}{k}}{M}}\right)$ Grover回転を達成し、最適値$M$の退化により、${0,1\}^n$の非構造探索と比較してグロバー反復の数が指数関数的に減少する。
この結果に基づいて,乗算器の交互方向法(ADMM)に基づく古典量子ハイブリッドフレームワークを開発した。
提案したフレームワークは、最大で${O}\left(\sqrt{\binom{n}{k}}\frac{n^{6}k^{3/2} }{ \sqrt{M}ε^2 δ}\right)$クエリを二次オラクルに出力し、${O}\left(\frac{n^{6}k^{3/2}}{ε^2δ}\right)$古典的オーバーヘッドを使って、一貫性のある$ε+δ$を出力することを保証している。
提案手法は, 量子資源の実用的利用を示唆し, 既存のGroverベースの手法よりも指数関数的に改善し, 制約付き二元最適化における量子優位性への道を開いた。
関連論文リスト
- A Grover-compatible manifold optimization algorithm for quantum search [17.013842168748127]
グロバーのアルゴリズムは、非構造化探索問題に対して2次高速化を提供する基本量子アルゴリズムである。
我々はGroverのアルゴリズムがGroverのアルゴリズムによって達成された$O(qrstN)$のスピードアップと一致することを示す。
論文 参考訳（メタデータ） (2025-12-09T10:01:55Z) - Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
本稿では、量子感応サンプリングのための統一的なフレームワークを提案し、量子コンピューティングの利点を古典近似問題の幅広いクラスに拡張する。
我々のフレームワークは、コアセットを構築するための合理化されたアプローチを提供し、クラスタリング、回帰、低ランク近似などのアプリケーションにおいて、大幅なランタイム改善を提供します。
論文 参考訳（メタデータ） (2025-09-20T20:18:49Z) - Quantum Algorithms for Non-smooth Non-convex Optimization [30.576546266390714]
本稿では、リプシッツ連続目的の$(,epsilon)$-Goldstein定常点を求める問題を考える。
代理オラクル関数に対するゼロ階量子推定器を構築する。
論文 参考訳（メタデータ） (2024-10-21T16:52:26Z) - Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problems [8.0153031008486]
有限和共役方程式 $Gx = 0$ を解くために, 分散還元を伴う高速クラスクラスKrasnoselkii-Mann 法を提案する。
我々のアルゴリズムは単一ループであり、より広範なルートフィンディングアルゴリズムのために特別に設計された、偏りのない分散還元推定器の新たなファミリーを利用する。
数値実験は我々のアルゴリズムを検証し、最先端の手法と比較して有望な性能を示す。
論文 参考訳（メタデータ） (2024-06-04T15:23:29Z) - Oblivious Stochastic Composite Optimization [47.48197617884748]
我々のアルゴリズムは問題のパラメータに関する事前の知識なしで収束することを示す。
3つのアルゴリズムは全て、実現可能な集合の直径、リプシッツ定数、あるいは目的関数の滑らかさについて事前の知識なしに機能する。
我々は,フレームワークを比較的大規模に拡張し,大規模半確定プログラム上での手法の効率性と堅牢性を実証する。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。
本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。
次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-10T13:07:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。