Quantum Communication Complexity and Nonlocality of Bipartite Quantum Operations.

Quantum Computation;Communication Complexity;Quantum Entanglement;Bipartite Quantum Operations;Nonlocality of Quantum Operations;Computer Science;Engineering;Computer Science & Engineering

Zhu, YufanMarkov, Igor L. ;

University of Michigan

关键词: Quantum Computation;    Communication Complexity;    Quantum Entanglement;    Bipartite Quantum Operations;    Nonlocality of Quantum Operations;    Computer Science;    Engineering;    Computer Science & Engineering;   

Others  :  https://deepblue.lib.umich.edu/bitstream/handle/2027.42/58538/yufanzhu_1.pdf?sequence=1&isAllowed=y

瑞士|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

This dissertation is motivated by the following fundamental questions: (a) arethere any exponential gaps between quantum and classical communication complexities?(b) what is the role of entanglement in assisting quantum communications? (c)how to characterize the nonlocality of quantum operations? We study four specificproblems below.1. The communication complexity of the Hamming Distance problem. TheHamming Distance problem is for two parties to determine whether or not theHamming distance between two n-bit strings is more than a given threshold. Weprove tighter quantum lower bounds in the general two-party, interactive communicationmodel. We also construct an efficient classical protocol in the more restrictedSimultaneous Message Passing model, improving previous results.2. The Log-Equivalence Conjecture. A major open problem in communicationcomplexity is whether or not quantum protocols can be exponentially more efficientthan classical ones for computing a total Boolean function in the two-party, interactivemodel. The answer is believed to be No. Razborov proved this conjecturefor the most general class of functions so far. We prove this conjecture for a broaderclass of functions that we called block-composed functions. Our proof appears to bethe first demonstration of the dual approach of the polynomial method in provingnew results.3. Classical simulations of bipartite quantum measurement. We define a newixconcept that measures the nonlocality of bipartite quantum operations. From thismeasure, we derive an upper bound that shows the limitation of entanglement inreducing communication costs.4. The maximum tensor norm of bipartite superoperators. We define a maximumtensor norm to quantify the nonlocality of bipartite superoperators. We showthat a bipartite physically realizable superoperator is bi-local if and only if its maximumtensor norm is 1. Furthermore, the estimation of the maximum tensor normcan also be used to prove quantum lower bounds on communication complexities.