Quantum Algorithm for Computing Distances Between Subspaces
- URL: http://arxiv.org/abs/2308.15432v2
- Date: Tue, 30 Apr 2024 15:39:32 GMT
- Title: Quantum Algorithm for Computing Distances Between Subspaces
- Authors: Nhat A. Nghiem,
- Abstract summary: We provide a quantum algorithm for estimating two kinds of distance: Grassmann distance and ellipsoid distance.
Some extensions regarding estimating different kinds of distance are then discussed as a corollary of our main quantum algorithmic method.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Geometry and topology have generated impacts far beyond their pure mathematical primitive, providing a solid foundation for many applicable tools. Typically, real-world data are represented as vectors, forming a linear subspace for a given data collection. Computing distances between different subspaces is generally a computationally challenging problem with both theoretical and applicable consequences, as, for example, the results can be used to classify data from different categories. Fueled by the fast-growing development of quantum algorithms, we consider such problems in the quantum context and provide a quantum algorithm for estimating two kinds of distance: Grassmann distance and ellipsoid distance. Under appropriate assumptions and conditions, the speedup of our quantum algorithm is exponential with respect to both the dimension of the given data and the number of data points. Some extensions regarding estimating different kinds of distance are then discussed as a corollary of our main quantum algorithmic method.
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) - Quantum Distance Approximation for Persistence Diagrams [1.0062127381149395]
We explore the potential of quantum computers to estimate the distance between persistence diagrams.
We propose variational quantum algorithms for the Wasserstein distance as well as the $dc_p$ distance.
arXiv Detail & Related papers (2024-02-27T08:16:17Z) - Simulating Field Theories with Quantum Computers [1.0377683220196874]
We identify different sources of errors prevalent in various quantum processing units and discuss challenges to scale up the size of the computation.
We present benchmark results obtained on a variety of platforms and employ a range of error mitigation techniques to address coherent and incoherent noise.
arXiv Detail & Related papers (2024-01-03T20:07:31Z) - A quantum k-nearest neighbors algorithm based on the Euclidean distance
estimation [0.0]
This article introduces a novel quantum k-NN algorithm based on the Euclidean distance.
Specifically, the algorithm is characterised by a quantum encoding requiring a low number of qubits and a simple quantum circuit not involving oracles.
arXiv Detail & Related papers (2023-05-07T14:21:44Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
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.
arXiv Detail & Related papers (2022-12-13T16:04:16Z) - A streamlined quantum algorithm for topological data analysis with
exponentially fewer qubits [5.478764356647437]
We present an improved quantum algorithm for computing persistent Betti numbers.
We discuss whether quantum algorithms can achieve an exponential speedup for tasks of practical interest.
arXiv Detail & Related papers (2022-09-26T17:56:11Z) - Scalable approach to many-body localization via quantum data [69.3939291118954]
Many-body localization is a notoriously difficult phenomenon from quantum many-body physics.
We propose a flexible neural network based learning approach that circumvents any computationally expensive step.
Our approach can be applied to large-scale quantum experiments to provide new insights into quantum many-body physics.
arXiv Detail & Related papers (2022-02-17T19:00:09Z) - Numerical Simulations of Noisy Quantum Circuits for Computational
Chemistry [51.827942608832025]
Near-term quantum computers can calculate the ground-state properties of small molecules.
We show how the structure of the computational ansatz as well as the errors induced by device noise affect the calculation.
arXiv Detail & Related papers (2021-12-31T16:33:10Z) - 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) - Quantum Algorithms for Data Representation and Analysis [68.754953879193]
We provide quantum procedures that speed-up the solution of eigenproblems for data representation in machine learning.
The power and practical use of these subroutines is shown through new quantum algorithms, sublinear in the input matrix's size, for principal component analysis, correspondence analysis, and latent semantic analysis.
Results show that the run-time parameters that do not depend on the input's size are reasonable and that the error on the computed model is small, allowing for competitive classification performances.
arXiv Detail & Related papers (2021-04-19T00:41:43Z)
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.