Research map / Learning theory and algorithms / Sample complexity

Characterizing Trainability of Instantaneous Quantum Polynomial Circuit Born Machine

NeurIPS 2026 · Learning theory and algorithms › Sample complexity · approach: Neural network approximation theory

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Analyzes barren plateaus in IQP quantum circuit Born machines trained with MMD loss, deriving closed-form gradient variances via a critical rank, and shows sparse Erdős–Rényi IQP circuits can be both anti-concentrated/hard to sample and trainable at low-weight frequencies.

Problem

Whether IQP-QCBMs trained with an MMD loss suffer barren plateaus at initialization, and whether trainable regimes overlap with regimes of classically hard sampling (potential quantum advantage).

Approach

Derives closed-form variances of characteristic-function values and MMD partial derivatives for IQP circuits, showing they depend only on the critical rank (F2-rank of anticommuting generators); uses kernel spectrum choice to avoid BP and shows Gaussian small-variance initialization ensures polynomial gradient scaling.

Key results

• Var[C^a] = 2^{-r^a} under uniform initialization, with partial-derivative variance 2^{2-r^a}, so BP is governed by the critical rank.
• For sparse Erdős–Rényi IQP circuits with p=c ln(n)/n and c>2, expected sum over frequencies of 2^{-r^a} is 2+o(1), implying L2 anti-concentration.
• Under Gaussian initialization with gamma^2=c/D, gradient variance for frequencies overlapping a generator is Omega(poly(n^{-1})), so no barren plateau in this sense.

Surprising findings

• Sparse Erdős–Rényi IQP circuits can be simultaneously anti-concentrated (hard to sample classically) and trainable at low-weight frequencies, contrary to the claim that anticoncentration implies non-trainability.
• Gaussian initialization, which avoids barren plateaus, concentrates gates near identity and may make circuits more classically simulable.

Limitations

• Trainability is shown at initialization only, not during optimization.
• Trainability guarantees rely on a symmetric i.i.d. initialization assumption and an unstructured target ensemble assumption.
• Average-case lower bounds depend on assumed target distribution ensemble properties; no numerical experiments reported in the text.

Experimental setup

Metrics: gradient variance critical rank collision probability

Builds on: IQP-QCBM maximum mean discrepancy sparse IQP circuits barren plateau theory

Closest papers by meaning

• On the Relation between Trainability and Dequantization of Variational Quantum Learning Models (ICLR 2025 · similarity 0.89)
• Non-asymptotic Approximation Error Bounds of Parameterized Quantum Circuits (NeurIPS 2024 · similarity 0.87)
• Circuit Design and Efficient Simulation of Quantum Inner Product and Empirical Studies of Its Effect on Near-Term Hybrid Quantum-Classic Machine Learning (CVPR 2024 · similarity 0.87)
• Exponential Hardness of Optimization from the Locality in Quantum Neural Networks (AAAI 2024 · similarity 0.87)
• Training-Free Quantum Architecture Search (AAAI 2024 · similarity 0.87)
• Generating Universal Adversarial Perturbations for Quantum Classifiers (AAAI 2024 · similarity 0.86)