Small quantum computers and large classical data sets

• URL: http://arxiv.org/abs/2004.00026v1
• Date: Tue, 31 Mar 2020 18:00:16 GMT
• Title: Small quantum computers and large classical data sets
• Authors: Aram W. Harrow
• Abstract summary: We introduce hybrid classical-quantum algorithms for problems involving a large classical data set X and a space of models Y. These algorithms use data reduction techniques to construct a weighted subset of X called a coreset that yields approximately the same loss for each model. Concrete applications include k-means clustering, logistical regression, zero-sum games and boosting.
• Score: 2.8174125805742416
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce hybrid classical-quantum algorithms for problems involving a large classical data set X and a space of models Y such that a quantum computer has superposition access to Y but not X. These algorithms use data reduction techniques to construct a weighted subset of X called a coreset that yields approximately the same loss for each model. The coreset can be constructed by the classical computer alone, or via an interactive protocol in which the outputs of the quantum computer are used to help decide which elements of X to use. By using the quantum computer to perform Grover search or rejection sampling, this yields quantum speedups for maximum likelihood estimation, Bayesian inference and saddle-point optimization. Concrete applications include k-means clustering, logistical regression, zero-sum games and boosting.

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 Machine Learning: Quantum Kernel Methods [0.0]
  Kernel methods are a powerful and popular technique in classical Machine Learning. The use of a quantum feature space that can only be calculated efficiently on a quantum computer potentially allows for deriving a quantum advantage. A data dependent projected quantum kernel was shown to provide significant advantage over classical kernels.
  arXiv  Detail & Related papers  (2024-05-02T23:45:29Z)
• Big data applications on small quantum computers [0.0]
  Coresets allow for a succinct description of large datasets and their solution in a computational task is competitive with the solution on the original dataset. We apply the coreset method in three different well-studied classical machine learning problems, namely Divisive Clustering, 3-means Clustering, and Gaussian Model Clustering. We show that our approach provides comparable performance to classical solvers.
  arXiv  Detail & Related papers  (2024-02-02T16:15:55Z)
• The Basis of Design Tools for Quantum Computing: Arrays, Decision Diagrams, Tensor Networks, and ZX-Calculus [55.58528469973086]
  Quantum computers promise to efficiently solve important problems classical computers never will. A fully automated quantum software stack needs to be developed. This work provides a look "under the hood" of today's tools and showcases how these means are utilized in them, e.g., for simulation, compilation, and verification of quantum circuits.
  arXiv  Detail & Related papers  (2023-01-10T19:00:00Z)
• 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)
• 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)
• Quantum Machine Learning with SQUID [64.53556573827525]
  We present the Scaled QUantum IDentifier (SQUID), an open-source framework for exploring hybrid Quantum-Classical algorithms for classification problems. We provide examples of using SQUID in a standard binary classification problem from the popular MNIST dataset.
  arXiv  Detail & Related papers  (2021-04-30T21:34:11Z)
• Error mitigation and quantum-assisted simulation in the error corrected regime [77.34726150561087]
  A standard approach to quantum computing is based on the idea of promoting a classically simulable and fault-tolerant set of operations. We show how the addition of noisy magic resources allows one to boost classical quasiprobability simulations of a quantum circuit.
  arXiv  Detail & Related papers  (2021-03-12T20:58:41Z)
• Unsupervised Event Classification with Graphs on Classical and Photonic Quantum Computers [0.0]
  Photonic Quantum Computers provides several benefits over the discrete qubit-based paradigm of quantum computing. We build an anomaly detection model to use on searches for New Physics. We present a novel method of anomaly detection, combining the use of Gaussian Boson Sampling and a quantum extension to K-means known as Q-means.
  arXiv  Detail & Related papers  (2021-03-05T19:02:31Z)
• Generation of High-Resolution Handwritten Digits with an Ion-Trap Quantum Computer [55.41644538483948]
  We implement a quantum-circuit based generative model to learn and sample the prior distribution of a Generative Adversarial Network. We train this hybrid algorithm on an ion-trap device based on $171$Yb$+$ ion qubits to generate high-quality images.
  arXiv  Detail & Related papers  (2020-12-07T18:51:28Z)
• Coreset Clustering on Small Quantum Computers [3.4075213885825377]
  Recent work by Harrow introduces a new paradigm in hybrid quantum-classical computing. We investigate using this paradigm to perform $k$-means clustering on near-term quantum computers. We find data sets where both coresets and QAOA work well--which is necessary for a quantum advantage over $k$-means on the entire data set--appears to be challenging.
  arXiv  Detail & Related papers  (2020-04-30T17:19:19Z)

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.