Learning Diffusion

Techniques for efficiently evaluating derivatives of functions underlie numerous large-scale applications of machine learning algorithms including computer vision and natural language processing. Machine learning algorithms are trained by minimizing a cost function, typically using some form of gradient descent. For example, gradients of the cost function of artificial neural networks can be efficiently computed using backpropagation, discovered (and re-discovered) since the 1960s.

Backpropagation is a special case of automatic differentiation, which can be applied to any function specified by a computer program, including those involving loops, conditional statements, and recursion. Reverse-mode automatic differentiation is highly efficient when the function of interest has a small number of outputs (dependent variables) and many inputs (independent variables).

Automatic differentiation is particularly promising for variational problems in physics, where one seeks a configuration in a high-dimensional phase space that minimizes the total energy. In the past, such problems would be solved by using hard-won physical insight to come up with a simple trial function (such as a Gaussian with a variable width and centre), evaluating the cost function gradients by hand, and then numerically performing the gradient descent. Nowadays this procedure could be replaced by a deep neural network, making the physicist's job a lot easier (or redundant for this kind of problem?).

Another important class of machine learning models are generative models, which are trained to generate samples from some unknown or complicated probability distribution. This becomes challenging when dealing with very high-dimensional spaces, for example in problems such text-to-image conversion. Generators based on diffusion models have attracted enormous interest this year, sparked by the success of DALL-E 2 and subsequent open source alternatives including stable diffusion, which is quite awesome. You can play with online here, or even install it on your own computer!

The seminal paper introducing diffusion models was directly inspired by the physics of diffusion. The approach taken by these models is to gradually corrupt the training data into a simple-to-model distribution (such as a uniform or gaussian distribution) via diffusion, and then train a neural network to reverse the process and reproduce the original data, as shown below (image taken from Fig. 1 of the paper). After the neural network is trained, new samples drawn from the easy-to-model distribution can be rapidly transformed to the learned distribution by reversing the diffusion. In effect, the problem of estimating and generating samples from the underlying probability distribution is reduced to fitting a function to carry out the reverse diffusion process.

 It is interesting to speculate on possible applications of these cutting-edge machine learning techniques to physics. For example, in the quantum computing context there is the problem of sampling measurement outcomes from a specified (noisy) quantum circuit.

Thresholds for quantum advantage for topological data analysis

More quantum topological data analysis (QTDA) preprints which I missed while I was on holiday:

Quantifying quantum advantage in topological data analysis

In contrast to the recent works by IBM focused on QTDA algorithms for near-term quantum processors without quantum error correction, this work presents improvements to the original QTDA algorithms for fault-tolerant quantum computers.

It is conjectured that QTDA may provide an exponential speedup compared to the best possible classical TDA algorithms. Establishing such a speedup rigorously is challenging, however, in part because the run-time of QTDA depends on the spectral properties of the graph Laplacian operator; one needs to estimate the fraction of zero (or approximately zero) eigenalues of the graph Laplacian, which is hard if there if the gap between its zero and nonzero eigenvalues is small. The authors give examples of families of graphs exhibiting both large Betti numbers and large gaps, suggesting that a useful quantum speedup is in principle possible for certain problems.

On the other hand, the authors also propose a "dequantized" randomized classical algorithm for estimating the fraction of zero eigenvalues using imaginary time propagation generated by the graph Laplacian. The scaling of their classical algorithm is polynomial for certain classes of graphs. This means that simple arguments for an exponential quantum advantage based on the exponential scaling of the size of the graph Laplacian are insufficient.

The authors conclude that "while the exact threshold for quantum advantage depends on constant factors in the classical algorithms, it seems likely that this application will fall somewhere in between quantum chemistry applications and Shor’s algorithm in terms of the resources required for quantum advantage."

Another recent work by Schmidhuber and Lloyd, Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis, tackles the question of quantum advantage for TDA using computational complexity theory. They argue that the complexity class of the Betti number calculation (estimation) problem is #P-hard (NP-hard), implying the QTDA will exhibit an exponential scaling for (almost all) inputs and enable at a best a polynomial speedup compared to the bet classical algorithms. They speculate that an exponential speedup may be possible by using simplices as input data rather than points and vertices. 

A few thoughts:

• One approach used by existing classical TDA libraries to study large intractable datasets is randomized sampling of the input data, exactly computing the Betti numbers of random subsets of the data. I wonder how this compares to the dequantized TDA algorithm, which computes (approximately) the Betti number of the full dataset using Monte Carlo sampling.
• In many practical applications one does not need just the Betti number of a single graph or simplicial complex, but rather one studies the persistent homology of families of graphs or simplicial complices. An important question is whether the approach here (and also the linear-depth algorithms developed by IBM) can be generalized to quantum algorithms for computing persistent homology.
  

I am looking forward to reading these papers more carefully over the coming weeks.

IBS-APCTP Conference on Advances in The Physics of Topological and Correlated Matter

Last month I attended the IBS-APCTP Conference on Advances in The Physics of Topological and Correlated Matter. It was great to be attending a conference in-person after so long! Slides from many of the talks are available here. Summaries of some of the talks from the notes that I took:

------

