Experimental implementation of quantum algorithm for association rules mining

Abstract

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 comment9 pages, 11 figures

References in corpus (40)

• Quantum Machine Learning
• Quantum Mechanics helps in searching for a needle in a haystack
• Quantum algorithm for solving linear systems of equations
• Supervised learning with quantum enhanced feature spaces
• Quantum support vector machine for big data classification
• Quantum machine learning in feature Hilbert spaces
• Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
• Quantum principal component analysis
• Toward the first quantum simulation with quantum speedup
• Quantum algorithms for supervised and unsupervised machine learning
• Quantum Data Fitting
• Practical Quantum Error Mitigation for Near-Future Applications
• Hybrid quantum-classical algorithms and quantum error mitigation
• Operating Quantum States in Single Magnetic Molecules: Implementation of Grover's Quantum Algorithm
• Experimental realisation of Shor's quantum factoring algorithm using qubit recycling
• Experimental demonstration of Shor's algorithm with quantum entanglement
• Prediction by linear regression on a quantum computer
• Demonstration of Shor's quantum factoring algorithm using photonic qubits
• Experimental Realization of Quantum Artificial Intelligence
• Implementing a distance-based classifier with a quantum interference circuit
• Entanglement-Based Machine Learning on a Quantum Computer
• Experimental Quantum Computing to Solve Systems of Linear Equations
• Quantum Algorithm for Linear Regression
• Quantum machine learning for quantum anomaly detection
• Quantum Discriminant Analysis for Dimensionality Reduction and Classification
• Quantum adiabatic machine learning
• Experimental realization of quantum algorithm for solving linear systems of equations
• Limitations of Quantum Simulation Examined by Simulating a Pairing Hamiltonian using Nuclear Magnetic Resonance
• Quantum data compression by principal component analysis
• Quantum algorithm for association rules mining
• Quantum algorithm for association rules mining
• On the CNOT-complexity of CNOT-PHASE circuits
• Quantum algorithm for visual tracking
• Quantum algorithm and quantum circuit for A-Optimal Projection: dimensionality reduction
• Quantum Anomaly Detection with Density Estimation and Multivariate Gaussian Distribution
• Experimental NMR Realization of A Generalized Quantum Search Algorithm
• Variational Quantum Algorithms for Dimensionality Reduction and Classification
• Variational Quantum Anomaly Detection: Unsupervised mapping of phase diagrams on a physical quantum computer
• Quantum diffusion map for nonlinear dimensionality reduction
• Automatic Generation of Grover Quantum Oracles for Arbitrary Data Structures