Pauli Correlation Encoding (PCE) compresses $m$ binary variables onto $n=O(m^{1/k})$ qubits by mapping them to commuting Pauli correlators, but its continuous expectation values must be decoded into feasible binary solutions, a challenge for dense-constraint problems. We apply PCE to mRNA secondary-structure prediction, formulated as a densely constrained QUBO, and train with a QUBO-space sigmoid loss thatpreserves the QUBO penalty structure. For decoding, we introduce the Problem-Aware Guided Decoder (PAGD), which scores candidate variable commitments by combining marginal QUBO energy reduction with a trained expectation-value prior and constraint-aware feasibility pruning. On six benchmark mRNA sequences (30-60 nt, 50-240 variables, 7-14 qubits), PAGD with 100 restarts achieves 75-100 percent near-optimal recovery, defined as $P(\mathrm{gap}<1\%)$, for sequences up to 152 variables, compared with 0-30 percent for a sign-rounding plus local-search baseline. On the 240-variable instance, trained PAGD reaches 50 percent $P(\mathrm{gap}<1\%)$ at 200 restarts, outperforming untrained-circuit and random-expectation-value controls. Hardware-scale tests extend the pipeline to three 102-105 nt instances (694-745 variables, 172,000-193,000 pair constraints, 23 qubits) on IBM Heron processors. The circuits transpile SWAP-free into 480 native two-qubit gates at depth 256, and PAGD decoded gaps on QPU runs match or beat simulator means for all three instances, including exact CPLEX-optimum recovery for one sequence. These results show that PCE-trained priors can survive deployment to noisy superconducting hardware at biologically relevant scale.
Pauli Correlation Encoding (PCE) compresses m binary variables onto n=O(m1/k) qubits by mapping them to commuting Pauli correlators, but its continuous expectation values must be decoded into feasible binary solutions, a challenge for dense-constraint problems. We apply PCE to mRNA secondary-structure prediction, formulated as a densely constrained QUBO, and train with a QUBO-space sigmoid loss thatpreserves the QUBO penalty structure. For decoding, we introduce the Problem-Aware Guided Decoder (PAGD), which scores candidate variable commitments by combining marginal QUBO energy reduction with a trained expectation-value prior and constraint-aware feasibility pruning. On six benchmark mRNA sequences (30-60 nt, 50-240 variables, 7-14 qubits), PAGD with 100 restarts achieves 75-100 percent near-optimal recovery, defined as P(gap<1%), for sequences up to 152 variables, compared with 0-30 percent for a sign-rounding plus local-search baseline. On the 240-variable instance, trained PAGD reaches 50 percent P(gap<1%) at 200 restarts, outperforming untrained-circuit and random-expectation-value controls. Hardware-scale tests extend the pipeline to three 102-105 nt instances (694-745 variables, 172,000-193,000 pair constraints, 23 qubits) on IBM Heron processors. The circuits transpile SWAP-free into 480 native two-qubit gates at depth 256, and PAGD decoded gaps on QPU runs match or beat simulator means for all three instances, including exact CPLEX-optimum recovery for one sequence. These results show that PCE-trained priors can survive deployment to noisy superconducting hardware at biologically relevant scale.
Pauli correlation encoding (PCE) encodes m binary variables in the signs of k-body Pauli correlators of n=O(m1/k) qubits, and trains a parameterized circuit on a relaxed loss of sharpness α. The strongest published schedules sharpen this loss aggressively and are benchmarked with exact expectation values, whereas a quantum computer estimates correlators from a finite number of shots. We show that the sharpness is a hidden shot budget. Since the expected sign of a correlator estimated from S shots, erf(cS/2), agrees with tanh(0.851Sc) to within 0.019, the edge term of the relaxed loss at α=0.851S approximately equals, up to a constant, minus twice the cut expected from decoding S shots. This explains why schedules tuned with exact expectation values lose their advantage at realistic budgets, and yields a shot-aware schedule whose final sharpness is set by the shot budget. On five G-set graphs with 800 variables on 13 qubits, this schedule outperforms every published schedule at its target budget in all 150 paired comparisons of the decoded circuit output, owing to the sharpness at 1.6×104 shots and mostly to switching off the regularization at 103; after a classical bit-swap search, it remains the best on average at 1.6×104 shots. Device noise damps the correlators by a factor s, which amounts to a smaller shot budget s2S. On the IBM Heron processor ibm_fez, an all-to-all ansatz of the type used for the best published G-set results compiles to 835 CZ gates and decodes to a random cut, while our 96-CZ hardware-native circuit, trained in simulation and sharpened to α≃0.65sS, retains up to 0.919 of the best-known cut. For new circuits, a damping and an offset calibrated on other circuits of the same graph predicted the decoded cuts at 103 shots to within 0.002.
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.
Recent advancements in quantum computing have created new opportunities for tackling long-standing, complex combinatorial optimization problems that are intractable for classical computers. Predicting the secondary structure of mRNA is one such notoriously difficult problem that can benefit from the rapid advancements in quantum computing technology. Accurate prediction of mRNA secondary structure is crucial for designing RNA-based therapeutics, as it dictates various stages of the mRNA life cycle, including transcription, translation, and decay. The current generation of quantum computers has reached a utility scale, enabling us to explore relatively large problem sizes. In this paper, we examine the feasibility of solving mRNA secondary structures on a quantum computer for sequence lengths up to 60 nucleotides, representing problems in the qubit range of 10 to 80. We use the Conditional Value at Risk (CVaR)-based VQE algorithm to solve optimization problems derived from mRNA secondary structure prediction on the IBM Eagle and Heron quantum processors. Encouragingly, even with minimal error mitigation and fixed-depth circuits, our hardware runs yield accurate predictions of minimum free energy (MFE) structures that match the results of the classical solver CPLEX. Our results provide substantial evidence for the viability of solving mRNA structure prediction problems on a quantum computer and motivate continued research in this direction.
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.
Accurate prediction of mRNA secondary structure is critical for understanding gene expression, translation efficiency, and advancing mRNA-based therapeutics. However, the combinatorial complexity of possible foldings, especially in long sequences, poses significant computational challenges for classical algorithms. In this work, we propose a scalable, quantum-centric optimization framework that integrates quantum sampling with classical post-processing to tackle this problem. Building on a Quadratic Unconstrained Binary Optimization (QUBO) formulation of the mRNA folding task, we develop two complementary workflows: a Conditional Value at Risk (CVaR)-based variational quantum algorithm enhanced with gauge transformations and local search, and an Instantaneous Quantum Polynomial (IQP) circuit-based scheme where training is done classically and sampling is delegated to quantum hardware. We demonstrate the effectiveness of these approaches using IBM quantum processors, solving problem instances with up to 156 qubits and circuits containing up to 950 nonlocal gates, corresponding to mRNA sequences of up to 60 nucleotides. Additionally, we validate scalability of the CVaR algorithm on a tensor network simulator, reaching up to 354 qubits in noiseless settings. These results demonstrate the growing practical capabilities of hybrid quantum-classical methods for tackling large-scale biological optimization problems.
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.