Interactive Shallow Clifford Circuits: Quantum advantage against NC1 and beyond

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.

quantum computing and information

Audience: researchers in the topic

( paper )

Comments: Hosted by Michael Bremner, UTS Centre for Quantum Software and Information

---

Centre for Quantum Software and Information Seminar Series

Series comments: To request the zoom link, please send a message to: cqsiadmin@uts.edu.au using your business/organisation/institution email address. Watch previous seminars on YouTube: - QSI Seminar Series 2021 (https://youtube.com/playlist?list=PLux7B14QYkPbDDOpqKSWScHXHodiBwr48) - QSI Seminar Series 2020 (https://youtube.com/playlist?list=PLux7B14QYkPZREUXReOq01ewLl02QXBXa)

---