Alex Arkhipov: Quantum Computation with Identical Bosons

Abstract: A central goal of quantum complexity theory is to prove the computational advantage of quantum mechanics over classical. This talk will discuss such evidence for linear optical systems. In the BosonSampling model, developed with Scott Aaronson, a fixed number of identical photons are produced in different modes, pass through a network of beamsplitters and phaseshifters, and are measured in number for each output mode. We argue that even this limited system forbids an efficient classical simulation.

 

We discuss obstacles to demonstrating this quantum advantage hands-on with a physical device. Despite the accumulating impact of imprecision, we show the outcome remains accurate if each optical component is accurate to a certain tolerance. A simplistic demonstration of rigging the device towards a single outcome is easily spotted by an adversary looking to forge the result. But, correlations between the network parameters and output probabilities can be used as a sanity check. Moreover, statistics of linear combinations of output counts can be verified classically.

 

Advisor: Scott Aaronson

 

Thesis readers: Aram Harrow (Physics), Ryan Williams (EECS)