Considering the problem of sampling from the output photon-counting probability distribution of a linear-optical network for input Gaussian states, we obtain results that are of interest from both quantum theory and the computational complexity theory point of view. We derive a general formula for calculating the output probabilities, and by considering input thermal states, we show that the output probabilities are proportional to permanents of positive-semidefinite Hermitian matrices. It is believed that approximating permanents of complex matrices in general is a #P-hard problem. However, we show that these permanents can be approximated with an algorithm in the BPP^{NP} complexity class, as there exists an efficient classical algorithm for sampling from the output probability distribution. We further consider input squeezed-vacuum states and discuss the complexity of sampling from the probability distribution at the output.
Considering the problem of sampling from the output photon-counting probability distribution of a linear-optical network for input Gaussian states, we obtain results that are of interest from both quantum theory and the computational complexity theory point of view. We derive a general formula for calculating the output probabilities, and by considering input thermal states, we show that the output probabilities are proportional to permanents of positive-semidefinite Hermitian matrices. It is believed that approximating permanents of complex matrices in general is a #P-hard problem. However, we show that these permanents can be approximated with an algorithm in the BPP^{NP} complexity class, as there exists an efficient classical algorithm for sampling from the output probability distribution. We further consider input squeezed-vacuum states and discuss the complexity of sampling from the probability distribution at the output.
Considering the problem of sampling from the output photon-counting probability distribution of a linear-optical network for input Gaussian states, we obtain new results that are of interest from both quantum theory and the complexity theory point of view. We derive a general formula for calculating the output probabilities. By considering input thermal states, we show that the output probabilities are proportional to permanents of positive definite Hermitian matrices. It is believed that approximating permanents of complex matrices in general is a #P-hard problem. However, we show that these permanents can be approximated with an algorithm within the third level of the polynomial hierarchy, as there exists an efficient classical algorithm for sampling from the output probability distribution. On the other hand, considering input squeezed-vacuum states, we show the output probabilities are proportional to a quantity which is, for at least a specific configuration, #P-hard to approximate.
We give new evidence that quantum computers -- moreover, rudimentary quantum computers built entirely out of linear-optical elements -- cannot be efficiently simulated by classical computers. In particular, we define a model of computation in which identical photons are generated, sent through a linear-optical network, then nonadaptively measured to count the number of photons in each mode. This model is not known or believed to be universal for quantum computation, and indeed, we discuss the prospects for realizing the model using current technology. On the other hand, we prove that the model is able to solve sampling problems and search problems that are classically intractable under plausible assumptions. Our first result says that, if there exists a polynomial-time classical algorithm that samples from the same probability distribution as a linear-optical network, then P^#P=BPP^NP, and hence the polynomial hierarchy collapses to the third level. Unfortunately, this result assumes an extremely accurate simulation. Our main result suggests that even an approximate or noisy classical simulation would already imply a collapse of the polynomial hierarchy. For this, we need two unproven conjectures: the "Permanent-of-Gaussians Conjecture", which says that it is #P-hard to approximate the permanent of a matrix A of independent N(0,1) Gaussian entries, with high probability over A; and the "Permanent Anti-Concentration Conjecture", which says that |Per(A)|>=sqrt(n!)/poly(n) with high probability over A. We present evidence for these conjectures, both of which seem interesting even apart from our application. This paper does not assume knowledge of quantum optics. Indeed, part of its goal is to develop the beautiful theory of noninteracting bosons underlying our model, and its connection to the permanent function, in a self-contained way accessible to theoretical computer scientists.
One of the most important problems in linear optics quantum computing is to find the origin of its computational complexity. This work shows that the majorization of photon distributions is one of the crucial factors that affect the complexity of multimode passive linear optics, which explains one aspect of the boson sampling hardness. As a preliminary to the main discussion, a majorization-dependent quantity that can measure the quantum complexity of identical particle distributions is introduced, which we name \emph{the Boltzmann entropy of elementary quantum complexity SBq.} It decreases as the majorization of the photon distribution vector increases (Schur concavity). Using the properties of majorization and SBq, we analyze two quantities that are important criteria for the photon scattering process, $\cT$ (the runtime of a generalized classical algorithm for calculating the permanent) and $\cE$ (the additive error bound for an approximated permanent estimator). First, for all the known algorithms for computing the permanents of matrices with repeated rows and columns, the runtime $\cT$ becomes shorter as the input and output distribution vectors are more majorized. Second, the error bound $\cE$ decreases as the majorization difference of input and output states increases. In addition, SBq turns out to be an underlying quantity of $\cT$ and $\cE$, which implies that SBq is an essential resource for the computational complexity of linear optics. We expect that our current results would provide a clue to find the genuine resource of quantum supremacy and its operational mechanism in linear optics.
We construct a quantum-inspired classical algorithm for computing the permanent of Hermitian positive semidefinite matrices by exploiting a connection between these mathematical structures and the boson sampling model. Specifically, the permanent of a Hermitian positive semidefinite matrix can be expressed in terms of the expected value of a random variable, which stands for a specific photon-counting probability when measuring a linear-optically evolved random multimode coherent state. Our algorithm then approximates the matrix permanent from the corresponding sample mean and is shown to run in polynomial time for various sets of Hermitian positive semidefinite matrices, achieving a precision that improves over known techniques. This work illustrates how quantum optics may benefit algorithm development.
This thesis presents results under the topics of quantum correlations and quantum information processing using linear-optical networks. The first part of this thesis concerns with quantum correlations, specially in Gaussian states, which play a central role as resource in quantum protocols. The second part is about quantum information processing using linear-optical networks that are of great practical interest due to their simple physical realization. In the first part, we present a measurement-based method for verifying nonzero quantum discord, a measure of quantum correlations, in bipartite systems that can be used for both continuous and discrete-variable systems. Based on this method, we show that the only bipartite Gaussian states with zero quantum discord are product states. We also present a simple and efficient experimental method for verifying quantum correlations in Gaussian states using homodyne measurements. Moreover, we introduce an operational measure for quantifying quantum correlations in Gaussian states that is purely based on Gaussian measurements. We then illustrate the operational significance of the measure in terms of a Gaussian quantum protocol. In the second part, we present results on linear quantum-optics experiments, specifically boson sampling, an intermediate model of quantum computation that can be implemented using single-photon states, linear-optical networks, and photodetectors. We first present an efficient experimental method for characterization of linear-optical networks, which is essential for practical implementation of boson sampling. We show that using coherent states one can directly measure all the nontrivial phases and moduli of the matrix describing the network. Next, we consider the problem of boson sampling with Gaussian states. We derive a general formula for calculating the output photon-counting probabilities. We show that for input thermal states, sampling from the output probability distribution can be efficiently classically simulated. Using this, we find that permanents of positive-semidefinite Hermitian matrices can be approximated to within a multiplicative error in BPPNP. We also discuss boson sampling with squeezed vacuum states. Finally, we provide a sufficient condition for the efficient classical simulation of the general sampling problem using linear-quantum optics, which involves a multimode input quantum state to a linear-optical network and set of measurements at the output. This condition is based on the phase-space quasiprobability distributions, and suggests that negativity is a quantum resource. We apply this condition to implementations of boson sampling using single-photon or spontaneous parametric down-conversion sources. We show that above some threshold for loss and noise in the experiment, boson sampling is classically simulatable.
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.