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

Most Frequent Itemset Optimization.

Jonas Nüßlein

Published Apr 16, 2019• 1 citation
OpenAlex

Abstract

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.

Related papers

Frequent Itemset Mining using QUBO

Jonas Nüßlein

In this paper we propose a R-step approximation to solve frequent itemset mining on quantum hardware like quantum annealing or QAOA. The idea is to search for the set of items where the minimal 2-item frequency is maximal. This can be represented as a maximum clique problem.

arXiv:1904.07693•Apr 16, 2019•1 citation

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

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 Algorithm for Mining Frequent Patterns for Association Rule Mining

Abdirahman Alasow, Marek A. Perkowski

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.

Journal of Quantum Information Science•Jan 1, 2023•3 citations

Quantum Computing and Data Processing for Frequent Itemset Mining

Yen-Hsin HSU, Ya-Wen Teng, De-Nian Yang +3 more

Frequent Itemset Mining (FIM) is an important task in data analytics, where classical algorithms face scalability bottlenecks from the combinatorial growth of candidates and the memory overhead of their data structures. Inspired by recent developments in quantum computing, in this paper, we propose the Quantum Frequent-itemset Mining (QFM) data-processing framework for FIM. Following the level-wise structure of the itemset lattice, QFM introduces three mechanisms: (1) Bit-Vector Qubit Encoding for quantum data representation, which organizes transaction data into branchless bit-vectors to facilitate systematic uncomputation; (2) Mining-Aware Candidate Superposition, which prepares a quantum superposition over valid candidates at each lattice level rather than the full itemset lattice; and (3) Bit-Parallel Threshold Marking, which constructs a logarithmic-depth threshold-marking oracle for reliable repeated support verification within hardware coherence limits. We provide theoretical time complexity analysis, implement QFM on IBM Qiskit and Amazon Braket, and evaluate it on real-world datasets against representative classical baselines, where QFM achieves 96% improvement on average.

arXiv:2606.09209•Jun 8, 2026•0 citations

A QAOA-Based Heuristic to Hide Sensitive Itemsets

Abhijeet Ghoshal, Yan Li, Syam Menon +1 more

The benefits of sharing transactional data with upstream supply chain partners has been known for a long time. However, many retailers are still reluctant to share, and there is evidence that the extent of sharing would be greater if information sensitive to retailers is concealed before data are shared. In transactional data, sensitive information are typically frequent itemsets that can be hidden by deleting items belonging to the sensitive itemsets from transactions that support the itemsets. The problem of identifying the smallest set of transactions from which to delete items such that sensitive itemsets will be hidden can be formulated as a generalized set covering problem. Numerous classical approaches have been developed for solving this problem. We propose a new approach to solve this optimization problem using QAOA. In our preliminary experiments, we find optimal solutions for small problems (that use up to 32 qubits) by using simulators and real quantum computers even when we use only one layer of QAOA. Identifying properties of the optimization problem should further help in faster convergence towards the optimal solutions of the optimization problem.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•0 citations
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.
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)}$.
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.
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.
Frequent Itemset Mining (FIM) is an important task in data analytics, where classical algorithms face scalability bottlenecks from the combinatorial growth of candidates and the memory overhead of their data structures. Inspired by recent developments in quantum computing, in this paper, we propose the Quantum Frequent-itemset Mining (QFM) data-processing framework for FIM. Following the level-wise structure of the itemset lattice, QFM introduces three mechanisms: (1) Bit-Vector Qubit Encoding for quantum data representation, which organizes transaction data into branchless bit-vectors to facilitate systematic uncomputation; (2) Mining-Aware Candidate Superposition, which prepares a quantum superposition over valid candidates at each lattice level rather than the full itemset lattice; and (3) Bit-Parallel Threshold Marking, which constructs a logarithmic-depth threshold-marking oracle for reliable repeated support verification within hardware coherence limits. We provide theoretical time complexity analysis, implement QFM on IBM Qiskit and Amazon Braket, and evaluate it on real-world datasets against representative classical baselines, where QFM achieves 96% improvement on average.
The benefits of sharing transactional data with upstream supply chain partners has been known for a long time. However, many retailers are still reluctant to share, and there is evidence that the extent of sharing would be greater if information sensitive to retailers is concealed before data are shared. In transactional data, sensitive information are typically frequent itemsets that can be hidden by deleting items belonging to the sensitive itemsets from transactions that support the itemsets. The problem of identifying the smallest set of transactions from which to delete items such that sensitive itemsets will be hidden can be formulated as a generalized set covering problem. Numerous classical approaches have been developed for solving this problem. We propose a new approach to solve this optimization problem using QAOA. In our preliminary experiments, we find optimal solutions for small problems (that use up to 32 qubits) by using simulators and real quantum computers even when we use only one layer of QAOA. Identifying properties of the optimization problem should further help in faster convergence towards the optimal solutions of the optimization problem.