Binary matrix factorization on special purpose hardware.

Area of Science:

• Computer Science
• Quantum Computing
• Data Mining

Background:

• Many data mining problems are NP-hard combinatorial optimization challenges.
• Quantum and quantum-inspired hardware offer potential speedups but require specific problem formulations like Ising or QUBO.
• Binary Matrix Factorization (BMF) is a key problem with broad data mining applications.

Purpose of the Study:

• To develop new Quadratic Unconstrained Binary Optimization (QUBO) formulations for the Binary Matrix Factorization (BMF) problem.
• To adapt BMF for quantum and quantum-inspired hardware, addressing limitations in variable handling for large matrices.
• To evaluate the performance of proposed methods against existing approaches using real-world and synthetic data.

Main Methods:

• Proposed two novel QUBO formulations for the BMF problem.
• Incorporated clustering constraints into the QUBO formulations.
• Developed a sampling-based approach to handle large matrices on hardware with limited variables.
• Conducted experiments on the Fujitsu Digital Annealer, a quantum-inspired annealer.

Main Results:

• The proposed QUBO formulations for BMF were successfully implemented and tested.
• The sampling-based approach enabled the factorization of large rectangular matrices.
• Experiments showed that the developed methods produced more accurate BMFs compared to competing methods on both synthetic and gene expression data.
• A simple baseline algorithm was also proposed and found to outperform sophisticated methods in specific scenarios.

Conclusions:

• The novel QUBO formulations and sampling-based approach are effective for solving the BMF problem on quantum-inspired hardware.
• This work advances the application of quantum computing paradigms to fundamental data mining tasks.
• The findings suggest a promising direction for accelerating complex data analysis using novel hardware architectures.