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!

Squeezed states, squashed states, spoofing, and more

Rationalizing systematic discrepancies between election outcomes and opinion polls

This work analyzes an exactly-solvable Ising model of the Bradley effect, which refers to discrepancies between election results and opinion polls resulting from poll respondents hiding their true preference. The Ising model takes the form of a bipartite network composed of a hidden layer (corresponding to voter intentions) and a visible layer (the voters' declared preferences).

Quadrature nonreciprocity: unidirectional bosonic transmission without breaking time-reversal symmetry

The authors propose and experimentally demonstrate quadrature non-reciprocity, referring to unidirectional transport of mode quadratures arising due to the interplay between linear coupling (beam splitter operations) and two-mode squeezing. This platform promises to be an interesting playground for non-Hermitian physics, with potential applications for multi-mode bosonic quantum networks. 

When you can't count, sample! Computable entropies beyond equilibrium from basin volumes

A very clear and beginner-friendly perspective on the difficulty of estimating volumes and densities in high-dimensional configuration spaces, and how the problem can be efficiently solved using importance sampling and replicas. Verification of quantum supremacy experiments is tricky for similar reasons - estimation of the probability density function of a random quantum state requires an exponential number of measurements.

Fundamental constraints on the observability of non-Hermitian effects in passive systems

There is still huge interest in non-Hermitian phenomena including non-Hermitian topological phases. Authors on this subject would be wise to understand important caveats regarding commonly-used models. For example, when considering a model including gain terms, some kind of nonlinear term such as gain saturation is required to avoid an unphysical blow-up of energy. Analysis of nonlinear systems is of course much more difficult, making it hard to obtain rigorous general results in this case. One alternative is to consider purely passive non-Hermitian systems formed via inhomogeneous losses, such that one does not need to worry about the stability of the system. Interestingly, this is not the whole story. This preprint shows that when inevitable material dispersion is included into passive non-Hermitian Hamiltonians (which is required for the model to satisfy the fundamental constraint of causality), "some of the most widely studied features [exceptional points, non-Hermitian skin effect, and symmetry-protected edge states] are effectively disguised in the density of states, in particular to the signatures of drastic mode nonorthogonality. These findings highlight the essential role of active elements in devices that aim to exploit these signatures."

Solving the sampling problem of the Sycamore quantum supremacy circuits 

This preprint from last year was just accepted in PRL. The authors demonstrate a method to classically spoof the results of the Google quantum supremacy experiments. "If our algorithm could be implemented with high efficiency on a modern supercomputer with ExaFLOPS performance, we estimate that ideally, the simulation would cost a few dozens of seconds, which is faster than Google's quantum hardware."

Classical models are a better explanation of the Jiuzhang Gaussian Boson Samplers than their targeted squeezed light models

Nicolas Quesada (formerly of Xanadu) and collaborators show that mixtures of coherent states termed squashed states are capable of spoofing higher order correlations measured in Gaussian BosonSampling experiments, one of the (multiple) tests used to establish a potential quantum advantage. However, the results of another test (Heavy Output Generation), could not be classically reproduced using the squashed state. "This work thus provides a new adversary that should be considered against future GBS experiments and, perhaps more importantly, further motivates the need to identify proper metrics and optimal classical adversaries for quantum advantage in the context of threshold GBS"

Quantum error correction in practice: it's really really hard

Suppressing quantum errors by scaling a surface code logical qubit

Today the Google AI team published a study demonstrating surface code quantum error correction using their superconducting quantum processor, advertised by an impressive-sounding summary on social media:

Fresh on the arxiv, Quantum AI demonstrates lower quantum error by scaling a surface code logical qubit from distance-3 (17 qubits) to distance-5 (49 qubits).

"These results mark the first experimental demonstration where quantum error correction begins to improve performance with increasing qubit number, illuminating the path to reaching the logical error rates required for computation."

In the paper, the "improved performance" is from a 3.0% logical error rate per correction cycle (distance-3 code) to 2.9% logical error per error correction cycle (distance-5), obtained after heroic efforts to improve the performance of their device (see Fig. 3c).

Specifically, setting the qubit and gate parameters (e.g. qubit frequencies and drive pulse parameters) for the physical qubits is an incredibly complicated optimization problem:

It is noisy, non-convex, and all parameters are explicitly or implicitly intertwined due to engineered interactions and/or crosstalk. Furthermore, since each parameter is constrained to ∼ 100 values by the control electronics, processor circuit, and gate parameters, the search-space is ∼ 10^552 . This space is intractable to search exhaustively and traditional global optimizers do not perform well on the objective. Therefore, we invented the Snake optimizer to address it.

The paper notes:

"Our experiment lies in a crossover regime where, due to finite-size effects, increasing system size initially suppresses the logical error rate before later increasing it."

 and

"Based on the error budget and simulations in Fig. 4, we estimate that component performance must improve by at least 20% to move below threshold, and significantly improve beyond that to achieve practical scaling."

Take-home message: Practical quantum error correction is still a long way off!

Pushing the limits of nonlinear optics

 Another entertaining and insightful perspective by Jacob Khurgin was uploaded to arXiv this week: Nonlinear optics: a look from the interaction time viewpoint and what it portends. It is similar in tone to his earlier article on high refractive index materials.

 This is real old-school physics - using simple intuitive models to understand fundamental limits to nonlinear optical response and "the universal principle of unavailability of free lunch."

On the one hand, the take-home message is somber: no huge magic enhancement of nonlinearity is possible due to fundamental physical constraints; hype regarding various wondrous materials does not stand up to scrutiny. On the other hand, finding new "boring" materials exhibiting modest enhancements to properties such as optical damage threshold or propagation loss is still a worthy goal as a means of improving the performance of existing nonlinear optical devices including light sources based on harmonic generation, optical frequency combs, and parametric amplifiers.

 

arXiv highlights

 A randomized benchmarking suite for mid-circuit measurements

Mid-circuit measurements of ancilla qubits form a key component of near-term quantum algorithms including NISQ-TDA, future quantum error correction techniques, and quantum algorithms for fault-tolerant quantum computers. This preprint from IBM presents techniques for quantifying the performance and error rates of mid-circuit measurements which are now supported by IBM quantum processors.

 

Laser-guided lightning

 

Focused high-intensity laser pulses can ionize air molecules, creating channels of air with higher electrical conductivity which can be used to guide and induce lightning strikes. Peaceful applications include protecting airports and rockets from lightning strikes. No doubt there are also military applications of this kind of research.

 

Large-Scale Simulation of Quantum Computational Chemistry on a New Sunway Supercomputer

 

Quantum chemistry calculations using classical supercomputers. Exponential memory scaling is avoided by using density matrix embedding theory to eliminate irrelevant degrees of freedom and matrix product states to efficiently capture quantum correlations. Apparently this approach can handle chemical systems with up to 100 atoms and it may also be useful for benchmarking variational quantum algorithms run on near-term quantum processors.

 

The Quantum Approximate Optimization Algorithm performance with low entanglement and high circuit depth

 

"Our simulation with the lowest bond dimension D = 2—for which the fidelity is close to zero—obtains a solution to the classical problem providing the depth of the circuit is high enough p ≈ 20, even with a sub-optimal choice of parameters and single deterministic sampling of bitstrings...In conclusion, we observe that entanglement plays a minor role in finding the solution to the classical problems studied here for large-depth QAOA." More evidence that your "quantum" optimization algorithm can be efficiently run on an ordinary classical computer.

Computing Electronic Correlation Energies using Linear Depth Quantum Circuits

 

Finally, I am advertising our own recent work on incorporating electronic correlation effects into shallow quantum circuits suitable for near-term noisy quantum processors. 

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.

PRA seeks a part-time remote Associate Editor

Since the start of the year I have been an Associate Editor at Physical Review A. So far it has been an interesting and enjoyable position, giving me exposure to topics I wouldn't normally read about as part of my own research.

They say that refereeing papers helps you to write better papers. The same is true for journal editorial work.

Even though there is less time for refereeing, editorial work also helps with reviewing papers, since you read many great (and some not-so-great) reports and can see what kinds of comments are useful and how others typically respond to critical comments.

PRA is now recruiting a part-time remote Associate Editor with expertise in quantum information and quantum foundations. The deadline to apply is July 9th, 2022.