Quantum-Assisted Greedy Algorithms PDF

Preview

Summary

Quantum-Assisted Greedy Algorithms Ramin Ayanzadeh , Milton Halem , John Dorband and Tim Finin Department of Computer Science and Electrical Engineering University of Maryland, Baltimore County, Baltimore, MD 21250, United States {ayanzadeh, halem, dorband, finin}@umbc.edu arXiv:1912.02362v3 [quant-...

Description

Quantum-Assisted Greedy Algorithms

arXiv:1912.02362v3 [quant-ph] 4 Feb 2020

Ramin Ayanzadeh , Milton Halem , John Dorband and Tim Finin Department of Computer Science and Electrical Engineering University of Maryland, Baltimore County, Baltimore, MD 21250, United States {ayanzadeh, halem, dorband, finin}@umbc.edu

Abstract We show how to leverage quantum annealers to better select candidates in greedy algorithms. Unlike conventional greedy algorithms that employ problem-specific heuristics for making locally optimal choices at each stage, we use quantum annealers that sample from the ground state(s) of a problem-dependent Ising Hamiltonians at cryogenic temperatures and use retrieved samples to estimate the probability distribution of problem variables. More specifically, we look at each spin of the Ising model as a random variable and contract all problem variables whose corresponding uncertainties are negligible. Our empirical results, on a D-Wave 2000Q quantum processor, revealed that the proposed quantum-assisted greedy algorithm (QAGA) can find notably better solutions (i.e., samples with lower energy value), compared to the state-of-the-art techniques in the realm of quantum annealing.

1

Introduction

Quantum artificial intelligence (QAI) is an emerging field that aims to apply quantum computers for addressing challenging problems in artificial intelligence (AI) [Lamata, 2017; Biamonte et al., 2017; Dunjko and Briegel, 2018] and use AI to advance quantum information processing [King et al., 2019; Ayanzadeh et al., 2020]. Quantum annealing is a meta-heuristic that addresses combinatorial optimization problems (i.e., discrete optimization problems)—which are intractable in the realm of classical computing—by taking advantage of quantum mechanical fluctuations. Quantum annealers are a physical realization of the quantum annealing process that draws samples from the ground state(s) of a given Ising Hamiltonian at cryogenic temperatures (i.e., near-zero Kelvin) in near-constant time [Finnila et al., 1994; Kadowaki and Nishimori, 1998; Ohzeki and Nishimori, 2011; Nishimori and Takada, 2017]. The quantum processing unit (QPU), by D-Wave Systems, is a programmable quantum annealer that samples from the ground state(s) of a given Ising Hamiltonian at cryogenic temperatures [Johnson et al., 2011]. From a problem-solving

point of view, the D-Wave quantum annealers receive coefficients of an Ising Hamiltonian as an executable quantum machine instruction (QMI), here h and J, and return the ground state of the following quadratic energy function: EIsing (z) =

N X i=1

h i zi +

N N X X

Jij zi zj ,

(1)

i=1 j=i+1

where N denotes the number of quantum bits (qubits). In this representation, zi ∈ {−1, +1}. One can apply a linear transform to map Eq. (1) to its equivalent quadratic unconstraint binary optimization (QUBO) form, and vice versa, as follows: N X EQUBO (x) = xi Qij xj , (2) i≤j

N

where x ∈ {0, 1} and i, j ∈ {1, 2, · · · , N }. In this representation, Q includes both linear biases and quadratic couplers—analogous to h and J in Eq. (1), respectively. Unlike conventional computing machines (namely classical and gate model quantum computers) that have a rich set of machine instructions, quantum annealers are singleinstruction computing machines that can only minimize Eq. (1) or (2). One can reduce any problem of class NP to an NP-complete problem in polynomial-time [Garey and Johnson, 2002; Ayanzadeh et al., 2019a]; thus, we can employ quantum annealers to address (significant) real-world problems that are intractable in the realm of classical computing. As an illustration, we can employ the quantum annealers to address the original problem of binary compressive sensing (i.e., the ℓ0 -norm sparse recovery) [Ayanzadeh et al., 2019b]. Similarly, we can represent the problem of nonnegative binary matrix factorization as finding the global minimum of (2) [O’Malley et al., 2018]. In the realm of quantum artificial intelligence and quantum machine learning, the D-Wave quantum annealer has been shown to address several problems including, but not limited to: planning [Rieffel et al., 2015], scheduling [Venturelli et al., 2015; Tran et al., 2016], constraint satisfaction problems (CSP) [Bian et al., 2016], and training deep neural networks [Adachi and Henderson, 2015]. Moreover, the D-Wave quantum annealer has also demonstrated a capable performance in solving discrete optimization problems [Bian et al., 2014]. In

addition to the optimization aspect of the quantum annealers, one can employ the D-Wave QPU to sample from highdimensional probability distributions, which has many applications in statistics, signal processing, artificial intelligence and machine learning [Biswas et al., 2017; Adachi and Henderson, 2015]. We can form an Ising Hamiltonian whose ground state represents the optimum solution of any given problem; however, in practice, executing the corresponding QMI on a physical quantum annealer does not guarantee to achieve the global optimum [Ayanzadeh et al., 2020]. Current generations of the D-Wave quantum processors, as an example, have some technological barriers—including, but not limited to, sparse connectivity between qubits [Cai et al., 2014], confined annealing schedule [Nishimori and Takada, 2017], coefficients’ range and precision limitations [Pudenz et al., 2015; Dorband, 2018a], noise and decoherence [Deng et al., 2013; Gardas et al., 2018; Gardas and Deffner, 2018]—that lower the quality of results (i.e., the energy value of the drawn samples is higher than the energy value of the ground state). Recent studies have demonstrated that applying preprocessing techniques such as gauge transforms, can reduce the impact of analog errors [Pelofske et al., 2019]. Such preprocessing techniques, however, are trivial because they do not alter the landscape of the Ising Hamiltonian. In addition, performing post-processing heuristics, namely the multi-qubit correction (MQC), can result in finding notably better solutions (i.e., samples with lower energy value) [Dorband, 2018b]. Applying MQC, nevertheless, cannot guarantee that we can find the global minimum. It is worth highlighting that MQC performs well only on sparse problems and many real-world applications can have non-sparse representations. Greedy algorithms are a problem-solving paradigm where we make locally optimal choices at each stage and expect that they yield a globally optimum solution. Although most greedy algorithms fail to achieve the global optimum, in many applications they are the best choice due to their efficiency [DeVore and Temlyakov, 1996]. As an example, greedy algorithms are widely used in sparse recovery applications, at the cost of lower recovery accuracy (compared to convex optimization methods in compressive sensing) [Mousavi et al., 2019]. Note that greedy algorithms can find globally optimum solutions if the problem exhibits optimal substructure. This study introduces a novel hybrid approach, called quantum-assisted greedy algorithms (QAGA), that leverages quantum annealers to better select candidates in each stage of the greedy algorithms. At each stage, QAGA employs a quantum annealer to provide samples from the ground state of the problem and use these retrieved samples to estimate the probability distribution of problem variables. After fixing variables with negligible uncertainties, QAGA proceeds to the next stage where the quantum annealer will solve a smaller problem with sparser couplings. Our experimental results, using a D-Wave 2000Q quantum processor, showed that QAGA can find samples with remarkably lower energy values, compared to the best-known enhancements in the realm of quantum annealing.

2

Method

Let H be an Ising Hamiltonian as follows: H :=

N X i=1

h i zi +

N N X X

Jij zi zj ,

(3)

i=1 j=i+1

where h and J represent linear and quadratic coefficients, respectively. Also, let z∗ represents the ground state of H as follows: z∗ = arg min H. (4) z

˜ such that: In this study, we aim to find z |Hz∗ − Hz˜ | → 0.

(5)

In other words, our objective is to find a sample whose corresponding Ising energy value, shown in Eq. (1), approaches the energy value of the ground state of the given Ising Hamiltonian. QAGA starts with: ˜ = {}, z and,

H0 = H. At each iteration, QAGA uses a quantum annealer to draw n samples from the ground state of Ht . To solve problem (4) on a D-Wave quantum processor, as an illustration, one needs to embed Ht to the working graph of the D-Wave quantum annealers(i.e., the Chimera topology for the current generation), and normalize h and J to [−2, +2] and [−1, +1], respectively [Ayanzadeh et al., 2020]. Let Z denotes the set of all samples, drawn by a quantum annealer from the ground state of Ht , as follows: Z = {z1 , z2 , · · · , zn }, where zj ∈ {−1, +1}N . All samples (i.e., zj for j = 1, 2, . . . , n) contain a measurement for every qubit. Hence, we can look at each problem variable (zi , for i = 1, 2, · · · , N ) as a random variable with Bernoulli distribution that takes its value from {−1, +1}. Note that in this representation, the value -1 in (1) is analogous to 0 in (2); therefore, we can extend all analysis to QUBO form and employ QAGA in binary settings. After retrieving the sample set Z, we estimate the uncertainty of every problem variable (zi ) as follows: Pn | j=1 zji | . (6) u(zi ) = 1 − n For any variable zi of Ht that: u(zi ) ≤ θ,

(7)

where θ ∈ [0, 0.5) specifies the threshold parameter, we fix the value of optimum solution as follows:   n X ˜i = sgn  (8) zji . z j=1

Since θ < 0.5, z˜i is guaranteed to take its value from {−1, +1}. After fixing the value of zi :

• we remove hi from Ht+1 ;

3

˜i Jij (or z ˜i Jji ) to hj , for j = • we add the value of z 1, 2, . . . , N and i 6= j;

This study proposes a hybrid approach, called quantumassisted greedy algorithms (QAGA), for improving the performance of physical quantum annealers in finding the global minimum (i.e., the ground state) of Ising Hamiltonians, shown in (1). It is important to emphasize that, therefore, our objective was not to introduce a new greedy algorithm that can address combinatorial optimization problems nor to guarantee that the quantum annealers will find the global minimum of the given Ising Hamiltonian. The current generation of the D-Wave quantum annealers (the Chimera architecture) includes more than 2,000 qubits and about 6,000 couplers, while the next generation (the Advantage architecture) will include more than 5,000 qubits and about 40,000 couplers [Boothby et al., 2019]. Since coupling every qubit to every other qubit is infeasible in practice, the D-Wave QPUs have a sparse connectivity architecture. One can entangle multiple physical qubits to form a virtual qubit with higher connectivity at the expense of a significant reduction in the number of virtual qubits relative to the actual number of available physical qubits. As an example, 2048 physical qubits on the Chimera topology are equivalent to 64 fully-connected virtual qubits. Benchmarking optimization techniques with computationally hard problems that we know the optimum solution is a common practice. However, recent studies have demonstrated that applying MQC [Dorband, 2018b] on the drawn samples by the D-Wave quantum processors always finds the optimum solution of such problems [Dorband, 2019]. Note that the current generation of the D-Wave quantum annealers is limited to represent a clique of size at most 63 and MQC may fail to find the global optimum of benchmark problems when we notably increase the number of variables, which is beyond the capacity of the current quantum annealers. It is worth highlighting that MQC performs well only on sparse problems—when we reduce the sparsity of the problem, i.e., increasing the number of non-zero quadratic coefficients in Eq. (1)—performance of the MQC approaches to a local search heuristic like single-qubit correction (SQC). Generating random problems results in hard problems for benchmarking quantum annealers [King et al., 2019; Dorband, 2018a; Dorband, 2018b]. Hence, as a proof-ofconcept, we use randomly generated Ising Hamiltonians for evaluating the performance of the proposed method in this paper (QAGA) and compare it with MQC which is the bestknown post-quantum error correction for quantum annealers.

• we remove the coupler Jij (or Jji ) from Ht+1 . QAGA terminates when Ht ≡ Ht+1 . If QAGA ended without fixing all problem variables, we apply the MQC method [Dorband, 2018b] on the samples from the last stage of the QAGA and assign values for the remaining problem variables. Contracting variables with negligible uncertainties results in a new Ising Hamiltonian (Ht+1 ) which is smaller and sparser, compared to Ht . Hence, at each iteration of QAGA, the remaining Ising Hamiltonian becomes easier to be solved with physical quantum annealers. Note that contracting variables reduces the number of qubits (N ) correspondingly. Algorithm 1 illustrates the QAGA process. Finally, we can ap˜ to increase the probability of ply a classical local search on z finding the ground state. Input: H, θ ˜ Output: z ˜ ← {} z Ht ← H Ht+1 ← {} while Ht+1 6= Ht do Ht+1 ← Ht Z ← {z1 , z2 , · · · , zn } = arg minz Ht for i ← 0 to N do if u(zi ) ≤ θ then  P n j ˜i ← sgn z j=1 zi

Hht+1 ← {} i for j ← 0 to N do if Jij ∈ Ht+1 then ˜i Hht+1 ← Hht+1 + Jij z j j ← {} HJt+1 ij end if Jji ∈ Ht+1 then ˜i Hht+1 ← Hht+1 + Jji z j j t+1 HJji ← {} end end end end end if |˜ z| < N then ˆ ← MQC(Z) z ˜←z ˆ∪z ˜ z end ˜ return z Algorithm 1: Quantum-assisted greedy algorithm (QAGA) for minimizing an Ising Hamiltonian

Results

3.1 Experiment A For every problem in this experiment, we generated a random graph of size 50 with a specified sparsity rate (s ∈ {0.05, 0.25, 0.5, 0.75, 1.0}). More specifically, we randomly selected edges from a complete graph with N = 50 nodes where the sparsity rate s denoted the probability of selecting edges. Afterward, we set values of the corresponding biases and couplers randomly. We generated three different types of benchmark problems: (a) we picked values of biases and couplers randomly from {−1, +1} (binary coefficients); (b) we used random numbers in [−1, +1] with uniform distribution to assign values of h and J (uniform coefficients); and

(c) coefficients’ values were drawn randomly from a standard normal distribution (normal coefficients). Our objective in this study was to improve the quality of results (i.e., finding samples with lower energy value), attained by the D-Wave quantum annealers. Hence, as our ground-truth, we compared the performance of QAGA with two different settings. Since applying spin-reversaltransforms (a.k.a. gauge transforms) has demonstrated to address the impact of analog errors of the physical quantum annealers [Pelofske et al., 2019], as our first groundtruth method, we compared QAGA with quantum annealing with 10 spin-reversal transforms (here, denoted by QA). We also enabled the inter-sample delay to reduce the sample-tosample correlations in successive reads/measurements, albeit longer execution time. As our second ground-truth method, we applied MQC on samples from QA—quantum annealing with 10 spin-reversal-transforms and enabled inter-sample delay—denoted by MQC. For each QMI, we requested 1,000 samples for all methods. The uncertainty threshold in QAGA was θ = 0.0—i.e., all spins must have the same value so QAGA can fix them for the next stage. We obtained this threshold empirically via evaluating the performance of QAGA on a small problem set. In the next experiment, we have studied the impact of θ on the performance of QAGA. Since randomly generated problems are not compatible with the working graph of the current D-Wave quantum processors, we used the minor-embedding heuristic [Cai et al., 2014] for embedding the arbitrary random graphs to the Chimera topology of the D-Wave 2000Q quantum processors. In addition, QAGA iteratively contracts variables whose uncertainties are negligible; thus, the Ising Hamiltonian in QAGA has a dynamic structure, in terms of the number of qubits and their connectivity. In this sense, at each stage, QAGA needs to embed the remaining Ising Hamiltonian to an executable QMI on the target quantum annealer. Figure 1 illustrates the performance comparisons between QAGA and QA in minimizing Ising Hamiltonians with binary, uniform and normal coefficients. For each case, we generated 100 random problems with the corresponding (uniform or normal) distributions. In this experiment, all randomly generated Ising Hamiltonians had 50 spin variables (N = 50). For each sparsity rate, the corresponding column illustrates the number of times that QA has found a better sample (compared to QAGA), number of times that QA and QAGA demonstrated same performance (i.e., best samples from both methods had identical Ising energies), and number of times that QAGA has outperformed QA. In the same manner, Fig. 2 illustrates the performance comparisons between QAGA and MQC in minimizing the same 100 randomly generated Ising Hamiltonians with binary, uniform and normal coefficients. Note that all arrangements in this experiment (e.g., number of variables, sparsity rate, number of spin-reversal-transforms, etc.) were identical to the previous experiment. Similar to Fig. 1, each column in Fig. 2 represents the number of times that MQC has found a sample with lower energy, MQC and QAGA had similar performance, and QAGA resulted in a sample with lower Ising energy value.

3.2 Experiment B In this experiment, we aim to study the impact of the threshold parameter on the performance of QAGA. To this end, we measured the average number of stages (iterations) that QAGA takes to be converged. Table 1 illustrates the average number of iterations that QAGA takes to solve 100 random benchmark problems with N = 50 variables and normal coefficients. Since the randomly generated Ising Hamiltonians had arbitrary graph structures, we used the minor-embedding heuristic [Cai et al., 2014] for mapping them to executable QMIs on the D-Wave quantum annealers. Table 1: Average number of iterations for QAGA in solving 100 random benchmark problems with different thresholds

θ 0.25 0.15 0.05 0.00

0.05 3.25 3.60 4.10 5.50

sparsity rate (s) 0.25 0.50 0.75 2.80 3.15 3.40 3.40 3.35 3.45 4.45 4.30 3.20 6.20 2.10 2.05

1.00 3.30 3.65 4.05 2.30

Table 1 reveals that for Chimera like problems (i.e., sparse problems where s = 0, 05 or 0.25), when θ → 0, QAGA takes more iterations (i.e., slower convergence). On the other side, for dense Ising Hamiltonians, where s → 1 (i.e., clique like problems), when θ → 0, QAGA converges quickly—the maximum number of iterations appears on θ ∼ 0.1.

4

Conclusion

Quantum annealing is a meta-heuristic for addressing discrete optimization problems in near-constant time; however, owing to some technological barriers, physical quantum annealers (like the D-Wave quantum processors) generally result in excited states (i.e., close to global minimum), rather than converging to the ground state (i.e., global minimum). In other words, quantum annealers can find very high-quality solutions for combinatorial optimization problems in a fraction of a second; nevertheless, they generally fail to get to the ground state of the given Ising Hamiltonians. In this study, we introduced a novel hybrid approach, called quantum-assisted greedy algorithms (QAGA), that employs the quantum annealers for making globally optimum choices at each stage of a greedy algorithm. To this end, we looked at the quantum annealers as a physical process that naturally draws samples from the ground state of Ising Hamiltonians (i.e., a problem-dependent Boltzmann distribution) at cryogenic temperatures. From a problem-solving point-of-vie...