arXiv:2608.25151

No Free Compression in Quantum Relaxations for Optimization

Stuart Hadfield

quant-phSubmitted Aug 25, 2026• Announced Aug 27, 2026• 0 citations• Revised Oct 2, 2026 (v2)

Abstract

Qubit-efficient quantum relaxations compress classical decision variables into expectation values on substantially fewer qubits. We ask what resource tradeoffs this compression entails for quantum optimization. For the complete quadratic-Majorana encoding of $m=Θ(n^2)$ binary variables on~$n$ qubits, we define the universal margin as the smallest correlator magnitude that can be guaranteed with prescribed signs for every target sign (bit) assignment. We show that it is exactly $Δ_{\rm Maj}(n)=\tan\!\left(\fracπ{4n}\right)=Θ(1/n)$, whereas uniformly random sign assignments retain $Θ(1/\sqrt n)$ target-specific margins. Arbitrary density operators and mixed fermionic Gaussian states generate the same quadratic-Majorana covariance body, so non-Gaussian state resources cannot enlarge this two-point relaxation. More generally, standard quantum random access code bounds provide general information-theoretic baselines. For any fixed family of $m$ designated binary observables on~$n$ qubits, the universal margin is at most $\sqrt{(2\ln2\,n/m)}$, and random access decoding from $N$ copies with constant success probability above $1/2$ requires $nN=Ω(m)$. For a fixed Pauli correlation encoding required to work uniformly over all targets, maintaining a fixed nonzero decoded magnitude under smooth sign decoding therefore requires a rescaling parameter that grows as the available margin shrinks. Thus, while providing substantial qubit savings, compression can shift cost into restricted expectation value geometry, smaller expectation value magnitudes, or more demanding information recovery rather than eliminate it.

Related papers

Complexity Amplification from Compression in Quantum Random Access Optimization

Stuart Hadfield

quant-pharXiv:2609.07090Sep 8, 20260 citations

Complexity Barriers to State Preparation in Quantum Approximate Optimization

Stuart Hadfield

quant-pharXiv:2609.31520Sep 28, 20260 citations

Quantum-Relaxation Based Optimization Algorithms: Theoretical Extensions

Kosei Teramoto, Rudy Raymond, Eyuri Wakakuwa +1 more

arXiv:2302.09481Feb 19, 20236 citations

Quantum limits and one-qubit advantage in optical predictive compression

Zixuan He

Oct 25, 20260 citations

Decoder-Consistent Hamiltonians for POVM-Based Quantum Relaxations

Takayuki Suzuki

quant-pharXiv:2606.05604Jun 5, 20260 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

quant-pharXiv:2607.24722Physical Review AppliedJul 28, 20260 citations

arXiv:2608.25151

No Free Compression in Quantum Relaxations for Optimization

Stuart Hadfield

quant-phSubmitted Aug 25, 2026• Announced Aug 27, 2026• 0 citations• Revised Oct 2, 2026 (v2)

arXiv HTML PDF

Abstract

m=Θ(n^2)

binary variables on~

n

qubits, we define the universal margin as the smallest correlator magnitude that can be guaranteed with prescribed signs for every target sign (bit) assignment. We show that it is exactly

Δ_{\rm Maj}(n)=\tan\!\left(\fracπ{4n}\right)=Θ(1/n)

, whereas uniformly random sign assignments retain

Θ(1/\sqrt n)

target-specific margins. Arbitrary density operators and mixed fermionic Gaussian states generate the same quadratic-Majorana covariance body, so non-Gaussian state resources cannot enlarge this two-point relaxation. More generally, standard quantum random access code bounds provide general information-theoretic baselines. For any fixed family of

m

designated binary observables on~

n

qubits, the universal margin is at most

\sqrt{(2\ln2\,n/m)}

, and random access decoding from

N

copies with constant success probability above

1/2

requires

nN=Ω(m)

