Complexity Amplification from Compression in Quantum Random Access Optimization

arXiv:2609.07090 · quant-ph, cs.CC · Submitted 2026-09-07 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: I'm Kai, and with me are Mira and Lev, guest researcher.

Mira: Today's paper: "Complexity Amplification from Compression in Quantum Random Access Optimization".

Kai: This paper investigates how compressing classical optimization problems into quantum random access encodings can amplify computational complexity, moving solvable problems from NP to QMA regimes.

Mira: First, who's behind it and why it matters.

Title and authors: Kai: So, looking at the title, "Complexity Amplification from Compression in Quantum Random Access Optimization," it really makes you wonder how we can use these compressed encodings for practical applications if they end up making things fundamentally harder to solve exactly.

Mira: I think the authors are pointing out a fundamental trade-off where we gain qubit efficiency but risk an exponential increase in the problem's computational difficulty, specifically by moving it into QMA territory.

Lev: If this amplification holds up across different encoding choices, then any attempt to use these compressed methods for large-scale problem solving has to account for that potential jump in complexity.

Kai: The authors are focusing on QRAO as the specific framework they use, which involves assigning up to three binary variables to the Pauli X, Y, and Z observables of each qubit.

Mira: That specific mapping is key because those observables don't commute, which means the resulting Hamiltonian isn't just a simple diagonal Ising model anymore; it becomes a more general noncommuting quantum Hamiltonian on fewer qubits.

Lev: From what I understand about running this on real hardware, if the complexity lands in QMA, we are looking at problems where even with some error correction techniques, finding an exact solution becomes incredibly resource-intensive.

Kai: The implication here is that simply reducing the number of qubits isn't a simple scaling down operation; it's a complex mapping that can fundamentally alter the nature of what we are trying to solve computationally.

The paper's summary: Mira: The main takeaway from the summary is that they establish explicit QRAO optimal energy promise problems complete for NP, StoqMA, and QMA classes based entirely on the specific packing choices made during the encoding process.

Kai: That's a very strong claim because it suggests that we can precisely predict where a problem will sit on the complexity landscape just by how we choose to pack those Pauli observables onto the qubits.

Lev: Predicting those boundaries is crucial for hardware planning; if you know which packing leads to QMA, you know exactly what kind of computational power you're pushing your physical system towards needing.

Mira: They systematically classify these regimes based on the number of active Pauli axes, denoted as 'r', showing that when 'r=one', it stays NP-complete, but when 'r' is two or three, things escalate quickly.

Kai: The paper then moves into showing this hardness isn't just theoretical; they construct dense, connected families of problems where the uncompressed version is NP-complete but the QRAO version is QMA-complete.

Lev: That construction part tells me that even if we use a standard compiler to generate these problems, the structural constraints imposed by those compiler rules are what enforce this complexity jump onto the Hamiltonian image.

The paper's improvements: Kai: One important improvement they highlight is how they prove that promise gaps established for classical problems are preserved even when moving to the quantum setting, which is a big deal for maintaining approximation guarantees.

Mira: They achieve this preservation through two main mechanisms: first, transformations arising from axis lifts and identity shifts, which are covered by Weyl’s inequality bounds on eigenvalue shifts.

Lev: From a fault tolerance perspective, those bounds are what we need to worry about because they tell us how much error or state change you can tolerate before the energy estimation accuracy degrades significantly.

Kai: The second mechanism involves completing filler edges using a common positive weight epsilon, which ensures that the total perturbation norm stays small relative to the original promise gap.

Mira: That second point confirms that QRAO optimization remains hard even when we restrict ourselves to certain state spaces, like QRAC codewords or pure product states, as mentioned in Theorem five point three.

Lev: So what this means practically is that if you are working with restricted quantum states, you still face these hardness barriers and the promise gaps hold true for those specific domains.

Conclusion: Kai: To wrap up, this study on "Complexity Amplification from Compression in Quantum Random Access Optimization" shows that complexity amplification from compression is a real phenomenon where noncommuting Hamiltonian terms can shift global optimization between NP, StoqMA, and QMA regimes.

Mira: The authors successfully classify the exact Hamiltonian image and demonstrate that hardness arises from the combination of fixed-interaction complexity classifications, compiler realization, and constraints on the admitted quantum state domain.

Lev: For me, what stands out is how they've tied this to hardware reality by showing that these results survive the compilation process, which means we can't ignore this structural hardness when planning our next experiments.

Kai: Right, so for listeners tuning in tomorrow on arXiv, remember that QRAO compression isn't just a way to save qubits; it's a way to fundamentally change the computational class of the problem you are trying to solve.

