PaperlayerView exact revision on arXiv

Source-linked AI summary

Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer

Maliheh Aramon, Gili Rosenberg, Elisabetta Valiante, Toshiyuki Miyazawa, Hirotaka Tamura, Helmut G. Katzgraber

arXiv:1806.08815v3physics.comp-phcond-mat.stat-mechcs.DM

TL;DR

The paper asks how specialized CMOS hardware and physics-inspired algorithms perform on QUBO optimization. It benchmarks the Digital Annealer and an early PTDA against classical methods on spin-glass problems, finding roughly two-orders-of-magnitude speedups for dense instances but no apparent speedup for sparse two-dimensional instances.

  • Problem

    Efficiently solving widely applicable QUBO problems remains important, while the comparative scaling advantage of specialized optimization hardware and algorithms is unresolved.

  • Method

    The paper benchmarks the Digital Annealer and an early Parallel Tempering Digital Annealer against simulated annealing and parallel tempering with isoenergetic cluster moves on sparse and dense spin-glass problems.

  • Results

    Roughly two orders of magnitude faster than SA and PT on dense problems, the DA shows no speedup on sparse problems, while early PTDA results show better scaling for average-difficulty fully connected bimodal problems.

  • Takeaways & Limitations

    Application-specific CMOS hardware paired with physics-inspired optimization can produce efficient special-purpose optimization machines for fully connected problems.

Abstract

from arXiv · show

The Fujitsu Digital Annealer (DA) is designed to solve fully connected quadratic unconstrained binary optimization (QUBO) problems. It is implemented on application-specific CMOS hardware and currently solves problems of up to 1024 variables. The DA's algorithm is currently based on simulated annealing; however, it differs from it in its utilization of an efficient parallel-trial scheme and a dynamic escape mechanism. In addition, the DA exploits the massive parallelization that custom application-specific CMOS hardware allows. We compare the performance of the DA to simulated annealing and parallel tempering with isoenergetic cluster moves on two-dimensional and fully connected spin-glass problems with bimodal and Gaussian couplings. These represent the respective limits of sparse versus dense problems, as well as high-degeneracy versus low-degeneracy problems. Our results show that the DA currently exhibits a time-to-solution speedup of roughly two orders of magnitude for fully connected spin-glass problems with bimodal or Gaussian couplings, over the single-core implementations of simulated annealing and parallel tempering Monte Carlo used in this study. The DA does not appear to exhibit a speedup for sparse two-dimensional spin-glass problems, which we explain on theoretical grounds. We also benchmarked an early implementation of the Parallel Tempering DA. Our results suggest an improved scaling over the other algorithms for fully connected problems of average difficulty with bimodal disorder. The next generation of the DA is expected to be able to solve fully connected problems up to 8192 variables in size. This would enable the study of fundamental physics problems and industrial applications that were previously inaccessible using standard computing hardware or special-purpose quantum annealing machines.

I. INTRODUCTION

The paper motivates efficient QUBO optimization, introduces the Digital Annealer as specialized CMOS hardware, and benchmarks it against physics-inspired classical algorithms on spin-glass problems.

  • QUBO and equivalent quadratic Ising formulations capture many NP-hard combinatorial optimization problems arising across finance, chemistry, biology, logistics, scheduling, and machine learning.
  • The end of Moore’s law has increased interest in novel computational technologies for computationally intensive discrete optimization.
  • Quantum annealers have not yet achieved a consensus scaling advantage over conventional algorithms, with no reported speedup for an industrial application.
  • The Digital Annealer is application-specific CMOS hardware for fully connected QUBO problems, currently supporting up to 1024 variables.
  • The study benchmarks the DA and PTDA against simulated annealing and parallel tempering with isoenergetic cluster moves on spin-glass problems.
  • Simulated annealing starts from a random high-temperature state, cools according to a predefined schedule, and repeats runs to seek the global optimum.

B. The Digital Annealer’s Algorithm

