PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Annealing for Industry Applications: Introduction and Review

Sheir Yarkoni, Elena Raponi, Thomas Bäck, Sebastian Schmitt

arXiv:2112.07491v3quant-ph

TL;DR

Quantum annealing offers a programmable heuristic approach to combinatorial optimization, but practical evidence and guidance about its industrial applicability remain dispersed. This paper reviews QA foundations, hardware and software, formulations, applications, and limitations, concluding that its practical value depends strongly on problem structure, size, constraints, and hardware overheads.

  • Problem

    Practitioners lack a centralized account of which industrial problems quantum annealing can address, at what sizes, and with which constraints and practical limitations.

  • Method

    The paper reviews QA theory, software, hardware, formulations, constrained optimization, and demonstrated industrial applications and proofs of concept, mainly using D-Wave systems.

  • Results

    The review catalogs demonstrated applications and empirical studies across domains, including traffic, scheduling, chemistry, and machine learning, while characterizing addressable problem sizes and constraints.

  • Takeaways & Limitations

    QA is most relevant when application instances fit available hardware and are sufficiently difficult that classical solvers cannot efficiently solve them.

  • Takeaways & Limitations

    Current QPUs have limited qubits and couplers, QA is heuristic, and hardware-specific transformations can impose significant polynomial or exponential overhead.

Abstract

from arXiv · show

Quantum annealing is a heuristic quantum optimization algorithm that can be used to solve combinatorial optimization problems. In recent years, advances in quantum technologies have enabled the development of small- and intermediate-scale quantum processors that implement the quantum annealing algorithm for programmable use. Specifically, quantum annealing processors produced by D-Wave Systems have been studied and tested extensively in both research and industrial settings across different disciplines. In this paper we provide a literature review of the theoretical motivations for quantum annealing as a heuristic quantum optimization algorithm, the software and hardware that is required to use such quantum processors, and the state-of-the-art applications and proofs-of-concepts that have been demonstrated using them. The goal of our review is to provide a centralized and condensed source regarding applications of quantum annealing technology. We identify the advantages, limitations, and potential of quantum annealing for both researchers and practitioners from various fields.

1 INTRODUCTION

Quantum annealing is a heuristic quantum optimization approach implemented by programmable processors, especially D-Wave systems, for combinatorial and industry-relevant problems. The review explains the workflow, technology, applications, and practical limitations relevant to researchers and practitioners.

  • Quantum computing uses quantum phenomena such as superposition and entanglement to provide a computational paradigm for challenging problems.
  • Quantum annealing relaxes adiabatic quantum computation and heuristically searches for ground states of Ising models, including formulations of NP-hard problems.
  • D-Wave annealers are the most widely used quantum-annealing devices because they currently provide commercially available superconducting-qubit hardware.
  • The D-Wave workflow converts an application into a QUBO and logical graph, minor-embeds it onto the QPU, and then programs the annealer.
  • The review synthesizes theoretical foundations, required software and hardware, industrial applications, proofs of concept, benefits, and limitations to guide practitioners.

2 FOUNDATIONS OF QUANTUM ANNEALING

Quantum annealing is motivated by adiabatic evolution from an easily prepared ground state toward a problem Hamiltonian, but practical implementations relax adiabatic conditions and operate heuristically. The section introduces the physical workflow, Ising formulation, reverse annealing, and hardware limitations.

  • The adiabatic theorem motivates evolving a system slowly from an easy initial Hamiltonian toward a complex final Hamiltonian whose ground state encodes the solution.
  • AQC can simulate any quantum circuit, whereas QA relaxes adiabatic conditions and therefore becomes a heuristic rather than universally guaranteed method.
  • The annealing schedule reduces the initial Hamiltonian and increases the final Hamiltonian over time, ideally evolving the system into the final ground state.
  • The final Ising Hamiltonian uses graph vertices and edges, symmetric pairwise couplings J_ij, and local fields h_i to define the classical optimization problem.
  • Noise, thermal fluctuations, unknown spectral gaps, limited hardware protocols, and competing effects of non-stoquastic terms constrain practical QA performance.
  • Reverse annealing starts from user-specified classical states, raises the transverse field for partial mixing, and lowers it to refine candidate solutions.

2.2 Quadratic unconstrained binary optimization formulation

QUBO is a standard formulation for quantum annealing in which binary optimization variables and their pairwise interactions define the objective. It is equivalent to the Ising representation through a change of basis.

  • QUBO and Ising models are the most common formulations used to construct problems for quantum annealing.
  • QUBO is equivalent to the Ising model through the basis transformation s ↦ 2x − 1.
  • The QUBO representation uses a vector x of N binary variables and a symmetric matrix Q defining interactions between variables.

2.3 Higher-order binary optimization problems

Higher-order binary optimization terms can be reduced to QUBO by introducing auxiliary variables and penalty constraints, but this increases problem size. Alternative parity architectures can represent higher-order interactions with different scaling properties.

  • A 3-local term x_1x_2x_3 can be reduced to QUBO by introducing y_1 = x_1x_2 and enforcing the relation with a penalty term.
  • Recursive reductions convert arbitrary higher-order polynomials to QUBO, but the polynomial number of added variables can quickly make representations intractable.
  • The penalty scalar λ > 1 ensures validity of the auxiliary-variable constraint in the reduced QUBO.
  • ParityQC’s LHZ architecture can implement k-local terms using a k-dimensional lattice and provide all-to-all connectivity for the encoded Hamiltonian.
  • The parity architecture requires a number of qubits linear in the number of non-zero Hamiltonian terms for arbitrary Hamiltonian encoding.

2.4 Constrained optimization problems

Quantum annealing does not natively enforce constraints, so constrained problems are converted into QUBOs by adding penalty terms, slack variables, or auxiliary optimization procedures. These transformations expand the problem and require carefully chosen penalties because hardware has limited coupling-strength range and noise sensitivity.

  • Constraint encoding: Constraints cannot be directly enforced after programming the Hamiltonian, so they must be encoded as contributions to the QUBO cost function.The annealing process selects a minimal-energy configuration without separately applying binary-variable conditions.
  • Equality constraints: One-hot and linear equality constraints are represented by quadratic penalty terms that vanish when the constraint is satisfied and increase otherwise.For a one-hot constraint, λ(x1 + x2 + x3 − 1)^2 is zero only when exactly one variable equals 1.
  • Inequality constraints: Linear inequalities are converted using auxiliary slack variables, allowing canonical NP-complete and NP-hard problems to be transformed into QUBOs and Ising models.The transformation increases the number of optimization variables and can increase embedding demands.
  • Scope boundary: Binary slack-variable encodings cannot straightforwardly handle the most general arbitrary real-valued coefficients.The number of slack variables can also increase for arbitrary integer coefficients, especially when negative coefficients occur.
  • Penalty selection: Penalty strengths must exceed any objective reduction from violating a constraint, yet remain as small as possible because large values reduce effective resolution and amplify noise distortion.Quantum annealing hardware has a limited dynamic range for coupling strengths and prefactors.
  • Alternative methods: An alternative Lagrangian-like approach introduces one real-valued auxiliary variable per constraint and iteratively alternates gradient ascent with quantum annealing.Instead of solving one QUBO, the method solves a series of QUBOs for successive auxiliary-variable values.

2.5 Discrete variables

Quantum annealing represents discrete variables through qubit encodings, with binary and one-hot schemes trading qubit count against interaction and embedding costs. Domain-wall encoding uses fewer qubits and more local couplings, and has shown improved feasibility in tested problems.

  • Discrete-variable encodings: Discrete variables are important in applications such as scheduling and graph colouring, and each categorical variable can be encoded using multiple qubits.The paper discusses several encodings for discrete or logical integer variables.
  • Binary encoding: Binary encoding represents d states with ⌈log2(d)⌉ qubits, but required validity and inter-variable interactions make it uncommon in practice.The practical drawback is particularly relevant for limited-topology hardware.
  • One-hot encoding: One-hot encoding uses d qubits for d states and requires quadratic interactions between all qubits representing one variable.This creates embedding overhead on hardware with limited topology.
  • Domain-wall encoding: Domain-wall encoding uses d−1 qubits for d states and replaces all-to-all intra-variable interactions with linear coupling.It has been reported as more efficient in different test problems and associated with a higher probability of feasible solutions.

2.6 Continuous variables

Continuous variables can be encoded with binary representations, but analog quantum-annealing hardware makes high-precision representations difficult. Exponentially spaced prefactors amplify noise differences, while the required qubit count can be large.

  • Binary representation: Continuous numbers are represented using binary encoding schemes, analogous to classical computing.A floating-point variable is expanded into binary variables with a chosen precision.
  • Encoding parameters: A floating-point variable with N bits uses binary variables xi ∈ {0, 1}, a base b > 1 controlling logarithmic resolution, and a real scale factor c controlling range.The encoding uses exponentially spaced prefactors for the binary variables.
  • Precision limitations: High-precision continuous encoding is poorly suited to quantum annealing because QPU noise affects exponentially weighted binary variables differently and can fall below the required precision.The encoding may also require a relatively large number of qubits.

2.7 Hardware architecture for quantum annealers

D-Wave systems are the largest-scale and best-known quantum-annealing initiative, using superconducting flux qubits arranged in fixed hardware graphs. Chimera and Pegasus illustrate how topology and defective components constrain programmable problem structure.

  • Industry hardware: D-Wave launched its first quantum-annealing hardware product line in 2011 and has continued offering updated platforms.Other industrial initiatives include NEC parametron-qubit hardware and Qilimanjaro processors targeting both annealing and gate-model computation.
  • Qubit technology: D-Wave QPUs use superconducting flux qubits, each realizing a simple two-level quantum system.Quantum annealers could in principle be built from several other qubit technologies.
  • Hardware graphs: A QPU’s fixed hardware graph represents qubits as nodes and couplers as edges, and its topology determines possible final Hamiltonians.Connectivity generally trades off against the total number of available qubits.
  • Hardware yield: Current D-Wave processors typically have approximately 97% qubit yield, so the working graph is a defective-component subgraph that can restrict solvable problem size and structure.Missing qubits and couplers matter according to their locations and quantity.
  • Chimera and Pegasus: Chimera uses a two-dimensional lattice of K4,4 unit cells with six couplers per qubit, whereas Pegasus has degree 15 and is not bipartite.The figure depicts qubits as nodes, couplers as edges, and the corresponding Chimera and Pegasus unit-cell structures.

2.8 Minor-embedding techniques for hardware graphs

Minor-embedding maps logical optimization graphs onto hardware topologies by representing logical variables with chains of physical qubits. This mapping is essential but costly, difficult to optimize, and increasingly burdensome for dense or higher-order problems.

  • Embedding fundamentals: Minor-embedding encodes each logical variable as a chain of physical qubits while preserving relevant graph topology on the QPU.The logical graph is mapped to a hardware-compatible graph through graph-minor techniques.
  • Embedding challenges: Embedding is nontrivial because deciding graph-minor embeddability is NP-complete, so practical systems rely on polynomial-time heuristics.Embeddings also require chain-strength constraints to keep physical qubits representing one logical variable aligned.
  • Embedding algorithms: Heuristic and specialized algorithms target efficient embeddings, including methods for sparse graphs, clique minors, damaged hardware, and Cartesian products of complete graphs.These approaches differ in scalability, topology assumptions, and resilience to missing qubits.
  • Resource overhead: N_physical ∼ N_logical^2 for pairwise problems embedded on Chimera hardware, making embedding overhead a dominant time and performance cost.Higher-order interactions can require substantially worse, typically exponential, scaling in the number of variables.
  • Resource overhead: Fully connected problems incurred unfavorable exponential time-to-solution overhead across square-lattice, Chimera, and LHZ embedding schemes as problem size increased.This comparison underlines the need for new approaches to reduce embedding overhead.

2.9 Noise and mitigation strategies

