GenQ Hackathon: Quantum for Finance

Last weekend I had the pleasure to attend the GenQ Hackathon: Quantum for Finance, joining as a mentor for the teams. Events such as this are important as a means of building familiarity with quantum processors amongst the participants from diverse backgrounds, from physics to finance majors and from high school students to veteran software engineers. Applications of quantum processors will not just need PhD-level quantum algorithm specialists, but also people with a broader range of skills able to make sense of where quantum algorithms may be practically useful.

The overall winning team had the, in my opinion, crucial insight that whatever fancy new solution you come up with, be it AI or quantum-designed, it had better be interpretable. Particularly in the high-stakes world of finance, someone will ultimately be responsible for decisions made based on the quantitative model. End-users won't trust a black box model. A model that spits out a single number - such as an F-score or correlation coefficient - will never be as trustworthy as a model that can clearly show all the relevant variables. Because of this, the team incorporated Mapper into their solution for detecting anomalies in the form of fraudulent credit card transactions.

One thing I was surprised by was how few of the teams took into account the clear advice given in the opening statement from Hongbin Liu (from Microsoft Quantum): In future practical use-cases of quantum processors, the cross-over point at which a quantum processor is expected to out-perform existing (very powerful) classical algorithms and high performance computers will involve days to weeks of wall-clock runtime. One on the judging criteria specifically focused on the scalability of the proposed solution. Despite this, in their final pitches many of the (unsuccessful) teams focused on quantum circuits limited to several qubits with second-scale run-times, claiming apparent speedups compared to selected classical benchmarks. However, such small-scale quantum circuits are trivially classically simulable.

I observed almost all the teams using ChatGPT or some other favourite large language model, both for background research on the chosen problem as well as rapid code generation. It was also striking to see how much easier it is now to write, compile, and execute quantum circuits on a cloud quantum processor by making use of quantum middleware providers, who now sell this as a convenient service. 

 

Cusp solitons mediated by a topological nonlinearity

Harvey just finished what should be the last paper of his PhD studies: Cusp solitons mediated by a topological nonlinearity

Harvey's PhD project studied the intersection between topological data analysis (TDA) techniques and nonlinear and many-body quantum dynamics. His first paper devised a TDA-based pipeline for detecting the emergence of quantum chaos in a periodically-driven nonlinear Kerr cavity. He followed this up with a demonstration of many-body quantum scar detection using topology-based dimensional reduction.

These works, while very nice, were ultimately using TDA to recover known physics. We really want to find examples where TDA can unveil new physics. This is a hard problem. Where to look? And what counts as "new"?

The easier solution for us was to insert TDA "by hand" into a nonlinear model, and see what came out of it.

For our testbed we took the nonlinear Schrodinger equation, frequently used to model nonlinear waves in various platforms. In the usual nonlinear Schrodinger equation, the conserved energy is the Hamiltonian,

$$ H = \int dx \left[ \frac{1}{2} |\partial_x \psi |^2 - \frac{g}{2} |\psi|^4 \right] $$

The second term, responsible for the nonlinear dynamics, can be interpreted as an intensity-dependent potential of depth $\frac{g}{2}|\psi|^2$. We looked at what would happen if we replaced this term with a quantity obtained using TDA. When dealing with one-dimensional functions, such as intensity profiles $|\psi(x)|^2$, TDA frequently uses sublevel set persistent homology, characterizing shape in terms of the persistence of local maxima and minima. We used the total persistence of these features as an energy penalty term, leading to

$$ H^{\prime} = \int dx \left[ \frac{1}{2} |\partial_x \psi|^2 - \alpha \mathrm{sgn}( \partial_x |\psi|^2 ) (\partial_x |\psi|^2) \right]  $$

Deriving the equations of motion, we found that this topological energy penalty gives rise to effective $\delta$ function potentials at the local maxima and minima of intensity, which act to enhance or suppress local maxima, depending on the sign of the nonlinear coefficient $\alpha$. We then studied the resulting nonlinear dynamics, including the focusing of Gaussian and flat-top beams.

