Mitigating Precision Errors in Quantum Annealing via Coefficient Reduction of Embedded Hamiltonians

1. Problem Statement

Current quantum annealers (e.g., D-Wave systems) face a critical limitation in numerical precision. The hardware accepts Ising Hamiltonians with coefficients within specific ranges (e.g., couplings $J_{ij} \in [-2, 1]$ and fields $h_i \in [-4, 4]$).

• Dynamic Range Issue: Real-world optimization problems often require a large dynamic range (the ratio between the largest and smallest coefficients). When a Hamiltonian with a large dynamic range is rescaled to fit hardware limits, small coefficients become susceptible to noise (control errors, thermal noise), degrading the quality of the output solution.
• The Missing Link: Existing literature proposes methods to reduce large coefficients in the logical Hamiltonian (the problem formulation). However, these studies largely ignore minor-embedding, the essential process of mapping the logical graph onto the sparse hardware graph of the quantum annealer.
• The Gap: Minor-embedding alters the coefficients of the Hamiltonian (specifically introducing "chain strengths" to enforce consistency). It is unknown whether coefficient-reduction methods designed for logical Hamiltonians remain effective after embedding, or if they inadvertently increase the dynamic range of the physical Hamiltonian.

2. Methodology

The authors revisited three existing coefficient-reduction methods under the constraints of minor-embedding, using the D-Wave Advantage quantum annealer (Pegasus graph topology).

The Three Methods Evaluated:

1. Interaction-Extension Method (IEM): Breaks down strong couplings into weaker ones by introducing auxiliary variables.
2. Bounded-Coefficient Encoding (BCE): Controls the magnitude of coefficients when representing integer variables as linear combinations of binary variables.
3. Augmented Lagrangian Method (ALM): Uses penalty perturbation to reduce the required penalty coefficients for constraints.

Experimental Workflow:

• Minor-Embedding: Mapped logical Hamiltonians to the hardware graph using a heuristic algorithm (clique-based minorminer).
• Scaling Factor Analysis: Calculated scaling factors for physical external fields ($s_{\tilde{h}}$) and couplings ($s_{\tilde{J}}$) to determine the bottleneck for precision.
• Optimal Chain Strength Search: Unlike theoretical studies, the authors performed an exhaustive grid search on actual hardware to find the optimal chain strength (the parameter that maximizes sample quality) for each configuration.
• Metrics: Evaluated sample quality using the probability of finding the ground state ($P_{opt}$) and average energy.

Datasets:

• QUBO: 126 instances from MQLIB.
• MKP (Multi-dimensional Knapsack Problem): Instances from OR-Library.
• QAP (Quadratic Assignment Problem): Small instances (nug5, tai5a).
• Trivial Problems: Custom-made minimal examples to isolate specific behaviors.

3. Key Contributions

1. First Comprehensive Study under Minor-Embedding: This is the first work to rigorously evaluate coefficient-reduction methods specifically on the physical (embedded) Hamiltonian, rather than just the logical one.
2. Empirical Validation of Chain Strength: The authors demonstrated that optimal chain strength cannot be reliably predicted by theory or simulation alone; it requires exhaustive search on actual hardware due to the problem-dependent nature of the energy landscape.
3. Discovery on External Fields: The study empirically proved that reducing external field coefficients at the logical level is generally unnecessary. Minor-embedding naturally reduces external field coefficients (by distributing them across chains), often making them smaller than the coupling coefficients.
4. Method-Specific Insights:
   • IEM: Proven effective for reducing dynamic range and improving sample quality in QUBO problems.
   • BCE: Effective for trivial integer problems but showed limited utility on practical MKP instances.
   • ALM: Effective in simulation (Simulated Annealing) without embedding, but failed to improve sample quality (and sometimes degraded feasibility) when applied with minor-embedding on quantum hardware.

4. Key Results

A. Necessity of Reducing External Fields

• Finding: In almost all tested instances (including QUBO, MKP, and QAP), the scaling factor of the physical external field ($s_{\tilde{h}}$) was smaller than or equal to the scaling factor of the physical couplings ($s_{\tilde{J}}$).
• Implication: The hardware precision bottleneck is determined by the coupling coefficients (specifically the chain strength), not the external fields. Therefore, preprocessing efforts to reduce logical external fields are redundant; the focus should remain on reducing coupling coefficients.

B. Interaction-Extension Method (IEM)

• Result: Successfully reduced the maximum coupling coefficients in the embedded Hamiltonian.
• Performance: On QUBO instances, reducing coefficients via IEM led to a significant improvement in sample quality ($P_{opt}$ approached 1.0). The optimal chain strength scaled down proportionally with the reduced logical coefficients.
• Trade-off: While effective, IEM increases the number of variables (auxiliary spins), which can degrade embedding quality if the reduction is too aggressive.

C. Bounded-Coefficient Encoding (BCE)

• Result: On a trivial integer problem, BCE successfully reduced chain strength and improved $P_{opt}$.
• Limitation: On practical MKP instances, the improvement was negligible. The authors hypothesize that the presence of other quadratic terms in the QUBO formulation (unrelated to the integer encoding) negates the benefits, or that the variable overhead from BCE degrades the embedding quality.

D. Augmented Lagrangian Method (ALM)

• Result: In Simulated Annealing (without embedding), ALM successfully reduced the required penalty coefficient while maintaining feasibility.
• Failure on Hardware: When applied with minor-embedding on the D-Wave machine, ALM did not improve sample quality. In fact, the feasibility rate decreased as the perturbation width increased.
• Cause: The interaction between the perturbation and the minor-embedding process (specifically the chain strength requirements) appears to negate the theoretical benefits of ALM. The perturbation did not allow for a lower chain strength, and the noise sensitivity increased.

5. Significance and Future Directions

• Practical Guidance: The paper provides a clear roadmap for preprocessing quantum annealing problems. Researchers should prioritize reducing coupling coefficients (using methods like IEM) rather than external fields.
• Hardware-Aware Preprocessing: It highlights that algorithms designed for theoretical models often fail when the physical constraints of minor-embedding are introduced. Future algorithms must be co-designed with embedding strategies.
• Future Work:
  • Developing embedding strategies that specifically minimize chain strength requirements.
  • Exploring combinations of Quantum Annealing Correction (QAC) and coefficient reduction.
  • Investigating non-ground-state-preserving heuristics that might offer better practical performance despite theoretical deviations.

In conclusion, this study establishes that while coefficient reduction is vital for mitigating hardware precision errors, the choice of method must be validated against the specific constraints of minor-embedding. The Interaction-Extension Method emerges as the most promising approach for current hardware, while ALM requires further investigation before it can be effectively utilized in this context.