Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.03949

Benchmarking Ansatze for Pauli Correlation Encoding in the Maximum Independent Set Problem

Cian C. Reeves, Aaron C. Kemp, Richard Padbury, Eva Lia Tarquini, Christoph Kloeffel, Vedangi Pathak, Hamed Mohammadbagherpoor, Vincent Beltrani

quant-phSubmitted Oct 2, 2026• Announced Oct 6, 2026• 0 citations
arXivHTMLPDF

Abstract

The increasing complexity of 5G and emerging 6G wireless networks has intensified the need for scalable optimization techniques capable of addressing computationally challenging combinatorial problems. While quantum optimization offers a promising alternative, current near-term quantum hardware remains limited by qubit availability, noise, and scalability constraints. Pauli Correlation Encoding (PCE) has emerged as a qubit-efficient optimization framework that addresses these challenges through polynomial variable compression. However, the impact of compression on representability and solution recovery remains poorly understood. In this work, we investigate the hypothesis that increasing compression ratios introduce representability constraints arising from algebraic closure relationships among encoded Pauli observables. Using Maximum Independent Set benchmark problems, we evaluate multiple PCE ansatz designs and compression ratios. We find that ansatz selection is critical to both solution quality and feasibility, with two ansatz families consistently outperforming alternatives and achieving approximation ratios approaching 0.9. Furthermore, increasing circuit repetitions provides limited benefit and can degrade performance. Most notably, reducing compression by increasing the number of available qubits significantly improves raw solution quality, while post-processed performance remains comparatively stable. These findings suggest that representability effects play an important role in compressed PCE encodings and provide new insight into the relationship among compression, ansatz design, decoding, and solution quality in scalable quantum optimization.

Comments
11 pages, 6 figures

Related papers

Benchmark of Pauli Correlation Encoding for different optimisation problems

Fernando Alonso, Colomán Samprón, Jacobo Veiga +2 more

The continuous progress of quantum technologies has spurred the exploration of their potential applications across diverse fields, particularly in combinatorial optimisation. In this work, we study a quantum-classical optimisation framework based on Pauli Correlation Encoding, an encoding scheme that can represent m binary variables using a polynomial number of qubits. To evaluate the performance of the method, we use three classical optimisation problems against the instances of the QOPTLib benchmark. The study includes an analysis of the impact of the compression order of the encoding scheme, the problem structure, and hyperparameter selection on solution quality, as well as the role of post-processing in improving performance. Additionally, we study the effect of shot-based execution and hardware noise, showing how these factors influence both the accuracy of expected value estimation and the overall dynamics of the optimisation process. The results indicate that the proposed PCE-based framework achieves competitive performance against the benchmark and, in several cases, obtains equivalent or even superior solutions, highlighting its potential as an efficient encoding strategy for quantum optimisation in the NISQ and near fault-tolerant era.

quant-pharXiv:2606.18914•Jun 18, 2026•0 citations

Enhancing Pauli Correlation Encoding for quantum optimization via systematic expressivity analysis

Riku Usuki, Don Arai, Ken N. Okada +1 more

Quantum approaches for combinatorial optimization problems have attracted considerable attention in recent years. Among these approaches, Pauli Correlation Encoding (PCE) has emerged as a promising framework for quantum devices with limited qubit resources because it embeds optimization variables in expectation values of Pauli strings. However, the mechanisms underlying its performance and the reasons for its saturation remain unclear. In this work, we investigate these questions through a systematic analysis of expressivity and trainability. First, we compare PCE with classical surrogate models based on tensor networks whose structures progressively approach the topology of the PCE circuit. The results show that PCE attains comparable solution quality with substantially fewer trainable parameters, indicating strong parameter efficiency. Second, to determine whether the performance saturation of conventional PCE is caused by insufficient expressivity or by optimization difficulty, we perform a diagnostic expressivity test in which the circuit is trained toward reference configurations for Max-Cut. The results show that even shallow PCE circuits can represent strong solutions, indicating that the main bottleneck is not the representational power of the ansatz, but the trainability under the relaxed objective function. Motivated by this finding, we propose a multistage continuation framework that gradually transforms a smooth relaxed objective into a sharper objective that more closely approximates the target discrete problem. Numerical experiments on G-set instances with 800 vertices show that the proposed method consistently outperforms conventional PCE and is competitive with representative graph neural network (GNN) methods. These results clarify the main factors behind PCE performance and provide a practical strategy for improving PCE on quantum devices with limited qubit resources.

