Quantum algorithm for association rules mining
arXiv:1605.07444 · doi:10.1103/PhysRevA.94.042311
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 frequent -itemsets in the candidate -itemsets (), our algorithm can efficiently mine these frequent -itemsets and estimate their supports by using parallel amplitude estimation and amplitude amplification with complexity , where is the error for estimating the supports. Compared with the classical counterpart, classical sampling-based algorithm, whose complexity is , our quantum algorithm quadratically improves the dependence on both and in the best case when and on alone in the worst case when .
arXiv comment8 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