index.Rmd

---
title: Quantum algorithms for data analysis
author: "Alessandro Luongo"
date: "`r Sys.Date()`"
site: bookdown::bookdown_site
documentclass: book
bibliography: [book.bib]
biblio-style: apalike
link-citations: yes
header-includes:
   - \usepackage{bm}
   - \usepackage{amsmath}
output:
  bookdown::gitbook:
    includes:
      in_header: [header.html]
      after_body: [cookiebanner.html, ribbon_body.html, googletag.html]
description: "Open-source book on quantum algorithms for information processing and machine learning"
url: 'https\://quantumalgorithms.org'
github-repo: "scinawa/quantumalgorithms.org"

---



<!--  ```{r, include=FALSE} -->
<!--  options(tinytex.verbose = TRUE) -->
<!--  ``` -->

\newcommand{\norm}[1]{\left\lVert#1\right\rVert}

\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\E}{\mathbb{E}}

\newcommand{\ket}[1]{|#1\rangle}
\newcommand{\bra}[1]{\langle#1|}
\newcommand{\braket}[1]{\langle#1\rangle}

\newcommand{\be}{\begin{equation}}
\newcommand{\ee}{\end{equation}}
\newcommand{\argmax}{\arg\max}

\newcommand{\Ord}[1]{\mathcal{O}\left( #1 \right)}
\newcommand{\tOrd}[1]{\widetilde{\mathcal{O}}\left( #1 \right)}






# Preface

This [open source project accessible on GitHub](https://github.com/Scinawa/quantumalgorithms.org/) is only possible thanks to its many [contributors.](contributions-and-acknowledgements.html) The website is licensed under CC BY-NC-SA 4.0. We are searching for talented people and researchers to [contribute](https://github.com/Scinawa/quantumalgorithms.org/issues).

**MEMO: we have some funding for motivated contributors**

The aim of this book is twofold:

- First, we want to bridge the gap between introductory material in quantum computation and research material.
- Second, you should be able to use this book as a resource for state-of-the-art algorithms. Readers and scholars should find statements of theorems (along with their citations) and runtimes of the best quantum subroutines in literature, ready to be used in new quantum algorithms or applications.


These lecture notes were used to teach at:

- Politecnico di Milano (2019) - Quantum machine learning in practice.
- Politecnico di Milano (2021) - Applied quantum computing.

Are you using these lecture notes to support your course? [Write us an email!](mailto://scinawa@luongo.pro)


<p style="text-align:right">
 This book is dedicated to all [cypherpunks: *civil liberties through complex mathematics*.](https://luongo.pro/cypherpunks/) </p>


## Abstract

In these lecture notes, we explore how we can leverage quantum computers and quantum algorithms for information processing. It has long been known that quantum computation can offer computational advantages over classical computation, and in this book we explore the consequences of this fact in current research areas of computer science.

Are there other reasons, besides getting a practical computational advantage for studying quantum algorithms? We argue that having faster algorithms is not the only reason for studying quantum computing.

One --- perhaps shallow --- reason is to satisfy our curiosity by studying how to use quantum mechanical systems for doing computation, and challenging yourself in finding a faster-then-classical algorithms. Studying quantum computation might also reveal profound insights into new ways to process
information. For instance, it can give us ideas on processing data
in a secure way (though, quantum cryptography is not discussed in these notes).
A better understanding of quantum computing might lead to understanding the
computational limits of nature: what can be computed in this world? What can be computed with classical computers? As an example, because of the interplay between research in classical and quantum
computation, many new *classical* algorithms have been invented (i.e. the
dequantizations of quantum machine learning algorithms, new classical algorithms
for Gibbs sampling, classical simulations of quantum circuits, etc..). This, in turn,
improved our understanding of physics, and ultimately of the world itself.
<!-- As some scientists believe\footnote{A friend told me this was originally an idea -->
<!-- of Miklos Santha}, quantum computing is the occasion for Theoretical Computer -->
<!-- Science to welcome contribution from Physics. As we know, TCS has (luckly) -->
<!-- welcome many contribution from Mathematical sciences, and at the current state -->
<!-- is basically a branch of Mathematics. With quantum computing, TCS can welcome -->
<!-- also contribution from physics, perhaps going towards the direction of a -->
<!-- "Physical Computer Science". -->
One last reason for studying quantum algorithms --- which a computer scientist can surely appreciate --- is that quantum computers are posing a significant challenge to the [*extended* Church-Turing thesis](https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis), which states that any "reasonable"
model of computation can be *efficiently* simulated on a probabilistic Turing machine.
However, there are many physical processes that we do not know how to simulate efficiently on classical computers, but for which we have efficient quantum algorithms! This is strong evidence that the strong Church-Turing thesis might be false!

<!-- Algorithms are often overlooked when thinking about speed of calculations. But they deserve more credit for the performance gains than the well known Moore's Law. As we can read [here](https://www.nitrd.gov/pubs/PCAST-NITRD-report-2010.pdf), some researcher tried to quantify the performance gains for some specific problem (linear programming and mixed integer programming), and they found that in 15 years we had an improvement of a factor of 43millions: a factor of roughly 1000 was due to increased processor speed, and a factor of 43.000 was due to algorithmic improvements for the problem.  -->

You might often hear that there are only two real quantum algorithms: phase estimation and the Grover's algorithm. This is true in the same way that we have only 12 notes in the western temperate scale, yet Pink Floyd was able to write [The Dark Side of the Moon](https://www.youtube.com/playlist?list=OLAK5uy_l1x-JAx0w53suECoCI0YJtW6VB8DBQWRQ) (and other musicians came up with "the rest" of the music).

The common thread of these algorithms is that they are faster than their best classical counterpart. Oftentimes, (especially for ML) the runtime will depend only [poly-logarithmically](https://en.wikipedia.org/wiki/Polylogarithmic_function) on the number of elements of the dataset, and it is usually only linear in the number of features (classical algorithms are often either linear in the number of elements and quadratic in the number of features, or depend on the number of nonzero components of the matrix and depend polynomially on other parameters of the matrix). The runtime of a quantum machine learning algorithm also often depends on characteristics of the matrix that represents the data under analysis, such as its rank, the Frobenius norm (or other matrix norms), the sparsity, the condition number, and the error we tolerate in the analysis. For this, along with an error-corrected quantum computer, we assume to have quantum access to a dataset. In other words, we assume that the data is stored in a quantum memory: the corresponding quantum version of the classical random-access memory.

We will see that, for a new QML algorithm, one often needs to make sure that the real performances of the quantum algorithms offer concrete advantages with respect to the effective runtime and the accuracy that is offered by the best classical algorithms. As we don't have access to big-enough quantum computers *yet*, we can only assess the performance of these quantum algorithms via a classical simulation.

These lecture notes should prepare the future quantum data analyst to understand the potential and limitations of quantum computers, so as to unlock new capabilities in information processing and machine learning. The hope is that this kind of technology can foster further technological advancements that benefit society and humankind, as soon as the hardware that supports this kind of computation becomes ready.

Last but not least, we will also cover important algorithms that are not necessarily related to machine learning, but are the quantum counterpart of important classical algorithms. Don't get swayed by the "lack" of exponential speedups. Remember: the square root of 365 days is a little less than 3 weeks. Besides this, big polynomial speedups, small polynomial speedups in important problems, or polynomial speedups proposing new algorithmic techniques are all much welcome in quantum computer science. All in all, quantum algorithms can be seen as a way for making **impossible things possible**.

While reading these lecture notes you should always remember a quote from the good Simon Martiel:
<p style="text-align:center">
"(quantum) Theoretical computer science is the fun part of mathematics."
</p>

To all of you, happy reading.




<!--
it would be nice to make just a preface, and put the text above this one without any heading..
https://stackoverflow.com/questions/41084020/add-a-html-block-above-each-chapter-header  -->

## Changelog

- **August 2020**: Migrated the old blog on bookdown
- **December 2020**: Moved thesis in bookdown
- **January 2021**: First system for typesetting algorithms, more appendix on linear algebra
- **February 2021**: New subroutines for estimating $\ell_1$ norms.
- **March 2021**: quantumalgorithms.org is proudly supported by the [Unitary Fund](https://unitary.fund/), and quantumalgorithms.org is a project of the [QOSF](https://qosf.org) mentorship program: 5 students started creating new content!
- **April 2021**: Mobile version working, search functionality added, q-means, finding the minimum, new algo for dimensionality reduction, and factor score ratio estimation estimation.
- **June 2021**: Quantum Monte Carlo algorithms, lower bounds techniques for query complexity of quantum algorithms, quantum algorithms for graph problems. The output of the mentorship program of the QOSF foundation!
- **January 2022**: In the past months we improved the overall quality of the website (graphics, typos) and added some content (Deutsch-Josza, Bernstein-Vazirani, swap and Hadamard tests)
- **February 2022**: We are happy to bring our swag (t-shirts, stickers, lanyards) to QIP. We added a whole chapter on perceptron algorithms and we doubled the chapter on quantum Monte Carlo algorithms with applications to finance and trace distance!
- **June 2022**: We are participating to the UnitaryHack! We also presented this work at QNLP2022 where we distributed our swag! Now the website can be compiled also with the latest version of RStudio,pandoc,bookdown.
- **August 2022**: Added in the appendix: polynomial approximation of 1/x, more on concentration inequalities (these were work started by contributors that discovered the project during the unitary.hack! ). Improved css as a bounty to the unitary.hack. Working (on a separate project) to improve chapter 3.
- **May 2023**: We are improving the overall book with the precious help from the editor (Hue Jun Hao Alexander) and other contributors.


**NEW** Submit your solution of the exercises as PR on [GitHub](https://github.com/scinawa/quantumalgorithms.org) and get it published in the chapter on [Solutions](https://quantumalgorithms.org/solutions-to-exercises.html).



**Coming soon:**
- quantum perceptrons
- quantum random walk
- quantum algorithms for dynamic programming
- quantum convolutional neural networks
- quantum random feature sampling


## Teaching using this book


- Lecture 1 - **Axioms of quantum mechanics**: Chapter \@ref(chapter-intro), section \@ref(section-axioms)
- Lecture 2 - **Quantum computer science**: oracle model, BPP vs BQP, from boolean to quantum circuits, Solovay-Kitavev, randomized algorithms, Markov Inequality, Union bound and applications. Section \@ref(measuring-complexity).
- Lecture 3 **Foundational quantum algorithms**, Section \@ref(review-famous-quantum-algos): Deutsch-Josza, Bernstein-Vazirani, Swap-test, Hadamard-test.
- Lecture 4 - **Oracles, data representation and data loaders**: Oracles for accessing the data, data representation, sparse models. Chapter \@ref(chap-classical-data-quantum-computers).
- Lecture 5 - **QFT and Grovers' algorithm**: Section \@ref(section:grover), Section \@ref(section:phaseestimation)
- Lecture 6 - **Phase estimation, amplitude amplification, counting, finding the minimum, and applications**: Beginning of Chapter \@ref(chap-toolbox).
- Lecture 7 (optional) - **More foundational quantum algorithms**: Simons's and Shor's algorithm (`#TODO`)
- Lecture 8 (optional): **Quantum perceptron models**: This is a very simple quantum machine learning algorithm that shows the applications of different techniques seen so far.  (`#TODO`, very soon!)
- Lecture 9: **Quantum numerical linear algebra pt. 1**: HHL algorithm, block-encodings and quantum singular value estimation. Mostly from Chapter \@ref(chap-svebased).
- Lecture 10: **Quantum numerical linear algebra pt. 2**: Quantum singular value transformation, Hamiltonian simulation. Theory and examples.
- Lecture 11: **Distance, inner product, trace estimation**: From Chapter \@ref(chap-toolbox), especially Section \@ref(sub:distances), (`#TODO` trace estimations).
- Lecture 12: **Quantum monte carlo algorithms and applications**: Content from Chapter \@ref(chap-montecarlo).
- Lecture 13: **Quantum machine learning pt. 1**:  QPCA and QSFA. Chapter \@ref(chap-dimensionality-reduction) Hamiltonian simulation with density matrices (`#TODO`).
- Lecture 14: **Quantum machine learning pt. 2**:   Random feature sampling (`#TODO`, to convert from .tex to markdown, check github repository).
- Lecture 15: **Classical simulation of quantum algorithms**: How to simulate a quantum circuit? (`#TODO`) How to simulate a quantum machine learning algorithm? Section \@ref(chap-QML-on-real-data).
- Lecture 16: **Lower bounds**: Adversarial and polynomial method in Chapter \@ref(chap-lowerbounds), state discrimination (missing).
- Lecture 17 (optional): **Between the qubits and me**: what do we have between the theory of our algorithms and the hardware? An overview of different hardware architectures, error correction codes, and compilation techniques. (`#TODO`).
- Lecture 18: **Quantum algorithms on graphs**: Backtracking algorithms, NP-complete problems on graphs (`#TODO`).
- Lecture 19: **Quantum optimization**: Introduction to optimization. Quantum simplex, quantum zero-sum games. (`#TODO`).
- Lecture 20: **Quantum optimization**:  Quantum SDP algorithms, quantum interior point methods, quantum branch-and-bound algorithms (`#TODO`).








```{js, echo = FALSE}
title=document.getElementById('header');
title.innerHTML = '<img src="images/mainlogo.png" alt="logo of quantumalgorithms.org">' + title.innerHTML
```