Yaoyun Shi （施尧耘，施堯耘）

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

This is a weekly reading group open to UM faculty and students. Please contact either Carl Miller or me if you would like to participate.

• Computational Complexity Poetry (Fall 2011)
• Quantum Poetry (Fall 2002)

Research Interests: quantum information processing and theory of computation. My research aims to understand the inherent power and limitations of various information processing technologies, especially those based on principles of quantum mechanics.

For example, with Høyer and Neerbek, I proved that quantum computers cannot substantially outperform classical computers for sorting numbers. Besides quantum lower bounds, other topics that I have worked on include universality of quantum gate sets, classical simulation of quantum computation and the evolution of quantum systems, (quantum and classical) communication complexity, capacity of quantum communication channels, entanglement transformations, and quantum cryptography.

Research Group Members

• Ph.D. students: Xiaodi Wu.
• Research Fellow: Carl A. Miller.
• Past Ph.D. students: Computer Science: Yufan Zhu (Google), Ye Du (Microsoft); Physics: Eric Chitambar (U Toronto).

• Paul Berman (Physics) - quantum optics theory and QI
• Tony Bloch (Math) - quantum control theory
• Hui Deng (Physics) - semiconductor cavity QI
• Luming Duan (Physics) - quantum information and atomic theory
• Theodore Goodson (Chemistry) - photonic QI
• John Hayes (EECS) - quantum circuit architecture and synthesis
• Aaron Leanhardt (Physics) - cold atom QI
• Igor Markov (EECS) - quantum circuit simulation, synthesis and optimization
• Roberto Merlin (Physics/EECS) - semiconductor QI
• Georg Raithel (Physics) - laser-cooled Rydberg atom QI
• Yaoyun Shi (EECS) - theory of quantum information and computation
• Vanessa Sih (Physics) - semiconductor QI
• Duncan Steel (EECS/Physics) - semiconductor quantum dot QI
• Kim Winick (EECS) - quantum information theory

Recent Papers

• Deciding unitary equivalence between matrix polynomials and sets of bipartite quantum states. With Eric Chitambar and Carl A. Miller. Quantum Information and Computation, Vol. 11, No. 9&10 (2011) 0813-0819.
• On parity complexity measures of Boolean functions. Zhiqiang Zhang and Yaoyun Shi. Theoretical Computer Science, Volume 411, Issues 26-28, 6 June 2010, Pages 2612-2618.
• Matrix pencils and entanglement classification. With Eric Chitambar and Carl A. Miller. Journal of Mathematical Physics, 51, 072205 (2010).[doi:10.1063/1.3459069]
• When is there a multipartite maximum entangled state? With Runyao Duan. Quantum Information and Computation, 10, 11&12 (2010) 0925-0935.
• Tripartite to bipartite entanglement transformations and Polynomial Identity Testing. With Eric Chitambar and Runyao Duan, 2009. Phys. Rev. A 81, 052310 (2010).[doi:10.1103/PhysRevA.81.052310]
• Predicting stock returns and fund performance through network analysis. With Noah Stoffman, Kathy Yuan, and Ji Zhu.
• Constant-degree graph expansions that preserve treewidth. With Igor Markov. To appear in Algorithmica, 2009.
• The quantum communication complexity of block-composed functions. With Yufan Zhu. Quantum Information and Computation, 9(5&6):444-460, 2009.
• Communication complexities of XOR functions. Zhiqiang Zhang and Yaoyun Shi Quantum Information and Computation, 9(3&4): 255-263, 2009.
• PerturbationRank: a non-monotone ranking algorithm. With Ye Du and James Leung.
• Tripartite entanglement transformations and tensor rank With Eric Chitambar and Runyao Duan, Physical Review Letters,101, 140502, 2008.
• Entanglement between two uses of a noisy multipartite quantum channel enables perfect transmission of classical information. With Runyao Duan. Physical Review Letters, 101, 020501, 2008.
• Characterizing locally indistinguishable orthogonal product states. With Yuan Feng, IEEE Transactions on Information Theory, 55(6), 2799--2806, 2009.
• 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. SIAM Journal on Computing, 38(3):963-981, 2008.
• 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, SIAM Journal on Computing, 38(3):753--766, 2008. 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.

Older Papers

You are visiting me from 38.107.179.242