Efficiently Simulable Pauli Correlation Encoding

Jul 22, 2026·
Daniele Lizzio Bosco
,
Gabriel Matos
,
Chen-Yu Liu
,
Frederic Rapp
,
Fabian Finger
Enrico Rinaldi
Enrico Rinaldi
,
Konstantinos Meichanetzidis
· 0 min read
Abstract
Pauli Correlation Encoding (PCE) is a heuristic framework for binary optimisation that encodes classical variables into many-body Pauli observables. While PCE requires fewer qubits than other approaches, it relies on estimating a large number of Pauli expectation values whose signs determine the variables’ values, which can incur substantial measurement overhead. Here, we introduce efficiently simulable PCE, a class of dequantised PCE realisations where all expectation values needed can be computed efficiently classically. We instantiate this idea using free-fermionic evolutions, realised by matchgate circuits, and Instantaneous Quantum Polynomial (IQP) circuits. On MaxCut, Maximum Independent Set, Multi-Dimensional Knapsack, and Max3SAT benchmarks, these methods produce high-quality solutions across problem sizes ranging from tens to thousands of variables. Our results show that PCE is naturally understood as a correlation-based optimisation framework with both quantum and classically simulable realisations. This yields a dequantised baseline for evaluating future quantum PCE implementations.
Type
publications
Enrico Rinaldi
Authors
Senior R&D Manager
I am a Senior R&D Manager at Quantinuum in London. I am also a Visiting Scientist at the RIKEN Center for Quantum Computing (Theory Unit) and an Honorary Senior Lecturer in the School of Mathematical Sciences at Queen Mary University of London.