PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Cesar Augusto do Amaral, Marcos Vinicius Reballo, Marcus Ritt, Alexsandro Santos da Rosa Júnior, Fernando Augusto Caletti de Barros

arXiv:2609.08907v1cs.ETquant-ph

TL;DR

Direct variable-per-qubit encodings face qubit limits for large combinatorial optimization instances. This paper proposes a sparse Walsh/PCE MaxCut relaxation with classically computed correlators; on tested Gset instances, it achieves the best mean approximation ratios among the tested methods and has faster reported runtimes.

  • Problem

    Directly encoding one binary variable per qubit is restrictive for near-term devices when instances have hundreds or thousands of variables and hardware has limited, noisy qubits.

    Source: §I · p. 1

  • Method

    The method trains sparse Walsh coefficients and computes relaxed vertex variables as Pauli/Walsh expectation values through Walsh autocorrelations.

    Source: §I · p. 1

  • Results

    Walsh/PCE achieves the best mean approximation ratios among tested methods on all evaluated instances before and after bitflip; on G1, its post-bitflip approximation ratio is 0.99033 ± 0.00226.

    Source: §VI · p. 4

  • Takeaways & Limitations

    The sparse Walsh/PCE approach remains connected to a possible quantum implementation in which correlators can be estimated by measurement on real hardware.

    Source: §VII · p. 5

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper proposes a sparse Walsh/PCE relaxation for MaxCut, motivated by the qubit limits of direct encodings. It replaces binary variables with Pauli/Walsh expectation values and computes them classically from Walsh autocorrelations.

I. INTRODUCTION

  • Direct one-variable-per-qubit encoding is restrictive for near-term devices because instances may have hundreds or thousands of variables while hardware has limited, noisy qubits.PCE instead represents binary variables as Pauli-observable expectation values; with k-body correlations, m = O(nk) variables can be represented using n qubits.Source: §I · p. 1
  • The method restricts PCE observables to diagonal Pauli-Z strings associated with Walsh operators, which form a basis for diagonal operators.The paper notes that Walsh-based constructions can use CNOT parity networks and single-qubit RZ rotations.Source: §I · p. 1, §II · p. 2
  • The proposed method trains sparse Walsh coefficients and uses Walsh autocorrelations as relaxed decision variables, preserving a Pauli/Walsh-observable interpretation while computing correlators classically.This produces a differentiable quantum-inspired optimization procedure with a path toward hardware implementation.Source: §I · p. 1
  • For q = 18, k = 3, and one base mask, the model uses 801 active trainable parameters, 0.306% of the full Walsh space.The full space contains 262,144 coefficients; the active support is generated from base masks and masks associated with graph vertices.Source: §I · p. 1

II. PAULI-CORRELATION ENCODING AND VARIATIONAL LOSS

  • PCE replaces each binary variable with a Pauli-observable expectation value, yielding a continuous relaxation, and the objective adds an optional penalty term weighted by λ.The smooth relaxed variable uses α to control how sharply it approaches binary values.Source: §II · p. 2

III. SPARSE WALSH REPRESENTATION OF PAULI CORRELATORS

The sparse Walsh representation connects diagonal Pauli-Z observables to Walsh functions and computes their expectation values as coefficient-space autocorrelations. A structured active support reduces the parameterization from exponential size to one controlled by decision variables and base masks.

III. SPARSE WALSH REPRESENTATION OF PAULI CORRELATORS

  • A real function can be expanded in the Walsh basis, and the paper uses this representation to define a normalized function state for representing a quantum state.The state construction provides the setting in which the Walsh-operator expectation values are evaluated.Source: §III · p. 2
  • Walsh functions are eigenvalue functions of diagonal Pauli-Z strings, and their products combine through bitwise XOR of their indices.The paper introduces the Walsh operators on q-bit indices and constructs the state using a binary mask defining the diagonal Pauli-Z string.Source: §III · p. 2
  • The expectation value of a diagonal Pauli-Z string can be computed directly in coefficient space as an autocorrelation of the Walsh coefficient vector.The method identifies each decision variable's PCE correlator with the correlator for its associated binary mask.Source: §III · pp. 2–3
  • Restricting coefficients to a sparse active support replaces the full exponential Walsh parameterization with one controlled by the number of decision variables and base masks.The support includes coefficient pairs separated by each decision mask, allowing the corresponding correlator to become nonzero.Source: §III · p. 3

IV. APPLICATION TO MAXCUT

For MaxCut, the method assigns each graph vertex a decision mask and substitutes its Walsh/PCE correlator for the spin variable in a normalized differentiable loss. It decodes trained relaxed spins into a binary partition and can apply a final bitflip local search.

IV. APPLICATION TO MAXCUT

  • Each vertex receives a decision mask, and its Walsh/PCE correlator replaces the spin variable in the normalized differentiable MaxCut loss.The first loss term is the normalized Walsh/PCE relaxation of the MaxCut Ising energy; a β-controlled regularization term with scale ν stabilizes optimization.Source: §IV · p. 3
  • At each optimization step, the active Walsh coefficients determine correlators that are mapped to relaxed spins and inserted into the loss before coefficient updates.The coefficients are updated by gradient descent and normalized because the correlators depend only on ratios of quadratic forms in the coefficients.Source: §IV · p. 3
  • After training, the relaxed spins are decoded into a binary partition, whose cut value is evaluated as the raw Walsh/PCE solution.The binary variable is obtained from the spin using x_i = (1 − z_i)/2.Source: §IV · p. 3
  • The optional final bitflip search flips a vertex only when the move increases the cut value, making one forward and one reverse pass.Source: §IV · p. 3

