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.
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.
Gaussian boson sampling (GBS) is a sampling task proposed to demonstrate quantum advantage. We consider Gaussian boson sampling on M optical modes, with K equally squeezed input modes and N observed photon counts. We complete the proof of the hiding conjecture for Gaussian boson sampling with an arbitrary number of squeezers K, which is a part of the argument for classical hardness of GBS. In particular, we show that for any K and N=o(K), the symmetric product MK−1/2UNKUNKT, for UNK the top left N×K submatrix of an M×M Haar random unitary U, is close in total variation distance to both an N×N symmetric complex Gaussian matrix G with independent entries, and the symmetric product GGT/K for G an N×K matrix of iid standard complex Gaussians. We show however that the density-based instance generating method of [Aaronson and Arkhipov, Theory Comput. 9, 143 (2013), Lemma 5.8] used to efficiently implement a hiding procedure fails for Gaussian boson sampling with K=cM if c<1/2. Instead we use approximate instance generating to implement the hiding for the usual classical hardness reduction.
BosonSampling is the leading candidate for demonstrating quantum computational advantage in photonic systems. While we have recently seen many impressive experimental demonstrations, there is still a formidable distance between the complexity-theoretic hardness arguments and current experiments. One of the largest gaps involves the ratio of particles to modes—all current hardness evidence assumes a “dilute” regime in which the number of linear optical modes scales at least quadratically in the number of particles. By contrast, current experiments operate in a “saturated” regime with a linear number of modes. In this paper, we bridge this gap, bringing the hardness evidence for experiments in the saturated regime to the same level as had been previously established for the dilute regime. This involves proving a worst-to-average-case reduction for computing the permanent, which is robust both to large numbers of row repetitions and also to distributions over matrices with correlated entries. We also apply similar arguments to give evidence for hardness of Gaussian BosonSampling in the saturated regime.
Recent experiments demonstrated quantum computational advantage in random circuit sampling and Gaussian boson sampling. However, it is unclear whether these experiments can lead to practical applications even after considerable research effort. On the other hand, simulating the quantum coherent dynamics of interacting spins has been considered as a potential first useful application of quantum computers, providing a possible quantum advantage. Despite evidence that simulating the dynamics of hundreds of interacting spins is challenging for classical computers, concrete proof is yet to emerge. We address this problem by proving that sampling from the output distribution generated by a wide class of quantum spin Hamiltonians is a hard problem for classical computers. Our proof is based on the Taylor series of the output probability, which contains the permanent of a matrix as a coefficient when bipartite spin interactions are considered. We devise a classical algorithm that extracts the coefficient using an oracle estimating the output probability. Since calculating the permanent is #P-hard, such an oracle does not exist unless the polynomial hierarchy collapses. With an anticoncentration conjecture, the hardness of the sampling task is also proven. Based on our proof, we estimate that an instance involving about 200 spins will be challenging for classical devices but feasible for intermediate-scale quantum computers with fault-tolerant qubits.
Recent demonstrations of quantum computational advantage have been driven largely by sampling problems. A prominent model, boson sampling, involves sampling from the output distribution of a linear optical network. However, its classical hardness hinges on two plausible yet less-studied conjectures: the average-case hardness of approximating Gaussian permanents, and the permanent anti-concentration conjecture (PACC). The PACC is a purely mathematical assertion regarding the distributional properties of random Gaussian matrices. While the typical magnitude of the permanent has been established for discrete random matrices, the complex Gaussian case, which governs transition amplitudes in linear optical networks, has remained open. Here, we establish a weak anti-concentration bound by upper-bounding the probability that a random Gaussian permanent is superexponentially smaller than its standard deviation. Tightening this bound to an inverse-polynomial fraction would prove the original PACC. As a corollary, we establish the typical magnitude of Gaussian permanents, on par with Tao and Vu's seminal result for Bernoulli matrices. Combined with the Aaronson-Arkhipov framework, our result implies that classically simulating boson sampling to within a superexponentially small total variation distance would collapse the polynomial hierarchy, assuming the remaining conjectures hold.
It remains questionable whether all physically realizable computational model can be simulated by currently available digital computer in an efficient manner. The theory of Quantum Mechanics offers an answer to this question through one of its branches that intersects with Computer Science, known as Quantum Computing. It claims that current computers, which is operating based on classical mechanics cannot efficiently simulate quantum mechanical process. Under this claim, a computer that is operating based on quantum mechanics holds more computational power than classical computers, promising a possibility to computationally solve problems that are classically intractable. To show that this claim holds, numerous quantum computational models have been proposed and analyzed through the lens of Computational Complexity Theory, providing a rigorous notion of efficiency. Models that are more feasible experimentally, although not necessarily universal, have also been of a particular interests given the numerous complicated challenges surrounding the experimental implementation of a universal quantum computer. One of this non-universal models is called Gaussian Boson Sampling (GBS), which embraces the methods of Quantum Optics by sampling the number of photon outputs from a linear optical network as a means to process quantum information. Compared to its prototype model, Boson Sampling, GBS is more experimentally feasible due to its method of generating photon that is based on the Continuous Variable (CV) paradigm of Quantum Information. Nevertheless as with Boson Sampling, it was also shown that classical simulation of GBS cannot be performed efficiently under some highly plausible conjectures. In the work presented in this thesis, we probe the complexity of classically constructing the probability distribution induced by GBS using the method of Quantum Homodyne Tomography. Instead of photon number measurement, this method further embraces the CV paradigm in the measurement of GBS by using Homodyne measurements that outputs real numbers. Sample data obtained from the measurement outcomes is then classically processed using Pattern Functions, which we use to approximate the probability distribution of GBS. A series of computer simulations that approximates some probability values of GBS are presented here, which shows that the number of samples needed to decrease the error of the approximation increases rapidly for more accurate approximation. We have derived a bound for the approximation error which can be achieved given that the sampled data satisfies a certain statistical property. This statistical property can eventually be satisfied as the number of Homodyne samples increases. Having shown another evidence for the complexity of approximating GBS using Homodyne Tomography, we further investigate the nature of the complexity of GBS by analyzing its classical-quantum computational boundary in the spectrum of amount of noise present in a GBS setup. In doing this, we built our discussions on the measure of non-classicality using the presence of negative values in the Quasi-probability distribution (QPD) representation of states of a quantum system. We then discuss existing results that shows the possibility of efficient classical simulation of a quantum computational model given a sufficient amount of noise. These results impose a necessary criteria of the minimum amount of noise that an experiment has to surpass in order for it to be impossible to simulate classically in an efficient manner. We extend this idea for GBS, where we propose a modified GBS where we consider noise in its measurements that opens a way for a possible formulation of a noise condition that a GBS experiment has to fulfill to rule out possible efficient classical simulation. To further probe the classical-quantum computational boundary, we also propose a different quantum computational model called the Photon-added Thermal State CV-Sampling (PATS CVS), which can be formulated similarly to our noisy GBS model. We then discuss existing results that analyzes the negativity of the QPD representation of a noisy Photon-added Thermal state (PATS), which constitutes the inputs for PATS CVS. Using the result that shows the quantum-classical transition in terms of the QPD negativity for a PATS state when the amount of noise changes, we discuss the potential of PATS CVS model as a possible avenue to further probe the transition between efficiently simulable and non-efficiently simulable quantum mechanical experiment.
Abstract Since its introduction boson sampling has been the subject of intense study in the world of quantum computing. In the context of Fock-state boson sampling, the task is to sample independently from the set of all n × n submatrices built from possibly repeated rows of a larger m × n complex matrix according to a probability distribution related to the permanents of the submatrices. Experimental systems exploiting quantum photonic effects can in principle perform the task at great speed. For classical computing, Aaronson and Arkhipov (2011) showed that exact boson sampling problem cannot be solved in polynomial time unless the polynomial hierarchy collapses to the third level. Indeed for a number of years the fastest known exact classical algorithm ran in O ( m + n − 1 n n 2 n ) time per sample, emphasising the potential speed advantage of quantum computation. The advantage was reduced by Clifford and Clifford (2018), who gave a significantly faster classical solution taking O ( n 2 n + poly ( m , n ) ) time and linear space, matching the complexity of computing the permanent of a single matrix when m is polynomial in n. We continue by presenting an algorithm for Fock boson sampling whose average-case time complexity is much faster when m is proportional to n. In particular, when m = n our algorithm runs in approximately O(n · 1.69 n ) time on average. This result further increases the problem size needed to establish quantum computational advantage via the Fock scheme of boson sampling.