The dynamics are very different from the regular nonlinear Schrodinger equation with focusing nonlinearity, where such a flat top beam would quickly break up into a collection of tightly-focused bright solitons. In this case, since the nonlinearity is proportional to the intensity gradient, its influence is mainly limited to the edges of the flat-top beam. 

We also uncovered some interesting connections to the physics of nonlocal nonlinear systems. Specifically, our "topological nonlinearity", when regularized, resembles a weakly nonlocal nonlinearity with a vanishing local part. Such nonlinearity leads to cusp solitons, as was previously studied in the context of plasma physics!

We hope to follow up this study with investigations of similar "topological" nonlinearities and potential experimental realizations. In the present work we speculated that similar nonlinearities may arise in the context of fluid-mediated nonlinearities and lattices undergoing Floquet modulation, but demonstrating such implementations explicitly remains an open problem for us.

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!

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!

Seeking quantum speedups using supersymmetric systems

There is a neat correspondence between the question of whether a simplicial complex has a k-dimensional hole and whether the ground state of a related supersymmetric (SUSY) quantum many-body Hamiltonian is at zero energy:

Complexity of Supersymmetric Systems and the Cohomology Problem

Clique Homology is QMA1-hard

A less technical presentation of the latter paper at QIP2023 and can be viewed here.

Both problems are QMA1-hard, meaning that the correctness of a trial solution can be efficiently checked by a quantum computer (but finding the correct solution remains hard even for the quantum computer). In contrast, recently-proposed quantum algorithms for TDA consider relaxations of the homology problem that can be solved efficiently using quantum algorithms, such as estimating the normalized number of k-cycles to some finite precision.

What other seemingly classical or purely mathematical problems can be naturally framed in the language of supersymmetric quantum mechanics? This promises to be fertile ground for exponential quantum speedups, and you don't need to be an expert in quantum algorithms to join the hunt!

Publish or perish

April was an unusually busy month for me for proof-checking, with five papers published:

Moiré Lattice in One-Dimensional Synthetic Frequency Dimension

This work led by collaborators at Shanghai Jiao Tong University analyzes frequency domain synthetic photonic lattices from a transfer matrix perspective, finding that the interplay between an incommensurate time modulation and off-resonant ring modes (not captured by the usual tight binding approximation) can be used to generate flat bands in a simple system of two coupled ring resonators.

Band relaxation triggered by modulational instability in topological photonic lattices

This was a long-delayed follow-up to our work on modulational instability in topological photonic lattices which we initiated during the start of the covid pandemic. Initially we had tried to understand the nonlinear wave dynamics in terms of an effective thermalization process, but it turned out that we could not observe any genuine thermalization within an experimentally-feasible time scale. This paper presents a detailed characterization of the long-lived pre-thermal state that is generated by the modulational instability. While our studies in this area are entirely theoretical / numerical, the dynamics of complex multimode nonlinear optical systems are now starting to be studied in a variety of experimental platforms, reviewed in Nature Physics last year.

Unravelling quantum chaos using persistent homology and Pseudospin-2 in photonic chiral borophene

I posted about these two papers when they were posted to arXiv late last year. The former made it into Physical Review E after a round of revisions. The latter was rejected by Nature Communications before being resubmitted to Photonics Research and accepted for publication after one round of revisions.

Topological data analysis and machine learning

This was a challenging review to prepare, given the need to concisely capture both the surprisingly-long history of applications of topological data analysis to physics (from the early 2000s) and a more recent wave of papers combining TDA with machine learning techniques. While it is far from perfect I hope it can still be a useful anchor for ongoing research in this area.

I'm hoping to have the next set of (now overdue) drafts finished and on arXiv sometime in June. Watch this space!

TDA Week 2023

TDA Week is a five-day conference on topics related to topological data analysis, held this year in person at Kyoto University from July 31 (Mon) to August 4 (Fri). It follows last year's conference, which was held online due to covid restrictions.

The abstract submission deadline for poster presentations is 14th April. Presenting authors may request partial support for travel expenses.

Snippets from the topological data analysis workshop

 I had the pleasure of visiting KIAS last week to attend their Workshop on Topological Data Analysis: Mathematics, Physics, and Beyond.

