Quantum Fp-Growth for Association Rules Mining

Abstract

Quantum computing, based on quantum mechanics, promises revolutionary computational power by exploiting quantum states. It provides significant advantages over classical computing regarding time complexity, enabling faster and more efficient problem-solving. This paper explores the application of quantum computing in frequent itemset mining and association rules mining, a crucial task in data mining and pattern recognition. We propose a novel algorithm called Quantum FP-Growth (QFP-Growth) for mining frequent itemsets. The QFP-Growth algorithm follows the traditional FP-Growth approach, constructing a QF-list, then the QFP-tree, a quantum radix tree, to efficiently mine frequent itemsets from large datasets. We present a detailed analysis of each step in the QFP-Growth algorithm, providing insights into its time complexity and computational efficiency. Our algorithm outperforms classical FP-Growth with a quadratic improvement in error dependence, showcasing the power of quantum algorithms in data mining. To validate the effectiveness of our approach, we conducted experiments using the IBM QASM simulator, qiskit. The results demonstrate the efficiency and effectiveness of our QFP-Growth algorithm in mining frequent itemsets from a transactional database.