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!

More on quantum topological data analysis

 Two preprints on quantum topological data analysis (TDA) were posted to arXiv last week.

From the IBM team, Exponential advantage on noisy quantum computers. This is a follow-up to their proposal from last year, arXiv:2108.02811, implementing their linear depth NISQ-TDA algorithm (my earlier synopsis) using a trapped ion quantum processor. 

The introduction nicely frames the key ingredients required for demonstrating an end-to-end quantum advantage using near-term device, and then explains how NISQ-TDA meets all of the requirements, for example by having small input and output data sizes. Another advantage of NISQ-TDA is that the output observables, the Betti numbers, are known to be quantized topological invariants, leading to a robustness to shot noise and reducing the number of measurements required to obtain an accurate result. 

The article ends with the optimistic outlook that "a 96-qubit quantum computer with a two-qubit gate and measurement fidelity of ∼ 99.99% suffices to to achieve quantum advantage on the Betti number estimation problem." This really seems to me the strongest candidate for demonstrating a quantum advantage. Anyone interested in near-term quantum algorithms for machine learning applications should read this paper!

------

A second preprint was posted by researchers from Deloitte, Understanding the Mapping of Encode Data Through An Implementation of Quantum Topological Analysis. This work offers a more pessimistic viewpoint, stating that "the empirical results show the noise within the data is intensified with each encoding method as there is a clear change in the geometric structure of the original data, exhibiting information loss." However, their approach seems to be based on the original quantum TDA algorithm, based on Grover search and quantum phase estimation, which is not suited for near-term devices.

Fusion-based quantum computation

A brief summary of the great talks by Mercedes Gimeno-Segovia and Terry Rudolph at the 6th Quantum Africa Conference on PsiQ's approach for building a large scale photonic fault-tolerant quantum computer using entangling measurements: fusion-based quantum computation. See also an earlier perspective by Rudolph published in APL Photonics.

Fusion-based quantum computation can be seen as a middle ground between the gate model (employed in most other platforms for quantum computing) and measurement-based quantum computation, which replaced nonlinear operations (hard to do using quantum states of light) with a suitable sequence of single qubit measurements.

The first step in measurement-based quantum computation is to prepare a large scale entangled resource state that is big enough to perform the desired computation. This is hard.

Fusion-based on the other hand employs two-qubit (entangling) measurements as its basic building block. This allows the calculation to be performed using a steady stream of constant-size resource states. These resource states also require multiple photons to be entangled, which is hard, but at least their size is bounded. Creating constant size resource states with sufficient fidelity and speed is the challenge which PsiQ believes they can solve.

What distinguishes PsiQ from their competitors is that their platform is easily scalable to billions of logical qubits and gates using commercial silicon lithography employed to make all our conventional electronic computers. I think the only other platform which can make such a claim are the silicon qubits being pursued by a few groups, including the UNSW spin-off Silicon Quantum Computing. By contrast, the quantum processors currently available on the cloud (superconducting circuits and ions trap) are (relatively) large and clunky devices requiring painstaking optimisation and babysitting but nevertheless might only support a few logical qubits if quantum error correction can be implemented.

An interesting point raised in the talks was that error-corrected devices will be very different from any of the currently-available quantum processors; once you have working error correction many of the details of the physical qubits become unimportant. Thus, PsiQ's approach is to create billions of "good-enough" physical qubits rather than a lower number of perfect qubits.

Quantum Africa Conference (QA6)

Quantum Africa is a conference covering quantum information and quantum computing running next week (Monday 12th to Friday 16th of September 2022).

It will be held in hybrid mode with a mix of in-person and online talks.

The talks should be quite pedagogical and will be given by outstanding researchers from academia and industry, including Steve Girvin (Yale, USA), Francesco Petruccione (UKZN, South Africa), Pedram Roushan (Google Quantum), and Terry Rudolph (PsiQuantum).

Talks will be recorded for later on-demand viewing for registered participants. Registration is free for online attendance!

Quantum computing debated in The Financial Times

Criticism of quantum computing hype and a rebuttal recently appeared in The Financial Times. The first article argues that even "well-established" applications of future quantum computers - breaking encryption and efficient quantum chemistry calculations - may not be useful in practice. The second article notes that even though there is tremendous hype, there is also slow but steady progress in scaling up quantum processors and understanding which quantum algorithms might provide value and which will not.

It is worth emphasizing that quantum technologies are much broader than quantum computing. For example, quantum research in Singapore are also encompasses quantum communications and quantum sensing. While these areas a seen as being closer to useful commercial applications, there are still some important caveats:

Quantum communication technologies are often marketed as the solution to the problem of future quantum computers being able to break widely-used public key cryptography schemes, with quantum key distribution providing unbreakable encryption protected by the laws of physics. The reality is that sharing of encryption keys is just one part of a secure communications network; a far bigger problem is authentication - how can you prove the other party is who they claim to be? Indeed, the vast majority of data breaches or online scams are not due to encryption protocols being broken or passwords being hacked, but rather are a result of phishing attacks where the victim is tricked into believing the attacker is someone else. The UK's National Cyber Security Centre's position on quantum communication technologies is:

"Given the specialised hardware requirements of QKD over classical cryptographic key agreement mechanisms and the requirement for authentication in all use cases, the NCSC does not endorse the use of QKD for any government or military applications, and cautions against sole reliance on QKD for business-critical networks, especially in Critical National Infrastructure sectors.

In addition, we advise that any other organisations considering the use of QKD as a key agreement mechanism ensure that robust quantum-safe cryptographic mechanisms for authentication are implemented alongside them."

Quantum sensing promises the ability to perform measurements with precision unattainable using classical devices. This encompasses many well-established approaches based on quantum coherence, including SQUIDs, atomic clocks, atomic gravimeters, and squeezed light interferometers, and more speculative ideas based on large-scale quantum entanglement. The latter entanglement-based approaches have however attracted criticism (see for example this preprint).

In all these examples - quantum computing, quantum communications, and quantum sensing - useful technologies will not emerge from quantum researchers working in isolation. Collaboration with researchers working in other disciplines and industry is essential to keep quantum "solutions" honest and ensure that we are solving problems that need to be solved, and to establish that quantum techniques provide a better solution than well-established classical methods.