Quantum Computing News and Views

In the past month there have been several interesting developments related to quantum computing:

Spoofing random circuit sampling

Claims of quantum supremacy via random circuit sampling are troublesome because it is so difficult to verify that the quantum processor is working correctly. The Google team used cross entropy benchmarking to verify their original experimental demonstration. The cross entropy benchmarking fidelity is basically a measure of the probability of observing a sequence of bitstrings based on the simulated output probabilities of a circuit. One criticism of this approach is that this fidelity cannot be computed for circuits operating in the classically-intractable quantum supremacy regime. The authors were limited to computing the fidelity for smaller, classically-tractable circuits and comparing its scaling to the expected gate error rates. This approach has several issues explained clearly in a blog post by Gil Kalai discussing a preprint from last year, Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage. 

New attacks of the cross entropy benchmarking fidelity have now appeared as arXiv preprints:

Changhun Oh and collaborators have come up with a method for spoofing the cross entropy benchmarking fidelity in recent Gaussian BosonSampling experiments.

Dorit Aharonov and collaborators show that samples from noisy quantum circuits can be computed classically to a good approximation in polynomial time.

Classical shadows and bosonic modes

Classical shadows continue to be a highly fruitful avenue for a potential near-term quantum advantage. Hsin-Yuan Huang and collaborators have now shown how classical shadows can be used to predict arbitrary quantum processes. To be precise, they give a procedure for estimating observables of a quantum state $\rho$ following application of a completely positive trace-preserving map (describing e.g. evolution of a quantum state in the presence of environmental noise).

When we first become interested in classical shadows almost a year ago a natural question that arose was whether the qubit-based formalism could be translated to bosonic systems. This turns out to be a hard problem because the proof of optimality of shadow methods rests on properties of finite-dimensional vector spaces which do not easily translate to the infinite-dimensional continuous variable quantum systems, discussed in The Curious Nonexistence of Gaussian 2-Designs. 

A team at NIST/University of Maryland now appears to have solved this problem. First, they show that the non-convergent integrals arising in the continouous variable case can be avoided by considering "rigged t-designs" obtained by expanding the Hilbert space to include non-normalizable states. Experimentally-meaningful predictions using this approach can be obtained by regularizing the designs to have a finite maximum or average energy. In a second study the team recasts existing bosonic mode tomography approaches to the classical shadow language to obtain bounds for estimating unknown bosonic states. In practice, however, homodyne tomography performs significantly better than the bounds obtained using classical shadows. These works open up further studies and applications of shadow-based methods to bosonic systems.

Edit: Another paper on continuous variable shadows appeared today: arXiv:2211.07578

IBM's Osprey 433-qubit quantum processor

Last week IBM made several announcements as part of their annual quantum summit, including their new 433-qubit Osprey device. Olivier Ezratty posted a great hype-free analysis of IBM's marketing announcements. In short, large two-qubit gate errors make such large qubit counts useless at this stage, but the advances in integration of the classical control electronics are an important step forward. IBM is still in the lead with the development of superconducting quantum processors. It is also nice to see that they are working towards integrating error mitigation techniques into their software. At present cloud quantum computing providers release devices with atrocious error rates (coughRigetticough), which requires users to spend significant time and money implementing error mitigation techniques in the hope extracting something useful out of their devices.

Bad news for NISQ?

Sitan Chen and collaborators analyze the capabilities of NISQ devices using tools from complexity theory, obtaining a complexity class lying between classical computation and noiseless quantum computation. Their model rules out quantum speedups for certain algorithms including Grover search that are run on near-term noisy quantum devices.

Variational quantum chemistry requires gate-error probabilities below the fault tolerance threshold. The authors compare different variational quantum eigensolvers. Gate errors severely limit the accuracy of energy estimates, making minimizing circuit depths of prime importance. Thus, hardware-efficient ansatzes are preferred over deeper physically-inspired variational circuits. Regardless, supremely low error rates seem to be needed to reach chemical accuracy.

Exponentially tighter bounds on limitations of quantum error mitigation. Quoting from the abstract, "a noisy device must be sampled exponentially many times to estimate expectation values." At first glance, this is good news for cloud quantum processor providers - simply by making your qubits noisier, you can increase your revenue exponentially! However, "there are classical algorithms that exhibit the same scaling in complexity," so classical cloud computing providers will give you much much much better value for money. "If error mitigation is used, ultimately this can only lead to an exponential time quantum algorithm with a better exponent, putting up a strong obstruction to the hope for exponential quantum speedups in this setting."

Towards fault tolerant quantum computing

