Yaoyun Shi (施尧耘)
Professor of Electrical Engineering and Computer Science
... you may want to climb a mountain. You don't climb the Everest; your sights are not so ambitious. But when you do reach the top of the mountain, you see the valley below; and that gives you a sense of contentment. ---
Some of my favorate open problems on device-independent quantum cryptography.
This is a presentation at the AQIS 2016.
This is a presentation at the 2015 North American International Cyber Summit. Quantum Information Technology is becoming real. The implication for information security is far-reaching. A crisis is looming as the very foundation of cryptography is being challenged. Much of today’s public key cryptography will be defeated by large scale quantum computers. If a secret needs to stay secret for many years to come, encrypting it using current technologies is inadequate. To overcome these challenges, “Post-Quantum Cryptography” has emerged as an active area of research for searching for alternatives that are quantum resilient and at the same time practical. While threatening today’s cryptography, quantum information on the other hand enables unbreakable quantum cryptography. Most remarkably, some quantum cryptographic methods are “trustworthy,” i.e., the hardware will prove its integrity to the user. This is in contrast to the current solutions, which are “trusted,” i.e., require the user’s faith on their integrity. In this talk, I will outline these challenges and opportunities without assuming any prior knowledge of the field.
Randomness is a faith: it is impossible to test directly. In fact, we
can't even know for sure its existence. Yet randomness is also
indispensable in reality: it is the mother secret that gives life to
the security of modern cryptography. When blind faith is not virtuous,
how much of it is necessary for ensuring true randomness? In this
general-audience talk at the
Randomness in Quantum Mechanics and Beyond conference,
I argued that it is not too much.
Quantum Information Science Seminar and Reading Groups
This is a weekly seminar/reading group open to UM faculty and students.
If you'd like to participate, you can join our Ctools site "Quantum Information" or if you are not at UM, contact Kevin Sung or me.
This semester (Winter 2017) the seminar is at 4246 Randall Hall (Physics Department), 4-5pm.
My student Cupjin Huang also runs a weekly reading seminar on quantum machine learning, Fridays 3:30-5.
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-1260.
Quantum Information Science.
I have worked on several topics in theoretical quantum information science: query complexity,
computational complexity, communication complexity, universality, classical simulations,
quantum channels, and quantum cryptography.
My current projects include quantum cryptography (see my tutorial talk
"Untrusted Quantum Devices"), quantum
algorithms, and quantum error-correction.
I am also interested in learning and exploring "post-quantum" cryptography, or classical cryptography secure against
a quantum adversary. Most, if not all, widely used public key cryptography systems (such as RSA)
are not secure under quantum attack.
Thus as quantum computing becomes a reality, the subject of post-quantum cryptography will be
more and more important.
- Limitations on Transversal Computation through Quantum Homomorphic Encryption, with Michael Newman, 2017.
- Parallel Device-Independent Quantum Key Distribution, with Rahul Jain and Carl A. Miller, 2017.
- Quantum hashing is maximumly secure against classical leakage (to be posted; comments welcome), with Cupjin Huang, 2016.
- Certified randomness between mistrustful players, with Carl A. Miller, 2016.
- General randomness amplification with non-signaling security (to be posted; comments welcome), with Kai-Min Chung and Xiaodi Wu, 2016.
- Certifying the absence of quantum nonlocality, with Carl A. Miller, 2016.
Universal security for randomness expansion, with Carl A. Miller, arXiv:1411.6608 (to be updated soon). QIP 2015.
Also to be presented by Carl Miller at QCrypt 2015 as an invited plenary talk.
Physical Randomness Extractors: Generating Random Numbers with Minimal Assumptions
with Kai-Min Chung and Xiaodi Wu, arXiv:1402.4797 (to be updated). QIP 2014 (Part of a plenary talk selected from submissions).
Partially presented in "Untrusted Quantum Devices" at Simons Institute of Theoretical Computer Science.
Presented as an invited plenary talk at TQC 2014.
Also presented as part of an invited plenary talk at QCrypt 2014, click for the video recording.
- Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices, with Carl A. Miller, Journal of the ACM, 63 (4), 2016.
Preprint: arXiv:1402.0489 (updated 29 Jul 2016). Partially presented in "Untrusted Quantum Devices" at Simons Institute of Theoretical Computer Science and QCrypt 2014, QIP 2014 (plenary) and STOC 2014.
Robust self-testing quantum states and binary nonlocal XOR games
, with Carl A. Miller. TQC 2013.
- Efficient Protocols for Generating Bipartite Classical Distributions and Quantum States, with Rahul Jain, Zhaohui Wei,
and Shengyu Zhang. IEEE Transactions on Information Theory, 59(8): 5171-5178 (2013). Also in ACM-SIAM Symposium on Discrete Algorithms 2013: 1503-1512.
- Upper bounds on the accuracy of an assisted classical channel, with Brett Hemenway, Carl A. Miller,
and Mary Wootters. Phys. Rev. A 87, 062301, 2013.
- Epsilon-net method for optimizations over separable states, with Xiaodi Wu.
Proceedings of The 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), 798-809, 2012.
- Quantum Simpsons Paradox and High Order Bell-Tsirelson Inequalities.
- 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 (
- 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.
Theoretical Computer Science, 411(1), Pages 293–300, 2000.
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.