Verifying Quantum Complexity in Linear Optical Experiments

We develop techniques to verify the computational complexity of a class of analogue quantum computers known as boson samplers. We demonstrate these techniques with up to 5 photons in two different types of integrated linear optical circuit, observing Hilbert spaces of up to 50,000 dimensions.