CS Seminar
Quantum computing is at an exciting moment in its history, with some high-profile experimental successes in building programmable quantum devices. That said, these quantum devices (at least in the near term) will be restricted in several ways, raising questions about their power relative to classical computers. In this talk, I will present three results which give us a better understanding of these near-term quantum devices, revealing key features which make them superior to their classical counterparts.
First, I will show that constant-depth quantum circuits can solve problems that cannot be solved by any constant-depth classical circuit consisting of AND, OR, NOT, and PARITY gates---giving the largest-known unconditional separation between natural classes of quantum and classical circuits. Second, I will show that these quantum circuits can nevertheless be simulated quickly by classical algorithms that have no depth restriction, emphasizing the role that depth plays in provable quantum advantage. Finally, I will address some of the experimental challenges in implementing linear optical quantum computers, and I will prove that they outperform classical computers using standard conjectures but in more practical experimental regimes.