Quantum-inspired classical algorithm for molecular vibronic spectra

Abstract

We have recently seen the first plausible claims for quantum advantage using sampling problems such as random circuit sampling and Gaussian boson sampling. The obvious next step is to channel the potential quantum advantage to solving practical applications rather than proof-of-principle experiments. Recently, a quantum simulator, specifically a Gaussian boson sampler, has been proposed to generate molecular vibronic spectra efficiently, which is an essential property of molecules and an important tool for analyzing chemical components and studying molecular structures. Computing molecular vibronic spectra has been a challenging task, and its best-known classical algorithm scales combinatorially in the system size. Thus, it is a candidate of tasks for which quantum devices provide computational advantages. In this work, we propose a quantum-inspired classical algorithm for molecular vibronic spectra for harmonic potential. We first show that the molecular vibronic spectra problem corresponding to Fock-state boson sampling can be efficiently solved using a classical algorithm as accurately as running a boson sampler. In particular, we generalize Gurvits's algorithm to approximate Fourier components of the spectra of Fock-state boson sampling and prove using Parseval's relation that the error of the spectra can be suppressed as long as that of the Fourier components are small. We also show that the molecular vibronic spectra problems of Gaussian boson sampling, which corresponds to the actual molecular vibronic spectra problem in chemistry, can be exactly solved even without Gurvits-type algorithms. Consequently, we demonstrate that those problems are not candidates of quantum advantage. We then provide a more general molecular vibronic spectra problem, which is also chemically well-motivated, for which we might be able to take advantage of a boson sampler.

11+16 pages, 2+1 figures, 1 table

References in corpus (8)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum computational advantage using photons
• Strong quantum computational advantage using a superconducting quantum processor
• Quantum circuits with many photons on a programmable nanophotonic chip
• Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
• The Boundary for Quantum Advantage in Gaussian Boson Sampling
• Franck-Condon factors by counting perfect matchings of graphs with loops
• Classical simulation of boson sampling based on graph structure

Cited by in corpus (9)

• Classical algorithm for simulating experimental Gaussian boson sampling
• Quantum-inspired classical algorithm for graph problems by Gaussian boson sampling
• Efficient validation of Boson Sampling from binned photon-number distributions
• Approximating outcome probabilities of linear optical circuits
• Compressed sensing enhanced by quantum approximate optimization algorithm
• Hidden $sl(2)-$Symmetry of the Generalized Landau-Zener Vibronic Model
• Configurable photonic simulator for quantum field dynamics
• Complexity of Gaussian quantum optics with a limited number of non-linearities
• Classical algorithms for measurement-adaptive Gaussian circuits