論文の概要: A direct product theorem for quantum communication complexity with
applications to device-independent cryptography
- arxiv url: http://arxiv.org/abs/2106.04299v3
- Date: Fri, 20 Jan 2023 19:13:30 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-27 06:36:53.615830
- Title: A direct product theorem for quantum communication complexity with
applications to device-independent cryptography
- Title（参考訳）: 量子通信複雑性の直接積定理とデバイス非依存暗号への応用
- Authors: Rahul Jain, Srijita Kundu
- Abstract要約: 我々は、$l$プレーヤの入力集合にまたがる分布である$p$に対して、任意の絡み合い支援量子通信プロトコルの成功確率は、$n$で指数関数的に低下することを示した。
また、デバイスが情報を漏らさないという仮定なしに、デバイス非依存(DI)量子暗号が可能であることも示している。
- 参考スコア（独自算出の注目度）: 6.891238879512672
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We give a direct product theorem for the entanglement-assisted interactive
quantum communication complexity of an $l$-player predicate $\mathsf{V}$. In
particular we show that for a distribution $p$ that is product across the input
sets of the $l$ players, the success probability of any entanglement-assisted
quantum communication protocol for computing $n$ copies of $\mathsf{V}$, whose
communication is $o(\log(\mathrm{eff}^*(\mathsf{V},p))\cdot n)$, goes down
exponentially in $n$. Here $\mathrm{eff}^*(\mathsf{V}, p)$ is a distributional
version of the quantum efficiency or partition bound introduced by Laplante,
Lerays and Roland (2014), which is a lower bound on the distributional quantum
communication complexity of computing a single copy of $\mathsf{V}$ with
respect to $p$.
Applying our direct product theorem for small communication and techniques
related to $\mathrm{eff}^*$, we show that it is possible to do
device-independent (DI) quantum cryptography without the assumption that
devices do not leak any information. First, we analyze the parallel DI quantum
key distribution protocol given by Jain, Miller and Shi (2020), and show that
when the protocol is carried out with devices that are compatible with $n$
copies of the Magic Square game, it is possible to extract $\Omega(n)$ bits of
key from it, even in the presence of $O(n)$ bits of leakage. Second, we show
that it is possible to do sequential versions of the Jain, Miller and Shi
protocol, which give a better key rate for QKD with leakage, and let us do
sequential DI randomness expansion with leakage (it is not known how to do
parallel DI randomness expansion even without leakage). Third, we show that
proofs of quantumness with two entangled provers are resistant to leakage,
i.e., classical players who communicate $O(n)$ bits with each other cannot
convince the verifier that they share entanglement.
- Abstract（参考訳）: 我々は、$l$-player 述語 $\mathsf{V}$ の絡み合い支援型対話型量子通信複雑性に対する直積定理を与える。
特に、$l$ プレーヤーの入力セットにまたがる分散 $p$ に対して、$o(\log(\mathrm{eff}^*(\mathsf{v},p))\cdot n)$ という$n$ を計算するためのエンタングル支援量子通信プロトコルの成功確率は、$n$ で指数関数的に低下する。
ここで、$\mathrm{eff}^*(\mathsf{v}, p)$ は laplante, lerays and roland (2014) によって導入された量子効率あるいは分割境界の分散バージョンであり、$p$ に関して$\mathsf{v}$ の1つのコピーを計算する際の分布的量子通信の複雑さに対する下界である。
小型通信のための直接積定理と$\mathrm{eff}^*$に関連する技術を適用することで、デバイスが情報を漏らさないという仮定なしにデバイスに依存しない(di)量子暗号を実行できることを示した。
まず、jain、miller、shi(2020)によって与えられた並列di量子鍵分散プロトコルを分析し、マジックスクエアゲームのn$コピーと互換性のあるデバイスでプロトコルを実行すると、o(n)$のリークがある場合でも、それから$\omega(n)$の鍵を抽出することができることを示した。
第2に、リークを伴うQKDのキーレートが向上するJain、Miller、Shiプロトコルのシーケンシャルバージョンを実行できることを示し、リークを伴うシーケンシャルなDIランダム性拡張を行わせることができる(リークのないDIランダム性拡張を並列に行う方法は不明である)。
第三に、2つの絡み合ったプロバーを持つ量子性証明は漏洩に抵抗する、すなわち、o(n)$ビットを互いに通信する古典的なプレイヤーは、絡み合いを共有することを検証者に納得させることができない。
関連論文リスト
- Linear gate bounds against natural functions for position-verification [0.0]
量子位置検証スキームは、証明者の空間的位置を検証しようとする。
我々は、$f$-routing(英語版)と$f$-BB84(英語版)として知られる2つのよく研究された位置検証スキームを考える。
論文 参考訳（メタデータ） (2024-02-28T19:00:10Z) - One Clean Qubit Suffices for Quantum Communication Advantage [3.729242965449096]
1つの量子ビットが純粋な状態にあり、他の全ての量子ビットが最大混合される量子通信の1つのクリーン量子ビットモデルについて検討する。
我々の証明は、Ellis, Kindler, Lifshitz, Minzerが最近導入した超収縮性不等式に基づいている。
論文 参考訳（メタデータ） (2023-10-03T19:58:08Z) - On sampling determinantal and Pfaffian point processes on a quantum
computer [49.1574468325115]
DPPは1970年代の量子光学のモデルとしてマッキによって導入された。
ほとんどのアプリケーションはDPPからのサンプリングを必要としており、その量子起源を考えると、古典的なコンピュータでDPPをサンプリングするのは古典的なものよりも簡単かどうか疑問に思うのが自然である。
バニラサンプリングは、各コスト$mathcalO(N3)$と$mathcalO(Nr2)$の2つのステップから構成される。
論文 参考訳（メタデータ） (2023-05-25T08:43:11Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - 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) - Distributed quantum inner product estimation [14.222887950206658]
2つの量子コンピュータ上で準備された状態の忠実度を推定することを目的とした、クロスプラットフォーム検証として知られるベンチマークタスクが提案されている。
ハードウェアの制約により、2つの物理プラットフォーム間で量子通信を行うことはできない。
サンプルの複雑さは、最強の設定でも少なくとも$Omega(max1/varepsilon2,sqrtd/varepsilon)$でなければならない。
論文 参考訳（メタデータ） (2021-11-05T05:35:03Z) - Matrix Discrepancy from Quantum Communication [13.782852293291494]
我々は,不一致の最小化と(量子)通信複雑性の新たな関連性を開発する。
対称$n times n$$A_1,ldots,A_n$ with $|A_i| leq 1$ and $|A_i|_F leq n1/4$ に対し、pm 1n において $sum_i leq n x_i A_i$ の最大固有値が最大となる符号 $x が存在することを示す。
論文 参考訳（メタデータ） (2021-10-19T16:51:11Z) - Quantum double aspects of surface code models [77.34726150561087]
基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。
有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
論文 参考訳（メタデータ） (2021-06-25T17:03:38Z) - Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
計算・比較プログラム(Computer-and-compare program)として知られる回避関数のクラスに対する量子コピー保護スキームを導入する。
我々は,量子乱数オラクルモデル(QROM)において,完全悪意のある敵に対する非自明なセキュリティを実現することを証明した。
補完的な結果として、「セキュアソフトウェアリース」という,ソフトウェア保護の概念の弱さが示される。
論文 参考訳（メタデータ） (2020-09-29T08:41:53Z) - Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。
我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文 参考訳（メタデータ） (2020-02-18T16:14:55Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。