. For a fixed Pauli correlation encoding required to work uniformly over all targets, maintaining a fixed nonzero decoded magnitude under smooth sign decoding therefore requires a rescaling parameter that grows as the available margin shrinks. Thus, while providing substantial qubit savings, compression can shift cost into restricted expectation value geometry, smaller expectation value magnitudes, or more demanding information recovery rather than eliminate it.

Related papers

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.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.07090Sep 8, 20260 citations

Complexity Barriers to State Preparation in Quantum Approximate Optimization

Stuart Hadfield

For many important optimization problems we are restricted to approximate solutions in practice due to computational complexity. Distinct from the exact optimization setting, approximate optimization admits performance measures beyond whether the optimum is found, with different tradeoffs and complexity. For MaxCut, a near-unity (ordinary) approximation ratio can coexist with near-zero improvement (gain) over a random cut. For the standard encoding, the unconditional classical MaxCut-Gain hardness gap implies that \emph{any uniformly efficient quantum or hybrid procedure recovering a fixed positive fraction of the optimal classical gain on every input, with at least inverse-polynomial success probability, would place} NP \emph{in} BQP. Such a procedure is therefore believed impossible under standard assumptions. We broadly address where our worst-case barriers do or do not apply across the quantum algorithm landscape. We prove that the barrier survives quantum random access optimization (QRAO) compression and applies between the classical and relaxed optimal values. For every input, a product state attains the classical optimum. Thus the barrier to reaching the classical threshold does not arise from a need for entanglement. For $d\in\{2,3\}$ variables per qubit, the known decoder transfers encoded energy gain to decoded mean gain by the exact factor $1/d^2$ . Combining this identity with MaxCut-Gain hardness gives an operational preparation barrier for QRAO. We also construct hard $n$ -qubit families with relative quantum relaxation excess $Θ(1/n)$ , while the maximally mixed state has energy approximation ratio $1-Θ(1/n)$ , zero encoded energy gain, and hence zero decoded mean gain. Our results separate the effects of relaxation tightness and energy approximation from operational accessibility, motivating more comprehensive accounting in benchmarking and performance assessment.For many important optimization problems we are restricted to approximate solutions in practice due to computational complexity. Distinct from the exact optimization setting, approximate optimization admits performance measures beyond whether the optimum is found, with different tradeoffs and complexity. For MaxCut, a near-unity (ordinary) approximation ratio can coexist with near-zero improvement (gain) over a random cut. For the standard encoding, the unconditional classical MaxCut-Gain hardness gap implies that \emph{any uniformly efficient quantum or hybrid procedure recovering a fixed positive fraction of the optimal classical gain on every input, with at least inverse-polynomial success probability, would place} NP \emph{in} BQP. Such a procedure is therefore believed impossible under standard assumptions. We broadly address where our worst-case barriers do or do not apply across the quantum algorithm landscape. We prove that the barrier survives quantum random access optimization (QRAO) compression and applies between the classical and relaxed optimal values. For every input, a product state attains the classical optimum. Thus the barrier to reaching the classical threshold does not arise from a need for entanglement. For $d\in\{2,3\}$ variables per qubit, the known decoder transfers encoded energy gain to decoded mean gain by the exact factor $1/d^2$. Combining this identity with MaxCut-Gain hardness gives an operational preparation barrier for QRAO. We also construct hard $n$-qubit families with relative quantum relaxation excess $Θ(1/n)$, while the maximally mixed state has energy approximation ratio $1-Θ(1/n)$, zero encoded energy gain, and hence zero decoded mean gain. Our results separate the effects of relaxation tightness and energy approximation from operational accessibility, motivating more comprehensive accounting in benchmarking and performance assessment.

quant-pharXiv:2609.31520Sep 28, 20260 citations

Quantum-Relaxation Based Optimization Algorithms: Theoretical Extensions

Kosei Teramoto, Rudy Raymond, Eyuri Wakakuwa +1 more

