In compression-based quantum relaxations like QRAO, classical variables are encoded into qubits and decoded after optimization. We formalize that the choice of the quantum Hamiltonian is fundamentally determined by this decoder. By representing the decoder as a POVM, we define a unique decoder-consistent Hamiltonian via the pullback of the post-decoding expected objective value. Using this framework, we reveal that standard QRAO Hamiltonians are inconsistent for certain mixed-degree quadratic functions, and we provide new approximation guarantees for the MaxCut problem based directly on POVM decoder design.
In compression-based quantum relaxations like QRAO, classical variables are encoded into qubits and decoded after optimization. We formalize that the choice of the quantum Hamiltonian is fundamentally determined by this decoder. By representing the decoder as a POVM, we define a unique decoder-consistent Hamiltonian via the pullback of the post-decoding expected objective value. Using this framework, we reveal that standard QRAO Hamiltonians are inconsistent for certain mixed-degree quadratic functions, and we provide new approximation guarantees for the MaxCut problem based directly on POVM decoder design.
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 ∩ 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.
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=Θ(n2) 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 ΔMaj(n)=tan(4nπ)=Θ(1/n), whereas uniformly random sign assignments retain Θ(1/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 (2ln2n/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.
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 3x, while it is 0.625 if the compression ratio is 2x, 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.5x) and obtain its approximation ratio for the maximum cut problem as 0.722. Also, we design a novel quantum relaxation that always guarantees a 2x 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 (>21). We hope that our results lead to the analysis of the quantum approximability and practical efficiency of the quantum-relaxation based approaches.
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∈{2,3} variables per qubit, the known decoder transfers encoded energy gain to decoded mean gain by the exact factor 1/d2. 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.
Mathematical optimization is a field where the potential of quantum algorithms is actively being explored. The Quantum Approximate Optimization Algorithm (QAOA) serves as a notable quantum-classical hybrid approach aimed at solving combinatorial optimization challenges on Noisy Intermediate-Scale Quantum (NISQ) devices. In QAOA, classical variables find representation in qubits via a one-to-one mapping. A newer entrant, Quantum Random Access Optimization (QRAO), encodes problems using fewer qubits than QAOA by leveraging the Quantum Random Access Code (QRAC) to structure a problem into its Hamiltonian form. Notably, the QRAO Hamiltonian, dubbed the Quantum Relaxation Hamiltonian, boasts of a ground state energy inferior to that of the QAOA Hamiltonian. Nonetheless, the QRAO's ground state exhibits entanglement, making it starkly different from QAOA's ground state. As a workaround, preceding studies formulated solutions to the original problem using a rounding algorithm. Our research introduces the Quantum Relaxation based Branch-and-Bound (QR-BnB) algorithm. This novel method marries Quantum Relaxation and the classical exact solution strategy, Branch-and-Bound. Within the QR-BnB framework, a classical device shoulders the responsibility of the branch-and-bound operation, while its quantum counterpart dedicates itself to determining each ground state energy for the subproblem's Quantum Relaxation Hamiltonian. This fusion eliminates the prerequisite of the rounding algorithm by crafting the optimal solution through branching operations. Preliminary simulations of the QR-BnB approach attest to its capability in accurately solving a MaxCut problem. As future work, exploring its applicability on diverse combinatorial optimization problems holds promise. Our algorithm signals a step forward in harnessing NISQ devices for tackling expansive optimization challenges.
Relaxation is a common way for dealing with combinatorial optimization problems. QRAO (Quantum Random Access Optimization) is a quantum-relaxation based optimizer that uses fewer qubits than the number of bits in the original problem, by encoding multiple variables per qubit using QRAC (Quantum Random Access Code). Reducing the number of qubits will alleviate physical noise (typically, decoherence) and, as a result, the quality of the binary solution of QRAO may be robust against noise, which is however unknown. In this paper, we numerically demonstrate that the mean approximation ratio of the (3, 1)-QRAC Hamiltonian, i.e., the Hamiltonian utilizing the encoding of 3 bits into 1 qubit by QRAC, is less affected by noise compared to the conventional Ising Hamiltonian used in quantum annealer and QAOA (Quantum Approximate Optimization Algorithm). Based on this observation, we discuss a plausible mechanism behind the robustness of QRAO under depolarizing noise. Finally, we assess the number of shots required to estimate the values of binary variables correctly under depolarizing noise and show that the (3, 1)-QRAC Hamiltonian requires less shots to achieve the same accuracy compared to the Ising Hamiltonian.