Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Journal of Quantum Information Science

Quantum Algorithm for Mining Frequent Patterns for Association Rule Mining

Abdirahman Alasow, Marek A. Perkowski

Published Jan 1, 2023• 3 citations
Publisher

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.

DOI
10.4236/jqis.2023.131001

Related papers

Quantum algorithm for association rules mining

Chao‐Hua Yu, Fei Gao, Qing-Le Wang +1 more

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 frequent itemsets from the candidate itemsets and acquiring their supports. Specifically, for the case in which there are ${M}_{f}^{(k)}$ frequent $k$-itemsets in the ${M}_{c}^{(k)}$ candidate $k$-itemsets (${M}_{f}^{(k)}\ensuremath{\le}{M}_{c}^{(k)}$), our algorithm can efficiently mine these frequent $k$-itemsets and estimate their supports by using parallel amplitude estimation and amplitude amplification with complexity $O(\frac{k\sqrt{{M}_{c}^{(k)}{M}_{f}^{(k)}}}{\ensuremath{\epsilon}})$, where $\ensuremath{\epsilon}$ is the error for estimating the supports. Compared with the classical counterpart, i.e., the classical sampling-based algorithm, whose complexity is $O(\frac{k{M}_{c}^{(k)}}{{\ensuremath{\epsilon}}^{2}})$, our quantum algorithm quadratically improves the dependence on both $\ensuremath{\epsilon}$ and ${M}_{c}^{(k)}$ in the best case when ${M}_{f}^{(k)}\ensuremath{\ll}{M}_{c}^{(k)}$ and on $\ensuremath{\epsilon}$ alone in the worst case when ${M}_{f}^{(k)}\ensuremath{\approx}{M}_{c}^{(k)}$.

arXiv:1512.02420•Physical Review A•Oct 7, 2016•78 citations

Quantum Search Algorithms for Constraint Satisfaction and Optimization Problems Using Grover's Search and Quantum Walk Algorithms with Advanced Oracle Design

Abdirahman Alasow

The field of quantum computing has emerged as a powerful tool for solving and optimizing combinatorial optimization problems. To solve many real-world problems with many variables and possible solutions for constraint satisfaction and optimization problems, the required number of qubits of scalable hardware for quantum computing is the bottleneck in the current generation of quantum computers. In this dissertation, we will demonstrate advanced, scalable building blocks for the quantum search algorithms that have been implemented in Grover's search algorithm and the quantum walk algorithm. The scalable building blocks are used to reduce the required number of qubits in the design. The proposed architecture effectively scales and optimizes the number of qubits needed to solve large problems with a limited number of qubits. Thus, scaling and optimizing the number of qubits that can be accommodated in quantum algorithm design directly reflect on performance. Also, accuracy is a key performance metric related to how accurately one can measure quantum states. The search space of quantum search algorithms is traditionally created by using the Hadamard operator to create superposition. However, creating superpositions for problems that do not need all superposition states decreases the accuracy of the measured states. We present an efficient quantum circuit design that the user has control over to create the subspace superposition states for the search space as needed. Using only the subspace states as superposition states of the search space will increase the rate of correct solutions. In this dissertation, we will present the implementation of practical problems for Grover's search algorithm and quantum walk algorithm in logic design, logic puzzles, and machine learning problems such as SAT, MAX-SAT, XOR-SAT, and like SAT problems in EDA, and mining frequent patterns for association rule mining.

•Apr 15, 2024•0 citations

Experimental Implementation of Quantum Algorithm for Association Rules Mining

Chao‐Hua Yu

Recently, a quantum algorithm for a fundamentally important task in data mining, association rules mining (ARM), called qARM for short, has been proposed. Notably, qARM achieves significant speedup over its classical counterpart for implementing the main task of ARM, i.e., finding frequent itemsets from a transaction database. In this paper, we experimentally implement qARM on both real quantum computers and a quantum computing simulator via the IBM quantum computing platform. In the first place, we design quantum circuits of qARM for a 2$\times $2 transaction database (i.e., a transaction database involving two transactions and two items), and run it on four real five-qubit IBM quantum computers as well as on the simulator. For a larger 4$\times $4 transaction database which would lead to circuits with more qubits and a higher depth than the currently accessible IBM real quantum devices can handle, we also construct the quantum circuits of qARM and execute them on “aer_simulator” alone. Both experimental results show that all the frequent itemsets from the two transaction databases are successfully derived as desired, demonstrating the correctness and feasibility of qARM. Our work may serve as a benchmarking, and provide prototypes for implementing qARM for larger transaction databases on both noisy intermediate-scale quantum devices and universal fault-tolerant quantum computers.