Daniel Gottesman has a relatively accessible survey on quantum error correcting codes. I was surprised to see that the problem of quantum error correction has not been reduced to an engineering challenge of building bigger devices with the required fidelities; work on understanding the properties and developing better error correction methods more robust against different error types is still an active area of research.

Quantum error correcting codes typically assume that errors are uncorrelated in time and space. In the presence of correlated errors at best you require a lower error rate for quantum error correction to work, and at worst the accumulation of uncorrectable errors will make the result of the computation useless. The Google team have put out a preprint aimed at reducing correlated errors arising from the excitation of higher-order states in their superconducting qubits.

Steps towards a quantum advantage

Xanadu's latest results on Gaussian BosonSampling attracted quite a bit of media attention. Their essential breakthrough is to combine time multiplexing with number-resolved photon detectors to massively increase the number of modes and photon counts, pushing their device into a regime that seems to be intractable using classical computers. 

It is reassuring that one of the reviewers of the Nature paper was Sergio Boixo, who has also authored work on developing more efficient classical algorithms for spoofing Gaussian BosonSampling. Other advanced classical algorithms can spoof shallow circuits and measurements with too many photons per mode.

The Gaussian BosonSampling device is now accessible on AWS. The price per shot is (\$0.00020) is slightly more than half of that of the superconducting processors (\$0.00035). Note this is not a general-purpose system, which remains challenging to implement, as noted by the Xanadu team in their paper:

If one were to target a universal and programmable interferometer, with depth equal to the number of modes, that covers densely the set of unitary matrices, the exponential accumulation of loss would prohibit showing a quantum advantage. There are then two ways around this no-go result: one can either give up programmability and build an ultralow loss fixed static interferometer, ...., or give up universality while maintaining a high degree of multimode entanglement using long-ranged gates.

Despite the lack of universality, this does seem to be the first classically-intractable programmable quantum processor available for general use via the cloud!

 On a related note, last week Nature published a paper demonstrating repeated error correction, using 17 superconducting qubits to create a single logical qubit. Each error correction cycle took 1.1 us and succeeding with 97% probability (95% without post-selection). Quantum error correction experiments are still at a very early stage; this experiment (and most others) have not yet reached the "break-even" point where the logical qubit lifetime exceeds the lifetime of a single physical qubit.

Mapping optimization problems onto boson sampling circuits

Certain properties and applications of shallow bosonic circuits

This arXiv preprint comes from ORCA Computing, an Oxford University spin-off company pursuing fibre optic-based quantum computing. In brief, the fibre optic platform uses trains of time-delayed single photon pulses and number-resolved photon detection.

The authors consider how variational quantum eigensolvers, an immensely popular class of algorithms for near-term qubit-based systems such as superconducting quantum processors, may be mapped to shallow linear interferometers employed for boson sampling experiments. Their idea is:

1. Boson sampling circuits sample from a distribution integer strings (n1,n2,...nM), where ni corresponds to n photons detected in mode i.

2. Taking the parity of the output maps this to a distribution of bitstrings (b1,...,bM), which can be interpreted as a measurement of a qubit-based system in the computational basis.

3. Under certain constraints this parity mapping allows one to sample from a complete basis of the qubit Hilbert space and thereby measure cost functions of binary optimization problems such as QUBO.

4. Output observables obey the parameter shift rule, making gradient-based minimization of the cost function to solve the optimization problem practical.

I think studies such as this on mappings between qubit-based and bosonic NISQ devices are important. While a few general-purpose optimization algorithms for qubit systems have been developed, proposed applications of NISQ bosonic circuits remain largely limited to "hardware native" schemes, i.e. simulation of properties of bosonic Hamiltonians such as molecular vibration spectra. This work provides a general scheme by which one might solve more general optimization problems using boson sampling devices, making them much more valuable for end-users.

However, two caveats I can see:

1. The QAOA algorithm is perhaps the most promising variational quantum algorithm, because it is a structured (problem-inspired) circuit with relatively few free parameters that need to be optimized, with some rigorous performance guarantees. While linear interferometers are described by a manageable number of free parameters, there is no guarantee that this kind of hardware-efficient circuit can always express the optimal solution to the optimization problem at hand.

2. The elephant in the room: Are the proposed circuits hard to simulate on a classical computer? While exact boson sampling is provably hard, hardness of the approximate sampling problem rests on the number of optical modes M being much larger than N^2, where N is the total number of input photons. In this limit there is a very low probability of detecting more than one photon in any output mode and the number resolved detection and parity map are not required. In their proof of concept simulations, however, the authors consider only the case M ~ N...