OST-QAOA • Noncommutative operator-spectral truncated priors • Query-efficient variational quantum optimization

Operator-Spectral Truncated Priors for Query-Efficient QAOA

For low-depth QAOA, the dominant practical cost is the number of objective-function queries spent tuning the variational angles on each graph — and a warm-start point alone does not tell the optimizer which angle directions deserve exploration under a fixed budget. OST-QAOA learns and searches in operator space. Each graph is mapped to two noncommuting $2p\times2p$ operators $\mathcal A_G,\mathcal B_G$ built from its Laplacian spectrum, degree moments, and topology; the resulting angle operator is spectrally truncated to a rank-$n$ covariance whose eigenbasis supplies the collective, cross-layer search directions probed by a deterministic query policy. Transporting the spectral-truncation–kernel construction of noncommutative $C^{*}$-algebraic kernel machines into variational quantum optimization, the truncation parameter $n$ controls a representation-versus-query-budget tradeoff through the prior's effective dimension $d_{\mathrm{eff}}(n)$; we prove the truncated prior is positive definite and Loewner-contractive, that it recovers the commutative diagonal prior in the single-direction limit, and that the expected queries to a target ratio scale with $d_{\mathrm{eff}}(n)$. On an exact-statevector MaxCut benchmark the method outperforms a budget-matched physics baseline on every paired held-out instance and reaches comparable quality in roughly half the queries. The complete method, theory, and evidence are regenerated end-to-end by the installable package uq-qaoa from a single deterministic seed.

Variational quantum algorithms Operator-valued priors Spectral truncation Noncommutativity Query complexity

Molena Huynh · North Carolina State University · molena.huynh@jmp.com

OST-QAOA vs. budget-matched TQA

+0.112

Mean approximation-ratio advantage over a budget-matched TQA coordinate-refinement baseline ($0.820$ vs.\ $0.708$), with a paired bootstrap 95\% interval $[+0.083,+0.142]$ and $16/16$ paired held-out instances (sign-test $p<10^{-4}$) at $p{=}3$, $Q{=}24$.

Queries to comparable quality

2.4× fewer

OST-QAOA reaches $98\%$ of the best observed ratio in $10.1$ objective queries on the primary seed ($10.5$ across ten seeds) against $\approx 25$ for the baseline ($\bar Q_{0.98}$) — the operationally relevant quantity in the query-budget tradeoff bound.

Spectral-truncation tradeoff

Interior $n^{\star}$

A truncation sweep over $n\in\{1,\dots,2p\}$ exhibits an interior optimum: under-truncation and no truncation both degrade, while the effective dimension $d_{\mathrm{eff}}(n)$ rises monotonically — the query-budget analogue of the representation–complexity tradeoff of spectral-truncation kernels.

AI for quantum, at HPC scale

OST-QAOA is an operator-valued learned prior: the search directions are read off a spectrally truncated operator built from each graph rather than hand-tuned per instance, reaching comparable solution quality in ~2.4× fewer objective queries. Those objectives are exact statevector expectations — the workload GPU statevector backends (NVIDIA cuQuantum / cuStateVec) are built to accelerate — and every figure and number on this page regenerates from a single deterministic seed.

Problem Setting

QAOA, MaxCut, and the objective-query model

The setting is depth-$p$ QAOA for MaxCut, with cost measured in objective queries rather than wall-clock time. Let $G=(V,E)$ be an undirected graph with $n=|V|$ vertices. The MaxCut cost Hamiltonian, the depth-$p$ QAOA state with mixer $H_M=\sum_i X_i$, and the exact objective are

$$H_C(G)=\sum_{(i,j)\in E}\frac{1-Z_iZ_j}{2},\qquad \lvert\psi_G(\theta)\rangle=\prod_{\ell=1}^{p} e^{-i\beta_\ell H_M}\,e^{-i\gamma_\ell H_C(G)}\,\lvert+\rangle^{\otimes n},\qquad f_G(\theta)=\langle\psi_G(\theta)\rvert H_C(G)\lvert\psi_G(\theta)\rangle.$$