arXiv:2204.13634•IEEE Journal on Emerging and Selected Topics in Circuits and Systems•Aug 23, 2022•14 citations

Improved qARM algorithm for frequent itemsets search in large-scale data sets

Han Qi, Liyuan Wang, Dianshuo Fu +2 more

Abstract The existing Quantum Algorithm for Association Rules Mining(qARM) need to set the quantum oracle of data artificially when mining frequent itemsets, which is very time-consuming when dealing with large-scale data. Based on the Cn − X gate and extended Grover algorithm (less-than-oracle), this paper proposes an improved method. In the process of calculating support degree, the original quantum phase estimation algorithm is abandoned, and the combined gate based on the Cn − X gate is used to calculate support, so as to improve the accuracy of calculating support. Then, the extended Grover algorithm is modified to screen the support degree. By using IBM’s Qiskit tool for simulation experiments, the data sets with sizes of 2x2 and 4x4 and fragments 29 − 32 items of data for the dataset Market Basket Optimization.The simulation results shown that,when dealing with large-scale data sets, it is no longer necessary to prepare quantum oracle for all data in advance. In the valid data, its search accuracy can reach 90% on average.

The Journal of Supercomputing•Apr 8, 2025•1 citation

Quantum Privacy-Preserving Data Mining

Shenggang Ying, Mingsheng Ying, Yuan Feng

Data mining is a key technology in big data analytics and it can discover understandable knowledge (patterns) hidden in large data sets. Association rule is one of the most useful knowledge patterns, and a large number of algorithms have been developed in the data mining literature to generate association rules corresponding to different problems and situations. Privacy becomes a vital issue when data mining is used to sensitive data sets like medical records, commercial data sets and national security. In this Letter, we present a quantum protocol for mining association rules on vertically partitioned databases. The quantum protocol can improve the privacy level preserved by known classical protocols and at the same time it can exponentially reduce the computational complexity and communication cost.

arXiv:1512.04009•Dec 13, 2015•2 citations

Most Frequent Itemset Optimization.

Jonas Nüßlein

In this paper we are dealing with the frequent itemset mining. We concentrate on the special case that we only want to identify the most frequent itemset of length N. To do that, we present a pattern on how to consider this search as an optimization problem. First, we extract the frequency of all possible 2-item-sets. Then the optimization problem is to find the N objects, for which the minimal frequency of all containing 2-item-sets is maximal. This combinatorial optimization problem can be solved by any optimization algorithm. We will solve them with Quantum Annealing and QUBO with QbSolv by D-Wave. The advantages of MFIO in comparison to the state-of-the-art-approach are the enormous reduction of time need, reduction of memory need and the omission of a threshold. The disadvantage is that there is no guaranty for accuracy of the result. The evaluation indicates good results.

