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 information-processing abilities. Unprecedented quantum advantages have been identified, such as Shor’s polynomial-time quantum algorithm for factorization, which compromises the widely-used 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 Prakash | 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 in-depth 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 - (slides) |
09:50am - 10:40am |
Elad Hazan - Efficient Optimization for Machine Learning: Beyond Stochastic Gradient Descent
(abstract)
Abstract: In this talk we will describe recent advances in optimization that gave rise to state-of-the-art 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 Quantum-enhanced Artificial Intelligence
(abstract)
Abstract: Artificial intelligence (AI) is a heavily overloaded term, which historically pertains to the development of human-level 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 quantum-enhanced 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)
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 so-called VC-dimension 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 non-zero 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 coupon-collector problem and show how quantum examples give a logarithmic-improvement 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 - Quantum Speed-up for SDPs and Kernel Learning
(abstract)
Abstract:
I'll discuss recent results on solving semidefinite programming with
quantum computers, including a quantum speed-up for the Goemans-Williamson
relaxation of Max-Cut and a proposal for achieving speed-ups in
NISQ devices. I will also show how the quantum algorithm can be
used to learn Kernel matrices in support vector machines.
|
10:40am - 11:30am |
Furong Huang - Discovery of Latent Factors in High-dimensional Data Using Tensor Methods
(abstract)
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 non-convexity 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 non-convexity of the objective. I will then discuss large-scale 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 state-of-art 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 Prakash - A Quantum Interior Point Method for LPs and SDPs
(abstract)
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)
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 well-conditioned, 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)
Abstract: We consider a generic framework of optimization algorithms based on gradient descent. We develop a quantum algorithm that computes the gradient of a multi-variate real-valued 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 phase-query model, our gradient computation algorithm has optimal query complexity up to poly-logarithmic factors, for a particular class of smooth functions. Moreover, we show that for low-degree 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 auto-encoders, variational quantum eigensolvers (VQE), and quantum approximate optimization algorithms (QAOA).
|
Free afternoon. |
|
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)
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 model-based view to GANs..
|
10:40am - 11:30am |
Eleanor G. Rieffel - Sampling and thermalization on NISQ processsors and beyond
(abstract)
Abstract: In the first part of the talk, I will discuss recent results obtained on the 2000Q D-Wave quantum annealer, which made use of the recently added pause and reverse annealing features. These results, together with theory, provide insights into thermalization and Boltzmann sampling. This work answers some questions while opening up others. In the second part of the talk, I will look more broadly at the relationship between machine learning, sampling, and quantum algorithms, touching on sampling from non-Boltzmann distributions, sampling on NISQ processors other than quantum annealers, and quantum effects that could be harnessed for sampling. The talk concludes with a discussion of open questions and future work.
|
Afternoon Session (1:30pm - 3:30pm) Chair: Eleanor G. Rieffel |
|
01:30pm - 02:20pm |
Kristan Temme - Supervised Learning with Quantum Enhanced Feature Spaces
(abstract)
Abstract: Near-term 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 fault-tolerant 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)
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 two-qubit 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 quantum-classical 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 - Quantum generative adversarial networks
(abstract)
Abstract:
Abstract: In generative adversarial learning, a generator attempts to generate `fake data' to fool a discriminator, who in turn tries to distinguish
between the fake data and the real data. The learning process can be regarded as an adaptive game, which converges to a fixed point
where the generator generates data with the same statistics as the real data. This talk investigates the quantum version of generative
adversarial networks, where the data may be classical or quantum, and the generator and discriminator may have access to quantum
information processing. I show that the fully quantum adversarial learning game converges to a point where the generator successfully
mimics the quantum data, but that without full quantum capability, the generator will fail.
|
10:40am - 11:30am |
Scott Aaronson - Gentle Measurement of Quantum States and Differential Privacy
(abstract)
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 so-called "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 - A new algorithm for product decomposition in quantum signal processing
(abstract)
Abstract: By exploring the algebraic structure for the set of periodic functions that arise in quantum signal processing, we design a new product decomposition algorithm. We provide experimental evidence that in settings where high-precision arithmetics is not available, our algorithm works more efficiently than previous ones.
|
02:40pm - 03:30pm |
Open Problem Session II + Closing Remarks (summary of open problems)
|
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 quics-coordinator@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, quantum-enhanced 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.
