Workshop on the intersection of Quantum Information and Machine Learning
Machine learning has fundamentally changed the way humans interact with and relate to data, and achieved remarkable successes in many application areas. However, this revolution faces increasing challenges due to limited computational power and the growing size of datasets. Information is fundamentally governed by the laws of physics, and quantum mechanics can enhance our informationprocessing abilities. Unprecedented quantum advantages have been identified, such as Shor’s polynomialtime quantum algorithm for factorization, which compromises the widelyused RSA cryptosystem. Motivated by this and other possible applications of quantum information, the study of the impact of quantum mechanics on information processing has become a major research area over the past two decades.
Considering these developments, the time is ripe to build bridges between machine learning and quantum information. The interaction between these areas naturally goes both ways: machine learning algorithms find application in understanding and controlling quantum systems and, on the other hand, quantum computational devices promise enhancement of the performance of machine learning algorithms for problems beyond the reach of classical computing. The intersection of these two areas offers great potential for both fields.
This workshop aims to foster interactions of experts from math, physics, and computer science for this interdisciplinary topic. We also aim to bring in research teams from industry as we envision that collaboration between academia and industry will be essential for research on this topic.
▶ Date: September 24 (Monday) to September 28 (Friday), 2018.
▶ Location: QuICS (Atlantic Building (ATL) 3100) at the University of Maryland, College Park. The workshop happens at ATL 3330.
▶ Contact: Have any question about the workshop? Please contact the organizer Xiaodi Wu (email).
Invited Speakers
Scott Aaronson  University of Texas, Austin 
Srinivasan Arunachalam  CWI, Amsterdam 
Fernando Brandao  Caltech 
Vedran Dunjko  University of Leiden 
Soheil Feizi  University of Maryland, College Park 
Elad Hazan  Princeton University 
Furong Huang  University of Maryland, College Park 
Norbert Linke  University of Maryland, College Park 
Seth Lloyd  MIT 
Anupam Praksah  CNRS & University Paris Diderot 7 
Eleanor G. Rieffel  NASA Ames Research Center 
Rolando Somma  Los Alamos National Laboratory 
Mario Szegedy  Aliyun 
Kristan Temme  IBM Waston 
Nathan Wiebe  Microsoft Research, Redmond 
Agenda
▶ Our workshop is one week long. We plan to schedule a relatively small number of talks to allow ample time for discussion and collaboration. There will be a free afternoon for indepth discussions or campus/laboratory visits, a poster session and an open question session.
September 24th (Monday)  
Morning Session (9:30am  10:40am) Chair: Xiaodi Wu 

09:30am  09:50am  Openning Remarks 
09:50am  10:40am 
Elad Hazan  Efficient Optimization for Machine Learning: Beyond Stochastic Gradient Descent
(abstract) watch
Abstract: In this talk we will describe recent advances in optimization that gave rise to stateoftheart algorithms in machine learning. While stochastic gradient descent is the workhorse behind the recent deep learning revolution, improving its performance both theoretically and in practice has proven challenging. We will explore recent innovations in stochastic second order methods and adaptive regularization that yield some of the fastest algorithms known.

Afternoon Session (1:30pm  3:30pm) Chair: Nathan Wiebe 

01:30pm  02:20pm 
Vedran Dunjko  A Route towards Quantumenhanced Artificial Intelligence
(abstract) watch
Abstract: Artificial intelligence (AI) is a heavily overloaded term, which historically pertains to the development of humanlevel machine intelligence. What is meant by intelligence is always fuzzy, and leads to various notions of AI.
In this talk we will focus on pragmatic flavours of AI, as discussed in the majority of modern AI research.
These include aspects of learning and planning, features of which have already been addressed, albeit individually, from the perspective of quantum information processing. Does this mean that all the building blocks of “quantum AI” are already present? How much can quantum computing help? in this talk we will reflect on aspects of quantum machine learning and of quantumenhanced search algorithms — including some recent results showing even small quantum computers can help — from the perspective of AI.

