CS Paper Radar

Hidden selection rules and amplitude ceilings in quantum Fourier models

Pavel Sulimov, Claude Lehmann

cs.LG quant-ph ·submitted 2026-10-31 22:26 UTC · v1
benchmark

Abstract

Quantum models with Pauli data encodings compute trigonometric polynomials whatever channels, ancillas and outcome-averaged measurements follow, so their expressivity depends on the Fourier coefficients a circuit can reach. We identify two kinds of structure that settle this before training. An antiunitary time-reversal rule and a unitary reflection rule remove frequencies. For gate-level circuits, deciding whether such a rule exists reduces to a linear system over GF(2), solvable in polynomial time, and the time-reversal rule holds in 17.6% of 6,120 configurations of standard templates. Single-upload encodings cap the top coefficient at $2^{-m}$ for every channel, and we compute the tight ceiling for every frequency and a depth-independent re-uploading bound. Frozen before training, these bounds were never violated on a non-linearity benchmark, and they predicted trained performance on real data. On IBM processors the rule held on a 65-qubit chain, and we switched rule-breaking relaxation noise on and off by design.

Closest papers

Nearest neighbours by meaning across the whole index.

A Tutorial on Quantum Amplitude Embedding with Data Re-Uploading

cs.AI quant-phcs.LG ·2026-10-13 ·Hyojun Ahn, Joongheon Kim
similarity 0.71
Abstract · 6 pages, 6 figures, 3 tables. Submitted to ICEIC 2027

Amplitude embedding lets a variational quantum model read many classical features with few qubits, but the model output is then only a quadratic form in the normalized input. Data re-uploading, which encodes the input repeatedly between trainable blocks, can be used to enrich such a model. Because every additional upload of an amplitude embedding repeats a costly state preparation, the gain that an upload buys has to be known before the gates are spent. This tutorial thus addresses the problem of explaining what data re-uploading adds to an amplitude-embedded model and how large the gain is. We express sequential re-uploading and parallel re-uploading with two copies in one notation and show that each upload raises the reachable polynomial order by two. Under one trainable circuit family and one budget of trainable parameters, simulation results show that re-uploading raises the test coefficient of determination from 0.689 to between 0.883 and 0.975 on targets of order four and from 0.337 to between 0.642 and 0.783 on targets of order six, on all ten seeds. On a quadratic target and on handwritten digits, one upload remains the best choice, and every additional upload lowers the gate error that the classifier tolerates. These results help designers match the number of uploads to the polynomial order of the task at hand.

0.32

Same Spectrum, Harder First-Order Training: Phase-Locking in Single- versus Multi-Qubit Re-Uploading Circuits

cs.LG quant-ph ·2026-10-15 ·Michael Poppel, David Bucher, Maximilian Zorn, Markus Baumann, Sebastian Wölckert +3 more
theory similarity 0.68
Abstract

Angle-encoded variational quantum circuits implement truncated Fourier series. For one-dimensional inputs, a single-qubit re-uploading (serial) circuit represents every function that a multi-qubit circuit with the same encoding budget $E$ can; we find that this exchange of width for depth is not free in first-order training. Because its state lives on the Bloch sphere, all parameters of the serial circuit move the state, at each input, along one complex direction, which we call \emph{phase-locking}. We prove that this costs no Fourier direction but leaves no direction to spare: however many parameters it has, the serial circuit has at most $2E+2$ tangent directions, one more than its $2E+1$ Fourier coefficients need, while a two-qubit control with the same encoding budget and model class generically has at least $6E+6$. The cost in training is measured against this control, as the number of runs out of 100 that reach the optimum within a fixed step budget. On an exact loss with flat-spectrum targets the gap grows with $E$; at $E=32$ the serial circuit converges in 3, 53 and 83 runs under gradient descent, Adam and Levenberg--Marquardt, the control in 99, 100 and 100. On three real-world series, at matched parameter counts, the serial circuit reaches the least-squares optimum in at most 9 runs under Adam and in 32 to 93 under Levenberg--Marquardt, the control in at least 98 and in all 100; its held-out error is up to about $1.5$ times that of the control under Adam, but no larger in the typical run under Levenberg--Marquardt.

0.28

Margin-Based Generalization for Quantum Machine Learning with Classical Data Encoding

cs.LG quant-ph ·2026-10-17 ·Ju-Young Ryu, Tak Hur, Daniel K. Park
similarity 0.66
Abstract · 22 pages, 6 figures, 7 tables

