論文の概要: Improved Approximate Degree Bounds For k-distinctness
- arxiv url: http://arxiv.org/abs/2002.08389v1
- Date: Wed, 19 Feb 2020 19:04:44 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-03 04:48:29.596332
- Title: Improved Approximate Degree Bounds For k-distinctness
- Title（参考訳）: k-distinctnessのための近似度境界の改善
- Authors: Nikhil S. Mande, Justin Thaler and Shuchen Zhu
- Abstract要約: 開問題は、サイズ N の入力上の k-判別関数の量子複雑性を解くことである。
任意の定数 k >= 4 に対して、Omega(N(3/4)-1/(4k)) への下界を改善する。
これは、例えば、4-連続性はより難しいという最初の証明をもたらす。
- 参考スコア（独自算出の注目度）: 2.1845023178514413
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: An open problem that is widely regarded as one of the most important in
quantum query complexity is to resolve the quantum query complexity of the
k-distinctness function on inputs of size N. While the case of k=2 (also called
Element Distinctness) is well-understood, there is a polynomial gap between the
known upper and lower bounds for all constants k>2. Specifically, the best
known upper bound is O(N^{(3/4)-1/(2^{k+2}-4)}) (Belovs, FOCS 2012), while the
best known lower bound for k >= 2 is Omega(N^{2/3} + N^{(3/4)-1/(2k)})
(Aaronson and Shi, J.~ACM 2004; Bun, Kothari, and Thaler, STOC 2018).
For any constant k >= 4, we improve the lower bound to
Omega(N^{(3/4)-1/(4k)}). This yields, for example, the first proof that
4-distinctness is strictly harder than Element Distinctness. Our lower bound
applies more generally to approximate degree.
As a secondary result, we give a simple construction of an approximating
polynomial of degree O(N^{3/4}) that applies whenever k <= polylog(N).
- Abstract（参考訳）: 量子クエリの複雑性において最も重要な問題の1つは、サイズ n の入力における k-ディスティンクネス関数の量子クエリの複雑さを解決することである。 k=2 の場合(要素の識別性とも呼ばれる)はよく理解されているが、すべての定数 k>2 に対して既知の上界と下界の間には多項式ギャップが存在する。
具体的には、最もよく知られている上界は O(N^{(3/4)-1/(2^{k+2}-4)} (Belovs, FOCS 2012) であるが、k >= 2 の最もよく知られている下界は Omega(N^{2/3} + N^{(3/4)-1/(2k)} (Aaronson and Shi, J.~ACM 2004; Bun, Kothari, and Thaler, STOC 2018) である。
任意の定数 k >= 4 に対して、下限をomega(n^{(3/4)-1/(4k)}) に改善する。
これは例えば、最初の証明である4-分極性は要素の区別性よりも厳密に難しい。
我々の下界はより一般に近似度に当てはまる。
二次的な結果として、次数 O(N^{3/4}) の近似多項式の簡単な構成を与える。
関連論文リスト
- Overcomplete Tensor Decomposition via Koszul-Young Flattenings [63.01248796170617]
最小ランク1項の和として$n_times n times n_3$ tensorを分解する新しいアルゴリズムを与える。
次数-d$s のさらに一般的なクラスは、定数 $C = C(d)$ に対して階数 $Cn$ を超えることができないことを示す。
論文 参考訳（メタデータ） (2024-11-21T17:41:09Z) - Better bounds on Grothendieck constants of finite orders [20.068273625719943]
我々は最近のフランク・ウルフのアプローチを利用して、いくつかのグロタンディーク定数を下限とするよい候補を提供する。
完全証明は難解な二項最適化問題を解くことに依存する。
論文 参考訳（メタデータ） (2024-09-05T17:53:52Z) - The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳（メタデータ） (2024-02-29T01:35:46Z) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
本稿では、2つの異なる対象の一般円錐最適化を最小化する近似二階定常点(SOSP)について検討する。
特に、近似SOSPを見つけるためのNewton-CGベースの拡張共役法を提案する。
論文 参考訳（メタデータ） (2023-01-10T20:43:29Z) - Quantum and classical low-degree learning via a dimension-free Remez
inequality [52.12931955662553]
ハイパーグリッド上の関数をポリトーラス上の高調波拡張に関連付ける新しい方法を示す。
巡回群 $exp(2pi i k/K)_k=1K$ の積に対して函数の上限が$f$であることを示す。
我々は最近、超キューブやキュービット上の観測可能な観測値の低次学習を、同様に効率的に行う方法として、EI22, CHP, VZ22を引用して、新しい空間に拡張した。
論文 参考訳（メタデータ） (2023-01-04T04:15:40Z) - Multidimensional Quantum Walks, with Application to $k$-Distinctness [0.5064404027153093]
時間複雑性に対して$widetildeOleft(n3/4-1/4(2k-1)right)の新たな上限を与える。
この新しい手法を用いて,$O(n)$クエリと$O(n2)$タイムで溶接木を解く方法を示す。
論文 参考訳（メタデータ） (2022-08-29T10:51:56Z) - On converses to the polynomial method [0.0]
アーロンソンらによる驚くべき「方法への逆」は、任意の有界二次函数は、グロエンディーク定数に関連する普遍的乗法因子まで正確に計算できることを示している。
小さい加法誤差を許容した場合、結果が依然として成り立つことを示す。
論文 参考訳（メタデータ） (2022-04-26T13:32:02Z) - 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) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Genuinely quantum SudoQ and its cardinality [0.0]
真の量子解の完全なパラメタライゼーションは、SudoQ の 4 倍 4$ である。
特に、最大濃度が16に等しい解が提示される。
論文 参考訳（メタデータ） (2021-06-05T21:22:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。