活动地点：

活动类型：学术报告

主讲人：Professor Kazuo Iwama(Kyoto University)

活动时间：

活动内容：

 

Abstract：

Ahlswede, Cai, Li, and Yeung (IEEE Trans. Inform. Theory, 2000) showed that the fundamental law for network flow, the max-flow min-cut theorem, no longer applies for ``digital information flow.''  The simple, nice example they gave is called the Butterfly network having six nodes, s0, s1, s2, t0, t1, t2 and seven directed links (s1, s0), (s1, t2), (s2, s0), (s2, t1), (s0, t0), (t0, t1), (t0, t2).  The capacity of each directed link is all one and there are two source-sink pairs s1 to t1 and s2 to t2. Notice that both paths have to use the single link from s0 to t0 and hence the total amount of (conventional commodity) flow in both paths is bounded by one, say, 1/2 for each. In the case of digital information flow, however, the protocol using EXOR operations at s0, t1 and t2 allows us to transmit two bits, x and y, simultaneously.  Thus, we can effectively achieve larger channel capacity than can be achieved by simple routing.  This is known as network coding since this seminal paper and has been quite popular as a mutual interest of theoretical computer science and information theory. The natural question is whether such a capacity enhancement is also possible for {\it quantum} information, more specifically, whether we can transmit two qubits from s1 to t1 and s2 to t2 simultaneously.  In this talk, we first introduce classic network coding and some basics of quantum computation.  Then we show that quantum network coding is possible if approximation is allowed.  Our results for the Butterfly network include: (i) We can send any quantum state from s1 to t1 and another any quantum state from s2 to t2 simultaneously with a fidelity strictly greater than 1/2. (ii) If one of two input states is classical, then the fidelity can be improved to 2/3. (iii) Similar improvement is also possible if the two input states 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.  Audience does not need any knowledge of quantum computation in advance.

This is a joint work with Masahito Hayashi, Harumichi Nishimura, Rudy Raymond, and Shigeru Yamashita.