On the experimental verification of quantum complexity in linear optics

Understand

The first quantum technologies to solve computational problems that are beyond the capabilities of classical computers are likely to be devices that exploit characteristics inherent to a particular physical system, to tackle a bespoke problem suited to those characteristics.

• Evidence implies that the detection of ensembles of photons, which have propagated through a linear optical circuit, is equivalent to sampling from a probability distribution that is intractable to classical simulation.
• However, it is probable that the complexity of this type of sampling problem means that its solution is classically unverifiable within a feasible number of trials, and the task of establishing correct operation becomes one of gathering sufficiently convincing circumstantial evidence.
• Here, we develop scalable methods to experimentally establish correct operation for this class of sampling algorithm, which we implement with two different types of optical circuits for 3, 4, and 5 photons, on Hilbert spaces of up to 50,000 dimensions.