Association Rules in QUBO Samples and Where to Find Them
Authors: Tian Huang
Siong Thye Goh
Rick Siow Mong Goh
Tao Luo
Venue: Submitted to ICLR 2023 (2023)
Keywords: Association rule
Annealing
QUBO

Abstract: There are sometimes strong associations between variables in the samples to a Quadratic Unconstrained Binary Optimization (QUBO) problem. A natural question arises to us: Are there any value in these association? We study max-cut problem and observe that association can be represented as rules to simplify QUBO problem. Classical and quantum annealers work better when the problem size is smaller. To effectively and efficiently find associations between variables, we adapt traditional association rule mining in the case of QUBO samples and propose a Fast Association Rule Mining algorithm (FARM) specifically for mining QUBO samples. We also propose strategies and a workflow to select and apply promising rules and simplify QUBO problems. We evaluate our method on D-Wave Quantum Annealer as well as Fujitsu Digital Annealer. The experiments demonstrate the utility of FARM as a visualisation tool for understanding associations in QUBO samples. The results also demonstrate the potential of our method in closing the gap between samples and ground truth. The source code will be disclosed to the public if the manuscript is accepted. 

Under review as a conference paper at ICLR 2023
ASSOCIATION RULES IN QUBO SAMPLES AND WHERE TO FIND THEM
Anonymous authors Paper under double-blind review
ABSTRACT
There are sometimes strong associations between variables in the samples a Quadratic Unconstrained Binary Optimization (QUBO) problem. A natural question arises to us: Are there any value in these association? We study max-cut problem and observe that association can be represented as rules to simplify QUBO problem. Classical and quantum annealers work better when the problem size is smaller. To effectively and efficiently find associations between variables, we adapt traditional association rule mining the case of QUBO samples and propose a Fast Association Rule Mining algorithm (FARM) specifically for mining QUBO samples. We also propose strategies and a workflow select and apply promising rules and simplify QUBO problems. We evaluate our method on D-Wave Quantum Annealer as well as Fujitsu Digital Annealer. The experiments demonstrate the utility of FARM samples. The results also demonstrate the potential of our method in closing the gap between samples and ground truth. The source code will be disclosed to the public if the manuscript is accepted.
visualisation tool for understanding associations in QUBO
INTRODUCTION
Many combinatorial optimization problems can be formulated as quadratic unconstrained binary optimization problem (QUBO) Lucas (2014), Glover et al. (018). QUBO corresponds naturally to the transverse Ising model and benefits from the speed up by quantum annealing Kadowaki Nishimori (1998). The combination of QUBO and Quantum annealing Kadowaki & Nishimori (1998) has proved its utility in various applications, such as Traveling Salesman Problem (TSP)
Martonak et al. (2004), Graph colouring Titiloye & Crispin (2011) Portfolio Optimization Venturelli Ventturrllinnnnetullllii & Kondratyev (2019) and Resource Scheduling Problem Ikeda et al. (2019).
Annealing, e.g., simulated LamnealingKikppttriii et al. 1983). is family of probabilistic methods for optimising the variables of a system (e.g. minimising a function). In annealing, we heat the system to high-temperature level and gradually bring down the temperature. Variables in the system gradually lose their energy and eventually sit in a low-energy state. One round of heating and cooling, i.e., an annealing process, produces one sample, which is configuration of all variables. The annealing process is random. The energy distribution of the samples follows Boltzmann distributior/Nelson al. (2022), i.c., the system more likely be in lower energy state. Quantum annealing works similarly, except that it makes use of quantum mechanics.
We can use annealing for optimisation in a sampling manner. While we cannot find optimal solution in one shot, one possible way to obtain a promising solution is to collect more samples. However, the marginal profit of "more samples" decreases as we collect more samples. Besides, access to quantum devices is expensive. We are looking for more efficient method to make additional samples more productive. The main idea of the paper is that we examine existing samples to discover interesting rules and simplify the original QUBO problem. More specifically, if most of the variables agrees certain decision, then most likely these variables have been solved correctly. We should then solve the remaining variables that we less certain of.
There are some earlier works in this domain, with their own limitations. Lewis & Glover (011)) invented few rules to transform the underlying QUBO structure into equivalent graph with fewer nodes and edges. However, such rules are hand-crafted. A question of interest is whether we can discover such rules that could be specific to particular application. Chardaire et al. (1995): Karimi

---

