Bernstein-Vazirani Networks: Quantum Machine Learning by Interference

Natacha Kuete Meli; Tolga Birdal; Prayag Tiwari; Vladislav Golyanik; Michael Moeller

Source-linked AI summary

Bernstein-Vazirani Networks: Quantum Machine Learning by Interference

Natacha Kuete Meli, Tolga Birdal, Prayag Tiwari, Vladislav Golyanik, Michael Moeller

arXiv:2608.19043v1Aug 19, 2026quant-phcs.AIcs.CVcs.LG

TL;DR

Quantum machine learning often relies on variational circuits with architectural and trainability challenges. BVNs instead use interference in standard or problem-adapted bases, achieving strong classification and image-fitting performance while avoiding gradient-based training.

Problem
Quantum machine learning lacks broadly expressive, trainable alternatives to variational circuits, while practical functions may not fit restricted linear-parity bases.
Method
BVNs infer target functions by interfering labelled data in standard or problem-adapted bases, using overcomplete interference to provide universal approximation without gradient-based parameter optimisation.
Results
Nearly 100% classification accuracy used 50% of training data, while image fitting reached close to 40 dB PSNR and often outperformed quantum and classical baselines.
Takeaways & Limitations
Generalised BVNs provide an interference-based QML framework with strong cross-task performance and reduced measurement cost relative to standard and variational approaches.
Takeaways & Limitations
On real-world Iris and Penguins data, generalised BVNs exhibit spectral leakage, while rectangle representations can introduce artefacts and hurt interpolation.

Abstract

from arXiv · show

We introduce Bernstein-Vazirani Networks (BVNs), a non-variational quantum machine learning framework that leverages quantum interference for supervised learning, demonstrated on vision and representation learning tasks. In their standard form, BVNs follow the principle of quantum Fourier sampling: labelled data are placed in superposition and interfered in the Fourier basis to extract globally informative features. We then define generalised BVNs that enable interference in problem-adapted bases, yielding more expressive models under the same measurement budget as in the standard setting. BVNs achieve universal function approximation through (over)complete interference bases, while training of BVNs is gradient-free. Experiments on synthetic and real-world classification tasks, as well as implicit image representation, show strong generalisation capabilities and competitive performance with classical and quantum baselines.

1. Introduction

BVNs address the practical trainability gap in QML by using quantum interference to discover basis functions from labelled data without variational loss optimization. Generalised BVNs extend this framework with expressive problem-adapted bases, while coefficient reconstruction addresses leakage and experiments cover classification and image fitting.

Introduction: Existing QML models commonly rely on parametrised quantum circuits, whose barren plateaus and costly gradient evaluation expose a gap between theoretical expressivity and practical efficiency.Barren plateaus are regions where gradients vanish exponentially with system size (McClean et al., 2018).
Introduction: Generalised BVNs interfere in alternative problem-adapted bases, producing more expressive features while reducing the required measurement budget.Their richer basis functions improve data fitting under the same measurement budget as the standard framework.
Introduction: BVNs avoid variational parameter optimization with respect to a loss function and infer configurations solely from labelled data.Interference samples multiple high-quality parameter configurations, which are aggregated to approximate the target function and address leakage.
Introduction: BVNs use quantum interference to discover dominant basis functions for efficient function approximation in machine learning tasks.They repurpose the Bernstein–Vazirani algorithm, which uses labelled examples in superposition to reveal basis functions explaining the training data.
Introduction: Ridge-regression coefficient reconstruction addresses leakage by recovering the best approximation of the target function in the sampled basis.This reconstruction aggregates sampled basis functions into the final approximation.
Introduction: BVNs are validated on synthetic and real-world classification tasks and 2D image-fitting tasks, performing on par with MLP, SVM, and a single-qubit classifier while being more sampling-efficient than PQCs.The classification experiments include the Iris and Penguins datasets.

2. Related Works

