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.

arXiv comment5 pages

References in corpus (23)

• Quantum Mechanics helps in searching for a needle in a haystack
• Elementary gates for quantum computation
• Quantum algorithm for solving linear systems of equations
• Quantum Simulation
• Quantum support vector machine for big data classification
• Quantum Amplitude Amplification and Estimation
• Quantum principal component analysis
• An introduction to quantum machine learning
• Quantum state tomography via compressed sensing
• Quantum algorithms: an overview
• Quantum random access memory
• The quest for a Quantum Neural Network
• Quantum algorithms for supervised and unsupervised machine learning
• Quantum Data Fitting
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Prediction by linear regression on a quantum computer
• Creating superpositions that correspond to efficiently integrable probability distributions
• Quantum Discriminant Analysis for Dimensionality Reduction and Classification
• Google in a Quantum Network
• Quantum Navigation and Ranking in Complex Networks
• Adiabatic quantum algorithm for search engine ranking
• Quantum Google in a Complex Network
• 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