Quantum Clustering with k-Means: a Hybrid Approach
- URL: http://arxiv.org/abs/2212.06691v2
- Date: Thu, 15 Dec 2022 08:35:42 GMT
- Title: Quantum Clustering with k-Means: a Hybrid Approach
- Authors: Alessandro Poggiali, Alessandro Berti, Anna Bernasconi, Gianna M. Del
Corso, Riccardo Guidotti
- Abstract summary: We design, implement, and evaluate three hybrid quantum k-Means algorithms.
We exploit quantum phenomena to speed up the computation of distances.
We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
- Score: 117.4705494502186
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Quantum computing is a promising paradigm based on quantum theory for
performing fast computations. Quantum algorithms are expected to surpass their
classical counterparts in terms of computational complexity for certain tasks,
including machine learning. In this paper, we design, implement, and evaluate
three hybrid quantum k-Means algorithms, exploiting different degree of
parallelism. Indeed, each algorithm incrementally leverages quantum parallelism
to reduce the complexity of the cluster assignment step up to a constant cost.
In particular, we exploit quantum phenomena to speed up the computation of
distances. The core idea is that the computation of distances between records
and centroids can be executed simultaneously, thus saving time, especially for
big datasets. We show that our hybrid quantum k-Means algorithms can be more
efficient than the classical version, still obtaining comparable clustering
results.
Related papers
- Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties?
We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d.
We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
arXiv Detail & Related papers (2024-08-22T08:21:28Z) - Parallel Quantum Computing Simulations via Quantum Accelerator Platform Virtualization [44.99833362998488]
We present a model for parallelizing simulation of quantum circuit executions.
The model can take advantage of its backend-agnostic features, enabling parallel quantum circuit execution over any target backend.
arXiv Detail & Related papers (2024-06-05T17:16:07Z) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
Quantum computing sets the foundation for new ways of designing algorithms.
New challenges arise concerning which field quantum speedup can be achieved.
Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
arXiv Detail & Related papers (2024-02-26T09:32:07Z) - A density-matrix renormalization group algorithm for simulating quantum
circuits with a finite fidelity [3.965473736150699]
We develop a density-matrix renormalization group (DMRG) algorithm for the simulation of quantum circuits.
For small circuit depths, the technique is exact and equivalent to other matrix product state (MPS) based techniques.
arXiv Detail & Related papers (2022-07-12T15:28:55Z) - Variational Quantum and Quantum-Inspired Clustering [0.0]
We present a quantum algorithm for clustering data based on a variational quantum circuit.
The algorithm allows to classify data into many clusters, and can easily be implemented in few-qubit Noisy Intermediate-Scale Quantum (NISQ) devices.
arXiv Detail & Related papers (2022-06-20T17:02:19Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle.
We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm.
We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z) - Benchmarking Small-Scale Quantum Devices on Computing Graph Edit
Distance [52.77024349608834]
Graph Edit Distance (GED) measures the degree of (dis)similarity between two graphs in terms of the operations needed to make them identical.
In this paper we present a comparative study of two quantum approaches to computing GED.
arXiv Detail & Related papers (2021-11-19T12:35:26Z) - Multiple Query Optimization using a Hybrid Approach of Classical and
Quantum Computing [1.7077661158850292]
We tackle the multiple query optimization problem (MQO) which is an important NP-hard problem in the area of data-intensive problems.
We propose a novel hybrid classical-quantum algorithm to solve the MQO on a gate-based quantum computer.
Our algorithm shows a qubit efficiency of close to 99% which is almost a factor of 2 higher compared to the state of the art implementation.
arXiv Detail & Related papers (2021-07-22T08:12:49Z) - Quantum Compiling by Deep Reinforcement Learning [30.189226681406392]
The architecture of circuital quantum computers requires layers devoted to compiling high-level quantum algorithms into lower-level circuits of quantum gates.
The general problem of quantum compiling is to approximate any unitary transformation that describes the quantum computation, as a sequence of elements selected from a finite base of universal quantum gates.
We exploit the deep reinforcement learning method as an alternative strategy, which has a significantly different trade-off between search time and exploitation time.
arXiv Detail & Related papers (2021-05-31T15:32:15Z) - Quantum K-medians Algorithm Using Parallel Euclidean Distance Estimator [0.0]
This paper proposes an efficient quantum k-medians clustering algorithm using the powerful quantum Euclidean estimator algorithm.
The proposed quantum k-medians algorithm has provided an exponential speed up as compared to the classical version of it.
arXiv Detail & Related papers (2020-12-21T06:38:20Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.