Thumbnail
Access Restriction
Open

Author Buhrman, Harry ♦ Wolf, Ronald De
Source CiteSeerX
Content type Text
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Communication Complexity Lower Bound ♦ Qubit Communication ♦ Inner Product Function ♦ Classical Communication Complexity ♦ Various Class ♦ Bounded-error Protocol ♦ Communication Complexity ♦ Bound Technique ♦ Unlimited Prior Entanglement ♦ Log Rank ♦ Communication Matrix ♦ Log-rank Conjecture ♦ Exact Protocol ♦ Polynomial Equivalence ♦ Strong Bound ♦ Prior Entanglement ♦ Quantum Version
Description The quantum version of communication complexity allows Alice and Bob to communicate qubits and/or to make use of prior entanglement (shared EPR-pairs). Some lower bound techniques are available for qubit communication [17, 11, 2], but except for the inner product function [11], no bounds are known for the model with unlimited prior entanglement. We show that the "log rank" lower bound extends to the strongest model (qubit communication + prior entanglement). By relating the rank of the communication matrix to properties of polynomials, we are able to derive some strong bounds for exact protocols. In particular, we prove both the "log-rank conjecture" and the polynomial equivalence of quantum and classical communication complexity for various classes of functions. We also derive some weaker bounds for bounded-error protocols.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 1999-01-01
Publisher Institution IN PROCEEDINGS OF THE 16TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY