A supervised machine learning problem with a provable quantum speed-up

Quantum machine learning is touted as one of the big potential applications of quantum computers. In quantum machine learning kernel methods are a topic attracting increasing interest as a means of circumventing the barren plateau problem that makes training of variational neural network-like quantum circuits challenging if not impossible.

The idea behind the kernel trick is to map data to a high-dimensional feature space. Owing to the curse (or blessing in this case) of dimensionality, complex datasets can become linearly separable in the high-dimensional space, allowing one to perform supervised classification using simple linear models. Quantum circuits generate states belonging to a huge (exponentially large) Hilbert space, suggesting that they may be naturally suited towards computing high dimensional feature maps. At least, this is what many researchers hope.

The challenge is that having a high dimensional feature space is a necessary but not sufficient condition for performing accurate classification. Therefore one needs to come up with a kernel that is not only hard to compute on a classical computer, but is also able to achieve a classification performance superior to any efficiently classically-computable kernel. A daunting task to prove, and a study by researchers at Google published recently suggests quantum kernels for classical machine learning tasks may be hard to find.

Yesterday researchers from IBM published a study in Nature Physics which is the first to my knowledge to propose a machine learning problem for which a quantum kernel can provide a rigorous advantage compared to classical kernel methods. The clever trick used by the authors is to consider a feature map that uses Shor's algorithm as a subroutine, which has a proven quantum advantage. The authors show that this feature map can be used efficiently classify a dataset whose labels are related to the classically-hard discrete logarithm problem. In the original space the data appear to be randomly distributed, such classical algorithms are limited to random guessing. On the other hand, the quantum feature map leads to a clear hyperplane distinguishing the data classes.

Like many recent rigorous demonstrations of quantum speed ups for machine learning, the problem considered by the authors was chosen specifically for its ability to exhibit a quantum speed up, and does not have any known practical applications. It is interesting to note that the hardness of the discrete logarithm problem underlies certain cryptographic protocols. So this is work may be a promising step towards potential useful applications of quantum machine learning. Worth a closer read!

ILJU POSTECH MINDS Workshop on Topological Data Analysis and Machine Learning

As a newcomer to the field of topological data analysis (TDA), I found the ILJU POSTECH MINDS Workshop on Topological Data Analysis and Machine Learning held this week to be highly informative.

I was not able to attend all the talks live due to other commitments and will miss the last day, but luckily the recorded talks are available for viewing later. Here are summaries of the talks I saw so far:

Paul Rosen (University of South Florida) talked about analyzing and visualizing graphs using TDA. First, TDA can provide optimized initial layouts for spring-mass visualization of graphs, allowing features such as clusters and cycles to be more easily resolved. Second, persistent homology combined with dimensional reduction (manifold learning) can be used to detect events or anomalies in time varying graphs. As an example, he considered the time-varying graph describing email interactions between members of a large research institute. Finally, he showed how Mapper can be used to generate simplified representations of large complex graphs.

Gary Shiu (University of Wisconsin) presented applications of TDA to some problems in physics, including quantifying the structure of the string landscape, measuring the large scale structure of the universe, and identifying phase transitions in spin models. For large datasets in Euclidean space, it's much more efficient to use the alpha complex (which has polynomial scaling with the number of data points) than the Vietoris-Rips complex (which scales exponentially). Persistent homology is useful because it can directly identify nonlocal physical features of interest, such as vortices and filaments.

Bei Wang (University of Utah) gave a talk on how TDA can be used to understand the behaviour of deep neural networks. Focusing on popular neural networks used for image classification, TDA can be used to analyze the shapes of the activation vectors at each layer and construct effective decision trees, showing for example how the neural networks distinguish deer from horses by the presence of antlers. This is clever step towards making deep neural network models more interpretable.

Moo K. Chung (University of Wisconsin - Madison) has used persistent homology to distinguish different configurations of the covid-19 virus's spike proteins. He discussed how the large size of the molecule and large number of topological features requires methods to simplify the information encoded in the persistence diagrams. One method - persistence images - based on coarse-graining of the persistence diagram, is unsuitable because it omits important information carried by a few of the features. It is preferable to use alternate methods such as persistence landscapes, which retain all the information while converting it into a vector space form, enabling different persistence diagrams to be systematically compared or fed into machine learning algorithms.

Naoya Tanabe (Kyoto University Hospital) talked about how persistent homology can be used for detection of lung diseases in 3D CT images. The usual manual approach is based on expert analysis of 2D lung images. Deep neural network-based machine learning can be used to carry out supervised classification of these images, but it requires large sets of training data and underlying model lacks interpretability. Persistent homology is a promising alternative, as it is able to directly recognise the relevant local image features used to identify the diseases of interest, namely localized clusters and voids in the 3D intensity images. This allows accurate automatic diagnosis using small training sets and simple rule-based decision trees.

Kelin Xia (Nanyang Technological University) provided a survey of his work on the use of TDA to characterize the shapes of complex molecules, with applications to drug design. He emphasized that in the case of point clouds constructed from positions of the atoms comprising the molecule, every feature birth and death scale is meaningful, corresponding to characteristics such as bond lengths and ring sizes. Feature sizes are typically divided into two groups, corresponding to short and long range features of the molecule. The former provides a fingerprint of which atoms and bonds are present in the molecule. Changes in the long range features are sensitive to chemical reaction dynamics. The multiscale information captured by persistent homology forms ideal features for use in machine learning-based drug design and discovery. He also mentioned recent work on generalizing persistent homology to hypergraphs describing more complex many-body interactions, which is relevant to collaboration networks.

Creative research takes time

Nowadays funding agencies prioritise research with immediate applications. Grants for early career researchers provide funding for only a few years, requiring funded projects to have a quick and clear path to fruition. However, in basic research the eventual applications are often not those that were first envisaged.

Perhaps my favourite research project was our study of topological effects in "leaky" optical systems, published earlier this year in Nature Physics. See here for a popular summary. I am proud of this work not merely because the results were eventually published in a glossy journal, but rather because it was a pure, curiosity-driven project involving short bursts of inspiration and progress separated by many months.

This project originated from a grant application we prepared in August 2018. The host institution had expertise in photonic crystal fibers, so we were interested in whether the photonic crystal fiber platform could be used to observe interesting topological phenomena. However, photonic crystal fibers are leaky wave systems which continuously radiate energy into their environment, so it was not clear whether our experience in designing topological states for bound modes would be useful in this setting.

We started working on the idea by implementing well-known approaches for numerically computing leaky modes with the help of a tutorial article, studying some simple one-dimensional examples to gain some intuition for the platform. 

By April 2019 we had developed a tight binding-like formalism allowing us to design and study topological wave effects in leaky wave systems, but we did not know what our formalism could be useful for apart from computing the decay rates of leaky topological edge states. 

After a few conferences and many discussions with other researchers, in October 2019 we finally stumbled upon the neat idea of using radiation losses to controllably fill energy bands and measure their bulk topological invariants. 

We finished a draft manuscript by the end of November 2019 and shared with some collaborators. Their feedback was that the idea was interesting, but it wasn't clear how easy it would be to experimentally test our theory. 

We spent a few more months carrying out numerical simulations of possible designs and polishing the manuscript, finally submitting it in May 2020. Our collaborators' impression was echoed by the referees, who requested more detailed and explicit simulations of our designs in a revised manuscript, which was finally accepted in December 2020.

Take home messages:

-Find inspiration for new lines of research in old reviews and tutorials, not the latest papers published in high impact journals.

-If you get stuck don't be afraid to put the project aside for a few months and work on other directions.

-Creative research takes time - 2.5 years between the initial idea and eventual publication in this case (a theory project). Experimental projects can take even longer.

Stronger quantum supremacy

 On arxiv today: Strong quantum computational advantage using a superconducting quantum processor, by the group of Jian-Wei Pan at USTC.

This preprint reports a large 66 superconducting transmon qubit quantum processor, with performance similar to Google's Sycamore processor.  The random circuit sampling protocol is used to demonstrate a quantum computational advantage with 56 qubits (c.f. the previous 53 qubit Google experiment). More measurements are taken per random circuit (19 million samples vs 3 million) to obtain a higher cross entropy benchmarking fidelity (9 sigma rejection of uniform sampling vs 5 sigma). Because the difficulty of classical simulation increases exponentially with the number of qubits, this small increase in the device size incurs a 2-3 orders of magnitude-increased cost of classically simulating the circuit.

This is a significant breakthrough - Google no longer has a monopoly on large scale programmable superconducting quantum circuits!

Edit: Today the USTC team released another preprint reporting an upgraded and programmable Gaussian boson sampling experiment!

CLEO covid conferencing

I attended (virtually) the CLEO/Europe conference last week. It's been said many times before by others, but networking and informal discussions which often lead to new creative lines of research do not occur to any significant extent at online conferences. The one silver lining is that when things return to normal, conferences will hopefully be run in a hybrid mode enabling those unable to attend in person to at least view talks remotely.

Some of the interesting talks I saw:

Fabio Sciarrino from Sapienza University of Rome gave an overview of Boson Sampling and discussed his group's recent work on using thermoelectric tuning of a laser-written waveguide array to create a semi-programmable Boson Sampling device. This aims to overcome the main limitation of the recent Chinese photonic quantum supremacy experiment (that their device is not programmable). The preprint is available here.

