Abstract A fundamental question in linear optical quantum computing is to understand the origin of the quantum supremacy in the physical system. It is found that the multimode linear optical transition amplitudes are calculated through the permanents of transition operator matrices, which is a hard problem for classical simulations (boson sampling problem). We can understand this problem by considering a quantum measure that directly determines the runtime for computing the transition amplitudes. In this paper, we suggest a quantum measure named “Fock state concurrence sum” C S , which is the summation over all the members of “the generalized Fock state concurrence” (a measure analogous to the generalized concurrences of entanglement and coherence). By introducing generalized algorithms for computing the transition amplitudes of the Fock state boson sampling with an arbitrary number of photons per mode, we show that the minimal classical runtime for all the known algorithms directly depends on C S . Therefore, we can state that the Fock state concurrence sum C S behaves as a collective measure that controls the computational complexity of Fock state BS. We expect that our observation on the role of the Fock state concurrence in the generalized algorithm for permanents would provide a unified viewpoint to interpret the quantum computing power of linear optics.
Abstract A fundamental question in linear optical quantum computing is to understand the origin of the quantum supremacy in the physical system. It is found that the multimode linear optical transition amplitudes are calculated through the permanents of transition operator matrices, which is a hard problem for classical simulations (boson sampling problem). We can understand this problem by considering a quantum measure that directly determines the runtime for computing the transition amplitudes. In this paper, we suggest a quantum measure named “Fock state concurrence sum” C S , which is the summation over all the members of “the generalized Fock state concurrence” (a measure analogous to the generalized concurrences of entanglement and coherence). By introducing generalized algorithms for computing the transition amplitudes of the Fock state boson sampling with an arbitrary number of photons per mode, we show that the minimal classical runtime for all the known algorithms directly depends on C S . Therefore, we can state that the Fock state concurrence sum C S behaves as a collective measure that controls the computational complexity of Fock state BS. We expect that our observation on the role of the Fock state concurrence in the generalized algorithm for permanents would provide a unified viewpoint to interpret the quantum computing power of linear optics.
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.
Boson sampling is a specific quantum computation, which is likely hard to implement efficiently on a classical computer. The task is to sample the output photon-number distribution of a linear-optical interferometric network, which is fed with single-photon Fock-state inputs. A question that has been asked is if the sampling problems associated with any other input quantum states of light (other than the Fock states) to a linear-optical network and suitable output detection strategies are also of similar computational complexity as boson sampling. We consider the states that differ from the Fock states by a displacement operation, namely the displaced Fock states and the photon-added coherent states. It is easy to show that the sampling problem associated with displaced single-photon Fock states and a displaced photon-number detection scheme is in the same complexity class as boson sampling for all values of displacement. On the other hand, we show that the sampling problem associated with single-photon-added coherent states and the same displaced photon-number detection scheme demonstrates a computational-complexity transition. It transitions from being just as hard as boson sampling when the input coherent amplitudes are sufficiently small to a classically simulatable problem in the limit of large coherent amplitudes.
Boson Sampling is a prominent candidate for the demonstration of quantum computational advantage but it remains unclear whether a large-scale boson sampler can find useful computational applications. The challenge is that to use a boson sampler to estimate, for example, a physical observable, it is necessary to coarse grain the outcome distribution, owing to the exponential size of the outcome space and the anti-concentration properties of the Boson Sampling distribution. In this work, we analyse the complexity of a specific type of coarse-graining of Boson Sampling distributions based on linear functions of the output photon occupation numbers, which we refer to as linear statistics. We present an efficient classical algorithm for approximating linear statistics of boson samplers within additive error for different kinds of input states, such as Fock states and squeezed states. This allows us to unify in the same framework recent results on efficient quantum-inspired classical algorithms for simulating molecular vibronic spectra, or efficient classical approximations of coarse-grained distributions based on detector binning. Additionally, we show how our algorithm can be used to classically evaluate a proposed one-way function based on Boson Sampling, while other proposals for cryptographic applications escape our classical simulation techniques. We leave open the question of classical simulability of non-linear statistics and connect it to the problem of computing transition amplitudes of linear-optical circuits with one layer of interactions.
ABSTRACT In linear optics, photons are scattered in a network through passive optical elements including beam splitters and phase shifters, leading to many intriguing applications in physics, such as Mach–Zehnder interferometry, the Hong–Ou–Mandel effect, and tests of fundamental quantum mechanics. Here we present the fundamental limit in the transition amplitudes of bosons, applicable to all physical linear optical networks. Apart from boson sampling, this transition bound results in many other interesting applications, including behaviors of Bose–Einstein condensates (BEC) in optical networks, counterparts of Hong–Ou–Mandel effects for multiple photons, and approximating permanents of matrices. In addition, this general bound implies the existence of a polynomial-time randomized algorithm for estimating the transition amplitudes of bosons, which represents a solution to an open problem raised by Aaronson and Hance (Quantum Inf Comput 2012; 14: 541–59). Consequently, this bound implies that computational decision problems encoded in linear optics, prepared and detected in the Fock basis, can be solved efficiently by classical computers within additive errors. Furthermore, our result also leads to a classical sampling algorithm that can be applied to calculate the many-body wave functions and the S-matrix of bosonic particles.
Boson sampling has been presented as a simplified model for linear optical quantum computing. In the boson-sampling model, Fock states are passed through a linear optics network and sampled via number-resolved photodetection. It has been shown that this sampling problem likely cannot be efficiently classically simulated. This raises the question as to whether there are other quantum states of light for which the equivalent sampling problem is also computationally hard. We present evidence, without using a full complexity proof, that a very broad class of quantum states of light---arbitrary superpositions of two or more coherent states---when evolved via passive linear optics and sampled with number-resolved photodetection, likely implements a classically hard sampling problem.
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.