Mira: Indeed, understanding how 'r', the number of active Pauli axes, dictates whether you are looking at StoqMA or QMA is essential for anyone building systems that rely on compressed Hamiltonians.

Lev: If we can build tools that can automatically detect these structural constraints based on the encoding choices, it could help us navigate this complexity landscape more effectively in practice.

Stuart Hadfield

USRA Research Institute for Advanced Computer Science

quant-ph, cs.CC

Submitted: 2026-09-07

Updated: 2026-09-29

Comments: Abstract shortened for arxiv submission

Project page: https://qiskit-community.github.io/qiskit-optimization/_modules/qiskit_optimization/algorithms/qrao/quantum_random_access_encoding

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 92/100

The gist: This paper investigates how compressing classical optimization problems into quantum random access encodings can amplify computational complexity, moving solvable problems from NP to QMA regimes.

Key concepts

Quantum Random Access Optimization (QRAO): This is a specific method of encoding classical binary variables into quantum states using Pauli observables (X, Y, Z). It creates a 'compressed Hamiltonian' that is then optimized over quantum states. The choice of how these variables are mapped determines the resulting problem's complexity.
Complexity Amplification: This refers to the phenomenon where transforming an NP-complete classical problem into a QMA-complete quantum optimization problem through QRAO compression. This amplification is not random; it is directly caused by the structural constraints imposed by valid encoding packings and compiler rules, making the resulting quantum problem significantly harder.
Pauli Correlation Encoding (PCE): PCE is a technique used to map classical binary variables onto quantum systems by assigning specific Pauli observables (X, Y, or Z) to each qubit. QRAO is a special case of PCE where up to three Pauli axes are assigned per qubit, leading to the compressed Hamiltonian being optimized.
QMA Complexity Class: QMA stands for Quantum Merlin-Arthur complexity class. Problems in this class are generally considered hard for classical computers but potentially verifiable by a quantum computer. The paper demonstrates that specific QRAO compressions yield problems complete for this class, indicating they are fundamentally difficult to solve exactly.

Terminology

Quantum Random Access Optimization — 9× in this paper
Accuracy — 3× in this paper · explained in 1 episode
Alignment — 3× in this paper · explained in 1 episode
Combinatorial Optimization — 3× in this paper · explained in 2 episodes
Entanglement — 3× in this paper · explained in 3 episodes
Pauli Correlation Encoding (PCE) — 3× in this paper · explained in 2 episodes
Ancilla Qubits — 2× in this paper · explained in 1 episode
Hilbert Space — 2× in this paper · explained in 2 episodes
Objective Function — 2× in this paper · explained in 2 episodes
Robustness — 2× in this paper · explained in 5 episodes
Structural Constraints — 2× in this paper · explained in 2 episodes
BQP — 1× in this paper · explained in 2 episodes
Benchmarking — 1× in this paper · explained in 3 episodes
Core — 1× in this paper · explained in 2 episodes
Effective Hamiltonian — 1× in this paper · explained in 2 episodes
Generalization — 1× in this paper · explained in 13 episodes
International Conference on Quantum Computing and Engineering — 1× in this paper
Loss Function — 1× in this paper · explained in 2 episodes
Quantum Circuits — 1× in this paper · explained in 2 episodes

Summary

This paper investigates how compressing classical optimization problems into quantum random access encodings can amplify computational complexity, moving solvable problems from NP to QMA regimes. It establishes that for specific, structured problem families, the process of compression itself introduces worst-case complexity barriers, demonstrating that the qubit reduction alone is insufficient to guarantee easier computation.

The Core Framework: Quantum Random Access Optimization (QRAO)

The study focuses on Quantum Random Access Optimization (QRAO), a special case of Pauli correlation encoding (PCE) that maps classical binary variables to up to three binary variables assigned to the Pauli X, Y, and Z observables of each qubit. This mapping results in a compressed Hamiltonian that is optimized over quantum states. The paper identifies explicit QRAO optimal energy promise problems complete for NP, StoqMA, and QMA classes based on the specific packing choices used in the encoding.

Complexity Amplification from Compression

The central finding is that QRAO compression produces a QMA-complete optimal-energy problem from an NP-complete classical input family. This amplification is not arbitrary; it arises directly from the constraints imposed by valid QRAO packings and the compiler's structure. The paper systematically classifies these regimes based on the number of active Pauli axes, denoted as 'r'. Specifically:

