Learning shallow quantum circuits with many-qubit gates

Add to your list(s) Download to your calendar using vCal

• Francisca Vasconcelos (UC Berkeley)
• Thursday 19 June 2025, 11:00-12:00
• Computer Laboratory, William Gates Building, Room SS03.

If you have a question about this talk, please contact Tom Gur.

In this talk, I will describe the first computationally-efficient algorithm for average-case learning of shallow quantum circuits with many-qubit gates. Specifically, leveraging prior results on Pauli concentration 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 most logarithmic ancilla) up to inverse-polynomially small error. As time permits, 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 .

The talk is based on the paper [arXiv:2410.16693], joint work with Robert Huang, to appear at COLT 2025 .

This talk is part of the Quantum Computing Seminar series.

This talk is included in these lists:

• Algorithms and Complexity Seminar
• All Talks (aka the CURE list)
• Cambridge talks
• Computer Laboratory, William Gates Building, Room SS03
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• Quantum Computing Seminar
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• yk449

Note that ex-directory lists are not shown.