Quantum Random Access Optimizer (QRAO) is a quantum-relaxation based optimization algorithm proposed by Fuller et al. that utilizes Quantum Random Access Code (QRAC) to encode multiple variables of binary optimization in a single qubit. The approximation ratio bound of QRAO for the maximum cut problem is $0.555$ if the bit-to-qubit compression ratio is $3$ x, while it is $0.625$ if the compression ratio is $2$ x, thus demonstrating a trade-off between space efficiency and approximability. In this research, we extend the quantum-relaxation by using another QRAC which encodes three classical bits into two qubits (the bit-to-qubit compression ratio is $1.5$ x) and obtain its approximation ratio for the maximum cut problem as $0.722$ . Also, we design a novel quantum relaxation that always guarantees a $2$ x bit-to-qubit compression ratio which is unlike the original quantum relaxation of Fuller~et~al. We analyze the condition when it has a non-trivial approximation ratio bound $\left(>\frac{1}{2}\right)$ . We hope that our results lead to the analysis of the quantum approximability and practical efficiency of the quantum-relaxation based approaches.Quantum Random Access Optimizer (QRAO) is a quantum-relaxation based optimization algorithm proposed by Fuller et al. that utilizes Quantum Random Access Code (QRAC) to encode multiple variables of binary optimization in a single qubit. The approximation ratio bound of QRAO for the maximum cut problem is $0.555$ if the bit-to-qubit compression ratio is $3$x, while it is $0.625$ if the compression ratio is $2$x, thus demonstrating a trade-off between space efficiency and approximability. In this research, we extend the quantum-relaxation by using another QRAC which encodes three classical bits into two qubits (the bit-to-qubit compression ratio is $1.5$x) and obtain its approximation ratio for the maximum cut problem as $0.722$. Also, we design a novel quantum relaxation that always guarantees a $2$x bit-to-qubit compression ratio which is unlike the original quantum relaxation of Fuller~et~al. We analyze the condition when it has a non-trivial approximation ratio bound $\left(>\frac{1}{2}\right)$. We hope that our results lead to the analysis of the quantum approximability and practical efficiency of the quantum-relaxation based approaches.

arXiv:2302.09481Feb 19, 20236 citations

Quantum limits and one-qubit advantage in optical predictive compression

Zixuan He

