An optimal quantum sampling regression algorithm for variational eigensolving in the low qubit number regime

I. INTRODUCTION

• Quantum simulation is exponentially hard classically but expected to be efficiently reproducible with quantum resources, motivating searches for useful quantum advantage [2].Source: §I · p. 1
• Hybrid quantum-classical variational algorithms are central to near-term quantum simulation because they operate with relatively small quantum resources during the NISQ era [3–6].Source: §I · p. 1
• The variational theorem identifies the ground-state approximation by minimizing the Hamiltonian expectation value, with analogous maximization or operator transformations targeting other eigenstates.Source: §I · pp. 1–2

A. Variational Quantum Eigensolver

• VQE prepares a parameterized quantum state, measures operator components repeatedly, combines their expectation values classically, and iteratively updates parameters toward a global minimum.Source: A. Variational Quantum Eigensolver · p. 2
• VQE repeats quantum evaluations according to the chosen classical optimizer, while the resulting converged parameters describe the desired eigenstate and its expectation value gives the eigenvalue.Source: A. Variational Quantum Eigensolver · p. 2

B. Operator averaging

• Expectation values are obtained by rewriting the target observable into measurable operators, collecting many measurement shots, and averaging their results.Source: B. Operator averaging · p. 2
• The operator decomposition must contain at most polynomially many addends so classical recombination remains efficient as the qubit count grows.Source: B. Operator averaging · pp. 2–3

C. Space parametrization and state preparation

• The ansatz seeks a smaller subspace than the exponentially growing phase space, often using heuristics or operator symmetries to narrow the searchable region.Source: C. Space parametrization and state… · p. 3
• A suitable parametrization can make the expectation-value function easier to optimize by avoiding unnecessary local minima and other optimization hazards.Source: C. Space parametrization and state… · p. 3
• Quantum circuits prepare states according to ansatz parameters, so their complexity is typically also required to be polynomial.Source: C. Space parametrization and state… · p. 3

D. Motivation and thesis

• VQE's cloud-access loop is time-consuming because each optimization cycle requires internet communication and queued samples, while future samples cannot be known before current results.Source: D. Motivation and thesis · p. 3
• The proposed trade-off uses extra classical resources to reduce quantum-processor access and investigate when quantum advantage can be achieved.Source: D. Motivation and thesis · p. 3

II. ALGORITHM OUTLINE

• Circuit rotations induce periodic expectation-value functions whose maximum frequencies can be bounded from circuit topology, enabling discrete Fourier reconstruction.Source: §II · p. 3
• For one parameter, 2S + 1 samples provide as many equations as Fourier unknowns, with spacing or oversampling available to mitigate sampling error.Source: §II · p. 4
• Finite precision and imperfect expectation estimates can make the linear system inconsistent, so QSR normalizes it and solves the resulting least-squares problem.Source: §II · p. 4
• Multidimensional Fourier regression extends the method to different bandwidths across n ansatz parameters, with a total sample requirement determined by the maximum bandwidth.Source: §II · p. 4
• QSR determines parameter bandwidths, samples the objective function, computes Fourier coefficients, and classically minimizes the resulting regression function.Source: §II · pp. 4–5
• The Nyquist-Shannon theorem shows that QSR needs one more than the strict lower bound 2S sample points, establishing optimality for fully reconstructing the objective function [20].Source: §II · p. 5

• Time complexity is emphasized because hybrid algorithms do not store intermediate quantum information classically, while retrievable quantum information remains limited.Classical memory limits may still become operationally relevant independently of asymptotic time complexity.Source: §III · p. 5
• The comparison treats classical computation as having unlimited memory, avoiding a separate analysis of memory-limited quantum advantage.Source: §III · p. 5
• The analysis also acknowledges that classical computers could eventually face memory limits that time-complexity comparisons do not capture.Source: §III · p. 5

A. Classical computation

• Classical quantum-state vectors and observable matrices require exponential space, ω(2^N), as the qubit count N grows.Source: A. Classical computation · p. 5
• Eigenvalue finding has a lower bound Ω(4^N) and a general spectral-decomposition upper bound O(8^N).The bounds follow from quadratic matrix-vector multiplication and cubic spectral-decomposition methods.Source: A. Classical computation · p. 5
• Simulating VQE through matrix-form expectation evaluations yields O(4^N n_p), where n_p is the optimizer complexity factor.This approach nests exponentially hard matrix multiplication inside the optimization loop.Source: A. Classical computation · p. 5
• No parametrization relation can remove exponential scaling in the general case, which reaches O(8^N) when n = O(2^N) and p = 1.Superlinear optimization can make the scaling worse.Source: A. Classical computation · p. 5

B. Variational Quantum Eigensolver

• VQE repeatedly evaluates target-operator expectation values inside a classical optimization loop, with objective-evaluation cost O(n_c^N q).Source: B. Variational Quantum Eigensolver · pp. 5–6
• Worst-case exhaustive search over the ansatz domain can make VQE exponential, whereas polynomial convergence would be needed for an efficient overall algorithm.Source: B. Variational Quantum Eigensolver · p. 6
• VQE becomes polynomial only when the parametrization ansatz has at most polynomial complexity in qubit number, such as n = O(N^t).Finding such an economical ansatz is difficult because Hilbert-space dimensionality grows exponentially.Source: B. Variational Quantum Eigensolver · p. 6
• Every optimization step relies heavily on the quantum processor, while non-convex stochastic objectives make polynomial-time convergence generally unreliable.Source: B. Variational Quantum Eigensolver · p. 6

C. Quantum Sampling Regression

