論文の概要: Exact Quantum Query Algorithms Outperforming Parity -- Beyond The
Symmetric functions
- arxiv url: http://arxiv.org/abs/2008.06317v5
- Date: Sun, 16 May 2021 13:35:55 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-06 07:10:01.551705
- Title: Exact Quantum Query Algorithms Outperforming Parity -- Beyond The
Symmetric functions
- Title（参考訳）: 正確な量子クエリアルゴリズムはパリティを上回る -- 対称関数を超えて
- Authors: Chandra Sekhar Mukherjee, Subhamoy Maitra
- Abstract要約: まず、$Omega left(2fracsqrtn2 right)$非対称関数の直和に基づくクラスに対して、最適な正確な量子クエリアルゴリズム(Q_algo(f)$)を得る。
Q_algo$のクエリ複雑性は$lceil frac3n4 rceil$であるのに対して、$D_oplus(f)$は$n-1$と$lceil frac3n4 rceの間で異なる。
- 参考スコア（独自算出の注目度）: 3.652509571098291
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In Exact Quantum Query model, almost all of the Boolean functions for which
non-trivial query algorithms exist are symmetric in nature. The most well known
techniques in this domain exploit parity decision trees, in which the parity of
two bits can be obtained by a single query. Thus, exact quantum query
algorithms outperforming parity decision trees are rare. In this paper we first
obtain optimal exact quantum query algorithms ($Q_{algo}(f)$) for a direct sum
based class of $\Omega \left( 2^{\frac{\sqrt{n}}{2}} \right)$ non-symmetric
functions. We construct these algorithms by analyzing the algebraic normal form
together with a novel untangling strategy. Next we obtain the generalized
parity decision tree complexity ($D_{\oplus}(f)$) analysing the Walsh Spectrum.
Finally, we show that query complexity of $Q_{algo}$ is $\lceil \frac{3n}{4}
\rceil$ whereas $D_{\oplus}(f)$ varies between $n-1$ and $\lceil \frac{3n}{4}
\rceil+1$ for different classes, underlining linear separation between the two
measures in many cases. To the best of our knowledge, this is the first family
of algorithms beyond generalized parity (and thus parity) for a large class of
non-symmetric functions. We also implement these techniques for a larger
(doubly exponential in $\frac{n}{4}$) class of Maiorana-McFarland type
functions, but could only obtain partial results using similar algorithmic
techniques.
- Abstract（参考訳）: Exact Quantum Queryモデルでは、非自明なクエリアルゴリズムが存在するブール関数のほとんどすべてが本質的に対称である。
この領域で最もよく知られているテクニックはパリティ決定木を利用しており、2ビットのパリティを単一のクエリで得ることができる。
したがって、パリティ決定木を上回る正確な量子クエリアルゴリズムはまれである。
本稿では、まず、$\Omega \left(2^{\frac{\sqrt{n}}{2}} \right)$非対称関数の直和に基づくクラスに対して、最適な正確な量子クエリアルゴリズム(Q_{algo}(f)$)を得る。
これらのアルゴリズムは、代数正規形を新しいアンタングリング戦略と共に解析することで構築する。
次に、ウォルシュスペクトルを分析する一般化パリティ決定木複雑性(d_{\oplus}(f)$)を得る。
最後に、$Q_{algo}$ のクエリ複雑性は $\lceil \frac{3n}{4} \rceil$ であるのに対し、$D_{\oplus}(f)$ は $n-1$ と $\lceil \frac{3n}{4} \rceil+1$ によって異なるクラスに対して異なる。
我々の知る限りでは、これは非対称関数の大きなクラスに対する一般化パリティ(つまりパリティ)を超えたアルゴリズムの最初のファミリーである。
また、maiorana-mcfarland型関数のより大きい(ほぼ指数関数の$\frac{n}{4}$)クラスに対してこれらの手法を実装したが、類似のアルゴリズム技術を用いてのみ部分的な結果を得ることができた。
関連論文リスト
- Towards Optimal Circuit Size for Sparse Quantum State Preparation [10.386753939552872]
我々は、$s$非ゼロ振幅を持つ$n$量子ビットスパース量子状態の準備を検討し、2つのアルゴリズムを提案する。
最初のアルゴリズムは$O(ns/log n + n)$ gatesを使用し、以前のメソッドを$O(log n)$で改善する。
2番目のアルゴリズムは、短いハミルトニアンパスを示す二進弦向けに調整されている。
論文 参考訳（メタデータ） (2024-04-08T02:13:40Z) - 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) - Robust Approximation Algorithms for Non-monotone $k$-Submodular
Maximization under a Knapsack Constraint [0.0]
2つの決定論的近似アルゴリズムは、knapsack制約の下での非単調な$k$-部分モジュラー複雑性の問題に対して提案される。
提案アルゴリズムは,非単調な目的に対して,O(nk)$クエリの計算量内で一定の近似比を提供する。
論文 参考訳（メタデータ） (2023-09-21T12:42:52Z) - Do you know what q-means? [50.045011844765185]
クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。
クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。
また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - 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) - 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) - 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) - Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。
本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文 参考訳（メタデータ） (2021-05-18T06:51:11Z) - Quantum speedups for dynamic programming on $n$-dimensional lattice
graphs [0.11470070927586015]
複雑性を$widetilde O(T_Dn)$で表すと、$T_D D+1$となる。
最もよく知られている古典的アルゴリズムは $textpoly(m,n)log n T_Dn$ であるが、量子アルゴリズムの時間複雑性は $textpoly(m,n)log n T_Dn$ である。
論文 参考訳（メタデータ） (2021-04-29T14:50:03Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。