8

It appears to be true, up to a point. As I read Scott Aaronson's paper, it says that if you start with 1 photon in each of the first $M$ modes of an interferometer, and find the probability $P_S$ that a set $s_i$ photons is output in each mode $i\in\{1,\ldots, N\}$ where $\sum_is_i=M$, is $$ P_s=\frac{|\text{Per(A)}|^2}{s_1!s_2!\ldots s_M!}. $$ So, indeed, ...


7

About the need of boson sampling verification First of all, let me point out that it is not a strict necessity to verify the output of a boson sampler. By this, I don't mean to say that it is not useful or interesting to try and do so, but rather that it is in some sense more of a practical than a fundamental necessity. I think you yourself put up a good ...


6

Boson sampling samples from a distribution, but does not compute the full distribution. While computing the distribution is linked to computing permanents, which is #P-hard, we would expect that sampling from such a distribution is considerably less powerful. Even if such sampling a number $N$ of times would allow us to estimate the permanent of a specific ...


6

You cannot efficiently recover the absolute values of the amplitudes, but if you allow for arbitrary many samples, then you can estimate them to whatever degree of accuracy you like. More specifically, if the input state is a single photon in each of the first $n$ modes, and one is willing to draw an arbitrary number of samples from the output, then it is ...


6

There are a couple variants of the HOG test. "Old HOG" computed the proportion of unique samples whose probability is larger than the median probability of the distribution. It then compares that proportion to a threshold, e.g. 2/3. If you have enough larger-than-median outputs, you pass the test. "New HOG" instead computes the mean of the probabilities of ...


4

Just a small complement to @gIS excellent answer: I know of several people (including myself) interested on the public verification aspect. As far as I know, all attempts have failed, hence the lack of literature on the subject: as soon as one can prove the Boson sampler acted correctly, it is indeed a regime where the Boson sampler can be efficiently ...


3

This is a well-framed question that highlights subtleties about what is known and unknown on the strengths and limitations of quantum computers. Initially, it is completely consistent with what we know, and indeed what we expect, for both NP and BQP to be incomparable. That is, there are problems such as the TSP that are known to be in NP that are not ...


2

The two main classes of sampling problems demonstrating quantum supremacy are BosonSampling and IQP which are intermediate models of optical and qubit based quantum information processing architectures. Even reasonable approximations to the outputs from these problems, given some highly plausible conjectures, are hard for classical computers to compute. ...


2

The reason for this is because when you truncate the Hilbert space, applying the raising operator on the highest state raises you out of the Hilbert space, ie it gives a zero vector. Thus the commutator in matrix form is not the identity but a diagonal matrix with all ones expect for the last entry which is minus one. If your have any nonzero amplitude in ...


1

@gIS's comment effectively answers the question, but to provide a bit more detail Aaronson at shtetl-optimized has a nice blog post on the Gaussian Boson Sampling approach of USTC, contrasting it with Fock state Boson Sampling, wherein the presence/absence of photons correspond to something closer to a conventional digital ($\vert 0\rangle$/$\vert 1\rangle$) ...


Only top voted, non community-wiki answers of a minimum length are eligible