PaperlayerView exact revision on arXiv

Source-linked AI summary

Complexity Amplification from Compression in Quantum Random Access Optimization

Stuart Hadfield

arXiv:2609.07090v2quant-phcs.CC

TL;DR

Compressed quantum encodings reduce qubit use by mapping classical variables to noncommuting observables, but whether that compression makes the resulting optimization problem harder is not settled by general Hamiltonian hardness results. The paper classifies QRAO's reachable energy problems and shows that NP-hard classical inputs can yield QMA-complete compressed problems, including compiler-produced instances.

  • Problem

    It is unclear which complexity classes arise for QRAO energy problems because compiler rules constrain the Hamiltonians reachable from valid compressed inputs.

    Source: §1 · p. 3

  • Method

    The paper characterizes QRAO's reachable Hamiltonians, uses promise-preserving reductions, and constructs hard instances realized by stable greedy compilers.

    Source: §1 · pp. 3–4

  • Results

    Aligned single-axis QRAO is NP-complete, while fixed positive aligned interactions on two or three axes are QMA-complete on unrestricted graphs, and a transverse-field variant is StoqMA-complete.

    Source: §1 · p. 4

  • Takeaways & Limitations

    The complexity of the compressed energy problem depends on its Pauli-axis choices and interaction topology, and the worst-case hardness survives specified compiler constructions.

    Source: §1 · p. 4

    The paper does not establish StoqMA-completeness for the transverse-field construction under greedy compilation because the compiler need not preserve the required variable pairings.

    Source: §3.2 · p. 9

Abstract

from arXiv · show

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 $\cap$ 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.

1 Introduction

QRAO compresses binary optimization variables into noncommuting Pauli observables, and the resulting energy problem can have greater worst-case complexity than the classical input problem. The paper classifies reachable Hamiltonians and state domains, then shows that hardness can survive compiler-generated compression.

1 Introduction

  • QRAO assigns multiple classical variables to Pauli observables on fewer qubits, producing a generally noncommuting Hamiltonian optimized over quantum states.QRAO product-state codewords represent classical assignments, and measurements with rounding recover classical solutions.Source: §1 · p. 2
  • The classification requires identifying reachable Hamiltonians, preserving promise gaps when lifting hard instances, and verifying that compilers produce those instances.Locality results alone do not settle QRAO hardness because compiler rules constrain the compressed Hamiltonians.Source: §1 · p. 3
  • Aligned single-axis QRAO is NP-complete, a transverse-field variant is StoqMA-complete, and fixed positive aligned interactions on two or three axes are QMA-complete on unrestricted graphs.The latter family lies in BQP and StoqMA on bipartite interaction graphs; the classifications use inverse-polynomial gaps for the quantum promise problems.Source: §1 · pp. 3–4
  • For stable degree-ordered greedy compilers, connected, regular, non-bipartite positive-weight MaxCut instances can be constructed with full d-to-1 packings and QMA-hard compressed energy problems.Small added edges force the desired grouping and Pauli assignments while preserving the source promise gap; the construction uses no additional ancilla qubits.Source: §1 · pp. 3–4
  • Codeword, product-state, and separable optimization are NP-complete in the constructed class, while unrestricted optimization is QMA-complete.Even matching instances have entanglement-related optimal-value factors of 1, 3/2, and 2 for one-, two-, and three-axis encodings, respectively; constant-factor approximation remains NP-hard for three axes.Source: §1 · p. 5
  • For fixed positive aligned interactions, bipartite graphs place the energy problem in both BQP and StoqMA, while odd cycles are necessary for QMA-hardness in the positive aligned sector unless StoqMA = BQP = QMA.The paper also identifies a cycle-based boundary for whether isotropic mixed-axis interactions can be locally relabeled to aligned interactions.Source: §1 · pp. 5–6

2 The Hamiltonian image of QRAO compression

For a fixed packing, positive-weight MaxCut instances realize the allowed nonnegative pairwise Pauli couplings, while QRAC codewords preserve classical objective values exactly. Aligned lifts create Pauli interactions without approximation, gadgets, or added physical qubits.

2.1 Positive MaxCut and QRAC codewords

  • QRAC codewords embed classical assignments while preserving their objective values exactly.The standard d-to-1 encoding assigns classical signs to Pauli observables.Source: §2.1 · p. 6
  • A fixed packing realizes every nonnegative matrix of pairwise Pauli couplings allowed by its Pauli slots.The classical edges supplying those couplings join variables in different packed blocks.Source: §2.1 · p. 7

