Complexity Amplification from Compression in Quantum Random Access Optimization

• URL: http://arxiv.org/abs/2609.07090v1
• Date: Mon, 07 Sep 2026 06:28:48 GMT
• Title: Complexity Amplification from Compression in Quantum Random Access Optimization
• Abstract summary: We study a special case of the Pauli correlation encoding framework that assigns up to three binary variables to the Pauli $X$, $Y$, and $Z$ observables of each qubit.<n>We identify explicit QRAO optimal energy promise problems complete for NP, StoqMA, and QMA, with inverse-polynomial promise gaps for the latter two.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Multivariate Decoded Quantum Interferometry for Weighted Optimization [6.4675604105664]
  Quantum Interferometry (DQI) reduces discrete optimization to decoding with potential advantages over the best-known analogue-time classical algorithms for certain Max-LINSAT problems.<n>In its original formulation, DQI treats all constraints uniformly and cannot exploit the weight structure present in most optimization problems of interest.
  arXiv  Detail & Related papers  (2026-05-11T14:45:46Z)
• Constrained Quantum Optimization at Utility Scale: Application to the Knapsack Problem [0.0]
  Constrained optimization problems are challenging for quantum computing.<n>Cop-QAOA is a hardware-efficient approach for constrained optimization to a single-period UC.<n>This work presents the largest successful demonstration of the knapsack problem on IBM Quantum hardware using up to 150 qubits.
  arXiv  Detail & Related papers  (2026-02-27T19:16:28Z)
• Characterizing QUBO Reformulations of the Max-k-Cut Problem for Quantum Computing [0.0]
  Quantum computing offers significant potential for solving NP-hardweighted (optimization) problems that are beyond the reach of classical computers.<n>One way to tap into this potential is by reformulating problems as a quadratic unconstrained binary optimization (QUBO) problem.<n>We present closed-form characterizations of tight penalty coefficients for two distinct QUBO reformulations of the max $k$-cut problem.
  arXiv  Detail & Related papers  (2025-11-02T22:49:59Z)
• Solving Constrained Combinatorial Optimization Problems with Variational Quantum Imaginary Time Evolution [4.266376725904727]
  We show that VarQITE achieves significantly lower mean optimality gaps compared to other conventional methods.<n>We demonstrate that scaling the Hamiltonian can further reduce optimization costs and accelerate convergence.
  arXiv  Detail & Related papers  (2025-04-17T03:09:37Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Recursive Quantum Relaxation for Combinatorial Optimization Problems [3.3053321430025258]
  We show that some existing quantum optimization methods can be unified into a solver to find the binary solution.<n>Experiments on standard benchmark graphs with several hundred nodes in the MAX-CUT problem, conducted in a fully classical manner.
  arXiv  Detail & Related papers  (2024-03-04T13:48:21Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
  We present an alternative method that does not require extra slack variables. We evaluate our approach on the traveling salesman problem, the bin packing problem, and the knapsack problem. This new approach can be used to solve problems with inequality constraints with a reduced number of resources.
  arXiv  Detail & Related papers  (2022-11-25T06:05:18Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.