  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 out frequent
itemsets from the candidate itemsets and acquiring their supports.
Specifically, for the case in which there are $M_f^{(k)}$ frequent $k$-itemsets
in the $M_c^{(k)}$ candidate $k$-itemsets ($M_f^{(k)} \leq M_c^{(k)}$), our
algorithm can efficiently mine these frequent $k$-itemsets and estimate their
supports by using parallel amplitude estimation and amplitude amplification
with complexity $\mathcal{O}(\frac{k\sqrt{M_c^{(k)}M_f^{(k)}}}{\epsilon})$,
where $\epsilon$ is the error for estimating the supports. Compared with the
classical counterpart, classical sampling-based algorithm, whose complexity is
$\mathcal{O}(\frac{kM_c^{(k)}}{\epsilon^2})$, our quantum algorithm
quadratically improves the dependence on both $\epsilon$ and $M_c^{(k)}$ in the
best case when $M_f^{(k)}\ll M_c^{(k)}$ and on $\epsilon$ alone in the worst
case when $M_f^{(k)}\approx M_c^{(k)}$.