The parameter vector is $\theta=(\gamma_1,\dots,\gamma_p,\beta_1,\dots,\beta_p)\in\Theta_p=[0,2\pi)^p\times[0,\pi)^p$, and the approximation ratio is $r_G(\theta)=f_G(\theta)/C_G^\star$ with optimal cut value $C_G^\star$. Each evaluation of $f_G$ dominates the budget, so cost is counted in objective queries $Q=\#\{\theta\text{ evaluated}\}$, and a method is judged by the rate at which quality rises with that budget—the best-so-far query curve

$$Q\;\longmapsto\;\max_{1\le q\le Q} r_G(\theta_q),\qquad\text{with}\qquad Q_G(\tau)=\min\{q: r_G^{\mathrm{best}}(q)\ge\tau\}.$$

In a measurement-limited regime, attaining comparable quality in substantially fewer queries outweighs a marginal objective gain obtained after many additional evaluations. OST-QAOA addresses precisely this trade-off: it concentrates the query budget on the collective eigendirections of a truncated, noncommuting operator prior, evaluating physics and transfer anchors first and then refining along the directions that carry the most variance.

Method

A truncated, noncommuting operator prior on QAOA angle space

For a graph $G$, OST-QAOA constructs two symmetric $2p\times2p$ angle-space operators $\mathcal A_G,\mathcal B_G$ from the normalized Laplacian spectral moments $m_\lambda$, the centered degree moments $m_d$, and a normalized topology descriptor $\phi(G)$. The two generators do not commute; their commutator $\mathcal C_G=[\mathcal A_G,\mathcal B_G]$ enters a single raw angle operator:

$$\mathcal A_G=\operatorname{Toeplitz}\!\big(0.70\,m_\lambda+0.30\,\phi(G)\big),\quad \mathcal B_G=\operatorname{sym}\!\big[\operatorname{roll}\operatorname{Toeplitz}(0.55\,m_d+0.45\,\phi(G)_{\mathrm{rev}})\big],\quad \mathcal O_G=\operatorname{sym}\!\big(0.55\,\mathcal A_G+0.45\,\mathcal B_G+\omega\,\mathcal C_G^{\!\top}\mathcal C_G\big).$$

The raw operator is spectrally truncated to rank $n$ — $\mathcal O_{G,r}=U_r\Lambda_r U_r^{\!\top}$ with nonnegative-clipped eigenvalues — and the truncated operator, rather than a diagonal uncertainty vector, supplies the leading search geometry of an operator-dominated covariance ($\beta=0.8$):

$$\mathcal O_{G,r}=U_r\Lambda_r U_r^{\!\top},\qquad \Sigma_G=\beta\,\frac{\mathcal O_{G,r}}{\operatorname{tr}\mathcal O_{G,r}}+\Big(1-\tfrac{\beta}{2}\Big)\frac{\Sigma_G^{\mathrm{nbr}}}{\operatorname{tr}\Sigma_G^{\mathrm{nbr}}}+\epsilon I.$$

The posterior mean $\mu_G$ is a Gaussian-weighted blend of the reference angles of the $k$ nearest training graphs in operator-signature space with the fixed TQA schedule. The query policy then diagonalizes $\Sigma_G=V\Lambda V^{\!\top}$ and probes its collective eigendirections $\pm s\sqrt{\lambda_j}\,v_j$ — cross-layer angle deformations, not the raw coordinates — in descending variance order until the objective-query budget is spent.

The construction is motivated by, but deliberately distinct from, the spectral-truncation–kernel framework for noncommutative $C^{*}$-algebraic kernel machines, where truncation of a positive-definite kernel controls noncommutativity and trades representation power against model complexity. Here the truncated noncommuting operator is not a supervised regression kernel: it is a graph-conditioned prior over QAOA angles, and the truncation parameter $n$ — analogous in spirit to spectral truncation in $C^{*}$-algebraic kernels — instead controls the number of QAOA angle directions the search covariance can emphasize. The generators are designed not to commute, so that $\mathcal C_G=[\mathcal A_G,\mathcal B_G]\neq 0$ in general, encoding local and global structure that no single symmetric generator captures; the off-diagonal operator geometry is then used operationally, with the policy probing the collective eigendirections of $\Sigma_G$ rather than the raw angle coordinates.

