Paper deep dive

Bernstein-Vazirani Networks: Quantum Machine Learning by Interference

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

Year: 2026Venue: arXiv preprintArea: quant-phType: PreprintEmbeddings: 96

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 89%

Last extracted: 8/21/2026, 4:43:48 AM

Summary

The paper introduces Bernstein-Vazirani Networks (BVNs), a non-variational quantum machine learning framework that uses quantum interference for supervised learning. Unlike Parametrised Quantum Circuits (PQCs) that suffer from barren plateaus and require gradient-based optimization, BVNs leverage the Bernstein-Vazirani algorithm to sample basis functions via Fourier sampling. The authors propose 'Generalised BVNs' which use problem-adapted bases and expressive input representations to improve model expressivity and data fitting under the same measurement budget. The method is gradient-free, addressing the 'leakage' problem through ridge regression coefficient reconstruction. Experiments on synthetic and real-world classification tasks (Iris, Penguins) and image representation show competitive performance with classical and quantum baselines while being more sampling-efficient.

Entities (13)

Bernstein-Vazirani Networks · model · 98%Bernstein-Vazirani Algorithm · algorithm · 96%Generalised BVNs · model · 95%Barren Plateaus · problem · 93%Parametrised Quantum Circuits · model · 92%Fourier Sampling · technique · 90%Quantum Machine Learning · field · 90%ridge regression · technique · 88%IRIS Dataset · dataset · 85%Penguins Dataset · dataset · 85%Single-Qubit Classifier · model · 82%QIREN · model · 80%Quantum Visual Fields · model · 80%

Relation Signals (12)

Bernstein-Vazirani Networks → isa → Quantum Machine Learning Framework

confidence 95% · We introduce Bernstein-Vazirani Networks (BVNs), a non-variational quantum machine learning framework

Generalised BVNs → isa → Bernstein-Vazirani Networks

confidence 95% · We then define generalised BVNs that enable interference in problem-adapted bases

Bernstein-Vazirani Networks → isbasedon → Bernstein-Vazirani Algorithm

confidence 95% · we introduce Bernstein–Vazirani Networks (BVNs), which repurpose the Bernstein–Vazirani (BV) algorithm (5) for learning tasks.

Bernstein-Vazirani Networks → uses → Quantum Interference

confidence 95% · BVNs... leverages quantum interference for supervised learning

Bernstein-Vazirani Networks → isgradientfree → true

confidence 92% · training of BVNs is gradient-free.

Parametrised Quantum Circuits → suffersfrom → Barren Plateaus

confidence 92% · PQC optimisation is often hindered by barren plateaus

Bernstein-Vazirani Networks → avoids → Barren Plateaus

confidence 90% · avoiding issues such as local minima and barren plateaus.

Generalised BVNs → improves → expressivity

confidence 90% · yielding more expressive models under the same measurement budget as in the standard setting.

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract: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.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

93,632 characters extracted from source content.

Expand or collapse full text

