The main problem in the approach they use to boson sampling is photon loss in the sources. In their method of generating photons, each source generates two photons, and one is routed to a detector to announce the presence of the other photon (‘herald’) while the second photon goes to the experiment. They key figure of merit is how well you can perform that process. That is: if you also plug the second photon directly into a detector, what is the probability that that detector clicks, given that the first one clicks? This number is called the heralding efficiency.

They claim a heralding efficiency of 97%, which indeed would be crazy good, but if you read their text, this number first goes to 93% when say they’ve backed out 4% in free space losses, and then later on they mention they have 75% efficient detectors. The detector efficiency constrains the overall heralding efficiency, so it’s not clear what this number 93% now means. I am pretty sure the referees will force them to clarify this. As far as I understand, the record for uncorrected heralding efficiency is still around 80-82%, achieved by various groups.

Is this enough for scalable boson sampling? No. In a recent work https://arxiv.org/abs/1809.01953 we show that in fact any level of losses or photon distinguishability results in some number of photons beyond which a polynomial sampling algorithm becomes efficient. If you then ask the question ‘at what level of imperfections is does that happen before you hit 50 photons?’ the answer is: you need 88% efficient sources, provided your definition of ‘simulated’ is ‘simulated to within 10%’.

]]>>”I want to be clear that they are two distinct states”

If I understand, you mean that it remains a superposition of two distinct branches or components?

My guess is that when you try to quantize the labs there has to be some allowance for error to creep in. Its crucial to have some quantitative bounds on this error, which may be a problem for F-R.

See

https://en.wikipedia.org/wiki/No-cloning_theorem#Imperfect_cloning

Buzek and M. Hillery showed that a universal cloning machine can make a clone of an unknown state with the surprisingly high fidelity of 5/6. Also,

https://en.wikipedia.org/wiki/No-broadcast_theorem

Even to quantize a dynamical system given by polynomials of low degree is problematic, as I recall. The naive approach of using an atomic description/reduction of the labs is not valid because it doesn’t provide an exact description of a Turing machine (or human or whatever the lab is); the latter is an abstraction insofar as its error free etc. and its states are equivalence classes of physical events that aren’t quite physically defined.

There’s some interesting discussion of classical no-cloning in:

https://physics.stackexchange.com/questions/296678/what-is-quantum-about-the-no-cloning-theorem

also to avoid confusion on a related issue from QCSD:

https://physics.stackexchange.com/questions/266957/no-cloning-and-uncertainty-connections-or-misconception?rq=1

And while at it…

There is a sub-wiki on the F-R paper in:

https://en.wikipedia.org/wiki/Wigner%27s_friend#An_Extension_of_Wigner's_Friend

and in,

https://en.wikipedia.org/wiki/Wigner%27s_friend#References

note 13 lists some papers from many months ago criticising the 2016 preprint of F-R; eg

Laloë, Franck (2018-02-18). “Can quantum mechanics be considered consistent? a discussion of Frauchinger and Renner’s argument”. arXiv:1802.06396

or

“The measurement problem is the measurement problem is the measurement problem”. arXiv:1611.01111

Highly commended too is Gil Kalai’s ICM 2018 Plenary Lecture “Noise Stability, Noise Sensitivity, and the Quantum Computer Puzzle” (video here, slides here). An invitation to give a ICM plenary lecture is a very high honor for a mathematician, so congratulations, Gil! 🙂

Considered in aggregate, these works provide multiple, obvious, tempting opportunities to engage in charmingly witty motte-and-bailey discourse; for prophesying that “quantum supremacy is near” or alternatively, “quantum supremacy is a mirage”; for arguing that “Gil Kalai is completely wrong” or alternatively, “Gil Kalai is entirely right”.

Such discourse too-easily devolves into “charm that does harm” — the phrase “charm that does harm” is from Arkady Plotnitsky’s foresighted essay “Derrida, Relativity, and the ‘Science Wars'” (*Postmodern Culture*, 1997).

As an active countermeasure against “charm that does harm”, I for one am hopeful that recent, top-quality quantum research relating to the universality (or not) of the Extended Church-Turing Thesis, will evoke the sober, reasoned, public, scientific discourse, that topics like the ECT absolutely require and eminently deserve.

Uhhh … discourse with perhaps with just enough charmingly witty and sardonic remarks, to provide grounds for shared hilarity, and evoke an appropriate shared humility, in the face of humanity’s many, immensely difficult, shared challenges.

]]>https://arxiv.org/abs/1810.03176

Do you have any thoughts as it relates to fault tolerant QC?

]]>Thanks for the notes!

]]>But it’s still extremely nice. What it is, is an unconditional separation between the class of relation problems solvable by constant-depth bounded-fanin quantum circuits, and the class of relation problems solvable by constant-depth bounded-fanin classical circuits. The relation problems considered are all easy to solve in classical polynomial time; the way they achieve their unconditional separation is to consider much, *much* weaker complexity classes (but weakening the classical and quantum models in the same way, namely to constant depth and bounded fanin).

In what’s now an *extremely* familiar pattern, this paper appeared on the arXiv a year and a half ago, and was a highlight of the QIP conference in January. So it’s already been assimilated by people in the field and there’s even been followup work. But then it gets officially published in *Science*, which leads to garbled popular articles about the brand-new earth-shattering breakthrough, and only by clicking the link to the paper do you learn that that breaking news and the thing that was really nice when you digested it last year are one and the same.