Workshop on Quantum Algorithms and Devices – Part 1


July 24, 2014


Yaoyun Shi and Ben Reichardt


University of Michigan, Ann Arbor, University of Southern California


8:30AM – 9:00AMWelcome and Introductions/Framing for event Krysta Svore (QuArC)

9:00AM – 9:40AMTrue Randomness: Its Genesis and Expansion Yaoyun Shi (University of Michigan)

Abstract: How can we produce randomness of almost perfect quality, in large quantities, and under minimal assumptions? This question is fundamental not only to modern day information processing but also to physics. Yet a satisfactory answer is still elusive to both the practice and the theory of randomness extraction.

Here we propose a solution through an emerging paradigm of extracting randomness from physical systems and basing security on the validity of physical theories. We construct and analyze such (new and existing) “physical extractors” extracting from non-interacting quantum devices, whose inner-workings may be imperfect or even malicious. Composing our extractors gives a protocol that starts with a single and arbitrarily weak source of a fixed length and produces an arbitrarily long random output of close to optimal quality and provable security against all- powerful quantum adversaries. Several desirable features of our protocols, including cryptographic level of security and the tolerance of device imprecision, widen the scope of their applications and facilitate their implementations with the current quantum technology.

Our work also implies that unless the world is deterministic, we can experimentally create inherently random events and be confident of their unpredictability. It thus provides a practical and strongest method known for mitigating the “freedom of choice” loophole for experimentally rejecting local realism.

Based on joint works with Carl A. Miller (arXiv:1402.0489), Kai- Min Chung and Xiaodi Wu (arXiv:1402.4797).

9:40AM – 10:20AMClassical Command of Quantum Systems

Ben Reichardt (University of Southern California)

Abstract: Can a classical experimentalist command an untrusted quantum system to realize arbitrary quantum dynamics, aborting if it misbehaves? We give a way for a classical system to certify the joint, entangled state of a bipartite quantum system, as well as command the application of specific operators on each subsystem. This is accomplished by showing a strong converse to Tsirelson’s optimality result for the CHSH game: the only way to win many games is if the bipartite state is close to the tensor product of EPR states, and if the measurements are the optimal CHSH measurements on successive qubits. This leads to a scheme for secure delegated quantum computation. Joint work with Falk Unger and Umesh Vazirani.

10:20AM – 10:50AMCoffee Break


Yaoyun Shi and Ben Reichardt

Yaoyun Shi received his Bachelor’s degree from Beijing University in 1997 and his PhD from Princeton University in 2001, both in Computer Science. He was a postdoc at the Institute of Quantum Information at Caltech and is currently an Associate Professor at the University of Michigan, Ann Arbor. His research focuses on the theory of quantum information processing.

Ben Reichardt is an Assistant Professor of Electrical Engineering at the University of Southern California (USC). His main research interests are in quantum computation: algorithms, fault tolerance and cryptography. He was a postdoc at the Institute for Quantum Information at Caltech from 2006-08, an assistant professor at the Institute for Quantum Computation at the University of Waterloo from 2008-11, and joined USC in 2012.