Quantum algorithm for association rules mining

Association rules mining (ARM) is one of the most important problems in knowledge discovery and data mining. Given a transaction database that has a large number of transactions and items, the task of ARM is to acquire consumption habits of customers by discovering the relationships between itemsets (sets of items). In this paper, we address ARM in the quantum settings and propose a quantum algorithm for the key part of ARM, finding frequent itemsets from the candidate itemsets and acquiring their supports. Specifically, for the case in which there are $M_f^{\left(k\right)}$ frequent $k$-itemsets in the $M_c^{\left(k\right)}$ candidate $k$-itemsets ($M_f^{\left(k\right)}\le M_c^{\left(k\right)}$), our algorithm can efficiently mine these frequent $k$-itemsets and estimate their supports by using parallel amplitude estimation and amplitude amplification with complexity $O\left(\frac{k\sqrt{M_c^{\left(k\right)}{M}_f^{\left(k\right)}}}{\epsilon }\right)$, where $\epsilon$ is the error for estimating the supports. Compared with the classical counterpart, i.e., the classical sampling-based algorithm, whose complexity is $O\left(\frac{k{M}_c^{\left(k\right)}}{{\epsilon }^2}\right)$, our quantum algorithm quadratically improves the dependence on both $\epsilon$ and $M_c^{\left(k\right)}$ in the best case when $M_f^{\left(k\right)}\ll M_c^{\left(k\right)}$ and on $\epsilon$ alone in the worst case when $M_f^{\left(k\right)}\approx M_c^{\left(k\right)}$.

Figure 1

An example of a transaction database that contains five transactions $\mathcal{T}=\{T_0,T_1,T_2,T_3,T_4\}$ with each one being a subset of the set of four items $\mathcal{I}=\{I_0=\mathrm{Bread},I_1=\mathrm{Cheese},I_2=\mathrm{Butter},I_3=\mathrm{Milk}\}$ and its binary matrix representation.

Figure 2

The whole process of the Apriori algorithm.

Figure 3

The left part is the quantum circuit for constructing the oracle $O^{\left(k\right)}$ by using the basic oracle $O$ and the generalized cnot operation ${\bigwedge }_k\left({\sigma }_x\right)$, where the circuit representation of $O$ is given in the right part.

Figure 4

Quantum circuit of the first three steps of our algorithm when $T=2^t$ and $N=2^n$. Here, $|C^{\left(k\right)}\rangle :=\frac{{\sum }_{j=1}^{M_c^{\left(k\right)}}|C_j^{\left(k\right)}\rangle }{\sqrt{M_c^{\left(k\right)}}}$.