Boson sampling is a computational task particularly friendly to quantum computers as opposed to classical computers. As explained by Philip Ball, it "entails calculating the probability distribution of many bosons — a category of fundamental particle that includes photons — whose quantum waves interfere with one another in a way that essentially randomizes the position of the particles", thus generating "an equation in many unknowns."
Background Boson sampling is a restricted model of non-universal quantum computation introduced by Scott Aaronson and Alex Arkhipov after the original work of Lidror Troyansky and Naftali Tishby, that explored possible use of boson scattering to evaluate expectation values of permanents of matrices.Troyansky, Lidror; Tishby, Naftali (1996). "Permanent uncertainty: On the quantum evaluation of the determinant and the permanent of a matrix". Proceedings of PhysComp, 1996: 314-318. The model consists of sampling from the probability distribution of identical bosons scattered by a linear interferometer. Although the problem is well defined for any bosonic particles, its photonic version is currently considered as the most promising platform for a scalable implementation of a boson sampling device, which makes it a non-universal approach to linear optical quantum computing. Moreover, while not universal, the boson sampling scheme is strongly believed to implement computing tasks that are hard to implement with classical computers by using far fewer physical resources than a full linear-optical quantum computing setup . This advantage makes it an ideal candidate for demonstrating the power of quantum computation in the near term.
Description Consider a multimode linear-optical circuit of N modes that is injected with M indistinguishable single photons (N>M). Then, the photonic implementation of the boson sampling task consists of generating a sample from the probability distribution of single-photon measurements at the output of the circuit. Specifically, this requires reliable sources of single photons (currently the most widely used ones are parametric down-conversion crystals), as well as a linear interferometer. The latter can be fabricated, e.g., with fused-fiber beam splitters, through silica-on-silicon or laser-written integrated interferometers, or electrically and optically interfaced optical chips. Finally, the scheme also necessitates high efficiency single photon-counting detectors, such as those based on current-biased superconducting nanowires, which perform the measurements at the output of the circuit. Therefore, based on these three ingredients, the boson sampling setup does not require any ancillas, adaptive measurements or entangling operations, as does e.g. the universal optical scheme by Knill, Laflamme and Milburn (the KLM scheme). This makes it a non-universal model of quantum computation, and reduces the amount of physical resources needed for its practical realization.
Specifically, suppose the linear interferometer is described by an N×N unitary matrix which performs a linear transformation of the creation (annihilation) operators of the circuit's input modes:
Here i (j) labels the input (output) modes, and denotes the creation (annihilation) operators of the output modes (i,j=1,..., N). An interferometer characterized by some unitary naturally induces a unitary evolution on -photon states. Moreover, the map is a homomorphism between -dimensional unitary matrices, and unitaries acting on the exponentially large Hilbert space of the system: simple counting arguments show that the size of the Hilbert space corresponding to a system of M indistinguishable photons distributed among N modes is given by the binomial coefficient .
Suppose the interferometer is injected with an input state of single photons with is the number of photons injected into the kth mode). Then, the state at
the output of the circuit can be written down as A simple way to understand the homomorphism between and is the following :
We define the isomorphism for the basis states: , and get the following result :
Consequently, the probability of detecting photons at the kth output mode is given as
In the above expression stands for the permanent of the matrix which is obtained from the unitary by repeating times its ith column and times its jth row. Usually, in the context of the boson sampling problem the input state is taken of a standard form, denoted as for which each of the first M modes of the interferometer is injected with a single photon. In this case the above expression reads:
where the matrix is obtained from by keeping its first M columns and repeating times its jth row. Subsequently, the task of boson sampling is to sample either exactly or approximately from the above output distribution, given the unitary describing the linear-optical circuit as input. As detailed below, the appearance of the permanent in the corresponding statistics of single-photon measurements contributes to the hardness of the boson sampling problem.
Complexity of the problem The main reason of the growing interest towards the model of boson sampling is that despite being non-universal it is strongly believed to perform a computational task that is intractable for a classical computer. One of the main reasons behind this is that the probability distribution, which the boson sampling device has to sample from, is related to the permanent of complex matrices. The computation of the permanent is in the general case an extremely hard task: it falls in the #P-hard complexity class. Moreover, its approximation to within multiplicative error is a #P-hard problem as well.
All current proofs of the hardness of simulating boson sampling on a classical computer rely on the strong computational consequences that its efficient simulation by a classical algorithm would have. Namely, these proofs show that an efficient classical simulation would imply the collapse of the polynomial hierarchy to its third level, a possibility that is considered very unlikely by the computer science community, due to its strong computational implications (in line with the strong implications of P=NP problem).
Exact sampling
The hardness proof of the exact boson sampling problem can be achieved following two distinct paths. Specifically, the first one uses the tools of the computational complexity theory and combines the following two facts:
Approximating the probability of a specific measurement outcome at the output of a linear interferometer to within a multiplicative constant is a #P-hard problem (due to the complexity of the permanent) If a polynomial-time classical algorithm for exact boson sampling existed, then the above probability could have been approximated to within a multiplicative constant in the BPPNPcomplexity class, i.e. within the third level of the polynomial hierarchy
When combined these two facts along with Toda's theorem result in the collapse of the polynomial hierarchy, which as mentioned above is highly unlikely to occur. This leads to the conclusion that there is no classical polynomial-time algorithm for the exact boson sampling problem.
On the other hand, the alternative proof is inspired by a similar result for another restricted model of quantum computation – the model of instantaneous quantum computing. Namely, the proof uses the KLM scheme, which says that linear optics with adaptive measurements is universal for the class BQP. It also relies on the following facts:
Linear optics with postselected measurements is universal for PostBQP, i.e. quantum polynomial-time class with postselection (a straightforward corollary of the KLM construction) The class PostBQP is equivalent to PP (i.e. the probabilistic polynomial-time class): PostBQP = PP The existence of a classical boson sampling algorithm implies the simulability of postselected linear optics in the PostBPP class (that is, classical polynomial-time with postselection, known also as the class BPPpath)
Again, the combination of these three results, as in the previous case, results in the collapse of the polynomial hierarchy. This makes the existence of a classical polynomial-time algorithm for the exact boson sampling problem highly unlikely.
The best proposed classical algorithm for exact boson sampling runs in time for a system with n photons and m output modes. This algorithm leads to an estimate of 50 photons required to demonstrate quantum supremacy with boson sampling. There is also an open-source implementation in R.
Approximate sampling The above hardness proofs are not applicable to the realistic implementation of a boson sampling device, due to the imperfection of any experimental setup (including the presence of noise, decoherence, photon losses, etc.). Therefore, for practical needs one necessitates the hardness proof for the corresponding approximate task. The latter consists of sampling from a probability distribution that is close to the one given by , in terms of the total variation distance. The understanding of the complexity of this problem relies then on several additional assumptions, as well as on two yet unproven conjectures.
Specifically, the proofs of the exact boson sampling problem cannot be directly applied here, since they are based on the #P-hardness of estimating the exponentially-small probability of a specific measurement outcome. Thus, if a sampler "knew" which we wanted to estimate, then it could adversarially choose to corrupt it (as long as the task is approximate). That is why, the idea is to "hide" the above probability into an N×N random unitary matrix. This can be done knowing that any M×M submatrix of a unitary , randomly chosen according to the Haar measure, is close in variation distance to a matrix of i.i.d. complex random Gaussian variables, provided that M ≤ N1/6 (Haar random matrices can be directly implemented in optical circuits by mapping independent probability density functions for their parameters, to optical circuit components, i.e., beam splitters and phase shifters). Therefore, if the linear optical circuit implements a Haar random unitary matrix, the adversarial sampler will not be able to detect which of the exponentially many probabilities we care about, and thus will not be able to avoid its estimation. In this case is proportional to the squared absolute value of the permanent of the M×M matrix of i.i.d. Gaussians, smuggled inside These arguments bring us to the first conjecture of the hardness proof of approximate boson sampling problem – the permanent-of-Gaussians conjecture: Approximating the permanent of a matrix of i.i.d. Gaussians to within multiplicative error is a #P-hard task.
Moreover, the above conjecture can be linked to the estimation of which the given probability of a specific measurement outcome is proportional to. However to establish this link one has to rely on another conjecture – the permanent anticoncentration conjecture: There exists a polynomial Q such that for any M and δ>0 the probability over M×M matrices of the following inequality to hold is smaller than δ: