Hierarchy in Sampling Gaussian-correlated Bosons

Joonsuk Huh, Man‐Hong Yung

Published Aug 12, 2016• 2 citations

Abstract

Boson Sampling represents a class of physical processes potentially intractable for classical devices to simulate. The Gaussian extension of Boson Sampling remains a computationally hard problem, where the input state is a product of uncorrelated Gaussian modes. Besides, motivated by molecular spectroscopy, Vibronic Boson Sampling involves operations that can generate Gaussian correlation among different Boson modes. Therefore, Gaussian Boson Sampling is a special case of Vibronic Boson Sampling. However, this does not necessarily mean that Vibronic Boson Sampling is more complex than Gaussian Boson Sampling. Here we develop a hierarchical structure to show how the initial correlation in Vibronic Boson Sampling can be absorbed in Gaussian Boson Sampling with ancillary modes and in a scattershot fashion. Since every Gaussian state is associated with a thermal state, our result implies that every sampling problem in molecular vibronic transitions, at any temperature, can be simulated by Gaussian Boson Sampling associated with a product of vacuum modes.

Related papers

Vibronic Boson Sampling: Generalized Gaussian Boson Sampling for Molecular Vibronic Spectra at Finite Temperature

Joonsuk Huh, Man‐Hong Yung

Molecular vibroic spectroscopy, where the transitions involve non-trivial Bosonic correlation due to the Duschinsky Rotation, is strongly believed to be in a similar complexity class as Boson Sampling. At finite temperature, the problem is represented as a Boson Sampling experiment with correlated Gaussian input states. This molecular problem with temperature effect is intimately related to the various versions of Boson Sampling sharing the similar computational complexity. Here we provide a full description to this relation in the context of Gaussian Boson Sampling. We find a hierarchical structure, which illustrates the relationship among various Boson Sampling schemes. Specifically, we show that every instance of Gaussian Boson Sampling with an initial correlation can be simulated by an instance of Gaussian Boson Sampling without initial correlation, with only a polynomial overhead. Since every Gaussian state is associated with a thermal state, our result implies that every sampling problem in molecular vibronic transitions, at any temperature, can be simulated by Gaussian Boson Sampling associated with a product of vacuum modes. We refer such a generalized Gaussian Boson Sampling motivated by the molecular sampling problem as Vibronic Boson Sampling.

arXiv:1608.03731Scientific ReportsAug 1, 201762 citations

Quantum Computing for Molecular Vibronic Spectra and Gaussian Boson Sampling

Seungbeom Chin, Joonsuk Huh

Boson sampling (BS) is a multimode linear optical problem that is expected to be intractable on classical computers. It was recently suggested that molecular vibronic spectroscopy (MVS) is computationally as complex as BS. In this review, we discuss the correspondence relation between BS and MVS and briefly introduce the experimental demonstrations of the molecular spectroscopic process using quantum devices. The similarity of the two theories results in another BS setup, which is called "vibronic BS". The hierarchical structure of vibronic BS, which includes the original BS and other Gaussian BS, is also explained.

arXiv:1803.10002Journal of Physics Conference SeriesAug 1, 20183 citations

Bridging chemistry and Gaussian boson sampling: a photonic hierarchy of approximations for molecular vibronic spectra

Jan-Lucas Eickmann, Kai-Hong Luo, Mikhail Roiz +10 more

Abstract Simulating vibronic spectra is a central task in physical chemistry, offering insight into important properties of molecules. Recently, it has been experimentally demonstrated that photonic platforms based on Gaussian boson sampling (GBS) are capable of performing these simulations. However, whether an actual GBS approach is required depends on the molecule under investigation. To develop a better understanding on the requirements for simulating vibronic spectra, we explore connections between theoretical approximations in physical chemistry and their photonic counterparts. Mapping these approximations into photonics, we show that for certain molecules the GBS approach is unnecessary. We place special emphasis on the linear coupling approximation, which in photonics corresponds to sampling from multiple coherent states. By implementing this approach in experiments, we demonstrate improved similarities over previously reported GBS results for formic acid and identify the particular attributes that a molecule must exhibit for this, and other approximations, to be valid. These results highlight the importance in forming deeper connections between traditional methods and photonic approaches.

