Every Ising energy is a known linear function of measured spin features, yet the standard QAOA estimator discards this structure. We introduce Hamiltonian-Guided Leverage Embedding (HGLE), which projects Hamiltonian coefficients onto the leading subspace of a measured feature matrix. The fraction of coefficient norm outside this subspace yields a deterministic, same-batch certificate bounding how much compression distorts the objective. This certificate is minimax-tight - no linear estimator on the same subspace achieves smaller worst-case error. We establish four results beyond the pointwise certificate. First, a held-out pilot projector with summable failure allocation gives population-distortion intervals valid over an unbounded adaptive sequence. Second, coefficient projection strictly reduces estimator variance, with the reduction equal to the variance of the discarded component. Third, one SVD basis simultaneously certifies Kobservables, defeating the rank-1 degeneracy of single-Hamiltonian compression. Fourth, the compression quality is governed by graph topology through the expected Gram matrix.
Every Ising energy is a known linear function of measured spin features, yet the standard QAOA estimator discards this structure. We introduce Hamiltonian-Guided Leverage Embedding (HGLE), which projects Hamiltonian coefficients onto the leading subspace of a measured feature matrix. The fraction of coefficient norm outside this subspace yields a deterministic, same-batch certificate bounding how much compression distorts the objective. This certificate is minimax-tight - no linear estimator on the same subspace achieves smaller worst-case error. We establish four results beyond the pointwise certificate. First, a held-out pilot projector with summable failure allocation gives population-distortion intervals valid over an unbounded adaptive sequence. Second, coefficient projection strictly reduces estimator variance, with the reduction equal to the variance of the discarded component. Third, one SVD basis simultaneously certifies Kobservables, defeating the rank-1 degeneracy of single-Hamiltonian compression. Fourth, the compression quality is governed by graph topology through the expected Gram matrix.
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.
Abstract This paper studies how much Quantum Processing Unit (QPU) work can be avoided while preserving optimization quality in the Quantum Approximate Optimization Algorithm (QAOA). Using exact statevector simulation of QAOA on six graph optimization problems across seven graph families, three baselines are compared: a naive QPU-centric workflow with 30 quantum evaluations, a best-practice workflow that separates classical parameter optimization from a single QPU evaluation, and a classical-only solver. Six QPUminimization strategies are evaluated: preprocessing, pretraining, surrogate modeling, adaptive stopping, adaptive shots, and measurement reuse. Quality is measured using normalized expected value rather than the saturated best-of-b metric. The key findings are: the best-practice baseline achieves 510- to 2070-fold shot reduction across 8 to 16 qubits with at most 0.4 percent quality loss relative to naive QAOA; quality improves with QAOA depth from 0.82 to 0.91 while the gap between naive and best-practice remains negligible; four of six strategies achieve 100 percent quality retention at depth 3; quality is stable across graph families ranging from 0.77 to 0.87; and a structural predictor achieves perfect prediction on held-out graph families. These results support the thesis that the required QPU budget is a structured, predictable function of the problem instance and workflow policy, rather than a fixed algorithmic constant.