The programme featuring so many pure mathematics-focused talks was daunting at first, but ultimately I learnt a lot more than I would have by presenting the same work at a physics conference. This serves as a nice reminder: When we become experts at a highly specialised topic in our PhD studies (and beyond), it is easy to lose sight of the bigger picture. Changing fields or even attending a wide range of seminars outside our own expertise sparks new ideas.

Some useful tidbits from the talks:

• The Vietoris-Rips complex is not stable with respect to outliers. For example, adding a few points to a middle of a circular point cloud will completely change the form of the 1D persistence diagram (replacing the single high persistence cycle with low-persistence cycles). Stability theorems for persistence diagrams refer to small perturbations of a fixed set of point.
• Similar persistence diagrams do not imply similar data, in fact datasets with an arbitrarily large Hausdorff distance can have the same persistence diagrams.
• Mathematicians like TDA because it involves interesting problems with elegant solutions. But not all these elegant methods end up being useful in practice.
• The chemical and biological sciences benefit from having large datasets publicly available for benchmarking and standardised scoring of new machine learning / data analysis methods including TDA. This allows demonstrations of new heuristic methods to be convincing. 
• TDA can be used to estimate geometric features of data, including their (fractal) dimension, which is useful for understanding the performance of neural networks.
• The generators of 0-dimensional persistence diagrams give the minimal spanning tree for the data. This widely-used "folklore" was only rigorously proved in 2020!
  

Workshop on Topological Data Analysis: Mathematics, Physics and beyond

Next month I'll be speaking at a workshop on topological data analysis (TDA) organized by the Korean Institute for Advanced Study, to be held on February 8-10 in Seoul. I'm quite excited because this will be my first chance to attend an in-person meeting dedicated to this topic! From the workshop website: 

"This workshop aims to share our knowledge about topological data analysis from the viewpoint of mathematics and physics. We are trying to make this event in-person with a relaxed schedule, so that we can discuss each other more freely. We hope this event help us widen our perspectives on mathematical and physical backgrounds about data analysis."

In other TDA news, there is an article on TDA published in the January issue of Physics Today which gives an overview of applications to condensed matter and soft matter physics using the "shape" of Jigglypuff as a pedagogical example!

arXiv backlog

I've been too busy finishing papers to carefully read the arXiv postings that looked interesting enough to download. Here is what's caught my attention:

• Textbook myths about early atomic models. The plum pudding model is fake news!
• Topological packing statistics distinguish living and non-living matter. This work develops a method to distinguish different types of point clouds using their distributions of local structural features. Seems like a promising new alternative to persistent homology.
• Strong intensity noise condensation using nonlinear dispersive loss in semiconductor lasers. A follow-up to the group's Fock state laser paper, which seems to be still under review.
• Optical isolation by temporal modulation: size, frequency, and power constraints. The third in a series of perspective-style anti-hype articles by Jacob Khurgin (previous ones on nonlinear optics and high refractive index materials), this one targeting the booming field of temporal metamaterials. Take a look at the entertaining introduction!
• A (simple) classical algorithm for estimating Betti numbers. An efficient path integral Monte Carlo algorithm constrains the region where quantum algorithms for Betti number estimation might provide a quantum advantage.
• Matters Arising: Time-reversal-based quantum metrology with
  many-body entangled states. Is entanglement-enhanced metrology a sham?
  

Two preprints

I haven't had much time for posting recently, since I've been rushing to finish several projects before the end of the year. We have two papers out on arXiv this week, with a few more hopefully ready soon!

Unravelling quantum chaos using persistent homology

We considered the application of (quantum) chaos detection techniques to a simple system, a driven-damped Kerr nonlinear oscillator. Tuning the driving frequency in this system can induce transitions between chaotic and regular dynamics, with classical chaos emerging in the limit of large amplitude coherent states. This provides a nice setting for looking at how persistent homology-based methods for detecting classical chaos can be translated to quantum dynamics. For this purpose, we treat the quantum oscillator as an open quantum system subject to random quantum jumps (photons leaking from the cavity), described by a stochastic Schrodinger equation. Despite the higher complexity of the quantum system (in terms of a larger phase space), we can still distinguish regimes of regular and chaotic dynamics by considering the topology of a time-delay embedding of the detected photon counts!

