Learning junta distributions, quantum junta states, and QAC$^0$ circuits

Francisco Escudero-Guti\'errez; Jinge Bao

arxiv: 2410.15822 · v3 · pith:DNIEE3B2new · submitted 2024-10-21 · 🪐 quant-ph · cs.CC

Learning junta distributions, quantum junta states, and QAC⁰ circuits

Jinge Bao , Francisco Escudero-Guti\'errez This is my paper

Pith reviewed 2026-05-23 18:39 UTC · model grok-4.3

classification 🪐 quant-ph cs.CC

keywords junta distributionsquantum junta statesQAC0 circuitssample complexitytrace distancetotal variation distancePauli spectrumlearning theory

0 comments

The pith

k-junta distributions can be learned to total variation error ε with O(2^k log n / ε²) samples, matching the lower bound.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that k-junta distributions over n bits, which depend on only k coordinates, can be learned to error ε in total variation distance from O(2^k log(n)/ε²) samples. This quadratically improves the prior upper bound and matches the known lower bound in every parameter. It extends the approach to quantum k-junta states, defined as tensor products of a k-qubit state and a maximally mixed state on the remaining qubits, which are learnable to trace distance ε with O(12^k log(n)/ε²) single copies and have a lower bound of Ω((4^k + log n)/ε²). The work also shows that the Choi states of QAC0 circuits are close to juntas, allowing learning of such circuits from 2^{O(log(s² 2^a)^d)} log n copies instead of the previous n to a power. A sympathetic reader would care because the bounds are nearly tight and reduce the resources needed for learning structured objects in high dimensions.

Core claim

The central claim is that k-junta distributions can be learned to error ε in total variation distance from O(2^k log(n)/ε²) samples, quadratically improving the upper bound of Aliakbarpour et al. and matching their lower bound in every parameter. Quantum k-junta states can be learned to trace distance ε with O(12^k log(n)/ε²) single copies, along with a lower bound of Ω((4^k + log n)/ε²) copies; for constant k, testing requires Θ̃(2^n/ε²) copies. QAC0 circuits with size s, depth d, and a auxiliary qubits have Choi states close to juntas and thus can be learned from 2^{O(log(s² 2^a)^d)} log n copies of the Choi state, improving the prior n^{O(log(s² 2^a)^d)} bound.

What carries the argument

The k-junta property (dependence on only k out of n bits or qubits) together with concentration of the Fourier spectrum for classical cases and the Pauli spectrum for quantum cases.

If this is right

Learning junta distributions now matches the information-theoretic lower bound in the dependence on k, n, and ε.
Quantum junta states admit learning with a number of copies exponential in k but only logarithmic in n.
For constant k, distinguishing k-junta states from those 7ε-far requires Θ(2^n / ε²) copies.
QAC0 circuits become learnable with a sample count that is polylogarithmic in n rather than polynomial.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The quadratic classical improvement may indicate that refined estimators can tighten bounds in other distribution learning settings.
The Pauli-spectrum approach for QAC0 could extend to additional circuit families with low-degree concentration.
The testing lower bound for constant-k juntas suggests that structured quantum state learning can still require resources comparable to full tomography in the worst case.

Load-bearing premise

Access consists of independent classical samples or single copies of the quantum state, and error is measured in total variation or trace distance.

What would settle it

An algorithm that learns every k-junta distribution to error ε using o(2^k log n / ε²) samples, or a k-junta distribution family that requires ω(2^k log n / ε²) samples, would settle the claimed sample complexity.