The Digital Annealer builds on simulated annealing by evaluating all variable flips in parallel and exploiting hardware parallelism, while PT and cluster moves target energy-barrier traversal.

  • The Digital Annealer’s Algorithm: The DA starts every run from one arbitrary state rather than a separate random state, avoiding initial effective-field and energy calculations.
  • The Digital Annealer’s Algorithm: Each DA Monte Carlo step evaluates flips of all variables in parallel, records accepted candidates, and chooses one accepted flip uniformly at random.
  • The Digital Annealer’s Algorithm: Application-specific CMOS hardware updates effective fields of all neighbours in parallel, making that update constant-time regardless of connectivity.
  • The Digital Annealer’s Algorithm: The DA’s effective-field update costs O(N) for fully connected SA graphs but O(d) for fixed-degree sparse graphs, whereas the DA’s cost is connectivity-independent.
  • Parallel Tempering: Parallel tempering exchanges replicas across temperatures so they can temporarily reach higher temperatures and overcome energy barriers.
  • Parallel Tempering with Isoenergetic Cluster Moves: Isoenergetic cluster moves swap opposite-variable clusters between same-temperature replicas without changing their total energy, but provide no benefit on fully connected graphs.

D. The Parallel Tempering Digital Annealer’s Algorithm

The PTDA combines the DA’s parallel updates with parallel tempering, while the paper analyzes when parallel-trial updates improve acceptance and identifies CPU exchange moves as a bottleneck.

  • The Parallel Tempering Digital Annealer’s Algorithm: The PTDA applies the DA’s parallel-trial, parallel-update, and dynamic-offset mechanisms within each replica, while performing replica exchanges on a CPU.
  • The Parallel Tempering Digital Annealer’s Algorithm: Sequential CPU replica-exchange work can become a bottleneck as parallelism increases, limiting asymptotic speedup to 1/α when it represents fraction α of total work.
  • Parallel-Trial Versus Single-Trial Monte Carlo: The single-trial acceptance probability applies the Metropolis criterion A(∆E_i, T) ≡ e^−∆E_i/T to one proposed variable flip.
  • Parallel-Trial Versus Single-Trial Monte Carlo: The parallel-trial acceptance probability is the complement of rejecting all N variable-flip proposals, contrasting with single-trial acceptance.
  • Parallel-Trial Versus Single-Trial Monte Carlo: At low temperatures, the parallel-trial scheme can provide a best-case speedup of N, whereas at high temperatures both acceptance probabilities reach 1.
  • Parallel-Trial Versus Single-Trial Monte Carlo: The acceptance-probability comparison was measured after thermalization across multiple temperatures and problem classes, including 2D and fully connected spin glasses.

IV. SCALING ANALYSIS

The paper defines time-to-solution through repeated stochastic runs and estimates its distribution using Bayesian success probabilities and bootstrap resampling.

  • Time-to-solution definition: TTS measures the total time required to find a reference energy with probability 0.99.The reference energy is represented by the optimal energy when available.
  • Time-to-solution definition: R99 is the number of independent runs needed for at least one success with probability 0.99.Success probability θ is estimated for each problem instance.
  • TTS distribution estimation: Bayesian posteriors estimate each instance’s success probability instead of using only the sample success proportion.The posterior uses a Jeffreys prior and has a Beta(α+y, β+r−y) form.
  • TTS distribution estimation: Bootstrap resampling estimates the distribution of the q-th percentile of TTS across instances.The procedure samples instances and posterior success probabilities before computing R99 and TTS.
  • Algorithm-specific measurement: For the DA and PTDA, each sweep corresponds to N iterations, while anneal time is measured directly for specified iterations and runs.The DA anneal time is not linear in the number of runs for a fixed number of sweeps.
  • Algorithm-specific measurement: TTS scaling is valid only after solver parameters are tuned to minimize TTS.Otherwise, suboptimal scaling and incorrect conclusions may result.

V. BENCHMARKING PROBLEMS

