The authors consider the communication complexity of the binary inner product function in a variation of the two-party scenario where the parties have an a priori supply of particles in an entangled quantum state. They prove linear lower bounds for both exact protocols, as well as for protocols that determine the answer with bounded-error probability. The proofs employ a novel kind of quantum reduction from multibit communication problems to the problem of computing the inner product. The communication required for the former problem can then be bounded by an application of Holevo`s theorem. They also give a specific example of ...
continued below
Publisher Info:
Los Alamos National Lab., NM (United States)
Place of Publication:
New Mexico
Provided By
UNT Libraries Government Documents Department
Serving as both a federal and a state depository library, the UNT Libraries Government Documents Department maintains millions of items in a variety of formats. The department is a member of the FDLP Content Partnerships Program and an Affiliated Archive of the National Archives.
Descriptive information to help identify this article.
Follow the links below to find similar items on the Digital Library.
Description
The authors consider the communication complexity of the binary inner product function in a variation of the two-party scenario where the parties have an a priori supply of particles in an entangled quantum state. They prove linear lower bounds for both exact protocols, as well as for protocols that determine the answer with bounded-error probability. The proofs employ a novel kind of quantum reduction from multibit communication problems to the problem of computing the inner product. The communication required for the former problem can then be bounded by an application of Holevo`s theorem. They also give a specific example of a probabilistic scenario where entanglement reduces the communication complexity of the inner product function by one bit.
This article is part of the following collection of related materials.
Office of Scientific & Technical Information Technical Reports
Reports, articles and other documents harvested from the Office of Scientific and Technical Information.
Office of Scientific and Technical Information (OSTI) is the Department of Energy (DOE) office that collects, preserves, and disseminates DOE-sponsored research and development (R&D) results that are the outcomes of R&D projects or other funded activities at DOE labs and facilities nationwide and grantees at universities and other institutions.
Cleve, R.; Dam, W. van; Nielsen, M. & Tapp, A.Quantum entanglement and the communication complexity of the inner product function,
article,
August 1, 1998;
New Mexico.
(digital.library.unt.edu/ark:/67531/metadc706249/:
accessed February 21, 2019),
University of North Texas Libraries, Digital Library, digital.library.unt.edu;
crediting UNT Libraries Government Documents Department.
