Quantum Machine Learning

What Quantum Computing Means to Data Mining

Peter Wittek

• Publisher: Academic Press
• Year: 2014
• ISBN:
  9780128010990
• Topic: Physical Sciences
• Subtopic: Quantum Theory

Quantum Machine Learning bridges the gap between abstract developments in quantum computing and the applied research on machine learning. Paring down the complexity of the disciplines involved, it focuses on providing a synthesis that explains the most important machine learning algorithms in a quantum framework. Theoretical advances in quantum computing are hard to follow for computer scientists, and sometimes even for researchers involved in the field. The lack of a step-by-step guide hampers the broader understanding of this emergent interdisciplinary body of research.

Quantum Machine Learning sets the scene for a deeper understanding of the subject for readers of different backgrounds. The author has carefully constructed a clear comparison of classical learning algorithms and their quantum counterparts, thus making differences in computational complexity and learning performance apparent. This book synthesizes of a broad array of research into a manageable and concise presentation, with practical examples and applications.

• Bridges the gap between abstract developments in quantum computing with the applied research on machine learning
• Provides the theoretical minimum of machine learning, quantum mechanics, and quantum computing
• Gives step-by-step guidance to a broader understanding of this emergent interdisciplinary body of research

Part One

Fundamental Concepts

1

Introduction

Abstract

Why should we look at quantum computing in machine learning? Apart from a speedup and increased storage capacity, quantum computing has further benefits for machine learning algorithms. Learning models lie at the core of data mining, a complex process of extracting meaningful information from large volumes of data. We expect a machine learning model to generalize well beyond a limited training collection. On classical computers, we are constrained by convexity conditions or heuristics to keep computational time under control. Quantum computers do not suffer from these issues in optimization problems; hence, we can achieve better generalization performance. Classical computers excel at other tasks; hence, a heterogeneous model is likely to prevail. Dozens of approaches have already been published on quantum machine learning—we briefly overview the major ones. We further mention classical algorithms that borrow metaphors from quantum mechanics; this is also a prolific area of research.

Keywords

Quantum computing

Machine learning

Data mining

Optimization

Convexity

Nonconvex problems

Quantum speedup

The quest of machine learning is ambitious: the discipline seeks to understand what learning is, and studies how algorithms approximate learning. Quantum machine learning takes these ambitions a step further: quantum computing enrolls the help of nature at a subatomic level to aid the learning process.

Machine learning is based on minimizing a constrained multivariate function, and these algorithms are at the core of data mining and data visualization techniques. The result of the optimization is a decision function that maps input points to output points. While this view on machine learning is simplistic, and exceptions are countless, some form of optimization is always central to learning theory.

The idea of using quantum mechanics for computations stems from simulating such systems. Feynman (1982) noted that simulating quantum systems on classical computers becomes unfeasible as soon as the system size increases, whereas quantum particles would not suffer from similar constraints. Deutsch (1985) generalized the idea. He noted that quantum computers are universal Turing machines, and that quantum parallelism implies that certain probabilistic tasks can be performed faster than by any classical means.

Today, quantum information has three main specializations: quantum computing, quantum information theory, and quantum cryptography (Fuchs, 2002, p. 49). We are not concerned with quantum cryptography, which primarily deals with secure exchange of information. Quantum information theory studies the storage and transmission of information encoded in quantum states; we rely on some concepts such as quantum channels and quantum process tomography. Our primary focus, however, is quantum computing, the field of inquiry that uses quantum phenomena such as superposition, entanglement, and interference to operate on data represented by quantum states.

Algorithms of importance emerged a decade after the first proposals of quantum computing appeared. Shor (1997) introduced a method to factorize integers exponentially faster, and Grover (1996) presented an algorithm to find an element ...