Bernstein–Vazirani Networks: Quantum Machine Learning by Interference Abstract 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 baselines11 1 Project page: https://4dqv.mpi-inf.mpg.de/BVNs/. †footnotetext: denotes equal advising Natacha Kuete Meli1 Tolga Birdal2 Prayag Tiwari3 Vladislav Golyanik4,† Michael Moeller1,† 1Department of Vision and Graphics, University of Siegen 3School of Information Technology, Halmstad University 2Department of Computing, Imperial College London 44D and Quantum Vision, Max Planck Institute for Informatics 1 Introduction Quantum Machine Learning (QML) (6; 8) aims to exploit the high-dimensional Hilbert spaces of quantum systems coupled with quantum effects to build expressively powerful learning models. Most existing QML approaches typically rely on Parametrised Quantum Circuits (PQCs) and face significant architectural and trainability challenges. A central challenge is the mismatch between classical neural networks’ reliance on nonlinear activations and the linear, unitary dynamics of closed quantum systems, where nonlinearity is recoverable only through Boolean encodings, as noted by Herman et al. (15). In addition, PQC optimisation is often hindered by barren plateaus, i.e., regions of the loss landscape where gradients vanish exponentially with system size (20), and, even outside such regimes, by the complexity of certified gradient-evaluation methods (e.g., parameter-shift rules (31)) combined with measurement noise, imposing substantial overhead in the execution and sampling of quantum circuits. A recent study (29) further confirms this crisis in PQCs, estimating to 38 years the runtime of a single epoch of gradient descent with the parameter-shift rule on MNIST with a 10410^4‑parameter PQC, requiring ∼1015 10^15 measurement shots. These recent insights expose a tangible gap between the theoretical expressivity of quantum models and their practical efficiency to emulate neural networks, motivating alternative QML paradigms. f⁡(x)=∑yf^(y)χy(x) f(x)= _y f(y)\, _y(x) χy(x)=(−1)y⊙x _y(x)=(-1)^y x Standard BVN (a) Standard BVN f⁡(x)≈∑y,z,tf^(yzt)χyzt(x) f(x)≈ _y,z,t f(yzt)\, _yzt(x) χyzt(x)=more expressive feature _yzt(x)=more expressive feature Generalised BVN (b) Generalised BVN (c) 2D classification with BVNs Figure 1: The proposed standard (1(a)) and generalised (1(b)) Bernstein–Vazirani Networks (BVNs). In the standard setting, binary inputs xix_i are linearly combined in a hidden layer with optimised binary weights yjy^j, passed through a parity activation χ, and linearly combined at the output layer using Fourier coefficients f^(yj) f(y^j). In the generalised setting, inputs pass through expressive optimised sub-models χ (cartooned in the red box) before the output combination, enabling richer representations. (1(c)): Illustratively, we classify 2D points where the target function (left) is a sum of expressive sub-models χ of the generalised basis. The generalised model fits the boundaries exactly, while the standard model has not yet converged. “Acc.” denotes accuracy. See Secs. 4 and 5 for more details. From this perspective, it is instructive to revisit quantum algorithms that originally demonstrated provable advantages compared to classical counterparts, such as Shor (35), Deutsch–Jozsa (11) or Bernstein–Vazirani (5), which use quantum Fourier sampling to extract hidden structure via interference. Wakeham and Schuld (37) identify a common blueprint underlying such algorithms that can be repurposed for inference tasks: place labelled information in superposition via an oracle, interfere in the Fourier space, and measure. In this paradigm, learning is achieved via interference by sampling globally informative Fourier characters rather than via gradient-based optimisation, avoiding issues such as local minima and barren plateaus. This reframes learning alternatively as a problem of frequency discovery rather than parameter optimisation. Wakeham and Schuld, however, left unresolved the “leakage” problem that occurs when no single frequency fits the data perfectly, preventing them from validating the idea practically. Building on this blueprint, we introduce Bernstein–Vazirani Networks (BVNs), which repurpose the Bernstein–Vazirani (BV) algorithm (5) for learning tasks. The BV algorithm interferes labelled training examples placed in superposition to reveal a set of basis functions that explain the training data. We further generalise the standard BV framework—defining generalised BVNs—by allowing interference in alternative problem-adapted bases, enabling to sample more diverse and expressive features while reducing the required measurement budget. Importantly, quantum circuits in BVNs require no variational parameter optimisation with respect to a loss function and rely solely on labelled data to infer the underlying target function that explains the observations. The expressivity of our models stems from the exponentially large Hilbert space and the (over)completeness of the interference basis that enable universal function approximation. Intuitively, generalised BVNs can be viewed as expressive parametrised quantum architectures, in which all network parameter configurations are placed in superposition. Interference then highlights the configurations that best align with the structure induced by the labelled data. Rather than identifying a single optimal configuration, the algorithm samples multiple high-quality configurations, which are aggregated to approximate the target function, addressing the leakage problem. Each sampled configuration corresponds to a sub-network within a larger implicit ensemble, evaluated at the cost of a single sub-network instance and optimised through interference rather than gradient descent. An intuitive illustration of the proposed BVNs is shown in Figure 1 with a hand-crafted 2D point classification result, where the target function is a sum of basis functions unique to the generalised basis. After only 100 shots, the generalised BVN fits the decision boundaries precisely, whereas the not-yet-converged standard BVN smooths them. In summary, our key technical contributions are as follows: • Bernstein–Vazirani Networks (BVNs), a new class of QML models that leverage quantum interference to discover dominant basis functions for efficient function approximation in machine learning tasks; • Generalised BVNs that extend the standard framework with more expressive basis functions, improving data fitting under the same measurement budget. • Coefficient reconstruction via ridge regression to address the leakage problem and recover the best approximation of the target function in the sampled basis. Empirically, we validate our BVNs on several synthetic and real-world classification tasks (Iris (12) and Penguins (16) datasets), as well as 2D image-fitting tasks. Classification results demonstrate the ability of BVNs to learn decision boundaries and perform on par with classical (MLP, SVM) and quantum models (Single-Qubit Classifier (27)), while being far more sampling-efficient than PQC models. In line with this, our BVNs continue to perform accurately on image representation tasks, competing with classical models (MLP+RFF, SIREN (3)) and outperforming the recent PQC models (QIREN (40) and QVF (38)) in both accuracy and sampling cost. 2 Related Works Quantum Machine Learning (QML) (6; 32; 8) is driven by the idea of combining the power of quantum computing with the success of neural networks. We review key developments in the field and refer the reader to a recent survey for further details (21). Quantum Neural Network Designs. Schuld et al. (33), by surveying early work on Quantum Neural Networks (QNNs), outlined three requirements for QNNs: (i) a fixed-length bitstring initial state; (i) neural‑like connections and update rules; and (i) quantum‑consistent evolution exploiting effects such as superposition, entanglement, and interference. These requirements motivated several elementary QNN architectures, including quantum neurons with ancillary registers (7) and various quantum perceptron models (2; 10; 17). While replacing classical components with quantum counterparts is a reasonable direction, a central challenge in QML has long been the tension between the nonlinear, dissipative dynamics of neural computation and the linear, unitary dynamics of quantum mechanics (33). Herman et al. (15) showed that one way to bypass this issue is to map inputs to the Boolean cube. Yet, training their models still relies on a classical optimisation loop. Recently, Wakeham and Schuld (37) explored an alternative approach to QML drawn from quantum algorithms such as Deutsch–Jozsa (11) and Shor’s algorithm (35), rather than from classical neural networks. They highlight a common blueprint shared by these algorithms: place labelled information in superposition via an oracle, interfere in Fourier space, and measure. The authors then leverage this interference strategy for inference, by regarding a learning task as a hidden-subgroup problem in which interference should reveal the so-called “annihilator” that generated the data, i.e., the true oracle that produced the training examples. This perspective suggests a promising route toward genuinely quantum learning models by directly aligning inference with intrinsic quantum mechanisms. Wakeham and Schuld (37) left open how to handle leakage, i.e., loss of information when no perfect annihilator exists. We address this gap by drawing on the Bernstein–Vazirani algorithm (5), validating the approach on several learning tasks and showing how “leaked information” can be aggregated. Variational Quantum Neural Networks. Variational quantum neural networks implemented via Parametrised Quantum Circuits (PQCs) are the dominant paradigm in contemporary QML. Schuld and Petruccione (32) formalised supervised learning with quantum computers, introducing the embedding of classical data into quantum states and optimising PQCs as trainable models. Key developments include PQC architectures designed for specific expressivities and inductive biases. Notably, data re-uploading classifiers showed that a single qubit with repeated data encoding suffices for binary classification (27), later formalised as implementing a Fourier series (34). Further work analysed how entanglement patterns affect expressivity (36) and introduced quantum convolutional neural networks inspired by classical ones (9). A major challenge for PQCs is barren plateaus (18), where flat loss landscapes hinder optimisation. Only a few architectures, mostly group-equivariant models with built-in inductive biases (30; 19; 23) or shallow-depth PQCs, admit theoretical training guarantees. Our approach diverges fundamentally from this paradigm by eliminating classical outer-loop optimisation and instead exploiting quantum interference to determine network configurations. Applications. Representative supervised learning tasks for assessing QML models include classification and implicit representation. For classification, Salinas et al. introduced the Single-Qubit Classifier (SQC) (27), which associates target classes with specific regions of the Bloch sphere and trains PQCs to cluster input states in the corresponding class representations. The SQC employs data re-uploading to approximate functions through their Fourier representations. This Fourier-based perspective was later extended to Quantum Implicit Neural Representation (QIREN) by Zhao et al. (40), where PQCs learn a mapping from coordinates to signal values, such as those describing images or audio. More recently, Wang et al. (38) introduced Quantum Visual Fields (QVFs), a hybrid architecture in which a classical backbone extracts and normalises feature vectors that are subsequently processed by PQCs, improving the expressive capacity of the quantum model. 3 Motivation Supervised learning (25; 14) seeks to approximate an unknown function f from training pairs (xi,yi)i=1m\(x^i,y^i)\_i=1^m, where f⁡(xi)=yif(x^i)=y^i. This is typically achieved by a parameterised model N such that ⁡(xi,θ)≈f⁡(xi)N(x^i,θ)≈ f(x^i) for some optimal parameter set θ. This network N is often organised into layers, with an output layer aggregating the results of previous layers. We can express this as ⁡(x)=∑j=1kwjϕj(x),N(x)= _j=1^kw_j _j(x), (1) where ϕj(x) _j(x) denotes the output of the j-th neuron in the last hidden layer and wjw_j are the corresponding output weights (both collectively parametrised by θ). In essence, we are representing the target function f in a learned basis formed by the functions ϕjj=1k\ _j\_j=1^k produced before the output layer. Typically, training requires designing an expressive architecture N, performing multiple passes over the data, and optimising non-trivial loss functions. The expressive architecture is constructed so that the hidden layers, or basis functions ϕjj=1k\ _j\_j=1^k, lift the data into a higher-dimensional space, which in practice increases the number of parameters. For this reason, it is believed that QC, which can access high-dimensional Hilbert spaces, may offer advantages in ML, giving rise to QML (6; 33; 8). An interesting question we would like to answer is how to design a learning paradigm that, given access to the training dataset, can infer within a high-dimensional basis ϕj\ _j\ a reasonably sized subset ϕjj∈S\ _j\_j∈ S, |S|≪|ϕj||S| |\ _j\|, that approximates f via Equation 1 sufficiently well. Our BVNs operate at the natural intersection of learning and quantum computing in the sense that, by exploiting superposition and interference, they sample indexed basis functions from an exponentially large basis with probability proportional to the amplitudes of their weights in the representation of the target function f in that basis. These properties, together with the fact that BVNs (Section 4) avoid several fundamental limitations of gradient-based PQC training, make them a highly appealing learning paradigm. 4 (Generalised) Bernstein–Vazirani Networks We introduce our interference-based models, beginning with a warm-up on the Bernstein–Vazirani algorithm. Key symbols and notations used in this work are listed in Table 1. Table 1: List of symbols used in this paper. ℤ2nZ_2^n n-dimensional Boolean space, ℤ2n=0,1nZ_2^n=\0,1\^n ⊙ , ⊕ inner-product and sum mod2 2, respectively f~ f, f standard and generalised target function f^(⋅) f(·) Fourier coefficient of f H Hadamard transform I interference operator UfU_f oracle unitary for function f η expressive representation ξ, χ standard and generalised basis function ⟨| , |⟩ bra and ket, complex row and column vectors 4.1 Warm-up: The Bernstein–Vazirani Algorithm The Bernstein–Vazirani (BV) algorithm (5) is a celebrated example of quantum advantage. It solves the following problem: Given a Boolean function f~:ℤ2n→0,1 f:Z_2^n→\0,1\ that is promised to satisfy f~(x)=s⊙x=s⊤xmod2 f(x)=s x=s x 2 for an unknown s∈ℤ2ns _2^n, the goal is to recover s from observed pairs (x,f~(x))(x, f(x)). The algorithm, illustrated in Figure 2, has three steps: (i) starting from |0⟩⊗n 0 n, we apply H⊗nH n to create a uniform superposition over all basis states, i.e., inputs; (i) we query the oracle Uf~U_ f, which applies the phase (−1)f~(x)(-1) f(x) to each basis state in the superposition; (i) we apply H⊗nH n again to interfere with the phases. The corresponding states are |ψ1⟩ _1 =12n∑x∈ℤ2n|x⟩, = 1 2^n -2.84544pt _x _2^n x, (2) |ψ2⟩ _2 =12n∑x∈ℤ2n(−1)f~(x)|x⟩, = 1 2^n -2.84544pt _x _2^n(-1) f(x) x, (3) |ψ3⟩ _3 =∑y∈ℤ2nf^(y)|y⟩,f^(y)=12n∑x∈ℤ2n(−1)f~(x)+y⊙x. = _y _2^n -2.84544pt f(y) y, f(y) -2.84544pt= -2.84544pt 12^n -2.84544pt _x _2^n -2.84544pt(-1) f(x)+y x. (4) Substituting the promise f~(x)=s⊙x f(x)=s x into Equation 4 gives f^(y)=12n∑x∈ℤ2n(−1)(s⊕y)⊙x f(y)= 12^n _x _2^n(-1)^(s y) x, which equals 11 if and only if y=sy=s, hence 00 else (see Appendix A). In essence, thanks to interference, a single measurement of the system reveals s out of 2n2^n solutions with probability 11. Figure 2: The Bernstein–Vazirani algorithm (5). The algorithm mainly consists of three steps: (i) initialise the system in a perfect superposition; (i) call the function oracle; (i) apply the Hadamard operator for interference. If f~ f satisfies the promise f~(x)=s⊙x f(x)=s x, measuring reveals s with certainty. Quantum Fourier Sampling. The BV algorithm (5) generalises to Fourier sampling over ℤ2nZ_2^n: If the promise f~(x)=s⊙x f(x)=s x holds, we measure s with probability 11. If not, consider the function space ℱ:=f:ℤ2n→ℝF:=\f:Z_2^n \ and the functions χy(x)=(−1)y⊙x _y(x)=(-1)^y x, parameterised by y∈ℤ2ny _2^n, which encode the parity y⊙xy x. The set χyy∈ℤ2n\ _y\_y _2^n forms an orthonormal basis of ℱF with respect to the inner product ⟨f,g⟩=x∈ℤ2n[f⁡(x)g(x)] f,g=E_x _2^n[f(x)g(x)], and we refer to y∈ℤ2ny _2^n as a basis vector. It follows that f^(y)=12n∑x∈ℤ2nf⁡(x)χy(x) f(y)= 12^n _x _2^nf(x) _y(x) (5) are precisely the Fourier coefficients of f in this basis χ. Theorem 4.1 (Fourier expansion on ℤ2nZ_2^n, (26)). Any function f:ℤ2n→ℝf:Z_2^n admits a unique expansion as f⁡(x)=∑y∈ℤ2nf^(y)χy(x).f(x)= _y _2^n f(y)\, _y(x). (6) This is called the Fourier expansion of f, and the coefficients f^(y)∈ℝ f(y) are the Fourier coefficients of f in the basis χ. Proof. See Appendix B. ∎ As implied by Theorem 4.1 and Equations 2, 3 and 4, running the BV algorithm for f⁡(x)=(−1)f~(x)f(x)=(-1) f(x) or any other f yields basis vectors y∈ℤ2ny _2^n and corresponding functions χy∈ℱ _y that approximate f. Moreover, each y is sampled with probability equal to the squared of its Fourier coefficient |f^(y)|2| f(y)|^2, so components with large coefficients appear first. This operation is known as Fourier sampling (5). An alternative linear‑algebraic derivation of BVNs is given in Appendix C. A Neural View on the Bernstein–Vazirani Model. We can view the BV algorithm as a two-layer network, which we call a Bernstein–Vazirani Network (BVN) and depict in Figure 1(a). Hidden units compute parity activations χy(x)=(−1)y⊙x _y(x)=(-1)^y x on binary inputs xix_i weighted by yiy_i, and the output aggregates them with coefficients f^(y) f(y). If f satisfies the BV promise, a single hidden unit suffices; otherwise, multiple units contribute according to |f^(y)|2| f(y)|^2. Importantly, this network “growth” comes purely from superposition and measurement, without additional quantum resources. 4.2 Generalised Bernstein–Vazirani Networks The standard BV algorithm learns within a restricted hypothesis class: the basis elements χy _y are linear parity functions in ℤ2nZ_2^n, so the BV promise effectively assumes that f is linear. Most practical learning functions will fail this assumption, possessing dense rather than sparse Fourier spectra and requiring many samples for the approximation. Our goal in generalising the BV algorithm is to design task‑adaptive basis functions (i.e., the promise) with inductive biases that better align with the target function f. We achieve this along two complementary axes: • Interference Operator. In standard BVNs, the Hadamard operator induces low-expressivity parity activations. Replacing this alone directly implies alternative features. However, any alternative interference operator, being unitary, still primarily probes linear structure over ℤ2nZ_2^n. • Expressive Input Representations. To capture non-linearity, we enlarge the quantum system and construct non-linear representations of the input x in an auxiliary register prior to interference, making them potentially parameter-dependent to model implicit biases. Notation. We will call a unitary I an interference operator if its action on computational basis states x∈ℤ2nx _2^n induces a family of functions ξyy∈ℤ2n\ _y\_y _2^n via I|x⟩=∑y∈ℤ2nξy(x)|y⟩.I x= _y _2^n _y(x) y. (7) The Method. Figure 3: Our generalised Bernstein–Vazirani algorithm. We use three quantum registers: An input register, a register that computes a weighted representation of the inputs, and a weight register controlling this representation. The algorithm has three stages: (i) Prepare a uniform superposition of all inputs (Prep.) and weight configurations, and compute the representations; (i) Query the oracle encoding the ground‑truth labels across all samples in the superposition; (i) Apply an interference operator so the labels interfere with the basis functions generated by the representation. We now propose a principled algorithm for QML by interference, inducing our generalised BVNs. To obtain expressive basis functions, we allocate two registers in addition to the input register: One register that encodes a pre-processed representation ηt(x)∈ℤ2nη _t(x) _2^n_η of the inputs x∈ℤ2nx _2^n, and one register that stores the weights or parameters t∈ℤ2ntt _2^n_t associated with this representation. Our generalised construction, as illustrated in Figure 3, follows the three main steps of the Bernstein–Vazirani algorithm. The inputs of the algorithm are training pairs (x,f⁡(x))i=1m(x,f(x))_i=1^m; a function oracle UfU_f to label the inputs; and an interference operator I. The main steps are as follows: • The initial step puts all training samples and parameters of the expressive representation in uniform superposition, then runs the representation circuit: |ψ1′⟩ _1 =1m∑x|x⟩|0⟩|0⟩, = 1 m _x x 0 0, (8) |ψ1′⟩ _1 =1m2nt∑t∑x|x⟩|0⟩|t⟩, and = 1 m2^n_t _t _x x 0 t, and (9) |ψ1⟩ _1 =1m2nt∑t∑x|x⟩|ηt(x)⟩|t⟩. = 1 m2^n_t _t _x x _t(x) t. (10) • The second step queries the oracle to mark the ground-truth labels f⁡(x)f(x) as amplitudes on the inputs: |ψ2⟩=1m2nt∑t∑xf⁡(x)|x⟩|ηt(x)⟩|t⟩. _2= 1 m2^n_t _t _xf(x) x _t(x) t. (11) • The third step creates, from the input and representation registers, interference of the function values: |ψ3⟩=12nt∑yztf^(yzt)|y⟩|z⟩|t⟩, _3= 1 2^n_t _yzt f(yzt) y z t, (12) where f^(yzt) f(yzt) =1m∑xf⁡(x)χyzt(x), = 1m _xf(x) _yzt(x), (13) χyzt(x) _yzt(x) =mξy(x)ξz(ηt(x)). = m _y(x) _z( _t(x)). (14) Sampling Equation 12 yields, with probability |f^(yzt)/2nt|2| f(yzt)/ 2^n_t|^2, the dominant basis vectors y∈ℤ2ny _2^n, z∈ℤ2nηz _2^n_η, t∈ℤ2ntt _2^n_t, and thus the corresponding basis functions χyzt _yzt. Since the extended basis may be non‑orthonormal due to its over‑completeness relative to the effective number of training samples m, we must reconstruct each sampled coefficient f^(yzt) f(yzt), which is done efficiently as described next. Reconstructing the Coefficients. Let X∈ℝm×kX ^m× k denote the matrix of k basis evaluations on the training set, Xij=χj(xi)X_ij= _j(x_i). Let F∈ℝmF ^m be the vector of target values on the training set, and F^∈ℝk F ^k the vector of Fourier coefficients. We aim to recover F from the basis X, or the best approximation of f in χ. In fact, the coefficients F F need to be scaled properly, as the sampling has learned the dominant correlations but not the overall scaling. A standard approach to recover the coefficients is to solve the ridge regression problem minF^⁡‖F−XF^‖22+λ‖F^‖22 _ F\|F-X F\|_2^2+λ\| F\|_2^2 via the Gram matrix: G=X⊤X,F^←(G+λI)−1X⊤F,G=X X, F←(G+λ I)^-1X F, (15) for a regularisation factor λ∈ℝ+λ _+. In practice, this reconstruction is comparable to a single training epoch in classical models, as it involves a single pass over the training set. Making New Predictions. A new prediction on a data point x is made by evaluating f⁡(x)=∑yztf^(yzt)χyzt(x).f(x)= _yzt f(yzt) _yzt(x). (16) Our construction generalises the standard Bernstein–Vazirani algorithm in the sense that we sample BV basis functions ξy(x) _y(x) if ξz(ηt(x)) _z( _t(x)) is a constant for all x,zx,z, and t. A summarising pseudocode of our generalised BVNs is provided in Algorithm 1. Algorithm 1 Generalised Berstein–Vazirani Networks Algorithm 1 (Quantum Machine Learning by Interference) Input: Training pairs (x,f⁡(x))i=1m(x,f(x))_i=1^m; Function oracle UfU_f; Interference operator I; Number of shots nshots. while nshots not reached do Prepare superposition of inputs x via Equation 8. Prepare superposition parameters t via Equation 9. Compute representation ηt(x) _t(x) via Equation 10. Query function oracle UfU_f via Equation 11. Interfere the x and η registers via Equation 12. Measure basis states |y⟩|z⟩|t⟩\ y z t\. end while for Parameter configuration (y,z,t)∈|y⟩|z⟩|t⟩(y,z,t)∈\ y z t\ do Evaluate χyzt(⋅)=mξy(⋅)ξz(ηt(⋅)) _yzt(·)= m _y(·) _z( _t(·)) on training set. end for Compute Fourier coefficient f^(yzt) f(yzt) via Equation 15. Return: Fourier pairs (f^(yzt),χyzt)( f(yzt), _yzt). The Generalised Bernstein–Vazirani Network. The generalised BVN architecture is shown in Figure 1(b). Unlike standard BVNs, the hidden units are no longer simple parity functions but expressive sub-models. Inputs xix_i pass through a hidden layer of optimised components χyzt _yzt, whose predictions are aggregated at the output and weighted by the interference amplitudes f^(yzt) f(yzt). The architecture behaves similarly to an ensemble, but the ensemble is generated implicitly through interference rather than by training multiple models. Crucially, this rich ensemble incurs no additional quantum resource cost: only a single model is physically implemented, while the remaining effective models emerge purely through superposition and measurement. 4.3 The Expressive Representation of Inputs We now elaborate on our expressive representation η of the inputs. This representation is central to obtaining smooth, regularised models that generalise well. In principle (24, Section 1.4.1), any Boolean function on binary inputs can be computed coherently: there exists a unitary A (constructed from Toffoli and CNOT gates; and ancilla qubits) such that A|x⟩|0⟩|t⟩=|x⟩|ηt(x)⟩|t⟩.A x 0 t= x _t(x) t. (17) That is, as an expressive representation, we could mirror standard classical network architectures—whose effectiveness is well established—to construct η in a reversible quantum form. Appendix D discusses a quantum implementation of a classical 2-layer MLP with step activation functions and fixed biases. In practice, however, implementing A to mirror classical models requires ancilla qubits and uncomputation, and induces nontrivial circuit depths. Constrained by the available qubits, we introduce a structured, resource‑efficient rectangle representation ηrect _rect. For instance, since the standard BV basis is already complete, our rectangle representations activate parameter‑dependent hyper‑rectangles of the input domain. This has the effect, after interference, of modifying the BV basis locally on different rectangles. Implementation details and ablations are discussed in Appendix E. 4.4 The Interference Operator We lastly discuss three candidate interference operators: Hadamard, Fourier, and Chebyshev. The interference operator determines the hidden activation and model expressivity, e.g., Hadamard produces step-like patterns, while Fourier and Chebyshev yield smoother variations (see Appendix F). The Hadamard Transform. The Hadamard transform H (24) is the most natural interference operator on ℤ2nZ_2^n. It acts on a basis state |x⟩ x as H|x⟩=12n∑y∈ℤ2n(−1)x⊙y|y⟩,H x= 1 2^n _y _2^n(-1)^x y y, (18) where x and y are binary vectors. The phase factor (−1)x⊙y(-1)^x y encodes the parity of the binary inner product. The Hadamard transform is the Fourier transform on ℤ2nZ_2^n. The Fourier Transform. A more general Fourier transform F (24) arises when we embed ℤ2nZ_2^n into the complex vector space indexed by integers in ℤ2nZ_2^n. In this viewpoint, the x is interpreted as an integer in 0,…,2n−1\0,…,2^n-1\. The transform acts on basis states as F|x⟩=12n∑y∈ℤ2nei2πxy/2n|y⟩,F x= 1 2^n _y _2^ne^i2π xy/2^n y, (19) where xyxy denotes standard integer multiplication. The Chebyshev Transform. The Chebyshev transform T (39) constructs Chebyshev polynomials on discretised Chebyshev nodes. For continuous inputs x∈[−1,1]x∈[-1,1], Chebyshev polynomials are defined as χy(x)=cos⁡(yarccos⁡(x)) _y(x)= (y (x)). In the discrete setting, we view x∈ℤ2nx _2^n as an integer and map it to a Chebyshev node xch:=cos⁡(π⁡(2x+1)/2n+1)x^ch:= (π(2x+1)/2^n+1 ). Defining polynomials Ty(x):=cos⁡(yarccos⁡(xch))T_y(x):= (y (x^ch) ), the transform acts as T|x⟩=12n2T0(x)|0⟩+12n−12∑y∈ℤ2n∖0Ty(x)|y⟩.T x= 12 n2\,T_0(x) 0+ 12 n-12 _y _2^n \0\T_y(x) y. (20) 5 Experimental Results We validate our BVNs on several representative supervised learning tasks of adequate size for classical simulation, from hand‑crafted sanity-check tasks Section 5.1), through synthetic 2D and real‑world 4D classification (Section 5.2), to implicit image representation (Section 5.3). Section 6 analyses complexities and compares qubits, parameters, shots and runtime costs, with extended discussions covering the sampling complexity in Appendix G. Section 7 lastly performs ablation studies on the proposed BVNs. All quantum circuits, unless otherwise stated, are simulated noise‑free using Pennylane’s lightning.qubit (4) to investigate properties of the new paradigm. We compute on a conventional computer (AMD Ryzen 9 5900X 12-Core Processor CPU with 128GB RAM). The classification metric is the top-1 accuracy between ground-truths and rounded predictions. 5.1 Fitting the Expressive Representation in 2D In Figure 1(c) we demonstrate the efficiency of the generalised model over the standard one, constructing 2D classification tasks whose regions match our expressive basis functions, making the target directly representable in the generalised basis. With Chebyshev interference and only 100100 shots, the generalised BVN achieves 100%100\% accuracy, whereas the standard BVN reaches only ∼70% 70\%. 5.2 Classification in 2D and 4D We experiment with classification tasks. First, we solve binary classification in 2D on a variety of synthetic datasets shown in Figure 4(a), including the canonical blobs, moons, and a circle, as well as several hand-made shapes with different boundaries, yielding ten datasets S1-S10. Second, we classify the real-world Iris (12) (150150 samples) and Penguins (16) datasets (333333 samples), each consisting of 4D vectors across three classes (1,2,3). Data are normalised to the qubit grid. We benchmark our BVNs with Hadamard and Chebyshev operators against a classical 33-layer MLP baseline with 10 units per layer, a classical SVM model, and a 2020-layer universal quantum single-qubit classifier (SQC) (27). We vary the training set size (25%,50%,75%,100%25\%,50\%,75\%,100\%) and evaluate on the full datasets to assess how well the models generalise, i.e., learn the classification boundaries. Appendix H inspects sampled pairs (f^,χ)( f,χ). Results report the mean performance over five runs per model and dataset. Figure 4(b) presents the binary classification results in 2D. Our BVNs successfully learn the decision boundaries. With only 50%50\% of the training data, they reach nearly 100%100\% accuracy. In the low training split, we observe that increasing the regularisation parameter λ improves generalisation. The MLP, the SVM and single-qubit classifier baselines struggle on datasets with high variation (S2, S6, S9), whereas the BVN bases are expressive enough to capture high variations. The MLP’s behaviour reflects its spectral bias, and we conjecture that the SQC is constrained by its depth. Figure 5 shows the 4D results. Here, we observed that the small number of training samples (<500<500) relative to the large Hilbert‑space dimension (2162^16) leads to severe sampling leakage (37). Assigning a dummy non‑zero fill‑label to inputs outside the training set mitigated this issue. We use λ=0.1λ=0.1, refer to Appendix I for other values of λ and to Section 7.1 for Ablations on fill fraction and value. Unfilled data lead to poor generalisation, whereas filled data, while degrading the standard BVN, substantially improve the generalised BVN, bringing it on par with baselines. We attribute the SVM’s slightly better performance over the MLP to the small size of the datasets. (a) 2D datasets (b) Classification results Figure 4: Binary classification results on synthetic 2D datasets. The top and bottom rows show BVN results with Hadamard and Chebyshev interference, with columns specifying data fractions for training. Chebyshev outperforms Hadamard; the generalised BVN outperforms the standard BVN. BVNs outperform MLP, SVM, and SQC, particularly on high-frequency shapes (S2, S6, and S9). Figure 5: Real‑world classification results on Iris and Penguins datasets, with filled vs. unfilled (original) comparison for BVNs. Filled data substantially improves the generalised BVN, allowing >90%>90\% accuracy with only 25%25\% data, comparable to the baselines. 5.3 Implicit Image Representation We run BVNs with λ=0.1λ=0.1 and Chebyshev on implicit image representations. We benchmark against the classical MLP+RFF and SIREN models (3), and the quantum QIREN (40) and QVF (38) models. The models are trained on a coarse 64×64 image, evaluated on a finer 128×128 grid to assess interpolation, and we report PSNR and MSE. We use 10,000 shots to demonstrate that BVNs can represent high‑frequency signals. Ablations in Figures 10 and 13 show that even 1,000 shots yield good results visually. Figure 6 presents our results. Again, the generalised BVN outperforms the standard one and stands competitively alongside the baselines. While it does not always yield the highest PSNR, it is visually more regular and coherent. 6 Computational Complexity Our labelled dataset encoding in BVNs has a cost of O⁡(mn)O(mn) for m training samples and n qubits. The rectangle representations with input and parameter resolutions n and ntn_t yield O⁡(nnt)O(n_t) gates. The Hadamard (24) or Chebyshev (39) operator costs O⁡(n)O(n) or O⁡(n+n2)O(n+n^2) gates. Coefficient reconstruction scales as O⁡(mk(c+k+1)+k3)O(mk(c+k+1)+k^3) for k sampled states. We provide a full discussion in Appendix G. Figure 6: Implicit image representation. The top row shows results on the coarse (64×64) training image, while the bottom row shows evaluations on a finer (128×128) test image. The generalised BVN outperforms the standard BVN and is competitive with the benchmarks. Table 2: Resource comparison across all models (quantum methods in blue). We report the expected shot count for parameter‑shift training of PQCs and the runtime using back-propagation. Our BVNs are significantly more efficient in terms of shots and runtime. Model Num. of qubits Params (PQC) Params (class.) Epochs ≡ Basis states for BVNs Shots (parameter-shift) Runtime (back-prob.) Classification (2D), Figure 4 MLP – – 151 30 – 2.70s SVM – – 253 – – 0.001s SQC 1 120 – 30 120⋅30(2c)120· 30(2c) 37.5s Std. BVN 8(+1) – – 45 100 0.027s Gen. BVN 14(+1) – – 95 100 0.039s Classification (4D), Figure 5 MLP – – 171 100 – 18.34s SVM – – 178 – – 0.0015s SQC 1 240 – 30 240⋅30(2c)240· 30(2c) 819.35s Std. BVN 16(+1) – – 95 100 1.36s Gen. BVN 22(+1) – – 100 100 4.65s Image Fitting, Figure 6 RFF+MLP – – 68,289 100 – 1.8s SIREN – – 24,073 100 – 1.2s QIREN 6 270 899 2,000 270⋅2000(2c)270· 2000(2c) 413.8s QVF 4 80 152,848 2,000 80⋅2000(2c)80· 2000(2c) 142.0s Std. BVN 12(+1) – – 288 10,000 4.8s Gen. BVN 24(+1) – – 6,383 10,000 82.5s The total data-loading cost of BVNs, given by O⁡(mn)×nshotsO(mn)× nshots, scales significantly more favorably than that of PQC models, which is O⁡(mn)×(2c⋅p⋅e)O(mn)×(2c· p· e), where 2c2c denotes the number of shots used for each partial derivative under the parameter-shift rule, p is the number of trainable parameters, and e is the number of training epochs. Table 2 provides a systematic resource comparison between BVNs and benchmarks, including the estimated shot count of parameter-shift training and true simulation runtime using back-propagation. BVNs are markedly efficient: our 8-22-qubit BVNs are 2-3 orders of magnitude faster than the SQC or the multi‑qubit QIREN and QVF. Approximation Error. Lastly, Section G.2 bounds the approximation error of BVNs. Let Ω⊂ℤ2n _2^n be a sampled subset of basis states and fΩf_ the truncated approximation of f using basis states in Ω . The approximation error ϵ=x[(f⁡(x)−fΩ(x))2]ε=E_x[(f(x)-f_ (x))^2] can be written as ϵ=F^Ω¯⊤GΩ¯F^Ω¯ε= F_ G_ F_ , with F^Ω¯=(f^(a))a∉Ω F_ =( f(a))_a∉ denoting the residual coefficients and GΩ¯G_ the Gram matrix from Equation 15. Since GΩ¯G_ is positive semidefinite, we have ϵ≤λmax(GΩ¯)‖F^Ω¯‖22ε≤ _ (G_ )\| F_ \|_2^2, where λmax(GΩ¯) _ (G_ ) is its largest eigenvalue. For standard BVNs, we have ‖F^ℤ2n‖2=1\| F_Z_2^n\|_2=1 and G=IG=I, yielding ϵ=‖F^Ω¯‖22=1−‖F^Ω‖22ε=\| F_ \|_2^2=1-\| F_ \|_2^2. Thus, the approximation error is determined entirely by the unsampled spectrum. For generalised BVNs, the induced basis is generally overcomplete and non-orthogonal, yielding ϵ≤λmax(GΩ¯)‖F^Ω¯‖22ε≤ _ (G_ )\| F_ \|_2^2, showing a trade-off between the non-orthogonality of the extended basis and the expressive representation: Stronger correlations between basis functions increase the penalty factor λmax(GΩ¯) _ (G_ ), while the richer representation ηt _t can yield expressive representations of the target that substantially reduce the residual norm ‖F^Ω¯‖22\| F_ \|_2^2. 7 Ablations 7.1 Dummy Filling We investigate the sensitivity of the generalised BVN to the dummy-fill value and fraction. We vary both and report results in Table 3 using tuples (value, fraction), with (0, 0) denoting unfilled data and (4, 1) the setting used in Figure 5. Benchmark methods are omitted as they fail on the filled data due to severe class imbalance: the m<500m<500 informative samples are expanded to 2162^16 points, with the remaining points assigned a constant dummy label. In contrast, the generalised BVN remains performant across a wide range of fill values and fractions. Table 3: Influence of the dummy filling on the performance of BVNs. Tuples (V, F) indicate dummy fill (value, fraction). (0, 0.0) (4, 0.25) (4, 0.5) (4, 0.75) (4, 1) (10, 1) (100, 1) (1000, 1) Iris Stad. BVN 0.84 0.78 0.65 0.39 0.33 0.33 0.33 0.33 Gen. BVN 0.77 0.76 0.74 0.99 0.88 0.99 0.93 0.85 Penguins Std. BVN 0.60 0.38 0.40 0.23 0.20 0.20 0.20 0.20 Gen. BVN 0.59 0.86 0.85 0.87 0.96 0.93 0.95 0.96 7.2 Random Sampling To isolate the value of quantum interference, we keep the coefficient reconstruction step from Equation 15 unchanged and replace the quantum-selected basis functions with uniformly random basis functions of identical cardinality. Expected Coverage. For an n-qubit input and an (nη+nt)(n_η+n_t)-qubit extended register for expressive representation, the total measurement space dimension is 2n+nη+nt2^n+n_η+n_t, but the relevant diversity for the input features is determined by the marginal distribution over the n-bit input register: p⁡(y)=∑ztp⁡(y,zt)p(y)= _ztp(y,zt). For uniform sampling, (y,z,t)∼⁡(2n+nη+nt)(y,z,t) (2^n+n_η+n_t), the probability of observing y is p⁡(y)=2nη+nt/2n+nη+nt=1/2np(y)=2^n_η+n_t/2^n+n_η+n_t=1/2^n, showing that the additional qubits do not improve the marginal probability of sampling a distinct input feature y. Yet, the expected coverage, or number of unique y, after N random draws, is E E =(number of y)⋅(1−prob(y never occurs)) =(number of y)·(1-prob(y never occurs)) (21) =2n(1−(1−1/2n)N)≈2n(1−e−N/2n), =2^n(1-(1-1/2^n)^N)≈ 2^n(1-e^-N/2^n), (22) which shows that the number of shots for covering a constant fraction of the input space scales exponentially with n. Empirical Evidence. In Figure 7, we validate the above analysis by comparing the performance of the approximated function using basis functions identified by our BVNs and uniform random sampling. We report average classification accuracy across the synthetic shapes in Figure 4, the real-world filled Iris and Penguins datasets in Figure 5, and PSNRs from the image fitting experiment in Figure 6. Figure 7: Ablation of interference-based sampling versus random uniform sampling. BVN’s performance indicates that interference effectively identifies informative basis functions. BVNs consistently outperform random sampling. As expected, the advantage is amplified as the search space grows: compare synthetic and real-world results using N=100N=100 shots for n=8/14n=8/14 and n=16/22n=16/22 qubits in the standard/generalised BVN, respectively. For the image fitting experiment (n=12n=12), random sampling benefits from a larger measurement budget at 10410^4 shots, reaching ∼~ 23 dB PSNR. Yet, both BVNs rapidly identify informative basis functions, particularly in the low-shot regimes (N=100,1000N=100,1000). 7.3 Robustness to Noise To evaluate robustness to hardware noise, we compare BVNs and SQC (27) on the S8 shape of Figure 4(a) using a NISQ-inspired noise model (1): Depolarizing errors of 5×10−35× 10^-3 on 1-qubit gates, 5×10−25× 10^-2 on 2-qubit gates, and a 2%2\% readout bit-flip error. State preparation in BVNs is decomposed into elementary gates to expose this step to noise. SQC is trained using backpropagation without noise and parameter-shift with noise. We report accuracy and runtime for both settings and compare BVNs against random sampling from Section 7.2. As shown in Table 4, BVNs remain noise-robust and outperform random selection. SQC performs the best, but requires ∼ 3.2 hours of parameter-shift training, while BVNs take <<15 seconds at competitive accuracy. Table 4: Accuracy and runtime comparison in noise simulation. The numbers in brackets are in seconds. The experimental setting does not apply for classical methods (denoted by “-”). Noise-free Noise Random Std. BVN 0.99 (0.005) 0.86 (13.610) 0.80 (0.005) Gen. BVN 0.98 (0.028) 0.92 (13.525) 0.85 (0.028) SQC 0.96 (112.066) 0.99 (11513.526) - MLP 0.94 (3.801) - - SVM 0.98 (0.010) - - 8 Practical Recipe for BVNs A central design question in BVNs is how to choose the interference operator, representation, and parameter resolution for a given application. The key principle is to select them such that the induced basis aligns with the target function: • We replace the standard BV basis ξy(x)=(−1)x⊙y _y(x)=(-1)^x y with χyzt(x)=mξy(x)ξz(ηt(x)) _yzt(x)= m _y(x) _z( _t(x)) to obtain potentially sparser representations. For example, a function requiring two BV basis states in ξ may become one-sparse in χ under a suitable representation. • Beyond sparsification, generalised BVNs enable spectrum reshaping. For example, a standard representation with coefficients 5/100 5/100 and 95/100 95/100 makes the smaller informative component unlikely to be sampled. A suitable representation can redistribute this to make informative components more accessible. Ultimately, these design choices should be guided by assumed structures in the data, like convolutional architectures for images or attention mechanisms for sequences. A practical heuristic is to choose an interference operator expected to concentrate the target spectrum, a representation that encodes task-specific structures or invariances, and vary the parameter resolution to control the resulting expressivity. 9 Conclusion We proposed an interference‑based alternative to variational QML by reinterpreting the Bernstein–Vazirani algorithm as a neural model, yielding Bernstein–Vazirani Networks (BVNs). Our generalised BVNs incorporate inductive bias to improve fitting and reduce measurement cost. Experimentally, the generalised BVNs achieved nearly 100%100\% classification accuracy using only 50%50\% of the training data, and reached close to 4040 dB PSNR on image‑fitting, consistently surpassing the standard model and often outperforming quantum and classical baselines. Our work advances QML by introducing a conceptually new framework, which, we believe, will lead to a plethora of improvements. Limitations and Future Work. While our BVNs make a first step in a fundamentally new QML direction, many open questions remain. For instance, while the generalised BVN performs well on synthetic data, scaling to real‑world data (e.g., Iris, Penguins) features spectral leakage. Beyond our ad-hoc dummy‑fill, basis engineering to align the parameter manifold with the data could help. Also, rectangle representations, while expressive, introduce artefacts and may hurt interpolation. Future work would explore smoother alternatives. We detail these directions in Appendix J. Acknowledgements This work was supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation), project number 534951134. T. Birdal was supported by a UKRI Future Leaders Fellowship [grant number MR/Y018818/1]. NKM and M acknowledge support from the Lamarr Institute for Machine Learning and Artificial Intelligence. References AbuGhanem (2026) M. AbuGhanem Early ibm quantum computers: architectural analysis and performance benchmarks. The Journal of Supercomputing 82 (8), p. 422. Cited by: §7.3. Beer et al. (2020) K. Beer, D. Bondarenko, T. Farrelly, T. J. Osborne, R. Salzmann, D. Scheiermann, and R. Wolf Training deep quantum neural networks. Nature communications 11 (1), p. 808. Cited by: §2. Benbarka et al. (2022) N. Benbarka, T. Höfer, A. Zell, et al. Seeing implicit neural representations as fourier series. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, p. 2041–2050. Cited by: §1, §5.3. Bergholm et al. (2018) V. Bergholm, J. Izaac, M. Schuld, C. Gogolin, S. Ahmed, V. Ajith, M. S. Alam, G. Alonso-Linaje, B. AkashNarayanan, A. Asadi, et al. Pennylane: automatic differentiation of hybrid quantum-classical computations. arXiv preprint arXiv:1811.04968. Cited by: §5. Bernstein and Vazirani (1993) E. Bernstein and U. Vazirani Quantum complexity theory. In ACM symposium on Theory of computing, p. 11–20. Cited by: Appendix A, §1, §1, §2, Figure 2, Figure 2, §4.1, §4.1, §4.1. Biamonte et al. (2017) J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd Quantum machine learning. Nature 549 (7671), p. 195–202. Cited by: §1, §2, §3. Cao et al. (2017) Y. Cao, G. G. Guerreschi, and A. Aspuru-Guzik Quantum neuron: an elementary building block for machine learning on quantum computers. arXiv preprint arXiv:1711.11240. Cited by: §2. Cerezo et al. (2022) M. Cerezo, G. Verdon, H. Huang, L. Cincio, and P. J. Coles Challenges and opportunities in quantum machine learning. Nature computational science 2 (9), p. 567–576. Cited by: §1, §2, §3. Cong et al. (2019) I. Cong, S. Choi, and M. D. Lukin Quantum convolutional neural networks. Nature Physics 15 (12), p. 1273–1278. Cited by: §2. da Silva et al. (2016) A. J. da Silva, T. B. Ludermir, and W. R. de Oliveira Quantum perceptron over a field and neural network architecture selection in a quantum computer. Neural Networks 76, p. 55–64. Cited by: §2. Deutsch and Jozsa (1992) D. Deutsch and R. Jozsa Rapid solution of problems by quantum computation. Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences 439 (1907), p. 553–558. Cited by: §1, §2. Fisher (1936) R. A. Fisher The use of multiple measurements in taxonomic problems. Annals of eugenics 7 (2), p. 179–188. Cited by: §1, §5.2. Gleinig and Hoefler (2021) N. Gleinig and T. Hoefler An efficient algorithm for sparse quantum state preparation. In Design Automation Conference (DAC), p. 433–438. Cited by: §G.1. Goodfellow et al. (2016) I. Goodfellow, Y. Bengio, and A. Courville Deep learning. MIT Press. Note: http://w.deeplearningbook.org Cited by: §3. Herman et al. (2023) D. Herman, R. Raymond, M. Li, N. Robles, A. Mezzacapo, and M. Pistoia Expressivity of variational quantum machine learning on the boolean cube. Quantum Engineering 4, p. 1–18. Cited by: §1, §2. Horst et al. (2022) A. M. Horst, A. P. Hill, and K. B. Gorman Palmer archipelago penguins data in the palmerpenguins r package-an alternative to anderson’s irises.. R Journal 14 (1). Cited by: §1, §5.2. Kapoor et al. (2016) A. Kapoor, N. Wiebe, and K. Svore Quantum perceptron models. Advances in neural information processing systems 29. Cited by: §2. Larocca et al. (2025) M. Larocca, S. Thanasilp, S. Wang, K. Sharma, J. Biamonte, P. J. Coles, L. Cincio, J. R. McClean, Z. Holmes, and M. Cerezo Barren plateaus in variational quantum computing. Nature Reviews Physics, p. 1–16. Cited by: §2. Liu et al. (2025) W. Liu, Y. Zhu, Y. Zha, Q. Wu, L. Jian, and Z. Liu Rotation-and permutation-equivariant quantum graph neural network for 3d graph data. Transactions on Pattern Analysis and Machine Intelligence. Cited by: §2. McClean et al. (2018) J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven Barren plateaus in quantum neural network training landscapes. Nature communications 9 (1), p. 4812. Cited by: §1. Meli et al. (2025) N. K. Meli, S. Wang, M. S. Benkner, M. Sasdelli, T. Chin, T. Birdal, M. Moeller, and V. Golyanik Quantum-enhanced computer vision: going beyond classical algorithms. arXiv preprint arXiv:2510.07317. Cited by: §2. Mozafari et al. (2022) F. Mozafari, G. De Micheli, and Y. Yang Efficient deterministic preparation of quantum states using decision diagrams. Physical Review A 106 (2), p. 022617. Cited by: §G.1. Nguyen et al. (2024) Q. T. Nguyen, L. Schatzki, P. Braccia, M. Ragone, P. J. Coles, F. Sauvage, M. Larocca, and M. Cerezo Theory for equivariant quantum neural networks. PRX Quantum 5 (2), p. 020328. Cited by: §2. Nielsen and Chuang (2010) M. A. Nielsen and I. L. Chuang Quantum computation and quantum information. Cambridge university press. Cited by: §4.3, §4.4, §4.4, §6. Nielsen (2015) M. A. Nielsen Neural networks and deep learning. Vol. 25, Determination press San Francisco, CA, USA. Cited by: §3. O’Donnell (2014) R. O’Donnell Analysis of boolean functions. Cambridge University Press. Cited by: Theorem 4.1. Pérez-Salinas et al. (2020) A. Pérez-Salinas, A. Cervera-Lierta, E. Gil-Fuster, and J. I. Latorre Data re-uploading for a universal quantum classifier. Quantum 4, p. 226. Cited by: §1, §2, §2, §5.2, §7.3. Ramacciotti et al. (2024) D. Ramacciotti, A. I. Lefterovici, and A. F. Rotundo Simple quantum algorithm to efficiently prepare sparse states. Physical Review A 110 (3), p. 032609. Cited by: §G.1. Recio-Armengol et al. (2025) E. Recio-Armengol, S. Ahmed, and J. Bowles Train on classical, deploy on quantum: scaling generative quantum machine learning to a thousand qubits. arXiv preprint arXiv:2503.02934. Cited by: §1. Schatzki et al. (2024) L. Schatzki, M. Larocca, Q. T. Nguyen, F. Sauvage, and M. Cerezo Theoretical guarantees for permutation-equivariant quantum neural networks. npj Quantum Information 10 (1), p. 12. Cited by: §2. Schuld et al. (2019) M. Schuld, V. Bergholm, C. Gogolin, J. Izaac, and N. Killoran Evaluating analytic gradients on quantum hardware. Physical Review A 99 (3), p. 032331. Cited by: §1. Schuld and Petruccione (2018) M. Schuld and F. Petruccione Supervised learning with quantum computers. Quantum science and technology 17. Cited by: §G.1, §2, §2. Schuld et al. (2014) M. Schuld, I. Sinayskiy, and F. Petruccione The quest for a quantum neural network. Quantum Information Processing 13 (11), p. 2567–2586. Cited by: §2, §3. Schuld et al. (2021) M. Schuld, R. Sweke, and J. J. Meyer Effect of data encoding on the expressive power of variational quantum-machine-learning models. Physical Review A 103 (3), p. 032430. Cited by: §2. Shor (1999) P. W. Shor Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review 41 (2), p. 303–332. Cited by: §1, §2. Sim et al. (2019) S. Sim, P. D. Johnson, and A. Aspuru-Guzik Expressibility and entangling capability of parameterized quantum circuits for hybrid quantum-classical algorithms. Advanced Quantum Technologies 2 (12), p. 1900070. Cited by: §2. Wakeham and Schuld (2024) D. Wakeham and M. Schuld Inference, interference and invariance: how the quantum fourier transform can help to learn from data. arXiv preprint arXiv:2409.00172. Cited by: Appendix I, §1, §2, §5.2. Wang et al. (2025) S. Wang, C. Theobalt, and V. Golyanik Quantum visual fields with neural amplitude encoding. In 39th Annual Conference on Neural Information Processing Systems, Cited by: §1, §2, §5.3. Williams et al. (2023) C. A. Williams, A. E. Paine, H. Wu, V. E. Elfving, and O. Kyriienko Quantum chebyshev transform: mapping, embedding, learning and sampling distributions. arXiv preprint arXiv:2306.17026. Cited by: Appendix G, §4.4, §6. Zhao et al. (2024) J. Zhao, W. Qiao, P. Zhang, and H. Gao Quantum implicit neural representations. arXiv preprint arXiv:2406.03873. Cited by: §1, §2, §5.3. Appendix This appendix entails further technical details and experiments to complement the main text. It includes: Title Text Appendix Derivation of the interference behind the Berstein-Vazirani algorithm Section 4.1 Appendix A Proof of the Fourier Expansion Theorem Theorem 4.1 Appendix B Derivation of BVNs from a Linear Algebra Perspective Theorem 4.1 Appendix C Layered Expressive Representation Section 4.3 Appendix D Rectangle Expressive Representation Section 4.3 Appendix E Interference Operators in Comparison Section 4.4 Appendix F Complexities and Systematic Comparison Section 5 Appendix G Inspecting the sampled Coefficients Section 5.2 Appendix H Comparing Filled and Unfilled Training Data Section 5.2 Appendix I Future Work and Technical Extensions Section 9 Appendix J Appendix A Interference in Bernstein–Vazirani We shortly review the Bernstein–Vazirani algorithm (5) and explain how interference occurs. From the three steps of the Bernstein–Vazirani algorithm (Equations 2, 3 and 4) and after replacing f by its signature f⁡(x)=s⊙xf(x)=s x, we have |ψ1⟩ _1 =12n∑x∈ℤn2|x⟩ = 1 2^n _x _n^2 x (23) |ψ2⟩ _2 =12n∑x∈ℤn2(−1)f⁡(x)|x⟩ = 1 2^n _x _n^2(-1)^f(x) x (24) |ψ3⟩ _3 =∑y∈ℤn2f^(y)|y⟩. = _y _n^2 f(y) y. (25) with Fourier coefficients f^(y) f(y) =12n∑x∈ℤn2(−1)s⊙x+y⊙x = 12^n _x _n^2(-1)^s x+y x (26) =12n∑x∈ℤn2(−1)(s⊙x+y⊙x)mod2. = 12^n _x _n^2(-1)^(s x+y x) 2. (27) We want to show that f^(y)=1 f(y)=1 if and only if y=sy=s and 00 otherwise. On ℤn2Z_n^2, we use two important properties: (a+b)mod2 (a+b) -8.5359pt 2 =(amod2+bmod2)mod2, =(a -8.5359pt 2+b -8.5359pt 2) 2, (28) (a⋅b)mod2 (a· b) -8.5359pt 2 =(amod2)⋅(bmod2)mod2. =(a -8.5359pt 2)·(b -8.5359pt 2) 2. (29) After applying Equations 28 and 29 to the phase term in Equation 27, it holds (s⊙x+y⊙x)mod2 (s x+y x) 2 (30) =(s⊤xmod2+y⊤xmod2)mod2 =(s x 2+y x 2) 2 (31) =((smod2)⊤(xmod2)CLOSE =((s 2) (x 2) OPEN+(ymod2)⊤(xmod2))mod2 +(y 2) (x 2)) 2 (32) =((smod2+ymod2)⊤(xmod2))mod2 =((s 2+y 2) (x 2)) 2 (33) =(((s+y)mod2)⊤(xmod2))mod2 =(((s+y) 2) (x 2)) 2 (34) =((s⊕y)⊤x)mod2 =((s y) x) 2 (35) =(s⊕y)⊤⊙x. =(s y) x. (36) Now substituting Equation 36 in Equation 27, we have 12n∑x∈ℤn2(−1) 12^n _x _n^2(-1) (s⊙x+y⊙x)mod2 =12n∑x∈ℤn2(−1)(s⊕y)⊤⊙x = 12^n _x _n^2(-1)^(s y) x (37) =12n∑x∈ℤn2∏i=1n(−1)(si⊕yi)⋅xi = 12^n _x _n^2 _i=1^n(-1)^(s_i y_i)· x_i (38) =12n∏i=1n∑xi∈ℤ12(−1)(si⊕yi)⋅xi = 12^n _i=1^n _x_i _1^2(-1)^(s_i y_i)· x_i (39) =12n∏i=1n(1+(−1)(si⊕yi)). = 12^n _i=1^n(1+(-1)^(s_i y_i)). (40) In the last term, we see that the complete sum evaluates to 00 if si⊕yi=1s_i y_i=1 for any index i, and to 11 if si⊕yi=0s_i y_i=0 for all i. On the other hand, we have si⊕yi=0s_i y_i=0 if and only if si=yis_i=y_i. This collapsing sum to either 00 or 11 is called interference, where undesired y interfere destructively, while the desired solution interferes constructively. Appendix B Proof of the Fourier Expansion Theorem In this section, we provide the proof of the Fourier Expansion Theorem 4.1. Proof. The proof follows from linear algebra by expressing f uniquely in an orthonormal basis via inner products. First, we verify that χyy∈ℤ2n\ _y\_y _2^n forms an orthonormal basis of the vector space ℱ:=f:0,1n→ℝF:=\f:\0,1\^n \ of functions from ℤ2n=0,1nZ_2^n=\0,1\^n to ℝR. This is principally possible because any function in ℱF can be replaced by a vector in ℝ2nR^2^n by enumerating all function values. We define the inner product on ℤ2nZ_2^n as ⟨f,g⟩=x∈ℤ2n[f⁡(x)g(x)] f,g=E_x _2^n[f(x)\,g(x)]. As derived in Equations 37, 38, 39 and 40, ∀y1,y2∈ℤ2n∀ y_1,y_2 _2^n, it holds ⟨χy1,χy2⟩ _y_1, _y_2 =12n∑x∈ℤ2n(−1)(y1⊙x+y2⊙x)mod2 = 12^n _x _2^n(-1)^(y_1 x+y_2 x) 2 (41) =1,if y1=y2,0,otherwise. = cases1,&if y_1=y_2,\\ 0,&otherwise. cases (42) Since there are 2n2^n functions χy _y, matching the dimension of ℱF, the set χyy∈ℤ2n\ _y\_y _2^n forms an orthonormal basis. Hence, any f∈ℱf expands uniquely as f⁡(x)=∑y∈ℤ2nf^(y)χy(x),f(x)= _y _2^n f(y) _y(x), (43) where f^(y)=⟨f,χy⟩=12n∑z∈ℤ2nf⁡(z)χy(z). f(y)= f, _y = 12^n _z _2^nf(z) _y(z). (44) ∎ Appendix C Alternative Derivation of (Generalised) Bernstein–Vazirani Networks from a Linear Algebraic Perspective Related, but not strictly equivalent concepts to our generalised Bernstein–Vazirani algorithm are generalised Fourier series or Sparse dictionary learning. To (informally) generalise Theorem 4.1, we assume that there is a set of functions =gyy∈ℤ2m⊂ℱG=\g_y\_y _2^m , such that f⁡(x)≈∑y∈ℤ2m⟨f,gy⟩gy,f(x)≈ _y _2^m f,g_yg_y, (45) with ⟨⋅,⋅⟩ ·,·, defined as ⟨f,gy⟩=12n∑x∈ℤ2nf⁡(x)gy(x) f,g_y= 12^n _x _2^nf(x)g_y(x), being the standard inner product in ℤ2nZ_2^n. We further still assume access to the function oracle UfU_f, which realises the state |ψ⟩=12n∑x∈ℤ2nf⁡(x)|x⟩. ψ= 1 2^n _x _2^nf(x) x. (46) As our inputs x live in ℝ2nR^2^n and we seek expressive models, we are interested in settings where m≥nm≥ n, i.e., where G is an overcomplete basis for the function space ℱF. Now, independently, let :=|y⟩,y∈ℤ2mY:=\ y,y _2^m\ be some orthonormal basis, with |y⟩ y written in the computational basis as |y⟩=12m∑x∈ℤ2n∑z∈ℤ2m−nayx,z|x,z⟩, y= 1 2^m _x _2^n _z _2^m-na_y^x,z x,z, (47) for some amplitudes ayx,z∈ℂa_y^x,z , where the |z⟩ z register is an ancillary register with (m−n)(m-n) qubits. We embed |ψ⟩ ψ from Equation 46 in the 2m2^m-dimensional Hilbert space as |ψ~⟩=|ψ,0⟩ ψ= ψ,0. Expressing |ψ~⟩ ψ in the basis Y yields |ψ~⟩ ψ =∑y∈ℤ2m⟨y|ψ~⟩|y⟩ = _y _2^m y| ψ y (48) =12n∑y∈ℤ2m∑p,q∈ℤ2nayp,0f(q)⟨p|q⟩|y⟩ = 12^n _y _2^m _p,q _2^na_y^p,0f(q) p|q y (49) =12n∑y∈ℤ2m∑x∈ℤ2nayx,0f(x)|y⟩. = 12^n _y _2^m _x _2^na_y^x,0f(x) y. (50) Now, to connect Y and G, we observe that the amplitudes ayx,0a_y^x,0 define the family of functions gy(x):=ayx,0.g_y(x):=a_y^x,0. (51) Even though the initial state has ancilla qubits in |0⟩ 0, the different y basis vectors spread across the ancillary dimensions, giving rise to an overcomplete dictionary of functions gyg_y. Constructing the basis Y such that gy(x)=ayx,0g_y(x)=a_y^x,0 transforms Equation 50 into |ψ~⟩=∑y∈ℤ2m⟨gy,f⟩|y⟩. ψ= _y _2^m g_y,f y. (52) Measuring |ψ~⟩ ψ in the basis Y reveals, with probability |⟨gy,f⟩|2| g_y,f|^2, the corresponding y and the associated gyg_y needed to approximate f according to Equation 45. If n=mn=m and the set G is orthonormal in ℱF, we recover the standard BV setting (up to the chosen basis Y). The generalised BV setting emerges when m≥nm≥ n, giving rise to an overcomplete and expressive basis. How to design Y that realises G? This is now an architectural design choice. The important point is that enlarging the system with ancillary qubits allows us to realise an overcomplete basis. The interference operator acting on the representation register effectively disentangles it from the input x, allowing us to write Equation 50 as a sum over x while isolating the |y⟩ y register. How to measure in general bases? We are interested in measuring |ψ~⟩ ψ in a basis Y that is not necessarily the computational basis. Let Y be the measurement observable of the basis Y. As a Hermitian operator, Y can be diagonalised. There exists a unitary UYU_Y such that UYYUY†=D,U_YYU_Y =D, (53) where D is diagonal in the computational basis. Then, ⟨ψ~|Y|ψ~⟩=⟨ψ~|UY†DUY|ψ~⟩. ψ|Y| ψ= ψ|U_Y DU_Y| ψ. (54) Measuring |ψ~⟩ ψ in the basis Y thus reduces to implementing UYU_Y followed by measurement in the computational basis. This is exactly the action of our expressive representation circuit followed by the interference operator. Appendix D Layered Expressive Representation In the following, we provide a quantum implementation of a classical two-layer MLP with step activation functions and fixed biases as an exemplary expressive representation to be used in our generalised BVNs (see Section 4.3). Equation 17 is written compactly for the input, activation, and weights. In practice, the system may be organised into several sub-registers to support different input dimensions and to implement a classical layered representation reversibly. Definition D.1 (Quantum Layer). A quantum layer ℓ consists of multiple units. Each unit is specified by an output register |0⟩ 0, an activation function σ, and d weight registers |t⟩ t, where d is the dimension of the activation vector of layer ℓ−1 -1. Given an input activation register |σℓ−1⟩ _ -1, the layer implements the coherent update |σℓ−1⟩|0⟩|t⟩↦|σℓ−1⟩|σℓ⟩|t⟩,σℓ=σ⁡(∑i=1dti(σℓ−1)i). _ -1 0 t _ -1 _ t,\ _ =σ ( _i=1^dt_i\,( _ -1)_i ). (55) Ancillary qubits are abstracted but may be required for reversible arithmetic. Figure 8: A quantum circuit realising an expressive representation of the input. It implements a fully connected two-layer network. The input is a two-dimensional register |x1⟩|x2⟩ x_1 x_2. The hidden layer consists of two units, each computing ηthj(x)=σ⁡(thj1x1+thj2x2) _t_h_j(x)=σ(t_h_j^1x_1+t_h_j^2x_2) and the output unit computes ηo _o in the same way, but acting on the hidden activations instead of the input. The circuit is implemented using quantum arithmetic with ancillary qubits (not shown). In Figure 8, we illustrate a quantum circuit implementing an expressive representation of the input. It realises a fully connected two-layer network. The 2-dimensional input |x⟩ x is stored in two sub-registers, forming the input layer. The hidden layer contains two units, each with two weight registers that modulate the input; the weighted sum is passed through an activation and written to an activation register. The output layer is a single unit acting on the hidden activations. For this example, the decomposition |x⟩|ηt(x)⟩|t⟩ x _t(x) t from Equation 17 becomes |x⟩ x =|x1⟩|x2⟩, = x_1 x_2, (56) |ηt(x)⟩ _t(x) =|ηth1(x)⟩|ηth2(x)⟩|ηt0(ηth)⟩, = _t_h_1(x) _t_h_2(x) _t_0( _t_h), (57) |t⟩ t =|th11⟩|th12⟩|th21⟩|th22⟩|to1⟩|to2⟩, = t_h_1^1 t_h_1^2 t_h_2^1 t_h_2^2 t_o^1 t_o^2, (58) where ηthj(x)=σ⁡(thj1x1+thj2x2), _t_h_j(x)=σ (t_h_j^1x_1+t_h_j^2x_2 ), and similarly for ηo _o acting on the hidden activations. 2-Layer Representation with Step Activation Function. We experimented with the architecture shown in Figure 8 in the 2D case, but due to the induced circuit size, we were restricted to a two-layer model with two hidden units and one output unit, using binary weights and no biases. The circuit computes the weighted sum and activates the output qubit (sets it to 1) if this sum does not exceed a hard-coded threshold. This requires three qubits per unit: one weight qubit for each of the two input dimensions and one output qubit. Such a binary 2-layer MLP therefore has six weights in total, corresponding to 26=642^6=64 possible network configurations. In Figure 9, we visualise the possible activations produced by this binary model across all weight configurations. The dimensional qubit-resolution of x is 66, and the thresholds of the hidden and output units are set to 3232 and 11, respectively, in one setting, and to 6464 and 11 in the other. Although the network has 64 possible weight assignments, the resulting activations are not very expressive: only seven distinct partitions of the 2D input space appear in the first setting and three in the second. The model would require learnable biases to shift activation boundaries freely, but introducing biases would significantly increase the qubit count. In addition, the hidden activations are no longer needed once they have been used in the output layer. Hence, they unnecessarily grow the qubit count. Figure 9: All distinct activation patterns produced by the 2-layer binary MLP for all 64 possible weight configurations. Top: thresholds (32, 1) for hidden and output units. Bottom: thresholds (64, 1). Despite the large number of weight settings, only a small number of unique input-space partitions are realisable, highlighting the limited expressivity of this bias-free architecture. Blue means 11 and grey 00. In Figure 10, we visualise the image fitting results using the 2-layer MLP as the expressive representation, with thresholds (16,1)(16,1) in the hidden and output layers. We observe that the MLP with fixed thresholds still lacks expressivity and does not significantly improve over the standard BVN. Figure 10: Visualising the fitting results of the standard (top row) and generalised (bottom row) BVNs for different numbers of shots, using the 2-layer MLP as the expressive representation. With few shots, we observe the effect of the MLP, which activates different regions of the input domain. However, the fixed region boundaries limit the model’s ability to capture fine details in the image. Appendix E Rectangle Expressive Representation In the following, we provide details on the rectangle activation as an exemplary expressive representation to be used in our generalised BVNs (see Section 4.3). To overcome the limited expressivity of bias-free 2-layer MLPs, we introduce the rectangle activation. Each input dimension is represented with a binary register, and smaller mask registers define local subdomains. The circuit accumulates contributions from each dimension into a shared sigma register, with superposition allowing all inputs and rectangles to be processed simultaneously. Figure 11: Quantum circuit implementing the rectangle activation. We circularly shift each input dimension x by its corresponding rectangle parameter t, and activate the output qubit if all high-significance qubits of x are 0, which corresponds to activating the rectangle parametrised by t. To reduce artefacts, the superposition register allows for overlapping rectangles by further shifting the input conditionally. In Figure 11, we illustrate the circuit implementing the rectangle activation. Since hidden activations are only temporarily needed for computing the output, we use the input register to store them temporarily. Let rxr_x be the qubit resolution of one dimension xix_i of the input x and rtr_t that of the rectangle positions. Then, the rectangle width is 2rx−rt2^r_x-r_t, and there are 2rt2^r_t positions to place the rectangle along the considered dimension i. We circularly shift each input dimension xix_i by its corresponding parameter tit_i: |xi⟩←|xi+ti⋅2rx−rtmod2rx⟩. x_i← x_i+t_i· 2^r_x-r_t 2^r_x. (59) The output qubit is activated (set to 1) if all (rx−rt)(r_x-r_t) most significant qubits of the input register are 00. After the activation, the shift is undone, leaving the input register back in the x-state. To reduce artefacts, we allow rectangles to overlap by introducing a superposition register |s⟩ s, which duplicates rectangle parameters. Depending on the value of s, we shift the input further before activation. In our experiments, we use one superposition qubit and shift by half of the rectangle resolution if the superposition bit is 1, yielding |xi⟩←|xi+ti⋅2rx−rt+s⋅2rt/2mod2rx⟩. x_i← x_i+t_i· 2^r_x-r_t+s· 2^r_t/2 2^r_x. (60) In Figure 12, we visualise the rectangle activations in 2D. The dimensional qubit-resolution of x is 55, and that of the rectangle positions is 33. With only 66 additional qubits (compared to nine in the MLP case plus ancillaries), the procedure effectively creates localised rectangles in the input space where the activation is turned on, modifying the standard BV basis locally. The result is a highly expressive activation pattern that captures fine-grained variations in the input while remaining resource-efficient. Figure 12: All distinct activation patterns produced by the rectangle activation for all 6464 possible weight configurations. Top: activations for s=0s=0. Bottom: activations for s=1s=1. Each weight configuration generates a distinct local activation, illustrating the expressive power of the rectangle activation without requiring biases or additional qubits. Blue indicates 11 and grey indicates 00. In Figure 13, we validate the expressivity of the rectangle activation for the resolutions r=3r_r=3 and r=5r_r=5, and ablate the number of shots used in the image fitting experiment. We clearly see how each rectangle locally modifies and corrects the standard BV basis functions toward a better fit of the target. As a consequence, the generalised model converges faster and captures finer details than the standard model. The finer the resolution r_r, the better the results. Figure 13: Visualising the fitting results of the standard and generalised BVNs for different numbers of shots and two rectangle resolutions, 3x3 (top) and 5x5 (bottom). With a few shots, we observe the effect of the rectangle activation functions. Each rectangle locally modifies the standard BV basis, allowing the model to better fit the target in that region. With a sufficient number of shots, the rectangles are no longer visible, and the generalised model becomes more accurate than the standard one. The finer rectangle resolution outperforms the coarse. Appendix F Interference Operators in Comparison We visualise the activation or basis function induced by the Hadamard, Fourier and Chebyshev interference operators in Figure 14. The Hadamard operator produces step parity functions with amplitude 11, while the Fourier and Chebyshev operators introduce finer variations. Figure 14: Interference operators in comparison. We visualise the basis functions ξy(⋅) _y(·) for the Hadamard, the Fourier and the Chebyshev operators. The Hadamard basis functions are parity activations that yield ±1± 1 depending on whether the weighted sum of the input is odd or even. The Fourier and Chebyshev basis functions, in contrast, allow more variations than ±1± 1 and smoother activations. We test these interference operators on regression examples of fitting 1D functions with increasing frequencies. The functions are generated by sampling random vectors of different lengths corresponding to the frequencies and interpolating the vectors. We also include a step function to analyse the Gibbs phenomenon. We compare the Hadamard and Chebyshev interference operators, along with the regularisation factor λ of the coefficient reconstruction. We omit the Fourier transform due to the imaginary part it introduces, which is not needed for the real-valued experiment. Figure 15: Regression of random 1D functions with different frequencies using the proposed interference-based quantum networks. The top and bottom rows show results with the Hadamard and Chebyshev interference operators, respectively. We compare the standard Bernstein–Vazirani model (blue) with the generalised model (red). Within each model, we contrast the Gram inversion regularisation factors λ. The Chebyshev interference produces smooth functions as it acts in the real domain, while Hadamard, due to rounding, produces step functions as it acts in the binary domain. The generalised method with λ=0.1λ=0.1 fits the target function better than that of the standard model (see step function in column 1). Increasing λ regularises the approximation. Figure 15 presents the 1D regression results. The Hadamard and Chebyshev operators perform similarly overall, as both can capture the function’s variations. However, the Chebyshev operator, which operates in the real domain, produces smooth outputs, whereas the Hadamard operator yields step‑like functions due to rounding effects inherent to the binary domain. Both the standard and generalised models fit the target function reasonably well. Different values of λ smooth the approximation, a property we expect to be beneficial in the presence of noise. A closer inspection shows that the generalised model is more accurate and better captures high‑frequency variations. For example, with the Chebyshev interference operator applied to the step function (first column, second row), the standard BVN oscillates around the target, whereas the locally corrected basis of the generalised model with rectangles significantly reduces these oscillations and matches the target more closely. See also the image fitting results in Figure 13. Appendix G Computational Complexity Our BVNs expect training inputs (binary strings) to be placed in superposition and labelled via an oracle. The gate complexity of this encoding depends on the sparsity of the training set relative to the dimension of the Hilbert space spanned by the input resolution; it is O⁡(mn)O(mn) for m being the effective size of the training set and n the number of qubits (details in Section G.1). Further, our rectangle representations with qubit resolution n and ntn_t for the input and parameter registers use ntn_t controlled adders and their inverses, along with a Toffoli gate to compute and mark the rectangles in the η-register, yielding a gate complexity of O⁡(nnt)O(n_t). The Hadamard interference operator can be implemented with O⁡(n)O(n) gates on n qubits, whereas Chebyshev (39) requires O⁡(n+n2)O(n+n^2) gates. Lastly, for reconstructing the coefficients, we build the matrix X∈ℝm×kX ^m× k by evaluating each of the k sampled basis functions on each of the m training inputs. We then recover the coefficients in closed form as described in Equation 13. Let c denote the cost of evaluating a basis function on a training input, which is O⁡(n)O(n) for the Hadamard interference operator and O⁡(1)O(1) for the Chebyshev and Fourier interference operators. Then the total cost of reconstructing the coefficients is: • O⁡(cmk)O(cmk) for constructing X, • O⁡(mk2)O(mk^2) for computing the Gram matrix G=X⊤XG=X X, • O⁡(mk)O(mk) for computing X⊤FX F, • O⁡(k3)O(k^3) for solving the linear system (G+λI)−1X⊤F(G+λ I)^-1X F. In practice, this reconstruction step was not prohibitively expensive. Its runtime was comparable to a single training epoch in classical models, as it involves a single pass over the training set. G.1 Dataset-Encoding and Oracle Complexities Since data encoding is a major bottleneck in QML, we verify that this step is efficient in our BVNs. In our experiments, dataset and oracle steps are combined into an amplitude encoding of a state vector with amplitudes proportional to the label values. As an example, for Iris classification, a 44-dimensional scaled and rounded feature x=(7,6,10,11)x=(7,6,10,11) is encoded with 44 qubits per dimension as x=(0111,0110,1010,1011)x=(0111,0110,1010,1011), giving when concatenated x=0111011010101011x=0111011010101011. Each input is thus a 1616-qubit computational basis vector |x⟩∈ℂ216 x ^2^16, and the labelled training set is encoded as a normalised superposition ∑xf⁡(x)|x⟩ _xf(x) x using amplitude encoding. The gate complexity of amplitude encoding depends on the sparsity of the input vector (32). Sparse-state preparation techniques have a complexity of O⁡(mn)O(mn) for m nonzero entries (13; 28), i.e., the effective size of the training set. In practice, m≪2nm 2^n (150150 Iris, 333333 Penguins samples for a 2162^16 dimensional space), yielding highly sparse vectors. Even for our dummy‑filled datasets in the Iris and Penguins experiments, the algorithm in (22), based on Decision Diagrams (DDs) is expected applicable, which complexity O⁡(kn)O(kn), where k is the number of D paths. Our dummy‑filled state is dominated by a constant‑amplitude component over large regions of the computational basis, with only a few data‑dependent deviations, so the effective path count k is expected to scale mainly with m. The data-loading cost in BVNs compares strictly better than variational QML methods, requiring O⁡(mn)O(mn) separate state preparation operations per parameter-shift rule evaluation of a single partial derivative, multiplied by the number of shots required for each estimate, multiplied by the number of parameters, and multiplied by the number of training iterations. Concretely, let c denote the number of shots needed to estimate an expectation value, which is required for computing partial derivatives when using the only certified method, the parameter‑shift rule. To estimate an expectation value to precision ϵε, it is known that the required number of shots scales as c=1/ϵ2c=1/ε^2. For illustration, a single partial derivative with accuracy ϵ=0.001ε=0.001 already requires 2c=2⋅1062c=2· 10^6 circuit evaluations. And we have to multiply this cost by the number of parameters and then by the number of training iterations. G.2 Sample Complexity Analysis The number of measurement shots in BVNs is not directly transferable to the approximation accuracy of the target function f, and is also not influenced by the dimension of the input space. Rather, it is determined by the “sparsity” of the target function f in the chosen basis χ. We can generalise the error bound analysis for the proposed BVN framework. In fact, since the standard BVN is a special case of the generalised BVN, we can write f uniquely in the standard subspace of the extended basis as f⁡(x)=12n∑y∈ℤ2nf^(y,0,0)χy00(x),f(x)= 1 2^n _y _2^n f(y,0,0)\, _y00(x), (61) or, more generally, as the non-unique expansion f⁡(x)=12n∑af^(a)χa(x),f(x)= 1 2^n _a f(a) _a(x), (62) where a=(y,z,t)a=(y,z,t) indexes the generalised basis functions. Now let Ω denote the set of sampled basis states of the generalised BVN, and define fΩ(x)=12n∑a∈Ωf^(a)χa(x).f_ (x)= 1 2^n _a∈ f(a) _a(x). (63) Then the approximation error is ϵ ε =x[(f⁡(x)−fΩ(x))2] =E_x [(f(x)-f_ (x))^2 ] (64) =12n∑x(12n∑a∉Ωf^(a)χa(x))2 = 12^n _x ( 1 2^n _a∉ f(a) _a(x) )^2 (65) =12n∑x∑a,b∉Ωf^(a)f^(b)χa(x)χb(x) = 12^n _x _a,b∉ f(a) f(b) _a(x) _b(x) (66) =∑a,b∉Ωf^(a)f^(b)(12n∑xχa(x)χb(x))⏟=:Gab, = _a,b∉ f(a) f(b) ( 12^n _x _a(x) _b(x) )_=:G_ab, (67) where G is the Gram matrix of the sampled basis functions. Hence, ϵ=F^Ω¯⊤GΩ¯F^Ω¯,ε= F_ G_ F_ , (68) where Ω¯ denotes the complement of Ω . Since GΩ¯G_ is positive semidefinite, ϵ≤λmax(GΩ¯)‖f^Ω¯‖22,ε≤ _ (G_ )\| f_ \|_2^2, (69) where λmax(GΩ¯) _ (G_ ) denotes the largest eigenvalue of the Gram matrix of the generalised basis functions and F^Ω¯=(f^(a))a∉Ω F_ =( f(a))_a∉ is the vector of residual coefficients. From the above derivation, we can further derive an explicit bound for the standard case. Indeed, for the standard BVN basis, the Gram matrix satisfies G=IG=I by orthonormality, and therefore ϵ=‖F^Ω¯‖22=1−sε=\| F_ \|_2^2=1-s, where s=∑a∈Ω|f^(a)|2s= _a∈ | f(a)|^2 denotes the accumulated spectral mass. Thus, in the standard BVN, the approximation error is determined entirely by the unsampled Fourier spectrum. For the generalised BVN, the induced basis is generally overcomplete and therefore non-orthogonal. Consequently, the approximation error satisfies ϵ≤λmax(GΩ¯)‖F^Ω¯‖22ε≤ _ (G_ )\| F_ \|_2^2. This bound exposes a natural trade-off introduced by the expressive representation. The more correlated the basis functions are, the higher the penalty factor λmax(GΩ¯) _ (G_ ). At the same time, the richer representation ηt _t enables the target function to admit more compact representations in the extended basis, so that the norm of the residual coefficients ‖F^Ω¯‖22\| F_ \|_2^2 may decrease substantially. Our empirical results of shots-vs-accuracy in Figure 7 show consistently lower approximation errors for the generalised BVNs, suggesting that this reduction in ‖F^Ω¯‖22\| F_ \|_2^2 dominates the additional Gram-matrix factor. Appendix H Inspecting the Sampled Coefficients We inspect the histograms of the coefficients sampled by the standard and generalised BVNs for the classification task on the 2D synthetic datasets Figures 16(a) and 16(b), as well as on the real-world Iris and Penguins datasets Figure 17. From the histograms of the standard BVN Figures 16(a) and 17, one can infer how easily the objective function can be approximated on a given dataset. Sparse histograms indicate that the target function is sparse in the BV basis, i.e., relatively easy to approximate with a finite number of shots. More challenging datasets, such as spiral, exhibit more dispersed histograms. The generalised model Figures 16(b) and 17 does not produce sparse histograms. This is expected, as it extends the standard BV basis and generates multiple copies of the dominant BV functions, each with a local modification. (a) Standard BVN (b) Generalised BVN Figure 16: Histograms of sampled coefficients for the 2D synthetic datasets using (a) the standard BVN and (b) the generalised BVN. Figure 17: Histograms of the sampled coefficients obtained with the standard (top row) and generalised BV (bottom row) methods on the Iris and Penguins datasets. The coefficients are not concentrated and exhibit dispersed magnitudes. Appendix I Comparing Filled and Unfilled Training Data As mentioned in the main text (Section 5.2), the small number of training samples (<500<500) relative to the large Hilbert-space dimension of 101610^16 (4 qubits per input dimension) leads to sampling leakage (37), which led us to fill the dataset. In this section, we complement the filled and unfilled comparison in Figure 5 by reporting the performance for additional values of λ. In Figure 18, we experimentally assign a dummy fill‑label to domain inputs not present in the training set. This small change substantially improves the generalised model, while the standard model degrades. The poor performance of the standard model on unfilled data is now due not to leakage but to the dummy label overwhelming the true training samples, causing the model to assign it uniformly as a constant approximation of the target function. The generalised model, using the same number of shots, gains enough expressivity to capture the geometry of the true training data. (a) Unfilled training data (b) Filled training data Figure 18: Classification results for unfilled (a) and filled (b) training data on the Iris and Penguins datasets for different λ. Filling the data strongly affects the performance of the BVNs: Unfilled data lead to poor generalisation, whereas filled data, while degrading the standard model, substantially improve the generalised model, allowing >90%>90\% accuracy with only 25%25\% training data, comparable to the baselines. Appendix J Future Work and Technical Extensions While the Generalised Bernstein–Vazirani model demonstrates strong capabilities on synthetic data, scaling to complex, real-world distributions (e.g., Iris, Penguins) presents challenges related to spectral leakage and shot complexity. The primary source of error in current experiments is the misalignment between the discrete, hard-edged quantum basis and the continuous geometry of natural data. We propose two enhancements to the expressive representation. J.1 Adaptive Basis Alignment Standard interference bases are static, determined solely by fixed parameters. To align the basis with the dataset’s principal manifolds, we propose a hybrid variational protocol. We introduce a parametrised unitary V⁡()V( θ) applied to the parameter register |t⟩|t prior to interference. The objective is to maximise the sparsity of the measurement distribution P⁡(y,z,t|)P(y,z,t| θ). We define the cost function ℒ⁡()L( θ) as the Shannon entropy: ℒ()=−∑y,z,tP(y,z,t|)logP(y,z,t|).L( θ)=- _y,z,tP(y,z,t| θ) P(y,z,t| θ). (70) A classical pre-training loop minimises ℒ⁡()L( θ), rotating the basis manifold to maximise constructive interference for the specific target dataset. J.2 Apodised Activation Functions The current rectangle activation χrect(x) _rect(x) acts as a boxcar function, exhibiting high-frequency leakage (Gibbs phenomenon). We propose replacing the binary thresholding with apodised activations. By replacing the multi-controlled Toffoli in the activation step with a controlled rotation CRy(ϕ)CR_y(φ) on the ancilla, we can implement ”soft” trapezoidal windows: Uactiv|x⟩|a⟩=|x⟩(cos⁡ϕ⁡(x)2−sin⁡ϕ⁡(x)2iY)|a⟩,U_activ|x |a =|x ( φ(x)2I- φ(x)2iY )|a , (71) where ϕ⁡(x)φ(x) varies smoothly across the boundary margin δ. This acts as a low-pass filter in feature space, accelerating spectral decay to O⁡(1/ω2)O(1/ω^2) and concentrating signal energy.

Instant research discovery