We are finished for 2017 but will be back with another group next year.
This is a reading archive for a journal club held at Melbourne University. Everybody is welcome to be involved. Please feel free to send pull requests with edits, added summaries or interesting links you might have stumbled across.
During the past year we have covered the following papers:
1. Quantum Algorithm for Linear Systems of Equations (HHL) - Harrow, Hassidim and Lloyd.
- University of Bristol and MIT.
Harrow, Aram W., Avinatan Hassidim, and Seth Lloyd. Physical review letters 103.15 (7-Oct-09): 150502.
Harrow, Aram W., Avinatan Hassidim, and Seth Lloyd. arXiv preprint arXiv:0811.3171v3 (30-Sep-09).
As the title suggests this paper introduces a new quantum algorithm for solving linear systems of equations. Classically, the best time scaling algorithm is roughly N sqrt(κ) where κ is something called the condition number (how sensitive the matrix is to changes). This new quantum algorithm scales roughly poly log(N) and poly (κ), which is essentially exponentially faster. There is a catch though, the actual readout of the solution scales linearly (which is the same as classical). So the algorithm will be mainly beneficial for feeding the output into the input of some other quantum algorithm or approximating the expectation value.
The method uses a technique where a non-unitary transformation involving measurement is used within the quantum circuit. Computation is only continued if a particular qubit state is measured, otherwise it is repeated.
2. Quantum Algorithms for Supervised and Unsupervised Machine Learning - Lloyd, Mohseni and Rebentrost.
- MIT and Google.
Lloyd, Seth, Masoud Mohseni, and Patrick Rebentrost. arXiv preprint arXiv:1307.0411 (4-Nov-13).
This paper focuses on applying quantum algorithms on supervised and unsupervised clustering algorithms.
The supervised algorithm (classification) is simply the process of assigning each new data point to a class with the closest mean. The distances to the means are composed of two factors. The paper describes a method to find one factor by applying a procedure called a swap test between a particular qubit register state representing the mean and an ancilla qudit (not qubit) representing the new datum. The second factor can be found using Grover’s algorithm or quantum counting. This algorithm can, in theory, obtain exponential speedup over the classical version.
The unsupervised algorithm (clustering) is for k-means clustering which uses Lloyd’s algorithm (not related to the author of this paper). There are a few visualisations of it around the net (It’s a pretty cool algorithm, so you should check it out). The paper introduces the quantum Lloyd’s algorithm with speed up (although not exponential) over the classical version. Unfortunately, we didn’t get enough time to go through this section in detail.
I think the take home message of this paper was that quantum computers are powerful when it comes to manipulating large numbers of high-dimensional vector spaces, which is precisely what is required for vector-based machine learning. This paper runs through some examples of how existing quantum algorithms can be directly applied to supervised and unsupervised machine learning clustering problems.
3. Quantum Sampling Problems, BosonSampling and Quantum Supremacy – Lund, Bremner and Ralph.
- CQC2T.
Lund, A. P., Michael J. Bremner, and T. C. Ralph. npj Quantum Information (13-Apr-17)
Lund, A. P., Michael J. Bremner, and T. C. Ralph. arXiv preprint arXiv:1702.03061 (10-Feb-17).
This paper is a review on quantum speedup for quantum sampling problems such as BosonSampling and IQP. IQP is essentially a generalisation of BosonSampling for commuting quantum gates on qubits. The paper reduces the argument of quantum supremacy for BosonSampling and IQP to be that either the polynomial hierarchy collapses to the third level or quantum algorithms are more powerful than classical. This is similar to the statement P = NP, except relative to an oracle. They go on to say that 50 photons (or qubits with sufficiently high fidelity for IQP) would be sufficient to demonstrate quantum supremacy. So quantum sampling is a promising direction that brings us much closer to demonstrating quantum supremacy.
4. Application of Quantum Annealing to Training of Deep Neural Networks - Adachi and Henderson.
- Lockheed Martin Information Systems & Global Solutions.
Adachi, Steven H., and Maxwell P. Henderson. arXiv preprint arXiv:1510.06356 (21-Oct-15).
5. Quantum Machine Learning over Infinite Dimensions - Lau, Pooser, Siopsis and Weedbrook.
- Ulm University, Oak Ridge National Laboratory and The University of Tennessee.
Lau, Hoi-Kwan, Raphael Pooser, George Siopsis, and Christian Weedbrook. Physical Review Letters 118.8 (21-Feb-17): 080501.
Lau, Hoi-Kwan, Raphael Pooser, George Siopsis, and Christian Weedbrook. arXiv preprint arXiv:1603.06222v2 (14-Nov-16).
6. Quantum machine learning with small-scale devices: Implementing a distance-based classifier with a quantum interference circuit - Schuld, Fingerhuth, and Petruccione.
- University of KwaZulu-Natal, University of Maastricht and National Institute for Theoretical Physics (KwaZulu-Natal).
Schuld, Maria, Mark Fingerhuth, and Francesco Petruccione. arXiv preprint arXiv:1703.10793 (31-Mar-17).
7. Quantum Random Access Memory - Giovannetti, Lloyd and Maccone.
- Scuola Normale Superiore, MIT and University of Pavia.
Giovannetti, Vittorio, Seth Lloyd, and Lorenzo Maccone. Physical review letters 100.16 (21-Apr-08): 160501.
Giovannetti, Vittorio, Seth Lloyd, and Lorenzo Maccone. arXiv preprint arXiv:0708.1879v2 (26-Mar-08).
Another paper by the same authors on qRAM that goes into more detail:
Giovannetti, Vittorio, Seth Lloyd, and Lorenzo Maccone. "Architectures for a quantum random access memory." Physical Review A 78.5 (5-Nov-08): 052310.
Giovannetti, Vittorio, Seth Lloyd, and Lorenzo Maccone. "Architectures for a quantum random access memory." arXiv preprint arXiv:0807.4994v2 (11-Nov-08).
8. Quantum gradient descent for linear systems and least squares - Kerenidis and Prakash
- Paris Diderot University and Nanyang Technological University
Kerenidis, Iordanis, and Anupam Prakash. arXiv preprint arXiv:1704.04992 (1-May-17).
Although difficult and long, this is a great paper full of the latest in quantum algorithmic techniques. There are two new major techniques that are introduced.
The first is a generalized quantum Singular Value Estimation (SVE) procedure that is more computationally efficient than previous methods. The HHL algorithm has complexity O(s(A)2κ(A)2 / ε) where s is the sparsity, κ is the condition number, ε is the algorithm error and the dependency of the dimension of matrix A has been supressed. Previous work has improved this algorithm to O(s(A)κ(A)log(1/ε)). By using this improved SVE procedure, the authors introduce a new parameter μ(A) such that μ(A) < s(A) and for sparse matrices μ(A) < sqrt[n] while s(A) has Ω(n) introducing polynomial speedup. This leads to an even faster algorithm with complexity O(μ(A)κ(A)log(1/ε)). Although this algorithm still doesn't have exponential savings on all matrices, it does have exponential savings on more matrices than previous methods.
Current work on quantum gradient descent algorithms have a major issue where each iteration requires measurement of an ancilla qubit to be in a particular state to continue, if the measurement was not in this state the entire algorithm would have to start over. This led to an exponential suppression in propability of measuring the correct output state of the algorithm with respect to the number of iterations. The second major technique that this paper introduces overcomes this challenge. The final set of parameters can be written as the initial parameter plus a summation over all update changes (gradients multiplied by step size), for the gradient descent with affine updates, the gradients are linear. The idea is to use the improved SVE for matrix multiplication and to compute the summation of gradients in quantum parallel, which overcomes this exponential suppression. Amplitude amplification is used to increase the probability of selecting the required ancilla states. In many cases the overall expected running time for general quantum gradient descent turns out to be O(τ(CUlog(τ))), where CU is the runtime cost for determining how much change an update has for a particular iteration step and τ is the number of iterations.
Most of the rest of the paper seems to go deep into the details and applications of the above while providing proofs for many of the methods. They define quantum gradient descent and go into detail about the correctness and running time. They show how their improved SVE procedure can be used to directly solve linear systems. Then they apply it to the linear update of quantum gradient descent, which can then be used to indirectly solve linear equations. These two methods are then compared. Finally they show how quantum gradient descent and stochastic quantum gradient descent can be used to solve the weighted least squares problem.
9. Simulating a perceptron on a quantum computer - Schuld, Sinayskiy and Petruccione
- University of KwaZulu-Natal, and National Institute for Theoretical Physics (KwaZulu-Natal).
Schuld, Maria, Ilya Sinayskiy, and Francesco Petruccione. Physics Letters A 379.7 (20-Mar-15): 660-663.
Schuld, Maria, Ilya Sinayskiy, and Francesco Petruccione. arXiv preprint arXiv:1412.3635 (11-Dec-14).
10. Quantum Machine Learning - Biamonte, Wittek, Pancotti, Rebentrost, Wiebe and Lloyd
- University of Malta, University of Waterloo, ICFO - The Institute of Photonic Sciences (Spain), University of Borås (Sweden), Max Planck Insitute of Quantum Optics (Germany), MIT, Station Q (Microsoft Research).
Biamonte, Jacob, et al. "Quantum Machine Learning." arXiv preprint arXiv:1611.09347 (28-Nov-16).
This is a great and detailed literature review on the fields combining machine learning and quantum computing. It looks at multiple perspectives including how machine learning could be used to help us improve and better understand quantum systems, how quantum computing could be used to improve the training of machine learning algorithms, experimental implementations of machine learning algorithms on physical quantum systems, quantum speedup, and the limits of machine learning with quantum systems. The paper mentions various open problems along the way.
Quantum computing will speedup machine learning algorithms and machine learning algorithms can be used to help create better quantum computers. This leads to a frontier where both fields will co-evolve and become enabling technologies for each other. However there are still many problems to investigate and challenges to overcome. I highly recommend this review for anyone starting out in research related to these fields.
11. Quantum algorithms for Gibbs sampling and hitting-time estimation - Chowdhury and Somma
- Center for Quantum Information and Control at the University of New Mexico, Theoretical Division at the Los Alamos National Laboratory.
Chowdhury, Anirban Narayan, and Rolando D. Somma. "Quantum algorithms for Gibbs sampling and hitting-time estimation." arXiv preprint arXiv:1603.02940 (09-Mar-16).
12. Simulating Hamiltonian Dynamics with a Truncated Taylor Series - Berry, Childs, Cleve, Kothari, and Somma
- Macquarie University, University of Waterloo, University of Maryland, Canadian Institute for Advanced Research, MIT, Theoretical Division at the Los Alamos National Laboratory.
Berry, Dominic W., et al. Physical review letters 114.9 (03-Mar-15): 090502.
Berry, Dominic W., et al. arXiv preprint arXiv:1412.4687 (15-Dec-14).
Also check out the "High-level overview of techniques" and "Linear Combination of Unitaries algorithm" sections of Robin Kothari's PhD thesis.
Previously in the quantum algorithm literature, Hamiltonian simulation algorithms have already achieved exponential speedups over their predecessors. This paper introduces a new Hamiltonian simulation algorithm that achieves the same complexity as current state of the art although is simpler and is efficient for a larger class of Hamiltonians.
The algorithm works by initially discretizing the time evolution into small steps and expanding each step as a Taylor series, then truncating this expansion based on desired precision. We are left with a series of power terms of the Hamiltonian that is no longer unitary due to the truncation, although each of the terms can be expanded as linear combinations of unitaries. Once expanded, the terms are contracted to form a single linear combination of unitary operators, V. To apply V, the authors use something called p-implementation, mentioned in Kothari's thesis, which is a transformation that results in two subspaces, one of which implements operator V and the other contains unwanted orthogonal states. The authors then use their new technique of oblivious amplitude amplification to amplify the propability of the desired subspace, operated upon by V, which works without knowledge of the input state.
The paper first shows how this method can be applied with time-independent Hamiltonians and then shows how to extend it to time-dependent Hamiltonians by discretizing time and breaking it into a summation of time-independent Hamiltonians.
David found a bunch of presentations by the authors containing further and lighter explanations
http://www.dominicberry.org/presentations/Bristol.pdf
http://www.dominicberry.org/presentations/Durban.pdf
http://www.quantum-lab.org/qip2015/slides/QIP2015-Dominic%20Berry.pdf
https://www.cs.umd.edu/~amchilds/talks/ibm13.pdf
And the paper https://arxiv.org/abs/1501.01715
13. Learning in Quantum Control: High-Dimensional Global Optimization for Noisy Quantum Dynamics - Palittapongarnpim, Wittek, Zahedinejad, Vedaie and Sanders
- University of Calgary, ICFO - The Institute of Photonic Sciences (Spain), University of Borås (Sweden), Canadian Institute for Advanced Research and the University of Science and Technology of China.
Palittapongarnpim, Pantita, et al. Neurocomputing (30-Apr-17).
Palittapongarnpim, Pantita, et al. arXiv preprint arXiv:1607.03428 (25-Nov-16).
14. High-order quantum algorithm for solving linear differential equations - Dominic W Berry
- Macquarie University, Institute for Quantum Computing - University of Waterloo
Berry, Dominic W. Journal of Physics A: Mathematical and Theoretical 47.10 (19-Feb-14): 105301.
Berry, Dominic W. arXiv preprint arXiv:1010.2745 (13-Oct-10).
15. Quantum Enhanced Inference in Markov Logic Networks - Wittek and Gogolin
- ICFO - The Institute of Photonic Sciences (Spain), University of Borås (Sweden).
Wittek, Peter, and Christian Gogolin. Scientific Reports 7 (19-Apr-17).
Wittek, Peter, and Christian Gogolin. arXiv preprint arXiv:1611.08104 (24-Nov-16).
16. Quantum Machine Learning: A Classical Perspective - Ciliberto, Herbster, Ialongo, Pontil, Rocchetto, Severini, and Wossnig
- University College London, University of Cambridge, Max Planck Institute for Intelligent Systems, Istituto Italiano di Tecnologia, University of Oxford, Shanghai Jiao Tong University, ETH Zürich.
Ciliberto, Carlo, et al. arXiv preprint arXiv:1707.08561 (26-Jul-17).
17. Hamiltonian for the Zeros of the Riemann Zeta Function - Bender, Brody and Müller
- Washington University, Brunel University London, ITMO University Russia, and University of Western Ontario.
Bender, Carl M., Dorje C. Brody, and Markus P. Müller. arXiv preprint arXiv:1608.03679 (12-Aug-16).
Bender, Carl M., Dorje C. Brody, and Markus P. Müller. Physical Review Letters 118.13 (30-Mar-17): 130201.
18. A Quantum Approximate Optimization Algorithm - Fahri, Goldstone and Gutmann
- MIT.
Farhi, Edward, Jeffrey Goldstone, and Sam Gutmann. arXiv preprint arXiv:1411.4028 (14-Nov-14).
Here's some further reading contributed by David.
Some clean explanations of parts of the paper (scattered throughout the webpage)
http://grove-docs.readthedocs.io/en/latest/qaoa.html
More recent paper (Sep 2017). Contains some generalisations. Also mappings to various problems.
https://arxiv.org/abs/1709.03489
This contains a video recording of a presentation by Farhi on QAOA
http://online.kitp.ucsb.edu/online/synquant16/farhi/
19. Quantum Supremacy through the Quantum Approximate Optimization Algorithm - Fahri and Harrow
- MIT.
Farhi, Edward, and Aram W. Harrow. arXiv preprint arXiv:1602.07674 (24-Feb-16).
20. A Quantum Recurrent Neural Network - Rebentrost, Bromley, Weedbrook and Lloyd
- Xanadu, Toronto, Canada. MIT.
Rebentrost, Patrick, et al. "A Quantum Recurrent Neural Network." arXiv preprint arXiv:1710.03599 (10-Oct-17).
21. Breaking the 49-Qubit Barrier in the Simulation of Quantum Circuits - Pednault, Gunnels, Nannicini, Horesh, Magerlein, Solomonik and Wisnieff
- IBM. Dept. of Computer Science, University of Illinois at Urbana-Champaign, Champaign, IL.
Pednault, Edwin, et al. arXiv preprint arXiv:1710.05867 (16-Oct-17).
A Quantum Linear System Algorithm for Dense Matrices (3-May-17) - Wossnig, Zhao and Prakash
Deep Learning and Quantum Entanglement: Fundamental Connections with Implications to Network Design (10-Apr-17) - Levine, Yakira, Cohen and Shashua
A Survey of Quantum Learning Theory (24-Jan-17) - Arunachalam and Wolf.
Quantum Deep Learning (22-May-15) - Wiebe, Kapoor and Svore
An Introduction to Quantum Machine Learning (15-Oct-14) - Schuld, Sinayskiy, and Petruccione
Neural Networks and Deep Learning is a great free online book by Michael Nielsen (the same author of the quantum computation and quantum information textbook)
colah's blog for various machine learning concepts and in particular the post Neural Networks, Manifolds, and Topology
TensorFlow Playground lets you play with neural networks that are completely visualised. Very useful for gaining intuition for how they learn.
Distill is an online academic journal focused on machine learning. It places emphasis on clear explanations and many articles contain interactive elements.