Quantum machine learning with large data sets

Today I came across this interesting paper by Aram Harrow, which presents a lucid discussion and possible solution to one of the big problems with quantum machine learning: how to obtain useful quantum speedups when dealing with big data sets that are slow to feed into and read out of the quantum processor.

The main point is that real world classical data sets are likely to lack special structure to enable them to be efficiently encoded into quantum states (a prerequisite for quantum algorithms with a proven speedup). Input and output of large data sets will thus overwhelm any possible near-term quantum advantage. Therefore, an essential step of any practical quantum machine learning algorithm will be to first preprocess the data to obtain a smaller but representative subset.

How then can the quantum computer help us? We should look for quantum speed ups in searching the space of machine learning models used to describe the reduced data set. Most machine learning models have some form of structure. That is, they can be specified in terms of relatively simple functions such as matrix multiplications or minimizing quadratic loss functions. The quantum computer can exploit this structure to place the available models in a quantum superposition and then achieve a speedup using rigorously-proven algorithms, such as Grover search to find the best model.

However, Grover search is impractical to run on near-term devices, which are largely limited to variational quantum algorithms which lack proven speedups. This paper has tested how well classical data preprocessing works in combination with the quantum approximate optimization algorithm (QAOA), focusing on k-means clustering. In the small scale examples considered, QAOA did not work well with the reduced data set. The authors conjecture that the poor performance may either be limitation of QAOA (requiring the exploration of other NISQ-friendly algorithms), or due to the rather small sizes of the reduced data sets (up to 20 points are used to summarize the full sets containing thousands of points). 

It will be interesting to explore these ideas further.

Cloud quantum computing on AWS

Some thoughts on Amazon's quantum computing offerings available via AWS, based on a quantum computing workshop I recently attended:

The AWS-Braket library conveniently provides access to three different hardware backends (DWave, Rigetti, IonQ), which each has its own strengths and limitations. 

You can also run two different cloud quantum simulators (SV1 and TN1). SV1 is a state vector simulator (so it runs circuits without any approximation), and can apparently handle up to 24 qubits, which is about double what can be easily done on a standard personal computer. TN1 uses tensor networks to more efficiently simulate certain larger circuits, but it doesn't always work.

Presently the AWS-Braket library only handles circuits defined using the gate model of quantum computation, so there is no ability to control the individual pulses used to implement the gates on the hardware, which are required to perform analog quantum simulation or implement specialised pulse sequences in order to improve the performance of specific circuits. Amazon plans to include this functionality in a later release.

The hardware: the DWave devices have 5760 and 2000 "qubits" (however with limited connectivity, and restricted to quantum annealing), the Rigetti chip has 32 qubits arranged in a quasi-1D geometry, while the IonQ device currently supports 11 qubits, with plans to extend to 32 qubits later this year. This means that one can run circuits that are in principle a real pain to simulate using the best classical computers. However, it's still unclear whether the current levels of device noise and limited qubit connectivity (in the case of the DWave and Rigetti devices) rule out a quantum advantage using these devices.

The catch: running these state-of-the-art devices is expensive! The schedule of prices can be found here: $0.30 per circuit run, plus an additional charge per measurement repetition. How much will this cost the end user? Let's take as a representative example solving the MaxCut problem using the quantum approximate optimization algorithm, taking parameters from a recent proof-of-concept experiment by the Google group. For the simplest implementation of the algorithm, optimization of the two variational parameters to find the optimal solution required ~10 iterations, each comprising 6 energy evaluations with 25,000 shots per energy. Using Rigetti's superconducting chip's fee of $0.00035 per shot, this translates to a total cost of 60*(0.03 + 25000*0.00035) = $527! Larger real world problems will likely require many more iterations in order to converge to good solutions, pushing the price up further. 

Therefore the priority for users of these noisy intermediate-scale quantum computers should be to not merely to use them to solve problems faster existing classical algorithms; it would be more cost-effective to simply throw more classical computing power at them. Instead, focus on problems that will remain too hard to solve even as classical computers continue to improve.

Detecting dark solitons using persistent homology