Operator map

Noncommuting generators

Two graph-derived Toeplitz operators $\mathcal A_G,\mathcal B_G$ encode local/global spectral and degree structure; their commutator $[\mathcal A_G,\mathcal B_G]$ injects noncommutativity, so the operator carries cross-coordinate interactions that a diagonal prior cannot.

Spectral truncation

Rank-$n$ covariance

Retaining the $n$ leading operator directions caps the number of collective angle modes the search explores. The truncation parameter $n$ is the single knob controlling the representation-versus-query-budget tradeoff.

Query policy

Eigendirection refinement

Anchors (TQA, operator mean, nearest neighbour, global) are evaluated first; remaining queries probe $\pm s\sqrt{\lambda_j}\,v_j$ along the covariance eigenvectors, an auditable deterministic sequence recorded as a full query trace.

Guarantees

A query-budget tradeoff governed by effective dimension

The truncated operator prior admits a small theory that mirrors, in the query budget, the representation-versus-complexity tradeoff of spectral-truncation kernels. The covariance is a valid, contractive search frame; the truncation parameter controls how many collective directions the policy explores; and the number of objective queries to a target ratio is governed by the prior's effective dimension.

Propositions — Positive definiteness, monotone truncation, commutative limit

For any floor $\epsilon>0$ and weights $\omega,\beta\ge0$, $\Sigma_G$ is symmetric positive definite, so its eigendecomposition $\Sigma_G=V\Lambda V^{\!\top}$ yields an orthonormal frame with strictly positive directional variances. Spectral truncation is Loewner-monotone in the rank, $\mathcal O_{G,r}\preceq\mathcal O_{G,r+1}$, interpolating between a one-direction prior and the full operator prior. At $\omega=0$ the operator is independent of the commutator, and restricting $\Sigma_G$ to its diagonal makes the eigenframe the coordinate axes — recovering exactly per-angle coordinate refinement. The commutator-off and diagonal-covariance variants are therefore the commutative special cases of OST-QAOA.

Proposition — Query-budget tradeoff under coverage

With effective dimension $d_{\mathrm{eff}}(\Sigma)=\big(\sum_j\lambda_j\big)^2\big/\sum_j\lambda_j^2$ and $m(r)$ the near-optimal mass captured by the leading $r$ operator directions, the expected queries to reach a target ratio $\tau$ obey

$$\mathbb E\!\big[Q_G(\tau)\big]\;\lesssim\;\frac{c\,d_{\mathrm{eff}}\!\big(\Sigma_G^{(r)}\big)}{m(r)},\qquad d_{\mathrm{eff}}\!\big(\Sigma_G^{(r)}\big)\le r+\mathcal O(\epsilon).$$

The numerator decreases with truncation while $m(r)$ is nondecreasing, so the minimiser $r^{\star}$ is interior whenever aggressive truncation sheds near-optimal mass faster than it concentrates the search. This is the query-budget analogue of the representation-versus-complexity tradeoff of spectral-truncation kernels: where their truncation parameter trades approximation against generalisation, OST-QAOA's trades near-optimal coverage against the number of objective queries. The benchmark below instantiates the bound — $d_{\mathrm{eff}}(n)$ rising monotonically with the rank and an interior optimum $n^{\star}$ in the truncation sweep.

Evidence

Controlled exact-statevector benchmark

The benchmark holds the query budget constant so that differences reflect search efficiency alone. Every method receives the same $Q{=}24$ exact-statevector objective queries on 16 held-out instances (four per family: Erdős–Rényi, random-regular, Watts–Strogatz, Barabási–Albert) at $n\in\{8,10\}$, $p{=}3$, truncation rank $4$, commutator weight $4.0$, with the global seed fixed at $260{,}424{,}803$. All objectives are exact statevector expectations and all MaxCut normalizers are exact brute-force optima. The table is transcribed verbatim from the artifact (table01_headline).

