• Quantum algorithms for data analysis
  • 1 Preface
    • 1.1 Abstract
    • 1.2 Changelog
    • 1.3 Teaching using this book
  • I - Bridging the gap
  • 2 Quantum computing and quantum algorithms
    • 2.1 Getting rid of physics in quantum computing
    • 2.2 Axioms of quantum mechanics
      • 2.2.1 Review of important statements in quantum computation
    • 2.3 Measuring complexity of quantum algorithms
    • 2.4 Review of famous quantum algorithms
      • 2.4.1 Deutsch-Josza
      • 2.4.2 Bernstein-Vazirani
      • 2.4.3 Hadamard test
      • 2.4.4 Modified Hadamard test
      • 2.4.5 Swap test
  • 3 Classical data in quantum computers
    • 3.1 Representing data in quantum computers
      • 3.1.1 Numbers and quantum arithmetics
      • 3.1.2 Vectors and matrices
    • 3.2 Access models
    • 3.3 Implementations
      • 3.3.1 Quantum memory models and the QRAM
      • 3.3.2 Circuits
      • 3.3.3 Quantum sampling access
    • 3.4 Block encodings
    • 3.5 Importance of quantum memory models
    • 3.6 QRAM architecures and noise resilience
    • 3.7 Working with classical probability distributions
    • 3.8 Retrieving data
      • 3.8.1 Denisty matrices
  • 4 Classical machine learning
    • 4.1 Supervised learning
    • 4.2 Unsupervised learning
    • 4.3 Generative and discriminative models
    • 4.4 Dimensionality reduction
    • 4.5 Generalized eigenvalue problems in machine learning
    • 4.6 How to evaluate a classifier
  • 5 A useful toolbox
    • 5.1 Phase estimation
    • 5.2 Grover’s algorithm, amplitude games
      • 5.2.1 Example: estimating average and variance of a function
    • 5.3 Finding the minimum
    • 5.4 Quantum linear algebra
    • 5.5 Linear combination of unitaries
    • 5.6 Singular value transformation
    • 5.7 Distances, inner products, norms, and quadratic forms
      • 5.7.1 Inner products and quadratic forms with KP-trees
      • 5.7.2 Inner product and l1-norm estimation with query access
    • 5.8 Hamiltonian simulation
      • 5.8.1 Introduction to Hamiltonians
  • II - Quantum Machine Learning
  • 6 Quantum perceptron
    • 6.1 Classical perceptron
      • 6.1.1 Training the perceptron
    • 6.2 Online quantum perceptron
    • 6.3 Version space quantum perceptron
  • 7 SVE-based quantum algorithms
    • 7.1 Estimation of the spectral norm and the condition number
    • 7.2 Explained variance
    • 7.3 Singular value estimation of a product of two matrices
    • 7.4 Log-determinant
  • 8 Quantum algorithms for Monte Carlo
    • 8.1 Monte Carlo with quantum computing
    • 8.2 Bounded output
    • 8.3 Bounded \(\ell_2\) norm
    • 8.4 Bounded variance
    • 8.5 Applications
      • 8.5.1 Pricing of financial derivatives
  • 9 Dimensionality reduction
    • 9.1 Unsupervised algorithms
      • 9.1.1 Quantum PCA
      • 9.1.2 Quantum Correspondence Analysis
      • 9.1.3 Quantum Latent Semantic Analysis
    • 9.2 Supervised algorithms
      • 9.2.1 Quantum Slow Feature Analysis
  • 10 q-means
    • 10.1 The k-means algorithm
      • 10.1.1 \(\delta-\)k-means
    • 10.2 The \(q\)-means algorithm
      • 10.2.1 Step 1: Centroid distance estimation
      • 10.2.2 Step 2: Cluster assignment
      • 10.2.3 Step 3: Centroid state creation
      • 10.2.4 Step 4: Centroid update
      • 10.2.5 Initialization of \(q\)-means++
    • 10.3 Analysis
      • 10.3.1 Error analysis
      • 10.3.2 Runtime analysis
  • 11 Quantum Expectation-Maximization
    • 11.1 Expectation-Maximization for GMM
    • 11.2 Expectation-Maximization
      • 11.2.1 Initialization strategies for EM
      • 11.2.2 Dataset assumptions in GMM
    • 11.3 Quantum Expectation-Maximization for GMM
      • 11.3.1 Expectation
      • 11.3.2 Maximization
  • 12 QML on real datasets
    • 12.1 Theoretical considerations
      • 12.1.1 Modelling well-clusterable datasets
    • 12.2 Experiments
      • 12.2.1 Datasets
      • 12.2.2 q-means
      • 12.2.3 QSFA
      • 12.2.4 QEM
      • 12.2.5 QPCA
  • 13 Quantum algorithms for graph problems
    • 13.1 Connectivity
  • 22 Cookie Policy
  • 23 References
  • By Alessandro 'Scinawa' Luongo

