Yaoyun Shi

Assistant Professor
Ph.D., Princeton, 2001; B.S., Beijing University, 1997.

Search for papers in quantum information processing

Search for theoretical computer science related informaiton

Research Interests: theory of computation and quantum computing.

My research aims to understand the inherent power and limitations of various computing technologies, including those currently deployed, as well as more recent paradigms such as quantum mechanical computation. The techniques involved come from many branches of mathematics, such as combinatorics, linear algebra, probability theory, and approximation theory.

For example, with Høyer and Neerbek, I proved that quantum computers cannot substantially outperform classical computers for sorting numbers. Lately, I have been trying to develop fast algorithms for systematic classical simulations of quantum computation and the evolution of quantum systems. Such algorithms will not only sharpen the boundary between quantum and classical computations, but may also provide powerful tools for the analysis and engineering of quantum information processing components.

Working with my students and colleagues, I am also developing interest on several other topics, such as biological information processing, computational game theory, and natural language processing.

Contact information:
Postal: University of Michigan, Electrical Engineering and Computer Science, 2260 Hayward, Ann Arbor, MI 48109-2121, USA
Office: CSE 3632, Telephone: (734)764-3308, Fax: (734)763-8094.
E-mail:

Recent Papers

• Entanglement between two uses of a noisy multipartite quantum channel enables perfect transmission of classical information. With Runyao Duan.
• The quantum communication complexity of block-composed functions. With Yufan Zhu.
• Characterizing locally indistinguishable orthogonal product states. With Yuan Feng.
• Constant-degree graph expansions that preserve treewidth. With Igor Markov.
• Approximate polynomial degree of Boolean functions and its applications. Proceedings of the 4th International Congress of Chinese Mathematicians, 2007.
• Simulating quantum computation by contracting tensor networks. With Igor Markov. To appear in SIAM Journal on Computing, 2007.
• Using Spam Farm to Boost PageRank. With Ye Du and Xin Zhao. Proceedings of Third International Workshop on Adversarial Information Retrieval on the Web ( AIRWeb07), 2007.
• On multicast in quantum networks. With Emina Soljanin. 40th Annual Conference on Information Sciences and Systems (CISS) 2006.
• Path Auction Games When an Agent Can Own Multiple Edges. With Ye Du and Rahul Sami. NetEcon 2006.
• Classical simulation of quantum many-body systems with a tree tensor network. Yaoyun Shi, Luming Duan, and Guifré Vidal, Physical Review A, 74, 022320, 2006.
• The communication complexity of the Hamming Distance Problem. With Wei Huang, Shengyu Zhang, and Yufan Zhu. Information Processing Letters, 99(4), 149--153, 2006.
• Tensor norms and the classical communication complexity of bipartite quantum measurements. With Yufan Zhu, to appear in SIAM Journal on Computing, 2007. A preliminary version appeared in Proceedings of the 37th ACM Symposium on Theory of Computing (STOC 2005), 460--467, 2005.
• Quantum and Classical Tradeoffs. Theoretical Computer Science, 344(2-3):335 345, 2005.
• Distributed construction of quantum fingerprints. With Andris Ambainis, Quantum Information and Computation, 4(2):146-151, 2004.
• Both Toffoli and Controlled-NOT need little help to do universal quantum computation. Quantum Information and Computation, 3(1):84-92, 2003.

Older Papers

You are visiting me from 38.103.63.17