DocumentCode :
1632535
Title :
On communication over an entanglement-assisted quantum channel
Author :
Nayak, Ashwin ; Salzman, Julia
Author_Institution :
Dept. of Comput. Sci., California Inst. of Technol., Pasadena, CA, USA
fYear :
2002
fDate :
6/24/1905 12:00:00 AM
Firstpage :
12
Lastpage :
12
Abstract :
Shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols: the two parties may be given some number of quantum bits jointly prepared in a fixed superposition, prior to communicating with each other. The quantum channel is then said to be "entanglement-assisted." Shared randomness does not help in the transmission of information from one party to another. Moreover, it does not significantly reduce the classical complexity of computing functions vis-a-vis private-coin protocols. On the other hand, prior entanglement leads to startling phenomena such as "quantum teleportation" and "superdense coding." The problem of characterising the power of prior entanglement has baffled many researchers, especially in the setting of bounded-error protocols. It is open whether it leads to more than a factor of two savings (using superdense coding) or more than an additive O(log) savings (when used to create shared randomness). Few lower bounds are known for communication problems in this setting, and are all derived using sophisticated information theoretic techniques. In this paper, we focus on the most basic problem in the setting of communication over an entanglement-assisted quantum channel, that of communicating classical bits from one party to another. We derive optimal bounds on the number of quantum bits required for this task, for any given probability of error
Keywords :
computational complexity; information theory; quantum communication; bounded-error protocols; communication; entanglement-assisted quantum channel; error probability; fixed superposition; information theory; lower bounds; optimal bounds; prior entanglement; quantum bits; quantum teleportation; shared entanglement; shared randomness; superdense coding; Complexity theory; Computational complexity; Computer science; Mathematics; Protocols; Quantum computing; Quantum entanglement; Quantum mechanics; Random variables;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computational Complexity, 2002. Proceedings. 17th IEEE Annual Conference on
Conference_Location :
Montreal, Que.
ISSN :
1093-0159
Print_ISBN :
0-7695-1468-5
Type :
conf
DOI :
10.1109/CCC.2002.1004331
Filename :
1004331
Link To Document :
بازگشت