What's next for applied quantum computing?

NISQ (noisy intermediate-scale quantum) algorithms generated a lot of excitement and a lot of publications - the 2022 review has amassed almost 2000 citations! Nowadays the tone is more subdued, with many experts believing any useful practical applications of quantum processors will need quantum error correction. The new hot topics are understanding how to make useful error correction a reality, and what might be done with a few hundred logical qubits. 

What then should a new student interested in applied quantum computing focus on?

Ryan Babbush and collaborators already argued in 2021 that algorithms with quadratic speedups won't be useful in practice. So sorry, but we won't be able to solve complex industry optimization problems using Grover search. However, their analysis indicated that quartic speedups and beyond could be practically useful. Which quantum algorithms have this property?

Consulting the excellent review article Quantum algorithms: A survey of applications and end-to-end complexities, there are only a few examples of known or suspected quartic or beyond end-to-end quantum speedups! They are:

Tensor principal component analysis (PCA). Ordinary PCA is a data reduction step widely used in data analysis and machine learning. It's not yet clear what tensor PCA might be useful for, but if an application can be found quantum computers will probably give a useful speedup.

Topological data analysis (TDA). This is another promising direction where a useful speedup for certain problems is possible. Following an initial buzz of excitement in 2022, it's unclear whether there are practical applications for where such a speedup can be useful. Recently-developed quantum-inspired classical algorithms will be useful to identify potential use-cases for quantum TDA.

On the classical computing side, quantum-inspired tensor network methods are very promising for near-term applications.  

There are also other approaches (QAOA, quantum machine learning) which attracted a lot of interest since 2020 and are still being explored theoretically, but at least in their present formulations they seem unable to provide a useful speedup for classical problems, with their most promising applications related to directly studying or simulating certain quantum systems. Thus, interest has shifted from "beating" classical methods on carefully-selected problems to better understanding the foundations of quantum machine learning. While this is a fascinating topic, it is at this stage it is more theoretical than applied research.

From classical to quantum HodgeRank

This is a rather late summary of a cool preprint I saw a few months ago: Quantum HodgeRank: Topology-Based Rank Aggregation on Quantum Computers 

This work is inspired by and builds on quantum subroutines developed for efficiently solving high-dimensional topological data analysis problems, offering superpolynomial speedups for ranking higher-order network data by developing a quantum version of the classical HodgeRank algorithm.

What is HodgeRank? It was originally proposed in 2011 as a better way of ranking incomplete or skewed datasets, for example based on user ratings or scores.

The basic idea is to apply an analogue of the Helmholtz decomposition (used routinely in electromagnetics) to graph data, enabling one to assign a ranking based on incomplete pairwise preferences. Importantly, HodgeRank outputs not just a raw ranking, but also an estimate of the quality of the ranking via the construction of local and global cycles present in the optimal ranking. To be specific, the returned optimal ranking is unique and fully consistent if the preference matrix can be written as the gradient of some scalar ranking function. If it cannot, then there are inevitable ambiguities present in the preference data due to the existence of global or local cycles. 

An example of a local ranking cycle is the following: B is preferred over A, C is preferred over B, and yet A is preferred over C. This leads to the ranking A < C < B < A, thus forming a cycle. It is better to identify cycles such as these and acknowledge that a traditional ranking does not make sense for these items. This is what HodgeRank does! User preference data is rarely consistent, so cycles such as these routinely occur in the wild, for example in user rankings of movies on online platforms such as Netflix. 

As a generalization of HodgeRank, Quantum HodgeRank promises the ability to perform ranking tasks on preference data forming higher-order networks, avoiding the exponential scaling with network dimension faced by classical algorithms. Moreover, the authors of the preprint argue that HodgeRank cannot be dequantized (i.e. implemented efficiently using a randomized classical algorithm) in the same manner as quantum TDA algorithms for the Betti number problem. Moreover, while applications of high-dimensional Betti numbers (and even their occurrence in real datasets) remain unclear, HodgeRank represents a ranking problem with more likely concrete applications. Thus, this looks like an exciting area to keep an eye on. 