What should an optical memory retain when only a limited amount of source information can be kept? This paper gives the complete quantum information frontier for a fixed Gaussian source and relevance channel, and identifies when a single retained qubit preserves correlations that every classical record loses. It also turns that advantage into a concrete test of whether received light belongs to its stored source preparation. The physical experiment and the complete frontier A fixed Gaussian state on $A$ is prepared with its actual purifier $C$ . A normal encoder acts on $C$ to produce memory $M$ , while a prescribed Gaussian channel maps $A$ to the relevant optical output $B$ . The source-information cost and useful correlation are $r=I(A:M)$ and $v=I(B:M)$ , respectively. All logarithms are natural. The paper determines $C_{\mathrm Q}(R)=\sup_{\mathcal N:\,I(A:M)\le R}I(B:M).$ For every fixed faithful finite-mode Gaussian source and finite-mode Gaussian relevance channel, optimization over arbitrary normal quantum encoders reduces to Gaussian supporting values and a mixture of at most two Gaussian branches. The branch flag is physically retained. The unrestricted frontier is a supremum with no imposed memory dimension or memory-energy cap; an explicit finite approximation gives an error uniform in the information budget. Hard finite-dimensional implementations are treated separately. Why one qubit can preserve the leading low-brightness information For a thermal source with mean photon number $n$ and a thermal attenuator with transmissivity $0<\eta<1$ , write the output occupation as $\eta n+b$ , where $b\ge0$ is the environment's added thermal occupation. With $g(x)=(x+1)\log(x+1)-x\log x$ , the exact optimum over all normal classical records is $C_{\mathrm{cl}}(n,R)=g(\eta n+b)-g(\eta u_R+b),\qquad u_R=g^{-1}\!\bigl(\max\{g(n)-R,0\}\bigr).$ A legal encoder applies vacuum loss with transmissivity $\lambda$ to the purifier and then coherently retains two levels, resetting the entire higher-photon tail. For fixed $b>0$ and $0<\lambda<1/2$ , at the common budget $R_n=g(n)+g(\lambda n)-g((1-\lambda)n)$ , its actual relevance satisfies $v_2=\frac{\eta\lambda}{1+b}\,n\log(1/n)+O(n),\qquad C_{\mathrm{cl}}(n,R_n)=2\lambda\eta\log(1+1/b)\,n+O\!\left(\frac{n}{\log(1/n)}\right).$ The full optical tail is included in the resource accounting. At $n=0.01$ , $\eta=b=0.5$ , $\lambda=0.2$ and $R=0.023875$ , the certified predictive-mutual-information advantage exceeds 85%. The leading correlation is quantified by memory-side discord and can survive when the final output–memory state is separable. The vacuum-environment endpoint is evaluated separately for the same encoder. A same-resource correlation decision The receiver distinguishes matched source pairs from independent systems with identical marginals. For $k$ uses, the retained predictive memory obeys $\dim K_k\le2^k$ and $I(A^k:K_k)\le kR$ , including all retained flags. Both competitors may make arbitrary joint binary measurements on the received optical modes and their retained memory. The received modes are common observation access, outside the predictive-memory cap. Let $\alpha_k$ be the missed-correlation probability and $\beta_k$ the false-match probability. For every classical block encoder, even with an unrestricted classical alphabet, the fixed-error converse is $\alpha_k\le\epsilon\quad\Longrightarrow\quad \beta_k\ge\exp\!\left[-\frac{k c_nR+\log2}{1-\epsilon}\right],\qquad c_n=\eta\frac{\log(1+1/(\eta n+b))}{\log(1+1/n)}.$ At the finite parameters above and $\epsilon=0.1$ , the product-qubit encoder achieves an asymptotic false-match exponent of 0.0049 nats per pair, whereas every classical block strategy has exponent below 0.003138386231. This uses one qubit per source pair and identical measurement permissions. It is an asymptotic discrimination guarantee, distinct from the 85% single-copy information comparison; it specifies neither a finite-sample threshold nor a laboratory receiver circuit. The integrated paper contains the complete proofs, resource accounting and figures. The exact thermal classical comparator, the finite-memory construction and the block-testing connection have explicit proof dependencies separate from the general Gaussian-frontier reduction.What should an optical memory retain when only a limited amount of source information can be kept? This paper gives the complete quantum information frontier for a fixed Gaussian source and relevance channel, and identifies when a single retained qubit preserves correlations that every classical record loses. It also turns that advantage into a concrete test of whether received light belongs to its stored source preparation. The physical experiment and the complete frontier A fixed Gaussian state on $A$ is prepared with its actual purifier $C$. A normal encoder acts on $C$ to produce memory $M$, while a prescribed Gaussian channel maps $A$ to the relevant optical output $B$. The source-information cost and useful correlation are $r=I(A:M)$ and $v=I(B:M)$, respectively. All logarithms are natural. The paper determines \[ C_{\mathrm Q}(R)=\sup_{\mathcal N:\,I(A:M)\le R}I(B:M). \] For every fixed faithful finite-mode Gaussian source and finite-mode Gaussian relevance channel, optimization over arbitrary normal quantum encoders reduces to Gaussian supporting values and a mixture of at most two Gaussian branches. The branch flag is physically retained. The unrestricted frontier is a supremum with no imposed memory dimension or memory-energy cap; an explicit finite approximation gives an error uniform in the information budget. Hard finite-dimensional implementations are treated separately. Why one qubit can preserve the leading low-brightness information For a thermal source with mean photon number $n$ and a thermal attenuator with transmissivity $0<\eta<1$, write the output occupation as $\eta n+b$, where $b\ge0$ is the environment's added thermal occupation. With $g(x)=(x+1)\log(x+1)-x\log x$, the exact optimum over all normal classical records is \[ C_{\mathrm{cl}}(n,R)=g(\eta n+b)-g(\eta u_R+b),\qquad u_R=g^{-1}\!\bigl(\max\{g(n)-R,0\}\bigr). \] A legal encoder applies vacuum loss with transmissivity $\lambda$ to the purifier and then coherently retains two levels, resetting the entire higher-photon tail. For fixed $b>0$ and $0<\lambda<1/2$, at the common budget $R_n=g(n)+g(\lambda n)-g((1-\lambda)n)$, its actual relevance satisfies \[ v_2=\frac{\eta\lambda}{1+b}\,n\log(1/n)+O(n),\qquad C_{\mathrm{cl}}(n,R_n)=2\lambda\eta\log(1+1/b)\,n+O\!\left(\frac{n}{\log(1/n)}\right). \] The full optical tail is included in the resource accounting. At $n=0.01$, $\eta=b=0.5$, $\lambda=0.2$ and $R=0.023875$, the certified predictive-mutual-information advantage exceeds 85%. The leading correlation is quantified by memory-side discord and can survive when the final output–memory state is separable. The vacuum-environment endpoint is evaluated separately for the same encoder. A same-resource correlation decision The receiver distinguishes matched source pairs from independent systems with identical marginals. For $k$ uses, the retained predictive memory obeys $\dim K_k\le2^k$ and $I(A^k:K_k)\le kR$, including all retained flags. Both competitors may make arbitrary joint binary measurements on the received optical modes and their retained memory. The received modes are common observation access, outside the predictive-memory cap. Let $\alpha_k$ be the missed-correlation probability and $\beta_k$ the false-match probability. For every classical block encoder, even with an unrestricted classical alphabet, the fixed-error converse is \[ \alpha_k\le\epsilon\quad\Longrightarrow\quad \beta_k\ge\exp\!\left[-\frac{k c_nR+\log2}{1-\epsilon}\right],\qquad c_n=\eta\frac{\log(1+1/(\eta n+b))}{\log(1+1/n)}. \] At the finite parameters above and $\epsilon=0.1$, the product-qubit encoder achieves an asymptotic false-match exponent of 0.0049 nats per pair, whereas every classical block strategy has exponent below 0.003138386231. This uses one qubit per source pair and identical measurement permissions. It is an asymptotic discrimination guarantee, distinct from the 85% single-copy information comparison; it specifies neither a finite-sample threshold nor a laboratory receiver circuit. The integrated paper contains the complete proofs, resource accounting and figures. The exact thermal classical comparator, the finite-memory construction and the block-testing connection have explicit proof dependencies separate from the general Gaussian-frontier reduction.