read the original abstract

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 $\Omega((4^k+\log (n))/\varepsilon^2)$ copies. Additionally, we show that, for constant $k$, $\tilde{\Theta}(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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper closes the classical junta distribution learning gap with a tight quadratic improvement and opens quantum junta states with concrete bounds.

read the letter

The main results are a sample bound of O(2^k log n / ε²) for learning k-junta distributions that matches the COLT'16 lower bound in every parameter, plus the first explicit bounds for learning quantum k-junta states (O(12^k log n / ε²) upper, Ω(4^k + log n / ε²) lower) and a corollary for learning QAC0 circuits via their Choi states being close to juntas. The classical improvement comes from a tighter analysis of support identification followed by estimation on the relevant coordinates. The quantum definition treats the state as a k-qubit piece tensored with maximally mixed on the rest, and the bounds follow from standard low-dimensional estimation plus information-theoretic arguments. The QAC0 claim is a direct remark that the prior Pauli-spectrum concentration already implies junta closeness for the Choi state, which upgrades the sample complexity from n to the exponential of log terms. The work is straightforward and extends the cited papers without circularity. The classical bound is a clean match to the lower bound. The quantum bounds leave a constant-factor gap in the 2^k term, which is typical and not a load-bearing issue. The testing result for constant k requiring Θ(2^n / ε²) copies is consistent with needing to probe the full space. Minor soft spots are that the 12^k constant could probably be improved with more care, and the QAC0 application inherits whatever looseness exists in the STOC'24 concentration result. Nothing here looks invented or overclaimed from the abstract and the stress-test note. This is for people in quantum property testing and learning theory who care about junta structure or low-depth circuits. It deserves a serious referee because the classical result is tight and the quantum direction is new with verifiable bounds. I would send it to peer review.

Referee Report

0 major / 3 minor

Summary. The manuscript studies three related learning problems. For classical k-junta distributions over {-1,1}^n it claims an upper bound of O(2^k log n / ε²) samples to achieve total-variation error ε, quadratically improving Aliakbarpour et al. (COLT'16) and matching their lower bound in every parameter. For the newly defined k-junta quantum states (tensor product of a k-qubit state and an (n-k)-qubit maximally mixed state) it gives an upper bound of O(12^k log n / ε²) copies for trace-distance error ε together with a lower bound of Ω((4^k + log n)/ε²); for constant k it also gives a tight Θ̃(2^n / ε²) bound for testing k-junta states. Finally, it observes that the Choi states of QAC^0 circuits (size s, depth d, a ancillas) are close to juntas by the Pauli-spectrum concentration of Nadimpalli et al. (STOC'24), yielding a learning algorithm that uses only 2^{O(log(s² 2^a)^d)} log n copies of the Choi state, improving the prior n^{O(log(s² 2^a)^d)} bound.

Significance. If the stated bounds hold, the work supplies nearly tight sample complexities for learning low-junta objects in both classical and quantum settings and supplies a useful reduction from QAC^0 learning to junta-state learning. The classical result closes the quadratic gap left by prior work while matching the information-theoretic lower bound in all parameters; the quantum results introduce a natural definition and obtain upper and lower bounds that differ only by a small constant factor in the 2^k term. The QAC^0 corollary is a direct and clean consequence of existing spectrum concentration. These contributions are of clear interest to the quantum learning-theory community.

minor comments (3)

Abstract, item (3): the exponent notation 2^{O(log(s^22^a)^d)} is ambiguous; explicitly parenthesize to clarify whether the logarithm is raised to the d power or the entire expression is inside the logarithm.
The definition of a quantum junta state (tensor product of a k-qubit state and maximally mixed state on the remaining qubits) should be stated verbatim in the introduction or the first section that introduces the concept, rather than only by reference to the classical case.
The testing result for constant-k junta states is stated only in the abstract; a brief pointer to the relevant theorem or section would help readers locate the argument.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, recognition of the significance of our results, and recommendation for minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity in claimed derivations

full rationale

The paper derives new sample-complexity upper bounds for learning k-junta distributions (O(2^k log n / ε²)) and quantum k-junta states (O(12^k log n / ε²)), plus a matching classical lower bound from external work and a quantum lower bound of Ω((4^k + log n)/ε²) proved directly in the paper. The QAC⁰ learning result is presented as a corollary of an external citation (Nadimpalli et al. STOC'24) on Pauli-spectrum concentration. All load-bearing steps rely on standard techniques (support identification for distributions, shadow tomography or direct estimation on relevant subsystems for states) rather than any self-definition, fitted-input renaming, or self-citation chain. The cited prior results are independent and externally verifiable; no equation or claim reduces to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The paper introduces the new concept of quantum junta states and relies on standard concentration and learning-theory tools to obtain the stated sample bounds; no numerical parameters are fitted to data.

axioms (1)

domain assumption Standard concentration inequalities and union bounds from learning theory suffice to obtain the stated sample complexities
Invoked to derive the O(2^k log n / ε²) and O(12^k log n / ε²) upper bounds from the abstract.

invented entities (1)

quantum junta state no independent evidence
purpose: Quantum analog of a classical k-junta distribution defined as tensor product of k-qubit state and (n-k)-qubit maximally mixed state
New definition introduced to initiate the quantum learning study; no independent evidence supplied beyond the definition itself.

pith-pipeline@v0.9.0 · 5980 in / 1455 out tokens · 54529 ms · 2026-05-23T18:39:38.765143+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We show that they can be learned with to error ε in total variation distance from O(2^k log(n)/ε²) samples... Pauli spectrum of QAC0 circuits is concentrated on low-degree... Choi states of those circuits are close to be juntas.
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Our techniques are based on Fourier and Pauli analysis, and our learning upper bounds are a refinement of the low degree algorithm by Linial, Mansour, and Nisan.

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.