It is also interesting to speculate on whether (classical) HodgeRank or HodgeRank-inspired methods can be useful for understanding the behaviour of interacting many-body quantum systems, where it is typically intractable to sample all of the pairwise interaction elements of Hamiltonians as the system size increases, but incomplete or skewed sampling is readily available. Watch this space!

What I've been reading lately

Continuity Equation for the Flow of Fisher Information in Wave Scattering

We can get an intuitive understanding of a wide variety of wave systems ranging including photonics, acoustics, and electronic condensed matter by visualizing the flow of intensity, energy, or probability density through them. These flows are useful for understanding the behaviour of conserved quantities, since they can be decomposed into sources, sinks, and solenoidal components. This paper shows that the Fisher information, a measure which bounds the precision with which parameters of interest can be measured, similarly obeys a conservation law enabling its visualization in terms of information flow. Remarkably, the Fisher information flow gives distinct insights into wave propagation in complex media and is complementary to more standard analysis methods based on the energy flow. This work raises many interesting questions and opens new possibilities!

Energy and Power requirements for alteration of the refractive index

This is another paper in a series of perspectives on estimating the capabilities and potential limits to the performance of photonic devices using relatively simple classical oscillator models and sharp physical insights. The take home message is that the power required to achieve a given level of optical modulation depends primarily on the interaction time, which depends on the device geometry (e.g. resonator vs travelling wave), without substantial variation among different materials. This suggests that improvements in power efficiency are more likely to come from improvements in fabrication methods and device design, rather than the discovery of some new material with substantially better physical properties.

Quantum Algorithm for Computing Distances Between Subspaces

There's growing evidence that the best place to look for a quantum advantage for classical machine learning will be geometrical or topological problems that have a natural connection to quantum systems. One example is the Betti number problem, which maps to computing the ground state of supersymmetric many-body Hamiltonians. This work shows that computing distances between k-dimensional subspaces of an n-dimensional space can be done exponentially faster using a fault-tolerant quantum computer. The algorithm exploits the ability to efficiently encode subspaces into quantum states combined with quantum signal processing. Subspace distances have to large scale machine learning and computer vision problems, suggesting the asymptotic exponential advantage promised by a fault-tolerant quantum computer could lead to practical speedups.

Will there be a useful quantum advantage for topological data analysis?

 

We don't know yet. 

Prominent applications of topological data analysis (TDA) including Mapper-based visualisation are based on fast and interpretable heuristics. While quantum TDA may speed up the calculation of high-dimensional Betti numbers, it doesn't help with understanding when and why high-dimensional topological features might be important, and whether they need to be computed to high precision or classical Monte Carlo methods can give a sufficient accuracy in practice. What high-dimensional Betti numbers might be good for needs to be determined empirically using machine learning benchmark datasets and the best classical algorithms.

Beyond the Betti number problem, for which quantum algorithms have already been proposed, it will be interesting to explore what other TDA methods could be sped up using quantum subroutines. For example, the nonzero eigenvalues of the persistent Laplacian also seem to be useful as features for machine learning algorithms, in contrast to traditional persistent homology methods that focus only on the zero or near-zero eigenvalues of the persistent Laplacian. The speedup for quantum persistent homology comes from being able to construct the persistent Laplacian exponentially faster the best-known classical methods. If there is useful information that can be extracted from the persistent Laplacian without requiring the quantum singular value transformation or rejection sampling, the resource requirements for a quantum advantage would be reduced enormously.

Thanks to the the team at QCWare for inviting me to give a seminar on this topic and the thought-provoking discussions afterwards!

Quantum advantage for machine learning using subspace states

My posts on quantum computing are usually pessimistic, in an attempt to counter the excessive amount of hype present in the literature and media. Recently I stumbled upon a refreshingly humble and exciting paper which presents a few quantum algorithms with the potential for a near-term quantum advantage:

Quantum machine learning with subspace states

I will attempt to summarise the main ideas of this paper and why they are important. For a video summary, one of the authors of the preprint (Anupam Prakash) also recently presented this work at a workshop (video here).

Introduction