quant-pharXiv:2609.09718•Sep 10, 2026•0 citations

Qubit-Efficient Variational Quantum Optimization via Pauli Correlation Encoding: Application to Large-Scale Power Demand Portfolio Optimization

Takuya Yoshioka, Keita Sasada, Riku Usuki +2 more

Variational quantum algorithms offer a promising route to combinatorial optimization, but their applicability is limited by the challenge of encoding large-scale problems within restricted qubit resources. In this work, we introduce a qubit-efficient variational framework based on Pauli correlation encoding (PCE) and apply it to electric power demand portfolio optimization. Binary variables are represented through expectation values of Pauli correlation operators, which encode multi-body correlations of the quantum state and provide a continuous relaxation enabling compact representations with few qubits. We further propose a two-stage hybrid formulation, in which a time-averaged problem provides initialization for a time-resolved optimization. Numerical simulations demonstrate near-optimal performance across problem sizes ranging from $m=18$ to $10{,}296$, with normalized cost gaps on the order of $10^{-4}$ relative to solutions with certified optimality. We show that the performance is governed by the interplay between continuous relaxation and discretization: the effective resolution of the correlator representation determines how reliably improvements in the continuous loss translate into better discrete solutions, with larger systems exhibiting more consistent behavior. Finally, we demonstrate robustness on a trapped-ion quantum processor, where high-quality solutions are obtained despite noise and finite sampling. These results establish PCE as a physically motivated and qubit-efficient framework for large-scale combinatorial optimization.

quant-pharXiv:2607.24722•Physical Review Applied•Jul 28, 2026•0 citations

Efficiently Simulable Pauli Correlation Encoding

Daniele Lizzio Bosco, Gabriel Matos, Chen-Yu Liu +4 more

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.

quant-pharXiv:2607.20409•Jul 23, 2026•0 citations

Progressive Binarization - Pauli Correlation Encoding: a Continuation Method for Constrained Optimization

Jacobo Padín-Martínez, Vicente P. Soloviev, Alejandro Borrallo-Rentero +3 more

Pauli Correlation Encoding (PCE) reduces the qubit requirements of quantum optimization by embedding the problem variables into the expectation values of Pauli observables, so that the number of qubits can be much smaller than the number of variables. PCE has not yet been studied for constrained optimization. We extend it to constrained combinatorial problems, using the budget-constrained MinCut as a case study, and show that the standard formulation fails to reliably enforce the constraint: feasibility hinges on the binarization of the encoded variables, which depends sensitively on hyperparameters that are hard to tune and do not transfer across instances. To address this, we introduce Progressive-Binarization PCE (PB-PCE), an adaptive continuation scheme that progressively increases the binarization parameter while re-optimizing the circuit from the previous solution, driving the variables towards the binary domain. PB-PCE attains near-complete constraint satisfaction (88--100\%) and smaller cut sizes than standard PCE, with a number of stages (10--20) essentially independent of problem size, solving instances of up to 300 variables with only 9-qubit circuits.

quant-pharXiv:2602.17479•Feb 20, 2026•0 citations

Complexity Amplification from Compression in Quantum Random Access Optimization

Stuart Hadfield