Understanding generalization is essential for assessing the practical viability of quantum machine learning. In many applications, quantum models operate on classical data that must first be encoded into quantum states, making the encoding part of the effective hypothesis class. We develop a margin-based generalization framework for this setting, covering both fixed and trainable quantum data encodings. For fixed encodings, the existing margin bound transfers unchanged. For trainable encodings, we derive a bound using a two-scale covering argument that combines the original margin-dependent term with an additive encoding-capacity term of order $\tilde O(\sqrt{L/m})$, where $L$ is the number of trainable encoding parameters and $m$ is the training-sample size. Across 19,440 simulated training runs spanning various image datasets, circuit architectures, and optimization settings, the inverse margin performs best among five baseline and two bound-derived complexity measures under conditional-independence and 90th-percentile sign-error criteria, within bootstrap uncertainty. These results provide a unified margin-based view of generalization in quantum machine learning with classical data.

0.14

Empirical Evaluation of Quantum Kernel Methods for Classification: A Comparative Study with Classical Kernels

cs.LG quant-ph ·2026-10-30 ·Ronak Bhalgami
position similarity 0.64
Abstract

Quantum kernel methods are the most concrete near-term proposal for quantum machine learning on classical data, yet published benchmarks disagree on whether they outperform tuned classical kernels, and the disagreement cannot be resolved from the literature because the comparisons are not protocol-controlled. We argue that the obstacle is one of measurement, not theory: the usual setup fixes the quantum feature map's data scaling while grid-searching the classical kernel's hyperparameters, recomputes nothing per fold, and reports cost in simulator time. We therefore treat the comparison itself as the object of study and impose three controls. The bandwidth is tuned on the same grid budget as the classical $γ$, the kernel is recomputed inside every fold from fold-fitted preprocessing, and cost is counted in hardware circuit evaluations. On top of these we run a factorial design of 324 cells in which dimensionality, training size, class separability and data structure are explicit covariates, together with four standard datasets, a shots-versus-gate-noise ablation, and a cost sweep. The dominant effect we measure is not quantum: tuning the feature map's bandwidth is worth 0.120 accuracy on synthetic data and 0.339 on real data, exceeding every quantum-classical difference we observe. Tuned quantum kernels are then statistically indistinguishable from a tuned RBF on all four real datasets. The advantage on synthetic data is confined almost entirely to data generated by the feature map itself, and it shrinks with dimensionality (-0.0045 per qubit) while growing with sample size. Finite sampling costs an order of magnitude more accuracy than gate and readout noise, and a fidelity kernel needs $5\times10^{7}$ circuits at n = 10,000. Protocol variance is thus sufficient to explain the field's contradictory conclusions.

0.03

Classical Limits of Spectral Filtering in Quantum Generative Models

cs.LG quant-ph ·2026-08-14 ·Marco Roth
similarity 0.64
Abstract · 12 (main text) + 8 pages (appendix and references), 3 figures

Spectral filtering has been proposed as a route to regularization in quantum generative models: the quantum Fourier transform exposes the amplitude spectrum of a quantum circuit Born machine, and a diagonal filter suppresses the high frequencies associated with finite-sample noise, an operation whose classical counterpart seemingly requires manipulating an exponentially long amplitude vector. We examine whether this coherent operation produces anything that classical post-processing of samples from the unfiltered model cannot match. Measuring the filter against convolution with a symmetric probability kernel at matched sampling cost, which accounts for the post-selection overhead of attenuation, we derive necessary and sufficient conditions for the gap between the two to vanish. Magnitude (attenuating) filters obey a dichotomy: at a fixed affordability threshold, the filtered output is either a constant-size Fourier object with an efficient classical sampler, or the passband must widen until no fixed frequency is attenuated and the filter no longer smooths. In neither case does the filter create a quantum-classical separation. Whatever separation survives is inherited from the spectral phase of the input state. Numerical experiments on trained circuit Born machines confirm the classification and show that the deciding phases are invisible to the Born-rule training loss and set by the initialization. Within the diagonal family, pure phase filters remain the only spectral operations exempt from these constraints.

0.10

Sparse Walsh-Pauli Correlation Encoding for MaxCut: A Quantum-Inspired Formulation with Quantum-Hardware Validation

cs.ET quant-ph ·2026-09-08 ·Cesar Augusto do Amaral, Nicolás Legnazzi, Marcos Vinicius Reballo, Marcus Ritt, Alexsandro Santos da Rosa Júnior +1 more
similarity 0.64
Abstract