Behind all the hype on quantum machine learning and optimization, practical algorithms remain scarce. Variational algorithms such as QAOA are extremely challenging to implement on problems of useful size. Moreover, the need for iterative optimization of the circuit parameters means that convergence issues may prevent these algorithms from out-performing existing highly sophisticated classical optimisation algorithms.

On the other hand, most non-variational algorithms are designed for fault-tolerant quantum computers and either only offer modest speedups (quadratic in the case of quantum amplitude amplification / quantum search), which may not be suitable for achieving a quantum advantage, or the claimed exponential speedups (quantum linear algebra subroutines) evaporate using "dequantization" techniques to obtain quantum-inspired classical algorithms with similar performance. The key point underlying dequantization is that certain quantum algorithms assume access to input data stored in quantum RAM (QRAM); their apparent speed-up comes from the additional overhead required to load the classical data into the QRAM.

Quantum algorithms for topological data analysis (QTDA) are one promising exception that promise an exponential quantum speedup that persists even when the classical data encoding step is taken into account. The reason for this is that QTDA algorithms take a set of N classical vectors as their input, and then consider different subsets of k vectors. Combinatorial explosion means that the runtime of classical algorithms for TDA grows exponentially with k, while quantum circuits can process and efficiently sample from different combinations in parallel, enabling an exponential speedup.

It turns out that performing efficient weighted sampling of subsets appears as a subroutine in other machine learning algorithms. One example is performing linear regression on large datasets by sampling a small number of the data points; the ability to use weighted sampling to construct an unbiased estimator of the optimal regression model allows the calculation to be performed using distributed computing.

Quantum subspace states are a generalization of amplitude encoded quantum states. Amplitude encoding is a way to map an n-dimensional data vector into a quantum state. Amplitude encoding starts with the |100...0> state, and then performs a sequence of n-1 data-dependent reconfigurable beam-splitter gates to produce a superposition of n unary (i.e. only one of the qubits is in the state |1>) quantum states using a circuit of depth log(n), called a data loader circuit. This scaling is very good for near-term quantum processors lacking quantum error correction; hardware providers are adding more and more qubits, but their devices can still only run very shallow circuits.

Subspace states generalise amplitude encoded states to, as the name implies, d-dimensional subspaces of the n-dimensional vector space. One way they can be viewed is as a suitable rotation of the product state (|1>)^d (|0>)^(n-d), i.e. with the first d qubits in the |1> state. They can be efficiently generated using a sequence of d "Clifford Loader" circuits applied to the initial state (|0>)^n, which has depth O(d log n) and O(nd) gates. Thus, subspace states are also NISQ-friendly.

Applications of quantum subspace states

(1) Simply measuring quantum subspace states in the computational basis, one samples bitstrings with probability weight given by the determinant of d-dimensional submatrices of the input data. The best classical algorithm scales as O(d^3), while the quantum sampling requires only O(nd) gates and depth O(log n). This kind of weighted sampling can have applications in distributed machine learning and randomised linear algebra algorithms. 

(2) Singular value estimation of compound matrices. Here, the quantum subspace state is used as an input to the quantum phase estimation algorithm, allowing k-order correlations to be decomposed into a linear combination of subspaces of singular vectors of some input matrix A. This has applications in joint recommendation algorithms.

(3) Quantum topological data analysis. The Clifford loader circuit provides an exponentially shallower [O(log n) vs O(n)] way to encode the Dirac operator of a simplicial complex.

Take home message

To achieve a quantum advantage for machine learning it is not necessary to encode classical data into a highly entangled quantum state that makes full use of the exponentially-large Hilbert space. Machine learning algorithms based on sampling from subsets of classical large datasets use shallow circuits and do not need variational optimisation, but still exhibit quantum speedups. This makes them highly promising for near-term applications of quantum processors; full quantum error correction is not required!

Resource-efficient quantum machine learning using matrix product states

Practical applications of noisy intermediate-scale quantum (NISQ) processors will require algorithms that combine qubit-efficiency and gate-efficiency with quantum speedups. This is especially challenging because qubit-efficient algorithms are typically based on highly-entangled qubits that require deep circuits to generate and manipulate.

