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.