BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Learning shallow quantum circuits with many-qubit gates - Francisc
 a Vasconcelos (UC Berkeley)
DTSTART:20250619T100000Z
DTEND:20250619T110000Z
UID:TALK233485@talks.cam.ac.uk
CONTACT:Tom Gur
DESCRIPTION:In this talk\, I will describe the first computationally-effic
 ient algorithm for average-case learning of shallow quantum circuits with 
 many-qubit gates. Specifically\, leveraging prior results on Pauli concent
 ration of QAC0 [NPVY'24] and efficient learning of QNC0 circuits [HLB+'24]
 \, we provide a quasi-polynomial sample- and time-complexity algorithm for
  learning a full unitary description of unknown QAC0 circuits (with at mos
 t logarithmic ancilla) up to inverse-polynomially small error. As time per
 mits\, I will discuss interesting open questions following from the work\,
  such as: using PRUs to prove optimality of learning\, the possibility of 
 efficient proper learning of QAC0\, and general connections to the number 
 of ancilla required to compute Parity in QAC0.\n\nThe talk is based on the
  paper [arXiv:2410.16693]\, joint work with Robert Huang\, to appear at CO
 LT 2025.
LOCATION:Computer Laboratory\, William Gates Building\, Room SS03
END:VEVENT
END:VCALENDAR