論文の概要: Quantum Implications of Huang's Sensitivity Theorem

• arxiv url: http://arxiv.org/abs/2004.13231v1
• Date: Tue, 28 Apr 2020 00:54:23 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-21 22:01:34.439952
• Title: Quantum Implications of Huang's Sensitivity Theorem
• Title（参考訳）: Huangの感度理論の量子的意味
• Authors: Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal
• Abstract要約: ブール関数の総和が$f$の場合、決定論的クエリ複雑性である$D(f)$は、量子的クエリ複雑性において少なくとも準位であることを示す。 また、Aanderaa-Karp-Rosenberg予想の量子アナログを解くためにもこの結果を利用する。
• 参考スコア（独自算出の注目度）: 4.970364068620607
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function $f$, the deterministic query complexity, $D(f)$, is at most quartic in the quantum query complexity, $Q(f)$: $D(f) = O(Q(f)^4)$. This matches the known separation (up to log factors) due to Ambainis, Balodis, Belovs, Lee, Santha, and Smotrovs (2017). We also use the result to resolve the quantum analogue of the Aanderaa-Karp-Rosenberg conjecture. We show that if $f$ is a nontrivial monotone graph property of an $n$-vertex graph specified by its adjacency matrix, then $Q(f) = \Omega(n)$, which is also optimal.
• Abstract（参考訳）: Huang (2019) の最近のブレークスルーに基づき、すべてのブール関数 $f$ に対して、決定論的クエリ複雑性である $D(f)$ は、量子的クエリ複雑性において最も質的に、$Q(f)$: $D(f) = O(Q(f)^4)$ であることを示す。 ambainis, balodis, belovs, lee, santha, smotrovs (2017) による既知の分離 (ログファクタ) と一致している。 また、この結果を用いてaanderaa-karp-rosenberg予想の量子アナログを解く。 f$ がその隣接行列によって指定された$n$-vertex グラフの非自明な単調グラフの性質であるなら、$q(f) = \omega(n)$ もまた最適である。

関連論文リスト

• Implementation of Continuous-Time Quantum Walk on Sparse Graph [0.0]
  連続時間量子ウォーク(CTQW)は、量子コンピューティングにおいて重要な役割を果たす。 CTQWを効率的に実装する方法は難しい問題である。 本稿では,スパースグラフ上でのCTQWの実装について検討する。
  論文  参考訳（メタデータ） (2024-08-20T05:20:55Z)
• A generic quantum Wielandt's inequality [0.9975341265604578]
  一般に$k$は$mathcalO(n2)$の次数でなければならないと推測されている。 量子ウィーランドの不等式の一般的なバージョンを提供し、確率 1 で最適な長さを与える。 我々は、Projected Entangled Pair Stateの長年のオープンな問題に新たな光を当てた。
  論文  参考訳（メタデータ） (2023-01-19T18:57:32Z)
• Quantum Speedups of Optimizing Approximately Convex Functions with Applications to Logarithmic Regret Stochastic Convex Bandits [8.682187438614296]
  量子アルゴリズムは、$F(x*)-min_xincal K F(x)leqepsilon$が$tildeO(n3)$が$F$となるような$x*incal K$を求める。 応用として、ゼロ階凸包帯に対して $tildeO(n5log2 T)$ regret の量子関数アルゴリズムを与える。
  論文  参考訳（メタデータ） (2022-09-26T03:19:40Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。 我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。 我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
  論文  参考訳（メタデータ） (2022-08-19T18:00:34Z)
• 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)
• Quantum double aspects of surface code models [77.34726150561087]
  基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。 有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
  論文  参考訳（メタデータ） (2021-06-25T17:03:38Z)
• Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem [4.549831511476248]
  すべてのブール関数に対して、$f$, $bullet quad mathrmdeg(f) = O(widetildemathrmdeg(f)2)$:$f$の次数は、f$の近似次数において最も自明な二次数であることを示す。 f$ がその隣接行列で指定される $n$-頂点グラフの非単調グラフ特性であるならば、$mathrmQ(f)=Omega(n)$ もまた最適である。
  論文  参考訳（メタデータ） (2020-10-23T19:21:28Z)
• 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)
• Quantum Coupon Collector [62.58209964224025]
  我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。 我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-02-18T16:14:55Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。