論文の概要: Communication Complexity of Private Simultaneous Quantum Messages
Protocols
- arxiv url: http://arxiv.org/abs/2105.07120v1
- Date: Sat, 15 May 2021 03:08:01 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-31 02:03:42.965724
- Title: Communication Complexity of Private Simultaneous Quantum Messages
Protocols
- Title（参考訳）: プライベート同時量子メッセージプロトコルの通信複雑性
- Authors: Akinori Kawachi and Harumichi Nishimura
- Abstract要約: 本稿では、量子通信の利点と、プライベート同時量子メッセージモデルの事前絡み合いについて検討する。
プライバシ条件は,PSQMモデルの通信コストを必然的に増大させることを示す。
また,共有絡み合った状態と共有ランダム文字列を持つPSQMプロトコルの通信複雑性の指数的差を示す。
- 参考スコア（独自算出の注目度）: 0.609170287691728
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The private simultaneous messages model is a non-interactive version of the
multiparty secure computation, which has been intensively studied to examine
the communication cost of the secure computation. We consider its quantum
counterpart, the private simultaneous quantum messages (PSQM) model, and
examine the advantages of quantum communication and prior entanglement of this
model. In the PSQM model, $k$ parties $P_1,\ldots,P_k$ initially share a common
random string (or entangled states in a stronger setting), and they have
private classical inputs $x_1,\ldots, x_k$. Every $P_i$ generates a quantum
message from the private input $x_i$ and the shared random string (entangled
states), and then sends it to the referee $R$. Receiving the messages, $R$
computes $F(x_1,\ldots,x_k)$. Then, $R$ learns nothing except for
$F(x_1,\ldots,x_k)$ as the privacy condition. We obtain the following results
for this PSQM model. (1) We demonstrate that the privacy condition inevitably
increases the communication cost in the two-party PSQM model as well as in the
classical case presented by Applebaum, Holenstein, Mishra, and Shayevitz. In
particular, we prove a lower bound $(3-o(1))n$ of the communication complexity
in PSQM protocols with a shared random string for random Boolean functions of
$2n$-bit input, which is larger than the trivial upper bound $2n$ of the
communication complexity without the privacy condition. (2) We demonstrate a
factor two gap between the communication complexity of PSQM protocols with
shared entangled states and with shared random strings by designing a
multiparty PSQM protocol with shared entangled states for a total function that
extends the two-party equality function. (3) We demonstrate an exponential gap
between the communication complexity of PSQM protocols with shared entangled
states and with shared random strings for a two-party partial function.
- Abstract（参考訳）: プライベート同時メッセージモデルはマルチパーティセキュアな計算の非インタラクティブバージョンであり、セキュアな計算の通信コストを調べるために集中的に研究されている。
量子通信の利点と事前の絡み合いを考察し,その量子対するプライベート同時量子メッセージ(PSQM)モデルについて考察する。
PSQMモデルでは、$k$party $P_1,\ldots,P_k$は、最初は共通のランダム文字列(あるいは強い設定で絡み合った状態)を共有し、プライベートな古典的な入力は$x_1,\ldots, x_k$である。
各$p_i$ はプライベート入力 $x_i$ と共有ランダム文字列 (絡み合った状態) から量子メッセージを生成し、それをレファレンス $r$ に送る。
メッセージを受け取ると、$R$は$F(x_1,\ldots,x_k)$を計算します。
そして、$R$はプライバシー条件として$F(x_1,\ldots,x_k)$以外何も学習しない。
このPSQMモデルについて,以下の結果を得た。
1) プライバシ条件は,Applebaum, Holenstein, Mishra, Shayevitz が提示した古典的事例と同様に,PSQMモデルの通信コストを必然的に増大させることを示した。
特に、PSQMプロトコルにおける通信複雑性の低い$(3-o(1))n$を、プライバシー条件のない通信複雑性の自明な上限2n$よりも大きい2n$-bit入力のランダムブール関数に対して共有ランダム文字列で証明する。
2) 共有絡み状態を持つPSQMプロトコルと、共有絡み状態を持つマルチパーティPSQMプロトコルとの通信複雑性のギャップを2つのパーティ平等関数を拡張する総関数に対して示す。
(3)PSQMプロトコルの共有絡み合い状態と2つの部分関数に対する共有ランダム文字列との通信複雑性の指数的ギャップを示す。
関連論文リスト
- Rank lower bounds on non-local quantum computation [0.0]
非局所量子計算(NLQC)は、2つの量子システム間の相互作用を1ラウンドの通信と共有絡みによって置き換える。
NLQCの2つのクラス、$f$-routingと$f$-BB84を研究し、これは古典的な情報理論の暗号と量子位置の検証に関係している。
論文 参考訳（メタデータ） (2024-02-28T19:00:09Z) - Relating non-local quantum computation to information theoretic cryptography [0.0]
非局所量子計算(NLQC)は位置検証スキームの不正な方法であり、AdS/CFT対応の文脈に現れている。
我々は、NLQCの特別な場合として、$f$-routing(英語版)と呼ばれ、シークレットプリミティブの条件開示の量子アナログと等価であることを示す。
これらの暗号プリミティブに位置検証を関連付けることで、暗号文学における多くの結果がNLQCに新しい意味を与える。
論文 参考訳（メタデータ） (2023-06-28T18:00:05Z) - Cooperative Multi-Agent Reinforcement Learning: Asynchronous
Communication and Linear Function Approximation [77.09836892653176]
マルコフ決定過程の設定におけるマルチエージェント強化学習について検討した。
本稿では非同期通信が可能な値に基づく証明可能な効率的なアルゴリズムを提案する。
我々は、コラボレーションによってパフォーマンスを改善するために、最小の$Omega(dM)$通信の複雑さが必要であることを示す。
論文 参考訳（メタデータ） (2023-05-10T20:29:29Z) - Communication complexity of entanglement assisted multi-party
computation [11.820804392113294]
プレーヤが2ドル、ドットが2ドル、n$が1に適切な情報を伝達する必要がある場合、プレーヤが$n$のマルチパーティ計算問題を考える。
量子プロトコル(複雑性$(n-1)log n$ bits)と古典的プロトコル(複雑性$(n-1)2(log n2$)ビット)を示す。
これは、我々の量子プロトコルが古典的プロトコルよりも厳密に優れていることを示している。
論文 参考訳（メタデータ） (2023-05-08T03:10:08Z) - Secure Computation with Shared EPR Pairs (Or: How to Teleport in
Zero-Knowledge) [26.90896904213257]
量子チャネルによるセキュアなテレポーテーションが可能であることを示す。
具体的には、量子演算の$Q$の説明を考えると、(量子)入力$rho$の送信者は単一の古典的メッセージを送り、$Q(rho)$を受信機に安全に送信することができる。
論文 参考訳（メタデータ） (2023-04-20T17:29:26Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
古典的アリス(Alice)と量子的ボブ(Quantum Bob)が古典的なチャネルを通してのみ通信できるような設定を考える。
悪質な量子逆数の場合,ブラックボックスシミュレーションを用いた2次元量子関数を実現することは,一般に不可能であることを示す。
我々は、QMA関係Rの古典的量子知識(PoQK)プロトコルを入力として、古典的当事者によって検証可能なRのゼロ知識PoQKを出力するコンパイラを提供する。
論文 参考訳（メタデータ） (2020-10-15T17:55:31Z) - Quantum Communication Complexity of Distribution Testing [114.31181206328276]
2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。
目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。
この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
論文 参考訳（メタデータ） (2020-06-26T09:05:58Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z) - Communication Cost of Quantum Processes [49.281159740373326]
分散コンピューティングにおける一般的なシナリオは、リモートコンピュータ上で計算を実行するようサーバに要求するクライアントである。
重要な問題は、所望の計算を指定するのに必要な最小限の通信量を決定することである。
クライアントが選択した量子処理を正確に実行するために、サーバが必要とする(古典的および量子的)通信の総量を分析する。
論文 参考訳（メタデータ） (2020-02-17T08:51:42Z) - Capacity Approaching Coding for Low Noise Interactive Quantum
Communication, Part I: Large Alphabets [15.078027648304115]
ノイズの多いチャネル上での双方向の対話型量子通信を実現する際の問題点を考察する。
$mathrmpoly(n)$ sizeアルファベット上のノイズのないquditチャネルの場合、主な結果は2-theta(nepsilon)$未満の確率で失敗するシミュレーション手法である。
我々は、$sqrtepsilon$項の定数係数まで最適であると推測する。
論文 参考訳（メタデータ） (2020-01-09T02:48:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。