Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA direct product theorem for quantum communication complexity with applications to device-independent QKD
154
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic 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$. As an application of our result, we show that it is possible to do device-independent quantum key distribution (DIQKD) without the assumption that devices do not leak any information after inputs are provided to them. We analyze the DIQKD protocol given by Jain, Miller and Shi (2017), 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. Our security proof is parallel, i.e., the honest parties can enter all their inputs into their devices at once, and works for a leakage model that is arbitrarily interactive, i.e., the devices of the honest parties Alice and Bob can exchange information with each other and with the eavesdropper Eve in any number of rounds, as long as the total number of bits or qubits communicated is bounded.
rate research
Read More
Device-independent not only represents a relaxation of the security assumptions about the internal working of the quantum devices, but also can enhance the security of the quantum communication. In the paper, we put forward the first device-independent quantum secure direct communication (DI-QSDC) protocol, where no assumptions are made about the way the devices work or on what quantum system they operate. We show that in the absence of noise, the DI-QSDC protocol is absolutely secure and there is no limitation for the communication distance. However, under practical noisy quantum channel condition, the photon transmission loss and photon state decoherence would reduce the communication quality and threaten its absolute security. For solving the photon transmission loss and decoherence problems, we adopt noiseless linear amplification (NLA) protocol and entanglement purification protocol (EPP) to modify the DI-QSDC protocol. With the help of the NLA and EPP, we can guarantee the absolute security of the DI-QSDC and effectively improve its communication quality.
Quantum secure direct communication (QSDC) is the technology to transmit secret information directly through a quantum channel without neither key nor ciphertext. It provides us with a secure communication structure that is fundamentally different from the one that we use today. In this Letter, we report the first measurement-device-independent(MDI) QSDC protocol with sequences of entangled photon pairs and single photons. It eliminates security loopholes associated with the measurement device. In addition, the MDI technique doubles the communication distance compared to those without using the technique. We also give a protocol with linear optical Bell-basis measurement, where only two of the four Bell-basis states could be measured. When the number of qubit in a sequence reduces to 1, the MDI-QSDC protocol reduces to a deterministic MDI quantum key distribution protocol, which is also presented in the Letter.
We give a new version of the adversary method for proving lower bounds on quantum query algorithms. The new method is based on analyzing the eigenspace structure of the problem at hand. We use it to prove a new and optimal strong direct product theorem for 2-sided error quantum algorithms computing k independent instances of a symmetric Boolean function: if the algorithm uses significantly less than k times the number of queries needed for one instance of the function, then its success probability is exponentially small in k. We also use the polynomial method to prove a direct product theorem for 1-sided error algorithms for k threshold functions with a stronger bound on the success probability. Finally, we present a quantum algorithm for evaluating solutions to systems of linear inequalities, and use our direct product theorems to show that the time-space tradeoff of this algorithm is close to optimal.
We prove a direct product theorem for the one-way entanglement-assisted quantum communication complexity of a general relation $fsubseteqmathcal{X}timesmathcal{Y}timesmathcal{Z}$. For any $varepsilon, zeta > 0$ and any $kgeq1$, we show that [ mathrm{Q}^1_{1-(1-varepsilon)^{Omega(zeta^6k/log|mathcal{Z}|)}}(f^k) = Omegaleft(kleft(zeta^5cdotmathrm{Q}^1_{varepsilon + 12zeta}(f) - loglog(1/zeta)right)right),] where $mathrm{Q}^1_{varepsilon}(f)$ represents the one-way entanglement-assisted quantum communication complexity of $f$ with worst-case error $varepsilon$ and $f^k$ denotes $k$ parallel instances of $f$. As far as we are aware, this is the first direct product theorem for quantum communication. Our techniques are inspired by the parallel repetition theorems for the entangled value of two-player non-local games, under product distributions due to Jain, Pereszl{e}nyi and Yao, and under anchored distributions due to Bavarian, Vidick and Yuen, as well as message-compression for quantum protocols due to Jain, Radhakrishnan and Sen. Our techniques also work for entangled non-local games which have input distributions anchored on any one side. In particular, we show that for any game $G = (q, mathcal{X}timesmathcal{Y}, mathcal{A}timesmathcal{B}, mathsf{V})$ where $q$ is a distribution on $mathcal{X}timesmathcal{Y}$ anchored on any one side with anchoring probability $zeta$, then [ omega^*(G^k) = left(1 - (1-omega^*(G))^5right)^{Omegaleft(frac{zeta^2 k}{log(|mathcal{A}|cdot|mathcal{B}|)}right)}] where $omega^*(G)$ represents the entangled value of the game $G$. This is a generalization of the result of Bavarian, Vidick and Yuen, who proved a parallel repetition theorem for games anchored on both sides, and potentially a simplification of their proof.
We study a new type of separation between quantum and classical communication complexity which is obtained using quantum protocols where all parties are efficient, in the sense that they can be implemented by small quantum circuits with oracle access to their inputs. More precisely, we give an explicit partial Boolean function that can be computed in the quantum-simultaneous-with-entanglement model of communication, however, every interactive randomized protocol is of exponentially larger cost. Furthermore, all the parties in the quantum protocol can be implemented by quantum circuits of small size with blackbox access to the inputs. Our result qualitatively matches the strongest known separation between quantum and classical communication complexity and is obtained using a quantum protocol where all parties are efficient.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