•Apr 16, 2019•1 citation
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.
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 frequent itemsets from the candidate itemsets and acquiring their supports. Specifically, for the case in which there are Mf(k){M}_{f}^{(k)}Mf(k)​ frequent kkk-itemsets in the Mc(k){M}_{c}^{(k)}Mc(k)​ candidate kkk-itemsets (${M}_{f}^{(k)}\ensuremath{\le}{M}_{c}^{(k)}$), our algorithm can efficiently mine these frequent kkk-itemsets and estimate their supports by using parallel amplitude estimation and amplitude amplification with complexity $O(\frac{k\sqrt{{M}_{c}^{(k)}{M}_{f}^{(k)}}}{\ensuremath{\epsilon}})$, where $\ensuremath{\epsilon}$ is the error for estimating the supports. Compared with the classical counterpart, i.e., the classical sampling-based algorithm, whose complexity is $O(\frac{k{M}_{c}^{(k)}}{{\ensuremath{\epsilon}}^{2}})$, our quantum algorithm quadratically improves the dependence on both $\ensuremath{\epsilon}$ and Mc(k){M}_{c}^{(k)}Mc(k)​ in the best case when ${M}_{f}^{(k)}\ensuremath{\ll}{M}_{c}^{(k)}$ and on $\ensuremath{\epsilon}$ alone in the worst case when ${M}_{f}^{(k)}\ensuremath{\approx}{M}_{c}^{(k)}$.
The field of quantum computing has emerged as a powerful tool for solving and optimizing combinatorial optimization problems. To solve many real-world problems with many variables and possible solutions for constraint satisfaction and optimization problems, the required number of qubits of scalable hardware for quantum computing is the bottleneck in the current generation of quantum computers. In this dissertation, we will demonstrate advanced, scalable building blocks for the quantum search algorithms that have been implemented in Grover's search algorithm and the quantum walk algorithm. The scalable building blocks are used to reduce the required number of qubits in the design. The proposed architecture effectively scales and optimizes the number of qubits needed to solve large problems with a limited number of qubits. Thus, scaling and optimizing the number of qubits that can be accommodated in quantum algorithm design directly reflect on performance. Also, accuracy is a key performance metric related to how accurately one can measure quantum states. The search space of quantum search algorithms is traditionally created by using the Hadamard operator to create superposition. However, creating superpositions for problems that do not need all superposition states decreases the accuracy of the measured states. We present an efficient quantum circuit design that the user has control over to create the subspace superposition states for the search space as needed. Using only the subspace states as superposition states of the search space will increase the rate of correct solutions. In this dissertation, we will present the implementation of practical problems for Grover's search algorithm and quantum walk algorithm in logic design, logic puzzles, and machine learning problems such as SAT, MAX-SAT, XOR-SAT, and like SAT problems in EDA, and mining frequent patterns for association rule mining.
Recently, a quantum algorithm for a fundamentally important task in data mining, association rules mining (ARM), called qARM for short, has been proposed. Notably, qARM achieves significant speedup over its classical counterpart for implementing the main task of ARM, i.e., finding frequent itemsets from a transaction database. In this paper, we experimentally implement qARM on both real quantum computers and a quantum computing simulator via the IBM quantum computing platform. In the first place, we design quantum circuits of qARM for a 2$\times 2transactiondatabase(i.e.,atransactiondatabaseinvolvingtwotransactionsandtwoitems),andrunitonfourrealfive−qubitIBMquantumcomputersaswellasonthesimulator.Foralarger42 transaction database (i.e., a transaction database involving two transactions and two items), and run it on four real five-qubit IBM quantum computers as well as on the simulator. For a larger 42transactiondatabase(i.e.,atransactiondatabaseinvolvingtwotransactionsandtwoitems),andrunitonfourrealfive−qubitIBMquantumcomputersaswellasonthesimulator.Foralarger4\times $4 transaction database which would lead to circuits with more qubits and a higher depth than the currently accessible IBM real quantum devices can handle, we also construct the quantum circuits of qARM and execute them on “aer_simulator” alone. Both experimental results show that all the frequent itemsets from the two transaction databases are successfully derived as desired, demonstrating the correctness and feasibility of qARM. Our work may serve as a benchmarking, and provide prototypes for implementing qARM for larger transaction databases on both noisy intermediate-scale quantum devices and universal fault-tolerant quantum computers.
Abstract The existing Quantum Algorithm for Association Rules Mining(qARM) need to set the quantum oracle of data artificially when mining frequent itemsets, which is very time-consuming when dealing with large-scale data. Based on the Cn − X gate and extended Grover algorithm (less-than-oracle), this paper proposes an improved method. In the process of calculating support degree, the original quantum phase estimation algorithm is abandoned, and the combined gate based on the Cn − X gate is used to calculate support, so as to improve the accuracy of calculating support. Then, the extended Grover algorithm is modified to screen the support degree. By using IBM’s Qiskit tool for simulation experiments, the data sets with sizes of 2x2 and 4x4 and fragments 29 − 32 items of data for the dataset Market Basket Optimization.The simulation results shown that,when dealing with large-scale data sets, it is no longer necessary to prepare quantum oracle for all data in advance. In the valid data, its search accuracy can reach 90% on average.
Data mining is a key technology in big data analytics and it can discover understandable knowledge (patterns) hidden in large data sets. Association rule is one of the most useful knowledge patterns, and a large number of algorithms have been developed in the data mining literature to generate association rules corresponding to different problems and situations. Privacy becomes a vital issue when data mining is used to sensitive data sets like medical records, commercial data sets and national security. In this Letter, we present a quantum protocol for mining association rules on vertically partitioned databases. The quantum protocol can improve the privacy level preserved by known classical protocols and at the same time it can exponentially reduce the computational complexity and communication cost.
In this paper we are dealing with the frequent itemset mining. We concentrate on the special case that we only want to identify the most frequent itemset of length N. To do that, we present a pattern on how to consider this search as an optimization problem. First, we extract the frequency of all possible 2-item-sets. Then the optimization problem is to find the N objects, for which the minimal frequency of all containing 2-item-sets is maximal. This combinatorial optimization problem can be solved by any optimization algorithm. We will solve them with Quantum Annealing and QUBO with QbSolv by D-Wave. The advantages of MFIO in comparison to the state-of-the-art-approach are the enormous reduction of time need, reduction of memory need and the omission of a threshold. The disadvantage is that there is no guaranty for accuracy of the result. The evaluation indicates good results.