Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Direct Product Theorem for One-Way Quantum Communication
76
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
Let $f: X times Y rightarrow {0,1,bot }$ be a partial function and $mu$ be a distribution with support contained in $f^{-1}(0) cup f^{-1}(1)$. Let $mathsf{D}^{1,mu}_epsilon(f)$ be the classical one-way communication complexity of $f$ with average error under $mu$ at most $epsilon$, $mathsf{Q}^{1,mu}_epsilon(f)$ be the quantum one-way communication complexity of $f$ with average error under $mu$ at most $epsilon$ and $mathsf{Q}^{1,mu, *}_epsilon(f)$ be the entanglement assisted one-way communication complexity of $f$ with average error under $mu$ at most $epsilon$. We show: 1. If $mu$ is a product distribution, then $forall epsilon, eta > 0$, $$mathsf{D}^{1,mu}_{2epsilon + eta}(f) leq mathsf{Q}^{1,mu, *}_{epsilon}(f) /eta+Obigl(log(mathsf{Q}^{1,mu, *}_{epsilon}(f))/etabigr).$$ 2. If $mu$ is a non-product distribution, then $forall epsilon, eta > 0$ such that $epsilon/eta + eta < 0.5$, $$mathsf{D}^{1,mu}_{3eta}(f) = O(mathsf{Q}^{1,mu}_{{epsilon}}(f) cdot mathsf{CS}(f)/eta^4)enspace,$$ where [mathsf{CS}(f) = max_{y} min_{zin{0,1}} { vert {x~|~f(x,y)=z} vert} enspace.]
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.
We study the relationship between various one-way communication complexity measures of a composed function with the analogous decision tree complexity of the outer function. We consider two gadgets: the AND function on 2 inputs, and the Inner Product on a constant number of inputs. Let $IP$ denote Inner Product on $2b$ bits. 1) If $f$ is a total Boolean function that depends on all of its inputs, the bounded-error one-way quantum communication complexity of $f circ IP$ equals $Omega(n(b-1))$. 2) If $f$ is a partial Boolean function, the deterministic one-way communication complexity of $f circ IP$ is at least $Omega(b cdot D_{dt}^{rightarrow}(f))$, where $D_{dt}^{rightarrow}(f)$ denotes the non-adaptive decision tree complexity of $f$. For our quantum lower bound, we show a lower bound on the VC-dimension of $f circ IP$, and then appeal to a result of Klauck [STOC00]. Our deterministic lower bound relies on a combinatorial result due to Frankl and Tokushige [Comb.99]. It is known due to a result of Montanaro and Osborne [arXiv09] that the deterministic one-way communication complexity of $f circ XOR_2$ equals the non-adaptive parity decision tree complexity of $f$. In contrast, we show the following with the gadget $AND_2$. 1) There exists a function for which even the randomized non-adaptive AND decision tree complexity of $f$ is exponentially large in the deterministic one-way communication complexity of $f circ AND_2$. 2) For symmetric functions $f$, the non-adaptive AND decision tree complexity of $f$ is at most quadratic in the (even two-way) communication complexity of $f circ AND_2$. In view of the first point, a lower bound on non-adaptive AND decision tree complexity of $f$ does not lift to a lower bound on one-way communication complexity of $f circ AND_2$. The proof of the first point above uses the well-studied Odd-Max-Bit function.
The classical communication complexity of testing closeness of discrete distributions has recently been studied by Andoni, Malkin and Nosatzki (ICALP19). In this problem, two players each receive $t$ samples from one distribution over $[n]$, and the goal is to decide whether their two distributions are equal, or are $epsilon$-far apart in the $l_1$-distance. In the present paper we show that the quantum communication complexity of this problem is $tilde{O}(n/(tepsilon^2))$ qubits when the distributions have low $l_2$-norm, which gives a quadratic improvement over the classical communication complexity obtained by Andoni, Malkin and Nosatzki. We also obtain a matching lower bound by using the pattern matrix method. Let us stress that the samples received by each of the parties are classical, and it is only communication between them that is quantum. Our results thus give one setting where quantum protocols overcome classical protocols for a testing problem with purely classical samples.
The celebrated minimax principle of Yao (1977) says that for any Boolean-valued function $f$ with finite domain, there is a distribution $mu$ over the domain of $f$ such that computing $f$ to error $epsilon$ against inputs from $mu$ is just as hard as computing $f$ to error $epsilon$ on worst-case inputs. Notably, however, the distribution $mu$ depends on the target error level $epsilon$: the hard distribution which is tight for bounded error might be trivial to solve to small bias, and the hard distribution which is tight for a small bias level might be far from tight for bounded error levels. In this work, we introduce a new type of minimax theorem which can provide a hard distribution $mu$ that works for all bias levels at once. We show that this works for randomized query complexity, randomized communication complexity, some randomized circuit models, quantum query and communication complexities, approximate polynomial degree, and approximate logrank. We also prove an improved version of Impagliazzos hardcore lemma. Our proofs rely on two innovations over the classical approach of using Von Neumanns minimax theorem or linear programming duality. First, we use Sions minimax theorem to prove a minimax theorem for ratios of bilinear functions representing the cost and score of algorithms. Second, we introduce a new way to analyze low-bias randomized algorithms by viewing them as forecasting algorithms evaluated by a proper scoring rule. The expected score of the forecasting version of a randomized algorithm appears to be a more fine-grained way of analyzing the bias of the algorithm. We show that such expected scores have many elegant mathematical properties: for example, they can be amplified linearly instead of quadratically. We anticipate forecasting algorithms will find use in future work in which a fine-grained analysis of small-bias algorithms is required.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
