論文の概要: Symmetry and Quantum Query-to-Communication Simulation
- arxiv url: http://arxiv.org/abs/2012.05233v1
- Date: Wed, 9 Dec 2020 18:58:55 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-21 07:56:59.734649
- Title: Symmetry and Quantum Query-to-Communication Simulation
- Title（参考訳）: 対称性と量子クエリー通信シミュレーション
- Authors: Sourav Chakraborty, Arkadev Chattopadhyay, Peter H{\o}yer, Nikhil S.
Mande, Manaswi Paraashar, Ronald de Wolf
- Abstract要約: 合成関数 f o G の有界エラー量子通信複雑性は O(Q(f) log n と等しい、ただし Q(f) は f の有界エラー量子通信複雑性を表す。
これは古典的な設定とは対照的で、Rcc(f o G) 2 R(f) は Rcc と Rcc がそれぞれ有界エラー通信とクエリ複雑性を表すことを示すのが簡単である。
- 参考スコア（独自算出の注目度）: 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 in
contrast with the classical setting, where it is easy to show that R^{cc}(f o
G) < 2 R(f), where R^{cc} and R denote bounded-error communication and query
complexity, respectively. Chakraborty et al. (CCC'20) exhibited a total
function for which the log n overhead in the BCW simulation is required. We
improve upon their result in several ways.
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). This upper bound assumes a shared entangled
state, though for most symmetric functions the assumed number of entangled
qubits is less than the communication and hence could be part of the
communication. To prove this, 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, one may ask whether the log n overhead in the
BCW simulation can be avoided even when f is transitive. 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, even if the parties are allowed to share an arbitrary
prior entangled state for free.
- 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) と等しいことを示した。
これは古典的な設定とは対照的であり、R^{cc}(f o G) < 2 R(f) であり、R^{cc} と R はそれぞれ有界エラー通信とクエリ複雑性を表す。
Chakraborty et al. (CCC'20) は、BCWシミュレーションにおけるlog nのオーバーヘッドを必要とする全関数を示した。
私たちはその結果をいくつかの方法で改善します。
f が対称である場合、log n のオーバーヘッドは不要であり、aaronson と ambainis の結果を集合分離関数(コンピューティング理論'05)に一般化する。
この上限は共有絡み状態(英語版)を仮定するが、ほとんどの対称函数では、想定される絡み合った量子ビットの数は通信よりも小さく、したがって通信の一部となる。
これを証明するために、f が OR 関数であるときに結果を証明できる雑音振幅増幅の効率的な分散バージョンを設計する。
最初の結果から、bcwシミュレーションにおけるlog nのオーバーヘッドはfが推移的であっても回避できるかどうかを問うことができる。
量子通信プロトコルが任意に1/2に近い誤差確率を許容しても、ある推移関数に対して、ログ n のオーバーヘッドが依然として必要であることを示すことで、強い負の答えを与える。
また, 任意の事前絡み合った状態を自由に共有することが許された場合でも, 境界付きエラー通信モデルにおけるBCWシミュレーションにおいて, ログ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) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。