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
u(n) and is surjective onto
U(n) via Givens rotations, enabling Haar initialization. Two-body correlator readouts achieve gradient variance
Θ(k3/n5), 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
∼1015 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(n2) gradients from
4kn circuit evaluations per step, a factor
n/k reduction over the standard rule's
4n2, growing linearly with
n at fixed
k.
The unitary butterfly targets all-to-all hardware, with
2logn layers of parallel gates and
(3/2)nlogn parameters, similar hardness guarantees, and
4klogn 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
Θ(k3/n5) rate needs a conjectured scalar comparison with the two-particle Haar second moment.
We study exact evaluation of the arithmetized
k-Orthogonal Vectors polynomial
FOVk of Ball et al. (2017, 2018). For every fixed integer
k≥3, set
d(n)=⌈log2n⌉. Assuming the basic decision version of Quantum Strong Exponential-Time Hypothesis (QSETH), for every constant
ε>0, no uniform quantum algorithm runs in
O(nk/2−ε) time on every input and evaluates this polynomial correctly with probability at least
3/4 over a uniformly random input in
Fp(n)knd(n) and the algorithm's internal randomness, for all sufficiently large
n. This holds when
p(n) is the smallest prime greater than
nk−1 and when it is the smallest prime greater than
nk. Our direct reduction combines classical polynomial self-correction with calls to a quantum average-case evaluator. For the smaller prime, random sampling finds an orthogonal tuple with constant probability whenever the count is large enough to wrap around modulo
p(n); otherwise, the exact residue determines the answer. For the larger prime, quantum minimum finding and an asymptotic prime-gap bound account for the cost of generating the prescribed field. In view of prior isolation-based reductions permitting small characteristics, we present these results as explicit reductions for the two canonical-prime families, with all setup costs included in the uniform quantum running time. The hardness guarantee concerns single-instance exact evaluation; a matching quantum evaluation algorithm and a quantum proof-of-work protocol remain open.
Polynomial transformations of data encoded in quantum operations are a building block of quantum algorithms, and their query complexity measures how often those operations are used. For multiple variables, existing methods either realize restricted polynomial families or implement monomials separately at a query cost exponential in the number of variables. We present a quantum circuit that implements every multivariate trigonometric polynomial up to an explicit normalization. The circuit processes one variable coherently over the frequency components of the remaining variables, allowing all components to share the same signal queries. Each variable is queried exactly as many times as its degree in the polynomial, and we prove that this query complexity is optimal. We further extend the construction to commuting unitaries. The resulting circuit applies the multivariate polynomial simultaneously across their shared eigenbasis, using the minimum numbers of forward and inverse queries to each unitary. We also study trainable rotations with fixed preparation and a local readout of the last input. At query depth at least two, independent uniform initialization gives every active readout gradient a variance lower bound set by its squared branch weight and the inverse square root of the depth, uniformly over data states and dimensions. For supervised squared loss, retaining sample correlations gives an initialization gradient-variance bound in terms of targets and input spectra. This also bounds the expected loss decrease after the first exact gradient step with a specified step size. These results provide a scalable and practical solution for developing multivariate quantum algorithms and quantum learning models.
Whether a fermionic variational quantum algorithm offers a genuine quantum advantage depends on whether its outputs are classically hard to compute. We show that for such algorithms classical simulability is not an intrinsic property of the circuit. It depends on the fermion-to-qubit encoding. Standard encodings are related by Clifford transformations, so they form a gauge group, and we classify the standard simulability resources by how they transform under it. The Pauli weight, the causal-cone width, and the entanglement that sets the cost of tensor-network contraction are gauge-covariant: a generic interacting Hamiltonian whose truncated Pauli-propagation cost grows linearly in the system size under the Jordan-Wigner encoding becomes logarithmic under a tree encoding, and we exhibit the resulting change of verdict at a fixed physical ansatz. The dynamical-Lie-algebra dimension and the non-stabilizerness are gauge-invariant. From this split we prove that the encoding-optimized simulation cost isbounded by the invariant resources, so genuine, encoding-robust hardness requires both the dynamical Lie algebra and the magic to be large; the covariant weight is necessary but never sufficient. These routes are sufficient certificates of simulability, not a complete characterization, so the floor is an upper bound and a full classification of representation-invariant cost functionals is left open. We confirm both invariant simulation routes numerically, and we show that the dynamical-Lie-algebra dimension separates simulable from hard instances where the Pauli weight cannot; we also construct an explicit one-parameter interacting family for which all three certificate routes fail at once, so the floor is achieved. We then establish a sharp dichotomy with trainability. Because the cost landscape is encoding-invariant, the gradient and the barren-plateau variance are exactly gauge-invariant, which we verify to machine precision; we show further that this invariance follows from faithfulness rather than Clifford-equivalence and is robust even to symmetry tapering, so trainability can be altered only by changing what the dynamics explores, such as restricting the ansatz, never by relabeling the qubits. One may therefore re-encode a fermionic circuit to make it easier to simulate, but never to make it easier to train. These results reframe advantage claims for fermionic ansatze: an advantage that isnot gauge-invariant is an artifact of the encoding
Variational quantum algorithms are a leading approach to near-term quantum computing, but their scalability can be limited by barren plateaus and the sampling cost of resolving small changes in the loss landscape. Here, we study the trainability of passive linear-optical quantum circuits and introduce a framework based on the ratio of sample variance to circuit variance. This ratio determines the number of circuit samples required to resolve local loss differences and gradients to proportional accuracy. We apply this framework to photon-number observables and identify both trainable and non-trainable regimes. Supported by analytic results and a numerically observed polynomial decay of the circuit variance, we find that fixed-order photon-number polynomials require only polynomially many samples as the system size grows, whereas high-order polynomials and observables based on output probabilities generally require exponentially many samples. Within the trainable regime, we further identify classes of observables in which quantum estimation achieves a polynomial speed-up over multiple classical methods. Within this family, neural network observables provide one practical construction that allow measurement outcomes to be efficiently processed into the desired polynomial. These results establish photonic variational quantum computing as a promising platform for near-term applications.
Solving the ground state and the ground-state properties of quantum many-body systems is generically a hard task for classical algorithms. For a family of Hamiltonians defined on an m -dimensional space of physical parameters, the ground state and its properties at an arbitrary parameter configuration can be predicted via a machine learning protocol up to a prescribed prediction error ɛ , provided that a sample set (of size N ) of the states can be efficiently prepared and measured. In a recent work [Huang , ], a rigorous guarantee for such a generalization was proved. Unfortunately, an exponential scaling for the provable sample complexity, N = m O ( 1 ɛ ) , was found to be universal for generic gapped Hamiltonians. This result applies to the situation where the dimension of the parameter space is large, while the scaling with the accuracy is not an urgent factor, not entering the realm of more precise learning and prediction. In this work, we consider an alternative relevant scenario, where the effective dimension m is a finite, not necessarily large constant, while the scaling with the prediction error becomes the central concern. By jointly preserving the fundamental properties of density matrices in the learning protocol and utilizing the continuity of quantum states in the parameter range of interest, we rigorously obtain a polynomial sample complexity for predicting quantum many-body states and their properties, with respect to the prediction error ɛ and the number of qubits, n , with N = poly ( ɛ − 1 , n , ln 1 δ ) , where poly denotes a polynomial function, and ( 1 − δ ) is the probability of success. Moreover, if restricted to learning local quantum-state properties, the number of samples can be further reduced to N = poly ( ɛ − 1 , ln n δ ) . Numerical demonstrations confirm our findings, and an alternative approach utilizing statistical learning theory with reproducing kernel Hilbert space achieves consistent results. The mere continuity assumption indicates that our results are not restricted to gapped Hamiltonian systems and properties within the same phase. Published by the American Physical Society 2024