Pseudospin-2 in photonic chiral borophene

One chapter of my PhD thesis covered wave propagation at conical interactions. At the time, we were most interested in intersections with pseudospin 1/2 (corresponding to Dirac cones in systems such as graphene), and pseudospin 1 (occurring in the Lieb lattice, a topic which I spent some time studying). While I was writing up the thesis, I found the analysis of both kinds of systems could be connected nicely by generalizing the description to arbitrary pseudospin s. We included this in a review article, but didn't give much thought as to how one might go about realizing intersections with higher values of s, assuming they would be unstable and hard to make in practice.

It turns out, higher pseudospin conical intersections can be symmetry-protected (similar to the case of the Lieb lattice), and can they emerge in lattices that don't look too crazy, can be realized using optical waveguide arrays, and may even exist as stable two-dimensional electronic materials!

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.

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.

The 2nd POSTECH MINDS Workshop on Topological Data Analysis and Machine Learning

Resuming (hopefully) semi-regular posting after a few weeks finishing revisions to a few manuscripts:

POSTECH in Korea is hosting another workshop on the intersection between topological data analysis (TDA) and machine learning at the end of September [Sep. 26 (Monday) ~ Sep. 29 (Thursday)]. From the conference website:

This workshop will bring together researchers and students working on TDA and machine learning and provide an opportunity where they present their recent research and share ideas. Further, this workshop will also provide tutorial sessions that will introduce various TDA computational tools and provide practical hands-on tutorials. This is a sequel to the workshop of the same name held in 2021 - ILJU POSTECH MINDS Workshop on Topological Data Analysis & Machine Learning, 2021.

I attended (virtually) last year's workshop and found it quite interesting. As a newcomer to the field it gave a good picture of some of the cutting-edge questions being pursued in TDA. There is no registration fee, but registration is required for access to the workshop live stream.

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!

Various items

Two jailed for conspiring with NUS lab executive to cheat more than S$350,000. I've heard from experimental colleagues that equipment purchasing system at NUS is very slow and inefficient. Now I understand!

Our short review on physics applications of topological data analysis is now out at arXiv:2206.15075. I hope it provides a good overview of the recent literature on this subject. I certainly learned a lot writing it!

Another probably controversial preprint was posted a few weeks ago: Observation of strong backscattering in valley-Hall topological interface modes. From the abstract: "We find no improvement in the propagation losses relative to topologically trivial waveguide modes with the same group index, even for state-of-the-art silicon photonics...our work raises fundamental questions about the existence of topological protection against real-world disorder in time-reversal-symmetric photonics." This is a must-read for anyone working on topological photonic crystals.

 

At CQT we will have our first in-person colloquium in more than two years (!) on 14th July, given by Prof. Michael Tobar: Precision Metrology with Photons, Phonons and Spins: Answering Major Unsolved Problems in Physics and Advancing Translational Science.

ICOAM 2022 - live stream

The 6th International Conference on Optical Angular Momentum is running this week, featuring an impressive lineup of invited speakers including Sir Michael Berry (of geometric/Berry phase fame), who will be giving a public lecture on Friday.

The organisers have kindly provided a zoom livestream of the sessions so those who unable to attend in person can still watch the talks.

I will be giving my talk remotely on Wednesday morning. Here are my slides. My aim is to provide an accessible introduction to topological data analysis and offer some potentially-interesting directions for future research.

Unfortunately the review article we've been working on is not yet finished - I was hoping to have an arXiv link ready in time for my talk.

ArXiv catchup

 Deadlines abound so I haven't been following arXiv postings that closely. Some papers of note from the last few weeks:

Dielectric Mie Voids: Confining Light in Air. The authors demonstrate a metasurface analogue of photonic crystal fibers. A neat idea that could enable ultra-low loss flat optics.

Beyond Barren Plateaus: Quantum Variational Algorithms Are Swamped With Traps. "We prove that a wide class of variational quantum models -- which are shallow, and exhibit no barren plateus -- have only a superpolynomially small fraction of local minima within any constant energy from the global minimum, rendering these models untrainable if no good initial guess of the optimal parameters is known." End-users beware: this work adds to evidence that variational quantum algorithms may not be scalable up to useful problem sizes.