Compressed quantum encodings aim to overcome hardware limitations towards tackling challenging problems at scale, with many classical variables mapped onto noncommuting observables of fewer qubits. Classically, relaxations such as the semidefinite program formulation of MaxCut trade solution quality for computational efficiency. By contrast, quantum relaxations based on compression can amplify the worst-case complexity of the problem being solved. We study quantum random access optimization (QRAO), a special case of the Pauli correlation encoding (PCE) framework that assigns up to three binary variables to the Pauli $X$, $Y$, and $Z$ observables of each qubit, with the packing choices determining the compressed Hamiltonian to be optimized. We identify explicit QRAO optimal energy promise problems complete for NP, StoqMA, and QMA, with inverse-polynomial promise gaps for the latter two. Our problem reductions preserve inverse-polynomial promise gaps without requiring gadgets or ancillas. For any prescribed packing, we show that weighted MaxCut instances compress, up to a known shift and rescaling, to arbitrary nonnegative-weight pairwise Pauli couplings allowed by the packing. For QRAO, using one aligned axis gives an NP-complete energy problem. Using two or three positive aligned Pauli axes generally gives QMA-complete problems, with bipartite restrictions in BQP $\cap$ StoqMA. We show that this computational hardness survives compilation and is practically relevant. Notably, this result applies directly to the current QRAO compiler implementation in Qiskit Optimization 0.7.0, confirming our hardness results are not artifacts of artificial or contrived packing rules. Altogether our results identify worst-case complexity barriers arising from quantum compression, while making no broad claims about typical cases or the performance and trainability of algorithm pipelines that use it.

