Information-theoretic bounds on quantum advantage in machine learning

• URL: http://arxiv.org/abs/2101.02464v2
• Date: Fri, 2 Apr 2021 00:26:59 GMT
• Title: Information-theoretic bounds on quantum advantage in machine learning
• Authors: Hsin-Yuan Huang, Richard Kueng, John Preskill
• Abstract summary: We study the performance of classical and quantum machine learning (ML) models in predicting outcomes of physical experiments. For any input distribution $mathcalD(x)$, a classical ML model can provide accurate predictions on average by accessing $mathcalE$ a number of times comparable to the optimal quantum ML model.
• Score: 6.488575826304023
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the performance of classical and quantum machine learning (ML) models in predicting outcomes of physical experiments. The experiments depend on an input parameter $x$ and involve execution of a (possibly unknown) quantum process $\mathcal{E}$. Our figure of merit is the number of runs of $\mathcal{E}$ required to achieve a desired prediction performance. We consider classical ML models that perform a measurement and record the classical outcome after each run of $\mathcal{E}$, and quantum ML models that can access $\mathcal{E}$ coherently to acquire quantum data; the classical or quantum data is then used to predict outcomes of future experiments. We prove that for any input distribution $\mathcal{D}(x)$, a classical ML model can provide accurate predictions on average by accessing $\mathcal{E}$ a number of times comparable to the optimal quantum ML model. In contrast, for achieving accurate prediction on all inputs, we prove that exponential quantum advantage is possible. For example, to predict expectations of all Pauli observables in an $n$-qubit system $\rho$, classical ML models require $2^{\Omega(n)}$ copies of $\rho$, but we present a quantum ML model using only $\mathcal{O}(n)$ copies. Our results clarify where quantum advantage is possible and highlight the potential for classical ML models to address challenging quantum problems in physics and chemistry.

Related papers

• Predicting adaptively chosen observables in quantum systems [1.1562071835482224]
  This work investigates the adaptive setting for three classes of observables: local, Pauli, and bounded-Frobenius-norm observables. We prove that $Omega(sqrtM)$ samples of an arbitrarily large unknown quantum state are necessary to predict expectation values of $M$ adaptively chosen local and Pauli observables.
  arXiv  Detail & Related papers  (2024-10-20T20:45:10Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Training Quantum Boltzmann Machines with the $β$-Variational Quantum Eigensolver [0.3670008893193884]
  The quantum Boltzmann machine (QBM) is a generative machine learning model for both classical data and quantum states. We show that low-rank representations obtained by $beta$-VQE provide an efficient way to learn low-rank target states. We implement a trained model on a physical quantum device.
  arXiv  Detail & Related papers  (2023-04-17T21:56:52Z)
• Improved machine learning algorithm for predicting ground state properties [3.156207648146739]
  We give a classical machine learning (ML) algorithm for predicting ground state properties with an inductive bias encoding geometric locality. The proposed ML model can efficiently predict ground state properties of an $n$-qubit gapped local Hamiltonian after learning from only $mathcalO(log(n))$ data.
  arXiv  Detail & Related papers  (2023-01-30T18:40:07Z)
• Validation tests of GBS quantum computers give evidence for quantum advantage with a decoherent target [62.997667081978825]
  We use positive-P phase-space simulations of grouped count probabilities as a fingerprint for verifying multi-mode data. We show how one can disprove faked data, and apply this to a classical count algorithm.
  arXiv  Detail & Related papers  (2022-11-07T12:00:45Z)
• Theory of Quantum Generative Learning Models with Maximum Mean Discrepancy [67.02951777522547]
  We study learnability of quantum circuit Born machines (QCBMs) and quantum generative adversarial networks (QGANs) We first analyze the generalization ability of QCBMs and identify their superiorities when the quantum devices can directly access the target distribution. Next, we prove how the generalization error bound of QGANs depends on the employed Ansatz, the number of qudits, and input states.
  arXiv  Detail & Related papers  (2022-05-10T08:05:59Z)
• About the description of physical reality of Bell's experiment [91.3755431537592]
  A hidden variables model complying with the simplest form of Local Realism was recently introduced. It reproduces Quantum Mechanics' predictions for an even ideally perfect Bell's experiment. A new type of quantum computer does not exist yet, not even in theory.
  arXiv  Detail & Related papers  (2021-09-06T15:55:13Z)
• Generalization in Quantum Machine Learning: a Quantum Information Perspective [0.0]
  We show how different properties of $Q$ affect classification accuracy and generalization. We introduce a quantum version of the Information Bottleneck principle that allows us to explore the various tradeoffs between accuracy and generalization.
  arXiv  Detail & Related papers  (2021-02-17T19:35:21Z)
• Embedding classical dynamics in a quantum computer [0.0]
  We develop a framework for simulating measure-preserving, ergodic dynamical systems on a quantum computer. Our approach provides a new operator-theoretic representation of classical dynamics. We present simulated quantum circuit experiments in Qiskit Aer, as well as actual experiments on the IBM Quantum System One.
  arXiv  Detail & Related papers  (2020-12-11T03:25:48Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)
• Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
  We give scalable, explicit digital quantum algorithms to simulate the lattice Schwinger model in both NISQ and fault-tolerant settings. In lattice units, we find a Schwinger model on $N/2$ physical sites with coupling constant $x-1/2$ and electric field cutoff $x-1/2Lambda$. We estimate observables which we cost in both the NISQ and fault-tolerant settings by assuming a simple target observable---the mean pair density.
  arXiv  Detail & Related papers  (2020-02-25T19:18:36Z)

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.