Scalable Quantum Machine Learning: Trainability, Expressivity and Efficiency

Abstract

Scalable parameterized quantum circuits for machine learning face three obstacles: barren plateaus, no guarantee the learned function class is classically hard, and prohibitive circuit evaluations per gradient step. We propose the unitary brick-wall: a $k$-particle fermionic architecture for nearest-neighbor hardware, combining Reconfigurable Beam Splitters with interleaved single-qubit phases and a non-Gaussian magic-state encoding, where $k$ trades classical hardness against training cost. Trainable. The brick-wall has dynamical Lie algebra $\mathfrak{u}(n)$ and is surjective onto $U(n)$ via Givens rotations, enabling Haar initialization. Two-body correlator readouts achieve gradient variance $Θ(k^3/n^5)$, polynomial in $n$ throughout $n-2k=Ω(n)$. Expressive. Hardness is controlled by $k$: best-known classical sampling runs in time $2^{Θ(k)}$, worst-case #P-hardness holds from $k=n^ε$, and the average-case machinery of Fermion Sampling applies at $k=Θ(n)$. The sampler is input-dependent, so costs are paid per query: at our operating point $k=100$ one query needs $\sim 10^{15}$ operations, beyond commercial query rates, and at $k=120$ an exascale machine sustains under one query per second. Efficient. A multi-layer parallel parameter-shift rule computes all $O(n^2)$ gradients from $4kn$ circuit evaluations per step, a factor $n/k$ reduction over the standard rule's $4n^2$, growing linearly with $n$ at fixed $k$. The unitary butterfly targets all-to-all hardware, with $2\log n$ layers of parallel gates and $(3/2)n\log n$ parameters, similar hardness guarantees, and $4k\log n$ evaluations per step -- the same factor-$n/k$ reduction. Its trainability holds at two levels: absence of exponential barren plateaus is unconditional, while the sharp $Θ(k^3/n^5)$ rate needs a conjectured scalar comparison with the two-particle Haar second moment.