Machine Intelligence and Quantum Information Processing - quinfog

Machine Intelligence and Quantum Information Processing Peter Wittek ICFO-The Institute of Photonic Sciences and University of Bor˚ as

January 2017

AI and Machine Learning

Quantum-Enhanced Learning

Learning in QIP

Towards Quantum AI

Summary

Directions •Quantum algorithms in machine learning •Improved sample and computational complexity

Machine learning and artiﬁcial intelligence

Quantum information processing and quantum computing

•Reinforcement learning in control problems •Deep learning and neural networks as representation

Peter Wittek

Machine Intelligence and Quantum Information Processing



Learning in QIP

Towards Quantum AI

Summary

How do AI and machine learning relate?

Source: https://blogs.nvidia.com/blog/2016/07/29/ whats-difference-artificial-intelligence-machine-learning-deep-learning-ai/ Peter Wittek




Learning in QIP

Towards Quantum AI

Summary

What makes a good theory in the first place? Aristotle wrote in his Posterior Analytics (4th century B.C.) that “We may assume the superiority ceteris paribus [other things being equal] of the demonstration which derives from fewer postulates or hypotheses.” Occam’s razor (1300s): “Among competing hypotheses, the one with the fewest assumptions should be selected.”

Peter Wittek




Learning in QIP

Towards Quantum AI

Summary

Major schools of thought in machine learning and AI Connectionism: neural networks and empirical risk minimization. Structural risk minimization: support vector machines. Probabilistic inference: Bayesian and Markov networks. Symbolic AI: first-order logic or other form of formal reasoning.

Pneumonia

Class 1 Class 2 Decision surface Margin

Peter Wittek

Tuberculosis

Lung I nf iltrates XRay

Sputum Smear




Learning in QIP

Towards Quantum AI

Summary

Statistics and sample complexity Descriptive and inferential statistics. Assumptions derive from probability theory. Parameters enter through assumed probability distributions. It is often assumed that the data is generated by certain probability distributions described by a finite number of unknown parameters.

Law of large numbers. Concentration theorems.

Independent and identically distributed (IID) random variables. We can establish guarantees on accuracy based on the sample size. Example: metrology. Standard quantum limit: scales as 1/N. Heisenberg limit: scales as 1/N 2 . Peter Wittek




Learning in QIP

Towards Quantum AI

Summary

Symbolic AI and Entailment Knowledge base (KB) in first-order logic: Every referee is competent: ∀x,y (Referees(x,y)⇒Competent(x)) Referees of physicists are physicists: ∀x,y (Referees(x,y)∧Physicist(y)⇒Physicist(x)) Let us have a formula from outside the KB: F: Bob referees Alice. Bob is not competent. Referees(Bob, Alice)∧¬Competent(Bob) Problem of entailment: KBF. What about contradictions? Combinatorial explosion and uncertainty. What is computable? What is the computational complexity of entailment and inference? Optimization: interesting problems tend to be NP-hard. Peter Wittek




Learning in QIP

Towards Quantum AI

Summary

A Measure of Model Complexity: Rademacher Complexity Empirical Rademacher complexity of a set H of functions mapping X 7→ [a, b] ⊂ R, with a sample S = {X1 , . . . , XN }, where Xi ∼ X : # " m X 2 b S (H) = E sup σi h(Xi ) R N h∈H i=1

where σ1 , σ2 , . . . , σN are independent random variables such that P(σi = +1) = P(σi = −1) = 1/2 for i = 1, 2, . . . , N. Intuition: capacity of the learner, including ability to pick up random noise. Rademacher complexity: h i b S (H) Average over possible samples: RN (H) = ES R

Peter Wittek




Learning in QIP

Towards Quantum AI

Summary

The essence of statistical learning theory Elements of balance: Sample complexity. Computational complexity. Model complexity. Generalization bounds E (h) ≤ ES (h) + F (model complexity of function family H, N) H is the function family we optimize over. F goes to zero as N → ∞. IID assumption. E (h) is the error of the learned function h over the whole distribution given the sample. ES is the error on the sample, the training error, the empirical risk. Peter Wittek




Learning in QIP

Towards Quantum AI

Summary

What’s an easy problem? What’s a hard one? From easier to harder: Supervised learning: this is where deep learning shines.

Structure data.

Semi-supervised learning.

Unstructured data: text, images, video, LHC collisions. . .

Unsupervised learning. Generative models.

Semistructure data.

Reinforcement learning. the foundations of quantum physics are fermionic data processes that complete convergence of a result of the first environment. we finally articousl define a number of the contriting contraction of the constrained for any classical algorithm for quantum. . . Peter Wittek




Learning in QIP

Towards Quantum AI

Summary

How to get started with machine learning? By doing it: The lingua franca is Python. Sebastian Raschka: Python Machine Learning, along with its git repository. Learn a deep learning framework. Perhaps Keras is the easiest to pick up today (13/01/2017). Sign up to Kaggle and start running kernels. E.g., the quant-ph dataset.

