中央研究院 資訊科學研究所

活動訊息

友善列印

列印可使用瀏覽器提供的(Ctrl+P)功能

Information-theoretic bounds on quantum advantage in machine learning

:::

Information-theoretic bounds on quantum advantage in machine learning

  • 講者黃信元 先生 (美國加州理工學院)
    邀請人:鐘楷閔
  • 時間2021-01-08 (Fri.) 10:30 – 12:30
  • 地點資訊所新館106演講廳
摘要

We compare the complexity of training classical and quantum machine learning (ML) models for predicting outcomes of physical experiments. The experiments depend on an input parameter x and involve the execution of a (possibly unknown) quantum process E. Our figure of merit is the number of runs of E needed during training, disregarding other measures of complexity. A classical ML performs a measurement and records the classical outcome after each run of E, while a quantum ML can access 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 D(x), a classical ML can provide accurate predictions on average by accessing E a number of times comparable to the optimal quantum ML. In contrast, for achieving accurate prediction on all inputs, we show that exponential quantum advantage exists in certain tasks. For example, to predict expectation values of all Pauli observables in an n-qubit system, we present a quantum ML using only O(n) data and prove that a classical ML requires 2^([@BackSlash]Omega(n)) data.