  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. With only a small number of
trials, we establish a confidence >99% that we are not sampling from a uniform
distribution or a classical distribution, and we demonstrate a unitary specific
witness that functions robustly for small amounts of data. Like the algorithmic
operations they endorse, our methods exploit the characteristics native to the
quantum system in question. Here we observe and make an application of a
"bosonic clouding" phenomenon, interesting in its own right, where photons are
found in local groups of modes superposed across two locations. Our broad
approach is likely to be practical for all architectures for quantum
technologies where formal verification methods for quantum algorithms are
either intractable or unknown.

Quantum Physics