Workshop on Quantum Algorithms and Devices - Part 1

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