論文の概要: Symmetries, graph properties, and quantum speedups

• arxiv url: http://arxiv.org/abs/2006.12760v1
• Date: Tue, 23 Jun 2020 05:00:15 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-13 01:00:59.734812
• Title: Symmetries, graph properties, and quantum speedups
• Title（参考訳）: 対称性、グラフ特性、および量子スピードアップ
• Authors: Shalev Ben-David, Andrew M. Childs, Andr\'as Gily\'en, William Kretschmer, Supartha Podder, Daochen Wang
• Abstract要約: 隣接行列モデルにおけるハイパーグラフ対称性は、少なくともランダム化と量子クエリの複雑さを分離することができることを示す。 また、これらの対称性から構築された置換群は、本質的に超ポリノミカル量子スピードアップを防ぐ唯一の置換群であることも示している。
• 参考スコア（独自算出の注目度）: 3.4253416336476246
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Aaronson and Ambainis (2009) and Chailloux (2018) showed that fully symmetric (partial) functions do not admit exponential quantum query speedups. This raises a natural question: how symmetric must a function be before it cannot exhibit a large quantum speedup? In this work, we prove that hypergraph symmetries in the adjacency matrix model allow at most a polynomial separation between randomized and quantum query complexities. We also show that, remarkably, permutation groups constructed out of these symmetries are essentially the only permutation groups that prevent super-polynomial quantum speedups. We prove this by fully characterizing the primitive permutation groups that allow super-polynomial quantum speedups. In contrast, in the adjacency list model for bounded-degree graphs (where graph symmetry is manifested differently), we exhibit a property testing problem that shows an exponential quantum speedup. These results resolve open questions posed by Ambainis, Childs, and Liu (2010) and Montanaro and de Wolf (2013).
• Abstract（参考訳）: aaronson and ambainis (2009) と chailloux (2018) は、完全対称(部分的)関数は指数量子クエリの高速化を認めないことを示した。 これは自然の疑問を提起する: 大きな量子スピードアップが得られない前に、関数はどのくらい対称でなければならないのか? 本研究では,隣接行列モデルにおけるハイパーグラフ対称性により,無作為化と量子クエリの複合性の多項式分離が可能となることを証明した。 また,これらの対称性から構成された置換群は,超多項量子スピードアップを阻害する唯一の置換群であることを示した。 超多項量子スピードアップを可能にする原始置換群を完全に特徴づけることで証明する。 対照的に、有界グラフ(グラフ対称性が異なる形で表される)の隣接リストモデルでは、指数的量子スピードアップを示す特性試験問題を示す。 これらの結果は、Ambainis, Childs, and Liu (2010) と Montanaro and de Wolf (2013) によるオープンな質問を解決する。

関連論文リスト

• Efficient Quantum Pseudorandomness from Hamiltonian Phase States [41.94295877935867]
  我々は、ハミルトニアン相状態(HPS)問題と呼ばれる量子硬度仮定を導入する。 我々は、我々の仮定が少なくとも完全に量子的であることを示し、すなわち片方向関数を構成するのに使用できない。 仮定とその変形により、多くの擬似ランダム量子プリミティブを効率的に構築できることを示す。
  論文  参考訳（メタデータ） (2024-10-10T16:10:10Z)
• Non-equilibrium dynamics of charged dual-unitary circuits [44.99833362998488]
  平衡外量子系における対称性と絡み合いの相互作用は、現在、激しい多分野研究の中心にある。 一般二重ユニタリ回路を拡張した可解状態のクラスを導入することができることを示す。 無限の温度状態に緩和する既知の可解状態のクラスとは対照的に、これらの状態は非自明な一般化されたギブスアンサンブルの族に緩和する。
  論文  参考訳（メタデータ） (2024-07-31T17:57:14Z)
• Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem [55.80819771134007]
  本稿では、離散時間量子ウォークによる溶接木問題に対する最適線形打撃時間の簡単な証明を行う。 同じ手法は他の1次元階層グラフにも適用できる。
  論文  参考訳（メタデータ） (2024-04-30T11:45:49Z)
• Studying Stabilizer de Finetti Theorems and Possible Applications in Quantum Information Processing [0.0]
  量子情報理論において、量子状態がそのサブシステムの置換の下で不変であれば、その限界は1つのサブシステムの状態のパワーの混合によって近似することができる。 近年、置換よりも大きな対称性群に対して同様の観測が可能であることが判明した。 このことは、この対称性が現れるアプリケーションで同様の改善が見つかるかどうかという疑問を自然に提起する。
  論文  参考訳（メタデータ） (2024-03-15T17:55:12Z)
• Quantum communication complexity of linear regression [0.05076419064097732]
  量子コンピュータは、いくつかの基本的な線形代数問題に対する通信の観点から、証明可能かつ指数関数的なスピードアップを持つことを示す。 本稿では,量子特異値変換のための効率的な量子プロトコルを提案する。
  論文  参考訳（メタデータ） (2022-10-04T13:27:01Z)
• Quantum squeezing and sensing with pseudo anti-parity-time symmetry [0.0]
  本研究では,Langevinノイズを伴わない2モードボゾン系において,量子擬似反mathcalPT$対称性を構築する。 自発的擬似$mathcalAPT$対称性の破れが例外点となることを示す。 例外点付近のスクイーズ因子と量子力学のこのような劇的な変化は、超精密量子センシングに利用される。
  論文  参考訳（メタデータ） (2021-08-29T16:28:28Z)
• Graph-Theoretic Framework for Self-Testing in Bell Scenarios [37.067444579637076]
  量子自己検査は、出力統計だけで量子状態と測定を認証するタスクである。 我々はベル非局所性シナリオにおける量子自己テストの新しいアプローチを提案する。
  論文  参考訳（メタデータ） (2021-04-27T08:15:01Z)
• Complete entropic inequalities for quantum Markov chains [17.21921346541951]
  有限次元代数上のすべての GNS-対称量子マルコフ半群が、修正対数ソボレフの不等式を満たすことを証明する。 また、相対エントロピーの最初の一般近似特性を確立する。
  論文  参考訳（メタデータ） (2021-02-08T11:47:37Z)
• On Representing (Anti)Symmetric Functions [19.973896010415977]
  対称の場合の自然な近似と、反対称の場合の単一の一般化 Slater に基づく近似を導出する。 我々は、対称普遍性とフェルミネットの普遍性を意味する同変多層パーセプトロンの完全かつ明示的な証明を提供する。
  論文  参考訳（メタデータ） (2020-07-30T08:23:33Z)
• Can graph properties have exponential quantum speedup? [5.101801159418223]
  特に、(部分)グラフの性質に対して指数的スピードアップが可能かどうかを問うのは自然である。 この疑問に対する答えは入力モデルに強く依存していることを示す。
  論文  参考訳（メタデータ） (2020-01-28T18:45:48Z)
• How symmetric is too symmetric for large quantum speedups? [0.0]
  我々は、グループアクションの理解に向けて、$G$を"量子不寛容"とするステップを立てる。 いくつかの自然変換によって保存される群作用の「十分にシャッフルする」性質は、量子スピードアップを許さないことを示す。 これは、グラフ特性試験の問題は超多項式量子スピードアップを持たないことを意味する。
  論文  参考訳（メタデータ） (2020-01-27T09:34:01Z)

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

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