Peter Wittek




Learning in QIP

Towards Quantum AI

Summary

Some synergies machine learning

quantum machine learning

quantum information processing

annealing quantum annealing

simulated annealing

markov chain monte-carlo

quantum BM

feed forward neural net

quantum perceptron

neural nets

quantum gibbs sampling

quantum topological algorithms

quantum PCA quantum SVM quantum NN classification quantum clustering quantum data fitting

Quantum ODE solvers

quantum rejection sampling / HHL control and metrology reinforcement learning

quantum control phase estimation hamiltonian learning

Peter Wittek

tomography




Learning in QIP

Towards Quantum AI

Summary

Quantum Data

Exponential speedup: Quantum principal component analysis and quantum singular value decomposition. Quantum support vector machines: sparsity lost. Topological data analysis. Core ideas: Quantum matrix inversion is fast: HHL algorithm. Simulation of sparse matrixes is efficient. Non-sparse density matrices reveal the eigenstructure exponentially faster than in classical algorithms.

Peter Wittek




Learning in QIP

Towards Quantum AI

Summary

Other gate-based models

Grover’s search as a building block: Discrete search space. Quantum associative memories. Quantum deep learning: Prepare-and-measure model for deep belief networks.

Peter Wittek




Learning in QIP

Towards Quantum AI

Summary

How about regression? Learning unitaries: Given N disposals of a black-box unitary, reproduce its effect K times. Inductive or transductive strategy? Counter-intuitively, inductive is optimal.

Unlabeled instances Class 1 Class 2

Peter Wittek




Learning in QIP

Towards Quantum AI

Summary

Quantum annealing and Gibbs sampling thermal annealing

quantum annealing

A

B

thermal state

Solve a nonconvex optimization directly: optimal sparsity of model. Generate samples of a Gibbs distribution: Boltzmann machines. Peter Wittek




Learning in QIP

Towards Quantum AI

Summary

Tensor networks and deep learning

Learn phases transitions. arXiv:1605.01735 ’Solve’ the many-body problem. arXiv:1606.02318 Peter Wittek




Learning in QIP

Towards Quantum AI

Summary

Foundational questions What does ’induction’ mean? Training and application phases. Translates to a non-signalling condition. Quantum de Finetti theorem for channels: asymptotic equivalence between classical and quantum cases. arXiv:1605.07541 Is there anything we can learn with quantum resources that we cannot with classical ones? A class of problems can be constructed. . . Complexity measures? Polynomial relationship between number of queries for classical learning problems. Sample complexity: constant factor difference in PAC setting. Peter Wittek




Learning in QIP

Towards Quantum AI

Summary

Neural Networks Implementations Towards a Feasible Implementation of Quantum Neural Networks Using Quantum Dots (2015). DOI:10.1063/1.4943622 Photonic Delay Systems as Machine Learning Implementations (2015). A Coherent Perceptron for All-Optical Learning (2015). DOI:10.1140/epjqt/s40507-015-0023-3 Adiabatic Quantum Optimization for Associative Memory Recall (2014). DOI:10.3389/fphy.2014.00079 Quantum pattern recognition with liquid-state nuclear magnetic resonance (2009). DOI:10.1103/PhysRevA.79.042321 Associative memory based image and object recognition by quantum holography (2004). DOI:10.1023/B:OPSY.0000047571.17774.8d Peter Wittek




Learning in QIP

Towards Quantum AI

Summary

Implementations of Not Neural Networks

Entanglement-Based Quantum Machine Learning (2014). K-means clustering, eight dimensions, photonic implementation. DOI:10.1103/physrevlett.114.110504 Experimental Realization of a Quantum Support Vector Machine (2014). Four-qubit NMR. DOI:10.1103/physrevlett.114.140504 On the Robustness of Bucket Brigade Quantum RAM (2015). DOI:10.1088/1367-2630/17/12/123010 And a suggestion with continuous-variable quantum optics: claimed exponential speedup. arXiv:1603.06222

Peter Wittek




Learning in QIP

Towards Quantum AI

Summary

Reinforcement and Supervised Learning in Quantum Control Reinforcement learning Why not use it for controlling the classical part of some quantum process? Adaptive quantum phase estimation (2010). Quantum computations with an agent (2014). Producing Bose-Einstein condensates (2015). How about quantum agents? (2015) Supervised learning Learning mapping gate-based models to spin systems (2015-2016) Recurrent neural networks in dynamic decoupling (2016). Peter Wittek




Learning in QIP

Towards Quantum AI

Summary

Reinforcement Learning in Adaptive Quantum Phase Estimation

Policy search in the processing unit (PU). Nonconvex objective function: Particle-swarm optimization. Differential evolution.

O(n7 ) computational complexity. Peter Wittek




Learning in QIP

Towards Quantum AI

Summary

Results