arXiv:2507.19442npj Quantum InformationMay 6, 20260 citations

The Complexity of Bipartite Gaussian Boson Sampling

Daniel Grier, Daniel J. Brod, Juan Miguel Arrazola +2 more

Gaussian boson sampling is a model of photonic quantum computing that has attracted attention as a platform for building quantum devices capable of performing tasks that are out of reach for classical devices. There is therefore significant interest, from the perspective of computational complexity theory, in solidifying the mathematical foundation for the hardness of simulating these devices. We show that, under the standard Anti-Concentration and Permanent-of-Gaussians conjectures, there is no efficient classical algorithm to sample from ideal Gaussian boson sampling distributions (even approximately) unless the polynomial hierarchy collapses. The hardness proof holds in the regime where the number of modes scales quadratically with the number of photons, a setting in which hardness was widely believed to hold but that nevertheless had no definitive proof. Crucial to the proof is a new method for programming a Gaussian boson sampling device so that the output probabilities are proportional to the permanents of submatrices of an arbitrary matrix. This technique is a generalization of Scattershot BosonSampling that we call BipartiteGBS. We also make progress towards the goal of proving hardness in the regime where there are fewer than quadratically more modes than photons (i.e., the high-collision regime) by showing that the ability to approximate permanents of matrices with repeated rows/columns confers the ability to approximate permanents of matrices with no repetitions. The reduction suffices to prove that GBS is hard in the constant-collision regime.

arXiv:2110.06964QuantumNov 28, 202241 citations

Vibronic spectra of molecules – an experiment with a quantum computer simulator

András Németh, Tamás Kozsik, Zoltán Zimborás

In addition to the exciting fundamental questions of quantum computing and implementation possibilities of quantum computers, it is important to look for application areas of quantum computing, to point out practical cases which justify the need for this technology. Besides the wellknown qubit-based quantum computers, there are also devices based on other foundations that can surpass the capabilities of classical computers. Among these, devices operating on the basis of boson sampling have a naturally occurring application: the approximate calculation of the vibrational spectrum of molecules. Two separate research groups, Huh et al. [14] and Wang et al. [22] created quantum simulators based on boson sampling, which were successfully used to calculate the transition probabilities between specific states of small molecules. Following the methodology found in these two articles, this paper presents how the calculations of transition probabilities can be performed on a classical computer using a quantum computer simulator which is based on Gaussian boson sampling.

Az Eszterházy Károly Tanárképző Főiskola tudományos közleményei. Tanulmányok a matematikai tudományok köréből/Az Eszterházy Károly Főiskola tudományos közleményei. Tanulmányok a matematikai tudományok köréből/Annales mathematicae et informaticaeJan 1, 20231 citation

Gaussian boson sampling: Benchmarking quantum advantage

Ned Goodman, Alexander S. Dellios, Margaret D. Reid +1 more

Quantum computers solve intractable problems which classically require an exponentially long time to compute. With the development of large-scale experiments that claim quantum advantage, a vital issue has now emerged. What are the errors, and how do they affect the complexity of the problem solved? Large-scale Gaussian boson sampling (GBS) experiments give an example in which random numbers are generated. Despite classical hardness, these have computable benchmarks for checking data validity. While there are other quantum computing architectures, Gaussian boson sampling is uniquely testable at all scales. Several large, pioneering quantum computing (QC) experiments have been carried out to investigate quantum advantage. Here, we introduce a highly scalable but classical algorithm that can solve GBS approximately. Our numerical simulation of the output count data is closer to the exact solution than current experiments up to 1152 modes. This algorithm outperforms all previous classical, approximate algorithms and scales efficiently to larger experiments. Our results show that effects beyond losses can cause the errors that allow classical simulability. This work will lead to more precise algorithms and is a step towards understanding how QC quantum advantage is affected by the underlying physics.

quant-pharXiv:2604.12330Apr 15, 20260 citations