{'fraction_non_alphanumeric': 0.039490638975214126, 'fraction_numerical': 0.011748654589555067, 'mean_word_length': 4.729049066435085, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Quantum-Assisted Greedy Algorithms

We show how to leverage quantum annealers (QAs) 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 QAs that sample from the ground state of problem-dependent 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 demonstrate that the proposed quantum-assisted greedy algorithm (QAGA) scheme can find notably better solutions compared to the state-of-the-art techniques in the realm of quantum annealing


INTRODUCTION
Artificial intelligence (AI) is a disruptive technology that has transformed many industries. Quantum computing (QC) is a transformative computing phenomenon that promises to better address challenging problems that are intractable in the realm of classical computing. Quantum artificial intelligence (QAI) and quantum machine learning (QML) appear at the intersection of machine intelligence and QC, and aim to revolutionize application domains that are challenging for classical AI. Although promising, near-term quantum machines are susceptible to various sources of errors (such as decoherence and gate errors), and they do not include enough quantum bits (qubits) to accommodate quantum error correction policies. We are in the noisy intermediate-scale quantum (NISQ) era where we must perform computations in the presence of noise and infer the desirable output from erroneous outcomes [1,2].
There are several models for the physical realization of quantum computers such as gate/circuit model, adiabatic, and This research was supported by NASA grant (#NNH16ZDA001N-AIST 16-0091), NIH-NIGMS Initiative for Maximizing Student Development Grant (2 R25-GM55036), and a Google Lime scholarship. We thank the D-Wave Systems management team, namely Rene Copeland, for granting us access to the D-Wave 2000Q quantum annealer. measurement-based QCs. For the case of gate model QC, variational quantum approaches (a.k.a. classical-quantum hybrid schemes) are the leading candidate for demonstrating the supremacy of QAI/QML models. Conversely, the limited programmability of adiabatic quantum processors-i.e., adiabatic quantum computers and quantum annealers are singleinstruction (quantum) computing machines that can only sample from the ground state of a given Hamiltonian-casts doubt on their ability to outperform classical AI/ML models [3]. In this paper, we introduce a novel variational scheme for quantum annealers (QAs) and demonstrate that it can outperform QAs in finding the ground state of Ising Hamiltonians.
Greedy algorithms are a problem-solving paradigm that makes locally optimal choices at each stage and expects them to yield a globally optimum solution. Although most greedy algorithms fail to achieve the global optimum, they are often the best choice due to their efficiency [4]. 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 [5]. Note that greedy algorithms can find globally optimum solutions if the problem exhibits optimal substructure. We introduce a novel hybrid approach, called quantumassisted greedy algorithms (QAGA), that leverages QAs to better select candidates in each stage of a greedy algorithm. At each stage, QAGA employs a QA 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 QA will solve a smaller problem with sparser couplings. Our experimental results using a D-Wave 2000Q quantum processor show that QAGA can find samples with remarkably lower energy values compared to the best-known enhancements in the realm of quantum annealing.

QAGA: A HYBRID APPROACH
Quantum annealing is a meta-heuristic for addressing combinatorial (or discrete) optimization problems that are intractable in the realm of classical computing. Quantum annealers (QAs) are a physical realization of the quantum annealing process that can draw samples from the ground state of the given Hamiltonians at cryogenic temperatures. The quantum processing unit (QPU) by D-Wave Systems is a single-instruction quantum computing machinery that can only sample from the ground state of the following Ising Hamiltonian: (1) where N denotes the number of quantum bits (qubits), spin variables z ∈ {−1, +1} N , and h and J represent local fields and couplers, respectively [6,7,8].
To solve a problem using QAs, we must define coefficients of the Ising Hamiltonian-i.e., h and J-such that the ground state of the corresponding H represents a solution of the problem of interest [9]. However, physical QAs are susceptible to various error sources, and therefore executing a quantum machine instruction (QMI) on a physical QA is not guaranteed to achieve the ground state of the corresponding H [10]. Recent studies have shown that applying preprocessing and postprocessing policies can improve the fidelity of QAs. Nevertheless, such policies cannot bypass the technological barriers of physical QAs, and addressing hardware drawbacks can require device-level enhancements that may span generations of QAs [10].
We present the notion of quantum-assisted greedy algorithms (QAGA) to improve the fidelity of the near-term QAs. Algorithm 1 illustrates the QAGA process. Let z * be the ground state of H-i.e., z * = arg min z H. 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. More specifically, we aim to find z such that: |H z * − Hz| → 0.
QAGA starts withz = {} and H t=0 = H. At each iteration, QAGA uses a QA to draw n samples from the ground state of H t . Let Z denotes the set of all samples, drawn by a QA from the ground state of H t , as Z = {z 1 , z 2 , · · · , z n } where z j ∈ {−1, +1} N . Every sample z j contains a measurement for all qubits. Hence, we can look at each problem variable z i as a random variable with Bernoulli distribution that takes its value from {−1, +1}. After retrieving the sample set Z, we estimate the uncertainty of every problem variable z i as follows: For every variable z i of H t that u(z i ) ≤ θ, where θ ∈ [0, 0.5) specifies the threshold parameter, we fix the value of optimum solution as: since θ < 0.5,z i is guaranteed to take its value from {−1, +1}.
After fixing the value of z i , we: (a) remove h i from H t+1 ; (b) add the value ofz i J ij (orz i J ji ) to h j , for j = 1, 2, . . . , N and i = j; and (c) remove the coupler J ij (or J ji ) from H t+1 . QAGA terminates when H t ≡ H t+1 . If QAGA ends without fixing all problem variables, we apply the multi-qubit correction (MQC) method [10] on the samples from the last QAGA stage and assign values for the remaining problem variables.
Contracting variables with negligible uncertainties results in a new Ising Hamiltonian (H t+1 ), which is smaller and sparser compared to H t . Hence, at each iteration of QAGA, the remaining Ising Hamiltonian becomes easier to solve with physical QAs. Note that contracting variables reduces the number of qubits (N ) correspondingly. Finally, we can apply a classical local optimization heuristic, such as the singlequbit correction (SQC) method [10], to increase the probability of finding the ground state.

RESULTS
We use randomly generated Ising Hamiltonians for evaluating the performance of the proposed QAGA and compare it with MQC, which is the state-of-the-art technique in the realm of QA [10]. We employ three different types of benchmark problems: (a) coefficients drawn uniformly from {−1, +1} (binary coefficients); (b) coefficients drawn uniformly from [−1, +1] (uniform coefficients); and (c) coefficients drawn from the standard normal distribution (normal coefficients). For our evaluations, we use a D-Wave 2000Q QA. Since randomly generated problems are not compatible with the working graph of QAs, we use the minor-embedding heuristic [11] for embedding the arbitrary random graphs to the Chimera topology of the D-Wave 2000Q quantum processors. QAGA iteratively contracts variables whose uncertainties are negligible; thus, the Ising Hamiltonian in QAGA has a dynamic structure, and we need to apply the embedding in all iterations of QAGA. Thus, QAGA needs to embed the remaining Ising Hamiltonian to an executable QMI on the target QA.
We compare the performance of QAGA to QA with ten spin-reversal transforms and longer inter-sample delay (denoted by QA), which is a notably stronger baseline. As our second baseline, we apply MQC to the result of the first baseline (denoted by MQC). For each QMI, we request 1,000 samples for all methods.

Experiment A
For every problem in this experiment, we generate 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 select edges from a complete graph with N = 50 nodes where the sparsity rate s denotes the probability of selecting edges. We then set values of the corresponding biases and couplers randomly. The uncertainty threshold in QAGA is θ = 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 by evaluating the performance of QAGA on a small problem set. We study the sensitivity of QAGA to θ in the following experiment. Figure 1 illustrates the performance comparisons between QAGA and QA in minimizing Ising Hamiltonians with binary, uniform and normal coefficients. For each case, we generate 100 random problems. In this experiment, all randomly generated Ising Hamiltonians include 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), the number of times that QA and QAGA demonstrated the same performance (i.e., best samples from both methods had identical Ising energies), and the 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 bi-nary, 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 a lower Ising energy value.

Experiment B
In this experiment, we aim to study the impact of the threshold parameter on the performance of QAGA. To this end, we measure the average number of stages (iterations) that QAGA takes to converge. Table 1 illustrates the average number of iterations that QAGA takes to solve 100 random benchmark problems with N = 50 variables and normal coefficients.  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 hand, 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.

CONCLUSION
Quantum annealers are a type of adiabatic quantum computer that can sample from the ground state of Hamiltonians. Unfortunately, several technological barriers preclude physical QAs from attaining the ground state of the given problem Hamiltonians. We introduce the notion of quantum-assisted greedy algorithms (QAGA) that employs QAs for making globally optimum choices at each stage of a greedy algorithm. QAGA views QAs 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. Combining QAs and greedy algorithms addresses the limitations of both and results in remarkably better solutions, albeit executing multiple QMIs for one problem.
Our empirical results on a D-Wave 2000Q quantum processor demonstrate that QAGA finds samples with remarkably lower energy values compared to the multi-qubit correc-    Fig. 2. Performance comparison between QAGA and MQC in solving 100 random benchmark problems with N = 50 spin variables and different sparsity rates s tion (MQC) method that is the state-of-the-art technique in the realm of QA. For sparse problems (i.e., the structure of the problem is close to the Chimera architecture), the performance of the QAGA approaches to MQC. When the sparsity decreases, however, QAGA shows supremacy in terms of finding samples with lower energy values.