Quantum compression changes problem hardness in optimization tasks
Complexity Amplification from Compression in Quantum Random Access Optimization
Computational Complexity
Summary
Solving big optimization problems on quantum computers is hard because qubits are limited. This work shows that using special quantum methods to compress many variables into fewer qubits can actually make some problems even harder in the worst case. The researchers identified categories of problems that become very tough to solve depending on how variables are packed into quantum measurements. Their findings explain fundamental challenges when using quantum compression, especially for current quantum compilers. They do not claim these are typical cases; rather, they highlight the hardest situations possible.
What this means in practice
- •For quantum compiler developers: Understand the hardness limits inherited in quantum compression techniques that directly affect compiler design and optimization strategies.
- •For quantum algorithm engineers: Guide design of quantum optimization algorithms when compressing variables, by knowing which packing approaches lead to inherently hard problem instances.
A theory result. No direct application yet.
Authors
Stuart Hadfield
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, while their bipartite restrictions lie in 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.