Master’s Thesis Presentation • Quantum Computing • On the Power of Interleaved Low-depth Quantum and Classical Circuits

Please note: This master’s thesis presentation will be given in QNC 1201 and online.

Abhishek Anand, Master’s candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Shalev Ben-David

Low-depth quantum circuits provide a well-suited model for near-term quantum devices given the short coherence times and noisy gate operations of these devices. Therefore, it is crucial to study the computational power of low-depth quantum circuits. It was already known as early as 2004 that sampling from even such low-depth circuits is classically hard under complexity-theoretic assumptions. Later, it was shown that low-depth quantum circuits interleaved with low-depth classical circuits can perform approximate quantum Fourier transform, the quantum subroutine of Shor’s algorithm.

Given these salient features of low-depth models, Terhal and DiVincenzo, Aaronson, and Jozsa have all independently conjectured regarding the elusive power of combining low-depth quantum circuits with efficient classical computation. However, much has remained unresolved in this interleaved setting. Therefore, in this thesis, we tackle the question of characterizing the computational power of interleaved low-depth quantum and classical circuits. We first review existing separations in the low-depth setting. Then, we formally define two interleaving models based on whether the quantum device is permitted to make subset measurements (weak interleaving) or must measure all qubits (strict interleaving).

By combining existing techniques from quantum fan-out constructions, teleportation-based quantum computation, and Clifford + T circuit synthesis, we show several results regarding the power of strictly and weakly interleaving variants of constant-depth quantum circuits (QNC0) with constant-depth classical parity circuits. Our main result is that QNC0 with log advice strictly interleaved with constant-depth classical parity circuits can simulate constant-depth threshold circuits (TC0), which neither of the interleaved classes can do on their own. This strictly separates this interleaved class from AC0[p] (constant-depth classical circuits with unbounded fan-in mod p and OR gates).

To join this master’s thesis presentation on Zoom, please go to https://uwaterloo.zoom.us/j/95954594871?pwd=cW83bU84WS9OTmYzUEkvV0MyYjBYQT09.