論文の概要: 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) によるオープンな質問を解決する。
関連論文リスト
- Quantum communication complexity of linear regression [0.05076419064097732]
量子コンピュータは、いくつかの基本的な線形代数問題に対する通信の観点から、証明可能かつ指数関数的なスピードアップを持つことを示す。
本稿では,量子特異値変換のための効率的な量子プロトコルを提案する。
論文 参考訳(メタデータ) (2022-10-04T13:27:01Z) - Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
我々は、トポロジカルデータ解析のための改良された量子アルゴリズムを解析し、最適化する。
超二次量子スピードアップは乗法誤差近似をターゲットとする場合にのみ可能であることを示す。
数百億のトフォリを持つ量子回路は、古典的に難解なインスタンスを解くことができると我々は主張する。
論文 参考訳(メタデータ) (2022-09-27T17:56:15Z) - Topological Quantum Computation on Supersymmetric Spin Chains [0.0]
ブレイド群要素で構築された量子ゲートは、トポロジカル量子計算の構成要素を形成する。
我々は、正則系の融合空間が、ある種のニコライ様超対称スピン鎖の積状態ゼロモードに正確にマッピング可能であることを示す。
論文 参考訳(メタデータ) (2022-09-08T13:52:10Z) - Tight Exponential Analysis for Smoothing the Max-Relative Entropy and
for Quantum Privacy Amplification [56.61325554836984]
最大相対エントロピーとその滑らかなバージョンは、量子情報理論の基本的な道具である。
我々は、精製された距離に基づいて最大相対エントロピーを滑らかにする量子状態の小さな変化の崩壊の正確な指数を導出する。
論文 参考訳(メタデータ) (2021-11-01T16:35:41Z) - Quantum squeezing and sensing with pseudo anti-parity-time symmetry [0.0]
本研究では,Langevinノイズを伴わない2モードボゾン系において,量子擬似反mathcalPT$対称性を構築する。
自発的擬似$mathcalAPT$対称性の破れが例外点となることを示す。
例外点付近のスクイーズ因子と量子力学のこのような劇的な変化は、超精密量子センシングに利用される。
論文 参考訳(メタデータ) (2021-08-29T16:28:28Z) - Information retrieval and eigenstates coalescence in a non-Hermitian
quantum system with anti-$\mathcal{PT}$ symmetry [15.273168396747495]
パリティ時逆数(mathcalPT$)や反$mathcalPT$対称性を持つ非エルミート系は、その特異な性質と反直観的現象により、幅広い関心を集めている。
単一トラップイオンの散逸量子系を周期的に駆動することにより、反$mathcalPT$対称性を持つ単一量子ビットのフロケハミルトニアンを実装する。
論文 参考訳(メタデータ) (2021-07-27T07:11:32Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。