論文の概要: Efficiency of k-Local Quantum Search and its Adiabatic Variant on Random
k-SAT
- arxiv url: http://arxiv.org/abs/2403.03237v1
- Date: Tue, 5 Mar 2024 15:03:47 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-07 17:16:31.878753
- Title: Efficiency of k-Local Quantum Search and its Adiabatic Variant on Random
k-SAT
- Title(参考訳): ランダムk-SATにおけるk-局所量子探索の効率とアダバティックバリアント
- Authors: Mingyou Wu
- Abstract要約: 本稿では、$k$-local quantum searchと呼ばれる、構造化量子探索アルゴリズムのファミリーを紹介する。
最大$k$-SSATは、平均ケース複雑性理論に基づく$m=Omega(n2+epsilon)$が平均であることを証明する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The computational complexity of random $k$-SAT problem is contingent on the
clause number $m$. In classical computing, a satisfiability threshold is
identified at $m=r_k n$, marking the transition of random $k$-SAT from
solubility to insolubility. However, beyond this established threshold,
comprehending the complexity remains challenging. On quantum computers, direct
application of Grover's unstructured quantum search still yields exponential
time requirements due to oversight of structural information. This paper
introduces a family of structured quantum search algorithms, termed $k$-local
quantum search, designed to address the $k$-SAT problem. Because search
algorithm necessitates the presence of a target, our focus is specifically on
the satisfiable side of $k$-SAT, i.e., max-$k$-SAT on satisfiable instances,
denoted as max-$k$-SSAT, with a small $k \ge 3$. For random instances with
$m=\Omega(n^{2+\epsilon})$, general exponential acceleration is proven for any
small $\epsilon>0$ and sufficiently large $n$. Furthermore, adiabatic $k$-local
quantum search improves the bound of general efficiency to
$m=\Omega(n^{1+\epsilon})$, within an evolution time of $\mathcal{O}(n^2)$.
Specifically, for $m=\Theta(n^{1+\delta+\epsilon})$, the efficiency is
guaranteed in a probability of $1-\mathcal{O}(\mathrm{erfc}(n^{\delta/2}))$. By
modifying this algorithm capable of solving all instances, we prove that the
max-$k$-SSAT is polynomial on average if $m=\Omega(n^{2+\epsilon})$ based on
the average-case complexity theory.
- Abstract(参考訳): ランダムな $k$-sat 問題の計算複雑性は、節番号 $m$ に付随する。
古典コンピューティングでは、溶解度から溶解度へのランダムな$k$-SATの遷移を示す、$m=r_k n$で満足度しきい値が特定される。
しかし、この確立されたしきい値を超えて、複雑さの理解は依然として困難である。
量子コンピュータでは、グロバーの非構造的量子探索の直接適用は、構造情報の監視による指数時間要求をもたらす。
本稿では、$k$-SAT問題に対処するために設計された、$k$-local quantum searchと呼ばれる構造化量子検索アルゴリズムのファミリーを紹介する。
探索アルゴリズムはターゲットの存在を必要とするため、我々の焦点は特に$k$-SATの満足度の高い側、すなわちmax-k$-SSATと表記されるインスタンスのmax-k$-SSATであり、小さな$k \ge 3$である。
m=\omega(n^{2+\epsilon})$のランダムインスタンスの場合、一般的な指数加速度は小さな$\epsilon>0$と十分大きい$n$に対して証明される。
さらに、adiabatic $k$-local quantum searchは、$\mathcal{O}(n^2)$の進化時間内で、一般効率の上限を$m=\Omega(n^{1+\epsilon})$に改善する。
具体的には、$m=\Theta(n^{1+\delta+\epsilon})$の場合、効率は1-\mathcal{O}(\mathrm{erfc}(n^{\delta/2})$の確率で保証される。
このアルゴリズムをすべてのインスタンスを解くことができるように修正することにより、m = Omega(n^{2+\epsilon})$が平均ケース複雑性理論に基づいて多項式であることが証明される。
関連論文リスト
- The Computational Complexity of Finding Stationary Points in Non-Convex
Optimization [60.53870185393238]
近似定常点、すなわち勾配がほぼゼロの点を見つけることは、非順序だが滑らかな目的函数の計算問題である。
制約付き最適化における近似KKT点の発見は、制約なし最適化における近似定常点の発見に対して再現可能であるが、逆は不可能であることを示す。
論文 参考訳(メタデータ) (2023-10-13T14:52:46Z) - 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) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳(メタデータ) (2023-07-13T18:59:28Z) - Succinct quantum testers for closeness and $k$-wise uniformity of
probability distributions [1.7789870146290503]
我々は、近接性の性質をテストする基本的な問題に対する潜在的な量子スピードアップについて検討する。
本稿では,クエリ複雑性を$Orbrasqrtnk/varepsilonで表した最初の量子アルゴリズムを提案する。
我々の量子アルゴリズムは、振幅推定のような基本的な量子サブルーチンのみを用いて、かなり単純で時間効率が高い。
論文 参考訳(メタデータ) (2023-04-25T15:32:37Z) - On the exact quantum query complexity of $\text{MOD}_m^n$ and
$\text{EXACT}_{k,l}^n$ [0.0]
我々は、$textMOD_mn$を計算するための正確な量子アルゴリズムを示す。
我々は、0,1n$ を有限集合 $X$ が$n$ 未満であるような対称関数の広いクラスの正確な量子クエリ複雑性を示す。
論文 参考訳(メタデータ) (2023-03-20T08:17:32Z) - Unitarity estimation for quantum channels [7.323367190336826]
ユニタリティ推定は、量子デバイス認証とベンチマークにおいて基礎的で重要な問題である。
我々は、アンシラ効率のアルゴリズムを誘導するユニタリティ推定のための統一的なフレームワークを提供する。
アルゴリズムの$d$-dependenceと$epsilon$-dependenceの両方が最適であることを示す。
論文 参考訳(メタデータ) (2022-12-19T09:36:33Z) - Robustness of Quantum Algorithms for Nonconvex Optimization [7.191453718557392]
量子アルゴリズムは多対数あるいは指数的なクエリ数を持つ$epsilon$-SOSPを$dで見つけることができることを示す。
また、量子アルゴリズムが多対数または指数的なクエリ数を持つ$epsilon$-SOSPを$dで見つけることができる領域を特徴付ける。
論文 参考訳(メタデータ) (2022-12-05T19:10:32Z) - 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) - The Algorithmic Phase Transition of Random $k$-SAT for Low Degree
Polynomials [18.00315760946089]
満足な代入は、節密度$m/n 2k log 2 - frac12で高い確率で存在することが知られている。
低次アルゴリズムは節密度$(1 - o_k(1)) 2k log k / k$で満足な代入を見つけることができる。
論文 参考訳(メタデータ) (2021-06-03T21:01:02Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳(メタデータ) (2020-08-24T06:50:57Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳(メタデータ) (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。