Topological data analysis on noisy quantum computers
- URL: http://arxiv.org/abs/2209.09371v4
- Date: Tue, 19 Mar 2024 20:41:32 GMT
- Title: Topological data analysis on noisy quantum computers
- Authors: Ismail Yunus Akhalwaya, Shashanka Ubaru, Kenneth L. Clarkson, Mark S. Squillante, Vishnu Jejjala, Yang-Hui He, Kugendran Naidoo, Vasileios Kalantzis, Lior Horesh,
- Abstract summary: Topological data analysis (TDA) is a powerful technique for extracting complex and valuable shape-related summaries of high-dimensional data.
The computational demands of classical algorithms for computing TDA are exorbitant, and quickly become impractical for high-order characteristics.
We present a fully implemented end-to-end quantum machine learning algorithm that is applicable to high-dimensional classical data.
- Score: 11.975008559320875
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Topological data analysis (TDA) is a powerful technique for extracting complex and valuable shape-related summaries of high-dimensional data. However, the computational demands of classical algorithms for computing TDA are exorbitant, and quickly become impractical for high-order characteristics. Quantum computers offer the potential of achieving significant speedup for certain computational problems. Indeed, TDA has been purported to be one such problem, yet, quantum computing algorithms proposed for the problem, such as the original Quantum TDA (QTDA) formulation by Lloyd, Garnerone and Zanardi, require fault-tolerance qualifications that are currently unavailable. In this study, we present NISQ-TDA, a fully implemented end-to-end quantum machine learning algorithm needing only a short circuit-depth, that is applicable to high-dimensional classical data, and with provable asymptotic speedup for certain classes of problems. The algorithm neither suffers from the data-loading problem nor does it need to store the input data on the quantum computer explicitly. The algorithm was successfully executed on quantum computing devices, as well as on noisy quantum simulators, applied to small datasets. Preliminary empirical results suggest that the algorithm is robust to noise.
Related papers
- Identifying Bottlenecks of NISQ-friendly HHL algorithms [0.0]
We study noise resilience of NISQ-adaptation Iterative QPE and its HHL algorithm.
Results indicate that noise mitigation techniques, such as Qiskit readout and Mthree readout packages, are insufficient for enabling results recovery even in the small instances tested here.
arXiv Detail & Related papers (2024-06-10T14:11:27Z) - Classification of the Fashion-MNIST Dataset on a Quantum Computer [0.0]
Conventional methods for encoding classical data into quantum computers are too costly and limit the scale of feasible experiments on current hardware.
We propose an improved variational algorithm that prepares the encoded data using circuits that fit the native gate set and topology of currently available quantum computers.
We deploy simple quantum variational classifiers trained on the encoded dataset on a current quantum computer ibmq-kolkata and achieve moderate accuracies.
arXiv Detail & Related papers (2024-03-04T19:01:14Z) - Probabilistic Sampling of Balanced K-Means using Adiabatic Quantum Computing [93.83016310295804]
AQCs allow to implement problems of research interest, which has sparked the development of quantum representations for computer vision tasks.
In this work, we explore the potential of using this information for probabilistic balanced k-means clustering.
Instead of discarding non-optimal solutions, we propose to use them to compute calibrated posterior probabilities with little additional compute cost.
This allows us to identify ambiguous solutions and data points, which we demonstrate on a D-Wave AQC on synthetic tasks and real visual data.
arXiv Detail & Related papers (2023-10-18T17:59:45Z) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem.
The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
arXiv Detail & Related papers (2023-04-18T11:57:15Z) - Solving various NP-Hard problems using exponentially fewer qubits on a
Quantum Computer [0.0]
NP-hard problems are not believed to be exactly solvable through general time algorithms.
In this paper, we build upon a proprietary methodology which logarithmically scales with problem size.
These algorithms are tested on a quantum simulator with graph sizes of over a hundred nodes and on a real quantum computer up to graph sizes of 256.
arXiv Detail & Related papers (2023-01-17T16:03:33Z) - Accelerating the training of single-layer binary neural networks using
the HHL quantum algorithm [58.720142291102135]
We show that useful information can be extracted from the quantum-mechanical implementation of Harrow-Hassidim-Lloyd (HHL)
This paper shows, however, that useful information can be extracted from the quantum-mechanical implementation of HHL, and used to reduce the complexity of finding the solution on the classical side.
arXiv Detail & Related papers (2022-10-23T11:58:05Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach.
We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers.
We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
arXiv Detail & Related papers (2022-09-28T17:53:25Z) - Iterative Qubits Management for Quantum Index Searching in a Hybrid
System [56.39703478198019]
IQuCS aims at index searching and counting in a quantum-classical hybrid system.
We implement IQuCS with Qiskit and conduct intensive experiments.
Results demonstrate that it reduces qubits consumption by up to 66.2%.
arXiv Detail & Related papers (2022-09-22T21:54:28Z) - Noisy intermediate-scale quantum (NISQ) algorithms [0.5325753548715747]
A universal fault-tolerant quantum computer that can solve efficiently problems such as integer factorization and unstructured database search requires millions of qubits with low error rates and long coherence times.
While the experimental advancement towards realizing such devices will potentially take decades of research, noisy intermediate-scale quantum (NISQ) computers already exist.
These computers are composed of hundreds of noisy qubits, i.e. qubits that are not error-corrected, and therefore perform imperfect operations in a limited coherence time.
arXiv Detail & Related papers (2021-01-21T05:27:34Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem.
We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
arXiv Detail & Related papers (2020-09-15T18:17:27Z)
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.