Under review as a conference paper at ICLR 2023
& Rosenberg (0117) ;; Irie et al. (2021) utilise sample persistency, which concerns the persistency of individual variables, and omits the associations between variables. These methods do not work well if persistency is not explicitly presented in samples. For example, in max-cut problem, each sample and its flipped version are equívalent, both having equal chances of presence in sampling. Therefore, variable in max-cut is going be persistent. Other problems like number partitioning, graph colouring, and TSP, also share a similar feature.
In this paper, we propose to use heuristic method discover association rules between variables. The concept of traditional Assocation Rule Mining (ARM) fits very well with our purpose, as is originally designed for discovering associations between items in Market Basket Analysis (MBA) Agrawal et al. (1933). Through adapting traditional ARM in the mining task of QUBO samples, we can discover associations between variables, reveal hidden persistency in samples, and simplify QUBO problems accordingly. By solving smaller QUBO problem, we stand better chance of obtaining more promising results. Our contributions can be summarised as follows.
We adapt association rule mining to the case of mining rules from QUBO samples. We introduce the concept of equivalent alternatives in the definition couple with the special requirements of applications like max-cut.
We explore effective ways to select and apply rules to reduce QUBO problems.
We propose Fast Association Rule Mining (FARM) algorithm for mining QUBO samples, to efficiently discover rules of wide range of support (typically 10-90%).
In the experiments, we evaluate our definitions and methods on two solvers, D-Wave Pegasus Quantum Annealer Willsch et al. (2022) (QA) and Fujitsu 2nd Gen Digital Annealer Aramon et al. (2019) (DA). We use max-cut problems as case study and include two datasets with different topologies in the experiment. Results on QA suggest that FARM can serve as a visualisation tool to help understand associations between variables. By fixing variables according to the discovered rules, we can simplify QUBO problem and find more promising solutions in a second run of solvers. Results on DA suggest that classical annealing- based solvers produce very low level of persistency on large problems, and receives very limited benefits from the proposed method. Comparing the results on QA and DA, we know that association rule has more potential in QA.
The rest of the paper is organised follows. Section 2 reviews existing literature and describes the position of this work. Section 3 introduces the concept of association rule the case of mining QUBO samples and presents a workflow and few strategies that apply the discovered rule to simplify QUBO problem. Section describes the assumption and design ideas of Fast Association Rule Mining (FARM) for QUBO samples. Section 5 quantitatively compares our methods with representative baseline method. Section 6 draws the conclusion.
2 RELATED WORK
2.1 OPTIMISATION
QUBO minimisation problem can be written in the form of min x. x.T..TQQQ Qr, where x is a vector of decision variables, Q is the QUBO matrix. Sometimes, the answers some variables are trivial, such that their value remains unchanged in the optimal solution, regardless of the values taken by other variables. This is called variable persistence in Boros et al. (2006). We can assign the values so that the variables are fixed. By this partial assignment, we effectively reduce the number of variables, and in turn, reduce or simplify the QUBO problem.
There are few ways to identify such partial assignments. One way is to check the QUBO matrix against set of rules Lewis Glover (2016) 2017); Glover et al. (2018). These include manually crafted rules for assigning values to individual variables and pair of variables. This method is designed as preprocessor to reduce the size of problem before passing it to any solvers. The preprocessor "QPro" scans through a QUBO matrix and apply the rules in an iterative way until no further variables can be assigned values. Experiments suggest that QPro works effectively on a synthetic dataset with sparse connectivity and non- non-uniform distributions Glover et al.) (2018) and scientific dataset [Seker et al. (2020), but failed to yield any reduction on the dense and uniformly distributed ORLIB 2500 variable problems Beasley (010) and real-world problem Kim al.
2

---

Under review as a conference paper at ICLR 2023
(2020). We aware of the limitation of manually crafted rules on practical problems. In this work, we are developping a heuristic method to automatically discover rules.
Such a partial assignment can also be identified by exploiting the dynamics in simulation based optimisation heuristics. For example, [Chardaire et al. (1995) focus on the simulated annealing algorithm and use the term "thermostatistical persistence" to describe the value of variable that remains constant as the annealing temperature decreases. The author "fix" such variables so that the
rest of the annealing process is guided and accelerated. [Irie et al. (2021) use molecular dynamics simulation instead. The authors use the term "frozen" and "ambivalent" to refer to variables that obtain "persistence" at an early or late stage of molecular dynamics simulation. The frozen variables are the "precondition" of the original problem. The ambivalent variables remain in the reduced problem, the size of which is determined by a manually-chosen hyper-parameter. The utility of these methods is based on and restricted by the characteristics of specific optimisation heuristics. In our work, we develop solver-independent method that can directly work on the samples or solutions of original problems.
is also possible to identify partial assignments by directly studying samples or solutions of solvers. Karimi & Rosenberg (2017); y Karimi et al. (2017) use the term "sample persistency" to describe variable that has the same value in most samples or solutions. The authors conjecture that variables with persistent values are likely to maintain their values in the ground state of the system. Such variables can be included in partial assignment. Sample persistency has found its utility in jet clustering Delgado & Thaler 2022) and subsurface hydrological inverse analysis(Golden Golden & O' M'Mllley 22021)
Sample persistency Karimi & Rosenberg (017)) is similar to the heuristic- based methods Chardaire eet al. (1955;; ; Irie et al. (2021). in the sense that they only concern the persistency of individual variables, and omit associations between variables. These methods will lose their utility if sample persistency is not explicitly presented in samples. Take max-cut problem as an example, each sample and its flipped version are equivalent to each other, such that you can always expect a persistency of 50% for all variables in fair sampling. Other problems like number partitioning, graph colouring problem and Traveling Salesman Problem (TSP) also have such characteristics.
Assocication Rule Mining (ARM) is good fit in solving the above mentioned issues. We are going to adapt ARM to find assocation between variables, which can used to reveal the implicit persistency in the mining task for QUBO samples. However, ARM is originally not designed for mining QUBÖ samples.
2.2 ASSOCIATION RULE MINING
Association rule mining Agrawal et al. (1993) (ARM) finds strong correlations and frequent patterns from sets of items in the transaction databases. The original concept is for Market Basket Analysis (MBA), e.g., optimising the arangement of items on racks in a supermarket, such that the number of items purchased by customers maximised. There have been various algorithms for ARM: the vanilla ARM algorithm AIS Agrawal et al. (1993), the pruning-enabled milestone, i.e., Apriori Agrawal et al. (1994). tree structured approaches, like Gr-Growth Han al. (2000) and RARM Das et al. (2001). approximated algorithms like ARMA Nayak & Cook (2001) and PARMARioonato, al. 2012). These algorithms assume that the transaction database is getting large (e.g. more than millions), whereas the size of each transaction is limited (e.g. an individual customer usually buys few dozens of items in a single shopping trip). Take the GroGrowth algorithm as an example; maintains a tree structure, the size of which scales very well with the number of transactions, but exponentially increases along with the average number of items in transactions. With high support rate and pruning technique, it climinates a lot of computation and ensures effective mining.
In the mining task for QUBO samples we assume a limited number of samples (corresponds to transactions, e.g. few hundreds), ever increasing number of variables (corresponds to items, e.g., few thousands or even more) and a wide range of support. Even if we avoid tree construction by using the Apriori algorithm, the generation of candidates is also very expensive if we use low support rate. Our assumptions are quite different from the traditional ARM applications and cause existing ARM algorithms to be computationally intractable for our mining task.
3

---

Under review as a conference paper at ICLR 2023
3 ASSOCIATION RULES IN QUBO SAMPLES
In this section, we adapt the traditional definition of association rule in our mining task. We describe the concept of equivalent alternatives, which is common in many problems. We also present workflow and strategies to select promising rules from many candidates and apply them simplify QUBO problem.
3.1 DEFINITION
We first introduce the traditional definition of association rules in the field of Market Basket Analysis, and then adapt it into our QUBO samples mining task.
One famous application of ARM is improve the business volume of supermarket by making smart arrangement of items to racks, according to analysis on its customers' baskets (Market Basket Analysis, MBA). We use X' = [x,, ................................ Zmml to represent all kinds of products or items in supermarket. Let be a set of transactions, where each transaction e is a set of items such that S X. Suppose P C X, Q C X. and P Q 0. A manager wants understand if customer is going to buy Q if he/she has already put P in his/her basket. An association rule r is an implication of the form of P + Q. We say that the rule has support s in the transaction set C if s percent of the transactions in C contain P PUQ. If a rule has a high support rate, it makes sense for the manager to place the racks of P and Q next each other, to facilitate purchase behaviour.
We can find some correspondence between the traditional application of ARM and our use case in mining QUBO samples. C is the set of samples that we can collect upon solving a particular QUBO problem. Since each variable can take value 0 or 1, we interpret it as an indicator variable if a particular item is present. This corresponds to the idea that we also record the absence of an item in a transaction. Suppose that there QUBO problem a bit string of length m. In addition, we define the length of a rule [r] = [P| + [Q] to be the number of variables in the rule.
decision variables in QUBO problem, then sample to the
Generally, one can look for rules with high support. The variables suggested by a high-support rule persistent in most of samples, and are likely to retain their values in the ground truth. Additionally, in an annealing system, we are also looking for a long rule, as a group of strongly associated variables is always & Rosenberg (2017) is a special case of our definition, where |r| = 1. Intuitively, we know that the high-support rules and the long rules are conflicting. The availability of rules that simultancously meet the requirements of minimum length and minimum support is problem-dependent. We can excavate all representative rules in set of samples to understand the availability of such promising rules. This raises the need for a mining rule with wide range of support.
predictable than single noisy variable. The definition of sample persistency Karimi
We use two examples to illustrate the concept of association rule mining for QUBO samples, which is shown in fig We use a minimum support of 10%, 20%.... 80%. 90% in the mining task and organise all discovered rules in a plot, according to their support and length.
T is rule-rich example. The minimum length of the rules is about 60%, which means that about 60% of the variables are persistent in all samples. Some samples with extremely small error (in blue) share about 80% percent variables in common but are rare, since their support rate is under 20%. There are fewer circles in fig Tb] which suggest that the variables in the second example are not strongly associated. The cluster of circles in the lower right corner suggests that only 0.4-0.6% of the variables are strongly associated with each other with a support rate of 90-100%.
We also swap the solvers to let them work different problem and perform rule mining. Readers with interest can find the figures in appendix. The experiment indicates that QA tends to produce samples with strong and diversified associations of variables, regardless of the topology of the problem. The classical solver DA has fewer and weak associations in variables, when the problem is large and sparsely connected.
3.2 EQUIVALENT ALTERNATIVES
The associations between variables could appear in the form of Equivalent Alternatives. We give a formal definition below.
4

---

Under review as a conference paper at ICLR 2023
80
15.6
1.4
Error std (%)
0.31
0.16
2.63
2.65
1.2
0.39
0.53
Length rule
75
15.4
Erou of m ane
Length rule
1.0
2.58
2.60
Endi of 1en 60
70
0.8
2.55
0.6
15.0
2.53
Error
0.4
2.50
0.44
8 0.70
14.8
9
2.48
20
40
60
80
100
40
60
100
Support of rule (%)
Support of rule (%)
(a) Wave Pegasus Quantum Annealer
(b) Fujitsu 2nd Gen Digital Annealer
Figure 1: Rules discovered in the samples of different solvers. (a) D-Wave Pegasus Quantum Annealer on connectivity 70, which is max-cut problem with 145 nodes and averaged degree of 70. X axis the support of rule in percentage. in rule. Each circle represents a subset of samples that follows the rule. The colour and size of circle represents the mean and std of error, i.e., the difference energy between the samples and ground truth. For example, small blue circle represents some promising samples with small energy variance. (b) Fujitsu 2nd Gen Digital Annealer on pegasus2715, 15, which max-cut problem with 2715 nodes and sparse connectivity. The problem instances are described in details in section S
axis is the length of rule, i.c., the number of variables
Suppose oj and ej are samples for the same QUBO problem and are elements of {0, 13"h, They satisfy f(c;) f(cz), where f(-) is the cost function of the QUBO problem. Suppose that A {0, 1mm {0. 11m a mapping function between samples. Given non-negane non-negative integers p and q, if can find function A such that (c;)) Cj and (cy)) C;, and for all c. f(A*+*(() (c,)) f(;),, then we say & and Ej are equivalent alternatives. Here, A denotes the composition A for times.
For the simplicity of explanation, let's first have look at the famous max-cut problem, which is very popular among quantum computing research community. In max-cut problem, one wants to divide set of nodes into two partitions, such that the sum of connection between the nodes from the two partitions are maximised. The conventional QUBO formulation for max-cut is shown in eq. eq.
Maximise DE (0.011)
Σ 1.
Each decision variable x; corresponds to a node. Wij is the connection or coupling between x; and Iz. 2; suggest the node i is in the first partition, whereas I; = means the node is in the second partition. For max-cut, we can find a mapping function
A(f11, T2,... Fm = {1 - I1, - I2, I2...., xm
that converts any sample its equivalent alternative. These alternatives have equal chance of being presented in sampling, since they have the same energy. The persistency of any variables is expected be 50% in fair sampling. Sample persistency Karimi & Rosenberg (2017) will loose its utility in this situation. One way to reveal the implicit persistency in max-cut samples is to find a long and high-support rule through ARM, and alternate samples such that they aligned with rule. We demonstrate the results of this method in Fig I
Equivalent alternatives are commonly seen optimisation problems, such as number partitioning problem (two alternatives), max-cut problem (two alternatives), graph colouring (I' alternatives, where T is the number of colours) and Traveling Salesman Problem (TSP) (T alternatives, where T is the number of cities). In TSP, two routes could be equivalent in order, but different in the starting cities. This is also referred to as Hamiltonian Cycles the context of TSP and its Ising spin model Lucas (2014). A workaround to break the cycle in TSP is to add penalty in the energy function such that a solution is penalised if the travelling path does not start from a specific city. This workaround works fine for the classical annealing methods, but introduces additional penalty weight and severe analog control error to quantum annealing devices Pearson et al. (2019) and makes optimisation more challenging.
5

---

Under review as a conference paper at ICLR 2023
3.3 STRATEGIES AND WORKFLOW
Once we find the collection of rules, the next question is how do we select and apply the rules to simplify a QUBO problem.
We may ask which rule leads to better improvement in the energy of the samples. Intuitively, we see that rules with high support are promising, as a variable with high persistency is likely to retain its value in an optimal state. We propose a rule selection strategy, which is called Highest Support (HS). HS sorts all rules according to their support. Optionally one can also sort the rules by their length second priority.
Intuitively, if a rule belongs to the best sample (c.g., with lowest energy for minimisation problem) in of samples, we might also see this rule to be very promising. We propose another rule selecting strategy, called Lowest Energy (LE). LE locates the neighbourhood of samples that follows a given rule, find the energy of the best sample within this neighbourhood. and use the energy as the key to sort rules. One can also use their support as a second key in the sort.
If want fix some decision variables in a QUBO, but the best rule suggested by HS LE does not include enough number of variables, we can combine and apply the top l: rules in the list. But this could raise an issue when there are conflicts between these rules, For example variable 2; could appear as 2; = 0 in rule A and z; = 1 in rule B. One can adopt greedy strategy to keep the rule with top rank in the list, skip the conflicted rule with rank 2, and check if r's is free of conflict. In practice, the greedy strategy cannot always find enough number of variables to fix, due to conflicts. The selection of rules itself could become a maximum satisfiability problem. To simplify this issue, we just combine the top l rules, with the conflicted variables taking the configuration in the top ranking rule.
To apply rules, fixing variables is the most straightforward way. By configuring decision variable to 0 or 1, one can convert a linear term into a constant and convert a quadratic term into a linear term. This method is widely adopted in many other works Lewis & Glover (2016); Irie et al. (202T): Karimi & Rosenberg (2017). We follow the same way to apply the selected rules. A detailed explanantion on how to fix variables and reduce QUBO size can be found in appendix.
A typical workflow to facilitate optimisation can be as follows. We get a set of samples to a QUBO problem from solver in the first run. To get more promising results, we find candidates of rules presented in the set of samples. We can select promising rules among candidates and fix variables accordingly to produce a reduced QUBO problem from the original. Then we pass the reduced problem to the solver for a second run and expect to find better results in the second run.
4 FAST ASSOCIATION RULE MINING FOR QUBO
As we mentioned in section 2.2 there is quite few mis-match between the assumption of traditional ARM and that of our use case. The computational complexity of existing ARM algorithm would be intractable. We have to design our own algorithm to discover rules efficiently.
We propose an algorithm for mining QUBO samples, called Fast Association Rule Mining (FARM). as shown in Algorithm 0 FARM does not construct a data structure for each mining task. Instead, it directly finds "rules" in each sample and aggregate these rules to form the final output. The input of FARM is set of samples. A sample is consisted of configurations to all decision variables in QUBO problem. We use e; to represent the configurations of sample i. For each C₁ we find "Longest Common Rule" (LCR) in it by evaluating the Hamming distance, denoted by h()))) between e, and its neighbourhood. We define LCR as the longest configurations that is shared by all the given samples and their equivalent alternatives. support s. A higher support results in a larger neighbourhood, and thus shorter LCR shared by this neighbourhood. We aggregate the LCR of all samples and perform a de-duplication of the discovered rules at the end of the algorithm. The detailed implementation of finding LCR can be found in appendix.
The size of the neighbourhood is determined by the
'The definition of LCR should be distinguished from the famous Longest Common Subsequence (LCS) problem, we do not assume order in decision variables. The occupancy of consecutive positions is not applicable our definition of I.C.R

---

Under review as a conference paper at ICLR 2023
Input: of samples Ci, i [1, n] and support
Output: rules
Set K. = næ;
Initialise rules as an empty list;
foreach c; do
Find IC nearest neighbours of c; according to h(c,, ?) # };; j;
Find longest rule r; cj that shared by its neighbourhood: Calculate the actual support of the discovered rule;
Add r; to rules;
end De-duplicate rules;
10 return rules
Algorithm 1: Fast Association Rule Mining for QUBO
Given a support rate, FARM returns rules with equal greater support. This is achieved by only including a specific number of samples the neighbourhood. To find rules with diversified support, one can call FARM with range of support to produce complete spectrum of rules just like the ones FARM is an approximated algorithm the sense that does not enumerate all rules, which
in [ neither resource efficient nor necessary in can find numerous amount of rules from the demo problem set. From them, we are only selecting one or two promising rules for subsequent evaluations. The approximation has a limited impact on the results.
case. We have demonstrated in [ig that FARM
EXPERIMENT
We evaluate our methods on two max-cut datasets with different topologies Huang et al. (002)). The connectivity-varied max-cut dataset consisted of 32 graphs with 145 nodes each graph. The averaged degree of graphs ranges from 1 to 140. The Pegasus-like max-cut dataset has ten graphs with a maximum of 12 edges attached to each node. The number of nodes ranges from 543 to 5430.
We include two solvers, D-Wave Pegasus Quantum Annealer and Fujitsu 2nd Gen Digital Annealer. As we demonstrated section 3.1 quantum and classical solvers produce very different associations between variables. We include the two solvers understand the generalisation of our methods. Regarding the hyper-parameter settings for the QA, we use the default geometric annealing schedule with 2000 μas annealing time and 100 samples in each annealing task. We run DA in parallel tempering mode and set 1e6 number of iterations with 128 replicas, which translates to 128 samples produced in annealing task.
We include sample persistency Karimi & Rosenberg (2017), Karimi et al. (011)) as baseline. Heuristic methods like Chardaire al. (1995) and Irie al. (2021) similar to sample persistency, in the sense that they do not take associations between variables into account. We do not include them in the comparison.
We implement FARM algorithm in Python. It is able to find rules with a few hundreds of variables within seconds. Readers with interests can find the plot of timing and explanation in the appendix.
5.1 QUANTUM ANNEALER ON CONNECTIVITY-VARIES PROBLEMS
We first evaluate our methods with quantum annealer on connectivity-varied problems. Quantum Annealer (QA) is generally weak on densely connected graphs. Existing work suggests prominent performance degradation in QA when the average degree is greater than 12. Fixing variables can effectively reduce averaged degrees. In fig 2 we demonstrate the result on the connectivity70 max-cut problem, in which averaged degree is 70.
In fig 2a the blue bars represent the histogram of variable persistency measured by the method in Karimi & Rosenberg (017)) which suggest the values of the samples are quite random. For example, it says that more than 80% of the variables have a persistence of 50%. However, we have already demonstrated the association rules discovered by FARM in fig Ta which suggests that there is quite
7

---

Under review as a conference paper at ICLR 2023
Unaligned Persistency
80
Percent of variables (%)
Aligned Persistency
14
60-
Error (%)
12
40
10
20
8-
FARM Pst
HS
FARM+LE
6
Variable persistency (%)
Reduced problem size (%)
(a) Persistency
(b) Error
Figure 2: Quantum Annealer on the connectivity70 max-cut problem. (a) Variable persistency in the results of first run, with and without alignment using the rules discovered by FARM (b) Error of different strategies. X axis represents the size of QUBQ in the second run, in percentage. Y axis represents error between achieved energy and ground truth, in percentage. Lower error is better. The dotted line and gray area represent the mean and std of the error in first run. The curves with error bars represent the statistics of errors in second run.
level of persistency samples. We can recover the persistency by replacing some samples with their equivalent alternatives. From the candidates for the rules discovered by FARM, select the longest rule with 100% support and alternate the samples so that they align with the rule. With the alignment, about 75% of variables have persistent value across all samples.
demonstraas the performance of different strategies. Pst is the strategy used by Karimi & Rosenberg (2017), which sorts the variables by persistency and fixes the top le variables. FARM+Pst first align the samples and then apply Pst accordingly. FARM+HS and FARM+LE combine FARM with the HS and LE strategy, which we proposed in Section 3.3 Fig 2b suggests that FARM+HS achieves a lower error compared to Pst and FARM+LE, but the improvement is limited. We can see that the FARM+HS curve green at 40% has a higher error than that of Pst in blue. Despite fig Tal suggesting that we can find a rule which has 100% support and includes 60% of variables of the original problem, applying such promising rule does not give FARM+HS advantage over other strategies, which is not as we expected. This could be due to the manufacturing limitation and imperfection the analog control in the quantum device Pearson et al. (2019), which causes a mis-match between the intended problem and the actual implementation of the problem. In other words, the promising rule that we discovered corresponds to the mis mis-implemented problem, not the original one. In comparison, FARM+Pst has the best performance, as it achieves competitive error as low as that FARM+HS, and retain a low error in wide range of reduced problem size.
5.2 DIGITAL ANNEALER ON PEGASUS-LIKE PROBLEMS
We evaluate our methods with Fujitsu 2nd Gen Digital Annealer (DA) on Pegasus-like max-cut problems. DA is an efficient hardware implementation of the parallel tempering algorithm and is specifically optimised for densely connected problems. DA is weak on sparsely connected problems, like the ones in Pegasus-like max-cut problems. Reducing variables raises the sparsity of the problem and potentially pose challenges to DA. In fig we demonstrate the result on the pegasus2715 max-cut problem, in which there are 27 2715 nodes.
BagBal suggests that there is very limited persistency in the samples even if we apply alignment to the samples. This match with our observation in fig lb] where the longest rule found by FARM only includes 1.4% variables of the QUBO problem.
With such a low level of persistency, Pst and FARM+Pst cannot find promising results. Their curves at 90% problem size lead to 6% averaged error in the second run, which is about 3% worse off compared to the results in the first run. As the number of fixed variables increases, their curves go off the chart and reach about 35% averaged error when the problem size is reduced to 10% of the original
8

---

Under review as a conference paper at ICLR 2023
80
Unaligned Persistency
Percent of variables (%)
Aligned Persistency
FARM-PS: MARM-HS FAAM-LE
Error 1%6
40
3-
20
2-
Variable persistency (%)
Reduced prob size (96)
(a) Persistency
(b) Error
Figure 3: DA on the pegasus2715 max-cut problem. The plot setting is the same as fig
size. comparison, FARM+HS and FARM+LE achieve similar error in the second run. FARM+HS slightly better than FARM+LE and sometimes outperform the results in the first run.
Given the same problem instance pegasus2715, if we compare the rules discovered in the sample set produced by QA, know that the length of rules ranges from 10-60%, which is much longer than those for DA and indicates the potential space of improvement for QA. We do not repeat the experiment of QA pegasus2715. since QA is already able to find global optimal in single Huang et al. (2022). The comparison between QA and DA on pegasus2715 suggests a stronger potential of association rule for QA.
6 CONCLUSION AND DISCUSSION
In this paper, we define the association rule mining in the context of the mining of QUBO samples. We propose strategies select promising rules and apply them simplify QUBO problems. We propose Fast Association Rule Mining (FARM), which effectively finds rules of wide range of support from QUBO samples. Experiments suggest that our method aware of associations among variables and can simplify QUBO problems and improve the optimisation results.
Determining the number variables that maximizes performance is challenging and remains an open question in the literature. We demonstrate FARM as a visualisation tool that help user understand the distribution of the rules, and narrow down the range optimal number variables to be fixed. In the history of this research topic, we are the first to investigate the distribution of frequent patterns terms length v.s. support rate. Our next step is to examine the corresponding determination methods.
We say the rules discovered by FARM are correct the sense that they do exist in the sample set. But the discovered rules do not necessarily hold in the global optimal, even if they have 100% support rate in the sample set. This is due to the noises and errors Pearson et al. (2019) in true quantum annealing devices. We do not investigate the divergence between the distribution of sample set and the solution space of the original problem, as this is out of the scope of this work. In our future work, are going to investigate how the divergence impact the association rule mining for QUBO.
REFERENCES
Rakesh Agrawal, Tomasz Imieliński, and Arun Swami. Mining association rules between sets of items in large databases. Proceedings of the 1993 ACM SIGMOD international conference on Management of data, pp. 207-216, 1993.
Rakesh Agrawal, Ramakrishnan Srikant, et al. Fast algorithms for mining association rules. In Proc. 20th int. conf. very large data bases, VLDB, volume 1215, pp. 487-499. Citeseer, 1994.

---

Under review as a conference paper at ICLR 2023
Maliheh Aramon, Gili Rosenberg, Elisabetta Valiante, Toshiyuki Miyazawa, Hirotaka Tamura, and Helmut G Katzgraber. Physics-inspire optimization for quadratic unconstrained problems using a digital annealer. Frontiers in Physics, 7:48, 2019.
John Beasley. Or-library. hup://people. brunel. ac, uk/" mustjjbijeblinfo himl, 2010.
Endre Boros, Peter L Hammer, and Gabriel Tavares. Preprocessing of unconstrained quadratic binary optimization. 2006.
Pierre Chardaire, Jean Luc Lutton, and Alain Sutter. Thermostatistical persistency: A powerful improving concept for simulated annealing algorithms. European Journal of Operational Research, 86(3):565-579 1995.
Amitabha Das, Wee-Keong Ng, and Yew-Kwong Woon. Rapid association rule mining. In Pro- ceedings of the tenth international conference on Information and knowledge management, pp. 474-481, 2001.
Andrea Delgado and Jesse Thaler. Quantum annealing for jet clustering with thrust. arXiv preprint arXiv:2205.028144 2022.
Fred Glover, Mark Lewis, and Gary Kochenberger. Logical and inequality implications for reducing the size and difficulty of quadratic unconstrained binary optimization problems. European Journal of Operational Research, 265(3):829-842, 2018.
John K Golden and Daniel O' Malley. Pre-and post-processing in quantum-computtationall hydrologic inverse analysis. Quantum Information Processing, 20(5):1-18, 2021.
Jiawei Han, Jian Pei, and Yiwen Yin. Mining frequent patterns without candidate generation. ACM sigmod record, 29(2):1-12 2000.
Tian Huang, Jun Xu, Tao Luo, Xiaozhe Guz, Rick Goh, and Weng-Fai Wong. Benchmarking quantum (-inspired) annealing hardware on practical use cases. IEEE Transactions on Computers, 2022.
Kazuki Ikeda, Yuma Nakamura, and Travis S Humble. Application of quantum annealing to nurse scheduling problem. Scientific reports, 9(1::1110, 2019.
Hirotaka Irie, Haozhao Liang, Shinya Gongyo, Tetsuo Hatsuda, et al. Hybrid quantum annealing via molecular dynamics. Scientific reports, 11(1):1-9, 2021.
Tadashi Kadowaki and Hidetoshi Nishimori. Quantum annealing the transverse ising model. Physical Review E, 58(5):5355, 1998.
Hamed Karimi and Gili Rosenberg. Boosting quantum annealer performance via sample persistence. Quantum Information Processing, 16(7):1-24, 2017.
Hamed Karimi, Gili Rosenberg, and Helmut Katzgraber. Effective optimization using sample persistence: A case study quantum annealers and various monte carlo optimization methods. Physical Review E, 96(4):043312, 2017
Minsung Kim, Davide Venturelli, and Kyle Jamieson. Towards hybrid classical- computation systems. Proceedings of the 19th ACM Workshop on Hot Topics in Networks, pp. 110-116, 2020.
structures
Scott Kirkpatrick, C Daniel Gelatt Jr, and Mario Vecchi. Optimization by simulated annealing. science, 22004598):671-660, 1983.
Mark Lewis and Fred Glover. Binary quadratic network preprocessing: theory and empirical analysis. Networks, 2016.
Mark Lewis and Fred Glover. Quadratic unconstrained binary optimization problem preprocessing: Theory and empirical analysis. Networks, 70(2):79-97,20)) 2017.
Andrew Lucas. Ising formulations of many np problems. Frontiers in physics, pp. 5, 2014.
10

