Skip to content
Preprint

A Quantum-Inspired Approach to MaxCut Based on Sparse Walsh/Pauli-Correlation Encoding

Sep 2026 · 0 citations · 11 references
Computer Science Physics

Abstract

We present a quantum-inspired Walsh/PCE solver for MaxCut based on sparse Pauli-correlation encodings. Instead of assigning one qubit or one variable to each graph vertex directly, the method represents relaxed binary variables through expectation values of diagonal Pauli/Walsh observables. These correlators are computed classically from sparse Walsh autocorrelations, producing a compact differentiable relaxation of the MaxCut objective. We evaluate the method on selected Gset instances, G1, G6, G12, and G18, and compare it with random search and tabu search over 10 independent seeds. The proposed model uses $801$ active parameters, corresponding to only $0.306\%$ of the full Walsh space over $18$ qubits. After a final bitflip local search, Walsh/PCE achieves approximation ratios of $0.99033 \pm 0.00226$ on G1, $0.95647 \pm 0.01604$ on G6, $0.96007 \pm 0.00951$ on G12, and $0.92964 \pm 0.02202$ on G18, outperforming both baselines on all tested instances. The method also yields the lowest average runtime in all cases. These results suggest that sparse Walsh/PCE representations provide an efficient quantum-inspired route for MaxCut and may be further extended to hardware-based estimation of Pauli/Walsh correlators.

View source

Similar papers

Preprint Oct 2026

Shot- and Noise-Aware Pauli Correlation Encoding for Max-Cut Experiments on IBM Heron Quantum Processor

Pauli correlation encoding (PCE) encodes $m$ binary variables in the signs of $k$-body Pauli correlators of $n=O(m^{1/k})$ qubits, and trains a parameterized circuit on a relaxed loss of sharpness $\alpha$. The strongest published schedules sharpen this loss aggressively and are benchmarked with exact expectation value...

Achraf Boussahi · 0 citations
Preprint Oct 2026

$T$-efficient unitary synthesis via block-sparse Hamiltonian simulation

We construct Clifford+$T$ circuits implementing arbitrary $n$-qubit unitaries with worst-case $T$-count $\widetilde{O}(N^{8/7})$ at constant operator-norm error, where $N=2^n$, improving the previous exponent $5/4$. The construction uses $\widetilde{O}(N^{6/7})$ clean ancillas. The main idea is to reduce the data addre...

Diyi Liu, Shu-Chen Zhu, Wibe A. de Jong et al. · 0 citations
Preprint Oct 2026

Sum-of-squares compilation of matrix-model dynamics for NISQ and fault-tolerant hardware

The SU$(N)$ matrix-model potential $V=-\tfrac{g^2}{4}\sum_{I,J}Tr[X_I,X_J]^2$, the interaction of the BFSS/BMN family, whose thermal large-$N$ states are dual to black holes, is diagonal in the coordinate basis and is compiled in the literature as a phase polynomial with $O(d^2N^4Q^4)$ rotations per Trotter step. That...

Ayanendu Dutta, N. Sarkar · 0 citations
Preprint Sep 2026

Approximate synthesis of general single-qubit unitaries over the Clifford+$\sqrt{T}$ gate set

A resource state cost model based on the magic-state catalysis approach of Gidney and Fowler is adopted, which shows that once a one-time catalyst state is amortized, the Clifford+$\sqrt{T}$ circuits are never costlier than their Clifford+$T$ counterparts.

Mathias Weiden, Jae Won Kim, J. Kalloor et al. · 0 citations
Preprint Oct 2026

Hardware-Friendly Estimation of LCU-Based Expectation Values via Quantum-to-Classical Workload Shifting

Estimating the expectation value of an observable $O$ for a quantum state evolved under a general, possibly non-unitary, operator $A$ is a fundamental task in quantum simulation, chemistry, and variational algorithms. Existing linear-combination-of-unitaries (LCU) approaches implement $A$ on hardware, requiring ancilla...

Hari Hara Suthan Chittoor, Thirumalai Manimaran · 0 citations
Preprint Oct 2026

Quantum codes in the Lee metric

We introduce a quantum coding framework for discrete small-shift noise, in which errors on qudits are modeled as low-weight $X$- and $Z$-type Pauli shifts, analogous to small phase-space displacements in continuous-variable systems. This structure is approximately respected by nuclear-spin noise and captured by the Lee...

Jin-Kang Guo, Yi-Qiu Han, Aranya Chakraborty et al. · 2 citations · ⚡2

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.