Prof. Changyoung Kim (IBS/SNU) spoke about tunable anomalous Hall conductivity in correlated electron systems. The anomalous Hall effect is a Hall effect that occurs in the absence of an external magnetic field in materials exhibiting a spontaneous magnetization of the electron spins. An extreme example of this is half-metals, where the energy bands are completely filled (insulating) for one spin and partially-filled (conducting) for the other spin. 

One way to potentially enhance the anomalous Hall conductivity is to dope the material to tune the Fermi level of the partially-filled band to a region of high Berry curvature, but in some cases this kind of perturbation picture will fail due to the doping-inducing a reconstruction of the band structure to form a distinct phase. It is important to distinguish the intrinsic anomalous Hall conductivity from (potentially much larger) extrinsic (disorder-induced) contributions.

Another approach applicable to thin film materials is substrate-induced magnetization, which can lead to interesting thickness-dependent material properties including the magnitude and even sign of the anomalous Hall conductivity changing as single layers are added or removed. These changes can be resolved using spin-resolved ARPES.

------

Prof. Masatoshi Sato (Kyoto University) talked about Majorana fermions in topological superconductors, particularly differences between spinless and spinful Majorana fermions; the latter require additional symmetries for protection. The symmetry requirements will likely make it quite extremely challenging to carry out robust braiding operations required for topological quantum computation. Another application of Majorana particles outside of quantum computing is to use them to probe the properties of the underlying superconductor, since they share the same symmetries as the underlying superconducting gap function.

------

Prof. Takashi Oka (University of Tokyo) covered Floquet engineering of topological bands and novel topological nonlinear optical effects, including Hall response dependent on a nonlinear gauge-invariant curvature term, related to theoretical analysis published in Nature Physics at the end of last year. Floquet engineering of topological bands has of course been a very influential idea since the late 2000s (Oka and Aoki's 2009 paper has amassed more than 1000 citations!), with a variety of linear (and nonlinear) phenomena occurring sensitive to the period and strength of the periodic Floquet driving.

------

Prof. Gil-Ho Lee (POSTECH) discussed his group's experimental work on Floquet engineering of graphene using microwaves. The effective strength of the Floquet-induced band structure modifications scales as \( E / \omega^2 \), where \( E \) is the (normalized) field strength of the drive and \( \omega \) is its frequency. By using a lower frequency microwave drive (instead of more conventional optical pumping), the required field strength is reduced, making it practical to study continuous wave driving while maintaining a sufficiently low temperature. The catch, however, is that the lower drive frequency is accompanied by smaller Floquet band gaps that require scanning tunneling microscopy to resolve. Ongoing work aims to observe Floquet topological bands induced by polarized microwave driving, and to improve the coupling between the microwave antenna and the graphene sheet to probe higher Floquet drive strengths.

------

Dr. Andrew Pierce (Harvard -> Cornell?) talked about thermodynamic measurements of topological states in magic angle graphene, the subject of his PhD studies and three (!) Nature Physics papers published in the last year ([1], [2], [3]). He mentioned that bilayer graphene is an extremely fickle system - every sample is different and it is very hard to reproduce experimental results. Trilayer graphene, on the other hand, can offer a more reliable platform for exploring moire phenomena including twist-induced superconductivity. 

------

Dr. Robert-Jan Slager (Cambridge University) talked about unconventional multi-gap topological phases. In the conventional topological band theory we usually consider a single band gap whose topological properties (and the existence or absence of robust edge states) is determined by topological invariants of all the bands below the gap, leading to the well-known periodic table of topological insulators. Interestingly, the topological band theory can be generalized to novel multi-gap topological phases which are trivial under the conventional topological band theory, involving partitions of the band structure into three or more sectors. One example of non-trivial multi-gap topological invariant is the Euler class. These ideas are now being generalized to Floquet systems.

------

Prof. Aris Alexandradinata (UC Santa Cruz) presented a topological principle in photovoltaics. Bulk photovoltaic effects known as shift currents are attracting interest as a potential route towards making more efficient solar cells. A nonzero shift current requires a material with broken inversion symmetry. Beyond this necessary condition it is not clear what is the best way to maximize the strength of the shift current. New classes of topological phases may provide a route to finding materials with stronger shift currents. He currently as a few PhD and postdoctoral research fellow positions open!

------

Prof. Emil Bergholtz (Stockholm University) talked about fractional Chern insulators and quantum geometry in moire materials. A long-standing goal in the field of topological materials has been the search for fractional Chern insulators, which are hoped to exhibit high temperature fractional quantum Hall states. The "simple" picture of a fractional Chern insulators is that they are lattice systems exhibiting nearly flat bands with nonzero Chern numbers that form a lattice analogue of the Landau levels underlying the conventional quantum Hall and fractional quantum Hall effects. In practice, however, the physics is more complicated. Even if the energy dispersion is relatively flat, other properties of the band including its quantum metric and Berry curvature can be strongly non-uniform, disrupting the analogy with continuum Landau levels and destroying the fragile fractional quantum Hall states. This seems to also be the case with the nearly flat topological bands arising in twisted bilayer graphene: although the single particle band structure is flat, interactions combined with the non-trivial momentum-dependence of the quantum metric lead to self-consistent (Hartree-Fock) bands with strong dispersion, inhibiting the formation of fractional quantum Hall states. He also has some postdoc openings!