---

Under review as a conference paper at ICLR 2023
Roman Martoñák, Giuseppe E Santoro, and Erio Tosatti. Quantum annealing of the traveling salesman problem. Physical Review E, 70(5):057701, 2004.
traveling-salesmann
Jyothsna R Nayak and Diane J Cook. Approximate association rule mining. In FLAIRS Conference, pp. 259-263, 2001.
Jon Nelson, Mare Vuffray, Andrey Y Lokhov, Tameem Albash, and Carleton Coffrin. High-quality thermal gibbs sampling with quantum annealing hardware. Physical Review Applied, 17(4):044046, 2022.
Adam Pearson, Anurag Mishra, Itay Hen, and Daniel A Lidar. Analog errors in quantum annealing: doom and hope. NPJ Quantum Information, 5(1):1-9, 2019.
Matteo Riondato, Justin A DeBrabant, Rodrigo Fonseca, and Eli Upfal. Parma: a parallel randomized algorithm for approximate association rules mining in mapreduce. In Proceedings of the 21st ACM international conference on Information and knowledge management, pp. 85-94, 2012.
Oylum Şeker, Neda Tanoumand, and Merve Bodur. Digital annealer for quadratic unconstrained binary optimization: a comparative performance analysis. arXiv preprint wrXiv:2012.12264 2020.
Olawale Titiloye and Alan Crispin. Quantum annealing of the graph coloring problem. Discrete Optimization, 8(2):77-338) -844, 2011.
Davide Venturelli and Alexci Kondratyev. Reverse quantum annealing approach to portfolio opti- mization problems. Quantum Machine Intelligence, 1(1):17-30, 2019.
Dennis Willsch, Madita Willsch, Carlos D Gonzalez Calaza, Fengping Jin, Hans De Raedt, Marika Svensson, and Kristel Michielsen. Benchmarking advantage and d-wave 2000g quantum annealers with exact cover problems. Quantum Information Processing, 21(4):1-22, 2022.
A LIST OF SYMBOLS
Table 1: List of symbols
decision variable
The binary value of decision variable
17
Number of samples
Number of decision variables
T
Number of equivalent alternatives to sample
Weight of linear terms and quadratic terms
C
A sample or configuration
The equivalent alternatives of configuration
An association rule
The equivalent alternatives of an association rule
hamming distance between rules or two configurations
support
B FIND LONGEST COMMON RULE (LCR)
To find the Longest Common Rule (LCR) in a sample we use another customised algorithm. as shown in Algorithm 2 For each GG we use the XNOR operator and compare it with the rest of the samples and their equivalent alternatives, denoted as cfg,- Aij. is a bit array, whose size equals to the number of decision variables in the QUBO problem. A one Ai, k suggests that the corresponding decision variable in the two samples shares the same value. The Hamming distance between C; and of can be calculated from A Among all the alternatives of a sample, we only keep the one closest to c₁. As dump the rest alternatives, a bit map that marks all common values shared by e; and its neighbourhood. We can find variables that are persistent throughout the neighbourhood, by applying aggregation based element-wise AND
can rename Ai,. as Ar,j Ar,j for all is
11