Oct 25, 20260 citations

Decoder-Consistent Hamiltonians for POVM-Based Quantum Relaxations

Takayuki Suzuki

In compression-based quantum relaxations such as quantum random access optimization (QRAO), a quantum state is optimized on a reduced number of qubits and then decoded into a classical solution on which the objective function is evaluated. The Hermitian operator whose expectation value is optimized should therefore be consistent with the expected objective value after decoding. For a fixed single-shot POVM decoder, we define the decoder-consistent Hamiltonian as the pullback of the classical objective observable through the decoder. Its expectation value exactly equals the expected post-decoding objective value for every quantum state. We further show that any Hermitian operator inducing the same ordering over the full quantum state space must be a positive affine transformation of the decoder-consistent Hamiltonian. Using a Boolean Fourier expansion, the decoder-consistent Hamiltonian decomposes into pullbacks of individual Fourier components. This provides a common framework for comparing direct encoding, simultaneous-decoding POVMs for QRAC blocks, and the effective POVM induced by the magic rounding of Teramoto et al. in terms of which components they preserve and at what rates. For standard magic-state rounding in coloring-based QRAO for MaxCut, the framework recovers the known positive affine relation between the relaxed-Hamiltonian expectation and the expected rounded cut value. For the simultaneous-decoding POVMs analyzed here, we further show that the analogous relation generally fails for mixed-degree QUBO objectives because one- and two-body components are attenuated at different rates. We also present a systematic construction of POVM decoder blocks from prescribed Fourier components and derive corresponding lower bounds on the expected post-decoding objective value under explicit conditions.In compression-based quantum relaxations such as quantum random access optimization (QRAO), a quantum state is optimized on a reduced number of qubits and then decoded into a classical solution on which the objective function is evaluated. The Hermitian operator whose expectation value is optimized should therefore be consistent with the expected objective value after decoding. For a fixed single-shot POVM decoder, we define the decoder-consistent Hamiltonian as the pullback of the classical objective observable through the decoder. Its expectation value exactly equals the expected post-decoding objective value for every quantum state. We further show that any Hermitian operator inducing the same ordering over the full quantum state space must be a positive affine transformation of the decoder-consistent Hamiltonian. Using a Boolean Fourier expansion, the decoder-consistent Hamiltonian decomposes into pullbacks of individual Fourier components. This provides a common framework for comparing direct encoding, simultaneous-decoding POVMs for QRAC blocks, and the effective POVM induced by the magic rounding of Teramoto et al. in terms of which components they preserve and at what rates. For standard magic-state rounding in coloring-based QRAO for MaxCut, the framework recovers the known positive affine relation between the relaxed-Hamiltonian expectation and the expected rounded cut value. For the simultaneous-decoding POVMs analyzed here, we further show that the analogous relation generally fails for mixed-degree QUBO objectives because one- and two-body components are attenuated at different rates. We also present a systematic construction of POVM decoder blocks from prescribed Fourier components and derive corresponding lower bounds on the expected post-decoding objective value under explicit conditions.

