論文の概要: Can graph properties have exponential quantum speedup?

• arxiv url: http://arxiv.org/abs/2001.10520v1
• Date: Tue, 28 Jan 2020 18:45:48 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-05 08:52:48.457287
• Title: Can graph properties have exponential quantum speedup?
• Title（参考訳）: グラフ特性は指数関数的量子スピードアップを持つか?
• Authors: Andrew M. Childs, Daochen Wang
• Abstract要約: 特に、(部分)グラフの性質に対して指数的スピードアップが可能かどうかを問うのは自然である。 この疑問に対する答えは入力モデルに強く依存していることを示す。
• 参考スコア（独自算出の注目度）: 5.101801159418223
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum computers can sometimes exponentially outperform classical ones, but only for problems with sufficient structure. While it is well known that query problems with full permutation symmetry can have at most polynomial quantum speedup -- even for partial functions -- it is unclear how far this condition must be relaxed to enable exponential speedup. In particular, it is natural to ask whether exponential speedup is possible for (partial) graph properties, in which the input describes a graph and the output can only depend on its isomorphism class. We show that the answer to this question depends strongly on the input model. In the adjacency matrix model, we prove that the bounded-error randomized query complexity $R$ of any graph property $\mathcal{P}$ has $R(\mathcal{P}) = O(Q(\mathcal{P})^{6})$, where $Q$ is the bounded-error quantum query complexity. This negatively resolves an open question of Montanaro and de Wolf in the adjacency matrix model. More generally, we prove $R(\mathcal{P}) = O(Q(\mathcal{P})^{3l})$ for any $l$-uniform hypergraph property $\mathcal{P}$ in the adjacency matrix model. In direct contrast, in the adjacency list model for bounded-degree graphs, we exhibit a promise problem that shows an exponential separation between the randomized and quantum query complexities.
• Abstract（参考訳）: 量子コンピュータは時として古典的コンピュータを指数関数的に上回ることができるが、十分な構造を持つ問題に限る。 完全置換対称性を持つ問合せ問題は、ほとんどの多項式量子スピードアップ -- 部分関数であっても -- を持つことはよく知られているが、指数的スピードアップを実現するためにこの条件がどの程度緩和されなければならないかは定かではない。 特に、入力がグラフを記述し、出力がその同型類にのみ依存する(部分的)グラフの性質に対して指数的高速化が可能かどうかを問うのは自然である。 この疑問に対する答えは入力モデルに強く依存していることを示す。 隣接行列モデルでは、任意のグラフプロパティの有界エラーランダム化クエリ複雑性 $r$ が $r(\mathcal{p}) = o(q(\mathcal{p})^{6})$ であることを証明する。 このことは、隣接行列モデルにおけるモンタナロとデ・ウルフの開問題を否定的に解決する。 より一般に、随伴行列モデルにおいて、任意の$l$-一様ハイパーグラフプロパティ$\mathcal{p}$に対して、$r(\mathcal{p}) = o(q(\mathcal{p})^{3l})$ が証明される。 対照的に、有界次グラフの隣接リストモデルでは、ランダム化と量子クエリの複雑度の間の指数関数的分離を示すpromise問題を示す。

関連論文リスト

• Data subsampling for Poisson regression with pth-root-link [53.63838219437508]
  ポアソン回帰のためのデータサブサンプリング手法を開発し解析する。 特に,ポアソン一般化線形モデルと ID-および平方根リンク関数について考察する。
  論文  参考訳（メタデータ） (2024-10-30T10:09:05Z)
• Implementation of Continuous-Time Quantum Walk on Sparse Graph [0.0]
  連続時間量子ウォーク(CTQW)は、量子コンピューティングにおいて重要な役割を果たす。 CTQWを効率的に実装する方法は難しい問題である。 本稿では,スパースグラフ上でのCTQWの実装について検討する。
  論文  参考訳（メタデータ） (2024-08-20T05:20:55Z)
• From Bit-Parallelism to Quantum String Matching for Labelled Graphs [0.0]
  二次時間で解ける多くの問題は、ビットパラレルのスピードアップが$w$で、$w$はコンピュータワードサイズである。 このような制限されたグラフの族上の単純なビット並列アルゴリズムは、現実的な量子アルゴリズムに変換可能であることを示す。
  論文  参考訳（メタデータ） (2023-02-06T15:14:34Z)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  多くの統計的推論タスクにおいて「統計計算ギャップ」が発生する。 1つの成分が他の成分よりもわずかに大きいランダムオーダー3分解モデルを考える。 テンソルエントリは$ll n3/2$のとき最大成分を正確に推定できるが、$rgg n3/2$のとき失敗する。
  論文  参考訳（メタデータ） (2022-11-10T00:40:37Z)
• 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 Law of Robustness beyond Isoperimetry [84.33752026418045]
  我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。 次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。 我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
  論文  参考訳（メタデータ） (2022-02-23T16:10:23Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• Inferring Hidden Structures in Random Graphs [13.031167737538881]
  本研究では,ランダムなグラフ上に植えられた群集群集の検出と復元の2つの推論問題について検討する。 我々は、パラメータ $(n,k,q)$ や $Gamma_k$ の特定の性質の観点から、構造を検出・復元するための下限を導出し、これらの下限を達成するための計算学的に最適なアルゴリズムを示す。
  論文  参考訳（メタデータ） (2021-10-05T09:39:51Z)
• Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
  我々は、マッサート(有界)ノイズの存在下でPAC学習のハーフスペースの複雑さを研究します。 情報理論上最適なエラーとSQアルゴリズムで達成できる最高のエラーとの間に指数関数的なギャップがあることを示した。
  論文  参考訳（メタデータ） (2020-12-17T16:43:11Z)
• Symmetries, graph properties, and quantum speedups [3.4253416336476246]
  隣接行列モデルにおけるハイパーグラフ対称性は、少なくともランダム化と量子クエリの複雑さを分離することができることを示す。 また、これらの対称性から構築された置換群は、本質的に超ポリノミカル量子スピードアップを防ぐ唯一の置換群であることも示している。
  論文  参考訳（メタデータ） (2020-06-23T05:00:15Z)
• How symmetric is too symmetric for large quantum speedups? [0.0]
  我々は、グループアクションの理解に向けて、$G$を"量子不寛容"とするステップを立てる。 いくつかの自然変換によって保存される群作用の「十分にシャッフルする」性質は、量子スピードアップを許さないことを示す。 これは、グラフ特性試験の問題は超多項式量子スピードアップを持たないことを意味する。
  論文  参考訳（メタデータ） (2020-01-27T09:34:01Z)

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

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