Summary
When trying to solve hard problems on quantum computers, some methods pack many problem variables into fewer quantum bits, called qubits. The authors show that while classical methods often simplify problems to make them easier, compressing quantum problems this way can actually make them harder in the worst case. They study a framework called quantum random access optimization (QRAO) and find that depending on how problem variables are assigned to quantum properties, the difficulty of solving the problem ranges from NP-complete to QMA-complete, which are categories of complex problems. Their results also apply directly to existing quantum software tools, meaning these complexity challenges are real and relevant. However, they do not claim these difficulties affect all typical problems or quantum algorithms using compression.
QubitQuantum compressionPauli operatorsNP-completeQMA-completeQuantum random access optimizationSemidefinite programmingMaxCut problemHamiltonian optimizationPromise gap
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.