The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical framework for combinatorial optimization on near-term quantum devices. A central bottleneck is the classical estimation of its variational parameters γ and β, which must be optimized over a high-dimensional, non-convex landscape corrupted by sampling noise. We observe that the classical feature matrices constructed from QAOA measurement samples exhibit pronounced low-rank structure, and exploit this property for noise-robust, reduced-dimension parameter search. We present the Hamiltonian-Guided Leverage Embedding (HGLE) algorithm - a hybrid pipeline that encodes low-energy quantum samples into a weighted Ising feature matrix and compresses it via leverage-score row sampling, provably preserving the dominant rank-rsubspace geometry. The compressed representation drives a classical trust-region loop for (γ, β) estimation at a fraction of the original cost. We provide formal guarantees for rank preservation and energy approximation error, and demonstrate robustness across problem types (Max-Cut, Maximum Independent Set) and graph topologies of varying density.
The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical framework for combinatorial optimization on near-term quantum devices. A central bottleneck is the classical estimation of its variational parameters γ and β, which must be optimized over a high-dimensional, non-convex landscape corrupted by sampling noise. We observe that the classical feature matrices constructed from QAOA measurement samples exhibit pronounced low-rank structure, and exploit this property for noise-robust, reduced-dimension parameter search. We present the Hamiltonian-Guided Leverage Embedding (HGLE) algorithm - a hybrid pipeline that encodes low-energy quantum samples into a weighted Ising feature matrix and compresses it via leverage-score row sampling, provably preserving the dominant rank-rsubspace geometry. The compressed representation drives a classical trust-region loop for (γ, β) estimation at a fraction of the original cost. We provide formal guarantees for rank preservation and energy approximation error, and demonstrate robustness across problem types (Max-Cut, Maximum Independent Set) and graph topologies of varying density.
Processing qubit Hamiltonians derived from electronic-structure problems can become classically prohibitive because many downstream manipulations still rely on dense operator constructions whose cost grows exponentially with qubit number. We introduce Qronecker, a cut-aware low-rank Kronecker decomposition algorithm that turns Hamiltonian compression into a certifiable, resource-aware decision primitive. Operating entirely in Pauli coefficient space, Qronecker avoids forming dense 2^n x 2^n matrices, constructs low-rank Kronecker approximations under a chosen bipartition, and returns both an instance-specific compressibility curve and a state-independent worst-case energy certificate that links rank and cut choices to conservative energy-deviation bounds. Across molecular benchmarks comprising hundreds of systems up to 30 qubits, we find that traceless low-rank structure is common but heterogeneous: many screened systems reach high coefficient-space fidelity at low rank, yielding large savings in classical preprocessing and conditional reductions in downstream circuit-resource proxies, while the certificate remains valid but conservative on the auditable subset. The same analysis shows that fixed global fidelity targets are not generally sufficient for chemistry-level guarantees, motivating adaptive rank and cut selection. These results position Qronecker as a certifiable compression primitive for rank and cut selection in quantum-chemistry Hamiltonian processing.
Abstract Learning the Hamiltonian of a quantum processor is important for controlling and certifying quantum devices, but the state preparation and measurement used to probe it are themselves imperfect. Even when exact data identify an interaction uniquely, identifiability alone does not determine finite-data precision. Here we show, for n-qubit Markovian dynamics under geometric regularity conditions, that the local uncertainty of a Hamiltonian coefficient scales either linearly or as the square root of the entrywise error in the generator matrix in the readout gauge. Square-root scaling occurs exactly when a gauge transformation moves the coefficient at first order while noise positivity can be restored at second order, and real noise correlations drive this first-order change. As a consequence, under suitable dynamical and readout conditions, square-root scaling forces uniformly valid confidence intervals from N shots to have expected length Ω(N⁻¹⁄⁴), even for adaptive local experiments. Under a common generator norm bound, estimating this matrix attains this rate up to logarithmic factors. Experiments on three superconducting processors show that additional measurement bases increase the visibility of injected rotations at a matched number of shots. Whether a coupling admits the usual N⁻¹⁄² scaling is therefore set by how noise correlations and positivity constrain its gauge directions.
Abstract Quantum processing units are scarce. Schedulers dispatch Max-Cut subgraphs to them anyway, rarely pausing to ask whether a cheap classical heuristic would have closed the gap just as well. This routing blindness wastes exactly the resource it can least afford to waste. QSE—a Topology-Driven Quantum Suit-ability Estimator—answers a narrower question than either QAOA or a classical heuristic can answer alone. Using only polynomial-time graph topology features, its four-phase pipeline routes each Max-Cut subgraph to the Quantum Approximate Optimization Algorithm (QAOA), to a classical greedy heuristic, or to human review, whichever the topology signal warrants. Central to this decision is a single quantity: the expected greedy gap, f cmax = 1 − ¯ c greedy /c *. It captures how far a 15-ordering-averaged greedy heuristic falls short of the exact Max-Cut optimum—no more, no less. 137 graphs, drawn from 18 structural families at N = 16, clear three pre-registered validation bars. Hardness exists (max(f cmax) = 0.2444); a cross-validated random forest learns it from topology alone (R 2 RF = 0.527 ± 0.11); and, more tellingly, a single feature—transitivity—tracks it almost linearly (|r| = 0.676). Reaching these results required repairing a self-calibrating sign-alignment layer for QAOA simulation, introduced after two earlier implementations silently violated the [0, m] physicality bound on every one of 105 runs; the repair eliminates the violation entirely. Trained on the resulting 105 physically valid QAOA evaluations , a meta-router (regressor R 2 CV = 0.506 ± 0.119; classifier accuracy 76.2%, ROC-AUC 0.834) feeds a production scheduler. That scheduler computes a polynomial-time spectral proxy for hardness and reports per-decision uncertainty as a tree-ensemble spread. Rather than forcing a verdict, ambiguous cases are downgraded to REVIEW. Alongside these results, we document three classes of engineering failure—a Hamiltonian sign-convention bug, a graph-reconstruction seed mismatch, and five fabricated-input bugs in an earlier scheduler—each diagnosed and corrected, since the diagnoses prove as informative as the final numbers.
Abstract We present a unified, practical pipeline for a quantum-assisted financial recommender system. Investor similarity graphs are constructed from high-dimensional profiles, compressed via normalized Laplacian spectral embedding, and optimized using the Quantum Approximate Optimization Algorithm (QAOA) on GPU-based quantum simulators (cuQuantum, Cirq-GPU, Cirq with IonQ simulation). We consolidate theoretical derivations (QUBO/Ising mapping, spectral compression correctness, QAOA parameter optimization) and implementation details (feature selection, Nyström extension, QAOA parameter optimization). The key contribution is a unified theoretical framework that directly connects QAOA optimization to classification performance, eliminating disjoint post-processing steps. We provide complete, rigorous proofs of all error bounds, including a variance bound for QAOA concentration, an explicit treatment of the degree-matrix discrepancy, unbalanced misclassification, effective VC dimension, and the QAOA approximation ratio. Two explicit caveats are documented: (i) the overcomplete feature regime is rank-deficient, with generalization controlled solely by the downstream bottleneck and dropout; and (ii) the unconstrained PAC bound is vacuous for target accuracies above roughly (15%), which formally motivates the Laplacian-constrained effective VC dimension. Results show that spectral compression enables tractable quantum optimization for mid-sized problems and that Cirq-GPU offers a favorable speed-accuracy trade-off. We discuss deployment considerations for financial institutions, including explainability, compliance, and workflows under the likely hybrid classical-quantum architecture. Mathematics Subject Classification (2020) 68Q12 · 81P68 · 91G10 · 68T05 · 90C27
Estimating molecular energies on quantum computers requires repeated measurements of many Pauli terms, making sampling a major resource cost. Measurement design chooses which compatible terms are measured together and allocates a finite shot budget among bases to minimize the variance of an energy estimator. We introduce variance-guided measurement group construction (VGMC), which reduces variance beyond optimization on existing measurement bases by changing which Hamiltonian terms share measurement shots. After including every Hamiltonian term measurable in each existing basis, we jointly optimize estimator coefficients and shot allocations to separate inefficient use of these measurements from limitations of their measurement combinations. We compare a candidate's benefit with the cost of withdrawing shots from existing bases, and use the resulting scores to guide greedy construction of qubit-wise commuting groups followed by joint re-optimization. With exact covariances, VGMC outperformed the state-of-the-art measurement design methods across the molecular benchmarks where it introduced additional measurement bases, achieving variance reductions of 18.19%-23.38%. The gains persisted with approximate covariances, and simulations with finite shots indicated lower estimated shot requirements near chemical accuracy. These results show that optimizing how measurements are combined can also guide which terms are measured together, offering a route to reducing the sampling overhead of variational quantum simulation while retaining local measurements on current and near-term devices.
Let f=EXACT3,45 be the Boolean function that equals 1 exactly on inputs of Hamming weight 3 or 4. Earlier numerical studies reported success probabilities close to one using three queries, but the existence of an exact three-query algorithm had remained unresolved. This paper settles this problem by proving that the exact quantum query complexity of f is 4. For the lower bound, we express every three-query algorithm through layer-by-layer Gram matrices of low-degree Fourier coefficients. We then construct a fixed rational dual certificate whose slack matrices are all positive definite. This certificate separates the necessary Gram-matrix region from the exact-output condition and therefore rules out every exact algorithm using at most three queries in the stated model. The positivity verification reduces to five small rational matrices and Sylvester's criterion. For the upper bound, we invoke the previously known four-query algorithm for the seven-bit function EXACT3,47 and apply the standard padding reduction. To quantify the near-exact behavior, we use the same certificate to derive a valid, though not claimed tight, lower bound 4377948819244925600>0 on the worst-case error of every algorithm using at most three queries. This positive error gap is compatible with the near-unit success probabilities reported in earlier numerical studies, which do not establish exact computation.