論文の概要: Quantum and classical algorithms for SOCP based on the multiplicative weights update method
- arxiv url: http://arxiv.org/abs/2507.14127v1
- Date: Fri, 18 Jul 2025 17:55:58 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-21 20:43:26.386276
- Title: Quantum and classical algorithms for SOCP based on the multiplicative weights update method
- Title（参考訳）: 乗法重み更新法に基づくSOCPの量子および古典的アルゴリズム
- Authors: M. Isabel Franco Garrido, Alexander M. Dalzell, Sam McArdle,
- Abstract要約: 第二次コーンプログラム(SOCP)を解くための古典的および量子的アルゴリズムを与える。
我々のアプローチは、半定値プログラム(SDP)に先立って適用されたMWフレームワークに従う。
我々は、SOCPの付加構造を利用して、SOCP固有のアルゴリズムでより優れたランタイムを提供することを示す。
- 参考スコア（独自算出の注目度）: 44.99833362998488
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We give classical and quantum algorithms for approximately solving second-order cone programs (SOCPs) based on the multiplicative weights (MW) update method. Our approach follows the MW framework previously applied to semidefinite programs (SDPs), of which SOCP is a special case. We show that the additional structure of SOCPs can be exploited to give better runtime with SOCP-specific algorithms. For an SOCP with $m$ linear constraints over $n$ variables partitioned into $r \leq n$ second-order cones, our quantum algorithm requires $\widetilde{O}(\sqrt{r}\gamma^5 + \sqrt{m}\gamma^4)$ (coherent) queries to the underlying data defining the instance, where $\gamma$ is a scale-invariant parameter proportional to the inverse precision. This nearly matches the complexity of solving linear programs (LPs), which are a less expressive subset of SOCP. It also outperforms (especially if $n \gg r$) the naive approach that applies existing SDP algorithms onto SOCPs, which has complexity $\widetilde{O}(\gamma^{4}(n + \gamma \sqrt{n} + \sqrt{m}))$. Our classical algorithm for SOCP has complexity $\widetilde{O}(n\gamma^4 + m \gamma^6)$ in the sample-and-query model.
- Abstract（参考訳）: 乗算重み更新法(MW)に基づく2次コーンプログラム(SOCP)の解法について,古典的および量子的アルゴリズムを提案する。
提案手法は,SOCPが特別な場合である半定値プログラム(SDP)に先立って適用されたMWフレームワークに従う。
我々は、SOCPの付加構造を利用して、SOCP固有のアルゴリズムでより優れたランタイムを提供することを示す。
m$$$n$変数を$r \leq n$ 2次錐に分割したSOCPの場合、我々の量子アルゴリズムは$\widetilde{O}(\sqrt{r}\gamma^5 + \sqrt{m}\gamma^4)$ (コヒーレントな)クエリをインスタンスを定義する基礎データに要求する。
これは、SOCPの表現力の低い部分集合である線形プログラム(LP)を解く複雑さにほぼ一致する。
また、(特に$n \gg r$ が)既存の SDP アルゴリズムを SOCP に適用する単純アプローチよりも優れている(複雑性 $\widetilde{O}(\gamma^{4}(n + \gamma \sqrt{n} + \sqrt{m}))。
我々のSOCPの古典的アルゴリズムは、サンプル・アンド・クエリモデルにおいて複雑さ$\widetilde{O}(n\gamma^4 + m \gamma^6)$である。
関連論文リスト
- Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳（メタデータ） (2025-02-07T15:57:56Z) - Quantum linear system algorithm with optimal queries to initial state preparation [0.0]
線形システムの量子アルゴリズムは、2つのオラクルを問合せして解状態$A-1|brangle$を生成する。
本稿では,$mathbfThetaleft (1/sqrtpright)$クエリを$O_b$に変換する量子線形系アルゴリズムを提案する。
微分方程式の解法のような様々な応用において、ブロックプレコンディショニングスキームを用いて$p$への依存をさらに改善することができる。
論文 参考訳（メタデータ） (2024-10-23T18:00:01Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Fast quantum algorithm for differential equations [0.5895819801677125]
我々は、数値複雑性を持つ量子アルゴリズムを、$N$で多対数であるが、大規模なPDEに対して$kappa$とは独立に提示する。
提案アルゴリズムは,解の特徴を抽出する量子状態を生成する。
論文 参考訳（メタデータ） (2023-06-20T18:01:07Z) - Quantum algorithm for position weight matrix matching [0.9404723842159504]
バイオインフォマティクス, 位置重み行列(PWM)マッチングにおける問題に対する2つの量子アルゴリズムを提案する。
提案した2つのアルゴリズム、ナイーブ法とモンテカルロ法は、生物学的配列のエントリへの分子アクセスを考慮し、一致したセグメントを出力する。
論文 参考訳（メタデータ） (2023-03-07T00:34:16Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Online Sub-Sampling for Reinforcement Learning with General Function
Approximation [111.01990889581243]
本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。
複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。
少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
論文 参考訳（メタデータ） (2021-06-14T07:36:25Z) - Practical and Parallelizable Algorithms for Non-Monotone Submodular
Maximization with Size Constraint [20.104148319012854]
サイズ制約に関して、必ずしも単調ではない部分モジュラ函数に対して存在および並列化可能である。
最適な適応性とほぼ最適な複雑性クエリを持つアルゴリズムによって達成される最適な近似係数を、0.193 - varepsilon$に改善する。
論文 参考訳（メタデータ） (2020-09-03T22:43:55Z) - Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
本稿では,有限地平線における全報酬の最大化と,各エポックにおける制約を確率1で満たすため,エージェントがポリシーを選択する,制約付きマルコフ決定プロセス(PCMDP)について考察する。
そこで本研究では,PCMDP問題を制約のない問題に変換するモデルフリーアルゴリズムを提案し,Q-ラーニングに基づくアプローチを適用した。
論文 参考訳（メタデータ） (2020-03-11T23:23:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。