Quantum complexity and circuit obfuscation

How powerful are quantum computers? Despite the prevailing belief that quantum computers are more powerful than their classical counterparts, this remains a conjecture backed by little formal evidence. Shor's algorithm, for instance, gives an example of a problem (factoring), which can be solved efficiently on a quantum computer with no known efficient classical algorithm. Factoring however, is unlikely to be NP-hard, meaning that few unexpected formal consequences would arise, should such a classical algorithm be discovered. Could it then be the case that any quantum algorithm can be simulated efficiently classically? Likewise, could it be the case that quantum computers can quickly solve problems much harder than factoring? In particular, what classical computational resources do we need to solve the hardest problem that has an efficient quantum algorithm? In this seminar, we address these questions and give an overview of recent research proving that quantum computers can sample from distributions that cannot be sampled efficiently by classical computers. We further utilize these results to discuss the feasibility of quantum circuit obfuscation-- a powerful primitive with many applications to cryptography. We show that some of the most desirable variants of quantum obfuscation procedures are impossible to achieve. Despite this, there are other variants that are not able to prove impossible, and even constructions of candidate quantum circuit obfuscators. We survey these results, and give new, quantum applications of these more limited obfuscators. (Based on joint work with Chris Umans (Caltech) and Gorjan Alagic (Copenhagen).