Thread by @fgrosshans

Now at #MCQS, Andrea Rocchetto, from @UCL @UniofOxford on «Machine learning in quantum information theory, a selection of results» #LTQI

@ucl @UniofOxford Andrea Rocchetto defines the PAC (porbabilistically aproximate correct) models, and defines the concept of PAC-learnable: a concept is PAC-learnable iff one can guess a good model for arbitrary input distributions
#LTQI #MCQS

@ucl @UniofOxford Andrea Rocchetto: PAC learning on quantum states. The goal is to guess σ havig the same probability ditribution under a binary POVM than the training set ρ. Aaronson proved in 2007 that the problem is really different from tomography. #LTQI #MCQS

@ucl @UniofOxford Andrea Rocchetto: σ is PAC learnable, but at an exponential complexity cost. “The information is there, but we cannot get it”.
In contrast, Stabiliser states are efficiently PAC-learnable
#LTQI #MCQS

@ucl @UniofOxford Andrea Rocchetto: it works by predicting the output of measurement without generating the states and/or the full stabilizer group. Only the commutation relations with the generators are checked
#LTQI #MCQS

@ucl @UniofOxford Andrea Rocchetto moves on to machine learning with a quantum computer #LTQI #MCQS

@ucl @UniofOxford Andrea Rocchetto looks at learning boolean function in disjunctive normal form (DNF)
Best classical algorithm is 2^Õ(n^⅓), learnung under product is quasipolynomial n^O(log(n))
and poly(n) under membership queries.
#LTQI #MCQS

@ucl @UniofOxford Andrea Rocchetto: A key tool in these classical results is the approximation of DNF with heavy Fourier coefficients.
Using the quantum Fourier transform (QFT) allows to accelerate this in the quantum setting.
#LTQI #MCQS

@ucl @UniofOxford Andrea Rocchetto: These result actually use µ-biased Fourier transform, which can be quantized and used in a quantum version of the Kushilevitz–Mansour algorithm #LTQI #MCQS

Andrea Rocchetto moves on to approximating Hamiltonian dynamics using Nyström method (arXiv:1804.02484 arxiv.org/abs/1804.02484 ). The goal here is a different classical simulation technique for quantum systems
#LTQI #MCQS

Andrea Rocchetto: Random linear transformation can be used for dimensionality reduction. The Nyström method use random projection to construct a low rank approximate version of a matrix #LTQI #MCQI

Andrea Rocchetto: H can be efficiently simulted if it is row-computable, row-searchable and has a bounded Froebenius norm.
Output: an efficient representation of exp(-iHt)[ψ⟩
#LTQI #MCQI

Andrea Rocchetto: an open question is to find physical Hamiltonians which respect the conditions of the theorem.
#LTQI #MQCS

Andrea Rocchetto moves on to learnign hard quantum states (
(arXiv:1710.00725 arxiv.org/abs/1710.00725 )
where he suses neural netwroks (Restricted/deep Boltzmann machines (RBMs /DBMs) to encode quantum states
#LTQI #MCQI

Andrea Rocchetto induced a deep generative models (variational autoencoders) for quantum states. Depth is useful, and allows a constant compression factor for hard states
#LTQI #MCQS

@ucl @UniofOxford Andrea Rocchetto’s talk on «Machine learning in quantum information theory, a selection of results» is available on