V. BENCHMARK SETUP

The experiments use selected Gset Max-Cut instances, with their benchmark characteristics listed in Table I. The passage defines the table’s graph-size and weight fields and identifies the source of the instance files and benchmark values.

V. BENCHMARK SETUP

  • The benchmark set comprises selected Gset Max-Cut instances listed in Table I.The passage says the set is small and will be expanded in future work.Source: §V · p. 3
  • Table I uses n for vertices, m for edges, Weight for possible edge weights, and Cbest for the best-known cut value.Source: §V · p. 3
  • The instance files and benchmark values came from a public GitHub repository.Source: §V · p. 3

A. Experimental protocol

The protocol fixes one Walsh/PCE configuration across instances and compares it with random and tabu search under matched step budgets. The reported active parametrization occupies a small fraction of the full Walsh space.

A. Experimental protocol

  • The final comparison uses k = 3, one base, α = 1.5 × n, and β = 0.1 for every benchmark instance.This fixed setting makes the representation consistent across instances.Source: A. Experimental protocol · p. 3
  • Random search and tabu search receive the same number of trials or steps as Walsh/PCE training, and tabu tenure is 10.Each method is also evaluated before and after final bitflip local search.Source: A. Experimental protocol · p. 3
  • The reported representation fixes PCE degree k = 3 and q = 18; its parameter-count context uses B = 1 and n = 800.Source: A. Experimental protocol · pp. 3–4
  • 98.04% of the selected degree-3 PCE support but only 0.306% of the full Walsh space is used by the active parametrization.Source: A. Experimental protocol · p. 4

B. Tabu search configuration

Tabu search is a single-start, one-vertex-flip heuristic run from random partitions under a fixed iteration budget. A shared bitflip local search is applied afterward as post-processing.

B. Tabu search configuration

  • Each tabu-search seed starts from a uniformly random partition and considers every single-vertex flip, selecting the admissible move with the largest gain.The chosen move need not improve the cut, allowing the search to escape local optima.Source: B. Tabu search configuration · p. 4
  • A vertex cannot be flipped again for 10 iterations unless the move beats the best cut found so far.Source: B. Tabu search configuration · p. 4
  • The search has a 300-iteration budget, reports results over 10 independent seeds, and returns its best trajectory solution before shared bitflip post-processing.Source: B. Tabu search configuration · p. 4

C. Evaluation metrics

Approximation ratio is the main quality metric, and the comparison also reports average runtime. The reported experiments were run on a specified MacBook Air system.

C. Evaluation metrics

VI. NUMERICAL RESULTS

Walsh/PCE achieved the best mean approximation ratio on every tested instance before and after bitflip refinement. Its G1 result also exceeded earlier PCE results, and the reported runtime comparison favored Walsh/PCE.

VI. NUMERICAL RESULTS

  • Walsh/PCE obtains the best mean AR on all tested instances both before and after bitflip, with only small bitflip gains compared with Random Search.The results cover 10 seeds; the final comparison reports average runtime separately.Source: §VI · p. 4
  • On G1, Walsh/PCE reaches AR 0.99033 ± 0.00226 after bitflip, versus prior PCE AR 0.957 for k = 2 and 0.965 for k = 3 in Ref..The passage states that the post-processed Walsh/PCE result improves over the prior reported values.Source: §VI · p. 4
  • The reported average computational-time results indicate that Walsh/PCE is faster than the other methods.The passage identifies average time in seconds but supplies no runtime values here.Source: §VI · p. 4

TABELA III

The table presents average runtime over 10 seeds, organized by instance and method, with time and standard deviation as the reported measure.

TABELA III

  • The table is scoped to average runtime over 10 seeds.The caption specifies the aggregation scope.Source: TABELA III · p. 4
  • The supplied headings describe runtime measurements rather than approximation-ratio results.Source: TABELA III · p. 4
  • Its stated columns identify the instance, method, and time in seconds with standard deviation.Source: TABELA III · p. 4

VII. CONCLUSION

The conclusion presents sparse Walsh/PCE as a classical method for optimizing MaxCut through Walsh-induced Pauli-Z correlators. It reports stronger approximation ratios and faster runtime than the tested baselines, while identifying quantum-hardware estimation and method improvements as future work.

VII. CONCLUSION

  • Walsh-induced Pauli-Z correlators are computed as Walsh-coefficient autocorrelations, allowing the main optimization loop to run classically without quantum-device sampling.Source: §VII · p. 5
  • On the selected Gset instances, Walsh/PCE achieves the best mean approximation ratios and is faster than random search and tabu search in the reported implementation and hardware setting.Source: §VII · p. 5
  • The sparse diagonal Walsh operator could be implemented as commuting Pauli-Z strings, with correlators estimated by measurement on quantum hardware.The passage frames this as a possible future hardware implementation.Source: §VII · p. 5
  • Future work includes systematic hyperparameter tuning, adaptive Walsh support, advanced post-processing comparisons, and testing noise and finite-sampling effects on hardware.Source: §VII · p. 5
Loading 2609.08907v1…