論文の概要: 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 のオーバーヘッドを必要とする関数を構築するための一般的なレシピも提供します。
関連論文リスト
- Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。
提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。
そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
論文 参考訳（メタデータ） (2024-05-14T15:28:37Z) - The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳（メタデータ） (2024-02-29T01:35:46Z) - 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) - Topologically driven no-superposing theorem with a tight error bound [0.0]
量子加法(quantum addition)は、2つの量子状態の重ね合わせである。
我々は、各状態のサンプルがいくつあるとしても、2つの未知の状態が重ね合わさることの不可能さを証明した。
以上の結果から,重ね合わせを量子計算の基本ゲートとして除外した。
論文 参考訳（メタデータ） (2021-11-03T17:57:56Z) - Random quantum circuits anti-concentrate in log depth [118.18170052022323]
本研究では,典型的な回路インスタンスにおける測定結果の分布に要するゲート数について検討する。
我々の反集中の定義は、予測衝突確率が分布が均一である場合よりも大きい定数因子に過ぎないということである。
ゲートが1D環上で最寄りである場合と、ゲートが長距離である場合の両方において、$O(n log(n))ゲートも十分であることを示す。
論文 参考訳（メタデータ） (2020-11-24T18:44:57Z) - Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
NISQとフォールトトレラントの両方の設定で格子シュウィンガーモデルをシミュレートするために、スケーラブルで明示的なデジタル量子アルゴリズムを提供する。
格子単位において、結合定数$x-1/2$と電場カットオフ$x-1/2Lambda$を持つ$N/2$物理サイト上のシュウィンガーモデルを求める。
NISQと耐故障性の両方でコストがかかるオブザーバブルを、単純なオブザーバブルとして推定し、平均ペア密度を推定する。
論文 参考訳（メタデータ） (2020-02-25T19:18:36Z) - Trading T gates for dirty qubits in state preparation and unitary synthesis [0.0]
古典的数のリストで指定された任意の次元-$N$純量子状態を作成するための量子アルゴリズムを提案する。
我々のスキームは、$mathcalO(fracNlambda+lambdalogfracNepsilonlogNepsilon)$を使用して、Tゲートコストを$mathcalO(fracNlambda+lambdalogfracNepsilon)$に削減します。
論文 参考訳（メタデータ） (2018-12-03T18:24:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。