論文の概要: Towards Optimal Separations between Quantum and Randomized Query
Complexities
- arxiv url: http://arxiv.org/abs/1912.12561v1
- Date: Sun, 29 Dec 2019 01:42:31 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-17 08:12:51.238236
- Title: Towards Optimal Separations between Quantum and Randomized Query
Complexities
- Title（参考訳）: 量子とランダムな問合せの最適分離に向けて
- Authors: Avishay Tal
- Abstract要約: 入力に対して2O(k)$クエリを行うことで量子アルゴリズムを解くことができることを示す。
任意の定数 $varepsilon>0$ に対して、$O(1)$ 対 $N2/3-varepsilon$ 分離を与える。
- 参考スコア（独自算出の注目度）: 0.30458514384586394
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The query model offers a concrete setting where quantum algorithms are
provably superior to randomized algorithms. Beautiful results by
Bernstein-Vazirani, Simon, Aaronson, and others presented partial Boolean
functions that can be computed by quantum algorithms making much fewer queries
compared to their randomized analogs. To date, separations of $O(1)$ vs.
$\sqrt{N}$ between quantum and randomized query complexities remain the
state-of-the-art (where $N$ is the input length), leaving open the question of
whether $O(1)$ vs. $N^{1/2+\Omega(1)}$ separations are possible? We answer this
question in the affirmative. Our separating problem is a variant of the
Aaronson-Ambainis $k$-fold Forrelation problem. We show that our variant:
(1) Can be solved by a quantum algorithm making $2^{O(k)}$ queries to the
inputs.
(2) Requires at least $\tilde{\Omega}(N^{2(k-1)/(3k-1)})$ queries for any
randomized algorithm.
For any constant $\varepsilon>0$, this gives a $O(1)$ vs.
$N^{2/3-\varepsilon}$ separation between the quantum and randomized query
complexities of partial Boolean functions. Our proof is Fourier analytical and
uses new bounds on the Fourier spectrum of classical decision trees, which
could be of independent interest. Looking forward, we conjecture that the
Fourier bounds could be further improved in a precise manner, and show that
such conjectured bounds imply optimal $O(1)$ vs. $N^{1-\varepsilon}$
separations between the quantum and randomized query complexities of partial
Boolean functions.
- Abstract（参考訳）: クエリモデルは、量子アルゴリズムがランダム化アルゴリズムよりも確実に優れている具体的な設定を提供する。
Bernstein-Vazirani、Simon、Aaronsonらによる美しい結果は、ランダム化されたアナログに比べてはるかに少ないクエリを量子アルゴリズムで計算できる部分ブール関数を提示した。
現在まで、量子化されたクエリとランダム化されたクエリの複雑さの間の$O(1)$ vs. $\sqrt{N}$の分離は最先端のままであり($N$は入力長である)、$O(1)$ vs. $N^{1/2+\Omega(1)}$の分離は可能か?
私たちはこの質問を肯定的に答える。
我々の分離問題は Aaronson-Ambainis $k$-fold Forrelation 問題の変種である。
1)入力に対して$2^{O(k)}$クエリを行う量子アルゴリズムによって解けることを示す。
2)任意のランダム化アルゴリズムに対して少なくとも$\tilde{\Omega}(N^{2(k-1)/(3k-1)})$クエリを必要とする。
任意の定数 $\varepsilon>0$ に対して、$O(1)$ vs. $N^{2/3-\varepsilon} の部分ブール関数の量子的およびランダムなクエリ複雑度を分離する。
我々の証明はフーリエ解析であり、古典的決定木のフーリエスペクトルの新たな境界を使い、これは独立した関心を持つ可能性がある。
今後は、フーリエ境界はより正確に改善できると予測し、そのような予想された境界は、部分ブール関数の量子的およびランダムなクエリ複雑度の間の分離を、最適に$O(1)$ vs. $N^{1-\varepsilon} であることを示す。
関連論文リスト
- Succinct quantum testers for closeness and $k$-wise uniformity of probability distributions [2.3466828785520373]
確率分布の近さ特性と$k$-wise均一性をテストする基本的な問題に対する潜在的な量子スピードアップについて検討する。
我々は、$ell1$-および$ell2$-closenessテストの量子クエリ複雑性が$O(sqrtn/varepsilon)$と$O(sqrtnk/varepsilon)$であることを示す。
クエリ複雑性を$O(sqrtnk/varepsilon)で表した最初の量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-25T15:32:37Z) - On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$ [4.956977275061968]
我々は、$textMOD_mn$を計算するための正確な量子アルゴリズムを示す。
我々は、0,1n$ を有限集合 $X$ が$n$ 未満であるような対称関数の広いクラスの正確な量子クエリ複雑性を示す。
論文 参考訳（メタデータ） (2023-03-20T08:17: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) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - Testing Boolean Functions Properties [1.5924410290166868]
関数のプロパティテストの分野での目標は、与えられたブラックボックスのブール関数が特定のプロパティを持っているか、あるいはそのプロパティが持たない$varepsilon$-farであるかどうかを決定することである。
ここでは、Deutsch-Jozsaアルゴリズムを用いてブール関数(同一性、相関、平衡性)のテストを行ういくつかの性質について検討する。
論文 参考訳（メタデータ） (2021-09-14T15:27:38Z) - 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) - The Quantum Supremacy Tsirelson Inequality [0.22843885788439797]
量子回路 $C$ on $n$ qubits とサンプル $z in 0,1n$ のとき、ベンチマークは$|langle z|C|0n rangle|2$ の計算を伴う。
任意の $varepsilon ge frac1mathrmpoly(n)$ に対して、サンプル $z$ を出力することは、平均で $|langle z|C|0nrangle|2$ に対して最適な 1-クエリであることを示す。
論文 参考訳（メタデータ） (2020-08-20T01:04:32Z) - $k$-Forrelation Optimally Separates Quantum and Classical Query
Complexity [3.4984289152418753]
我々は、$N$ビット上の任意の部分関数は、$q$量子クエリを作れば、ランダムな推測よりも$delta$で計算できることを示した。
我々はまた、$k$-Forrelation問題 -- $q = lceil k/2 rceil$量子クエリで計算できる部分関数 -- を予想した。
論文 参考訳（メタデータ） (2020-08-16T21:26:46Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z) - Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。
我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文 参考訳（メタデータ） (2020-02-18T16:14:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。