A direct product theorem for quantum communication complexity with applications to device-independent cryptography

• URL: http://arxiv.org/abs/2106.04299v3
• Date: Fri, 20 Jan 2023 19:13:30 GMT
• Title: A direct product theorem for quantum communication complexity with applications to device-independent cryptography
• Authors: Rahul Jain, Srijita Kundu
• Abstract summary: 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 goes down exponentially in $n$. We also show that it is possible to do device-independent (DI) quantum cryptography without the assumption that devices do not leak any information.
• Score: 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.

Related papers

• Linear gate bounds against natural functions for position-verification [0.0]
  A quantum position-verification scheme attempts to verify the spatial location of a prover. We consider two well-studied position-verification schemes known as $f$-routing and $f$-BB84.
  arXiv  Detail & Related papers  (2024-02-28T19:00:10Z)
• One Clean Qubit Suffices for Quantum Communication Advantage [3.729242965449096]
  We study the one-clean-qubit model of quantum communication where one qubit is in a pure state and all other qubits are maximally mixed. Our proof is based on a recent hypercontractivity inequality introduced by Ellis, Kindler, Lifshitz, and Minzer.
  arXiv  Detail & Related papers  (2023-10-03T19:58:08Z)
• On sampling determinantal and Pfaffian point processes on a quantum computer [49.1574468325115]
  DPPs were introduced by Macchi as a model in quantum optics the 1970s. Most applications require sampling from a DPP, and given their quantum origin, it is natural to wonder whether sampling a DPP on a classical computer is easier than on a classical one. Vanilla sampling consists in two steps, of respective costs $mathcalO(N3)$ and $mathcalO(Nr2)$ operations on a classical computer, where $r$ is the rank of the kernel matrix.
  arXiv  Detail & Related papers  (2023-05-25T08:43:11Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• Distributed quantum inner product estimation [14.222887950206658]
  A benchmarking task known as cross-platform verification has been proposed that aims to estimate the fidelity of states prepared on two quantum computers. No quantum communication can be performed between the two physical platforms due to hardware constraints. We show that the sample complexity must be at least $Omega(max1/varepsilon2,sqrtd/varepsilon)$, even in the strongest setting.
  arXiv  Detail & Related papers  (2021-11-05T05:35:03Z)
• Matrix Discrepancy from Quantum Communication [13.782852293291494]
  We develop a novel connection between discrepancy minimization and (quantum) communication complexity. We show that for every collection of symmetric $n times n$ $A_1,ldots,A_n$ with $|A_i| leq 1$ and $|A_i|_F leq n1/4$ there exist signs $x in pm 1n such that the maximum eigenvalue of $sum_i leq n x_i A_i$ is at most
  arXiv  Detail & Related papers  (2021-10-19T16:51:11Z)
• Quantum double aspects of surface code models [77.34726150561087]
  We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry. We show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$.
  arXiv  Detail & Related papers  (2021-06-25T17:03:38Z)
• Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
  We introduce a quantum copy-protection scheme for a class of evasive functions known as " compute-and-compare programs" We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM) As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing"
  arXiv  Detail & Related papers  (2020-09-29T08:41:53Z)
• Quantum Coupon Collector [62.58209964224025]
  We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements. We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
  arXiv  Detail & Related papers  (2020-02-18T16:14:55Z)
• Capacity Approaching Coding for Low Noise Interactive Quantum Communication, Part I: Large Alphabets [15.078027648304115]
  We consider the problem of implementing two-party interactive quantum communication over noisy channels. For a noiseless qudit channel over a $mathrmpoly(n)$ size alphabet, our main result is a simulation method that fails with probability less than $2-Theta(nepsilon)$ We conjecture that it is optimal up to a constant factor in the $sqrtepsilon$ term.
  arXiv  Detail & Related papers  (2020-01-09T02:48:43Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.