Online Seminar: Dr Daniel Grier, U.Waterloo, Canada

Constant-depth quantum circuits can outperform log-depth classical circuits for certain interactive tasks.

quantum advantage text over blue and pink abstract light burst

Background Image: Tomislav Jakupec / Pixabay

Interactive Shallow Clifford Circuits: Quantum advantage against NC1 and beyond

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.

 

Back to QSI Seminars & Events
Acknowledgement of Country

UTS acknowledges the Gadigal people of the Eora Nation, the Boorooberongal people of the Dharug Nation, the Bidiagal people and the Gamaygal people, upon whose ancestral lands our university stands. We would also like to pay respect to the Elders both past and present, acknowledging them as the traditional custodians of knowledge for these lands.