2.2 Aligned Pauli axis lifts

  • Aligned lifts create weighted copies of a graph, which couple only when corresponding variables share a qubit on noncommuting observables.Maximizing the QRAO Hamiltonian is equivalent under a known affine transformation to the lifted objective.Source: §2.2 · p. 7
  • The aligned lift is exact and adds neither gadgets nor physical qubits.Any gadgets or interaction-strength ranges required by a source Local Hamiltonian reduction are inherited.Source: §2.2 · p. 7

3 NP, StoqMA, and QMA regimes of QRAO

The section classifies aligned QRAO energy problems by active Pauli axes and by field and graph restrictions. One active axis gives NP-completeness, while multiple axes yield QMA- or StoqMA-complete regimes, with bipartite cases contained in BQP ∩ StoqMA.

3.1 NP to QMA computational complexity transition

  • One active aligned Pauli axis gives an NP-complete energy problem, whereas two or more active axes give a QMA-complete problem; this worst-case result does not mean every compressed instance is hard.With one axis, a basis change makes the Hamiltonian diagonal and its optimum corresponds to weighted MaxCut.Source: §3.1 · p. 8

3.2 Stoquastic boundaries

  • The transverse-field construction is StoqMA-complete at inverse-polynomial precision, while its classical threshold problem remains NP-complete; it requires prescribed pairings that greedy compilation does not guarantee.The encoding pairs each xu with its corresponding zu; the paper does not establish StoqMA-completeness under greedy compilation.Source: §3.2 · p. 9
  • For positive aligned interactions with at least two active axes, a bipartite interaction graph places the energy problem in BQP ∩ StoqMA, so an odd cycle is necessary for QMA-hardness unless StoqMA = BQP = QMA.The bipartite containment is not a completeness claim.Source: §3.2 · pp. 9–10

3.3 Canonical examples with equal axis coefficients

  • Equal-coefficient positive two-axis interactions and the three-axis Quantum MaxCut Hamiltonian are QMA-complete; restricting the latter to QRAC codewords recovers classical MaxCut.The three-axis lift has codeword optimum 3 · MaxCut(G).Source: §3.3 · p. 11

4 Compiler-layer hardness and existing software realization

The section shows how stable degree-ordered greedy compilers can be made to produce hard compressed Hamiltonians, and connects the construction to a specified Qiskit implementation. The resulting hardness applies to those compiler rules and constructions, not automatically to other releases or heuristics.

4 Compiler-layer hardness and existing software realization

  • Qiskit Optimization 0.7.0's QuantumRandomAccessEncoding is reported to instantiate the specified compiler rules; the claim does not extend to other releases, preprocessing pipelines, or heuristics.The implementation uses NetworkX 3.6.1's largest_first coloring, variable-index ordering, and fixed Pauli slots.Source: §4 · p. 12

4.1 Connected compiler realization with local-axis control

  • For d=2,3, a fixed stable degree-ordered greedy compiler can produce connected, regular, non-bipartite supports that pack dn variables onto n qubits and reproduce source Hamiltonians up to local-axis relabeling, a known shift, and bounded perturbation.The perturbation comes from positive-weight filler edges.Source: §4.1 · pp. 12–13
  • Small independent positive edge-weight changes preserve each constructed instance's answer within an inverse-polynomial ℓ1 neighborhood.The construction reserves promise-gap slack to accommodate the resulting Hamiltonian perturbation.Source: §4.1 · p. 13
  • Under exactly d vertices per color class, the construction's edge-count ratio to the lower bound is (n + d − 2)/(n − 1), tending to 1; full occupancy alone does not imply quadratic density.The exact-class-size condition is stronger than full occupancy.Source: §4.1 · pp. 13–14
  • On the constructed classes, classical positive-weight MaxCut threshold problems are NP-complete, while compiled QRAO energy promise problems are QMA-complete with inverse-polynomial gaps.The reductions use the same structural class, though not necessarily the same individual instances.Source: §4.1 · p. 14

5 Relaxation optima and complexity across state domains

QRAO’s relaxation gap and complexity depend on the allowed quantum state domain: restricted domains can have NP-complete energy problems, while unrestricted states yield QMA-completeness. Matching instances also exhibit a strict gap between codeword and unrestricted optima for two and three active axes.