quant-pharXiv:2606.05604Jun 5, 20260 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.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.24722Physical Review AppliedJul 28, 20260 citations

m=Θ(n^2)

binary variables on~

n

qubits, we define the universal margin as the smallest correlator magnitude that can be guaranteed with prescribed signs for every target sign (bit) assignment. We show that it is exactly

Δ_{\rm Maj}(n)=\tan\!\left(\fracπ{4n}\right)=Θ(1/n)

, whereas uniformly random sign assignments retain

Θ(1/\sqrt n)

m

designated binary observables on~

n

qubits, the universal margin is at most

\sqrt{(2\ln2\,n/m)}

, and random access decoding from

N

copies with constant success probability above

1/2

requires

nN=Ω(m)

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.

d\in\{2,3\}

variables per qubit, the known decoder transfers encoded energy gain to decoded mean gain by the exact factor

1/d^2

. Combining this identity with MaxCut-Gain hardness gives an operational preparation barrier for QRAO. We also construct hard

n

-qubit families with relative quantum relaxation excess

Θ(1/n)

, while the maximally mixed state has energy approximation ratio

1-Θ(1/n)

, zero encoded energy gain, and hence zero decoded mean gain. Our results separate the effects of relaxation tightness and energy approximation from operational accessibility, motivating more comprehensive accounting in benchmarking and performance assessment.

0.555

if the bit-to-qubit compression ratio is

3

x, while it is

0.625

if the compression ratio is

2

x, thus demonstrating a trade-off between space efficiency and approximability. In this research, we extend the quantum-relaxation by using another QRAC which encodes three classical bits into two qubits (the bit-to-qubit compression ratio is

1.5

x) and obtain its approximation ratio for the maximum cut problem as

0.722

. Also, we design a novel quantum relaxation that always guarantees a

2

x bit-to-qubit compression ratio which is unlike the original quantum relaxation of Fuller~et~al. We analyze the condition when it has a non-trivial approximation ratio bound

\left(>\frac{1}{2}\right)