Method	Mean ratio ↑	$\Delta$ vs. TQA+coord. [95% CI]	Wins	$\bar Q_{0.98}$ ↓
Random	0.743	+0.035 [+0.001, +0.070]	11/16	24.1
TQA (single ramp)	0.614	−0.093 [−0.156, −0.040]	0/16	25.0
TQA + coordinate	0.708	0.000	—	25.0
$k$-NN + coordinate	0.751	+0.043 [+0.019, +0.068]	13/16	23.6
OST diagonal	0.810	+0.102 [+0.073, +0.131]	16/16	13.1
OST-QAOA (ours)	0.820	+0.112 [+0.083, +0.142]	16/16	10.1

OST-QAOA is the strongest method under the matched query budget, winning on $16/16$ paired held-out graphs (sign-test $p<10^{-4}$) with a mean advantage of $+0.112$ over budget-matched TQA coordinate refinement. It is also markedly more query-efficient: it reaches $98\%$ of the best observed ratio in a mean of $10.1$ objective queries against $25.0$ for the baseline ($\bar Q_{0.98}$) — a $\approx 2.4\times$ reduction that holds across ten seeds ($+0.107\pm0.011$).

Spectral-truncation sweep (rank $n$)	Noncomm. (on)	Comm. (off)	$d_{\mathrm{eff}}$
$n=1$ (aggressive truncation)	0.814	0.812	2.50
$n=2$	0.812	0.818	2.96
$n=3$	0.815	0.812	3.24
$n^{\star}=4$ (operating point)	0.820	0.817	3.46
$n=5$	0.810	0.810	3.64
$n=6=2p$ (no truncation)	0.810	0.812	3.64

The truncation sweep exhibits the interior optimum predicted by the query-budget bound: aggressive truncation ($n{=}1$) underfits the angle geometry and no truncation ($n{=}2p$) over-diffuses the covariance, while the effective dimension $d_{\mathrm{eff}}(n)$ rises monotonically with the rank. In the design ablation, restricting the search to diagonal (commutative) directions falls to $0.810$ ($-0.010$), localizing the advantage to the off-diagonal, noncommuting operator geometry; the explicit squared-commutator energy term is near-neutral at the operating point, which we report rather than overclaim.

Read the OST-QAOA paper (PDF) Reproducible code artifact

Significance

Why query efficiency is the operationally relevant axis

In low-depth QAOA the dominant practical cost is not the circuit but the outer loop: the number of objective-function evaluations — each a full quantum-circuit execution, or a costly classical statevector simulation — spent tuning the variational angles on every new instance. A warm start that only supplies a good point still leaves the optimizer to discover, from scratch, which directions in angle space are worth probing. OST-QAOA supplies both: an operator-derived posterior mean and, through the spectrally truncated rank-$n$ covariance, the collective cross-layer search directions themselves. The measured consequence is a $\approx 2.4\times$ reduction in objective queries to comparable quality — the quantity that, on hardware, translates directly into shots and wall-clock on the device.

What the result is

A budget-matched, paired, leakage-controlled win

Every method receives the identical $Q{=}24$ exact-statevector query budget on $16$ family-held-out instances. OST-QAOA wins all $16$ paired comparisons against budget-matched TQA coordinate refinement (sign-test $p<10^{-4}$), at a $+0.112$ mean approximation-ratio advantage.

Where the gain comes from

Off-diagonal operator geometry, not just a point

Ablating the search to diagonal (commutative) directions removes a measurable part of the advantage ($0.820\to0.810$), localizing the gain to the noncommuting, off-diagonal structure of the angle operator — exactly the object the spectral truncation preserves.

Honest scope

A controlled method study, not a speedup claim

Results are exact-statevector MaxCut on synthetic graph families ($n\in\{8,10\}$, $p{=}3$); the margin is configuration-dependent. This is a fully reproducible, audit-sized method study — not a hardware-scale or asymptotic-advantage claim, and stated as such.

