論文の概要: Exponential quantum communication reductions from generalizations of the
Boolean Hidden Matching problem
- arxiv url: http://arxiv.org/abs/2001.05553v2
- Date: Tue, 17 Aug 2021 08:05:21 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-11 07:07:32.306727
- Title: Exponential quantum communication reductions from generalizations of the
Boolean Hidden Matching problem
- Title（参考訳）: ブール隠れマッチング問題の一般化による指数量子通信の低減
- Authors: Jo\~ao F. Doriguello, Ashley Montanaro
- Abstract要約: 指数的古典量子通信分離を示す一方向モデルにおける最初の通信問題
効率的な通信プロトコルは、$f$の符号度に応じて提示される。
- 参考スコア（独自算出の注目度）: 0.05076419064097732
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: In this work we revisit the Boolean Hidden Matching communication problem,
which was the first communication problem in the one-way model to demonstrate
an exponential classical-quantum communication separation. In this problem,
Alice's bits are matched into pairs according to a partition that Bob holds.
These pairs are compressed using a Parity function and it is promised that the
final bit-string is equal either to another bit-string Bob holds, or its
complement. The problem is to decide which case is the correct one. Here we
generalize the Boolean Hidden Matching problem by replacing the parity function
with an arbitrary Boolean function $f$. Efficient communication protocols are
presented depending on the sign-degree of $f$. If its sign-degree is less than
or equal to 1, we show an efficient classical protocol. If its sign-degree is
less than or equal to $2$, we show an efficient quantum protocol. We then
completely characterize the classical hardness of all symmetric functions $f$
of sign-degree greater than or equal to $2$, except for one family of specific
cases. We also prove, via Fourier analysis, a classical lower bound for any
function $f$ whose pure high degree is greater than or equal to $2$. Similarly,
we prove, also via Fourier analysis, a quantum lower bound for any function $f$
whose pure high degree is greater than or equal to $3$. These results give a
large family of new exponential classical-quantum communication separations.
- Abstract（参考訳）: 本研究では,一方向モデルにおける最初の通信問題であり,指数的古典量子通信分離を示すBoolean Hidden Matching通信問題を再検討する。
この問題では、アリスのビットはボブが持つ分割に従ってペアに一致する。
これらのペアはパリティ関数を用いて圧縮され、最後のビットストリングはボブが持つ他のビットストリングまたはその補数と等しいことが保証される。
問題はどのケースが正しいかを決めることである。
ここではパリティ関数を任意のブール関数$f$に置き換えることでブール隠れマッチング問題を一般化する。
効率的な通信プロトコルは、$f$の符号度に応じて提示される。
符号次数が 1 以下であれば、効率的な古典的プロトコルを示す。
もしその署名度が2ドル以下の場合、効率的な量子プロトコルを示す。
次に、すべての対称関数の古典的硬さを完全に特徴付け、特定のケースの1つのファミリーを除いて、2ドル以上の符号次数をf$とする。
また、フーリエ解析(英語版)により、純高次数が 2$ 以上である任意の函数に対して古典的な下界が$f$であることを示す。
同様に、フーリエ解析(英語版)(Fourier analysis)により、純高次数が 3$ 以上である任意の函数の量子下界が$f$であることを示す。
これらの結果は、新しい指数的古典量子通信分離の族を与える。
関連論文リスト
- Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - A one-query lower bound for unitary synthesis and breaking quantum
cryptography [7.705803563459633]
ユニタリ合成問題では、任意の$n$qubitのユニタリ$U$を、任意のブール関数$f$を計算するオラクルで拡張された効率的な量子$A$で実装できるかどうかを問う。
本研究は, 対向する$Af$の最大成功確率を解析することにより, 下位境界の証明を可能にする, 効率的なチャレンジャーアドゲームとしてのユニタリ合成を証明する。
論文 参考訳（メタデータ） (2023-10-13T05:39:42Z) - One Clean Qubit Suffices for Quantum Communication Advantage [3.729242965449096]
1つの量子ビットが純粋な状態にあり、他の全ての量子ビットが最大混合される量子通信の1つのクリーン量子ビットモデルについて検討する。
我々の証明は、Ellis, Kindler, Lifshitz, Minzerが最近導入した超収縮性不等式に基づいている。
論文 参考訳（メタデータ） (2023-10-03T19:58:08Z) - Approximate degree lower bounds for oracle identification problems [19.001036556917818]
本稿では,特定のオラクル識別問題に対する近似次数下界を証明するためのフレームワークを提案する。
我々の下界は、大域関数と等値関数に対するランダムな通信上界によって駆動される。
論文 参考訳（メタデータ） (2023-03-07T14:30:28Z) - 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) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - On the relation between completely bounded and $(1,cb)$-summing maps
with applications to quantum XOR games [65.51757376525798]
一般作用素空間から C$*$-代数の双対への線型写像が与えられたとき、その完全有界ノルムは、その$(''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
論文 参考訳（メタデータ） (2021-12-09T21:06:52Z) - Tight Bounds for the Randomized and Quantum Communication Complexities
of Equality with Small Error [1.6522364074260811]
誤差が小さいEquality関数のランダム化および量子化通信複雑性を$epsilon$で調べる。
任意の$log(n/epsilon)-log(sqrtn/epsilon)+3$プロトコルが少なくとも$log(n/epsilon)-log(sqrtn/epsilon)-O(1)$ qubitsを通信することを示す。
論文 参考訳（メタデータ） (2021-07-25T13:52:42Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - Lower Bounds for XOR of Forrelations [7.510385608531827]
我々は Forrelation 関数の独立コピー $k$ の XOR について検討する。
また、任意の準ポリノミカルサイズの定数深さ回路が、ランダムな推測に対して準ポリノミカルに小さな優位性を持つことを示す。
論文 参考訳（メタデータ） (2020-07-07T17:05:09Z) - Quantum Communication Complexity of Distribution Testing [114.31181206328276]
2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。
目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。
この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
論文 参考訳（メタデータ） (2020-06-26T09:05:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。