The benchmark uses quadratic Ising and equivalent QUBO formulations on two-dimensional and fully connected spin glasses, varying disorder and problem size.

  • Problem formulation: The quadratic Ising Hamiltonian encodes Boolean spins through biases and couplers on graph vertices and edges.The spin variables satisfy s_i ∈ {−1, 1}.
  • Problem formulation: Minimizing the Hamiltonian is generally equivalent to weighted max-cut and is NP-hard on nonplanar graphs.Planar graphs are a special case with exact polynomial-time methods.
  • Problem formulation: The DA uses binary variables x_i ∈ {0, 1}, related to Ising spins by s_i = 2x_i − 1.This transformation converts the quadratic Ising problem into a QUBO problem.
  • Benchmark problem families: The benchmark includes 2D and SK spin glasses with bimodal or Gaussian couplings.These represent sparse versus fully connected structures and high versus low ground-state degeneracy.
  • Benchmark problem families: The Gaussian coefficients exceed the DA’s precision limit, so they are scaled to the maximum range and rounded to integers.The stated hardware limits are 225−1 for linear coefficients and 215−1 for quadratic coefficients.
  • Benchmark construction: Nine problem sizes and 100 random instances per size are generated for each problem category.For larger SK problems, high-sweep PT solutions serve as upper bounds for the optimal energy.

VI. RESULTS AND DISCUSSION

The study benchmarks DA and PTDA on Fujitsu hardware against optimized SA and PT-based methods across sparse and fully connected spin-glass problems.

  • Benchmark setup: DA and PTDA run on Fujitsu’s Digital Annealer hardware, while SA uses Isakov et al.’s optimized open-source implementation.The PT and PT+ICM implementation follows Zhu et al.
  • Benchmark setup: The benchmark varies graph density and coupling disorder to test sparse versus fully connected and high- versus low-degeneracy regimes.Two-dimensional and SK problems provide the density limits, while bimodal and Gaussian disorder vary degeneracy.
  • Benchmark setup: The reported comparisons use two-dimensional and SK spin-glass problems with bimodal and Gaussian disorder.The study also investigates how problem density affects DA performance.

A. 2D Spin-Glass Problems

On two-dimensional spin-glass problems, PT+ICM has the best TTS, while DA and SA are similar for bimodal disorder and DA is better for harder Gaussian disorder.

  • TTS comparison: PT+ICM has the lowest TTS and a clear scaling advantage for both bimodal and Gaussian 2D problems.The TTS distributions report means and 5th and 95th percentiles.
  • 2D-bimodal: For 2D-bimodal problems, DA and SA show similar TTS as problem size increases, although SA is better for small sizes.The parallel-trial boost does not reduce TTS or improve scaling in this regime.
  • 2D-Gaussian: For harder 2D-Gaussian problems, DA outperforms SA despite its current precision limit.The DA achieves lower residual energy for S ≤ 10^5 and higher success probabilities in the reported comparisons.
  • PTDA comparison: PTDA has higher TTS than DA for both disorder types, likely because parallel-tempering moves add CPU overhead.PTDA solves more bimodal instances to optimality but fewer Gaussian instances than DA.
  • Evaluation boundary: For 2D-Gaussian sizes N ≥ 400, DA and PTDA could not solve more than 80% of instances within 10^7 iterations.DA required 10^8 iterations for estimating TTS80, while PTDA was not run that long.
  • Success probabilities: For 2D-bimodal instances with N = 1024, DA has higher success probability than SA for 52 of 100 instances.At fixed size and sweeps, DA also reaches higher mean success probabilities, though the gap narrows with size.

B. SK Spin-Glass Problems

For fully connected SK spin-glass problems, the DA delivers substantial speedups, while PTDA shows the strongest scaling evidence for bimodal disorder. The comparison is constrained by uncertainty in reference-energy optimality and parameter tuning.

  • Performance: At the largest problem sizes, the DA provides at least two orders of magnitude speedup over SA and PT for SK-bimodal instances.The comparison uses the TTS distributions shown in Fig. 7a.
  • Limitations: The reference energy for complete-graph problems is an upper bound on the exact optimum, and its tightness is unknown.It is nevertheless reported as the best known solution.
  • Scaling: For the TTS50 statistic, PTDA exhibits superior scaling over the other three algorithms for SK-bimodal problems.Scaling exponents were estimated by fitting y = 10^α+βN to the largest five problem sizes.
  • Scaling: For TTS80, overlapping 90% confidence intervals prevent a strong scaling conclusion, although PTDA has the lowest point estimate.The overlap limits the strength of the comparison despite PTDA’s point estimate.
  • Limitations: Non-optimal parameter tuning may make the measured algorithmic scaling suboptimal, including for PTDA and PT.PT might improve with a more optimized temperature schedule, while PTDA might improve after tuning.
  • Performance: For SK-Gaussian instances, the DA retains at least two orders of magnitude speedup over the other algorithms without a strong scaling advantage.Gaussian disorder produces harder problems in this comparison.