Figures from the manuscript

The evidence, as it appears in the paper

Every panel below is a figure from the manuscript, rendered from the artifact that the installable uq-qaoa package regenerates from a single deterministic seed. No number on this page is entered by hand.

Operator spectrum and rank-n spectral truncation of the QAOA angle operator — Operator construction & spectral truncation

Each graph maps to two noncommuting $2p\times2p$ angle-space operators; their commutator enters a single operator that is spectrally truncated to a rank-$n$ covariance. The spectrum shows how truncation concentrates the search onto the leading collective directions.

See in paper

Approximation ratio of OST-QAOA versus baselines at matched query budget — Controlled benchmark at matched budget

Mean approximation ratio across the six methods at the identical $Q{=}24$ query budget on $16$ family-held-out instances. OST-QAOA attains the highest ratio ($0.820$); the diagonal/commutative ablation isolates the contribution of the off-diagonal operator geometry.

See in paper

Truncation sweep showing an interior optimum in rank n — Interior optimum of the truncation sweep

Sweeping the truncation rank $n\in\{1,\dots,2p\}$ exhibits the interior optimum predicted by the query-budget bound: aggressive truncation underfits the angle geometry, no truncation over-diffuses the covariance, and the operating point sits at $n^{\star}{=}4$.

See in paper

Best-so-far approximation ratio versus number of objective queries — Query-efficiency frontier

Best-so-far approximation ratio versus the number of objective queries. OST-QAOA reaches $98\%$ of the best observed ratio in a mean of $10.1$ queries against $25.0$ for the budget-matched baseline — the $\approx2.4\times$ reduction that defines the result.

See in paper

Interactive Demonstration

Live in-page QAOA demonstration

The workflow runs in the page itself: generate a graph, predict its QAOA angles, and inspect the returned parameters without leaving this view. If the API is unavailable, the demonstration falls back to an in-browser exact depth-1 simulation with local refinement, so it remains functional offline.

Interactive Controls

Generate a weighted graph and predict QAOA parameters

This is a compact live view of the repository demonstration, meant for quick inspection of the operator-prior parameterization workflow rather than full benchmark reproduction.

Number of nodes

The range is kept small so exact browser-side fallback remains responsive and the visual graph remains readable.

Open full QAOA notebook Open combined notebook

6 nodes · no edges yet — click Random Graph

Headline result (exact statevector, p=3, Q=24): OST-QAOA mean ratio 0.820 vs 0.708 budget-matched TQA+coordinate (delta +0.112, 16/16 paired wins); reaches 98% of the best observed ratio in 10.1 objective queries vs 25.0 (~2.4x fewer; +0.107+/-0.011 across ten seeds).

Paper, Code & Notebooks

Reproducible materials

Every claim on this page is backed by released material: the OST-QAOA manuscript, its installable and deterministic code artifact, and the full repository source. The entire manuscript — every figure, table, CSV summary, and query trace — is regenerated from a single seed by:

cd submission/code
pip install .
uqqaoa-reproduce --output-dir . --depth 3 --budget 24 --rank 4 --commutator-weight 4.0

OST-QAOA manuscript

Operator-Spectral Truncated Priors for Query-Efficient QAOA — the noncommutative operator construction, the positive-definiteness, monotone-truncation, commutative-limit, and query-budget-tradeoff results, and the controlled exact-statevector benchmark.

PDF

OST-QAOA code artifact (uq-qaoa)

Installable Python package (python/uq_qaoa/) exposing a CLI (uqqaoa-reproduce) and Python API; pip install . regenerates every figure, table, CSV, and query trace deterministically from the global seed.

Browse code

Repository source

Source code, outputs, figure-generation scripts, and manuscript assets for the complete project.

Repository

References

Related work and bibliography

