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

arXiv:1512.02420 · Physical Review A

Quantum algorithm for association rules mining

Chao‐Hua Yu, Fei Gao, Qing-Le Wang, Qiaoyan Wen

Published Oct 7, 2016• 78 citations
arXivHTMLPDF

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 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)}$.

DOI
10.1103/physreva.94.042311

Related papers

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

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

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 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

Quantum enhanced rare event discovery and sampling

Naixu Guo, Po-Wei Huang, Qisheng Wang +4 more

Financial crashes, cascading failures in infrastructure, and critical errors in AI systems are frequently triggered by events that occur with extremely small probability. Efficiently discovering and sampling events with probability below a threshold is therefore of critical interest. Yet this task is highly non-trivial using existing classical or quantum methods. Being rare, such events require an immense sampling overhead to collect sufficient data samples. Moreover, because the rare events are not known in advance, they cannot be flagged for amplification using standard techniques. Here, we introduce a quantum algorithm for rare-event discovery and sampling without first learning which events are rare. The algorithm achieves the optimal quantum scaling with the rarity threshold. We further demonstrate that this can achieve a quadratic speedup for heavy-tailed systems whose tail has nonvanishing total mass, and translates into a robust polynomial speedup for stationary stochastic processes, with the exponent determined by its entropy-rate structure.

quant-pharXiv:2606.06316•Jun 5, 2026•0 citations

Association Rules Mining with Quantum Computing and Quantum Storage

Qiang Gao, Fengli Zhang, Ruijin Wang +1 more

The rapid development of big data puts forward higher requirements on computational efficiency and storage capacity. But the traditional mining algorithms based on classical computing were unable to satisfy the demand of data analysis and computing. Because of quantum systems unique ability of hyper parallel computation and hyper acceleration, the large-scale computing and data storage can be solve well. Although the development of quantum computer has not yet achieved a qualitative leap, quantum computing in big data application has achieved lots of theoretical achievements. In this paper, we make quantum data mining as a starting point. Since we have no sufficient space to store candidate sets of association rules and have low computation ability in the processing of association rules, we propose a novel quantum method of data storage and retrieval for association rules mining based on Boolean matrix, we propose the algorithm called Q-Eclat can accelerate the computation of candidate sets support. According to our analysis based on open data source, the proposed method outperforms the classical Eclat algorithm in terms of storage capacity and computing ability.

International Conference on Big Data Computing and Communications (BigCom)•Aug 1, 2017•5 citations
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 (Mf(k)\ensuremath≤Mc(k){M}_{f}^{(k)}\ensuremath{\le}{M}_{c}^{(k)}Mf(k)​\ensuremath≤Mc(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(kMc(k)Mf(k)\ensuremathϵ)O(\frac{k\sqrt{{M}_{c}^{(k)}{M}_{f}^{(k)}}}{\ensuremath{\epsilon}})O(\ensuremathϵkMc(k)​Mf(k)​​​), where \ensuremathϵ\ensuremath{\epsilon}\ensuremathϵ is the error for estimating the supports. Compared with the classical counterpart, i.e., the classical sampling-based algorithm, whose complexity is O(kMc(k)\ensuremathϵ2)O(\frac{k{M}_{c}^{(k)}}{{\ensuremath{\epsilon}}^{2}})O(\ensuremathϵ2kMc(k)​​), our quantum algorithm quadratically improves the dependence on both \ensuremathϵ\ensuremath{\epsilon}\ensuremathϵ and Mc(k){M}_{c}^{(k)}Mc(k)​ in the best case when Mf(k)\ensuremath≪Mc(k){M}_{f}^{(k)}\ensuremath{\ll}{M}_{c}^{(k)}Mf(k)​\ensuremath≪Mc(k)​ and on \ensuremathϵ\ensuremath{\epsilon}\ensuremathϵ alone in the worst case when Mf(k)\ensuremath≈Mc(k){M}_{f}^{(k)}\ensuremath{\approx}{M}_{c}^{(k)}Mf(k)​\ensuremath≈Mc(k)​.
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.
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.
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.
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.
Financial crashes, cascading failures in infrastructure, and critical errors in AI systems are frequently triggered by events that occur with extremely small probability. Efficiently discovering and sampling events with probability below a threshold is therefore of critical interest. Yet this task is highly non-trivial using existing classical or quantum methods. Being rare, such events require an immense sampling overhead to collect sufficient data samples. Moreover, because the rare events are not known in advance, they cannot be flagged for amplification using standard techniques. Here, we introduce a quantum algorithm for rare-event discovery and sampling without first learning which events are rare. The algorithm achieves the optimal quantum scaling with the rarity threshold. We further demonstrate that this can achieve a quadratic speedup for heavy-tailed systems whose tail has nonvanishing total mass, and translates into a robust polynomial speedup for stationary stochastic processes, with the exponent determined by its entropy-rate structure.
The rapid development of big data puts forward higher requirements on computational efficiency and storage capacity. But the traditional mining algorithms based on classical computing were unable to satisfy the demand of data analysis and computing. Because of quantum systems unique ability of hyper parallel computation and hyper acceleration, the large-scale computing and data storage can be solve well. Although the development of quantum computer has not yet achieved a qualitative leap, quantum computing in big data application has achieved lots of theoretical achievements. In this paper, we make quantum data mining as a starting point. Since we have no sufficient space to store candidate sets of association rules and have low computation ability in the processing of association rules, we propose a novel quantum method of data storage and retrieval for association rules mining based on Boolean matrix, we propose the algorithm called Q-Eclat can accelerate the computation of candidate sets support. According to our analysis based on open data source, the proposed method outperforms the classical Eclat algorithm in terms of storage capacity and computing ability.