The review situates QML at the intersection of quantum computing and neural networks, contrasting dominant variational PQC-based models with interference-based learning inspired by quantum algorithms (Biamonte et al., 2017; Schuld & Petruccione, 2018; Cerezo et al., 2022). It also surveys QNN design principles and representative classification and implicit-representation applications.

Quantum Neural Network Designs: Early QNN work proposed fixed-length bitstring inputs, neural-like connections and updates, and quantum-consistent evolution using superposition, entanglement, and interference (Schuld et al., 2014).These requirements motivated elementary QNN architectures, including quantum neurons with ancillary registers (Cao et al.,
Quantum Neural Network Designs: Interference-based QML follows a quantum-algorithm blueprint: encode labelled information in superposition, interfere in Fourier space, and measure (Wakeham & Schuld, 2024).Wakeham and Schuld draw this approach from Deutsch–Jozsa (Deutsch & Jozsa, 1992) and Shor’s algorithm.
Variational Quantum Neural Networks: Variational QML developed trainable PQC architectures with task-specific expressivity and inductive biases, including Fourier-series models, entanglement-pattern analyses, and quantum convolutional neural networks (P´erez-Salinas et al., 2020; Schuld et al., 2021; Sim et al., 2019; Cong et al., 2019).Schuld and Petruccione formalised supervised learning by embedding classical data into quantum states and optimising PQCs.
Variational Quantum Neural Networks: The paper contrasts dominant PQC-based QML, whose optimisation can suffer from barren plateaus, with its gradient-free use of quantum interference.PQC models embed classical data into quantum states and optimise parametrised circuits, whereas the proposed approach eliminates classical outer-loop optimisation.
Applications: Representative QML applications include classification and implicit representation; the Single-Qubit Classifier assigns classes to Bloch-sphere regions and uses data re-uploading for Fourier-based function approximation (P´erez-Salinas et al., 2020).The SQC trains PQCs to cluster input states in corresponding class representations.

3. Motivation

The motivation frames supervised learning as representing an unknown function in a learned basis, then asks whether quantum resources can identify a compact, accurate subset from an exponentially large basis. BVNs address this through superposition and interference while avoiding several limitations of gradient-based PQC training.

3. Motivation: Supervised learning approximates an unknown function f from labelled training pairs using a parameterised model N with optimised parameters θ.
3. Motivation: Neural networks represent the target function f in a learned basis formed by last-hidden-layer functions {ϕ_j}, with output weights combining those basis functions.
3. Motivation: Quantum computing is motivated for machine learning because access to high-dimensional Hilbert spaces may offer advantages when expressive basis functions lift data into higher-dimensional spaces (Schuld et al., 2014; Cerezo et al., 2022).
3. Motivation: The central question is whether learning can select a reasonably sized subset from a high-dimensional basis that approximates f sufficiently well, with |S| ≪ |{ϕ_j}|.
3. Motivation: BVNs exploit superposition and interference to sample indexed basis functions from an exponentially large basis with probabilities proportional to their representation weights, while avoiding several gradient-based PQC-training limitations.

4. (Generalised) Bernstein–Vazirani Networks

Generalised Bernstein–Vazirani Networks extend interference-based Fourier sampling beyond linear parity bases by adapting the interference operator and input representation. The resulting architecture samples expressive, potentially overcomplete basis functions and reconstructs their coefficients from training data.

Generalisation axes: The generalisation addresses dense Fourier spectra by combining alternative interference operators with nonlinear, parameter-dependent input representations.Changing the interference operator supplies alternative features, while auxiliary registers construct nonlinear representations aligned with the target function’s inductive biases.
The Method: Generalised BVNs prepare superpositions of inputs and representation parameters, query labels as amplitudes, and interfere the resulting function values before sampling basis functions.The construction uses input, representation, and weight registers, following the three stages of preparation, oracle querying, and interference.
Reconstructing the Coefficients: Because the extended basis can be overcomplete and non-orthonormal, sampled coefficients are reconstructed by fitting the basis evaluations to training targets with appropriate scaling.Sampling identifies dominant correlations but not overall scale; coefficient reconstruction uses the training-set matrix of basis evaluations and target values.
The Generalised Bernstein–Vazirani Network: Generalised BVNs replace restrictive parity hidden units with expressive sub-models whose outputs are implicitly ensembled through interference amplitudes.Standard BVNs use parity activations and aggregate them according to Fourier coefficients, whereas generalised BVNs use optimised components χ_yzt(x).
Resource-efficient representations: Under qubit constraints, structured rectangle representations activate parameter-dependent hyper-rectangles, locally modifying the standard BV basis after interference.The rectangle representation is resource-efficient and its implementation details and ablations are discussed in Appendix E.

5. Experimental Results

Experiments evaluate BVNs across synthetic and real-world classification, sanity-check tasks, and implicit image representation. Generalised BVNs consistently improve over standard BVNs, while showing strong accuracy and competitive representation quality under limited data or shots.

Experimental scope: The experimental suite spans hand-crafted sanity checks, synthetic 2D and real-world 4D classification, and implicit image representation at sizes suitable for classical simulation.Complexity comparisons and ablation studies are addressed in later sections.
5.1 Sanity-check tasks: Generalised BVNs outperform standard BVNs, achieving 100% accuracy versus approximately 70% with Chebyshev interference using only 100 shots.The classification regions were selected to match the expressive basis functions, making the target directly representable in the generalised basis.
5.2 Classification: On synthetic 2D datasets, BVNs learn decision boundaries with nearly 100% accuracy using only 50% of the training data, while outperforming classical baselines on high-variation shapes.Increasing λ improves low-split generalisation; Chebyshev outperforms Hadamard, and generalised BVNs outperform standard BVNs.
5.2 Classification: Filled data substantially improves real-world 4D classification, enabling generalised BVNs to exceed 90% accuracy with only 25% of the data, comparable to baselines.Unfilled data produce poor generalisation because sparse training samples are small relative to the Hilbert-space dimension; λ = 0.1 is used for the reported results.
5.3 Implicit image representation: For implicit image representation, BVNs are trained on 64×64 images and evaluated on 128×128 grids, reporting PSNR and MSE against classical and quantum baselines.Using 10,000 shots demonstrates representation of high-frequency signals, while ablations show visually good results with 1,000 shots; generalised BVNs outperform standard BVNs.

6. Computational Complexity

BVNs have favorable resource scaling, with data loading and training requiring substantially fewer shots and runtime than PQC benchmarks. Their approximation error is controlled by the unsampled spectrum, with generalized bases trading non-orthogonality against expressive representation.

Circuit and reconstruction costs: Labelled dataset encoding costs O(mn), rectangle representations cost O(nn_t) gates, operator application costs O(n) or O(n + n^2), and coefficient reconstruction costs O(mk(c+k +1)+k^3).These costs correspond respectively to m samples and n qubits, input and parameter resolutions n and n_t, Hadamard or Chebyshev operators, and k sampled states.
Approximation error: For standard BVNs, approximation error equals the squared norm of the unsampled spectrum, whereas generalized BVNs satisfy ϵ ≤ λ_max(Ḡ_Ω)∥b_F̄_Ω∥^2.The standard expression assumes an orthonormal basis, while generalized BVNs induce generally overcomplete, non-orthogonal bases.
Approximation error: Generalized BVNs trade stronger basis correlations, which increase λ_max(Ḡ_Ω), against richer representations that can substantially reduce the residual norm ∥b_F̄_Ω∥^2.Thus, non-orthogonality penalizes approximation error while expressive representations can lower the unsampled residual.
Resource comparison: BVNs are significantly more efficient than benchmark models in shots and runtime, with data loading scaling as O(mn) × n_shots versus PQC training scaling as O(mn) × (2^c · p · e).Table 2 compares expected parameter-shift shot counts and back-propagation runtime across models.

7. Ablations

The ablations show that generalised BVNs remain performant across dummy-fill settings and that interference-based basis selection consistently outperforms uniform random sampling. Theoretical and empirical analyses attribute this advantage to efficient identification of informative basis functions, especially in low-shot regimes.

Dummy filling: Generalised BVNs remain performant across a wide range of dummy-fill values and fractions, whereas benchmark methods fail because filling creates severe class imbalance.The ablation varies dummy-fill value and fraction, with (0, 0) denoting unfilled data and (4, 1) the setting used in Figure 5.
Interference ablation: The interference ablation replaces quantum-selected basis functions with uniformly random functions of identical cardinality while keeping coefficient reconstruction unchanged.This isolates the contribution of quantum interference to basis-function selection.
Expected coverage: Uniform sampling does not benefit from additional qubits at the input-feature level: its marginal probability of observing a distinct input feature remains 1/2^n.For N random draws, the resulting coverage analysis shows that covering a constant fraction of the input space requires exponentially many shots in n.
Empirical evidence: The empirical comparison evaluates average classification accuracy on synthetic and real-world datasets and PSNR on image fitting across the corresponding experiments.These evaluations use results from Figures 4–6 to compare BVN-selected and uniformly sampled basis functions.
Interference versus random sampling: BVNs consistently outperform random sampling, with the advantage amplified as the search space grows and remaining evident in low-shot regimes (N = 100, 1000).The comparison uses N = 100 shots for synthetic and real-world tasks; for image fitting, random sampling reaches ∼23 dB PSNR only with 10^4 shots.

8. Practical Recipe for BVNs

BVN design should align the induced interference basis with the target function. In practice, choose task-appropriate operators and representations, then tune parameter resolution to balance spectral concentration and expressivity.

Design principle: Choose the interference operator, representation, and parameter resolution so the induced basis aligns with the target function.These are the central design choices for adapting BVNs to a given application.
Representation choice: Generalised representations can sparsify functions, potentially reducing a function requiring two BV basis states to one χ basis state.This occurs when χyzt(x) = √mξy(x)ξz(ηt(x)) is suitably chosen.
Spectrum reshaping: Generalised BVNs can reshape spectra, redistributing coefficients so smaller informative components become more accessible to sampling.A standard 95/100 coefficient split can make the smaller informative component unlikely to be sampled.
Practical heuristic: Use assumed data structure to guide choices: convolutional architectures for images, attention mechanisms for sequences, and resolution adjustments for expressivity.The practical heuristic is to concentrate the target spectrum, encode task-specific structures or invariances, and vary parameter resolution.

9. Conclusion … D. Layered Expressive Representation

BVNs provide a gradient-free, interference-based alternative to variational QML, with generalised models improving fitting and reducing measurement cost. The appendix formalises the interference and basis constructions and shows that a restricted layered representation remains insufficiently expressive.

9. Conclusion: Generalised BVNs achieved nearly 100% classification accuracy with 50% of the training data and close to 40 dB PSNR on image fitting, surpassing the standard model.These results motivate generalised BVNs as an interference-based alternative to variational QML that incorporates inductive bias while reducing measurement cost.
9. Conclusion: Generalised BVNs perform well on synthetic data but exhibit spectral leakage when scaled to real-world datasets such as Iris and Penguins.The paper identifies basis engineering aligned with the data manifold as a possible remedy, while noting that rectangle representations can introduce artefacts and hurt interpolation.
Appendix: The appendix provides supplementary technical details and experiments covering the interference derivation, Fourier expansion, generalised bases, and layered expressive representations.It complements the main text rather than introducing a separate empirical conclusion.
A. Interference in Bernstein–Vazirani: The Bernstein–Vazirani interference mechanism makes undesired outputs interfere destructively while the desired solution interferes constructively.The Fourier sum evaluates to 1 only when the measured string matches the hidden string and otherwise evaluates to 0.
B. Proof of the Fourier Expansion Theorem: The Fourier expansion theorem follows by expressing functions uniquely in an orthonormal basis, with the 2^n characters matching the dimension of the function space.The character set therefore forms an orthonormal basis for real-valued functions on {0,1}^n.
C. Alternative Derivation of (Generalised) Bernstein–Vazirani Networks from a Linear Algebraic Perspective: Generalised BVNs use an overcomplete basis when m ≥ n, recovering the standard BV setting for m = n and extending expressivity through ancillary qubits.Measuring in the adapted basis reveals basis elements with probability |⟨g_y, f⟩|^2, while the corresponding basis unitary implements the measurement.
D. Layered Expressive Representation: The layered expressive representation implements a reversible classical two-layer MLP through quantum layers containing output registers, activations, and weight registers.The construction uses coherent weighted updates and may require ancillary qubits for reversible arithmetic.
D. Layered Expressive Representation: The tested binary two-hidden-unit representation produced only seven or three distinct 2D partitions and did not significantly improve image fitting over standard BVNs.The experiment used binary weights, no biases, fixed thresholds, and a circuit-size-limited two-layer architecture.

E. Rectangle Expressive Representation … G.1. Dataset-Encoding and Oracle Complexities

Generalised BVNs use rectangle activations and problem-adapted interference bases to improve local expressivity and fitting accuracy, while retaining sparse, gradient-free reconstruction and data-loading costs characterized by the effective training-set size.

E. Rectangle Expressive Representation: Rectangle activation overcomes bias-free MLP limitations by combining binary input registers, local mask registers, shared accumulation, and simultaneous superposition over inputs and rectangles.Overlapping rectangles use a superposition register and conditional shifts, creating localised, resource-efficient activation patterns without biases.
E. Rectangle Expressive Representation: The generalised model converges faster and captures finer image details than the standard BVN, with finer rectangle resolution producing better results.Each rectangle locally modifies the standard BV basis toward a better fit; sufficient shots make the generalised model more accurate than the standard model.
F. Interference Operators in Comparison: Chebyshev and Hadamard interference operators both fit regression variations, but Chebyshev produces smoother real-domain outputs while Hadamard produces step-like functions from binary-domain rounding.The generalised model better captures high-frequency variations and reduces oscillations around step-function targets through locally corrected rectangular bases.
G. Computational Complexity: Rectangle representations with input resolution n and parameter resolution n_t require O(nn_t) gates, while Hadamard interference requires O(n) gates on n qubits.The rectangle circuit uses n_t controlled adders and inverses plus a Toffoli gate; coefficient reconstruction constructs X at cost O(cmk).
G. Computational Complexity: Coefficient reconstruction is not prohibitively expensive in practice, with runtime comparable to one classical training epoch because it requires a single pass over the training set.
G.1. Dataset-Encoding and Oracle Complexities: BVN dataset and oracle loading uses amplitude encoding of label-weighted input superpositions, with sparse-state preparation scaling as O(mn) for m nonzero entries.For Iris and Penguins, m is far smaller than the 2^n-dimensional Hilbert space, yielding highly sparse encoded vectors.
G.1. Dataset-Encoding and Oracle Complexities: The effective path count k for dummy-filled states is expected to scale mainly with m because large constant-amplitude regions contain only a few data-dependent deviations.Compared with variational QML, parameter-shift derivatives require repeated O(mn) state preparations, shots, parameters, and training iterations.

G.2. Sample Complexity Analysis

BVN shot complexity is governed by target-function sparsity in the chosen basis, not approximation accuracy or input dimension. Generalised BVNs trade a Gram-matrix penalty for potentially smaller residual spectra, empirically yielding lower errors than standard BVNs.

Shot complexity: The number of measurement shots depends on the target function’s sparsity in the chosen basis χ, rather than directly transferring to approximation accuracy or depending on input dimension.
Standard BVN: For standard BVNs, orthonormality makes the approximation error equal to the norm of the unsampled Fourier spectrum, so error is determined entirely by unsampled spectral mass.The standard basis has Gram matrix G = I.
Generalised BVN: For generalised BVNs, non-orthogonal overcomplete bases bound error by λmax(G¯Ω)∥bF¯Ω∥2, introducing a correlation penalty alongside potentially more compact representations.More correlated basis functions increase λmax(G¯Ω), while the richer representation can substantially reduce the residual-coefficient norm.
Empirical shots-versus-accuracy: Figure 7 shows consistently lower approximation errors for generalised BVNs, indicating that reduced residual-coefficient norms outweigh the additional Gram-matrix penalty.The comparison is attributed to shots-versus-accuracy results, with the reduction in ∥bF¯Ω∥2 dominating the additional factor.

H. Inspecting the Sampled Coefficients

The coefficient histograms compare standard and generalised BVNs on synthetic, Iris, and Penguins classification datasets. Standard BVNs reveal approximation difficulty through sparsity, whereas generalised BVNs produce nonsparse coefficients by replicating dominant basis functions with local modifications.

Coefficient histograms are inspected for standard and generalised BVNs across 2D synthetic, Iris, and Penguins classification datasets.
Sparse standard-BVN histograms indicate that a target function is relatively easy to approximate with finitely many shots, while dispersed histograms signal greater difficulty.The spiral dataset exhibits more dispersed histograms.
Generalised BVNs produce nonsparse histograms because they extend the standard BV basis by generating locally modified copies of dominant BV functions.

I. Comparing Filled and Unfilled Training Data … J.2. Apodised Activation Functions

Filled training data substantially improves generalised BVN performance on Iris and Penguins, while unfilled data generalise poorly. The proposed extensions address basis misalignment and activation-induced spectral leakage through adaptive basis alignment and apodised activations.

I. Comparing Filled and Unfilled Training Data: Coefficient histograms for standard and generalised BV methods on Iris and Penguins show dispersed, non-concentrated magnitudes.This observation accompanies the filled-versus-unfilled analysis but does not establish a performance winner.
I. Comparing Filled and Unfilled Training Data: The dataset is filled because fewer than 500 training samples embedded in a 1016-dimensional Hilbert space cause sampling leakage, and additional λ values are evaluated.The comparison is motivated by the mismatch between the small training set and the large encoded space.
J. Future Work and Technical Extensions: Generalised BVNs remain challenged by spectral leakage and shot complexity when scaling from synthetic data to complex real-world distributions such as Iris and Penguins.The proposed extensions target these difficulties and the misalignment between discrete hard-edged quantum bases and continuous natural-data geometry.
J.1. Adaptive Basis Alignment: Adaptive basis alignment applies a parametrised unitary V(θ) to the parameter register before interference, aligning the basis with the dataset’s principal manifolds.A classical pre-training loop minimises the Shannon-entropy cost L(θ) to maximise sparsity in P(y, z, t|θ).
I. Comparing Filled and Unfilled Training Data: Filled data enable the generalised model to exceed 90% accuracy with only 25% training data, whereas unfilled data generalise poorly and degrade the standard model.The dummy fill-label substantially improves the generalised model but causes the standard model to assign the dummy label uniformly, overwhelming true training samples.
J.2. Apodised Activation Functions: The rectangle activation χrect(x) produces high-frequency leakage through the Gibbs phenomenon, motivating apodised activations.The proposed replacement removes binary thresholding in the activation step.
J.2. Apodised Activation Functions: Controlled rotations CRy(ϕ) replace multi-controlled Toffoli gates to implement soft trapezoidal windows whose boundary variation acts as a low-pass filter.The smooth boundary margin δ accelerates spectral decay to O(1/ω2) and concentrates signal energy.