Persistent homology analysis of a generalized Aubry-André-Harper model. Our own recent work on applying topological data analysis to study localization transitions in photonic lattices. What we found particularly exciting is that this is our first example of TDA discovering an unanticipated effect - the emergence of disorder-free eigenstates for certain model parameters.

Experimentally realized in situ backpropagation for deep learning in nanophotonic neural networks. Spoiler: the nonlinear activation functions are implemented digitally. Incorporating useful nonlinear optical response into integrated photonic neural networks while outperforming conventional electronic circuits is a big challenge. One promising potential solution is to employ measurement+based nonlinearities + feedforward.

Fabrication-Robust Silicon Photonic Devices in Standard Sub-Micron Silicon-on-Insulator Processes. With the continuing interest (and hype) in topological photonics it's important to keep in mind conventional non-topological approaches for designing photonic devices. For example, wider waveguides are more robust to fabrication imperfections, at the expense of being multimode. This is a problem, because waveguide bends will then induce coupling between the different guided modes, corrupting signals. Here the authors demonstrate how a clever choice of bending profile can suppress unwanted inter-modal coupling while not increasing the device footprint.

Breakdown of quantization in nonlinear Thouless pumping. Quantized adiabatic pumping of solitons attracted a lot of interest last year. This theoretical analysis shows how quantization can break down for moderate nonlinearity strengths due to the emergence of loops in the adiabatic energy spectrum, leading to dead-ends in the adiabatic path resulting in sudden non-adiabatic transitions of the soliton.

Topological data analysis using noisy intermediate-scale quantum processors

Topological data analysis (TDA) is an interesting potential application of future quantum computers. One step of the topological data analysis pipeline is to find the null space of the combinatorial Laplacian of a simplicial complex, a problem whose complexity grows exponential in the simplex dimension k. It is remarkable that the combinatorial Laplacian has a certain structure that makes it efficient to implement using quantum circuits, which enabled Lloyd and collaborators to propose a quantum algorithm for topological data analysis back in 2016: Quantum algorithms for topological and geometric analysis of data. However, being based on quantum phase estimation, this algorithm is not suitable for the noisy intermediate-scale quantum (NISQ) processors current available, apart from proof-of-concept experiments.

Last year Ubaru and collaborators proposed a NISQ-friendly TDA algorithm. What is very nice about this algorithm is that it has depth and qubit requirements linear in the number of input data points n, it potentially offers an exponential speed-up compared to the best classical algorithm, and it is not variational. In my opinion, the variational quantum algorithms for NISQ will have serious issues with scaling up to useful (i.e. classically-intractable) system sizes. Therefore I find this NISQ-QTDA algorithm quite exciting.

The NISQ-TDA algorithm uses a few neat tricks: the quantum phase estimation algorithm (not suitable for NISQ devices) is replaced with random sampling of the moments of the graph Laplacian to provide an estimate of the dimension of its null space, giving a circuit depth linear in the number of input data points n. Additionally, intermediate measurements and reset of ancilla qubits reduce the number of ancillas from O(n^2) to O(n). In a subsequent work the group has shown that the boundary operator used to construct the graph Laplacian can be implemented exactly using 2(n-1) two-qubit rotations plus a single qubit rotation. 

QTDA is one of the few quantum machine learning algorithms that offers an exponential speedup without requiring QRAM tricks, which suggests its speedup will be robust to dequantization approaches (i.e. analysis that takes the data-encoding bottleneck into account).

Still, there are a few limitations. The original algorithm by Lloyd and collaborators only computes the Betti number of a single simplicial complex. On the other hand, TDA generally requires computation of the persistent Betti numbers, using a range of scales to obtain a family of simplicial complices. Recent studies [arXiv:2111.00433, arXiv:2202.12965] have proposed quantum algorithms for computing persistent Betti numbers, but only suitable for fault-tolerant quantum computers. It will be interesting to see whether these approaches can be generalized into NISQ-friendly algorithms. This is definitely a subject to keep an eye on.

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.