Yaoyun Shi

... 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. 
Subrahmanyan Chandrasekhar


This is a presentation at the 2015 North American International Cyber Summit. Quantum Information Technology is becoming real. The implication for information security is farreaching. 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, “PostQuantum 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
generalaudience talk at the
Randomness in Quantum Mechanics and Beyond conference,
I argued that it is not too much.

Reading Group
Class Poetry
Contact Information
Research
Recent Papers
Quantum Information Processing Seminar and Reading Group
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 Mike Newman or me.
Class Poetry:
Contact information:
Postal: University of Michigan,
Electrical Engineering and Computer Science, 2260 Hayward, Ann Arbor, MI 481092121, USA
Office: CSE 3632, Telephone: (734)7643308, Fax: (734)7631260.
Email:
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
these based on the principles of quantum mechanics.
I have worked on several topics in quantum information processing: query complexity,
computational complexity, communication complexity, universality, classical simulations,
quantum channels, and quantum cryptography.
One topic that I find particularly fascinating in recent years is quantum
cryptography using untrusted devices (see my tutorial talk
"Untrusted Quantum Devices").
It is usually referred to as "deviceindependent," or "untrusteddevice" quantum cryptography, but
it may be more intuitive to call it "Trustworthy Quantum Cryptography."
Here "trustworthiness" means that it never fails. The beauty of this area is that
by quantum magic, we can achieve provable and unconditional security using completely untrusted hardware.
I am interested in working with experimentalists to prototype protocols that my coauthors and I studied.
I'd welcome collaborations with information security, especially hardware security, researchers to explore together
quantum approaches for solving security problems.
I am also interested in learning and exploring "postquantum" 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 postquantum cryptography will be
more and more important.
Recent Papers
 Quantum homomorphic encryption, transversal computation, and their limitations (to be posted, comments welcome),
with Michael Newman, 2016.
 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 nonsignaling security (to be posted; comments welcome), with KaiMin 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 KaiMin 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, arXiv:1402.0489 (updated
2 Aug 2016).
QIP 2014 (Part of a plenary talk selected from submissions).
Partially presented in "Untrusted Quantum Devices" at Simons Institute of Theoretical Computer Science, and STOC 2014.
Also presented as part of an invited plenary talk at QCrypt 2014, click for the video recording.
Journal version to appear in Journal of the ACM, 2016.

Robust selftesting 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): 51715178 (2013). Also in ACMSIAM Symposium on Discrete Algorithms 2013: 15031512.
 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.
 Epsilonnet method for optimizations over separable states, with Xiaodi Wu.
Proceedings of The 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), 798809, 2012.
 Quantum Simpsons Paradox and High Order BellTsirelson Inequalities.
[Presentation]
 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) 08130819.
 On parity complexity measures of Boolean functions. Zhiqiang Zhang and Yaoyun Shi. Theoretical Computer Science, Volume 411, Issues 2628, 6 June 2010, Pages 26122618.
 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) 09250935.
 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.

Constantdegree graph expansions that preserve treewidth.
With Igor Markov. To appear in Algorithmica, 2009.
 The quantum communication complexity of blockcomposed functions.
With Yufan Zhu. Quantum Information and Computation, 9(5&6):444460, 2009.

Communication complexities of XOR functions. Zhiqiang Zhang and Yaoyun Shi
Quantum Information and Computation, 9(3&4): 255263, 2009.

PerturbationRank: a nonmonotone 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), 27992806, 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):963981, 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.
Theoretical Computer Science, 411(1), Pages 293–300, 2000.
NetEcon 2006.

Classical simulation of quantum manybody 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), 149153, 2006.

Tensor norms and the classical communication complexity of
bipartite quantum measurements. With Yufan Zhu,
SIAM Journal on Computing, 38(3):753766, 2008.
A preliminary version appeared in
Proceedings of the 37th ACM Symposium on Theory of Computing (STOC 2005), 460467, 2005.

Quantum and Classical Tradeoffs.
Theoretical Computer Science, 344(23):335 345, 2005.
Older Papers
You are visiting me from 54.147.211.117