IQC Math and CS seminar featuring Franciso Escudero Gutierrez

Learning junta distributions and quantum junta states, and QAC0 circuits

by Franciso Escudero Gutierrez | Centrum Wiskunde and Informatica (CWI)

In this work we consider the problems of learning junta distributions, their quantum counterpart, quantum junta states, and QAC0 circuits, which we show to be juntas.

1. Junta distributions. A probability distribution p:{−1, 1}^n → [0, 1] is a k-junta if it only depends on k variables. We show that they can be learned with to error ε in total variation distance from O(2^k log(n)/ε^2) samples, which quadratically improves the upper bound of Aliakbarpour et al. (COLT’16) and matches their lower bound in every parameter.

2. Junta states. We initiate the study of n-qubit states that are k-juntas, those that are the tensor product of a k-qubit state and an (n−k)-qubit maximally mixed state. We show that these states can be learned with error ε in trace distance with O(12^k log(n)/ε^2) single copies. We also prove a lower bound of Ω((4^k + log(n))/ε^2) copies. Along the way, we give a new proof of the optimal performance of Classical Shadows based on Pauli analysis.

3. QAC0 circuits. Nadimpalli et al. (STOC’24) recently showed that the Pauli spectrum of QAC0 circuits (with not too many auxiliary qubits) is concentrated on low-degree. We remark that they showed something stronger, namely that the Choi states of those circuits are close to be juntas. As a consequence, we show that n-qubit QAC0 circuits with size s, depth d and a auxiliary qubits can be learned from 2^[O(log(s^2 2^a)^d] log(n) copies of the Choi state, improving the n^[O(log(s^2 2^a)^d] by Nadimpalli et al. In addition, we use this remark to improve on the lower bounds against QAC0 circuits to compute the address function.

Based on arXiv:2410.15822

Location

• Online on Zoom

  • Meeting ID: 989 8451 1688

    Passcode: 388104