Vera Neef from Rostock University discussed the generation of non-Abelian geometric phases using two photon quantum states propagating through an adiabatically-modulated array of four coupled waveguides. The approach can be extended to photonic simulation of quantum chromodynamics.

Christophe Galland from EPFL gave an overview of his group's recent work on molecular optomechanics and nanocavities. The former is an interesting platform for observing quantum coherent effects at room temperature, by using a laser beam to excite a high frequency vibrational resonance of a molecule; Raman scattering can then be used to probe the resulting vibrational quantum states.

Nathan Goldman from Universite libre de Bruxelles presented a scheme to detect fractional quantum Hall states of bosons. The idea is to prepare a few-body ground state of bosons in a topological (Chern) band trapped by a confining potential, turn off the confining potential, and then apply a uniform acceleration. The resulting transverse Hall shift exhibits quantized plateaus which can be used to measure the many-body Chern number. For larger numbers of bosons, density measurements can be used to obtain the Chern number. The study was published in PRA last year. These effects could be probed using superconducting qubits using an approach similar to this paper, but with a larger lattice and more photons.

Christina Jörg from Pennsylvania State University discussed the creation of bound states in the continuum in photonic crystals using tailored environmental coupling. By embedding a photonic crystal in a suitably-designed thin photonic crystal cladding, one can create bound states in the continuum above the diffraction limit (i.e. with a volume larger than the operating wavelength). The preprint is available here.

Dynamical versus spectral localization in dissipative systems

A short summary of this paper which was published in Nature Photonics last week.

Waves in random or disordered media can exhibit Anderson localization. In Anderson localization, interference between different wave scattering paths (and in particular, constructive interference of backscattering) results in a complete suppression of wave propagation; waves remain localized around their sources indefinitely, with an amplitude (or intensity) decaying exponentially with the distance from the source.

Anderson localization is a universal phenomenon. It was originally predicted in a 1958 publication analyzing electrons in disordered crystalline materials, and has since been observed for a wide variety of waves including matter waves (Bose-Einstein condenstates), optics, and acoustics.

Historically, a thorny issue complicating the observation of Anderson localization in classical wave systems such as optics and acoustics has been the question of how to distinguish Anderson localization from absorption-induced localization; both lead to a similar exponential decay of the wave amplitude.

The present work concerns the generalization of Anderson localization to disordered dissipative optical wave systems with random distributions of gain and/or loss, and the subtle distinction between spectral localization and dynamical localization.

Spectral localization refers to localization of the modes of the medium. Each mode has a specific energy (frequency). The mode may be excited by placing a source (e.g. a speaker in the case of acoustic waves) in the medium tuned to that frequency, in which case the amplitude profile of the generated wave will match the profile of the correspond mode.

Dynamical localization refers to the time evolution behaviour of wavepackets comprising a range of frequencies, excited by switching the source on for a short time.

In wave systems that are Hermitian (conservative, i.e. no gain or loss of energy), spectral and dynamical localization coincide because the time evolution of any wavepacket can be obtained by expanding it as a sum of the medium's modes. The paper shows that this is not the case for wave systems with dissipative disorder; dynamical delocalization can occur despite spectral localization. In other words, waves generated by a monochromatic source will have an exponentially localized amplitude profile, whereas waves emitted by a broadband source will spread to distant parts of the system.

To demonstrate this dynamical delocalization, the authors had to carefully distinguish between energy transport and energy loss due to absorption. In particular, for lossy media the wave amplitudes are always decaying exponentially in time. At any moment in time we can consider the shape of the wave's amplitude distribution (e.g. by increasing the sensitivity of the camera or microphone used to detect the waves) and how it decays with separation from the source. 

In dissipative wave media the modal expansion is still valid, but different modes will have different loss rates. Therefore, the relative amplitudes of the different modes in the expansion will change in time, leading to large changes and in particular spreading in the normalized wave amplitude profile - dynamical delocalization. This is the main result of the study, which observes the phenomenon using a cleverly-designed system of coupled optical fibres.

Has topological photonics plateaued?

Not yet.

Data taken from Web of Science. I compare the publication rate of papers on topological photonics with some other hot topics in photonics during my graduate studies. Of course, the number of publications measures interest in a topic and does not necessarily correlate with real progress.

Whether topological photonics was close to reaching a plateau was a topic of discussion during a workshop I attended in 2019. Close to half of all papers on topological photonics have been published since 2019! During this period the main emerging research directions have been nonlinear effects, non-Hermitian topological structures (i.e. with gain and/or loss), higher order topological phases, and bulk topological defects. Ongoing experimental efforts in all of these directions is likely to sustain interest for the next few years, at least. Will the peak be followed by a sustained plateau or an immediate decline?