Constant-depth quantum circuits can outperform log-depth classical circuits for certain interactive tasks.
TITLE: Quantum Advantage from Interactive Shallow Clifford Circuits
SPEAKER: Dr Daniel Grier
AFFILIATION: Institute for Quantum Computing, University of Waterloo, ON, Canada
HOSTED BY: Prof Michael Bremner, UTS Centre for Quantum Software and Information
ABSTRACT:
Recent work of Bravyi et al. and follow-up work by Bene Watts et al. demonstrates a quantum advantage with shallow circuits: constant-depth quantum circuits can perform a task which constant-depth classical (i.e., AC^0) circuits cannot. Their results have the advantage that the quantum circuit is fairly practical, and their proofs are free of hardness assumptions. In this talk, I’ll present a follow-up result, which attempts to hold on to these advantages, while increasing the power of the classical simulator.
The main result is a two-round interactive task which is solved by a constant-depth quantum circuit (using only Clifford gates, between neighboring qubits of a 2D grid, with Pauli measurements), but such that any classical machine/circuit for the task would need to solve parity-L-hard problems. I’ll focus on proving a slightly weaker result (NC^1-hardness), but the techniques generalize to parity-L.
Joint work with Luke Schaeffer.
RELATED ARTICLES:
Interactive shallow Clifford circuits: quantum advantage against NC1 and beyond: https://arxiv.org/abs/1911.02555
OTHER LINKS:
Daniel Grier Personal Webpage: danielgrier.com/
Institute for Quantum Computing: https://uwaterloo.ca/institute-for-quantum-computing/
UTS Centre for Quantum Software and Information: https://www.uts.edu.au/research-and-teaching/our-research/centre-quantum-software-and-information
Michael Bremner: https://www.uts.edu.au/staff/michael.bremner