0 SQL DE σ=0,η=0 PSO σ=0.2,η=0 DE σ=0.2,η=0 HL DE σ=0.2, η=0.2 Hill Climbing σ=0.0, η=0.0

−0.5

logVH

−1

−1.5

−2

−2.5 4

10

25

50

100

N

Peter Wittek




Learning in QIP

Towards Quantum AI

Summary

Quantum Gate Learning

Alternative to gate-based quantum computing: pairwise always-on interactions between qubits. Computation by combining natural couplings with moderate external control. Can we do it without external modulation? “Computation by waiting.” Task: implemented a target unitary gate U acting on a set of qubits Q with a set A auxiliary qubits. exp(ıtHQA ) = U ⊗ VA after some time t.

Peter Wittek




Learning in QIP

Towards Quantum AI

Summary

Quantum Gate Learning

Idea: coupling weights are just like a feedforward network. Algorithm: 1

Choose an initial parameter set λ at random; choose an initial learning rate ;

2

Repeat

3

Generate a random ψi;

4

Update the coupling strengths as λ 7→ λ + ∇λ hψ|U † ελ [|ψihψ|]U|ψi;

5

decrease ;

6

until convergence.

Peter Wittek




Learning in QIP

Towards Quantum AI

Summary

Probabilistic Graphical Models Uncertainty (probabilities) and logical structure (independence constraints). Goal: compact representation of a joint probability distribution. For {X1 , . . . , XN } binary random variables, there are 2N assignments.

Complexity is dealt through graph theory. Factorization: compactness. Inference: reassembling factors. Conditional independence (X ⊥ Y |W ): P(X = x, Y = y |W = w ) = P(X = x|W = w )P(Y = y |W = w ) ∀x ∈ X , y ∈ Y , w ∈ W Peter Wittek




Learning in QIP

Towards Quantum AI

Summary

Markov Networks Aka Markov random fields Direction may not be important. E.g., computer vision. See also pattern recognition.

D: set of random variables. Ideally a clique in the graph. Factor: π : Val(D) 7→ R+ A distribution factorizes over G if: P(X1 , . . . , XN ) = Z1 P 0 (X1 , . . . , XN ), where P 0 (X1 , . . . , XN ) = π1 [C1 ] × . . . × πk [Ck ] and Ci is a clique in G .

If all probabilities are Ppositive: P(X = x) = Z1 exp( k wj gj (x)). Connection to Boltzmann machines Peter Wittek




Learning in QIP

Towards Quantum AI

Summary

Probabilistic Inference

How to apply the learned model? NP-hard, in fact, it is in #P. Contrast this to the cost of applying a model in other machine learning models.

Two types of queries: ,e) Conditional probability: P(Y |E = e) = P(Y P(e) . Maximum a posteriori: P argmaxy P(y |e) = argmaxy W P(y , W |e).

Inference by Markov chain Monte Carlo Gibbs sampling.

Peter Wittek




Learning in QIP

Towards Quantum AI

Summary

Markov Logic Networks Real world can never match a KB. Weight each formula in a KB: high weight indicates high probability. Markov Logic Network Apply a KB {Fi } with matching weights {wi } to a finite set of constants C to define a Markov network: Add a binary node for each possible grounding for each atom. Add a binary feature for each possible grounding of each formula Fi . It is like a template to generate Markov networks.

Peter Wittek




Learning in QIP

Towards Quantum AI

Summary

Prepare a Thermal State

Best known state preparation protocol (arXiv:1603.02940): p p O( d n β/Z polylog( d n β/Z /))

Where: n is number of subsystems and d local Hilbert space dimension. The good: Huge improvement over ∼ d n / runtime of classical simulated annealing. The bad: Still exponential in n. The ugly: Requires essentially a universal quantum computer.

Peter Wittek




Learning in QIP

Towards Quantum AI

Summary

Can we hope for something better?

Not really. . . Finding and sampling from thermal states of (quantum) many-body problems is usually hard even though they have much more structure: Very small cliques Sites on a simple lattice Cliques geometrically local

For ground states we even have rigorous hardness results: Classical 3-SAT is NP-complete. Estimating quantum ground state energy is QMA-hard.

Peter Wittek




Learning in QIP

Towards Quantum AI

Summary

Open Questions: Long Term

Strong AI Deep learning has its limits. What enabled its success? Generalization performance and computational complexity will play a role. ML/AI as an enabling technology in universal quantum computing See measurement-based and spin-based models. . . Reinforcement learning crops up in quantum metrology, error correction. . .

Peter Wittek




Learning in QIP

Towards Quantum AI

Summary

Open Questions: Mid-Term

Quantum annealing and interesting learning/AI models. Other experimentally relevant learning protocols. Structural risk minimization and quantum resources. More contemporary approach to reinforcement learning in quantum control. Quantum learning in other quantum protocols. Establish mutual foundations of deep learning and tensor networks.

Peter Wittek