quant-pharXiv:2609.07090•Sep 8, 2026•0 citations
The increasing complexity of 5G and emerging 6G wireless networks has intensified the need for scalable optimization techniques capable of addressing computationally challenging combinatorial problems. While quantum optimization offers a promising alternative, current near-term quantum hardware remains limited by qubit availability, noise, and scalability constraints. Pauli Correlation Encoding (PCE) has emerged as a qubit-efficient optimization framework that addresses these challenges through polynomial variable compression. However, the impact of compression on representability and solution recovery remains poorly understood. In this work, we investigate the hypothesis that increasing compression ratios introduce representability constraints arising from algebraic closure relationships among encoded Pauli observables. Using Maximum Independent Set benchmark problems, we evaluate multiple PCE ansatz designs and compression ratios. We find that ansatz selection is critical to both solution quality and feasibility, with two ansatz families consistently outperforming alternatives and achieving approximation ratios approaching 0.9. Furthermore, increasing circuit repetitions provides limited benefit and can degrade performance. Most notably, reducing compression by increasing the number of available qubits significantly improves raw solution quality, while post-processed performance remains comparatively stable. These findings suggest that representability effects play an important role in compressed PCE encodings and provide new insight into the relationship among compression, ansatz design, decoding, and solution quality in scalable quantum optimization.
The continuous progress of quantum technologies has spurred the exploration of their potential applications across diverse fields, particularly in combinatorial optimisation. In this work, we study a quantum-classical optimisation framework based on Pauli Correlation Encoding, an encoding scheme that can represent m binary variables using a polynomial number of qubits. To evaluate the performance of the method, we use three classical optimisation problems against the instances of the QOPTLib benchmark. The study includes an analysis of the impact of the compression order of the encoding scheme, the problem structure, and hyperparameter selection on solution quality, as well as the role of post-processing in improving performance. Additionally, we study the effect of shot-based execution and hardware noise, showing how these factors influence both the accuracy of expected value estimation and the overall dynamics of the optimisation process. The results indicate that the proposed PCE-based framework achieves competitive performance against the benchmark and, in several cases, obtains equivalent or even superior solutions, highlighting its potential as an efficient encoding strategy for quantum optimisation in the NISQ and near fault-tolerant era.
Quantum approaches for combinatorial optimization problems have attracted considerable attention in recent years. Among these approaches, Pauli Correlation Encoding (PCE) has emerged as a promising framework for quantum devices with limited qubit resources because it embeds optimization variables in expectation values of Pauli strings. However, the mechanisms underlying its performance and the reasons for its saturation remain unclear. In this work, we investigate these questions through a systematic analysis of expressivity and trainability. First, we compare PCE with classical surrogate models based on tensor networks whose structures progressively approach the topology of the PCE circuit. The results show that PCE attains comparable solution quality with substantially fewer trainable parameters, indicating strong parameter efficiency. Second, to determine whether the performance saturation of conventional PCE is caused by insufficient expressivity or by optimization difficulty, we perform a diagnostic expressivity test in which the circuit is trained toward reference configurations for Max-Cut. The results show that even shallow PCE circuits can represent strong solutions, indicating that the main bottleneck is not the representational power of the ansatz, but the trainability under the relaxed objective function. Motivated by this finding, we propose a multistage continuation framework that gradually transforms a smooth relaxed objective into a sharper objective that more closely approximates the target discrete problem. Numerical experiments on G-set instances with 800 vertices show that the proposed method consistently outperforms conventional PCE and is competitive with representative graph neural network (GNN) methods. These results clarify the main factors behind PCE performance and provide a practical strategy for improving PCE on quantum devices with limited qubit resources.
Variational quantum algorithms offer a promising route to combinatorial optimization, but their applicability is limited by the challenge of encoding large-scale problems within restricted qubit resources. In this work, we introduce a qubit-efficient variational framework based on Pauli correlation encoding (PCE) and apply it to electric power demand portfolio optimization. Binary variables are represented through expectation values of Pauli correlation operators, which encode multi-body correlations of the quantum state and provide a continuous relaxation enabling compact representations with few qubits. We further propose a two-stage hybrid formulation, in which a time-averaged problem provides initialization for a time-resolved optimization. Numerical simulations demonstrate near-optimal performance across problem sizes ranging from m=18m=18m=18 to 10,29610{,}29610,296, with normalized cost gaps on the order of 10−410^{-4}10−4 relative to solutions with certified optimality. We show that the performance is governed by the interplay between continuous relaxation and discretization: the effective resolution of the correlator representation determines how reliably improvements in the continuous loss translate into better discrete solutions, with larger systems exhibiting more consistent behavior. Finally, we demonstrate robustness on a trapped-ion quantum processor, where high-quality solutions are obtained despite noise and finite sampling. These results establish PCE as a physically motivated and qubit-efficient framework for large-scale combinatorial optimization.
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.
Pauli Correlation Encoding (PCE) reduces the qubit requirements of quantum optimization by embedding the problem variables into the expectation values of Pauli observables, so that the number of qubits can be much smaller than the number of variables. PCE has not yet been studied for constrained optimization. We extend it to constrained combinatorial problems, using the budget-constrained MinCut as a case study, and show that the standard formulation fails to reliably enforce the constraint: feasibility hinges on the binarization of the encoded variables, which depends sensitively on hyperparameters that are hard to tune and do not transfer across instances. To address this, we introduce Progressive-Binarization PCE (PB-PCE), an adaptive continuation scheme that progressively increases the binarization parameter while re-optimizing the circuit from the previous solution, driving the variables towards the binary domain. PB-PCE attains near-complete constraint satisfaction (88--100\%) and smaller cut sizes than standard PCE, with a number of stages (10--20) essentially independent of problem size, solving instances of up to 300 variables with only 9-qubit circuits.
Compressed quantum encodings aim to overcome hardware limitations towards tackling challenging problems at scale, with many classical variables mapped onto noncommuting observables of fewer qubits. Classically, relaxations such as the semidefinite program formulation of MaxCut trade solution quality for computational efficiency. By contrast, quantum relaxations based on compression can amplify the worst-case complexity of the problem being solved. We study quantum random access optimization (QRAO), a special case of the Pauli correlation encoding (PCE) framework that assigns up to three binary variables to the Pauli XXX, YYY, and ZZZ observables of each qubit, with the packing choices determining the compressed Hamiltonian to be optimized. We identify explicit QRAO optimal energy promise problems complete for NP, StoqMA, and QMA, with inverse-polynomial promise gaps for the latter two. Our problem reductions preserve inverse-polynomial promise gaps without requiring gadgets or ancillas. For any prescribed packing, we show that weighted MaxCut instances compress, up to a known shift and rescaling, to arbitrary nonnegative-weight pairwise Pauli couplings allowed by the packing. For QRAO, using one aligned axis gives an NP-complete energy problem. Using two or three positive aligned Pauli axes generally gives QMA-complete problems, with bipartite restrictions in BQP ∩\cap∩ StoqMA. We show that this computational hardness survives compilation and is practically relevant. Notably, this result applies directly to the current QRAO compiler implementation in Qiskit Optimization 0.7.0, confirming our hardness results are not artifacts of artificial or contrived packing rules. Altogether our results identify worst-case complexity barriers arising from quantum compression, while making no broad claims about typical cases or the performance and trainability of algorithm pipelines that use it.