The DA versus SA

The DA achieves lower time-to-solution than SA on fully connected bimodal and Gaussian spin-glass problems. This advantage is associated with variable- and density-independent anneal time and parallel-trial improvements in success probability, while hardware precision was not limiting for Gaussian instances.

  • Overall comparison: The DA achieves lower TTS than SA for both SK-bimodal and SK-Gaussian problem instances.The reported TTS80 scaling estimates are β = 0.0021(7) versus 0.0027(6) for bimodal disorder, and β = 0.0019(3) versus 0.0028(5) for Gaussian disorder.
  • Mechanism: The DA’s anneal time is independent of variable count and problem density, whereas an SA sweep becomes more expensive as size and density increase.This difference contributes to lower DA TTS on fully connected problems.
  • Mechanism: The parallel-trial scheme significantly improves success probability for fully connected 1024-variable spin glasses, with a larger boost for Gaussian coefficients.Gaussian coefficients correspond to the low-degeneracy instances in this comparison.
  • Precision: The DA outperforms SA on Gaussian-disorder instances, indicating that the study’s 16-bit hardware precision is not a limiting factor there.The authors relate this to the expected energy gap exceeding 10^-5.

C. Spin-Glass Problems with Different Densities

Across problem densities, the DA matches SA on the sparsest instances but gains roughly two orders of magnitude in TTS on dense, fully connected problems. The results also connect this advantage to parallel trials and hardware parallelization, while PTDA shows better scaling for an average-difficulty fully connected bimodal problem.

  • Approximately two orders of magnitude: the DA outperforms SA on fully connected problems, while showing similar TTSs on sparse problems.
  • The DA has lower TTSs than SA at every tested density except the sparsest 2D-bimodal problem.For the sparsest 2D-bimodal set, too few instances were solved optimally to estimate TTS80 statistics.
  • The DA has statistically significantly higher success probabilities than SA at every density except the sparsest 2D-bimodal set.The experiment used 100 size-1024 spin-glass instances per density.
  • The dense-problem advantage is attributed to the parallel-trial scheme combined with massive application-specific CMOS parallelization.
  • The early PTDA implementation has higher TTS because of CPU overhead for replica-exchange moves, yet it shows better scaling on an average-difficulty fully connected bimodal problem.
  • The next DA generation is expected to optimize up to 8192 fully connected variables, while hardware replica-exchange moves could improve PTDA performance.
  • Pairing application-specific CMOS hardware with physics-inspired optimization produces special-purpose machines potentially useful for previously inaccessible physics and industrial problems.

CONFLICT OF INTEREST STATEMENT

The authors report affiliations with 1QBit, Fujitsu Laboratories, Microsoft Research, and funding from several organizations. They declare no further commercial or financial relationship constituting a potential conflict of interest.

  • Authors report employment or prior employment at 1QBit, Fujitsu Laboratories Ltd., and Microsoft Research.
  • The authors declare no further commercial or financial relationship that could constitute a potential conflict of interest.
  • The research received support from 1QBit, Fujitsu Laboratories Ltd., Fujitsu Ltd., the National Science Foundation, ODNI, and IARPA.

Appendix A: Simulation Parameters

The appendix describes parameter tuning and TTS estimation for DA, SA, PT, PT+ICM, and PTDA across the benchmark problem classes. It specifies temperature schedules, run procedures, and hardware-related parameter choices.

  • Grid searches on subsets of instances selected algorithm parameters using optimality counts, success probability, and residual energy.
  • Optimal TTS was obtained by varying sweeps or iterations, estimating each TTS distribution, and selecting the lowest-mean distribution.
  • DA and SA used 100 independent runs from zero vectors with a linear inverse-temperature schedule; the DA used Metropolis acceptance.
  • The DA’s dynamic offset was disabled because parameter experiments found performance indifferent to that mechanism.
  • PT and PT+ICM used geometric temperature schedules and replica counts chosen for replica-exchange acceptance probabilities above 0.2.
  • PTDA used 40 replicas for both SK-bimodal and SK-Gaussian instances, with dependent replicas requiring 30 repeated algorithm runs for TTS estimation.
Loading 1806.08815v3…