Several problem in Artificial Intelligence and Pattern Recognition are computationally intractable due to their inherent complexity and the exponential size of the solution space. One example of such problems is biclustering, a specific clustering problem where rows and columns of a data-matrix must be clustered simultaneously. Quantum information processing could provide a viable alternative to combat such a complexity. A notable work in this direction is the recent development of the D-Wave computer, whose processor has been designed to the purpose of solving Quadratic Unconstrained Binary Optimization (QUBO) problems. In this paper, we investigate the use of quantum annealing by providing the first QUBO model for biclustering and a theoretical analysis of its properties (correctness and complexity). We empirically evaluated the accuracy of the model on a synthetic data-set and then performed experiments on a D-Wave machine discussing its practical applicability and embedding properties

Biclustering with a quantum annealer

Bottarelli, Lorenzo;Bicego, Manuele;Denitto, Matteo;Di Pierro, Alessandra;Farinelli, Alessandro;Mengoni, Riccardo
2018-01-01

Abstract

Several problem in Artificial Intelligence and Pattern Recognition are computationally intractable due to their inherent complexity and the exponential size of the solution space. One example of such problems is biclustering, a specific clustering problem where rows and columns of a data-matrix must be clustered simultaneously. Quantum information processing could provide a viable alternative to combat such a complexity. A notable work in this direction is the recent development of the D-Wave computer, whose processor has been designed to the purpose of solving Quadratic Unconstrained Binary Optimization (QUBO) problems. In this paper, we investigate the use of quantum annealing by providing the first QUBO model for biclustering and a theoretical analysis of its properties (correctness and complexity). We empirically evaluated the accuracy of the model on a synthetic data-set and then performed experiments on a D-Wave machine discussing its practical applicability and embedding properties
D-Wave
Quantum Annealing
Bi-clustering
File in questo prodotto:
File Dimensione Formato  
2-Draft.pdf

solo utenti autorizzati

Tipologia: Documento in Pre-print
Licenza: Dominio pubblico
Dimensione 810.74 kB
Formato Adobe PDF
810.74 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/974079
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 7
social impact