Boson sampling
Boson sampling is a restricted model of non-universal
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
Specifically, suppose the linear interferometer is described by an N×N unitary matrix which performs a linear transformation of the
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 (notice that since this homomorphism exists, not all values of are possible).
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: x, and get the following result : xx
Consequently, the probability of detecting photons at the kth output mode is given as[9]
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
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[citation needed] 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,[10] 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.[11] 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 PP (i.e. the probabilistic polynomial-time class): PostBQP = PP[12]
- 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.[13] 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
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
- 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 δ:
By making use of the above two conjectures (which have several evidences of being true), the final proof eventually states that the existence of a classical polynomial-time algorithm for the approximate boson sampling task implies the collapse of the polynomial hierarchy. It is also worth mentioning another fact important to the proof of this statement, namely the so-called bosonic birthday paradox (in analogy with the well-known
Although the probability of a specific measurement outcome at the output of the interferometer is related to the permanent of submatrices of a unitary matrix, a boson sampling machine does not allow its estimation. The main reason behind is that the corresponding detection probability is usually exponentially small. Thus, in order to collect enough statistics to approximate its value, one has to run the quantum experiment for exponentially long time. Therefore, the estimate obtained from a boson sampler is not more efficient that running the classical polynomial-time algorithm by Gurvits for approximating the permanent of any matrix to within additive error.[17]
Variants
Scattershot boson sampling
As already mentioned above, for the implementation of a boson sampling machine one necessitates a reliable source of many indistinguishable photons, and this requirement currently remains one of the main difficulties in scaling up the complexity of the device. Namely, despite recent advances in photon generation techniques using atoms, molecules,
Recently, however, a new scheme has been proposed to make the best use of PDC sources for the needs of boson sampling, greatly enhancing the rate of M-photon events. This approach has been named scattershot boson sampling,[18][19] which consists of connecting N (N>M) heralded single-photon sources to different input ports of the linear interferometer. Then, by pumping all N PDC crystals with simultaneous laser pulses, the probability of generating M photons will be given as Therefore, for N≫M, this results in an exponential improvement in the single photon generation rate with respect to the usual, fixed-input boson sampling with M sources. This setting can also be seen as a problem of sampling N two-mode squeezed vacuum states generated from N PDC sources.
Scattershot boson sampling is still intractable for a classical computer: in the conventional setup we fixed the columns that defined our M×M submatrix and only varied the rows, whereas now we vary the columns too, depending on which M out of N PDC crystals generated single photons. Therefore, the proof can be constructed here similar to the original one. Furthermore, scattershot boson sampling has been also recently implemented with six photon-pair sources coupled to integrated photonic circuits of nine and thirteen modes, being an important leap towards a convincing experimental demonstration of the quantum computational supremacy.[20] The scattershot boson sampling model can be further generalized to the case where both legs of PDC sources are subject to linear optical transformations (in the original scattershot case, one of the arms is used for heralding, i.e., it goes through the identity channel). Such a twofold scattershot boson sampling model is also computationally hard, as proven by making use of the symmetry of quantum mechanics under time reversal.[21]
Gaussian boson sampling
Another photonic implementation of boson sampling concerns Gaussian input states, i.e. states whose quasiprobability Wigner distribution function is a Gaussian one. The hardness of the corresponding sampling task can be linked to that of scattershot boson sampling.[22] Namely, the latter can be embedded into the conventional boson sampling setup with Gaussian inputs. For this, one has to generate two-mode entangled Gaussian states and apply a Haar-random unitary to their "right halves", while doing nothing to the others. Then we can measure the "left halves" to find out which of the input states contained a photon before we applied This is precisely equivalent to scattershot boson sampling, except for the fact that our measurement of the herald photons has been deferred till the end of the experiment, instead of happening at the beginning. Therefore, approximate Gaussian boson sampling can be argued to be hard under precisely the same complexity assumption as can approximate ordinary or scattershot boson sampling.[19] Gaussian resources can be employed at the measurement stage, as well. Namely, one can define a boson sampling model, where a linear optical evolution of input single-photon states is concluded by Gaussian measurements (more specifically, by eight-port homodyne detection that projects each output mode onto a squeezed coherent state). Such a model deals with continuous-variable measurement outcome, which, under certain conditions, is a computationally hard task.[21] Finally, a linear optics platform for implementing a boson sampling experiment where input single-photons undergo an active (non-linear) Gaussian transformation is also available. This setting makes use of a set of two-mode squeezed vacuum states as a prior resource, with no need of single-photon sources or in-line nonlinear amplification medium.[23] This variant uses the Hafnian, a generalization of the permanent.[22]
Classically simulable boson sampling tasks
The above results state that the existence of a polynomial-time classical algorithm for the original boson sampling scheme with indistinguishable single photons (in the exact and approximate cases), for scattershot, as well as for the general Gaussian boson sampling problems is highly unlikely. Nevertheless, there are some non-trivial realizations of the boson sampling problem that allow for its efficient classical simulation. One such example is when the optical circuit is injected with distinguishable single photons. In this case, instead of summing the probability amplitudes corresponding to photonic many-particle paths, one has to sum the corresponding probabilities (i.e. the squared absolute values of the amplitudes). Consequently, the detection probability will be proportional to the permanent of submatrices of (component-wise) squared absolute value of the unitary The latter is now a non-negative matrix. Therefore, although the exact computation of the corresponding permanent is a
Another instance of classically simulable boson sampling setups consists of sampling from the probability distribution of
Experimental implementations
The above requirements for the photonic boson sampling machine allow for its small-scale construction by means of existing technologies. Consequently, shortly after the theoretical model was introduced, four different groups[3][4][6][7] simultaneously reported its realization.
Specifically, this included the implementation of boson sampling with:
- two and three photons scattered by a six-mode linear unitary transformation (represented by two orthogonal polarizations in 3×3 spatial modes of a fused-fiber beam splitter) by a collaboration between the University of Queensland and MIT[3]
- three photons in different modes of a six-mode silica-on-silicon waveguide circuit, by a collaboration between Universities of Oxford, Shanghai, London and Southampton[4]
- three photons in a femtosecond laser-written five-mode interferometer, by a collaboration between universities of Vienna and Jena[6]
- three photons in a femtosecond laser-written five-mode interferometer implementing a Haar-random unitary transformation, by a collaboration between Milan's Institute of Photonics and Nanotechnology, Universidade Federal Fluminense and Sapienza University of Rome.[7]
Later on, more complex boson sampling experiments have been performed, increasing the number of spatial modes of random interferometers up to 13[27] and 9[28] modes, and realizing a 6-mode fully reconfigurable integrated circuit.[8] These experiments altogether constitute the proof-of-principle demonstrations of an operational boson sampling device, and route towards its larger-scale implementations.
Implementation of scattershot boson sampling
A first scattershot boson sampling experiment has been recently implemented[20] using six photon-pair sources coupled to integrated photonic circuits with 13 modes. The 6 photon-pair sources were obtained via type-II PDC processes in 3 different nonlinear crystals (exploiting the polarization degree of freedom). This allowed to sample simultaneously between 8 different input states. The 13-mode interferometer was realized by femtosecond laser-writing technique on alumino-borosilicate glas.
This experimental implementation represents a leap towards an experimental demonstration of the quantum computational supremacy.[20]
Proposals with alternative photonic platform
There are several other proposals for the implementation of photonic boson sampling. This includes, e.g., the scheme for arbitrarily scalable boson sampling using two nested fiber loops. In this case, the architecture employs time-bin encoding, whereby the incident photons form a pulse train entering the loops. Meanwhile, dynamically controlled loop coupling ratios allow the construction of arbitrary linear interferometers. Moreover, the architecture employs only a single point of interference and may thus be easier to stabilize than other implementations.[29]
Another approach relies on the realization of unitary transformations on temporal modes based on dispersion and pulse shaping. Namely, passing consecutively heralded photons through time-independent dispersion and measuring the output time of the photons is equivalent to a boson sampling experiment. With time-dependent dispersion, it is also possible to implement arbitrary single-particle unitaries. This scheme requires a much smaller number of sources and detectors and do not necessitate a large system of beam splitters.[30]
Certification
The output of a
A first relevant question is whether it is possible or not to distinguish between uniform and boson-sampling distributions by performing a polynomial number of measurements. The initial argument introduced in Ref.[31] stated that as long as one makes use of symmetric measurement settings the above is impossible (roughly speaking a symmetric measurement scheme does not allow for labeling the output modes of the optical circuit). However, within current technologies the assumption of a symmetric setting is not justified (the tracking of the measurement statistics is fully accessible), and therefore the above argument does not apply. It is then possible to define a rigorous and efficient test to discriminate the boson sampling statistics from an unbiased probability distribution.[32] The corresponding discriminator is correlated to the permanent of the submatrix associated with a given measurement pattern, but can be efficiently calculated. This test has been applied experimentally to distinguish between a boson sampling and a uniform distribution in the 3-photon regime with integrated circuits of 5, 7, 9[28] and 13 modes.[27]
The test above does not distinguish between more complex distributions, such as quantum and classical, or between fermionic and bosonic statistics. A physically motivated scenario to be addressed is the unwanted introduction of distinguishability between photons, which destroys quantum interference (this regime is readily accessible experimentally, for example by introducing temporal delay between photons). The opportunity then exists to tune between ideally indistinguishable (quantum) and perfectly distinguishable (classical) data and measure the change in a suitably constructed metric. This scenario can be addressed by a statistical test which performs a one-on-one likelihood comparison of the output probabilities. This test requires the calculation of a small number of permanents, but does not need the calculation of the full expected probability distribution. Experimental implementation of the test has been successfully reported in integrated laser-written circuits for both the standard boson sampling[27] (3 photons in 7-, 9- and 13-mode interferometers) and the scattershot version[20] (3 photons in 9- and 13-mode interferometers with different input states). Another possibility is based on the bunching property of indinguishable photons. One can analyze the probability to find a k-fold coincidence measurement outcomes (without any multiply populated input mode), which is significantly higher for distinguishable particles than for bosons due to the bunching tendency of the latters.[28] Finally, leaving the space of random matrices one may focus on specific multimode setups with certain features. In particular, the analysis of the effect of bosonic clouding (the tendency for bosons to favor events with all particles in the same half of the output array of a continuous-time many-particle quantum walk) has been proven to discriminate the behavior of distinguishable and indistinguishable particles in this specific platform.[28]
A different approach to confirm that the boson sampling machine behaves as the theory predicts is to make use of fully reconfigurable optical circuits. With large-scale single-photon and multiphoton interference verified with predictable multimode correlations in a fully characterized circuit, a reasonable assumption is that the system maintains correct operation as the circuit is continuously reconfigured to implement a random unitary operation. To this end, one can exploit quantum suppression laws (the probability of specific input-output combinations is suppressed when the linear interferometer is described by a Fourier matrix or other matrices with relevant symmetries).[33] These suppression laws can be classically predicted in efficient ways. This approach allows also to exclude other physical models, such as mean-field states, which mimic some collective multiparticle properties (including bosonic clouding). The implementation of a Fourier matrix circuit in a fully reconfigurable 6-mode device has been reported,[8] and experimental observations of the suppression law have been shown for 2 photons in 4- and 8-mode Fourier matrices.[34]
Alternative implementations and applications
Apart from the photonic realization of the boson sampling task, several other setups have been proposed. This includes, e.g., the encoding of bosons into the local transverse phonon modes of
Another platform for implementing the boson sampling setup is a system of interacting spins: recent observation show that boson sampling with M particles in N modes is equivalent to the short-time evolution with M excitations in the
The task of boson sampling shares peculiar similarities with the problem of determining
It has also been suggested to use a superconducting resonator network Boson Sampling device as an interferometer. This application is assumed to be practical, as small changes in the couplings between the resonators will change the sampling results. Sensing of variation in the parameters capable of altering the couplings is thus achieved, when comparing the sampling results to an unaltered reference.[38]
Variants of the boson sampling model have been used to construct classical computational algorithms, aimed, e.g., at the estimation of certain matrix permanents (for instance, permanents of
Coarse-grained boson sampling has been proposed as a resource of decision and function problems that are computationally hard, and may thus have cryptographic applications.[41][42][43] The first related proof-of-principle experiment was performed with a photonic boson-sampling machine (fabricated by a direct femtosecond laser-writing technique),[44] and confirmed many of the theoretical predictions.
Gaussian boson sampling has been analyzed as a search component for computing binding propensity between molecules of pharmacological interest as well.[45]
See also
References
- .
- ^ 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.
- ^ S2CID 22912771.
- ^ S2CID 11687876.
- PMID 19532390.
- ^ S2CID 119241050.
- ^ S2CID 121093296.
- ^ S2CID 19067232.
- S2CID 121606171.
- ^ "Polynomial-time hierarchy". Complexity Zoo. Archived from the original on February 14, 2014.
- S2CID 12301677.
- S2CID 1770389.
- arXiv:1706.01260 [cs.DS].
- S2CID 46915633.
- S2CID 41510747.
- S2CID 26984278.
- ^ Gurvits, Leonid (2005). "On the complexity of mixed discriminants and related problems". Mathematical Foundations of Computer Science: 447–458.
- S2CID 27742471.
- ^ a b Aaronson, Scott (8 November 2013). "Scattershot BosonSampling: a new approach to scalable BosonSampling experiments". Shtetl-Optimized.
- ^ PMID 26601164.
- ^ S2CID 119431211.
- ^ S2CID 1665615. Retrieved 22 January 2021.
- S2CID 119227039.
- S2CID 47361920.
- S2CID 436866.
- S2CID 23490704.
- ^ S2CID 120825561.
- ^ S2CID 10874278.
- S2CID 33602886.
- S2CID 5022049.
- ].
- ].
- S2CID 44653164.
- PMID 26843135.
- S2CID 10489988.
- arXiv:1509.02703 [quant-ph].
- S2CID 960357.
- S2CID 119077553.
- ^ See open problem (4) at "Shtetl Optimized: Introducing some British people to P vs. NP". 22 July 2015.
- S2CID 54194194.
- S2CID 5311008.
- S2CID 195791867.
- ISSN 0031-8949.
- S2CID 256757275.
- PMID 32548251.