For example, while optimally qubit-efficient encodings require only log(N) qubits, where N is the input data size, the encoding circuit depth will be polynomial in N. This is bad because NISQ processors are practically limited to circuit depths linear in N. At the other extreme, classical data can be encoded as an N-qubit product state using single qubit rotations, but this kind of entanglement-free encoding will not out-perform a classical computer. What is needed for practical applications is a way to control the level of compression so that one can make full use of the available qubit numbers and circuit depth.

A new preprint posted to arXiv shows how matrix product state-based data encodings allow one to control the trade-off between qubit and gate resources: Data compression for quantum machine learning. Specifically, the bond dimension $\chi$ of a matrix product state controls its degree of entanglement; data can be encoded into a matrix product state using a circuit depth of O(poly($\chi)\log N)$. Qubit compression is achieved by segmenting the data into a product state of patches, where each patch is described by a matrix product state. Larger patches enable stronger compression, at the cost of requiring a larger bond dimension to accurately encode the input data.

As an application of the approach, the authors combine their matrix product state data encoding with a matrix product state-based quantum classification algorithm. Using shallow hardware-efficient circuits the authors demonstrate modest accuracy at classifying images from the Fashion-MNIST dataset. The matrix product state classifier does however require variational optimization of the gate parameters, requiring on the order of 100 gradient-free optimizer iterations to converge for the small problem sizes considered. This will increase the cost of running the classifier on real quantum hardware. It would be timely to study the combination of matrix product state-based data encodings with non-variational shallow quantum algorithms, such as quantum kernel methods.

Generalised coherent states for variational quantum circuits

One challenge with designing variational quantum algorithms is choosing a good ansatz for the parameterised quantum circuit. One needs to balance multiple competing requirements: 

1. The circuit needs to be complex enough to be able to express a good solution to the problem at hand.

2. The parameterisation should be simple enough to admit analytical calculation of gradients, so that the solution can be found efficiently using gradient descent.

3. The circuit should generate non-trivial quantum entanglement, which is a necessary (but not sufficient) condition for a classical computer to be inefficient at obtaining the same solution.

The most common choices for parameterised circuits either do not meet all three requirements, or give rise to very deep circuits that cannot be run on current quantum processors.

Last week I saw an interesting preprint posted to arXiv:

A Variational Ansatz for the Ground State of the Quantum Sherrington-Kirkpatrick Model

This work builds on an earlier paper by the same group: Generalization of group-theoretic coherent states for variational calculations.

The authors consider variational quantum states based on generalised coherent states, which are formed by applying a single qubit and two qubit (entangling) rotations. Crucially, the form of the ansatz enables expectation values of Pauli operators (required to obtained energies and gradients) to be measured efficiently, with the required number of measurements scaling polynomially in the system size. At the same time, the non-trivial entanglement of the generalised coherent states means that evaluating the overlap between different parameterised states is a classically hard task.

These properties seem quite promising for quantum kernel methods: the analytical gradients would allow one to optimise key properties of the quantum feature map, while the model output (quantum state overlaps with the training data) remains hard to simulate classically.

It is interesting to speculate on whether these parameterised quantum states could be adapted form the basis for a quantum perceptron; they are simple and efficiently trainable, but I am not sure whether they are also modular and can be stacked to form a deep quantum neural network.

Perspectives on quantum machine learning

Is quantum advantage the right goal for quantum machine learning?

This perspective article is a must-read for anyone working on or interested in quantum machine learning. In it, the authors argue that current research should not focus on attempting to "beat" existing classical machine learning approaches; rather, we should aim to better understand the fundamentals of how quantum learning may work. For example, what is the quantum analogue of a perceptron, and how can we quantum machine learning algorithms be related to better-understand classical learning theory?

In my opinion, unless someone can come up with a quantum version of the backpropagation algorithm, quantum neural networks will never be competitive with classical deep neural networks, because they will be too slow and expensive to train. 

Even avoiding this training issue (e.g. using kernel methods), the bottleneck of transferring data into and out of the quantum circuit will be huge in practical applications and may overwhelm any quantum speedups.

I am most excited about topological data analysis-based approaches because quantum TDA algorithms seem to avoid this data input bottleneck.