Quantum algorithm for association rules mining

Abstract

Association rules mining is one of the most important problems in knowledge discovery and data mining. The goal of it is to acquire consumption habits of customers by discovering the relationships between items from a transaction database that has a large number of transactions and items. The most compute intensive process for ARM is to find out the frequent 1-itemsets and 2-itemsets. In this paper, we propose a quantum algorithm for finding out the frequent 1-itemsets and 2-itemsets. In our algorithm, to mine the frequent 1-itemsets efficiently, we use the technique of amplitude amplification. To mine the frequent 2-itemsets efficiently, we propose a new tomography scheme, i.e., pure-state-based quantum state tomography. It is shown that our algorithm is potential to achieve exponential speedup in the number of transactions and polynomial speedup in the number of items over the classical algorithm.

5 pages

References in corpus (9)

• Quantum algorithm for solving linear systems of equations
• An introduction to quantum machine learning
• Quantum algorithms: an overview
• Quantum random access memory
• The quest for a Quantum Neural Network
• Quantum Data Fitting
• Prediction by linear regression on a quantum computer
• Creating superpositions that correspond to efficiently integrable probability distributions
• Quantum Privacy-Preserving Data Mining

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