Late fusion is an efficient, noise-robust, self-characterizing alternative to reconstruction for circuit-cutting QML and claims advantage over classical machine learning - consistent with recent benchmarking, quantum offers no accuracy edge on these datasets.
Abstract
Circuit cutting lets a large quantum neural network (QNN) run as independent subcircuits on small devices, but rebuilding its outputs by reconstruction carries a classical sampling overhead exponential in the number of cuts - the dominant runtime cost in prior work. We ask whether, for machine-learning tasks, this step is necessary, and replace it with late fusion: each subcircuit is trained and measured independently, and a small classical head combines their outputs - a linear-cost, decision-level combination borrowed from multimodal learning. To characterize the trade-off we introduce a quantumness dial $Q$, a tunable reconstruction budget interpolating from pure fusion to full reconstruction, and a cut-entanglement diagnostic that indicates how much reconstruction a task needs (Spearman $\rho=0.59$ over $104$ runs). Across synthetic and standard datasets, independently trained late fusion matches full reconstruction accuracy within $0.04$ at every point of the controlled sweep and on every classical benchmark, at exponentially lower cost; it is also markedly more robust to shot and device noise. Controlled entangled-data experiments locate the boundary where fusion must fail. We do not claim advantage over classical machine learning - consistent with recent benchmarking, quantum offers no accuracy edge on these datasets. Late fusion is thus an efficient, noise-robust, self-characterizing alternative to reconstruction for circuit-cutting QML.
Designing scalable parameterized quantum circuits for machine learning faces three obstacles: barren plateaus, the absence of 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 $k$ is a tunable dial trading classical simulation 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 $\Theta(k^3/n^5)$, polynomial in $n$ throughout $n-2k=\Omega(n)$. Expressive. Classical hardness is controlled by $k$: best-known classical sampling algorithms run in time $2^{\Theta(k)}\mathrm{poly}(n)$, worst-case #P-hardness holds from $k=n^{\epsilon}$, and the average-case machinery of Fermion Sampling applies at $k=\Theta(n)$. At our operating point $k=60$, best-known classical simulation exceeds $10^{24}$ operations at every $n$. Efficient. A multi-layer parallel parameter-shift rule computes all $O(n^2)$ gradients from $4kn$ circuit evaluations per gradient step, a factor $n/k$ reduction over the $4n^2$ evaluations of the standard rule, growing linearly with $n$ at fixed $k$. The unitary butterfly variant targets all-to-all hardware, with depth $2\log n$ and $(3/2)n\log n$ parameters, similar hardness guarantees, and $4k\log n$ evaluations per gradient step -- the same factor-$n/k$ reduction. Its trainability holds at two levels: absence of exponential barren plateaus is unconditional, while the sharp $\Theta(k^3/n^5)$ rate holds under a two-particle approximate-2-design conjecture.
Variational quantum circuits have been central to many proposed near-term applications of quantum computing, but a growing body of evidence suggests that trainability and quantum advantage are fundamentally at odds: ans\"atze expressive enough to resist efficient classical simulation tend to exhibit barren plateaus, while structures that provably rule out barren plateaus typically render them classically simulable. We propose a stacked linear combination of unitaries (S-LCU) as a variational ansatz which provides a tunable trade-off between barren plateaus and classical simulability. Using a diagrammatic analysis, we bound the loss-landscape variance of the Free Fermion S-LCU, whose elements are fermionic Gaussian unitaries. We prove a variance lower bound of $\Omega(1/(n k^{3l}))$, with a simulation cost of $O(k^{2l} n^3)$ using the best known classical algorithm, compared to a quantum gate complexity of only $O(lkn^2)$. The number of layers $l$ serves as a single dial that trades computational complexity against the rate of cost concentration. This offers practitioners a systematic method for constructing ans\"atze with a complexity-trainability trade-off that best suits their application and hardware.
Quantum reservoirs offer a hardware-friendly route to quantum machine learning, replacing trainable circuits with fixed random dynamics and a classical readout. Because the reservoir is not optimized, performance depends entirely on the choice of reservoir family, yet existing diagnostics demand resources that grow exponentially with system size. We introduce a scalable, hardware-agnostic framework built on two complementary quantities. The first is a task-independent order-statistics (ORS) expressivity score, which compares only the largest output probabilities of a reservoir ensemble against an analytical Haar baseline. It never reconstructs the full output distribution, is cost-independent of Hilbert-space dimension, and admits a closed-form depolarizing noise correction, making it directly usable on hardware. The second is the task-dependent effective rank $R_{\mathrm{eff}}$ of the feature matrix, which measures how much input-dependent information reaches the readout. We validate the ORS score against established complexity diagnostics and confirm it remains informative under simulated noise and on IBM quantum hardware. Across synthetic and real quantum extreme learning machine and quantum reservoir computing benchmarks, ORS captures the intrinsic expressivity hierarchy of reservoir families while $R_{\mathrm{eff}}$ determines when that expressivity becomes usable predictive information.
L. Domingo, Oriol Balló-Gimbernat, Fernando Vilariño· 0 citations
Quantum algorithms are conventionally presented with their input state supplied for free. When the input is classical data, this convention conceals a cost that is frequently larger than the algorithm it precedes. We review what the three standard encodings, such as basis encoding, amplitude encoding, and Grover--Rudolph distribution loading, actually cost once transpiled to a hardware gate set, and argue that the resulting $\Theta(N)$ bound is a counting theorem rather than an engineering limitation that improved hardware will remove. Measured gate counts for a representative loading task are reported: an optimal library implementation requires $247$ CNOT gates at $n=8$ qubits and doubles with each additional qubit, while the classical preprocessing that produces the rotation angles requires reading the entire input vector. We show how this cost eliminates the quadratic advantage of quantum amplitude estimation for Monte Carlo integration, and argue that the same accounting constrains quantum machine learning more broadly: the strong input models that make quantum algorithms fast on classical data also enable classical dequantization, and quantum kernel methods carry a $\Theta(M^2)$ state-preparation cost for the Gram matrix that does not amortize. We explain that the efficiently preparable states, device-generated distributions, variationally learned loading, and amortized preparation are required to get advantage from quantum machine learning and close with a checklist for evaluating input-dependent advantage claims. Executable notebooks reproducing every construction and measurement discussed here are available.
We examine the classical-cost claim for the triplet-block two-body readout in arXiv:2607.24014v1. The Gaussian-state expansion used there gives an $O(2^{2k/3}\mathrm{poly}(n))$ classical algorithm, but it is not necessary for fixed-body observables. The triplet-block input has an explicitly computable diagonal two-particle reduced density matrix, which passive fermionic linear optics propagates through $\bigwedge^2 W$. This gives a deterministic $O(n^4)$ algorithm for the complete correlator vector $(\langle n_i n_j\rangle)_{i<j}$, independently of $k$ and the fermionic-linear-optics extent. More generally, every number-conserving fixed-$r$-body expectation is polynomially computable whenever the input $r$-particle reduced density matrix is classically available; if that matrix is diagonal, all diagonal correlators are computable in $O(n^{2r})$ time. This invalidates the algorithm-relative exponential-cost conclusion for the supervised two-body readout, without affecting the gradient-variance, barren-plateau, parameter-shift, or sampling-hardness results.