---

Under review as a conference paper at ICLR 2023
Input: a reference configuration and set of oj. E A.
Output: rule r
foreach v, # j do
foreach cf e do
Ai.j. = XNOR(c, ef); h(,, o3) sum(1 A.,,k):
end
Keep of with shortest h, and name it cy;
Dump the rest alternatives and rename Ai.j. as Asgi
end
Aggregate A., by applying element-wise AND along subscript
10 Select decision variables whose corresponding bit in the aggregation 1;
Selected variables and their values in o; form a rule
12 return
Algorithm 2: Find the LCS in sample ca
operation along subscript j. Those persistent variables and their values forms the longest common rule within this neighbourhood.
The complexity of the FARM algorithm is O(m?nT), where m is the total number of samples in a mining task, n is the total number of variables sample, T the total number of equivalent alternatives each sample. The majority of the calculations in FARM are logical operations like XNOR or AND. There are limited levels of data dependency between these calculations, which means that exploit massive parallelism, e.g., like vectorisation SIMD in advanced computing architecture. The complexity of FARM scales linearly with n. suggesting its ability to handle a mining task with large number of decision variables. Since FARM expecting a limited number of samples in mining task, the quadratic complexity factor m² still tractable for modern computing architecture.
C APPLY A RULE TO REDUCE QUBO PROBLEM
QUBO minimisation problem be written in the form of m _ _Qx, where is vector decision variables, Q is the QUBO matrix. We can also rewrite the QUBO in the following representation.
Σ waa Σ WiyKTa C fJJ
min (0.1
w; is on the diagonal of Q, wi, is the off-diagonal element of Q. We refer to uaz; linear term, and Wyjaa as quadratic term. is the constant. If we discover through FARM that a variable xy equals one in most of samples, we can assign to Zz.. This will change the linear term Wyz, into constant wy, and change the quadratic term WiyJ,T into a linear term W3y If ar equals to zero in most of samples, either case, the number variables in the QUBO problem reduces.
assign 0 to 2y,, such that the linear term wyzy and Wyy0, become zero. In
In our experiment, solver API used to access the quantum annealer.
the function "fix, variables" provided by Dawave Ocean 5.5, which is the
D EXPERIMENT APPENDIX
D. THE DISCOVERY OF RULES
D.2 TIMING OF FARM
The timing of FARM is shown in fig
12

---

Under review as a conference paper at ICLR 2023
100
Error std (%)
Error std (%)
0.42
0:00
60
0.04
Error of mobn energy (%6
0.40
Length rule
60
80
1
0.13
0.38
0.6
mean energy
Length of rule (%)
50
0.00
0.10
0.38
0.4
0.36
40
0.34
20
0.2
20
COC0
0.32
(0)
10-
0.30
40
60
100
40
60
100
Support of rule (%)
Support of rule (%)
(a) Digital Annealer on connectivity70
(b) Quantum Annealer on pegasus2715
Figure 4: Frequent patterns found by different solvers
Support
Support
0.20
10%
60%
10%
60%
30%
80%
1.0
30%
80%
Timing (s)
0.15
90%
Timing (6)
50%
0.8
50%
0.6
0.4
0.05
0.2
10a
10
1000
5000
Averaged degree
Num of nodes
Connectivity- varied problems
(b) Pegasus-lik like problems
Figure 5: Timing of FARM with respect to problem complexity and support
shows the timing of FARM on the sample set produced by QA on the connectivity70 problem. use lower support in the mining. 5bg55]ssowe shows the timing of FARM on the sample set produced by DA on the pegasus2715 15 problem. The run-time linearly increase along with the number of nodes. The run- un-timee not sensitive to the setting of support, which match our expectation because we find limited number of rules shown in fig
Fig 5a
The run-time increases with the number of averaged degrees. It also increases
13


Reviews:
[{"review_id": "koxRILa5jAg", "reviewer": "Reviewer_5aqV", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes applying association rule mining for reducing the problem size of QUBO. The mining is performed for solution samples, and the authors proposes an efficient approximate association rule mining specifically for QUBO. Empirical results show that the proposed procedure can substantially reduce the problem size and find good solutions compared with an existing method.", "summary_of_the_review": "The paper seems to try an interesting approach combining QA and rule mining. Although the proposed method is a simple heuristics that do not have a theoretical support, the empirical results suggest the practical usefulness of the proposed framework. However, to be honest, I am not familiar with the topic and my review contains educated guess. ", "strength_and_weaknesses": "Strength:\n- The basic idea, combining a quantum annealer (QA) and association rule mining, is interesting and seems novel.\n- The empirical results suggest superiority of the proposed method.\n\nWeaknesses:\n- As the authors mentioned, determining the number of variables that maximizes performance is difficult.\n- No theoretical guarantee or justification for the approximation quality (e.g., risk to find wrong rule) is provided.\n- The paper is sometimes difficult to follow for those who are not familiar with a QA. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "VywuGpXh7Br", "reviewer": "Reviewer_ABPP", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes to use heuristic method to discover association rules between variables in an optimization problem.\n", "summary_of_the_review": "The introduction of the problem is unclear. For instance in the introduction in not clear the the meaning of samples in an optimization problem. This should be clarified.\n\nThe are same part of the paper that could be better explained. For instance how the rules have been adopted to reduce the size of the dataset is not reported. \n\nThe idea could be interesting but the experimental evaluation is poor and the validity of the proposed approach is non confirmed by the reported results.", "strength_and_weaknesses": "+ An interesting idea compared to the state of the art works\n- Poor results", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject