On the Emerging Potential of Quantum Annealing Hardware for Combinatorial Optimization Byron Tasse

2025-05-02 0 0 707.45KB 25 页 10玖币
侵权投诉
On the Emerging Potential of Quantum Annealing Hardware for
Combinatorial Optimization
Byron Tasseff
Los Alamos National Laboratory, Los Alamos, NM 87545
Tameem Albash
University of New Mexico, Albuquerque, NM 87131
Zachary Morrell, Marc Vuffray, Andrey Y. Lokhov, Sidhant Misra, Carleton Coffrin∗
Los Alamos National Laboratory, Los Alamos, NM 87545
Abstract
Over the past decade, the usefulness of quantum annealing hardware for combinatorial optimization
has been the subject of much debate. Thus far, experimental benchmarking studies have indicated that
quantum annealing hardware does not provide an irrefutable performance gain over state-of-the-art op-
timization methods. However, as this hardware continues to evolve, each new iteration brings improved
performance and warrants further benchmarking. To that end, this work conducts an optimization per-
formance assessment of D-Wave Systems’ most recent Advantage Performance Update computer, which
can natively solve sparse unconstrained quadratic optimization problems with over 5,000 binary decision
variables and 40,000 quadratic terms. We demonstrate that classes of contrived problems exist where this
quantum annealer can provide run time benefits over a collection of established classical solution meth-
ods that represent the current state-of-the-art for benchmarking quantum annealing hardware. Although
this work does not present strong evidence of an irrefutable performance benefit for this emerging op-
timization technology, it does exhibit encouraging progress, signaling the potential impacts on practical
optimization tasks in the future.
1 Introduction
In the 1990s, an optimization algorithm called quantum annealing (QA) was proposed with the aim of
providing a fast heuristic for solving combinatorial optimization problems [44, 68, 26, 23, 71]. At a high
level, QA is an analog quantum algorithm that leverages the non-classical properties of quantum systems
and continuous time evolution to minimize a discrete function. Annealing is the process that steers the
dynamics of the quantum system into an a priori unknown minimizing variable assignment of that function.
Under suitable conditions, theoretical results have shown that QA can arrive at a global optimum of the
desired function [10, 45, 40]. These results have motivated the study of using this algorithm for combinatorial
optimization over the past thirty years.
Due to the computational difficulty of simulating quantum systems [25], the study of QA remained a
theoretical pursuit until 2011, when D-Wave Systems produced a quantum hardware implementation of the
QA algorithm [6, 43, 33, 42]. This represented the first time that QA could be studied on optimization
problems with more than a few dozen decision variables and spurred significant interest in developing a
better understanding of the QA computing model [41, 35, 12].
The release of D-Wave Systems’ QA hardware platform also generated expectations that this new tech-
nology would quickly outperform state-of-the-art classical methods for solving well-suited combinatorial
∗corresponding author, cjc@lanl.gov
1
arXiv:2210.04291v1 [math.OC] 9 Oct 2022
optimization problems [23, 22, 71]. The initial interest from the operations research community was signif-
icant. However, through careful comparison with both complete search solvers [59, 67, 18] and specialized
heuristics [73, 8, 72, 56, 55, 70, 36, 2], it was determined that the available QA hardware was a far cry
from state-of-the-art optimization methods. These results tempered the excitement around the QA com-
puting model and reduced interest from the operations research community. Since the waning of the initial
excitement around QA, QA hardware has steadily improved and now features better noise characteristics
[78, 79, 47] and quantum computers that can solve optimization problems more than fifty times larger than
what was possible in 2013 [58].
Since 2017, we have been using the benchmarking practices of operations research to track the perfor-
mance of QA hardware platforms and compare the results with established optimization algorithms [11, 66].
In previous studies of this type, this benchmarking approach ruled out any potential performance benefit
for using available QA hardware platforms in hybrid optimization algorithms and practical applications, as
established algorithms outperformed or were competitive with the QA hardware in both solution quality
and computation time. However, in this work, we report that with the release of D-Wave Systems’ most
recent Advantage Performance Update computer in 2021, our benchmarking approach can no longer rule out
a potential run time performance benefit for this hardware. In particular, we show that there exist classes
of combinatorial optimization problems where this QA hardware finds high-quality solutions around fifty
times faster than a wide range of heuristic algorithms under best-case QA communication overheads and
around fifteen times faster under real-world QA communication overheads. This work thus provides com-
pelling evidence that quantum computing technology has the potential for accelerating certain combinatorial
optimization tasks. This represents an important and necessary first condition for demonstrating that QA
hardware can have an impact on solving practical optimization problems.
Although this work demonstrates encouraging results for the QA computing model, we also emphasize
that it does not provide evidence of a fundamental or irrefutable performance benefit for this technology.
Indeed, it is quite possible that dramatically different heuristic algorithms [21, 63] or alternative hardware
technologies [60, 32, 57, 53] can reduce the run time performance benefits observed in this work. We
look forward to and encourage ongoing research into benchmarking the QA computing model, as closing
the performance gap presented in this work would provide significant algorithmic insights into heuristic
optimization methods, benefiting a variety of practical optimization tasks.
This work begins with a brief introduction to the types of combinatorial optimization problems that can
be solved with QA hardware and the established benchmarking methodology in Section 2. It then presents a
summary of the key outcomes from a large-scale benchmarking study in Section 3, which required hundreds
of hours of compute time. In Section 4, the paper concludes with some discussion of the limitations of our
results and future opportunities for QA hardware in combinatoral optimization. Additional details regarding
the experimental design, as well as further analyses of computational results, are provided in the appendices.
2 Quantum Annealing for Combinatorial Optimization
Available QA hardware is designed to perform optimization of a class of problems known as Ising models,
which have historically been used as fundamental modeling tools in statistical mechanics [28]. Ising models
are characterized by the following quadratic energy (or objective) function of N={1,2, . . . , n}discrete spin
variables, σi∈ {−1,1},∀i∈ N :
E(σ) = X
(i,j)∈E
Jij σiσj+X
i∈N
hiσi,(1)
where the parameters, Jij and hi, define the quadratic and linear coefficients of this function, respectively.
The edge set, E ⊆ N × N , is used to encode a specific sparsity pattern in the Ising model, which is
determined by the physical system being considered. The optimization task of interest is to find the lowest
energy configuration(s) of the Ising model, i.e.,
minimize
σE(σ)
subject to σi∈ {−1,1},∀i∈ N .(2)
At first glance, the lack of constraints and limited types of variables make this optimization task appear
distant from real-world applications. However, the optimization literature on quadratic unconstrained binary
2
optimization (QUBO), which is equivalent to minimization of an Ising model’s energy function, indicates
how this model can encode a wide range of practical optimization problems [51, 54].
2.1 Foundations of Quantum Annealing
The central idea of QA is to leverage the properties of quantum systems to minimize discrete-valued functions,
e.g., finding optimal solutions to Problem (2). The mathematics of QA is comprised of two key elements: (i)
leveraging quantum states to lift the minimization problem into an exponentially larger space and (ii) slowly
interpolating (i.e., annealing) between an initial easy problem and the target problem to find high-quality
solutions to the target problem. The quantum lifting begins by introducing, for each spin, σi∈ {−1,1}, a
2|N | ×2|N | dimensional matrix, bσi, expressible as a Kronecker product of |N | 2×2 matrices,
bσi=1 0
0 1⊗···⊗1 0
0 1
| {z }
1 to i−1
⊗1 0
0−1
| {z }
i
⊗1 0
0 1⊗···⊗1 0
0 1
| {z }
i+ 1 to |N |
.(3)
In this lifted representation, the value of a spin, σi, is identified with the two possible eigenvalues, 1 and −1,
of the matrix bσi. The quantum counterpart of the energy function defined in Equation (1) is the 2|N | ×2|N |
matrix obtained by substituting spins, σi, with the bσimatrices, defined in Equation (3), within the algebraic
expression for the energy. That is,
b
E=X
(i,j)∈E
Jij bσibσj+X
i∈N
hibσi.(4)
Notice that the eigenvalues of the matrix b
Eare the 2|N | possible energies obtained by evaluating E(σ) from
Equation (1) for all possible configurations of spins. This implies that finding the minimum eigenvalue of b
E
is equivalent to solving Problem (2). This lifting is clearly impractical in the classical computing context, as
it transforms a minimization problem over 2|N | configurations into computing the minimum eigenvalue of a
2|N | ×2|N | matrix. The key motivation for the QA computational approach is that it is possible to model
b
Ewith only |N | quantum bits (qubits), so it is feasible to compute over this exponentially large matrix.
The annealing process in QA provides a method for steering a quantum system into the a priori unknown
eigenvector that minimizes Equation (4) [44, 24]. First, the system is initialized at an a priori known
minimizing eigenvector of a simple (“easy”) energy matrix, b
E0. After the system has been initialized, the
energy matrix is interpolated from the easy problem to the target problem slowly over time. Specifically, the
energy matrix at a point during the anneal is b
Ea(Γ) = (1−Γ) b
E0+ Γ b
E, with Γ varying from zero to one. The
annealing time is the physical time taken by the system to evolve from Γ = 0 to Γ = 1. When the anneal
is complete (Γ = 1), the interactions in the quantum system are described by the target energy matrix.
For suitable starting energy matrices, b
E0, and a sufficiently slow annealing time, the adiabatic theorem
demonstrates that a quantum system remains at the minimal eigenvector of the interpolating matrix, b
Ea(Γ)
[10, 45, 40], and therefore achieves the minimum energy of the target problem.
2.2 Quantum Annealing Hardware
The computers developed by D-Wave Systems realize the QA computational model in hardware with more
than 5,000 qubits. However, the engineering challenges of building real-world quantum computers are signif-
icant and have an impact on the previously discussed theoretical model of QA. In particular, QA hardware
is an open quantum system, meaning that it is affected by environmental noise and decoherence. The coef-
ficients in Equation (1) are constrained to the ranges, −4≤hi≤4, −1≤Jij ≤1, and nonzero Jij values
are restricted to a specific sparse lattice structure (i.e., EH⊆ E), which is determined by the hardware’s
implementation. (See Appendix A for details.) The D-Wave hardware documentation also highlights five
sources of deviation from ideal system operations called integrated control errors, which include background
susceptibility, flux noise, digital-to-analog conversion quantization, input/output system effects, and vari-
able scale across qubits [14]. These implementation details impact the performance of QA hardware [64].
Consequently, QA hardware often does not find globally optimal solutions but instead finds near-optimal
solutions, e.g., within 1% of global optimality [11]. All of these deviations from the ideal QA setting present
3
notable challenges for encoding and benchmarking combinatorial optimization problems with available QA
hardware platforms.
2.3 Benchmarking Quantum Annealing Hardware
Due to the challenges associated with mapping established optimization test cases to specific QA hardware
[11], the QA benchmarking community has adopted the practice of building instance generation algorithms
that are tailored to specific quantum processing units (QPUs) [48, 36, 49, 19, 2, 66]. The majority of the
proposed problem generation algorithms build Ising model instances that are defined over a specific QPU’s
hardware graph, i.e, (N,EH), or subsets of this graph, which are typically referred to as hardware-native
problems.
In this work, we build upon an earlier class of hardware-native instances termed corrupted biased ferro-
magnets, or CBFMs, as proposed by [66]. Given the QPU graph, (N,EH), the CBFM model adopts the
following distributions for hardware-native instances:
P(Jij = 0) = 0, P (Jij =−1) = 0.625, P (Jij = 0.2) = 0.375,∀(i, j)∈ EH
P(hi= 0) = 0.97, P (hi=−1) = 0.02, P (hi= 1) = 0.01,∀i∈ N .(CBFM)
Benchmarking these instances on the previous generation of D-Wave’s QPU architecture (i.e., the 2000Q plat-
form using the Chimera hardware graph) showed promising performance against state-of-the-art classical
alternatives, although a clear wall-clock run time benefit was not achieved [66].
In this work, we design a variant of the CBFM problem class called CBFM-P, which is tailored to
D-Wave’s new Advantage QPU platform. The parameter distributions are
P(Jij = 0) = 0.35, P (Jij =−1) = 0.10, P (Jij = 1) = 0.55,∀(i, j)∈ EH
P(hi= 0) = 0.15, P (hi=−1) = 0.85, P (hi= 1) = 0,∀i∈ N .(CBFM-P)
The CBFM-P parameters differ from CBFM, as the new Advantage QPU architecture features a different
and denser hardware graph called Pegasus, whose topology is detailed in Appendix A. These parameters
were discovered using a metaheuristic approach that explored different combinations of the twelve parameters
in this model and sought to maximize the problem’s difficulty. In each evaluation of the metaheuristic, a
combination of parameters was selected, one random instance was generated following this parameterization,
and a variety of classical solution methods were executed on the instance. The instance difficulty was
determined by comparing the lower and upper bounds of solutions found by these classical solution methods.
Although this approach is naive, we found that it was sufficient for the objectives of this study. We expect
that there exist classes of more challenging hardware-native instances on the Pegasus graph, but identifying
these classes is left for future work.
3 Optimization Performance Analysis
In this section, we compare the performance of the D-Wave Advantage QPU and a variety of classical
algorithms for optimization of CBFM-P Ising models. Specifically, we consider the following established
classical algorithms:
•A greedy algorithm based on steepest coordinate descent (SCD) [66];
•An integer quadratic programming (IQP) model formulation solved using the commercial mathematical
programming solver Gurobi [7];
•Simulated annealing (SA) [76, 16];
•A spin-vector Monte Carlo (SVMC) algorithm, which was proposed to approximate the behavior of
QA [74];
•Parallel tempering with iso-energetic clustering moves (PT-ICM) [80].
4
10−1100101102103
10−3
10−2
10−1
100
101
102
Execution time (seconds)
Relative difference from best (%)
D-Wave Advantage (τ= 62.5µs) D-Wave Advantage (τ= 62.5µs, tot.)
D-Wave Advantage (Best) Spin-vector Monte Carlo
Simulated Annealing Steepest Coordinate Descent
Integer Quadratic Programming Parallel Tempering with ICM
Traditional Optimality Tolerance
Figure 1: Evaluation of solution quality for a characteristic example of the CBFM-P instance class with
5,387 decision variables. Although the Advantage system4.1 QPU does not find the best-known solution,
it consistently and quickly finds solutions within 0.5% of the best-known solution. Here, the dashed line
corresponds to the achieved solution quality from QA when using 2,560 anneal-read cycles, as used in
subsequent analyses. For comparison, the dotted line corresponds to a traditional optimization tolerance of
0.01%, as typically used by mathematical programming solvers as a termination criterion.
SCD and IQP are general optimization approaches, intended to serve as strawman comparisons to understand
solution quality, while SA, SVMC, and PT-ICM reflect high-performance classical competitors, which provide
different tradeoffs in run time and solution quality. Details of these methods and others that were considered
are discussed in Appendix B. All of these classical optimization algorithms were executed on a system with
two Intel Xeon E5-2695 v4 processors, each with 18 cores at 2.10 GHz, and 125 GB of memory. The
parameterizations used by each algorithm in this work are also detailed in Appendix B.
For the QA hardware comparison, we use the Advantage system4.1 QPU accessed through D-Wave
Systems’ LEAP cloud platform. The largest system we consider features |N | = 5,387 discrete variables
and |EH|= 25,324 quadratic coefficients in the Pegasus topology. Solving a hardware-native optimization
problem on this platform consists of (i) programming an Ising model, (ii) repeating the annealing and read-
out process a number of times, and (iii) returning the highest quality solution found over all replicates. In
this analysis, we hold the annealing time constant at 62.5µs, which is justified in Appendix C. The number
of anneal-read cycles are varied between 10 and 5,120 to produce different total run times. We also leverage
the spin reversal transforms feature, provided by the LEAP platform, after every 100 anneal-read cycles to
mitigate the undesirable impacts of the aforementioned integrated control errors. For each Ising instance,
this protocol typically requires less than two seconds of QPU compute time and less than 10 seconds of total
wall-clock time.
3.1 A Characteristic Example
Here, we present an evaluation of the above optimization techniques on a characteristic problem instance
of the largest CBFM-P Ising models that we considered on the Advantage system4.1 QPU, with 5,387
variables.1For each solution technique, parameters that control the execution time of the algorithm (e.g.,
the number of sweeps in SA or the wall-clock time limit of the IQP method) were varied to understand their
effects on solution quality. These parameters are detailed in Appendix B. All other parameters remained
1An evaluation over 50 CBFM-P instances in Appendix D indicates this example is not an outlier.
5
摘要：

OntheEmergingPotentialofQuantumAnnealingHardwareforCombinatorialOptimizationByronTasse LosAlamosNationalLaboratory,LosAlamos,NM87545TameemAlbashUniversityofNewMexico,Albuquerque,NM87131ZacharyMorrell,MarcVu ray,AndreyY.Lokhov,SidhantMisra,CarletonCo rin*LosAlamosNationalLaboratory,LosAlamos,NM87545A...

展开>> 收起<<
On the Emerging Potential of Quantum Annealing Hardware for Combinatorial Optimization Byron Tasse.pdf

共25页,预览5页

还剩页未读， 继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

相关推荐

更多
立即下载
分类：图书资源 价格：10玖币 属性：25 页 大小：707.45KB 格式：PDF 时间：2025-05-02

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

人际关系 动力学连接体 力的合成 配电装置 高考理综 全宋诗作者索引 公务员考试
/ 25
评分 收藏
分享
立即下载
客服
关注