5 Relaxation optima and complexity across state domains

  • In the isotropic three-axis case, the unrestricted QRAO optimum is 3 times Quantum MaxCut, while the codeword optimum is 3 times classical MaxCut.The resulting QRAO relaxation gap equals the Quantum MaxCut-to-Classical MaxCut relaxation gap.Source: §5 · pp. 14–15
  • For a matching of total edge weight W under the full d-axis lift with equal axis coefficients, unrestricted states improve on the product-state bound by factors 1, 3/2, and 2 for d=1, 2, and 3, respectively.Source: §5 · p. 15
  • The matching relaxation gain does not imply a better decoded cut; for d = 3, product states attain at most half the unrestricted Quantum MaxCut optimum in this example.Parekh and Thompson achieve the one-half guarantee on arbitrary positive-weight graphs [35].Source: §5 · p. 15
  • Three-axis product-state Quantum MaxCut is NP-complete, and linearity gives the same optimum for separable states, making that problem NP-complete as well.A polynomial-precision list of Bloch vectors supplies an NP witness for product states.Source: §5 · p. 15

5.1 Stability and restricted state space complexity

  • A stability bound controls changes in the optimum under perturbations, and the paper applies it to show QRAO optimization remains hard on restricted state spaces.The bound applies to any nonempty compact family of density operators and Hermitian perturbations.Source: §5.1 · pp. 15–16
  • On connected, regular, non-bipartite, exactly three-to-one compressed positive-weight MaxCut instances, codeword, pure-product, and separable-state optimization are NP-complete, while full-Hilbert-space optimization is QMA-complete.The classifications have inverse-polynomial promise gaps; the restricted-domain NP-completeness results use different Hamiltonian subfamilies.Source: §5.1 · p. 16

6 Hardness of Approximation

The paper proves constant-factor approximation hardness for isotropic three-axis QRAO on two classes of MaxCut-derived instances. The constructions differ in graph structure, weights, and compiler-order robustness.

6 Hardness of Approximation

  • The hardness uses an η < 1 supplied by an unconditional Quantum MaxCut result, but that result gives no explicit approximation ratio for quantitative comparison.The result holds even on unweighted graphs of constant bounded degree [36, Theorem 1].Source: §6 · p. 16
  • For some constant η < 1, approximating isotropic three-axis QRAO within factor η is NP-hard on three identical disjoint unweighted bounded-degree MaxCut graphs and on connected, regular, positive-weight, fully compressed instances.The first family uses a stable degree-ordered greedy compiler; the second belongs to C3.Source: §6 · p. 16
  • The first hard family is unweighted and bounded-degree but disconnected before compression, whereas the connected family is weighted and dense.The first construction relies on vertex-major input order; the connected family is robust to any fixed order.Source: §6 · p. 16
  • The theorem concerns approximation of the best relaxation value, not the quality of a classical string produced by a particular decoder.The uncompleted isotropic lift scales every state’s energy by three, but an identity shift in the connected construction can change multiplicative ratios.Source: §6 · p. 16

7 Discussion

The discussion frames QRAO compression as a source of worst-case complexity amplification, with the resulting regime depending on the Hamiltonian image, topology, and admitted state domain. It distinguishes this exact-optimization classification from algorithm performance and identifies limits on generalizing the results.

7 Discussion

  • QRAO compression can move global optimization among NP, StoqMA, and QMA regimes; bipartite topology places part of the positive interaction cone in both BQP and StoqMA.The order-robust compiler construction establishes QMA-completeness after exact compression on a connected regular classical support graph.Source: §7 · pp. 16–17
  • The hardness results are worst-case and do not establish when hardness arises in typical QRAO instances or how QRAO algorithms perform or train.The paper leaves typical-case hardness and broader PCE compression as open concerns.Source: §7 · p. 17
  • The classified hard task is global optimization over a chosen state domain, not evaluating a fixed candidate state or decoding it.Restricted or locally optimized ansätze, approximation algorithms, and tailored decoders may avoid hard exact global optimization.Source: §7 · p. 17
  • Related QAOA evaluation and parameter-optimization hardness results concern fixed circuits or ansätze, unlike this paper’s optimization over specified Hamiltonian state domains.Other cited work examines resource tradeoffs, efficiently computable correlations, or achievable energies rather than the same worst-case classification.Source: §7 · p. 17
  • Compiler hardness coverage may change if preprocessing deletes, thresholds, or contracts small-weight edges before coloring, because that can change the packing.The specified Qiskit version retains all filler edges because its coloring graph uses every nonzero quadratic coefficient.Source: §7 · p. 18
  • The QRAO results do not automatically extend to general PCE workflows with higher-locality strings, nonlinear losses, different state preparation, or alternative decoding.Analogous results would require a hard-family image that preserves the promise gap over a suitable quantum state domain.Source: §7 · p. 18

