論文の概要: The Role of Symmetry in Quantum Query-to-Communication Simulation
- arxiv url: http://arxiv.org/abs/2012.05233v2
- Date: Tue, 25 Apr 2023 18:10:43 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-27 18:53:47.327741
- Title: The Role of Symmetry in Quantum Query-to-Communication Simulation
- Title(参考訳): 量子クエリー通信シミュレーションにおける対称性の役割
- Authors: Sourav Chakraborty, Arkadev Chattopadhyay, Peter H{\o}yer, Nikhil S.
Mande, Manaswi Paraashar, Ronald de Wolf
- Abstract要約: 量子設定におけるO(log n)オーバーヘッドはいくつかの関数に対して必要であり、したがってBCWシミュレーションは厳密であることを示す。
また、BCWシミュレーションでは、ログnのオーバーヘッドが要求される関数を構成するための一般的なレシピも提供する。
- 参考スコア(独自算出の注目度): 3.517404936232172
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Buhrman, Cleve and Wigderson (STOC'98) showed that for every Boolean function
f : {-1,1}^n to {-1,1} and G in {AND_2, XOR_2}, the bounded-error quantum
communication complexity of the composed function f o G equals O(Q(f) log n),
where Q(f) denotes the bounded-error quantum query complexity of f. This is
achieved by Alice running the optimal quantum query algorithm for f, using a
round of O(log n) qubits of communication to implement each query.
This is in contrast with the classical setting, where it is easy to show that
R^{cc}(f o G) is at most 2R(f), where R^{cc} and R denote bounded-error
communication and query complexity, respectively. We show that the O(log n)
overhead is required for some functions in the quantum setting, and thus the
BCW simulation is tight. We note here that prior to our work, the possibility
of Q^{cc}(f o G) = O(Q(f)), for all f and all G in {AND_2, XOR_2}, had not been
ruled out. More specifically, we show the following.
- We show that the log n overhead is *not* required when f is symmetric,
generalizing a result of Aaronson and Ambainis for the Set-Disjointness
function (Theory of Computing'05).
- In order to prove the above, we design an efficient distributed version of
noisy amplitude amplification that allows us to prove the result when f is the
OR function.
- In view of our first result above, one may ask whether the log n overhead
in the BCW simulation can be avoided even when f is transitive, which is a
weaker notion of symmetry. We give a strong negative answer by showing that the
log n overhead is still necessary for some transitive functions even when we
allow the quantum communication protocol an error probability that can be
arbitrarily close to 1/2.
- We also give, among other things, a general recipe to construct functions
for which the log n overhead is required in the BCW simulation in the
bounded-error communication model.
- Abstract(参考訳): Buhrman, Cleve and Wigderson (STOC'98) は、すべてのブール関数 f : {-1,1}^n to {-1,1} と G in {AND_2, XOR_2} に対して、合成関数 f o G の有界エラー量子通信複雑性は O(Q(f) log n) と等しいことを示した。
これは、Alice が f に対して最適な量子クエリアルゴリズムを実行し、各クエリを実装するために、O(log n) qubit の丸い通信を用いて実現している。
これは古典的な設定とは対照的であり、R^{cc}(f o G) が少なくとも 2R(f) であることは容易に示され、R^{cc} と R はそれぞれ有界エラー通信とクエリ複雑性を表す。
量子設定におけるO(log n)オーバーヘッドはいくつかの関数に対して必要であり、したがってBCWシミュレーションは厳密であることを示す。
ここでは、我々の研究に先立ち、すべての f に対して Q^{cc}(f o G) = O(Q(f)) の可能性と {AND_2, XOR_2} におけるすべての G が除外されていないことに注意する。
より具体的には、以下に示す。
- 対数 n のオーバーヘッドは、f が対称であるときに *not* が要求されることを示し、Aaronson と Ambainis の結果を集合交叉関数に対して一般化する(Theory of Computing'05)。
-上記のことを証明するため、fがor関数であるときに結果を証明できる雑音振幅増幅の効率的な分散バージョンを設計。
- 上記の最初の結果から、BCWシミュレーションにおける対数 n のオーバーヘッドは、f が推移的であっても回避できるかどうかを問うことができるが、これは対称性の弱い概念である。
量子通信プロトコルが任意に1/2に近い誤差確率を許容しても、ある推移関数に対して、ログ n のオーバーヘッドが依然として必要であることを示すことで、強い負の答えを与える。
また、bcwシミュレーションにおいて、有界エラー通信モデルにおいて、log n のオーバーヘッドを必要とする関数を構築するための一般的なレシピも提供します。
関連論文リスト
- The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳(メタデータ) (2024-02-29T01:35:46Z) - Taming Quantum Time Complexity [50.10645865330582]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳(メタデータ) (2023-11-27T14:45:19Z) - Unbounded Quantum Advantage in One-Way Strong Communication Complexity
of a Distributed Clique Labelling Relation [0.19090202146054183]
分散クリフラベル問題により誘導される関係のクラスに対する一方向ゼロエラー古典的および量子的通信複雑性について検討する。
ここでは、プレイヤーがリソースを共有しない場合に考慮された特定の関係のクラスについて、任意のグラフに対してCCRタスクに量子的優位性はないことを示す。
我々は、このタスクの半デバイス非依存のディメンション目撃への応用と、ミューチュアルアンバイアスベースの検出について強調する。
論文 参考訳(メタデータ) (2023-05-17T16:58:05Z) - 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) - The power of qutrits for non-adaptive measurement-based quantum
computing [0.0]
量子相関は、一般化された四重項グリーンベルガー・ホーネ・ザイリンガー状態(GHZ)を資源とし、最低でも3n-1$の四重項関数の計算を可能にすることを証明している。
これにより、LHVが計算できない任意の三次函数に対して対応する一般化されたGHZ型パラドックスが得られる。
論文 参考訳(メタデータ) (2022-03-23T13:41:22Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳(メタデータ) (2022-01-31T22:19:49Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳(メタデータ) (2021-11-29T19:26:28Z) - Random quantum circuits anti-concentrate in log depth [118.18170052022323]
本研究では,典型的な回路インスタンスにおける測定結果の分布に要するゲート数について検討する。
我々の反集中の定義は、予測衝突確率が分布が均一である場合よりも大きい定数因子に過ぎないということである。
ゲートが1D環上で最寄りである場合と、ゲートが長距離である場合の両方において、$O(n log(n))ゲートも十分であることを示す。
論文 参考訳(メタデータ) (2020-11-24T18:44:57Z) - Exponential quantum communication reductions from generalizations of the
Boolean Hidden Matching problem [0.05076419064097732]
指数的古典量子通信分離を示す一方向モデルにおける最初の通信問題
効率的な通信プロトコルは、$f$の符号度に応じて提示される。
論文 参考訳(メタデータ) (2020-01-15T21:05:32Z) - Tight Limits on Nonlocality from Nontrivial Communication Complexity;
a.k.a. Reliable Computation with Asymmetric Gate Noise [19.970633213740363]
ある種の超量子非局所相関の存在が通信複雑性の崩壊を引き起こすことは、長い間知られている。
最大勝利確率が量子値を超える任意の物理理論において、通信複雑性が崩壊することを示す。
我々は、0.91の結果が証明戦略の大規模なクラスで可能な限り最良のものであることを示す。
論文 参考訳(メタデータ) (2018-09-25T22:39:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。