Readiness of Quantum Optimization Machines for Industrial Applications

There have been multiple attempts to demonstrate that quantum annealing and, in particular, quantum annealing on quantum-annealing machines, has the potential to outperform current classical optimization algorithms implemented on CMOS technologies. The benchmarking of these devices has been controversial. Initially, random spin-glass problems were used, however, these were quickly shown to be not well suited to detect any quantum speedup. Subsequently, benchmarking shifted to carefully crafted synthetic problems designed to highlight the quantum nature of the hardware while (often) ensuring that classical optimization techniques do not perform well on them. Even worse, to date a true sign of improved scaling with the number of problem variables remains elusive when compared to classical optimization techniques. Here, we analyze the readiness of quantum-annealing machines for real-world application problems. These are typically not random and have an underlying structure that is hard to capture in synthetic benchmarks, thus posing unexpected challenges for optimization techniques, both classical and quantum alike. We present a comprehensive computational scaling analysis of fault diagnosis in digital circuits, considering architectures beyond D-Wave quantum annealers. We find that the instances generated from real data in multiplier circuits are harder than other representative random spin-glass benchmarks with a comparable number of variables. Although our results show that transverse-field quantum annealing is outperformed by state-of-the-art classical optimization algorithms, these benchmark instances are hard and small in the size of the input, therefore representing the first industrial application ideally suited for testing near-term quantum annealers and other quantum algorithmic strategies for optimization problems.

Figure 1

Multiplier circuits used to generate our CCFD benchmark instances. In this example, the multiplication of two numbers represented as $k$-digit binary numbers, $a_1{a}_2\cdots a_k$ and $b_1{b}_2\cdots b_k$, is shown, resulting in a product output of length $2k$, corresponding to $p_1{p}_2\cdots p_{2k}$. HA and FA denote half-adder and full-adder circuit modules, respectively.

Figure 2

Example of a model-based fault diagnosis in combinational circuits (CCFD) on a small full adder circuit. In this work, the CCFD optimization problem consists in finding the smallest set of Boolean gate outputs that, when stuck-at-one, match an input-output observation vector. This setting where one restricts the expected fault behavior of the gates is known as the strong-fault model (see, for example, Ref. [31]). Although, in principle, each gate can have a characteristic fault mode, without loss of generality, we adopt stuck-at-one as the fault mode for all gates. Generalizations to other common fault modes and multiple fault modes per gate are detailed in Appendix pp3. In this example, the flagged xor gate is faulty, because its nominal behavior should yield an output equal to zero. The diagnosis explains the input $\{i_1=0,i_2=0,c_i=0\}$ and the apparently anomalous output $\{c_0=0,\mathrm{\Sigma }=1\}$.

Figure 3

Generation of benchmarks driven with a real-world scenarios’ flowchart. The first challenge consists in finding an efficient translation of the natural description of the optimization problem into a pseudo-Boolean function [panel (a)], $H_P({\mathbf{s}}_P)$, with domain ${\mathbf{s}}_P\in \{+1,-1{\}}^{N_P}$ and co-domain in $\mathbb{R}$. The resulting PUBO problem consists in finding assignments ${\mathbf{s}}_P^{\ast }$, which minimize the quartic-degree polynomial $H_P({\mathbf{s}}_P)$ [panel (b)]. This specific degree, known as the locality of the Hamiltonian (here, 4-local), arises from the effective local interactions between gates with two input variables $x_{i,1}$ and $x_{i,2}$, the wire output $z_i$, and the health variable, $f_i$, associated to each gate. By adding ancilla qubits, a, the quartic (4-local) $s_i{s}_j{s}_k{s}_l$ and cubic (3-local) $s_i{s}_j{s}_k$ terms can be reduced to an effective 2-local Hamiltonian defining an effective QUBO version of the problem instance [panel (d)]. Finally, minor embedding can be used to embed the QUBO into the physical hardware—in this case the chimera structure (see Fig. 7) of the D-Wave quantum annealers [panel (c)]. The cost of the embedding is an additional overhead in the number of qubits. While the “propositional logic” panel contains the description of the full-adder circuit in Fig. 2, the remaining are realistic representations of one of the smallest instances from our multiplier circuit with $23$, $33$, and $72$ qubits (or spin variables), for its PUBO, QUBO, and DW2X representation, respectively. In this work, we assess the impact on the performance of each of these representations and also perform experiments on the DW2X. Steps 1–4 denote some of the desiderata for an application to be a potential candidate for benchmarking the next generation of quantum annealers. Note that while the D-Wave device requires the embedding of a QUBO. However, future hardware implementations might include $k$-local interactions with $k>2$. Therefore, we perform the classical simulations both in the QUBO and PUBO representations to compare both approaches.