We introduce a sparse Walsh-Pauli correlation encoding for MaxCut, in which graph variables are represented by diagonal Pauli-string expectation values computed classically as normalized XOR autocorrelations of Walsh coefficients. The complete Walsh basis can reproduce the diagonal correlators of arbitrary quantum states, while a structured sparse support reduces the number of trainable coefficients to $m+1$ for $m$ graph variables. We evaluate the method on $1{,}400$ held-out random graphs with up to $7{,}000$ vertices, obtaining empirical approximation ratios near $0.98$ relative to MQLib heuristic references. On Gset instances G14, G23, G60, and G64, the sparse model achieves mean refined approximation ratios of $0.9828$, $0.9926$, $0.9781$, and $0.9369$, respectively, with $80.4\%$-$89.3\%$ fewer parameters than the complete Walsh representation. The trained coefficients are transferred without retraining to quantum circuits. Statevector simulations of the four Gset instances achieve fidelities above $0.99994$ and preserve all correlator signs. Separately, a seven-qubit experiment on a $15$-vertex graph executed on IBM quantum hardware achieves a correlator-sign agreement of $0.927\pm0.049$ relative to the corresponding noiseless circuit. These results demonstrate the potential of sparse Walsh-PCE for large-instance quantum-inspired MaxCut optimization while validating the transfer of classically trained parameters to quantum hardware.

0.25

Beyond the Mean Gap: What Transferred-Angle QAOA Retains on a Superconducting Processor

cs.AI quant-ph ·2026-11-07 ·Sanim Yousuf Fahim, Mohammad Arif Hossain
similarity 0.64
Abstract

Hardware executions of the quantum approximate optimization algorithm (QAOA) are often validated by comparing the device's mean cost with a simulation, a check that can miss what matters for optimization. Under global depolarization, the mean normalized gap and the floor-corrected probability of every set of bitstrings, the optimum included, retain the same fraction of their noiseless improvement over uniform sampling. We test this prediction with depth-2, transferred-angle QAOA circuits for binary subproblems of an alternating-direction decomposition on the IBM Heron processor \texttt{ibm\_marrakesh}, with and without dynamical decoupling and twirling. At 12 qubits, the main-family circuits retained 29\% to 46\% of their mean-gap improvement but only 5\% to 15\% of their probability of the optimum, lower on at least nine of ten instances per run. Near-optimal bitstrings were lost about as much as the optimum, whereas the avoidance of poor bitstrings was retained best. In the first submission, a device-matched noise model reproduced the pattern but overestimated the retention of the optimum five- to eightfold. On a rugged planted family, the device found the optimum in 62\% of 768-shot blocks (noiseless: 98\%), within the range of local heuristics. Validations of optimization circuits should report retention of the optimum and of near-optimal sets.

0.26

Exponential quantum advantages for decoded quantum interferometry in the streaming setting

cs.CC quant-phcs.DS ·2026-10-01 ·Kewen Wu, Guangxu Yang
theoryhot direction similarity 0.64
Abstract

Decoded quantum interferometry (DQI) is a polynomial-time quantum algorithm introduced by Jordan et al. (Nature 2025). For a natural optimization problem, known as optimal polynomial intersection (OPI), it achieves approximation guarantees in regimes where all known classical algorithms require exponential time. Besides time, space is another central resource: storing and manipulating a massive input can be very challenging, especially when logical qubits carry substantial fault-tolerant implementation overhead. This motivates the following question: does DQI yield quantum advantages in memory, and can we prove it unconditionally? We give an affirmative answer to this question in the streaming setting. In particular, we consider a natural generalization of OPI using Hermite interpolation and Hasse derivatives, which asks for a low-degree polynomial satisfying as many constraints on its values and derivatives as possible. As a concrete example, we show [Quantum efficiency.] An adaptation of the DQI algorithm produces a polynomial satisfying $93\%$ of the constraints; moreover, it only reads the input stream in one pass, uses polylogarithmic space, and has polylogarithmic computation time per stream entry. [Classical hardness.] Any classical algorithm that produces an answer satisfying just $76\%$ of the constraints requires polynomial space, even if it can read the input stream with polynomially many passes and can use unlimited time. Our result provides a complete tradeoff curve for the tunable parameters, and implies that DQI has provable quantum advantages for the original OPI problem.

0.51