論文の概要: Quantum advantage and lower bounds in parallel query complexity
- arxiv url: http://arxiv.org/abs/2410.02665v1
- Date: Thu, 3 Oct 2024 16:50:00 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-04 01:42:49.674240
- Title: Quantum advantage and lower bounds in parallel query complexity
- Title（参考訳）: 並列クエリ複雑性における量子優位性と低境界
- Authors: Joseph Carolan, Amin Shiraz Gilani, Mahathi Vempati,
- Abstract要約: 本稿では,全関数に対する量子・ランダム化・決定論的(逐次的)問合せ複雑性について検討する。
これらの測度の平行一般化の間には、はるかに大きな分離が可能であることが分かる。
逐次上界から並列量子下界を導出する新しい手法を開発した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: It is well known that quantum, randomized and deterministic (sequential) query complexities are polynomially related for total boolean functions. We find that significantly larger separations between the parallel generalizations of these measures are possible. In particular, (1) We employ the cheatsheet framework to obtain an unbounded parallel quantum query advantage over its randomized analogue for a total function, falsifying a conjecture of Jeffery et al. 2017 (arXiv:1309.6116). (2) We strengthen (1) by constructing a total function which exhibits an unbounded parallel quantum query advantage despite having no sequential advantage, suggesting that genuine quantum advantage could occur entirely due to parallelism. (3) We construct a total function that exhibits a polynomial separation between 2-round quantum and randomized query complexities, contrasting a result of Montanaro in 2010 (arXiv:1001.0018) that there is at most a constant separation for 1-round (nonadaptive) algorithms. (4) We develop a new technique for deriving parallel quantum lower bounds from sequential upper bounds. We employ this technique to give lower bounds for Boolean symmetric functions and read-once formulas, ruling out large parallel query advantages for them. We also provide separations between randomized and deterministic parallel query complexities analogous to items (1)-(3).
- Abstract（参考訳）: 量子的、ランダム化され、決定論的(シークエンシャル)なクエリ複合体が、全体ブール関数に対して多項式的に関連していることはよく知られている。
これらの測度の平行一般化の間には、はるかに大きな分離が可能であることが分かる。
特に,(1) 浮動小数点数に対する非有界な並列量子クエリの優位性を得るために, 1 つの浮動小数点数列を用いて,Jeffery et al 2017 (arXiv:1309.6116) の予想をfalsifyする。
2) 逐次的優位性を持たないにもかかわらず、非有界な並列量子クエリ優位性を示す全関数を構築することにより、(1) 真の量子優位性は、並列性によって完全に生じることを示唆する。
(3) 2010年のモンタナロの結果(arXiv:1001.0018)と対照的に、1ラウンドの(非適応的な)アルゴリズムに対して少なくとも一定の分離が存在する。
(4) 逐次上界から並列量子下界を導出する新しい手法を開発する。
我々はこの手法を用いてブール対称関数と読み取りオンス公式の低い境界を与え、それらに対して大きな並列クエリの利点を除外する。
また、アイテム(1)-(3)に類似したランダム化と決定論的並列クエリ複雑度を分離する。
関連論文リスト
- Taming Quantum Time Complexity [45.867051459785976]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳（メタデータ） (2023-11-27T14:45:19Z) - Quantum Query Complexity of Boolean Functions under Indefinite Causal
Order [0.9208007322096533]
一般高次量子計算におけるブール関数の問合せ複雑性について検討する。
最近導入された因果順序の量子制御を持つ量子回路のクラスは、クエリの複雑さを減らすことは不可能である。
因果不確定なスーパーマップを利用する場合、2つのクエリで計算できる最小誤差が厳密に低い関数がいくつか見つかる。
論文 参考訳（メタデータ） (2023-07-18T13:12:55Z) - Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and
Optimal Algorithms [64.10576998630981]
最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。
ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。
本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
論文 参考訳（メタデータ） (2023-06-21T17:03:22Z) - Decoupling by local random unitaries without simultaneous smoothing, and applications to multi-user quantum information tasks [0.0]
単純なテレスコープ和のトリックは、三角形の不等式とランダムチャネルの予測収縮係数のテンソル化特性とともに、局所的な動作によって複数のユーザに対して一般的な同時疎結合を実現することができることを示す。
我々は、スムーズなミンエントロピーの1ショット設定やR'enyiエントロピーの有限ブロック長設定のいずれにおいても、理想デカップリングから期待される偏差の有界を得る。
これは量子シャノン理論におけるいくつかのタスクに対して、1ショット、有限ブロック長、同時達成性をもたらす。
論文 参考訳（メタデータ） (2023-04-24T14:17:32Z) - An Exponential Separation Between Quantum Query Complexity and the
Polynomial Degree [79.43134049617873]
本稿では,部分関数に対する完全次数と近似量子クエリの指数関数的分離を実証する。
アルファベットのサイズについては、定値対分離の複雑さがある。
論文 参考訳（メタデータ） (2023-01-22T22:08:28Z) - Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。
我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。
任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
論文 参考訳（メタデータ） (2022-03-30T02:02:16Z) - Bounds on quantum evolution complexity via lattice cryptography [0.0]
量子論における可積分運動とカオス運動の差は、対応する進化作用素の複雑さによって表される。
ここでの複雑性は、時間依存進化作用素とユニタリ群内の原点の間の最短測地線距離として理解されている。
論文 参考訳（メタデータ） (2022-02-28T16:20:10Z) - On query complexity measures and their relations for symmetric functions [0.0]
本稿では, ブール法と逆法を用いて, 量子クエリの複雑性を低く抑える方法について述べる。
また、部分対称関数Gap Majorityの量子クエリ複雑性についても考察する。
証明の複雑さとブロック感度が対称関数の感度と比較していかに大きいかを示す。
論文 参考訳（メタデータ） (2021-10-25T02:55:39Z) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
本稿では,最適化問題における短期量子優位性の提案に着想を得た高忠実度ゲートセットを提案する。
3つのトランペット四重項のコヒーレントな多レベル制御を編成することにより、自然な3量子ビット計算ベースで作用する決定論的連続角量子位相ゲートの族を合成する。
論文 参考訳（メタデータ） (2021-08-03T17:49:09Z) - Detailed Account of Complexity for Implementation of Some Gate-Based
Quantum Algorithms [55.41644538483948]
特に、状態準備および読み出しプロセスのような実装のいくつかのステップは、アルゴリズム自体の複雑さの側面を超越することができる。
本稿では、方程式の線形系と微分方程式の線形系を解くための量子アルゴリズムの完全な実装に関わる複雑性について述べる。
論文 参考訳（メタデータ） (2021-06-23T16:33:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。