Figure 4

Hardness comparison of the chimera representation of the CCFD instances with other representative random spin-glass problems from the literature. (a) For consistency, all the time to solutions ($T_{\mathrm{tts}}$) in $\mu \mathrm{s}$ are obtained with PTICM with the same single-core processors. (b) Note the steeper scaling [larger value for $b$ from a fit of the $T_{\mathrm{tts}}$ to $T_{\mathrm{tts}}\sim \exp (b\sqrt{N})$] for the CCFD problems compared to the other classes of random spin-glass benchmarks. Data points correspond to the median values extracted from a bootstrapping statistical analysis from $100$ instances per problem size, with error bars indicating the $90$% confidence intervals (CIs). The different instance classes are described in the main text.

Figure 5

Scaling analysis from (a) physics and (b) application-centric perspectives. The $T_{\mathrm{tts}}$ is plotted as a function of $\sqrt{N}$, with $N$ the number of spin variables in each of the problem representations [PUBO (P), QUBO (Q), or chimera (C)]. Panel (b) corresponds to $\sqrt{N_{\mathrm{gates}}}$, with $N_{\mathrm{gates}}$ the number of gates regardless if we are considering symmetric multipliers, mult[$n$-$n$] as in Fig. 1, or asymmetric ones (mult[$n$-$m$]). The legend for the data sets depicted in (a) is shared with (b), with SAT-based results only appearing in (b). SQA/C runs are performed with an optimized linear schedule, as well as the DW2X schedule, marked with “LS” and “DWS” subscripts, respectively, (details in Appendix pp4).

Figure 6

Asymptotic scaling analysis. The asymptotic scaling exponent $b_{\mathrm{app}}$ refers to the multiplier representation, whereas $b_{\mathrm{phys}}$ refers to the physical representation of the problem. Data points correspond to the median values extracted from a bootstrapping statistical analysis from 100 instances per problem size, with error bars indicating the 90% CIs.

Figure 7

Device architecture and qubit connectivity. The array of superconducting quantum bits is arranged in $12\times 12$ unit cells that consist of eight quantum bits each. Within a unit cell, each of the four qubits on the left-hand partition (LHP) connects to all four qubits on the right-hand partition (RHP), and vice versa. A qubit in the LHP (RHP) also connects to the corresponding qubit in the LHP (RHP) of the units cells above and below (to the left and right of) it. Edges between qubits represent couplers with programmable coupling strengths. We show only the 1097 functional qubits out of the 1152 qubit array.

Figure 8

(a) Details for the different annealing schedules used in this work. Panels (b) and (c) show a comparison of the DW2X experimental results and SQA simulations of hypothetical QA devices with a DW2X-like [SQA(q)_DWS] and with a linear annealing schedule [SQA(q)_LS]. Data points correspond to the median values extracted from a bootstrapping analysis from $100$ instances per problem size, with error bars indicating the 90% CIs.

Figure 9

Qubit resources for each of the problem representation [(a) PUBO, (b) QUBO, and (c) chimera (DW2X)] considered in our benchmarking study of the CCFD instances. Data points correspond to the median values extracted from a bootstrapping statistical analysis from $100$ instances per problem size, with error bars indicating the 90% CIs.

Figure 10

Comparison of CCFD-based benchmark problems against other random spin-glass benchmark classes, at different percentiles. (a) 25th, (b) 50th, (c) 60th, and (d) 75th percentile. Data points correspond to the specific percentile value extracted from a bootstrapping statistical analysis from $100$ instances per problem size, with error bars indicating the 90% CIs.

Figure 11

Scaling analysis from the application-centric perspective at different percentile levels. (a) 25th, (b) 50th, (c) 60th, and (d) 75th percentile. Data points correspond to the specific percentile value extracted from a bootstrapping statistical analysis from $100$ instances per problem size, with error bars indicating the 90% CIs.

Figure 12

Scaling analysis from the physics perspective at different percentile levels. (a) 25th, (b) 50th, (c) 60th, and (d) 75th percentile. Data points correspond to the specific percentile value extracted from a bootstrapping statistical analysis from $100$ instances per problem size, with error bars indicating the 90% CIs.