論文の概要: How symmetric is too symmetric for large quantum speedups?

• arxiv url: http://arxiv.org/abs/2001.09642v1
• Date: Mon, 27 Jan 2020 09:34:01 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-05 11:51:05.031992
• Title: How symmetric is too symmetric for large quantum speedups?
• Title（参考訳）: 大規模な量子スピードアップには対称性が多すぎるか?
• Authors: Shalev Ben-David and Supartha Podder
• Abstract要約: 我々は、グループアクションの理解に向けて、$G$を"量子不寛容"とするステップを立てる。 いくつかの自然変換によって保存される群作用の「十分にシャッフルする」性質は、量子スピードアップを許さないことを示す。 これは、グラフ特性試験の問題は超多項式量子スピードアップを持たないことを意味する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Suppose a Boolean function $f$ is symmetric under a group action $G$ acting on the $n$ bits of the input. For which $G$ does this mean $f$ does not have an exponential quantum speedup? Is there a characterization of how rich $G$ must be before the function $f$ cannot have enough structure for quantum algorithms to exploit? In this work, we make several steps towards understanding the group actions $G$ which are "quantum intolerant" in this way. We show that sufficiently transitive group actions do not allow a quantum speedup, and that a "well-shuffling" property of group actions -- which happens to be preserved by several natural transformations -- implies a lack of super-polynomial speedups for functions symmetric under the group action. Our techniques are motivated by a recent paper by Chailloux (2018), which deals with the case where $G=S_n$. Our main application is for graph symmetries: we show that any Boolean function $f$ defined on the adjacency matrix of a graph (and symmetric under relabeling the vertices of the graph) has a power $6$ relationship between its randomized and quantum query complexities, even if $f$ is a partial function. In particular, this means no graph property testing problems can have super-polynomial quantum speedups, settling an open problem of Ambainis, Childs, and Liu (2011).
• Abstract（参考訳）: ブール関数 $f$ が群アクション $G$ の下で対称であると仮定すると、入力の$n$ビットに作用する。 これは、$f$ が指数関数的な量子スピードアップを持たないことを意味するのだろうか? 関数 $f$ が量子アルゴリズムを悪用するのに十分な構造を持つことができない前に、どれだけリッチでなければならないのかという特性は存在するか? この研究では、この方法で「量子不寛容」なグループアクション$g$を理解するためのいくつかのステップを行います。 十分に推移的な群作用は量子的スピードアップを許容せず、群作用の「十分にシャッフルする」性質は、群作用の下で対称な函数に対する超多項式的スピードアップが欠如していることを示す。 我々の手法はChailloux (2018) による最近の論文によって動機付けられ、$G=S_n$ の場合を扱う。 グラフの隣接行列上で定義されるブール関数$f$(およびグラフの頂点を緩和する対称)は、f$が部分関数であるとしても、そのランダム化と量子的クエリ複雑度の間のパワー6$の関係を持つことを示す。 特に、これはグラフ特性試験の問題は超ポリノミカルな量子スピードアップを持たず、アンバイニス、チャイルドズ、リュー (2011) のオープンな問題を解決したことを意味する。

関連論文リスト

• A one-query lower bound for unitary synthesis and breaking quantum cryptography [7.705803563459633]
  ユニタリ合成問題では、任意の$n$qubitのユニタリ$U$を、任意のブール関数$f$を計算するオラクルで拡張された効率的な量子$A$で実装できるかどうかを問う。 本研究は, 対向する$Af$の最大成功確率を解析することにより, 下位境界の証明を可能にする, 効率的なチャレンジャーアドゲームとしてのユニタリ合成を証明する。
  論文  参考訳（メタデータ） (2023-10-13T05:39:42Z)
• On the universality of $S_n$-equivariant $k$-body gates [0.0]
  本稿では,QNNジェネレータにおける対称性と$k$-bodynessの相互作用が,その表現性に与える影響について検討する。 我々の結果は、同変QNNの能力と限界をよりよく理解するための一歩を踏み出した。
  論文  参考訳（メタデータ） (2023-03-01T18:42:14Z)
• 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)
• Monogamy of entanglement between cones [68.8204255655161]
  モノガミーは量子論の特徴であるだけでなく、凸錐の一般対の極小テンソル積を特徴づけることを示した。 我々の証明は、アフィン同値まで単純化された生成物の新たな特徴を生かしている。
  論文  参考訳（メタデータ） (2022-06-23T16:23:59Z)
• Beyond the Berry Phase: Extrinsic Geometry of Quantum States [77.34726150561087]
  状態の量子多様体のすべての性質がゲージ不変のバーグマンによって完全に記述されることを示す。 偏光理論への我々の結果の即時適用について述べる。
  論文  参考訳（メタデータ） (2022-05-30T18:01: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)
• Uncertainties in Quantum Measurements: A Quantum Tomography [52.77024349608834]
  量子系 $S$ に関連する可観測物は非可換代数 $mathcal A_S$ を形成する。 密度行列 $rho$ は可観測物の期待値から決定できると仮定される。 アーベル代数は内部自己同型を持たないので、測定装置は可観測物の平均値を決定することができる。
  論文  参考訳（メタデータ） (2021-12-14T16:29:53Z)
• The Parallel Reversible Pebbling Game: Analyzing the Post-Quantum Security of iMHFs [6.305950347749109]
  本稿では,量子コンピューティングにおけるNo-Deletion Theoremによる追加制約を捉える並列可逆ペブブリングゲームを提案する。 我々は、いくつかの重要なグラフの可逆空間時間複雑性を解析するために、新しい可逆ペブブリングゲームを適用した。
  論文  参考訳（メタデータ） (2021-10-08T15:24:31Z)
• Quantum double aspects of surface code models [77.34726150561087]
  基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。 有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
  論文  参考訳（メタデータ） (2021-06-25T17:03:38Z)
• Symmetries, graph properties, and quantum speedups [3.4253416336476246]
  隣接行列モデルにおけるハイパーグラフ対称性は、少なくともランダム化と量子クエリの複雑さを分離することができることを示す。 また、これらの対称性から構築された置換群は、本質的に超ポリノミカル量子スピードアップを防ぐ唯一の置換群であることも示している。
  論文  参考訳（メタデータ） (2020-06-23T05:00:15Z)
• Can graph properties have exponential quantum speedup? [5.101801159418223]
  特に、(部分)グラフの性質に対して指数的スピードアップが可能かどうかを問うのは自然である。 この疑問に対する答えは入力モデルに強く依存していることを示す。
  論文  参考訳（メタデータ） (2020-01-28T18:45:48Z)

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

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