Author contributions and AI disclosure

The author takes responsibility for the research, manuscript, code, and data, and discloses ChatGPT assistance. The appendix describes how the reductions preserve promise gaps through scaling and bounded perturbations.

Author contributions and AI disclosure

  • Stuart Hadfield is the sole author and takes responsibility for the research, manuscript, accompanying code, and data; ChatGPT assisted with literature synthesis, checking, and editing.The disclosed assistance included validation of Qiskit and NetworkX implementation claims and generation of the code and data package.Source: Author contributions and AI disclosure · p. 18

A.1 Promise-gap transformations

  • The reductions preserve gaps under energy shifts and rescaling, while a perturbation of norm at most ε leaves at least β∆ − 2ε gap after threshold adjustment.The transverse-field rationalization and connected positive completion choose ε ≤ β∆/8; multiplicative ratios require separate control of the full filler contribution, including its identity part.Source: §A.1 · pp. 21–22

A.2 Completion details for Theorem 4.2

The completion adds positive-weight filler edges whose perturbation is bounded, preserving at least three quarters of the source promise gap while keeping edge weights polynomial-bit-complexity.

A.2 Completion details for Theorem 4.2

  • Assigning each remaining clique or matching edge a common positive weight ε gives a filler contribution of 2Mε.Source: §A.2 · p. 22
  • Choosing ε ≤ ∆/(4dM) bounds the perturbation norm by ∆/8, while the identity coefficient contributes the known shift α = Mε/2.After shifting thresholds by α, Weyl’s inequality bounds eigenvalue movement by the perturbation norm.Source: §A.2 · p. 22
  • The completed instance retains a promise gap of at least 3∆/4, and all resulting edge weights have polynomial bit complexity.This follows from M = O(n^2) and inverse-polynomial ∆.Source: §A.2 · p. 22

B Cyclic-twist balance and local alignability

Cyclic Pauli interactions are locally alignable exactly when their twists sum to zero modulo three around every cycle; fixed greedy compilation also retains QMA-hardness for specified mixed-axis source terms.

B Cyclic-twist balance and local alignability

Mixed-axis source terms under greedy compilation

  • For every fixed stable degree-ordered greedy compiler, the compiled problem remains QMA-complete on the stated regular, connected, non-bipartite instances, even when every non-filler source term is mixed-axis.The construction applies the anisotropic-interaction hardness theorem [37]; filler couplings may remain aligned, and the cited hardness theorem covers anisotropic interactions only.Source: Mixed-axis source terms under greedy… · pp. 23–24

C.1 Proof of Theorem 5.3

The proof establishes NP-completeness for QRAC codewords, product states, and separable states, and QMA-completeness for unrestricted states.

C.1 Proof of Theorem 5.3

  • The QRAC-codeword energy problem is NP-complete because encoded assignments have the witnessed classical MaxCut value.Source: §C.1 · p. 24
  • For product states, the compiled three-axis family remains NP-hard with a promise gap of at least 3∆/4 and belongs to NP; the same NP-completeness extends to separable states.The separable-state optimum equals the product-state optimum for a linear energy objective.Source: §C.1 · p. 24
  • The unrestricted-state problem is QMA-complete by the three-axis hardness result and its compiler realization.Source: §C.1 · p. 24

C.2 Proof of Theorem 6.1

The proof uses rescaling and a three-copy construction for its first statement, then completes the hard family with positive filler weights for the connected case.

C.2 Proof of Theorem 6.1

  • The QRAO lift multiplies Quantum MaxCut value by three, preserving every multiplicative ratio; the stated convention’s Hamiltonians differ by factors of two and six.Source: §C.2 · p. 24
  • In three disjoint copies, corresponding vertices have matching degree and colored-neighbor histories, so the vertex-major order gives them the same color and packs them onto one qubit’s three axes.Source: §C.2 · p. 24
  • For the connected construction, positive filler weights can be chosen with polynomial bit complexity, leaving the compressed Hamiltonian in C3.The proof bounds the total filler contribution by δ.Source: §C.2 · p. 24

Related papers

Loading 2609.07090v2…