Complexity and Sensitivity of Noisy BosonSampling - Gil Kalai

626 views · Published 19 November 2014 · 1:03:47 · Indexed 8 November 2026

Channel: Hebrew University of Jerusalem · 2014 · Education

Watch on YouTube

Speaker: Professor Gil Kalai (Hebrew University of Jerusalem and Yale University)

Title: Complexity and Sensitivity of Noisy BosonSampling  ( joint work with Guy Kindler.)

HUJI CS Colloquium Series, Monday Nov. 10, 2014. 

Abstract: BosonSampling (Tishby and Troyansky 1996 and Aaronson and Arkhipov 2013) is the following computational task. The input is  an n by m complex matrix whose rows are unit vectors. The output is a sample from a probability distribution on all choices of n columns where the probability of such a choice is proportional to the square of the absolute value of the permanent of the associated n by n minor. 

This sampling task can be achieved by an (ideal) quantum computer. In fact, it can be realized by linear systems of n noninteracting photons which describe a restricted regime of quantum algorithms.The analogous algorithmic task with determinants instead of permanents is referred to as FermionSampling. While FermionSampling is in P, Aaronson and Arkhipov remarkably proved that a polynomial algorithm for BosonSampling implies that the polynomial hierarchy collapses to the third level. BosonSampling is proposed as a practical way to demonstrate, in the near future, the computational advantage of quantum computational devices! 

We study the computational complexity and sensitivity to noise of  the permanent-squared for random n by n Gaussian matrices X subject to an additive Gaussian noise. We show that asymptotically the correlation between the noisy and noiseless outcomes tends to zero when the noise level  is above 1/n.  We also show that when the amount of noise is constant the noisy value can be approximated efficiently on a classical computer and even by a constant-depth circuit of polynomial size. These results are used to derive similar consequences for the sensitivity to noise and computational complexity of noisy BosonSampling.

More from this channel