. We hope that our results lead to the analysis of the quantum approximability and practical efficiency of the quantum-relaxation based approaches.

A

is prepared with its actual purifier

C

. A normal encoder acts on

C

to produce memory

M

, while a prescribed Gaussian channel maps

A

to the relevant optical output

B

. The source-information cost and useful correlation are

r=I(A:M)

and

v=I(B:M)

, respectively. All logarithms are natural. The paper determines

C_{\mathrm Q}(R)=\sup_{\mathcal N:\,I(A:M)\le R}I(B:M).

For every fixed faithful finite-mode Gaussian source and finite-mode Gaussian relevance channel, optimization over arbitrary normal quantum encoders reduces to Gaussian supporting values and a mixture of at most two Gaussian branches. The branch flag is physically retained. The unrestricted frontier is a supremum with no imposed memory dimension or memory-energy cap; an explicit finite approximation gives an error uniform in the information budget. Hard finite-dimensional implementations are treated separately. Why one qubit can preserve the leading low-brightness information For a thermal source with mean photon number

n

and a thermal attenuator with transmissivity

0<\eta<1

, write the output occupation as

\eta n+b

, where

b\ge0

is the environment's added thermal occupation. With

g(x)=(x+1)\log(x+1)-x\log x

, the exact optimum over all normal classical records is

C_{\mathrm{cl}}(n,R)=g(\eta n+b)-g(\eta u_R+b),\qquad u_R=g^{-1}\!\bigl(\max\{g(n)-R,0\}\bigr).

A legal encoder applies vacuum loss with transmissivity

\lambda

to the purifier and then coherently retains two levels, resetting the entire higher-photon tail. For fixed

b>0

and

0<\lambda<1/2

, at the common budget

R_n=g(n)+g(\lambda n)-g((1-\lambda)n)

, its actual relevance satisfies

v_2=\frac{\eta\lambda}{1+b}\,n\log(1/n)+O(n),\qquad C_{\mathrm{cl}}(n,R_n)=2\lambda\eta\log(1+1/b)\,n+O\!\left(\frac{n}{\log(1/n)}\right).

The full optical tail is included in the resource accounting. At

n=0.01

\eta=b=0.5

\lambda=0.2

and

R=0.023875

, the certified predictive-mutual-information advantage exceeds 85%. The leading correlation is quantified by memory-side discord and can survive when the final output–memory state is separable. The vacuum-environment endpoint is evaluated separately for the same encoder. A same-resource correlation decision The receiver distinguishes matched source pairs from independent systems with identical marginals. For

k

uses, the retained predictive memory obeys

\dim K_k\le2^k

and

I(A^k:K_k)\le kR

, including all retained flags. Both competitors may make arbitrary joint binary measurements on the received optical modes and their retained memory. The received modes are common observation access, outside the predictive-memory cap. Let

\alpha_k

be the missed-correlation probability and

\beta_k

the false-match probability. For every classical block encoder, even with an unrestricted classical alphabet, the fixed-error converse is

\alpha_k\le\epsilon\quad\Longrightarrow\quad \beta_k\ge\exp\!\left[-\frac{k c_nR+\log2}{1-\epsilon}\right],\qquad c_n=\eta\frac{\log(1+1/(\eta n+b))}{\log(1+1/n)}.

At the finite parameters above and

\epsilon=0.1

, the product-qubit encoder achieves an asymptotic false-match exponent of 0.0049 nats per pair, whereas every classical block strategy has exponent below 0.003138386231. This uses one qubit per source pair and identical measurement permissions. It is an asymptotic discrimination guarantee, distinct from the 85% single-copy information comparison; it specifies neither a finite-sample threshold nor a laboratory receiver circuit. The integrated paper contains the complete proofs, resource accounting and figures. The exact thermal classical comparator, the finite-memory construction and the block-testing connection have explicit proof dependencies separate from the general Gaussian-frontier reduction.

m=18

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.