This paper describes our participation in Task 2 of the QuantumCLEF lab, where we explored the use of quantum annealing for clustering 6486 document embeddings. We employed a Quadratic Unconstrained Binary Optimization (QUBO) formulation to address the NP-hard problem of -medoids clustering, optimizing the selection of cluster centers without explicitly assigning each data point to a cluster. Our approach aimed to minimize pairwise dissimilarities among selected medoids while maximizing their separation, ensuring well-defined and diverse clusters. To manage the limitations of current quantum hardware, we implemented a hierarchical clustering procedure: initially reducing the dataset using classical methods and then applying quantum annealing for ifnal medoid optimization. The results indicate that a combination of simulated annealing for initial clustering, followed by quantum annealing, yielded the best outcomes, achieving a Davies-Bouldin index of 4.6798 and an nDCG@10 of 0.5349 when using = 50 clusters. This hierarchical approach underscores the potential of quantum annealing in enhancing clustering quality despite current hardware constraints. Our findings suggest that quantum-enhanced clustering methods could significantly advance the field of information retrieval and recommender systems by providing more eficient and accurate data organization techniques.
Clustering is an unsupervised machine learning technique that involves grouping similar data points
together [
Quantum Annealing (QA) is an emerging technology that leverages quantum mechanical efects to
ifnd optimal solutions to certain optimization problems [
This paper discusses our participation in Task 2 of the QuantumCLEF (qCLEF) lab, an innovative
evaluation platform designed to explore the potential of QA in the domains of Information Retrieval (IR)
and Recommender Systems (RS). The goal of this task is to use quantum annealing to group document
embeddings to facilitate the browsing of large collections [
For our QA method, we formulate the clustering problem as a Quadratic Unconstrained Binary
Optimization (QUBO) that can be solved by a quantum annealer. We tested our approach on the
provided datasets of sentence embeddings from ANTIQUE [
Our focus within this framework has been on leveraging QA to tackle the computationally intensive task of document clustering. This process, essential for organizing large datasets and improving user interaction through more precise recommendation systems, poses significant challenges due to the sheer volume and complexity of the data. Traditional clustering methods, while efective to some extent, often struggle under the weight of modern data demands, necessitating a quantum approach that could potentially revolutionize our capabilities. The qCLEF lab provided a unique opportunity to compare the performance of QA-based clustering algorithms against their classical counterparts (Simulated Annealing (SA)), using both the quantum resources of D-Wave machines accessing by the CINECA platform and traditional computational methods.
The paper is organized as follows. Section 2 introduces related works; Section 3 describes our approach; Section 4 explains our experimental setup; Section 5 discusses our main findings; finally, Section 6 draws some conclusions and outlooks for future work.
QA, an optimization algorithm proposed by Kadowaki and Nishimori in 1998 [
To utilize QA, the optimization problem must first be formulated as a QUBO problem. This formulation
allows the problem to be mapped onto the quantum annealer’s architecture. Once the problem is
expressed as a QUBO, QA operates by encoding the solution into the ground state of a quantum system.
The process involves initializing the system into a superposition of all possible states and gradually
evolving it towards the ground state using a technique known as adiabatic evolution. This method has
shown promise in solving combinatorial optimization problems, where traditional algorithms struggle
due to computational complexity [
In the realm of optimization, QA has shown significant potential. For example, it has been applied to
solve complex scheduling problems in aviation and manufacturing, optimizing resource allocation and
process planning [
In the context of clustering, QA has been applied to optimize the clustering objective function.
Kurihara et al. [
In general, Quantum Computing (QC) has emerged as a promising approach to improve IR and RS
[
Despite promising results, QA still faces challenges due to the limitations of current quantum
hardware. Ongoing research focuses on developing more eficient quantum annealing algorithms and
addressing the scalability issues of quantum machines [
To sum up, QA has emerged as a powerful tool for clustering and optimization, with successful applications in IR and RS. The D-Wave machine has been instrumental in implementing QA algorithms and exploring their potential. However, more research is necessary to fully harness the capabilities of QA and overcome the limitations of current quantum hardware.
For quantum annealing-based clustering, we follow the approach of Bauckhage et al. [
The essence of the approach is captured in the Quadratic Unconstrained Binary Optimization (QUBO) formulation, designed to be executed on a quantum annealer. The formulation abstracts the clustering problem into finding an optimal set of cluster centers (medoids) by minimizing an objective function that represents the clustering criteria without directly clustering each data point.
The QUBO for the -medoids problem is formulated as: * = argmin∈{0,1} z 11 z
− ︁( 2 z Δz + z Δ1 − 2 1 ︁) where Δ is a matrix where each element ∆ quantifies the dissimilarity between data points and , based on the pairwise distances between the data points. This QUBO formulation seeks to minimize the dissimilarity among the selected medoids while ensuring that the selected points are spread across the entire dataset.
The function embedded within the QUBO aims to balance two critical objectives: 1. Minimizing the sum of pairwise dissimilarities among the chosen medoids, thereby ensuring that the clusters are tight and well-defined, weighted by the variable . 2. Maximizing the separation between the selected medoids to enhance the diversity and coverage of the clusters in the data set, with the contribution weighted by the variable .
A crucial constraint in this QUBO formulation is to ensure that exactly medoids are selected from the set of points. This is implemented via the constraint:
∑︁ = =1 This condition is essential for preserving the accuracy of the clustering procedure, guaranteeing that precisely clusters are created, each represented by a single medoid. In our QUBO, the contribution to this constraint is represented by . The parameter acts as a Lagrange multiplier, which is crucial in (1) (2) balancing the minimization of the objective function against the constraint that the number of selected medoids is equal to .
The settings of , along with and , help fine-tune the performance of the clustering algorithm on
quantum annealing hardware. In our experiments, we fix the values of the hyperparameters = 1/,
= 1/, and = 2 in the QUBO formulation. These values are chosen according to the guidelines
provided by Bauckhage et al. [
Before applying the QUBO formulation on the quantum annealer, we experimented with diferent sizes of prior clusters to reduce the number of data points. This hierarchical approach allows us to handle larger datasets that exceed the capacity of the quantum hardware. We explore the impact of size reduction on clustering performance and solution quality.
The hierarchical clustering procedure, illustrated in Figure 1, works as follows: 1. We start with the original dataset of sentence embeddings. 2. We apply a classical clustering algorithm (e.g., k-means, pairing-point method or simulated annealing) to group embeddings into clusters, where < . 3. We use the representative vectors as input to the QUBO formulation and solve it using the
D-Wave quantum annealer. 4. The resulting medoids obtained from the quantum annealer are then used to assign each of the original data points to its nearest medoid, forming the final clusters.
We vary the size of the prior clustering to investigate the trade-of between the reduction of problem size and the quality of the clustering. Smaller values of lead to a more compact representation of the dataset but may lose some fine-grained details. Larger values of preserve more information, but increase computational complexity and may exceed the capacity of the quantum annealer.
By comparing the clustering results obtained with diferent sizes of prior clusterings, we aim to find a balance between the eficiency of the quantum approach and the efectiveness of the resulting clusters. We evaluated the quality of the final clusters using the Davies-Bouldin index and the nDCG@10 metric, as described in the evaluation measures section.
This hierarchical approach allows us to leverage the power of quantum annealing for the clustering task while addressing the limitations of current quantum hardware. By systematically exploring the impact of problem size reduction, we provide insights into the scalability and practicality of using quantum annealing for clustering in the context of information retrieval.
The clustering task in qCLEF focuses on using QA to group document embeddings to facilitate browsing of large collections. Specifically, the task involves obtaining a list of representative medoids for a given dataset of sentence embeddings.
For this task, we used datasets derived from the ANTIQUE collection. The organizers provide two
datasets [
The sentence embeddings provided by the organizers were generated using a transformer model to convert each sentence into a dense vector representation.
(a) (c) (b) (d)
Two main metrics are used to evaluate the quality of the clusters:
1. Davies-Bouldin Index: This is an internal evaluation metric utilized to assess the quality of
clustering. It quantifies the average similarity ratio of each cluster to its most similar counterpart,
considering both the within-cluster scatter (compactness) and the between-cluster separation.
A lower DBI value indicates better clustering performance, characterized by compact and
wellseparated clusters.
2. Normalized Discounted Cumulative Gain (nDCG@10): This is an external evaluation metric that
assesses the usefulness of the clustering for a retrieval task. For each query, the most relevant
cluster is identified based on the similarity between the query embedding and cluster centroids.
The documents belonging to that cluster are then ranked based on their similarity to the query.
So, the nDCG@10 metric measures the quality of the top 10 retrieved documents in terms of
relevance. These relevance evaluations were calculated by the organizers after submitting the
clustering results from the lab. A higher nDCG signifies that the clustering is more beneficial for
retrieval tasks [
To apply quantum annealing to the clustering task, we formulate it as a QUBO problem that can be
solved with a quantum annealer. We adopt a similar approach to that proposed by Bauckhage et al. [
One challenge of the QUBO formulation is that it requires the specification of the number of clusters () in advance. To address this, participants are encouraged to experiment with = 10, 25 or 50 values and use a cluster validity index such as Davies-Bouldin to select the best number of clusters. The organizers provide tutorials and code templates to assist participants in implementing the QUBO formulation and interfacing with the D-Wave quantum annealer. Participants have the flexibility to explore alternative problem formulations and strategies for mapping the clustering task to the quantum hardware, taking into account the specific characteristics and limitations of the quantum annealer.
To simulate the quantum annealing process on a classical computer, we use the SA algorithm, which can be implemented using the SimulatedAnnealingSampler method from the D-Wave sampler library. This allows us to test and debug our QUBO formulation locally before running on the actual quantum hardware.
For our quantum experiments, we utilized the D-Wave Advantage quantum annealer, which was made available through CINECA. In this lab, we were allocated 120 s of Quantum Processing Unit (QPU). The device comprises over 5000 qubits organized in a Pegasus topology, where each qubit is linked to 15 others. To interact with the quantum annealer, we employed the dwave-system library, particularly the DWaveSampler and EmbeddingComposite classes. Despite this advanced architecture, the current hardware limitations still present challenges in embedding large problems directly onto the quantum hardware. Consequently, only a few hundred variables can be embedded in the machine. One potential solution could be the dimensionality reduction of the document vectors, which are part of Task 1 of the qCLEF lab. To explore other approaches, we proposed a hierarchical clustering strategy. This approach entails initial clustering using classical algorithms to decrease the number of vectors and select representatives until the problem size is small enough to fit into the quantum hardware. One example is the LeapHybridSampler, which is already part of the Dwave library. Additionally, we considered other classical algorithms, including k-medoids, simulated annealing, and an alternative involving pairwise clustering iterations.
Our experimental procedure is as follows: 1. We first run the classical k-medoids baseline on the set to establish a reference performance level.
We experiment with = 10, 25, 50 (number of clusters) according to the guidelines. 2. We then implement our proposed QUBO formulation of the clustering problem and validate it using the SimulatedAnnealingSampler. 3. We run experiments using the D-Wave quantum annealer, comparing the direct embedding approach for small k and the hierarchical approach for larger . We tune hyperparameters such as the annealing time and the number of reads. 4. We compare the performance of the classical and quantum approaches using the Davies-Bouldin index. 5. We analyze the results and discuss the benefits and limitations of the quantum annealing approach for the clustering task.
Our code is available in the following BitBucket repository: https://bitbucket.org/eval-labs/qc24-qiimas/ src/main/. The repository is organized as follows: • antique_doc_embeddings.csv : This file contains a subset of the ANTIQUE dataset. Includes sentences from Yahoo! Answers that have been converted into embeddings using a transformer model. There are 6486 vectors for the clustering in total. • antique_train_queries.csv : This file also includes a portion of the ANTIQUE dataset. It contains 50 unique query embeddings along with their manually assigned relevance annotations to documents from the dataset. • annealings.py : This module contains all the functions used in our Quantum and Simulated
Annealing codes. As well as in our Hybrid Algorithm. • clustering-two-algorithms.ipynb : This notebook presents two algorithms.The first one involves executing K-medoids clustering followed by Quantum Annealing on the derived medoids. In the second approach, we executed Classical Annealing prior to implementing Quantum Annealing on the obtained medoids. • clustering.ipynb : This notebook performs clustering using Simulated or Hybrid Annealing, utilizing reduced data obtained through point-pairing clustering. • hybrid_algorithm.py : In this notebook, we split the data into one-thirty-second of its original size using a function named ’half_points’, which clusters through point-pairing. Subsequently, we performed Hybrid Annealing using the LeapHybridSampler function on the downsized data. • submissions/ : This directory holds .txt files with the cluster medoids derived from each algorithm.
We assessed clusters with = 15, 25, and 50. • query_results/ : This folder contains the query results and the nDCG@10 metric evaluated in our submissions, which have been provided to us by the organizers.
Our findings, summarized in Table 1, provide valuable insights into the performance of various clustering approaches, particularly the hierarchical methods combining classical and quantum techniques. In particular, for the hybrid annealing (hybrid) method provided by the D-Wave machine, it should be emphasized that because of the restricted computational time available in the laboratory, we considered the minimum time required to execute the hybrid method based on the number of vectors. Within these constraints, the hybrid method included with D-Wave, despite its built-in optimization, did not outperform the classical simulated annealing (simulated) approach. This suggests that the current state of the hybrid quantum-classical algorithm in D-Wave may require further refinements to fully leverage the potential advantages of quantum annealing when dealing with limited computational resources.
Among the hierarchical methods (+) explored, the point-pair clustering (pp) for the initial clustering approach stands out for its simplicity and ease of implementation. By initially reducing the size of the dataset using point-pair clustering and subsequently applying quantum annealing, this method ofers a straightforward way to handle larger datasets while harnessing the power of quantum computing. However, our experiments reveal that the point-pair clustering approach does not yield the best results in terms of clustering quality. In contrast, employing k-medoids for the initial clustering step prior to quantum annealing leads to superior performance. This finding highlights the importance of selecting an appropriate classical clustering algorithm to efectively reduce the problem size and provide a solid foundation for the quantum annealing process.
Notably, the best results were obtained by combining classical simulated annealing for the initial clustering followed by quantum annealing (quantum) for further optimization. This two-step approach consistently outperformed other methods across diferent values of k (number of clusters). The simulated+quantum method achieved the lowest Davies-Bouldin index of 4.6798 and the highest nDCG@10 score of 0.5349 when using 50 clusters. These results underscore the synergistic efect of leveraging both classical and quantum techniques in a hierarchical manner. The initial simulated annealing step efectively reduces the problem complexity, allowing the quantum annealing process to refine and optimize the clustering solution.
This paper explores the use of quantum annealing for clustering document embeddings, as part of Task 2 in the qCLEF lab at CLEF 2024. To address the limitations of current quantum hardware and the restricted QPU time available in the laboratory setting, we proposed a hierarchical approach that combines classical pre-processing with quantum annealing, showing promising results. The performance of simulated annealing models was robust, as reflected in the Davies-Bouldin (DB) index. However, models combining simulated and quantum annealing slightly surpassed the purely classical approach in cluster quality. These findings highlight the potential of quantum annealing in enhancing cluster quality.
Our results highlight the advantages of a hierarchical approach, which addresses the limitations of current quantum technology by first reducing the problem size using classical methods before applying quantum annealing. This approach not only optimizes the use of scarce quantum resources, but also facilitates the handling of larger datasets. Future research should focus on improving these techniques by developing more advanced pre-processing methods to enhance the quantum annealing process. Exploring advanced dimensionality reduction techniques, similar to those used in Task 1 of the qCLEF lab, can improve eficiency to some extent. But, it is important to note that in the case of our clustering formulation, the size of the problem mainly depends on the number of documents and not in the number of their features. However, further research in this direction could help overcome hardware limitations.
Finally, fine-tuning the quantum annealing parameters, such as the annealing time and the number of reads, could yield additional improvements in clustering quality. As quantum computing technology continues to evolve, the development of more advanced quantum algorithms and hardware advancements will likely enhance the scalability and eficiency of these methods. In conclusion, our study demonstrates the potential of quantum annealing to enhance clustering performance for IR and RS. The hierarchical model we propose provides a viable solution to the challenges posed by current quantum hardware. By continuing to refine hierarchical methods, investigating advanced preprocessing techniques, and leveraging advances in quantum computing technology, we can harness the power of quantum annealing to tackle the complex challenges of clustering large-scale data in the field of IR and RS. systems and optimization problems, Quantum Information Processing 16 (2017) 153. URL: https: //doi.org/10.1007/s11128-017-1600-4. doi:10.1007/s11128-017-1600-4. [23] R. Bhagawati, T. Subramanian, An approach of a quantum-inspired document ranking algorithm by using feature selection methodology, International Journal of Information Technology 15 (2023) 4041–4053. URL: https://doi.org/10.1007/s41870-023-01543-w. doi:10.1007/ s41870-023-01543-w. [24] M. Ferrari Dacrema, F. Moroni, R. Nembrini, N. Ferro, G. Faggioli, P. Cremonesi, Towards feature selection for ranking and classification exploiting quantum annealers, in: Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR ’22, Association for Computing Machinery, New York, NY, USA, 2022, p. 2814–2824. URL: https://doi.org/10.1145/3477495.3531755. doi:10.1145/3477495.3531755. [25] R. Nembrini, M. Ferrari Dacrema, P. Cremonesi, Feature selection for recommender systems with quantum computing, Entropy 23 (2021). URL: https://www.mdpi.com/1099-4300/23/8/970. doi:10.3390/e23080970. [26] M. Ferrari Dacrema, N. Felicioni, P. Cremonesi, Optimizing the selection of recommendation carousels with quantum computing, in: Proceedings of the 15th ACM Conference on Recommender Systems, RecSys ’21, Association for Computing Machinery, New York, NY, USA, 2021, p. 691–696.
URL: https://doi.org/10.1145/3460231.3478853. doi:10.1145/3460231.3478853. [27] B. Fauseweh, Quantum many-body simulations on digital quantum computers: State-of-the-art and future challenges, Nature Communications 15 (2024) 2123. URL: https://doi.org/10.1038/ s41467-024-46402-9. doi:10.1038/s41467-024-46402-9.