1 Introduction
Advantage
system [4], having a 5000+ QPU featuring a Pegasus topology with increased connectivity compared to the one of its predecessor, a 2000+ qubit QPU with a Chimera topology in the DW2000Q
system [5]. As the complexity of commercially available quantum annealers increases, so does the need for methods to systematically benchmark these systems, using problems which do not become obsolete as quantum annealers grow in size. Therefore, we need problems which are flexibly scalable to an arbitrarily large number of qubits.Advantage
system against the DW2000Q
system, as well as the recently released Hybrid Solver Service hybrid
_binary
_quadratic
_model
_version2
(HSSv2
) against its former version hybrid
_binary
_quadratic
_model
_version1
(HSSv1
) and other classical software solvers.DW2000Q
and its successor system Advantage
using garden optimization problems of up to 100 variables reveals that while there were no significant performance differences solving smaller problems, Advantage
is capable of embedding and solving much larger problems than DW2000Q
(see also the results in Ref. [10]). Additionally, we compare the performance of D-Wave’s hybrid solvers and some software solvers using problems of up to 12000 variables. We find that HSSv1
returns better results than its successor HSSv2
within the same execution time, but is unable to process the biggest problem instances, and QBSolv
requires much longer execution times than both hybrid solvers but can return better results than HSSv2
for the biggest problems.2 The garden optimization problem
2.1 Formulation of the cost function
2.2 Formulation of the constraints
2.3 Relation to the quadratic assignment problem
2.4 QUBO formulation of the problem
3 Quantum annealing
3.1 D-Wave QPUs
DW2000Q
since January 2017. Connecting the over 2000 qubits, this system features over 6000 couplers arranged in a Chimera graph of size 16, also known as \(C_{16}\) [3]. In September 2020, a new system called Advantage
was released, which features over 5000 qubits and over 35000 couplers arranged in a Pegasus topology of size 16 (\(P_{16}\)) [5]. Besides the significant increase in the number of qubits, the most noteworthy improvement of the new generation was the qubit connectivity increasing from 6 to 15, which should allow the user to solve problems with more variables and denser connectivity [4]. The characteristic form of the Chimera and the Pegasus graph is shown in Fig. 2a and b, respectively.DW2000Q
and the Pegasus architecture on the new D-Wave Advantage
. The Pegasus architecture should allow for equally or more compact embeddings than Chimera for any given problem. Also, the increased number of qubits would allow us to run bigger problems that do not fit on the DW2000Q
chip.3.2 D-Wave hybrid solvers
DW2000Q
and Advantage
, D-Wave Systems offers access to QUBO solvers following a hybrid approach. As we saw in the previous section, the current QPUs have a limited number of qubits which might not be enough to solve problems at a real-world scale. Hybrid solvers have been designed to overcome this limitation by classically partitioning the problem into sub-problems that are small enough to be solved on a QPU. The version 1 solver HSSv1
was released in February 2020, using DW2000Q
as the hardware backend to solve the sub-problems and being able to run problems of up to 10,000 variables. In September 2020, parallel to the release of the Advantage
QPU, the version 2 solver HSSv2
was released. The new hybrid solver relied on Advantage
instead and was able to solve sparsely connected problems of up to one million variables or fully connected problems of up to 20,000 variables [29].HSSv1
and HSSv2
, we have included in this study two purely classical QUBO solvers provided by the D-Wave Ocean SDK: TabuSampler
, an MST2 multistart search algorithm [30], and QBSolv
[31], a partitioning algorithm which solves the sub-problems using TabuSampler
as backend. We thus have two different hybrid classical/quantum partitioning solvers, a classical non-partitioning solver, and a classical partitioning solver.4 Results
Advantage
and DW2000Q
), as well as for the hybrid and software solvers (HSSv1
, HSSv2
, TabuSampler
, and QBSolv
) in two separate subsections. For the hardware samplers, we created four problem instances and performed a chain strength scan for several embeddings of each problem. Subsequently, we chose the most successful embedding together with its optimal RCS value to perform an annealing time scan. These scans were used for comparing the performance of the hardware samplers. For the hybrid and software solvers, we created 324 problem instances which we submitted to each solver. The Python 3 code used to generate these problem instances is available online as a Jupyter Notebook at Ref. [12]. Here, we present the energy of the returned solutions as well as the execution times required to reach them.4.1 Hardware samplers
DW2000Q
and Advantage
(see Sect. 3.1), we define a successful solution as one which fulfils all the constraints in Eqs. (5)–(7) regardless of the quality of the placement of the plants in the garden (i.e. regardless of the contribution of the cost function Eq. (4) to the solution energy). We remark that there is no tolerance in the success of a solution, as we only count solutions as successful if they satisfy all constraints. The success rate is then defined as the ratio of successful solutions to the total number of samples produced. Defining the success rate in this way allows us to assess the quality of the solutions provided by a batch of samples in this scenario, where we do not know whether we have found the ground state of the problem unless the energy of the sample is zero. An alternative metric which could be used to measure the success of a given embedded problem is the energy of the best sample, i.e. the lowest energy (as considered in Sect. 4.2 for comparing hybrid and classical solvers). This metric has the advantage over the success rate of taking into account not only the satisfaction of the constraints but also the quality of the placement of plants in the garden. However, for the hardware samplers evaluated here, the lowest energy turned out not to be a sensitive enough metric to tune the RCS and AT. The reason for this is that among the valid solutions, the different samplers and embeddings often returned identical lowest energy results (data not shown).DW2000Q
and Advantage
systems at solving QUBO problems. Given the problem size limitations of the studied systems, the problem suite consists of four problems of 16, 36, 64, and 100 variables. We ensure that the created problems are satisfiable by setting n to an even number (here \(n \in \{4,6,8,10\}\)) and sampling without replacement n/2 times from each of both the sets of big plants (\(\{j : 0<=j<=t-1\) and \(s_j=0\}\)) and small plants (\(\{j : 0<=j<=t-1\) and \(s_j=1\}\)) to obtain the list of plants to place in the garden. Sampling without replacement generates problems where there is at most one plant specimen of each species, so the number of variables in these problems is equal to \(n^2\).DW2000Q
(a subset of the \(C_{16}\) graph) and Advantage
(a subset of the \(P_{16}\) graph) using the find_embedding
function of the minorminer
module included within the D-Wave Ocean SDK (see [5] for more information on the working graphs and [33] for information on the embedding algorithm used). These embeddings were successfully created for all problems except for the 100 variable problem on DW2000Q
, since it was too big to fit on the DW2000Q
chip. Therefore, for this problem, we only report results obtained on Advantage
.DW2000Q
embeddings were mapped onto the Advantage graph (see Fig. 2b for a visualization of how the Chimera graph can be embedded onto the Pegasus graph, and by extension how a Chimera-embedded problem can be mapped onto a Pegasus graph). By this process, we obtain 10 new embeddings for each problem which could be used on the DW2000Q
system in addition to the two original sets of 10 embeddings. In what follows, we refer to these Chimera embeddings used on the Advantage
system as Advantage(Chimera) embeddings. Since the Advantage(Chimera) embeddings were not created specifically for Advantage
, the compatibility of these embeddings with the working graph of the Advantage
chip was checked prior to executing the problems, so that they could be replaced in the case that any of the involved qubits or couplers were not available.4.1.1 Chain strength scan
DW2000Q
, possibly due to properties of this particular system; otherwise, it would also be observable in the Advantage(Chimera) scans. For problems of up to 64 variables, for which Chimera embeddings were found, the performances of the DW2000Q
and Advantage
systems are comparable, whereas Advantage(Chimera) embeddings performed significantly worse. This difference in performance cannot be attributed to the embedding quality. Therefore, we conjecture that the additional unused couplers of the Pegasus architecture in the Advantage(Chimera)-embedded problems when compared to the DW2000Q
-embedded problems play a role in lowering the success rate. For the 100 variable problem, only Pegasus embeddings could be found, and although the success rates are small, this indicates that the Advantage
system is able to solve bigger problems due to its increased qubit number and connectivity. We also note that for the 36 variable problem, DW2000Q
seems to outperform Advantage
. This might be due to the fact that Chimera and Pegasus embeddings for small problems have similar chain lengths and the DW2000Q
embeddings could have less unused couplers connected to qubits involved in the embeddings.4.1.2 Annealing time scan
DW2000Q
embedding for each problem was the same as the best for Advantage(Chimera), although the optimal \(\mathrm {RCS}\) was slightly lower in the Advantage(Chimera) embedding for problems of 36 and 64 variables and the same for the 16-variable problem.
DW2000Q
and Advantage
allow the user to set the AT value between \(1\,{\mu }\mathrm s\) and \(2000\,{\mu }\mathrm s\). Therefore, the AT scan was performed using 20 values evenly spaced on a logarithmic scale in this range. All jobs in each scan produced \(10^4\) samples for the 16 and 36 variable problems, \(10^5\) samples for the 64 variable problem, and \(10^6\) samples for the 100 variable problem. The number of samples in the latter problems was increased to produce sufficient statistics given the small success rates.
Advantage
and Advantage(Chimera) against DW2000Q
, we see that increasing the AT tends to be more consistently effective on the Advantage
system. On DW2000Q
, however, the success rate is found to decrease again for larger AT (see the blue curves in Fig. 4). This may be an effect caused by the environment (see [34] for more information). It is possible that if the Advantage
system accepted AT values beyond \(2000 \,{\mu }\mathrm s\), we would observe similar behaviour, where the success rate decreases past some optimal AT value.4.2 Hybrid and software solvers
HSSv1
and HSSv2
against the classical software solvers TabuSampler
and QBSolv
(see Sect. 3.2 for details on these solvers). The hybrid solvers were executed online on D-Wave servers, and the classical solvers were executed on an Intel(R) Core(TM) i7-4770 CPU @ \(3.40\,\)GHz workstation with \(32\,\)GB of RAM. For this study, we generated increasingly bigger problems in an attempt to evaluate how the performance of the solvers behaves under increasing problem sizes. Each problem instance was created by fixing the number of pots n to an even number and sampling with replacement the sets of available small and big plant species n/2 times each, so as to ensure that as many small plants as big ones were to be placed in the garden. Here, we sample with replacement (as opposed to the problems created in Sect. 4.1) to allow for more than one plant specimen per species. Therefore, we create problems with more pots than unique species defined in the companions matrix \(C_{jj'}\) shown in Fig. 1. The biggest problem which could be created given the available memory on the used workstation was for \(n=684\) pots, with a total of 12312 variables. Note that the biggest problems are beyond the problem size limit of HSSv1
(10000 variables), but within the limit for HSSv2
(20000 variables, fully connected). Each of the 342 problems in this set was submitted to each of the studied solvers, so we can make a direct comparison of their performance. Here, rather than comparing the success rates as we did in the previous section, we compare the energy of the single sample returned by each of the solvers, as well as the execution times taken to return said sample.
4.2.1 Energies
TabuSampler
seems to perform significantly worse than the others. This is probably due to the fact that it is the only solver that does not partition the problem into separately solved sub-problems, but attempts to solve the complete problem at once. The energy results for this solver were at least three orders of magnitude larger than the rest for problems beyond 2500 variables. QBSolv
displays a rather predictable linear trend for increasing problem size in the studied range of problems. For problems below 5000 variables, HSSv2
, HSSv1
, and QBSolv
show very similar performance, with QBSolv
returning slightly worse results. Above 5000 variables, the differences become clearer, with HSSv1
outperforming all other solvers up until the 10000 variable barrier, after which no results are available for this solver. Surprisingly, as the problem size increases, HSSv2
seems to perform comparatively worse than QBSolv
and especially HSSv1
. Additionally, the spread of the energies returned by HSSv2
increases compared to that of the other solvers.
HSSv1
and HSSv2
for each problem is shown in Fig. 6. Here, we plot the energy of both HSSv1
and HSSv2
on the x- and y-axes, respectively, and use the colour dimension to represent the number of variables of each problem represented by a point. For problems of up to 2000 variables, there is no visible difference between the solvers. However, as problems increase beyond this number of variables, the gap in the energies returned by each solver increases in favour of HSSv1
. It should be noted that the results shown here should be interpreted exclusively within the scope of the studied garden optimization problems, and further evaluation involving different problem classes would be required to reach a general conclusion regarding the performance of these solvers.
4.2.2 Execution times
TabuSampler
is the fastest among all tested solvers, although as it is shown in Fig. 5, its returned energies were much worse than the others. HSSv1
and HSSv2
have identical execution times up to 10000 variables. Note that the minimum execution time for HSSv1
and HSSv2
is \(3\,\mathrm s\) independent of the problem size. Hence, the execution time is constant for these two solvers for the smaller problems. Among all solvers, QBSolv
is the slowest, with execution times at least one order magnitude larger than the hybrid solvers. Considering this together with the energy results shown in Fig. 5, one might conclude that HSSv1
is the most competitive among the tested solvers if the problem size does not exceed its limit of 10000 variables. For problems above this threshold, however, it is unclear whether the shorter running times and higher energies of HSSv2
should be preferred over the longer running times but closer to optimal solutions of QBSolv
.5 Conclusion
Advantage
and DW2000Q
, as well as hybrid and classical solvers HSSv1
, HSSv2
, TabuSampler
, and QBSolv
. To the authors’ knowledge, these have been the first benchmarking results of Advantage
and HSSv2
developed by researchers independent of D-Wave Systems. Nevertheless, we remark that before generalizing the results shown here, it would be good to verify the general trends by benchmarking these systems using other classes of problems. For similar studies, see [10, 35‐41].Advantage
system is capable of embedding and solving garden optimization problems of 100 variables, which is far beyond the reach of the previous generation of D-Wave systems, DW2000Q
. This is due to the increase in the number of qubits and couplers in the newer system. For the evaluated problems with less than 100 variables, we did not observe significant differences in the performance of both systems. The results for Advantage(Chimera), i.e. a Chimera embedding used on Advantage
(cf. Fig. 2), suggest that the additional couplers of Advantage
’s Pegasus architecture with respect to DW2000Q
’s Chimera architecture can negatively impact the success rate if these couplers are not used in the embedding. However, these additional couplers allow for equally and often more compact embeddings for a fixed problem, so they should be beneficial when solving embedded problems, especially when the problems have more variables or denser connectivity.HSSv1
is the most competitive among the tested solvers as long as the problem does not exceed 10000 variables, since it has the shortest execution times together with HSSv2
but returns lower energy results than the other solvers. Problems beyond 10000 variables cannot be submitted to HSSv1
. For the largest problems, it is unclear whether QBSolv
or HSSv2
performs best: QBSolv
has longer execution times but returns results with lower energies, whereas HSSv2
is faster, but the results returned have higher energies.HSSv1
with the generated set of problems, it would have been interesting to also include such results for HSSv2
, TabuSampler
, and QBSolv
. We leave the exploration of even larger problem instances to approach the size limits of HSSv2
for future work.