When a quantum decoder blocks good solutions, changing the starting state can help

When decoding, not depth, sets the limit

In the quantum approximate optimization algorithm (QAOA), a quantum circuit is tuned to seek a low-energy state for a mathematical problem. In compressed quantum optimization, a qubit can represent several binary variables by associating them with its different Pauli axes, X, Y and Z. Those axes cannot all be measured as ordinary simultaneous quantities. The researchers therefore use expectation values and a deterministic sign rule to turn each axis into a classical ±1 assignment. The score of that decoded assignment is distinct from the energy used to tune the circuit: a circuit with favorable relaxed energy need not decode to the best classical solution.

The paper’s central theoretical result is a deliberately constructed family of connected cubic graphs, each with n = 3r vertices, paired with a specific Pauli encoding and decoder. For this setup, the all-plus initialization has a strict ceiling: no matter how many finite QAOA layers are added, and whatever real angles are chosen, the decoded cut cannot exceed 2r. The reason is symmetry. Rotating the physical qubits around the construction leaves the all-plus circuit unchanged, so corresponding variables have identical expectation values and decode to matching signs. That forces every edge in three designated edge families to remain uncut; only 2r other edges can contribute.

A signed initialization, or “mask,” changes the sign of the starting product state on selected physical qubits and changes the mixer to match. On the constructed graphs, a uniformly chosen mask at one fixed depth-one angle pair has an expected cut of 13r/4, exceeding the all-depth all-plus ceiling by 5n/12. This is an average over masks, not a promise that every mask wins. For an infinite subfamily, the authors also identify a mask that cuts every edge. These are exact structural statements for the displayed graph family, its encoding, and deterministic sign decoding—not a claim that extra depth is generally useless or that random optimization problems have the same symmetry obstruction.

A second proof uses modules connected by weak weighted edges. Under a specified vertex ordering that produces a particular layout in the authors’ encoder, a depth-one signed mask reaches the optimum while the all-plus result remains separated by a gap that grows linearly with the number of modules. This bound is limited to the stated coupling range and a bounded interval of cost angles; it is not an arbitrary-depth result or a general robustness guarantee.

Can a classical selector choose the mask?

The authors next test whether a classical procedure can select one promising mask before the circuit’s continuous angles are optimized. They run noiseless, depth-one statevector simulations, using the same encoding, sign decoder and angle-optimization protocol across methods. The selector predicts mask quality with classical surrogate objectives; its chosen mask then receives an angle optimization. The comparison includes the all-plus X baseline and a random pool of r² masks, with each pool member optimized separately.

On 1,699 random cubic MaxCut instances, the selected MARS mask reaches a mean approximation ratio of 0.9100, compared with 0.7067 for all-plus and 0.9125 for the best member of the random pool. Thus the selector substantially improves on the baseline in this tested cohort, while the pool has a slightly higher mean. Across full cohorts for weighted MaxCut, sparse Ising, weighted Max-2-XOR and weighted Max-2-SAT, selection also improves on all-plus at each measured size. Against the pool, however, the selected mask trails at small sizes and significantly leads it only at larger MaxCut and Ising sizes; on the other two objectives, it does not show a statistically established reversal. Some graph families reuse topologies, so these are not all independent graph replications.

That comparison is not an equal-computation contest. One selected mask still requires classical search and many circuit evaluations for angle optimization, while the pool separately optimizes r² candidates. The paper does not fully measure the selector’s end-to-end cost, so it does not establish a speedup. Its numerical evidence comes from finite-size, noiseless simulations rather than quantum hardware. The constructions rely on specific encodings and a deterministic decoder, and the simulations do not prove that the same mechanism explains gains on random graphs, that results persist at larger sizes or with other seeds, or that QAOA outperforms classical optimization. The work is an arXiv preprint, not evidence of a quantum computational advantage.