• QSR divides computation into quantum sampling, regression construction, and optimization as separate stages.Source: C. Quantum Sampling Regression · p. 6
• Its total cost combines quantum sampling, cubic regression-system construction O(2^(3sn)), and optimization evaluation O(2^(sn)n_p).Regression construction also requires ω(2^(sn)) classical space.Source: C. Quantum Sampling Regression · p. 6
• QSR requires no more quantum sampling detail than VQE’s exhaustive search, because optimality implies x ≥ s under the same ansatz.Source: C. Quantum Sampling Regression · p. 6
• The classical side is dominated by solving the linear system, O(8^(sn)), but can become more efficient when the ansatz uses n = O(log N).Source: C. Quantum Sampling Regression · p. 6
• QSR generally satisfies p_QSR ≤ p_VQE because deterministic regression enables optimization techniques unavailable for stochastic objectives.Source: C. Quantum Sampling Regression · p. 7

Analytical model

• The comparison models VQE optimization with monomial complexity (mn)^p, defines r ≜ p/s, and compares quantum-resource requirements for VQE and QSR.Most model results depend on the quotient r rather than p or s independently.Source: §IV · p. 7

Efficiency comparison

• The resource-ratio distribution peaks at a characteristic ansatz size n*, while increasing p raises the peak and increasing m broadens it.Increasing r with fixed p and m shifts the graph by scaling it.Source: §IV · p. 7
• QSR can outperform VQE over a specific range of ansatz parameters, identified using the two real branches of the Lambert W function.The comparison determines boundary values n0 and n1 for the region where QSR is more efficient.Source: §IV · pp. 7–8
• The optimization-complexity power p affects overall efficiency but not the ansatz-parameter range in which QSR is more competitive.This follows because the relevant threshold equation is the only one that depends on p.Source: §IV · p. 7

Results

• For plotted values of m, p, and s, the quantum-advantage threshold can reach 100 ansatz parameters, while efficiency grows exponentially and QSR may greatly outperform VQE below that threshold.Figures 4 and 5 depict the threshold and efficiency quantities from eqs. (21) and (23).Source: §IV · p. 8, Figure 4 · p. 8, Figure 5 · p. 8

Limitations and scope

• The analytical results are approximate because they use only a lower bound on VQE optimization complexity, with m and p fitted from VQE runs and s obtained from circuit topology.More precise numerical analysis could use a detailed description of the VQE optimizer; the discussion applies broadly when the ansatz-parameter count remains low, even with many qubits.Source: §IV · pp. 8–9

V. APPLICATIONS

• QSR fixes the minimum samples needed to reproduce the expectation-value function, while allowing oversampling for precision or undersampling for performance.Knowing all samples in advance also permits batching them into fewer backend connections, unlike VQE's iterative sampling loop.Source: §V · p. 9
• Undersampling lowers the Fourier frequency cutoff, trading precision for approximate solutions that can remove small-wavelength oscillations and burdensome local minima.Such low-resolution results can initialize later QSR iterations or VQE.Source: §V · p. 9
• QSR treats the expectation-value function as a black box requiring only the parameter count and circuit-imposed maximum frequency cutoff.This permits classical optimization of an approximation without the usual exponentially growing matrix formulation.Source: §V · p. 9
• Classical optimization is easier on QSR's regression function because direct quantum evaluations fluctuate between queries, shifting minima and complicating convergence and numerical derivatives.The regression function has shown practical usefulness for convergence under these stochastic sampling effects.Source: §V · p. 9
• QSR can provide an intermediate simulator-to-hardware stage by isolating regression behavior, storing Fourier coefficients, and reducing repeated processor access.This may help analyze non-local effects without simultaneously handling stochastic function evaluation.Source: §V · pp. 9–10
• QSR is especially useful when quantum resources are scarce, classical resources are affordable, VQE convergence is difficult, or a smooth objective is needed for derivatives.The approach is presented as relevant to NISQ hardware because it can reduce backend overheads and wait times.Source: §V · pp. 9–10

VI. BENCHMARKING

• The benchmark targets deuteron binding energy with a leading-order pionless effective-field-theory Hamiltonian and a low-depth, problem-specific unitary coupled-cluster ansatz.It includes a two-qubit, single-parameter Hamiltonian and a three-qubit, two-parameter Hamiltonian shown in fig. 6.Source: §VI · p. 10, Figure 6 · p. 10
• Circuit topology predicts the frequency bounds: the single-parameter circuit has S_θ = 1, while propagation and overlapping rotations give the second parameter S_η = 2.The bounds connect the parametrization circuit structure to the Fourier domain used by QSR.Source: §VI · p. 10
• QSR's two-parameter deuteron benchmark improves upon the reproduced results from [34], as reported in table I.The comparison uses a regression with S_q = S_max = 2 and T = 25 evenly spaced samples.Source: §VI · p. 10, Table I · p. 10
• Figure 7 contrasts raw quantum-chip samples, shown as an expectation-value triangulation, with the QSR approximation obtained using the minimum sample count from eq. (6).The figure concerns the two-ansatz-parameter deuteron Hamiltonian model.Source: §VI · p. 10, Figure 7 · p. 11

VII. CONCLUSIONS

• Cloud-based VQE incurs substantial execution delays because optimization cycles require repeated internet requests and unconstrained evaluations, including costly intermediate quantities.The paper identifies this access pattern as a practical obstacle to near-term quantum-advantage applications.Source: §VII · p. 11
• QSR builds a regression function from the minimum number of quantum-processor samples and optimizes that function classically using Fourier analysis of the target expectation value.The proposed strategy is intended to address the request bottleneck in VQE.Source: §VII · p. 11