論文の概要: Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end
- arxiv url: http://arxiv.org/abs/2212.01513v1
- Date: Sat, 3 Dec 2022 02:45:23 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-09 19:35:56.527622
- Title: Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end
- Title（参考訳）: ギャップを心に留めて - スーパーグローバーによる量子スピードアップの実現
- Authors: Alexander M. Dalzell, Nicola Pancotti, Earl T. Campbell, Fernando G.
S. L. Brand\~ao
- Abstract要約: 本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
- 参考スコア（独自算出の注目度）: 114.3957763744719
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a quantum algorithm that has rigorous runtime guarantees for
several families of binary optimization problems, including Quadratic
Unconstrained Binary Optimization (QUBO), Ising spin glasses ($p$-spin model),
and $k$-local constraint satisfaction problems ($k$-CSP). We show that either
(a) the algorithm finds the optimal solution in time $O^*(2^{(0.5-c)n})$ for an
$n$-independent constant $c$, a $2^{cn}$ advantage over Grover's algorithm; or
(b) there are sufficiently many low-cost solutions such that classical random
guessing produces a $(1-\eta)$ approximation to the optimal cost value in
sub-exponential time for arbitrarily small choice of $\eta$. Additionally, we
show that for a large fraction of random instances from the $k$-spin model and
for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a)
is the case. The algorithm and its analysis is largely inspired by Hastings'
short-path algorithm [$\textit{Quantum}$ $\textbf{2}$ (2018) 78].
- Abstract（参考訳）: 我々は、二分最適化問題(qubo)、スピングラスのイジング(p$-spinモデル)、k$ローカル制約満足度問題(k$-csp)など、いくつかの二分最適化問題に対して厳密な実行時保証を持つ量子アルゴリズムを提案する。
どちらかに示すのは
(a)このアルゴリズムは、グロバーのアルゴリズムに対して、n$非依存定数$c$、$2^{cn}$の利点に対して、時間$o^*(2^{(0.5-c)n})$の最適解を見つける。
(b) 古典的ランダムな推定が$(1-\eta)$の近似を任意に小さな$\eta$を選択するための準指数時間における最適コスト値に生成するような、十分に多くの低コストの解が存在する。
さらに、$k$-spinモデルからのランダムインスタンスのごく一部と、完全に満足できる、あるいは少しフラストレーションのある$k$-csp公式のステートメントを示す。
(a)がそうである。
このアルゴリズムとその解析はHastingsのショートパスアルゴリズム [$\textit{Quantum}$ $\textbf{2}$ (2018) 78] に大きく影響を受けている。
関連論文リスト
- Quantum Algorithms for Non-smooth Non-convex Optimization [30.576546266390714]
本稿では、リプシッツ連続目的の$(,epsilon)$-Goldstein定常点を求める問題を考える。
代理オラクル関数に対するゼロ階量子推定器を構築する。
論文 参考訳（メタデータ） (2024-10-21T16:52:26Z) - Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss [16.91814406135565]
我々は量子アルゴリズムと下界の体系的な研究を行い、最大で$N$凸、リプシッツ関数を最小化する。
我々は、量子アルゴリズムが$tildeOmega(sqrtNepsilon-2/3)$クエリを1次量子オラクルに取らなければならないことを証明している。
論文 参考訳（メタデータ） (2024-02-20T06:23:36Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - Near-Optimal Lower Bounds For Convex Optimization For All Orders of
Smoothness [26.71898403195793]
非常に滑らかな凸関数を最適化する複雑性について検討する。
正の整数 $p$ に対して、凸関数 $f$ の最小値 $epsilon$-approximate を求める。
我々は、この境界(ログファクタまで)にマッチする新しい下界を証明し、ランダム化アルゴリズムだけでなく、量子アルゴリズムにも適用する。
論文 参考訳（メタデータ） (2021-12-02T10:51:43Z) - No quantum speedup over gradient descent for non-smooth convex
optimization [22.16973542453584]
ブラックボックスアクセスは(必ずしも滑らかではない)関数 $f:mathbbRn から mathbbR$ とその (サブ) 階数へのアクセスである。
私たちのゴールは、$epsilon$-approximate minimum of $f$ を、真極小から少なくとも$R$ の距離から始めることにある。
下界で使われる関数族はランダム化アルゴリズムでは難しいが、$O(GR/epsilon)$量子クエリで解くことができる。
論文 参考訳（メタデータ） (2020-10-05T06:32:47Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Maximizing Determinants under Matroid Constraints [69.25768526213689]
我々は、$det(sum_i in Sv_i v_i v_itop)$が最大になるような基底を$S$$$$M$とする問題を研究する。
この問題は、実験的なデザイン、商品の公平な割り当て、ネットワーク設計、機械学習など、さまざまな分野に現れている。
論文 参考訳（メタデータ） (2020-04-16T19:16:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。