This preprint has made available a large collection of labelled images of BECs containing 0, 1 or multiple dark solitons. The authors of that study trained a convolutional neural network to distinguish these three classes of images. Single dark solitons could be detected with an accuracy of about 90\%. On 2014 MacBook Pro each image took 2.3s to classify using the neural network. Our aim here is to develop a persistent-homology based approach with superior performance (both in accuracy and run-time). Fast and accurate machine learning-based identification of solitons would enable high-throughput experimental study of their dynamics by eliminating the time-consuming and at times error-prone manual identification of the solitons in the experimentally-obtained images.

Read more...

Edit (3/8/21): I have a more recent post discussing the finished manuscript resulting from this project.

Scarry quantum systems

There are various classes of non-equilibrium dynamics supported by isolated many-body quantum systems. In systems obeying the eigenstate thermalization hypothesis, initially-ordered states evolve into states that appear to be in thermal equilibrium with a fictitious bath. On the other hand, many-body localised systems retain memory of the initial state indefinitely via a set of emergent local conserved quantities. Recently peculiar quantum phases hosting co-existing thermal and athermal states with similar energy densities have been discovered. The athermal (or non-ergodic) eigenstates embedded within a chaotic spectrum are dubbed "quantum many-body scars".

Interest in this topic appears to have been sparked by a 2017 experiment using a 1D chain of 51 trapped Rydberg atoms, where long-lived interaction-induced oscillations of the atomic states were observed. A subsequent theory paper analyzed this behaviour using a relatively simple effective model, where strong interactions constrain the dynamics of certain initial states to a small subset of the full Hilbert space. Remarkably, the set of anomalous non-ergodic eigenstates is not necessarily limited to a small fraction of the full spectrum; models with confining interaction potentials or geometrical frustration can exhibit a fragmentation of the spectrum into an exponentially large number of disconnected sectors of various sizes!

One motivation for studying many-body quantum scars is that their long-lived coherent dynamics may be useful as a means of storing and manipulating quantum information. However, we still need to better understand what precise model features give rise to this non-ergodicity, and how to control and maximise the lifetime of the coherent many-body dynamics, such as by optimising longer-range interactions. Experiments using arrays of 200 Rydberg atoms published last month have demonstrated the importance of the underlying lattice geometry (persistent coherent dynamics were only observed in bipartite lattices) as well as the ability to stabilise the many-body scars using periodic driving. In the future I think it will be important to come up with more flexible ways to identify and measure the quantum many-body scarring and Hilbert space fragmentation, in particular to quantify its robustness to various perturbations.

Photonic band structure design using persistent homology

 

A short summary of our paper recently published in APL Photonics and presented at the APS March Meeting (talk slides available here).

Optimising the design of photonic crystals is challenging due to the large number of available degrees of freedom. We have shown how a machine learning technique known as persistent homology can be applied to classify the shape of photonic band structures and speed up the design process.

Persistent homology studies the shape of datasets over a range of different scales. Shapes are quantified by computing the numbers of topological features, such as holes or loops. Features persisting over a wide range of scales typically represent its true shape, while features with low persistence may be identified as noise and reliably discarded.

In the context of photonic crystals there are different important notions of shape. The shape of constant frequency lines or surfaces in the photonic band structure determines the radiation profile of emitters at that frequency embedded in the photonic crystal. The modes of photonic crystals also have abstract shapes characterised by topological invariants, which currently attract a lot of interest as a means of designing robust cavities and waveguides for light. 

We applied persistent homology to characterise low energy modes in a honeycomb photonic lattice and identify ranges of lattice parameters supporting interesting looped “moat band” and multi-valley dispersion relations. In the future, it will be interesting to apply persistent homology to study the properties of more complex many-body quantum systems.

Quantum chemistry on near-term quantum computers: the measurement problem

Quantum chemistry calculations including computing the ground state energies of complex molecules are touted as a promising application of near-term quantum computers. While numerous small-scale proof-of-concept calculations have been performed for small molecules, whether near-term quantum algorithms will offer any useful advantage over existing classical computers remains an intensely-debated question.

The variational quantum eigensolver is a leading candidate for near-term quantum computers. This algorithm uses a hybrid quantum-classical feedback loop to optimise the parameters of the quantum gates and minimise the required circuit depth. Each iteration of this algorithm requires estimating the energy of the trial solution, which requires O(1/ε^2) measurements to achieve an accuracy of ε. This becomes a severe bottleneck as the problem size is increased. 