02:40pm  03:30pm 
Srinivasan Arunachalam  Strengths and weaknesses of quantum examples for learning
(abstract) watch
Abstract: Recently, there has been a lot of recent interest in quantum algorithms for machine learning. These try to improve over classical algorithms for generalizing or otherwise learning from given data (the data itself could also be quantum).
I will consider the following setting: Let C be concept class of Boolean functions f:{0,1}^n>{1,1}. In the classical learning model, a learner is given a (x,f(x)) sample where x is drawn according to a distribution D and quantumly an example would be a *superposition* sum_x sqrt{D(x)}x,c(x)>. The goal of the learner is output an hypothesis with error (from the unknown f) is at most eps. In this talk, I will describe a few instances where quantum examples help and when they dont. a) In the classical PAC model, D is unknown to the learner. Fundamental results in classical learning show that the classical sample complexity of a concept class C in the PAC model is tightly determined by the socalled VCdimension of C. Our main result is to show that exactly the same formula gives the quantum sample complexity, showing that quantum examples do not help in the PAC model of learning (nor in the related agnostic model). b) Let D be the uniform distribution, eps=0 (i.e., we need to *identity* f) and suppose C contains Boolean functions having at most k nonzero Fourier coefficients, then how many classical examples suffice to identity f? This question has been studied for over a decade under the name of sparse recovery and Fourier sampling, having applications in compressed sensing and the data stream model. Regev and Haviv (CCC'15) showed Theta(nk) classical samples suffice and are required to solve this problem. In this work, we solve this problem using O(k^{1.5}) quantum samples and show that Omega(k) quantum samples are necessary (importantly, it is independent of n!). c) I will also consider the couponcollector problem and show how quantum examples give a logarithmicimprovement over the classical algorithms that solve the coupon collector problem. Based on joint work with Ronald de Wolf and others.. 
September 25th (Tuesday)  
Morning Session (9:30am  11:30am) Chair: Rolando Somma 

09:30am  10:20am 
Fernando Brandao  TBA
(abstract) watch
Abstract: TBA.

10:40am  11:30am 
Furong Huang  Discovery of Latent Factors in Highdimensional Data Using Tensor Methods
(abstract) watch
Abstract: Latent or hidden variable models have applications in almost every domain, e.g., social network analysis, natural language processing, computer vision and computational biology. Training latent variable models is challenging due to nonconvexity of the likelihood objective function. An alternative method is based on the spectral decomposition of low order moment matrices and tensors. This versatile framework is guaranteed to estimate the correct model consistently. I will discuss my results on convergence to globally optimal solution for stochastic gradient descent, despite nonconvexity of the objective. I will then discuss largescale implementations (which are highly parallel and scalable) of spectral methods, carried out on CPU/GPU and Spark platforms. We obtain a gain in both accuracies and in running times by several orders of magnitude compared to the stateofart variational methods. I will discuss the following applications in detail: (1) learning hidden user commonalities (communities) in social networks, and (2) learning sentence embeddings for paraphrase detection using convolutional models.

Afternoon Session (1:30pm  3:30pm) Chair: Xiaodi Wu 

01:30pm  02:20pm 
Anupam Praksah  A Quantum Interior Point Method for LPs and SDPs
(abstract) watch
Abstract: We present a quantum interior point method with worst case running time $\widetilde{O}(\frac{n^{2.5}}{\xi^{2}} \mu \kappa^3 \log (1/\epsilon))$
for SDPs and $\widetilde{O}(\frac{n^{1.5}}{\xi^{2}} \mu \kappa^3 \log (1/\epsilon))$ for LPs, where the output of our algorithm is a pair of matrices $(S,Y)$
that are $\epsilon$optimal $\xi$approximate SDP solutions. The factor $\mu$ is at most $\sqrt{2}n$ for SDPs and $\sqrt{2n}$ for LP's, and $\kappa$
is an upper bound on the condition number of the intermediate solution matrices. For the case where the intermediate matrices for the interior point
method are well conditioned, our method provides a polynomial speedup over the best known classical SDP solvers and interior point based
LP solvers, which have a worst case running time of $O(n^{6})$ and $O(n^{3.5})$ respectively. Our results build upon recently developed
techniques for quantum linear algebra and pave the way for the development of quantum algorithms for a variety of applications in
optimization and machine learning.

02:40pm  03:30pm 
Open Problem Session I

September 26th (Wednesday)  
Morning Session (9:30am  11:30am) Chair: Gorjan Alagic 

09:30am  10:20am 
Rolando Somma  Quantum Algorithms for Systems of Linear Equations
(abstract) watch
Abstract: Harrow, Hassidim, and Lloyd (HHL) proved that, for a matrix A of dimension NxN and a vector b of dimension N, there exists a quantum algorithm that prepares a quantum state proportional to the solution of the linear system A.x=b. When the matrix A is sparse and wellconditioned, the HHL algorithm has complexity that is polynomial in 1/ε and log(N), where ε>0 is the precision. This result represents a quantum speedup with respect to classical algorithms.
In this talk I will describe improved quantum algorithms for the linear system’s problem with a significant reduction in complexity and other resources. One such quantum algorithm has complexity that depends logarithmically in 1/ε, exponentially improving the complexity dependence on precision while keeping essentially the same dependence on other parameters. The other quantum algorithm is based on quantum adiabatic evolutions and does not use complex subroutines like phase estimation or variable time amplitude amplification that require several ancillary qubits..

10:40am  11:30am 
Nathan Wiebe  Optimizing Quantum Optimization Algorithms via Faster Quantum Gradient Computation
(abstract) watch
Abstract: We consider a generic framework of optimization algorithms based on gradient descent. We develop a quantum algorithm that computes the gradient of a multivariate realvalued function by evaluating it at only a logarithmic number of points in superposition. Our algorithm is an improved version of Stephen Jordan's gradient computation algorithm, providing an approximation of the gradient ∇f with quadratically better dependence on the evaluation accuracy of f, for an important class of smooth functions. Furthermore, we show that most objective functions arising from quantum optimization procedures satisfy the necessary smoothness conditions, hence our algorithm provides a quadratic improvement in the complexity of computing their gradient. We also show that in a continuous phasequery model, our gradient computation algorithm has optimal query complexity up to polylogarithmic factors, for a particular class of smooth functions. Moreover, we show that for lowdegree multivariate polynomials our algorithm can provide exponential speedups compared to Jordan's algorithm in terms of the dimension d.
One of the technical challenges in applying our gradient computation procedure for quantum optimization problems is the need to convert between a probability oracle (which is common in quantum optimization procedures) and a phase oracle (which is common in quantum algorithms) of the objective function f. We provide efficient subroutines to perform this delicate interconversion between the two types of oracles incurring only a logarithmic overhead, which might be of independent interest. Finally, using these tools we improve the runtime of prior approaches for training quantum autoencoders, variational quantum eigensolvers (VQE), and quantum approximate optimization algorithms (QAOA). 
Free afternoon with an optional lab tour. 

Poster Session at QuICS from 3:00pm  5:00pm. 

September 27th (Thursday)  
Morning Session (9:30am  11:30am) Chair: Xin Wang 

09:30am  10:20am 
Soheil Feizi  Generative Adversarial Networks: Formulation, Design and Computation
(abstract) watch
Abstract: Learning a probability model from data is a fundamental problem in machine learning and statistics. A classical approach to this problem is to fit (approximately) an explicit probability model to the training data via a maximum likelihood estimation. Building off the success of deep learning, however, there has been another approach to this problem using Generative Adversarial Networks (GANs). GANs view this problem as a game between two sets of functions: a generator whose goal is to generate realistic fake samples and a discriminator whose goal is to distinguish between the real and fake samples. In this talk, I will explain challenges that we face in formulation, design and computation of GANs. Leveraging a connection between supervised and unsupervised learning, I will then elaborate how we can overcome these issues by proposing a modelbased view to GANs..

10:40am  11:30am 
Eleanor G. Rieffel  TBA
(abstract) watch
Abstract: TBA.

Afternoon Session (1:30pm  3:30pm) Chair: Eleanor G. Rieffel 

01:30pm  02:20pm 
Kristan Temme  Supervised Learning with Quantum Enhanced Feature Spaces
(abstract) watch
Abstract: Nearterm applications of early quantum devices rely on accurate estimates of expectation values to become relevant. Decoherence and gate errors lead to wrong estimates. This problem was, at least in theory, remedied with the advent of quantum error correction. However, the overhead that is needed to implement a fully faulttolerant gate set with current codes and current devices seems prohibitively large. In turn, steady progress is made in improving the quality of the quantum hardware and we believe that we can build machines in the near term that cannot be emulated by a conventional computer. In light of recent progress mitigating the effect of decoherence on expectation values, it becomes interesting to ask what these noisy devices can be used for. In this talk we will present our advances in finding quantum machine learning applications for noisy quantum computers. We propose, and experimentally implement, two classification algorithms on a superconducting processor. Both methods represent the feature space of the classification problem in terms of quantum states, taking advantage of the large dimensionality of Hilbert space. One method, the quantum variational classifier operates through using a variational quantum circuit to classify a training set in direct analogy to conventional SVMs. In the second, a quantum kernel estimator, we estimate the kernel function and optimize the classifier directly. The two methods present a new class of tools for exploring the applications of noisy intermediate scale quantum computers to machine learning..

02:40pm  03:30pm 
Norbert Linke  Quantum Machine Learning with Trapped Ions
(abstract) watch
Abstract: To realize the potential of quantum machine learning, a scalable hardware platform is required, for which trapped ions are a promising candidate. We present a modular quantum computing architecture comprised of a chain of 171Yb+ ions with individual Raman beam addressing and individual readout [1]. We use the transverse modes of motion in the chain to produce entangling gates between any qubit pair. This creates a fully connected system which can be configured to run any sequence of single and twoqubit gates, making it in effect an arbitrarily programmable quantum computer.
We have applied this versatile quantum system in a number of different demonstrations relating to machine learning in a quantumclassical hybrid approach, such as error mitigation in the processor itself [2], finding the ground state binding energy of the deuteron nucleus, the training of shallow circuits [3], and the preparation of quantum critical states using a quantum approximate optimization algorithm (QAOA) scheme. Recent results from these efforts, and concepts for scaling up the architecture will be discussed.
[1] S. Debnath et al., Nature 563:63 (2016) [2] A. Seif et al., J. Phys. B 51 174006 (2018) [3] M. Benedetti et al., arXiv:1801.07686 (2018) 
September 28th (Friday)  
Morning Session (9:30am  11:30am) Chair: Andrew Childs 

09:30am  10:20am 
Seth Lloyd  TBA
(abstract) watch
Abstract: TBA.

10:40am  11:30am 
Scott Aaronson  Gentle Measurement of Quantum States and Differential Privacy
(abstract) watch
Abstract: We prove a surprising connection between gentle measurement (where one wants to measure n quantum states, in a way that damages the states only by a little) and differential privacy (where one wants to query a database about n users, in a way that reveals only a little about any individual user). The connection is bidirectional, though with loss of parameters in going from DP to gentle measurement. By exploiting this connection, together with the Private Multiplicative Weights algorithm of Hardt and Rothblum, we're able to give a new protocol for socalled "shadow tomography" of quantum states, which improves over the parameters of a previous protocol for that task due to Aaronson, and which has the additional advantage of being "online" (that is, the measurements are processed one at a time).
Joint work with Guy Rothblum (Weizmann Institute); paper still in preparation.. 
Afternoon Session (1:30pm  3:30pm) Chair: Xiaodi Wu 

01:30pm  02:20pm 
Mario Szegedy  TBA
(abstract) watch
Abstract: TBA.

02:40pm  03:30pm 
Open Problem Session II (if applicable) + Closing Remarks

Logistics
The workshop is hosted at the Joint Center for Quantum Infomration and Computer Science (QuICS). Atlantic Building 3100, UMD.
Here are detailed directions and transportation options to the University of Maryland and QuICS.
For accommodations and other logistics information or questions, please email quicscoordinator@umiacs.umd.edu.
About QuICS and the University of Maryland
The Joint Center for Quantum Information and Computer Science (QuICS) is a partnership between the University of Maryland (UMD) and the National Institute of Standards and Technology (NIST). Located at the University of Maryland just outside of Washington, D.C., the center advances research and education in quantum computer science and quantum information theory. Ongoing projects at QuICS include theoretical and experimental research on quantum algorithms, quantum complexity theory, quantum communication, implementations of quantum information processing, quantum cryptography, quantumenhanced metrology, and more.
The University of Maryland is the state's flagship university and one of the nation's preeminent public research universities. A global leader in research, entrepreneurship, and innovation, the university is home to more than 37,000 students, 9,000 faculty and staff, and 250 academic programs. Its faculty includes three Nobel laureates, two Pulitzer Prize winners, 49 members of the national academies and scores of Fulbright scholars. The institution has a $1.7 billion operating budget, secures $500 million annually in external research funding and recently completed a $1 billion dollar fundraising campaign.