論文の概要: On the Fine-Grained Query Complexity of Symmetric Functions
- arxiv url: http://arxiv.org/abs/2309.11279v2
- Date: Sun, 22 Oct 2023 02:38:07 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-25 07:29:51.765590
- Title: On the Fine-Grained Query Complexity of Symmetric Functions
- Title（参考訳）: 対称関数のきめ細かい問合せ複雑性について
- Authors: Supartha Podder, Penghui Yao and Zekun Ye
- Abstract要約: 本稿では、Watrous予想のきめ細かいバージョンについて考察する。
確率が任意に1/2ドルに近いランダム化および量子化アルゴリズムを含む。
- 参考スコア（独自算出の注目度）: 4.956977275061968
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper explores a fine-grained version of the Watrous conjecture,
including the randomized and quantum algorithms with success probabilities
arbitrarily close to $1/2$. Our contributions include the following:
i) An analysis of the optimal success probability of quantum and randomized
query algorithms of two fundamental partial symmetric Boolean functions given a
fixed number of queries. We prove that for any quantum algorithm computing
these two functions using $T$ queries, there exist randomized algorithms using
$\mathsf{poly}(T)$ queries that achieve the same success probability as the
quantum algorithm, even if the success probability is arbitrarily close to 1/2.
ii) We establish that for any total symmetric Boolean function $f$, if a
quantum algorithm uses $T$ queries to compute $f$ with success probability
$1/2+\beta$, then there exists a randomized algorithm using $O(T^2)$ queries to
compute $f$ with success probability $1/2+\Omega(\delta\beta^2)$ on a
$1-\delta$ fraction of inputs, where $\beta,\delta$ can be arbitrarily small
positive values. As a corollary, we prove a randomized version of
Aaronson-Ambainis Conjecture for total symmetric Boolean functions in the
regime where the success probability of algorithms can be arbitrarily close to
1/2.
iii) We present polynomial equivalences for several fundamental complexity
measures of partial symmetric Boolean functions. Specifically, we first prove
that for certain partial symmetric Boolean functions, quantum query complexity
is at most quadratic in approximate degree for any error arbitrarily close to
1/2. Next, we show exact quantum query complexity is at most quadratic in
degree. Additionally, we give the tight bounds of several complexity measures,
indicating their polynomial equivalence.
- Abstract（参考訳）: 本稿では、確率が任意に1/2$に近いランダム化および量子化アルゴリズムを含む、Watrous予想のきめ細かいバージョンを探索する。
私たちの貢献には以下のものがある。
i) 固定されたクエリ数が与えられた2つの基本部分対称ブール関数の量子およびランダム化クエリアルゴリズムの最適成功確率の解析。
我々は、これらの2つの関数を$t$クエリで計算する量子アルゴリズムに対して、成功確率が1/2に近い場合であっても、量子アルゴリズムと同じ成功確率を達成する$\mathsf{poly}(t)$クエリを用いたランダム化アルゴリズムが存在することを証明する。
i)任意の全対称ブール関数$f$に対して、量子アルゴリズムが成功確率1/2+\beta$を計算するために$T$クエリを使用していれば、成功確率1/2+\Omega(\delta\beta^2)$を計算するために$O(T^2)$クエリを使用してランダム化されたアルゴリズムが存在し、$\beta,\delta$を任意に小さな正の値にすることができる。
コーナリーとして、アルゴリズムの成功確率が 1/2 に任意に近づく状態において、全対称ブール関数に対するアーロンソン・アンバイニス導出のランダム化版を証明する。
iii) 部分対称ブール関数のいくつかの基本複雑性測度に対する多項式同値性を示す。
具体的には、ある部分対称ブール関数に対して、量子的クエリの複雑性は1/2に近い任意の誤差に対して最も2次的に証明する。
次に、量子クエリの複雑性が少なくとも2次であることを示す。
さらに、いくつかの複雑性測度の厳密な境界を与え、それらの多項式同値性を示す。
関連論文リスト
- Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳（メタデータ） (2023-11-07T04:59:02Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - 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) - 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) - 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) - Testing Boolean Functions Properties [1.5924410290166868]
関数のプロパティテストの分野での目標は、与えられたブラックボックスのブール関数が特定のプロパティを持っているか、あるいはそのプロパティが持たない$varepsilon$-farであるかどうかを決定することである。
ここでは、Deutsch-Jozsaアルゴリズムを用いてブール関数(同一性、相関、平衡性)のテストを行ういくつかの性質について検討する。
論文 参考訳（メタデータ） (2021-09-14T15:27:38Z) - Random quantum circuits anti-concentrate in log depth [118.18170052022323]
本研究では,典型的な回路インスタンスにおける測定結果の分布に要するゲート数について検討する。
我々の反集中の定義は、予測衝突確率が分布が均一である場合よりも大きい定数因子に過ぎないということである。
ゲートが1D環上で最寄りである場合と、ゲートが長距離である場合の両方において、$O(n log(n))ゲートも十分であることを示す。
論文 参考訳（メタデータ） (2020-11-24T18:44:57Z) - Characterization of exact one-query quantum algorithms (ii): for partial
functions [0.2741266294612775]
クエリモデル(またはブラックボックスモデル)は、古典コンピューティングと量子コンピューティングの両方のコミュニティから多くの注目を集めている。
通常、量子の利点は、古典的なアルゴリズムよりもクエリの複雑さが高い量子アルゴリズムを提示することで明らかにされる。
例えば、Deutsch-Jozsaアルゴリズム、Simonアルゴリズム、Groverアルゴリズムといったよく知られた量子アルゴリズムは、クエリ複雑性の観点から量子コンピューティングのかなりの利点を示している。
論文 参考訳（メタデータ） (2020-08-27T09:06:34Z) - 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) - Exact Quantum Query Algorithms Outperforming Parity -- Beyond The
Symmetric functions [3.652509571098291]
まず、$Omega left(2fracsqrtn2 right)$非対称関数の直和に基づくクラスに対して、最適な正確な量子クエリアルゴリズム(Q_algo(f)$)を得る。
Q_algo$のクエリ複雑性は$lceil frac3n4 rceil$であるのに対して、$D_oplus(f)$は$n-1$と$lceil frac3n4 rceの間で異なる。
論文 参考訳（メタデータ） (2020-08-14T12:17:48Z) - Towards Optimal Separations between Quantum and Randomized Query
Complexities [0.30458514384586394]
入力に対して2O(k)$クエリを行うことで量子アルゴリズムを解くことができることを示す。
任意の定数 $varepsilon>0$ に対して、$O(1)$ 対 $N2/3-varepsilon$ 分離を与える。
論文 参考訳（メタデータ） (2019-12-29T01:42:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。