For example, Google's recent paper preparing the Hartree-Fock wavefunction required 250,000 measurements to estimate each observable to sufficient accuracy, translating to a few seconds to perform a single iteration of the algorithm with N=12 qubits. They employed clever tricks to obtain the N^2 one-particle reduced density matrix elements required to compute the energy using only N+1 measurements. When electronic correlations are taken into account, N^4 two-particle reduced density matrix elements are needed to estimate energies. This poor scaling must be improved for the variational quantum eigensolver to have any practical applications.

Interestingly, larger error-corrected quantum computers may not solve this problem: Pessimists estimate that millions of qubits and years of runtime will be required to run error-corrected algorithms such as quantum phase estimation on useful problem sizes.

One approach towards tackling this problem is to use more efficient problem encodings. The most-commonly employed second quantization approach uses N qubits to encode N electron orbitals, and can represent states containing up to N electrons. However, typically the number of orbitals needs to be considerably larger than the number of electrons K in order to achieve convergence to accurate ground state energies. Alternatively, using a first quantization encoding can encode the quantum state using K log N qubits. Estimating the energy then requires measuring elements of a Hamiltonian with ~(KN)^2 nonzero elements. However, one needs to be careful to ensure that the required antisymmetry of the trial wavefunction is preserved. Nevertheless, this approach may be superior for achieving chemical accuracy when a large number of basis states is required. Further discussion on this point can be found in this paper.

Some other useful references I read today on this topic:

This preprint estimates runtimes for applying the quantum phase estimation algorithm to compute energies of catalysts.

This preprint proposes a Bayesian approach to estimating energies with runtime interpolating between the 1/ε^2 of the variational quantum eigensolver and the 1/ε of quantum phase estimation, which trades longer circuit depths for fewer required measurements.

This preprint discusses the measurement problem further.

 

Xanadu's latest quantum photonic chip

 The photonic quantum computing company Xanadu published an article in Nature last week reporting on the capabilities of their latest programmable Gaussian BosonSampling chip. Their device generates certain eight mode quantum states of light, which are detected (off-chip) using superconducting number-resolving photon detectors. In contrast to the much-publicised Gaussian BosonSampling experiment using 100 modes by the group of Jian-Wei Pan last year, this device is programmable. However, it will need to be scaled up to a much large number of modes in order to solve problems difficult for existing classical computers. Three proof-of-principle quantum algorithms were demonstrated using this chip:

1. Gaussian BosonSampling. BosonSampling is the problem of computing probabilities of obtaining multi-photon coincidences after applying a unitary transformation to quantum squeezed states of light. In the case of (Gaussian) squeezed states, the probabilities of individual detection events can be related to a property of the unitary transformation (Hafnians of its submatrices), which is hard to compute.

2. Molecular vibronic spectra. Here the problem is to compute the absorption or emission spectra of molecules, corresponding to changes in their internal (vibrational) states. These spectra can serve as molecular fingerprints. Although this task is not proven to be computationally hard, no efficient classical algorithms are known. By complementing the Gaussian BosonSampling circuit with an additional transformation (state displacement), the output photon number distribution can be used to simulate molecular vibronic spectra. Unfortunately, the present Xanadu chip does not implement displacements, and therefore was only used to solve a toy problem of this class (without displacements, and limited squeezing). In the case of coherent states, displacements can be implemented using a beamsplitter and an auxiliary mode. Another approach appears employ electro-optic modulators.

3. Graph similarity. This forms a variant of Gaussian BosonSampling. The connectivity of a graph is encoded by its adjacency matrix. This adjacency matrix is encoded into a multimode Gaussian state by suitably choosing the squeezing parameters and unitary matrix. Then, the distribution of output photon counts provides a fingerprint of the graph that can be used to compare the similarity of different graphs. In particular, the probability of a individual combination of output photons can be related to the number of perfect matchings of a subgraph of the graph. This is generally a hard task (related to the Hafnian), but if all the elements of the adjacency matrix have the same sign efficient approximate algorithms exist. I am not sure what important real-world problems involve adjacency matrices with elements with mixed signs...