TITLE:
Quantum Algorithm for Mining Frequent Patterns for Association Rule Mining
AUTHORS:
Abdirahman Alasow, Marek Perkowski
KEYWORDS:
Data Mining, Association Rule Mining, Frequent Pattern, Apriori Algorithm, Quantum Counter, Quantum Comparator, Grover’s Search Algorithm
JOURNAL NAME:
Journal of Quantum Information Science,
Vol.13 No.1,
March
31,
2023
ABSTRACT: Maximum frequent pattern generation from a large database of transactions and items for association rule mining is an important research topic in data mining. Association rule mining aims to discover interesting correlations, frequent patterns, associations, or causal structures between items hidden in a large database. By exploiting quantum computing, we propose an efficient quantum search algorithm design to discover the maximum frequent patterns. We modified Grover’s search algorithm so that a subspace of arbitrary symmetric states is used instead of the whole search space. We presented a novel quantum oracle design that employs a quantum counter to count the maximum frequent items and a quantum comparator to check with a minimum support threshold. The proposed derived algorithm increases the rate of the correct solutions since the search is only in a subspace. Furthermore, our algorithm significantly scales and optimizes the required number of qubits in design, which directly reflected positively on the performance. Our proposed design can accommodate more transactions and items and still have a good performance with a small number of qubits.