Quantum algorithms for data analysis

H Cookie Policy

The website https://quantumalgorithms.org (the “Website”) uses cookies for the following purposes: allowing online authentication, monitoring sessions and memorising information on specific configurations of users accessing the server. This document sets out detailed information on the use of cookies and similar technology, how they are used by the Website and how to manage them. Visitors are able to configure their own browsers so that they are alerted to the use of cookies or they may otherwise refuse them. Browser acceptance of cookies can be disabled by changing your settings.

H.0.0.1 DEFINITIONS

Cookies are small strings of text (letters or numbers) that allow a web server to memorise browser information that can be used during the same session (session cookies) or at a later stage, even days later (persistent cookies). Cookies are memorised in accordance with the user settings by the individual browser on the device being used (computer, tablet, smartphone).

H.0.0.2 TYPES OF COOKIES

There are different categories of cookies and each has its own characteristics and uses:

  • Technical cookies: this type of cookie is essential for a website to function properly and they are only used to the extent required for the transmission of communications over an electronic communication network, or to the extent strictly necessary for the supplier of an information service explicitly requested by the subscriber or by the user to supply that service;
  • Analytical cookies: this type of cookie is used to anonymously collect and analyse the traffic to and use of a website. Without identifying the user, they make it possible for example, to detect whether said user has subsequently accessed the website. They also make it possible to monitor the system and enhance the services and user experience. These cookies may be disabled without affecting the functioning of a website.
  • Profiling cookies: these are persistent cookies used to identify (anonymously and not) user preferences and to enhance the navigation experience.
  • Third-party cookies (analytical and/or profiling): these are generated by companies other than the actual website and integrated into a website’s pages, for example Google widgets (such as Google Maps) or social plugins (Facebook, Twitter, LinkedIn, Google+, etc.). The management of information that is collected by a “third party” is regulated by the relevant privacy statement, which you are requested to read. For ease of reference, they are indicated in the links set out below.

H.0.0.3 TYPES OF COOKIES USED

The Website uses the following type of cookies:

  • Third-party analytical cookies: Google Analytics, a web traffic analysis service provided by Google Inc. (“Google”), which makes it possible to access and analyse detailed statistics on website visitors. The Google Analytics service has been designed to use pre-anonymised data so as to conceal the last part of the visitor’s IP address. For further information, please see https://www.google.it/policies/privacy/partners/. Users may disable Google Analytics by installing on their browser the opt-out add-on tool provided by Google (please see https://tools.google.com/dlpage/gaoptout)

H.0.0.4 DURATION

Some cookies (called session cookies) remain active until a user closes their browser. Other cookies (called persistent cookies) “survive” the closure of the browser and are available in subsequent user visits. Their duration is set by the server when they are created: in some cases, there is a set expiry date whereas in other cases their duration is unlimited. However, they may always be deleted using browser settings. The majority of the cookies we use are persistent and expire 2 years from the date when they are downloaded onto the Visitor’s device.

H.0.0.5 MANAGEMENT

Visitors may accept or refuse cookies via their browser settings. Content may be accessed even if cookies are completely disabled and disabling “third–party technical” cookies will not prevent a visitor from using a website. It could however adversely impact the User’s experience (insofar as it is not possible to memorise their data for future use). Settings can be changed for different websites and/or website applications. Moreover, the leading browsers allow users to change their settings depending on the type of cookie:

  • Firefox: https://support.mozilla.org/it/kb/Gestione%20dei%20cookie
  • Internet Explorer: https://support.microsoft.com/it-it/help/17442/windows-internet-explorer-delete-manage-cookies
  • Chrome: https://support.google.com/chrome/answer/95647?hl=it
  • Opera: http://help.opera.com/Windows/10.00/it/cookies.html
  • Safari for Mac: https://support.apple.com/kb/PH21411?viewlocale=it_IT&locale=it_IT
  • Safari for iOS: http://support.apple.com/kb/HT1677?viewlocale=it_IT

Third parties are hereby informed that the use of this policy, even partial, for other websites shall be subject to sanctions by the Italian Data Protection Authority. This page may be accessed via the link set out in the footer of all the website’s pages, pursuant to Article 122(2) of Legislative Decree 196/2003 and the simplified process for privacy information and the acquisition of consent to the use of cookies published on the Italian Official Journal no. 126 of 3 June 2014 and the relevant register of measures 229 dated 8 May 2014.