Quantum Network Coding

Complexity of Boolean Functions

计算机科学;物理学;物理学

Masahito Hayashi1 ; Kazuo Iwama2 ; Harumichi Nishimura3 ; Rudy Raymond2 and Shigeru Yamashita4 1 Japan Science and Technology Agency ; ERATO-SORST Quantum Computation and Information Project Tokyo 113-0033 ; Bunkyo-ku ; Hongo 5-28-3 ; Japan ; 2 Kyoto University ; Graduate School of Informatics Kyoto 606-8501 ; Sakyo-ku ; Yoshida-Honmachi ; Japan ; 3 Osaka Prefecture University ; Graduate School of Science Osaka 599-8531 ; Sakai ; Gakuen-cho 1-1 ; Japan ; 4 Graduate School of Information Science ; N

Others  :  http://drops.dagstuhl.de/opus/volltexte/2006/608/pdf/06111.IwamaKazuo.Paper.608.pdf
PID  :  6441

学科分类：计算机科学（综合）

来源: CEUR

【 摘 要 】

Since quantum information is continuous, its handling issometimes surprisingly harder than the classical counterpart. A typical example is cloning; making a copy of digital information is straightfor- ward but it is not possible exactly for quantum information. The question in this paper is whether or not quantum network coding is possible. Its classical counterpart is another good example to show that digital infor- mation flow can be done much more efficiently than conventional (say, liquid) flow. Our answer to the question is similar to the case of cloning, namely, it is shown that quantum network coding is possible if approximation is al- lowed, by using a simple network model called Butterfly. In this network, there are two flow paths, s1 to t1 and s2 to t2, which shares a single bot- tleneck channel of capacity one. In the classical case, we can send two bits simultaneously, one for each path, in spite of the bottleneck. Our results for quantum network coding include: (i) We can send any quan- tum state jÃ1i from s1 to t1 and jÃ2i from s2 to t2 simultaneously with a fidelity strictly greater than 1=2. (ii) If one of jÃ1i and jÃ2i is classi- cal, then the fidelity can be improved to 2=3. (iii) Similar improvement is also possible if jÃ1i and jÃ2i are restricted to only a finite number of (previously known) states. (iv) Several impossibility results including the general upper bound of the fidelity are also given.