Learning junta distributions, quantum junta states, and QAC$^0$ circuits
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917512435728384 |
|---|---|
| author | Bao, Jinge Escudero-Gutiérrez, Francisco |
| author_facet | Bao, Jinge Escudero-Gutiérrez, Francisco |
| contents | In this work, we consider the problems of learning junta distributions, their quantum counterparts (quantum junta states) and $\mathsf{QAC}^0$ circuits, which we show to be close to juntas.
(1) Junta distributions. A probability distribution $p:\{-1,1\}^n\to \mathbb [0,1]$ is a $k$-junta if it only depends on $k$ bits. We show that they can be learned with to error $\varepsilon$ in total variation distance from $O(2^k\log(n)/\varepsilon^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 $\varepsilon$ in trace distance with $O(12^{k}\log(n)/\varepsilon^2)$ single copies. We also prove a lower bound of $Ω((4^k+\log (n))/\varepsilon^2)$ copies. Additionally, we show that, for constant $k$, $\tildeΘ(2^n/\varepsilon^2)$ copies are necessary and sufficient to test whether a state is $\varepsilon$-close or $7\varepsilon$-far from being a $k$-junta.
(3) $\mathsf{QAC}^0$ circuits. Nadimpalli et al. (STOC'24) recently showed that the Pauli spectrum of $\mathsf{QAC}^0$ circuits (with a limited number of auxiliary qubits) is concentrated on low-degree. We remark that they implied something stronger, namely that the Choi states of those circuits are close to be juntas. As a consequence, we show that $n$-qubit $\mathsf{QAC}^0$ circuits with size $s$, depth $d$ and $a$ auxiliary qubits can be learned from $2^{O(\log(s^22^a)^d)}\log (n)$ copies of the Choi state, improving the $n^{O(\log(s^22^a)^d)}$ by Nadimpalli et al. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_15822 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Learning junta distributions, quantum junta states, and QAC$^0$ circuits Bao, Jinge Escudero-Gutiérrez, Francisco Quantum Physics Computational Complexity In this work, we consider the problems of learning junta distributions, their quantum counterparts (quantum junta states) and $\mathsf{QAC}^0$ circuits, which we show to be close to juntas. (1) Junta distributions. A probability distribution $p:\{-1,1\}^n\to \mathbb [0,1]$ is a $k$-junta if it only depends on $k$ bits. We show that they can be learned with to error $\varepsilon$ in total variation distance from $O(2^k\log(n)/\varepsilon^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 $\varepsilon$ in trace distance with $O(12^{k}\log(n)/\varepsilon^2)$ single copies. We also prove a lower bound of $Ω((4^k+\log (n))/\varepsilon^2)$ copies. Additionally, we show that, for constant $k$, $\tildeΘ(2^n/\varepsilon^2)$ copies are necessary and sufficient to test whether a state is $\varepsilon$-close or $7\varepsilon$-far from being a $k$-junta. (3) $\mathsf{QAC}^0$ circuits. Nadimpalli et al. (STOC'24) recently showed that the Pauli spectrum of $\mathsf{QAC}^0$ circuits (with a limited number of auxiliary qubits) is concentrated on low-degree. We remark that they implied something stronger, namely that the Choi states of those circuits are close to be juntas. As a consequence, we show that $n$-qubit $\mathsf{QAC}^0$ circuits with size $s$, depth $d$ and $a$ auxiliary qubits can be learned from $2^{O(\log(s^22^a)^d)}\log (n)$ copies of the Choi state, improving the $n^{O(\log(s^22^a)^d)}$ by Nadimpalli et al. |
| title | Learning junta distributions, quantum junta states, and QAC$^0$ circuits |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2410.15822 |