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.
We establish efficient learning for a family of fermionic magic states under unknown number-conserving free-fermion evolution. Each input block has a definite particle number and is a superposition of Fock states, with occupied mode sets disjoint both within and across blocks. The key idea is to exploit the spectral structure of particle reduced density matrices (RDMs) to separate contributions from individual blocks from those involving several blocks, allowing us to reconstruct the hidden block structure. For a fixed upper bound on the particle number per block, our algorithm uses single-copy measurements and polynomial sample and classical computational complexity to recover a compact description of the state with prescribed fidelity and high probability, without prior knowledge of the block decomposition or the evolution. RDMs up to this upper bound suffice for reconstruction. We further show that this RDM order is necessary in general: two orthogonal states in the family can have identical RDMs at every lower order. These results show that an extensive number of non-Gaussian blocks can be compatible with efficient state learning.