2026/07/27 by Iordanis Kerenidis
#quant-ph
Designing scalable parameterized quantum circuits for machine learning faces three fundamental obstacles: barren plateaus that prevent gradient-based training, the absence of provable guarantees that 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 Splitter gates with interleaved single-qubit phase gates and a non-Gaussian magic-state encoding, where the particle number k is a tunable dial trading classical simulation hardness against training cost. Trainable. The brick-wall has dynamical Lie algebra \mathfraku(n) and directly parametrizes U(n) via Givens rotations, enabling Haar initialization. Two-body correlator readouts achieve gradient variance Θ(k2/n5). Expressive. Classical hardness is controlled by the particle number k: best-known classical algorithms for sampling and for two-body expectation values run in time 2Θ(k)poly(n), worst-case #P-hardness holds at k = nε, and average-case hardness applies at k = Θ(n). Efficient. A multi-layer parallel parameter-shift rule computes all O(n2) gradients from k(8n+4) circuit evaluations per gradient step, a factor 3n/(8k) reduction over the 3n2 evaluations required by the standard parameter-shift rule. The unitary butterfly variant targets all-to-all hardware, with depth 2log n and nlog n parameters. It achieves similar hardness guarantees at 8klog n evaluations per gradient step, the same factor 3n/(8k) reduction. Its trainability is established at two levels: the absence of exponential barren plateaus is unconditional, whereas the sharp Θ(k2/n5) rate holds under a two-particle approximate-2-design conjecture.