If r = 1 (one aligned axis), the problem is NP-complete.
If r ≥ 2 (two or three positive aligned Pauli axes), the problem is QMA-complete on unrestricted interaction graphs, while bipartite restrictions lie in StoqMA.

Compiler Realization and Structural Hardness

The hardness results are shown to be practically relevant because they survive the compilation process. The paper constructs dense, connected, regular, non-bipartite MaxCut families where the uncompressed classical problem is NP-complete, but the QRAO energy promise problem is QMA-complete. This construction works for any fixed stable degree-ordered greedy compiler with fixed-order tie breaking, including the one in Qiskit Optimization 0.7.0, confirming that hardness results are not artifacts of artificial packing rules but arise from the structure imposed by the compiler's rules on the Hamiltonian image.

Classification Across State Domains and Topology

The complexity classification depends critically on whether optimization is performed over different quantum state spaces:

For QRAC codewords, pure product states, and separable states, the problem remains NP-complete for specific subfamilies of the compressed Hamiltonians (Theorem 5.3).
Optimization over unrestricted states leads to QMA-completeness when r=3 (three axes), as seen in the Quantum MaxCut Hamiltonian image.
Graph topology provides further boundaries: a Hamiltonian is stoquastic if it lies in StoqMA, and a bipartite interaction graph restricts the problem to StoqMA, implying that QMA-hardness requires non-bipartite structures unless StoqMA = QMA.

Promise Gap Preservation

The paper rigorously proves that the inverse-polynomial promise gaps established for classical problems are preserved in the quantum setting. This is achieved through two primary mechanisms:

Transformations arising from axis lifts and identity shifts, which are covered by Weyl’s inequality bounds on eigenvalue shifts (Theorem 4.2).
The completion of filler edges using a common positive weight epsilon, ensuring that the total perturbation norm remains sufficiently small relative to the original promise gap (Appendix A.2). This confirms that QRAO optimization remains hard on restricted state spaces.

Conclusion and Implications

The paper concludes that complexity amplification from compression is a fundamental phenomenon where noncommuting Hamiltonian terms can move global optimization between NP, StoqMA, and QMA complexity regimes. The results classify the exact Hamiltonian image and show that hardness arises from the combination of fixed-interaction complexity classifications, compiler realization, and the constraints on the admitted quantum state domain. The findings serve as worst-case barriers to exact optimization of compressed Hamiltonians.

Key Enumerated Results:

: NP-complete:

Aligned single-axis compression (r=1).
QRAC codewords optimization over any state domain.

: StoqMA-complete:

Restricted two-to-one encoding with aligned interactions along one axis and local fields along a second axis (r=2).
The Hamiltonian interaction graph is bipartite, but the QRAO energy promise problem lies in StoqMA (Proposition 3.3).

: QMA-complete:

Every fixed positive aligned interaction with two or three Pauli axes on unrestricted interaction graphs (when non-bipartite).
The full unrestricted optimization over all quantum states for the d=3 case, which is equivalent to the Quantum MaxCut Hamiltonian image.

: Approximation Hardness:

Improvements for AI systems

Here are the specific improvements an AI system can make by leveraging the findings of this research:

A quantum-compressed optimization engine capable of solving NP-complete problems (like MaxCut) on current, limited quantum hardware by treating the problem as a QRAO energy optimization problem.
The ability to rigorously classify any given compressed Hamiltonian into one of four complexity regimes: NP-complete, StoqMA-complete, QMA-complete, or StoqMA (for bipartite restrictions).
A compiler module that automatically generates hard quantum instances from classical optimization problems (e.g., QUBO) by applying a fixed stable degree-ordered greedy coloring algorithm and specific Pauli packing rules identified in the paper (Theorem 4.2).
A state-domain selector that allows users to choose between optimizing over restricted quantum states (QRAC codewords, pure product states, separable states) or unrestricted quantum states, and provides an exact prediction of the resulting computational complexity classification for each domain (Proposition 5.1 and Theorem 5.3).
A method to identify curable Hamiltonians—those that can be made stoquastic (and thus solvable in StoqMA) via local single-qubit basis changes—by checking for specific graph cycle conditions or identifying bipartite interaction graphs (Proposition B.1 and Proposition 3.3).
A tool to analyze the complexity amplification from compression, allowing researchers to understand precisely how mapping classical variables onto noncommuting observables moves a problem from NP to QMA, based on the active Pauli axes and interaction topology (Section 7).
A robust approximation analysis framework that can quantify the exact multiplicative value hardness transferred through compression, providing concrete bounds (like Theorem 6.1) on how well an algorithm can approximate the optimal energy of a compressed problem.

Abstract

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.