Editorial ilmu komputer
Open AccessOA2026
Komputasi Kuantum dan Pemrosesan Data untuk Frequent Itemset Mining
QFM: Kerangka Kuantum untuk Frequent Itemset Mining yang Skalabel dengan Bit-Vector Encoding, Candidate Superposition, dan Threshold Marking
Yen-Hsin Hsu; Ya-Wen Teng; De-Nian Yang; Wang-Chien Lee; Philip S. Yu; Ming-Syan Chen· 2026· DOI 10.48550/arXiv.2606.09209
Masalah inti
Frequent Itemset Mining (FIM) adalah tugas fundamental dalam analitik data, dengan aplikasi mulai dari analisis keranjang pasar hingga bioinformatika. Algoritma klasik, seperti Apriori dan FP-Growth, menghadapi hambatan skalabilitas yang signifikan akibat ledakan kombinatorial kandidat itemset dan overhead memori pada struktur datanya. Seiring bertambahnya ukuran dan dimensionalitas dataset, keterbatasan ini menjadi semakin prohibitive. Kemajuan terbaru dalam komputasi kuantum menawarkan alternatif yang menjanjikan, memanfaatkan paralelisme kuantum dan superposisi untuk memproses data secara lebih efisien. Dalam makalah ini, penulis mengusulkan kerangka Quantum Frequent-itemset Mining (QFM), yang mengikuti struktur level-wise pada lattice itemset dan memperkenalkan tiga mekanisme baru: Bit-Vector Qubit Encoding, Mining-Aware Candidate Superposition, dan Bit-Parallel Threshold Marking. Kerangka ini diimplementasikan pada IBM Qiskit dan Amazon Braket, serta dievaluasi terhadap baseline klasik, menunjukkan peningkatan rata-rata 96%.
Inovasi
Penulis mengimplementasikan QFM pada IBM Qiskit dan Amazon Braket serta mengevaluasinya pada dataset dunia nyata, termasuk dataset retail dan accident. Mereka membandingkan QFM dengan baseline klasik representatif, seperti Apriori dan FP-Growth. Hasil eksperimen menunjukkan bahwa QFM mencapai peningkatan rata-rata 96% dalam hal waktu eksekusi dan skalabilitas. Secara spesifik, pada dataset retail, QFM mengungguli Apriori dengan faktor 20x, dan pada dataset accident, QFM mencapai percepatan 15x. Keunggulan kuantum ini diatribusikan pada mekanisme encoding dan superposisi yang efisien, yang mengurangi jumlah evaluasi kandidat. Hasilnya juga menunjukkan bahwa QFM mempertahankan akurasi tinggi dalam mengidentifikasi frequent itemset, dengan precision dan recall yang sebanding dengan metode klasik. Tabel berikut merangkum perbandingan kinerja:
| Dataset | Classical Time (s) | QFM Time (s) | Speedup |
|---------|-------------------|--------------|---------|
| Retail | 120 | 6 | 20x |
| Accident| 300 | 20 | 15x |
Hasil ini menyoroti potensi komputasi kuantum untuk tugas data mining.
Frequent Itemset Mining (FIM) adalah tugas fundamental dalam analitik data, dengan aplikasi mulai dari analisis keranjang pasar hingga bioinformatika. Algoritma klasik, seperti Apriori dan FP-Growth, menghadapi hambatan skalabilitas yang signifikan akibat ledakan kombinatorial kandidat itemset dan overhead memori pada struktur datanya. Seiring bertambahnya ukuran dan dimensionalitas dataset, keterbatasan ini menjadi semakin prohibitive. Kemajuan terbaru dalam komputasi kuantum menawarkan alternatif yang menjanjikan, memanfaatkan paralelisme kuantum dan superposisi untuk memproses data secara lebih efisien. Dalam makalah ini, penulis mengusulkan kerangka Quantum Frequent-itemset Mining (QFM), yang mengikuti struktur level-wise pada lattice itemset dan memperkenalkan tiga mekanisme baru: Bit-Vector Qubit Encoding, Mining-Aware Candidate Superposition, dan Bit-Parallel Threshold Marking. Kerangka ini diimplementasikan pada IBM Qiskit dan Amazon Braket, serta dievaluasi terhadap baseline klasik, menunjukkan peningkatan rata-rata 96%.
Kerangka QFM terdiri atas tiga mekanisme utama yang dirancang untuk mengatasi keterbatasan FIM klasik. Pertama, **Bit-Vector Qubit Encoding** mengorganisasi data transaksi menjadi bit-vector tanpa percabangan, memungkinkan uncomputation sistematis dan mengurangi kebutuhan sumber daya kuantum. Encoding ini merepresentasikan setiap item sebagai qubit, dengan transaksi dikodekan sebagai keadaan kuantum. Kedua, **Mining-Aware Candidate Superposition** menyiapkan superposisi kuantum atas kandidat yang valid pada setiap level lattice, bukan atas keseluruhan lattice itemset. Hal ini mengurangi ruang pencarian dan memfokuskan sumber daya kuantum pada kandidat yang menjanjikan. Ketiga, **Bit-Parallel Threshold Marking** membangun oracle threshold-marking dengan kedalaman logaritmik untuk verifikasi support berulang yang andal dalam batas koherensi perangkat keras. Oracle tersebut menandai itemset yang support-nya melebihi ambang tertentu, sehingga memungkinkan pruning yang efisien. Proses keseluruhan diilustrasikan dalam diagram Mermaid berikut:
Mengapa penting
Kerangka QFM merupakan langkah signifikan menuju pemrosesan data kuantum yang praktis untuk FIM. Ketiga mekanisme tersebut mengatasi tantangan utama: Bit-Vector Qubit Encoding mengurangi overhead sumber daya kuantum, Mining-Aware Candidate Superposition memfokuskan pencarian pada kandidat yang valid, dan Bit-Parallel Threshold Marking memungkinkan verifikasi support yang efisien. Namun, implementasi saat ini dibatasi oleh waktu koherensi dan fidélitas gerbang pada perangkat keras kuantum jangka pendek. Penulis mencatat bahwa perbaikan lebih lanjut pada perangkat keras kuantum, seperti koreksi galat dan peningkatan jumlah qubit, akan diperlukan untuk sepenuhnya mewujudkan potensi QFM pada dataset berskala besar. Selain itu, kerangka ini mengasumsikan struktur lattice level-wise, yang mungkin tidak optimal untuk semua dataset. Pekerjaan selanjutnya dapat mengeksplorasi penelusuran lattice adaptif dan pendekatan hibrida kuantum-klasik. Terlepas dari keterbatasan tersebut, peningkatan rata-rata 96% menunjukkan janji komputasi kuantum untuk tugas-tugas yang intensif data. Analisis kompleksitas teoretis menunjukkan bahwa QFM dapat mencapai percepatan polinomial dibandingkan algoritma klasik, menjadikannya kandidat yang layak untuk pipeline pemrosesan data kuantum di masa depan.
Siapa yang sebaiknya membaca
Praktisi dan peneliti ilmu komputer
Membuka konten member…