Quantum algorithm for association rules mining

Abstract

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)}\le 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{k{M}_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)}$.

8 pages

References in corpus (6)

• Quantum algorithm for solving linear systems of equations
• An introduction to quantum machine learning
• Quantum random access memory
• The quest for a Quantum Neural Network
• Quantum Data Fitting
• Creating superpositions that correspond to efficiently integrable probability distributions

Cited by in corpus (15)

• Quantum generative adversarial network for generating discrete distribution
• Quantum data compression by principal component analysis
• Quantum K-nearest neighbor classification algorithm based on Hamming distance
• Asymptotic Quantum Algorithm for the Toeplitz Systems
• Quantum algorithm for visual tracking
• Machine learning \& artificial intelligence in the quantum domain
• Improved quantum algorithm for A-optimal projection
• Quantum algorithms for anomaly detection using amplitude estimation
• Efficient quantum circuit for singular value thresholding
• A brief introduction to quantum algorithms
• Quantum algorithm for Neighborhood Preserving Embedding
• Quantum Gaussian process regression
• Experimental implementation of quantum algorithm for association rules mining
• Quantum Algorithm for Unsupervised Anomaly Detection
• Quantum algorithm for logistic regression