Noise affects quantum annealing both through environmental dynamics and direct perturbations of programmed Hamiltonian parameters. Mitigation methods exist, but error correction remains less established than in gate-model quantum computing.

  • Noise effects: Decoherence errors reduce the probability of obtaining global minima, while the open, interacting dynamics make universal conclusions about QA power difficult.Thermal robustness can depend on sufficiently long annealing times and weak environmental coupling.
  • Noise effects: Integrated Control Errors perturb programmed fields and couplings through low-frequency noise, discretization errors, and other hardware effects.The perturbation is modeled as shifts in the final Hamiltonian parameters.
  • Noise effects: |δh_i| ≈ 0.05 and |δJ_ij| ≈ 0.02 in Ising units are typical magnitudes for hardware- and problem-dependent parameter shifts.Next-nearest-neighbor effects can also produce effective ghost couplings between physically unconnected qubits.
  • Noise effects: Static noise reshuffles energy levels, while quantum annealing showed a limited scaling advantage over simulated thermal annealing under same-magnitude disorder in the SKM study.The study also found that chain couplings must grow with problem size, up to logarithmic corrections, to represent larger SKM instances.
  • Mitigation strategies: Spin-reversal transforms average asymmetric Hamiltonian distortions without changing the ground-state distribution.Other approaches include anneal offsets and redundant encoding with majority-vote recovery, though the latter incurs polynomial qubit overhead.
  • Mitigation strategies: Current QA lacks error-correction methodologies as established as those in gate-model QC, motivating continued hardware and software research.Proposed directions include additional control features, alternative drivers, spin reversals, and annealing-parameter tuning.

2.10 Software and hybrid algorithms

Quantum annealing workflows depend heavily on classical software for model construction, hardware access, and orchestration. Hybrid algorithms extend applicability by partitioning problems or combining quantum sampling with classical search.

  • Software ecosystem: High-level QA software development has lagged hardware progress, and many tools for control, QUBO/Ising formulation, and access are concentrated within D-Wave Systems.This software dependence shapes how practitioners formulate and submit problems to quantum processors.
  • Software ecosystem: D-Wave’s Ocean provides Python tools for constructing Ising/QUBO models, submitting embedded or topology-specific problems, and solving them with QPU and classical samplers.Ocean includes dimod, dwave-system, and classical solvers such as simulated thermal annealing and Tabu search.
  • Software ecosystem: Ising/QUBO libraries developed for other quantum-computing contexts can also support QA, including selected OpenFermion algorithms and domain-wall encodings.Specialized compilers such as ParityQC target counter-diabatic protocols, LHZ architectures, and higher-than-quadratic binary optimization.
  • Hybrid algorithms: Hybrid algorithms partition problems into sub-problems solved by the annealer and then recombine the results, enabling problems too large to embed directly on QPUs.More generally, any algorithm that offloads part of its calculation to a quantum processor can be considered hybrid quantum-classical.
  • Hybrid algorithms: Reverse annealing can serve as a tunable mutation operator in quantum-assisted genetic algorithms by locally refining classically prepared candidate solutions.The reverse-annealing point s = s′ controls the degree of mutation.

2.11 Role of time in quantum annealing

QA time includes programming, annealing, readout, and repeated sampling, but these engineering costs differ from the annealing cycle’s algorithmic runtime. Selecting annealing time therefore requires problem-specific calibration.

  • Time components: A QA run comprises initialization, annealing, and readout; initialization programs fields and couplings, annealing follows A(t) and B(t), and readout returns a candidate spin configuration.Reverse annealing adds a reverse-annealing duration to the forward annealing time.
  • Time components: T_total = T_init + k(T_tot_a + T_r) measures wall-clock time for k samples, including programming, repeated annealing, and readout.Steps corresponding to annealing and readout are repeated to obtain statistics and improve the chance of finding the global optimum.
  • Runtime interpretation: T_total should not be conflated with T_a, because programming and readout are implementation-dependent costs and k is user-selected.The paper distinguishes engineering wall-clock time from the duration of a single annealing cycle.
  • Runtime calibration: Longer annealing times increase the probability of remaining in the ground state, although shorter cycles with more repetitions can be more efficient in practice.The practical choice balances sufficient ground-state probability against minimizing cycle duration.
  • Runtime calibration: QA is not a fixed-time algorithm in the classical sense because an appropriate T_a must be calibrated for each particular problem.The optimal setting depends on the trade-off between annealing duration and success probability.

3 QUANTUM ANNEALING IN REAL-WORLD APPLICATIONS