OST-QAOA sits at the intersection of two lines of prior art. The first is QAOA parameter transfer and concentration: objective values concentrate for fixed parameters on typical instances [5], [3], optimal parameters concentrate with system size [6], and angles trained on one graph transfer to others [7], [8], with Trotterized–annealing (TQA) schedules supplying strong instance-independent warm starts [4]. These results motivate transferring structure between graphs but do not specify a budgeted search geometry — the directions, and their relative scales, along which a few queries should be spent once a warm start is in hand. The second line is the spectral-truncation–kernel framework of Hashimoto et al. [9], in which truncation of positive-definite $C^{*}$-algebraic kernels controls noncommutativity and trades representation power against model complexity. OST-QAOA adopts that design idea — finite-rank noncommutativity as a tractable way to encode interaction — but transports it from supervised vector-valued regression into a graph-conditioned prior over QAOA angles paired with a deterministic objective-query policy, asking what it buys in the operational currency that limits near-term QAOA [1], [2]: the number of objective queries.

E. Farhi, J. Goldstone, and S. Gutmann, “A Quantum Approximate Optimization Algorithm,” arXiv 2014. arXiv:1411.4028
J. Preskill, “Quantum Computing in the NISQ Era and Beyond,” Quantum 2, 79 (2018). doi:10.22331/q-2018-08-06-79
L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, “Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices,” Phys. Rev. X 10, 021067 (2020). doi:10.1103/PhysRevX.10.021067
S. H. Sack and M. Serbyn, “Quantum Annealing Initialization of the Quantum Approximate Optimization Algorithm,” Quantum 5, 491 (2021). doi:10.22331/q-2021-07-01-491
F. G. S. L. Brandão, M. Broughton, E. Farhi, S. Gutmann, and H. Neven, “For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances,” arXiv 2018. arXiv:1812.04170
V. Akshay, D. Rabinovich, E. Campos, and J. Biamonte, “Parameter Concentrations in Quantum Approximate Optimization,” Phys. Rev. A 104, L010401 (2021). doi:10.1103/PhysRevA.104.L010401
A. Galda, X. Liu, D. Lykov, Y. Alexeev, and I. Safro, “Transferability of Optimal QAOA Parameters between Random Graphs,” in 2021 IEEE International Conference on Quantum Computing and Engineering (QCE), 171–180 (IEEE, 2021). arXiv:2106.07531
R. Shaydulin, P. C. Lotshaw, J. Larson, J. Ostrowski, and T. S. Humble, “Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut,” ACM Trans. Quantum Comput. 4(3), 1–15 (2023). doi:10.1145/3584706
Y. Hashimoto, A. Hafid, M. Ikeda, and H. Kadri, “Spectral Truncation Kernels: Noncommutativity in $C^{*}$-Algebraic Kernel Machines,” arXiv 2024 (revised 2026). arXiv:2405.17823
G. E. Crooks, “Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem,” arXiv 2018. arXiv:1811.08419
M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, and P. J. Coles, “Variational Quantum Algorithms,” Nat. Rev. Phys. 3, 625–644 (2021). doi:10.1038/s42254-021-00348-9
J. Wurtz and P. J. Love, “MaxCut Quantum Approximate Optimization Algorithm Performance Guarantees for $p$-Regular Graphs,” Phys. Rev. A 103, 042612 (2021). doi:10.1103/PhysRevA.103.042612
R. Shaydulin, C. Li, S. Chakrabarti, M. DeCross, D. Herman, N. Kumar, J. Larson, D. Lykov, P. Minssen, Y. Sun, Y. Alexeev, J. M. Dreiling, J. P. Gaebler, T. M. Gatterman, J. A. Gerber, K. Gilmore, D. Gresh, N. Hewitt, C. V. Horst, S. Hu, J. Johansen, M. Matheny, T. Mengle, M. Mills, S. A. Moses, B. Neyenhuis, P. Siegfried, R. Yalovetzky, and M. Pistoia, “Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem,” Sci. Adv. 10, eadm6761 (2024). doi:10.1126/sciadv.adm6761

Molena Huynh · North Carolina State University · molena.huynh@jmp.com
OST-QAOA — Operator-Spectral Truncated Priors for Query-Efficient QAOA · Reproducible from the installable uq-qaoa package.