BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Daniel Grier (University of Waterloo\, Canada) DTSTART:20200616T010000Z DTEND:20200616T020000Z DTSTAMP:20260423T010236Z UID:UTSQSI/9 DESCRIPTION:Title: I nteractive Shallow Clifford Circuits: Quantum advantage against NC1 and be yond\nby Daniel Grier (University of Waterloo\, Canada) as part of Cen tre for Quantum Software and Information Seminar Series\n\n\nAbstract\nRec ent work of Bravyi et al. and follow-up work by Bene Watts et al. demonstr ates a quantum advantage with shallow circuits: constant-depth quantum cir cuits can perform a task which constant-depth classical (i.e.\, AC^0) circ uits 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. \n\nThe main result is a two-round interactive task which is solved by a c onstant-depth quantum circuit (using only Clifford gates\, between neighbo ring qubits of a 2D grid\, with Pauli measurements)\, but such that any cl assical machine/circuit for the task would need to solve parity-L-hard pro blems. I'll focus on proving a slightly weaker result (NC^1-hardness)\, b ut the techniques generalize to parity-L.\n\nJoint work with Luke Schaeffe r.\n\nHosted by Michael Bremner\, UTS Centre for Quantum Software and Info rmation\n LOCATION:https://researchseminars.org/talk/UTSQSI/9/ END:VEVENT END:VCALENDAR