The review surveys quantum annealing applications across industrial optimization, scientific simulation, machine learning, and finance. Reported benefits are highly problem-dependent, with practical limits arising from modeling choices, connectivity, noise, embedding, and hybrid-solver overhead.

  • Traffic flow optimization: Quantum annealing enabled real-time multi-robot routing, but hybrid execution faced classical formulation, collision-detection, communication, and embedding bottlenecks.The reported approach addressed up to 800 variables, while reducing calls to the QPU was proposed to lower overhead.
  • Scheduling and logistics: Scheduling applications reached realistic near-term problem scales, but performance depended on the instance, embedding requirements, and comparison-time definition.For wind-optimal flight conflict resolution, challenging programmable subproblems were solved to optimality with 99% probability within a second of annealing time under reasonable modeling choices.
  • Traffic flow optimization: QA outperformed simulated annealing for traffic-signal optimization in a specific parameter domain, while partitioning introduced a performance drawback as straight-through traffic increased.The optimization was divided into 42 groups and solved in parallel.
  • Scheduling and logistics: A real-world factory paint-shop study found adequate quantum and hybrid solutions at smaller sizes, while large-size performance approached that of a simple greedy algorithm.The authors concluded that QA was approaching the limit of industrially relevant problem scales.
  • Quantum Simulation for Chemistry, Physics and Biology: In quantum simulation and biology applications, QA supported constrained polymer sampling and DNA-binding prediction, but hardware connectivity restricted implementable features and favored classical methods for larger datasets.The DNA-binding study used a D-Wave 2X with 1098 functional qubits, yet only about 40 features were implementable.
  • Quantum Machine Learning: Quantum machine-learning results varied with training size and algorithm: QA showed advantages on some small datasets, underperformed traditional methods on larger Higgs datasets, and reverse annealing improved NBMF factorization quality by 12%.The matrix-factorization benefit depended on the exact matrix being factorized.

4 LESSONS LEARNED ABOUT QUANTUM ANNEALING

The review identifies formulation and hardware constraints that shape how quantum annealing can be applied in practice. QA remains a heuristic method whose potential benefits are not yet conclusively established.

  • QA applications must be formulated as Ising or QUBO problems using spin or binary variables tailored to the hardware architecture.For D-Wave superconducting QPUs, current formulations encode problems through these hardware-compatible representations.
  • Current annealers encode only linear and quadratic terms, requiring all objective terms and constraints to be represented in that form.Fixed qubit topologies can also restrict connectivity or require minor-embedding and hybrid techniques.
  • Hardware-specific transformations can impose significant polynomial or even exponential overhead on arbitrary problems.The overhead arises when general problems are converted into formulations compatible with available connectivity and interaction structures.
  • QA relaxes the conditions of adiabatic quantum computation, sacrificing theoretical guarantees for near-term applicability as a metaheuristic optimization algorithm.Quantum fluctuations may aid transitions between spin configurations, but conclusive evidence remains elusive.

5 CONCLUSIONS

This review synthesizes quantum annealing’s foundations, enabling software and hardware, and demonstrated applications to assess its current practical status. It concludes that performance is problem-dependent and hardware-limited, while specialized mappings can support robust fixed-time instance solving.

  • The paper reviews QA foundations, the software and hardware of current processors, and empirical applications organized across major application fields.The review examines addressable problems, problem sizes, scaling behavior, and representable constraints.
  • QA’s empirical performance depends strongly on the problem formulation, logical-variable encoding, and embedding onto the hardware platform.The review identifies these interactions as influencing results across application domains.
  • Current hardware efficiently addresses only relatively small problem sizes, with physical-qubit counts and restricted connectivity creating major overheads.The number of physical qubits required typically scales polynomially with the number of logical variables.
  • After careful problem-class analysis and hardware mapping, QA can solve each instance robustly in a fixed amount of time.This fixed-time behavior is identified as a major advantage for suitably mapped problem classes.
  • Future practical applicability depends on exploiting QA hardware properties that classical software cannot compensate for, including greater control and connectivity.The review highlights additional qubit control, driver Hamiltonians and operators, and higher connectivity as needed hardware developments.
Loading 2112.07491v3…