Manifold Learning for Dimensionality Reduction: Quantum Isomap algorithm
- URL: http://arxiv.org/abs/2212.03599v1
- Date: Wed, 7 Dec 2022 12:29:41 GMT
- Title: Manifold Learning for Dimensionality Reduction: Quantum Isomap algorithm
- Authors: WeiJun Feng and GongDe Guo and Kai Yu and Xin Zhang and Song Lin
- Abstract summary: Isomap algorithm is widely used in neuroimaging, spectral analysis and other fields.
We propose the quantum Isomap algorithm, which consists of two sub-algorithms.
The time complexity of quantum Isomap algorithm is $O(dNpolylogN)$.
- Score: 15.622577797491788
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Isomap algorithm is a representative manifold learning algorithm. The
algorithm simplifies the data analysis process and is widely used in
neuroimaging, spectral analysis and other fields. However, the classic Isomap
algorithm becomes unwieldy when dealing with large data sets. Our object is to
accelerate the classical algorithm with quantum computing, and propose the
quantum Isomap algorithm. The algorithm consists of two sub-algorithms. The
first one is the quantum Floyd algorithm, which calculates the shortest
distance for any two nodes. The other is quantum Isomap algorithm based on
quantum Floyd algorithm, which finds a low-dimensional representation for the
original high-dimensional data. Finally, we analyze that the quantum Floyd
algorithm achieves exponential speedup without sampling. In addition, the time
complexity of quantum Isomap algorithm is $O(dNpolylogN)$. Both algorithms
reduce the time complexity of classical algorithms.
Related papers
- Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices [7.174256268278207]
We propose a quantum algorithm inspired by the classical multi-row iteration method.
Our algorithm places less demand on the coefficient matrix, making it suitable for solving inconsistent systems.
arXiv Detail & Related papers (2024-09-06T03:32:02Z) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry.
The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time.
Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
arXiv Detail & Related papers (2024-05-02T10:29:06Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al.
We apply our algorithm to the quantum information bottleneck with three quantum systems.
Our numerical analysis shows that our algorithm is better than their algorithm.
arXiv Detail & Related papers (2023-11-19T00:06:11Z) - A simple quantum algorithm to efficiently prepare sparse states [0.0]
We show that the gate complexity is linear in the number of non-zero amplitudes in the state and quadratic in the number of qubits.
This is competitive with the best known algorithms for sparse state preparation.
arXiv Detail & Related papers (2023-10-30T07:05:15Z) - 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) - Quantum jet clustering with LHC simulated data [0.0]
Two new quantum algorithms might speed up classical jet clustering algorithms.
In the first two algorithms, an exponential speed up in dimensionality and data length can be achieved.
In the $k_T$ algorithm, a quantum version of the same order as FastJet is achieved.
arXiv Detail & Related papers (2022-09-19T10:51:13Z) - 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) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
Bilevel optimization has been widely applied in many important machine learning applications.
We propose two new algorithms for bilevel optimization.
We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
arXiv Detail & Related papers (2021-06-08T21:05:30Z) - An Online Algorithm for Maximum-Likelihood Quantum State Tomography [6.261444979025642]
We propose the first online algorithm for maximum-likelihood quantum state tomography.
The expected numerical error of the algorithm is $O(sqrt ( 1 / T ) D log D )$, where $T$ denotes the number of iterations.
arXiv Detail & Related papers (2020-12-31T08:21:50Z) - Efficient Algorithms for Causal Order Discovery in Quantum Networks [44.356294905844834]
Given black-box access to the input and output systems, we develop the first efficient quantum causal order discovery algorithm.
We model the causal order with quantum combs, and our algorithms output the order of inputs and outputs that the given process is compatible with.
Our algorithms will provide efficient ways to detect and optimize available transmission paths in quantum communication networks.
arXiv Detail & Related papers (2020-12-03T07:12:08Z)
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.