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
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
-
1:22:14
פרופ' אברהם הוכברג- הגן H-19, תקווה חדשה לחולי סרטן
-
1:22:54
מר משה נגבי- על היעדר האחריותיות בדמוקרטיה הישראלית
-
1:30:58
פרופ' ששון צחייק- מדע הכימיה
-
1:13:59
פרופ' אבנר דה שליט- על מורשת, מקום ותכנון בר קיימא
-
1:17:03
פרופ' ארי לאור- עדויות לקיומם של חורים שחורים ענקיים
-
1:07:28
פרופ' ניר שביב- על קרינה קוסמית ואקלים כדור-הארץ
-
1:21:11
ד"ר דני צ'רנוב- השפעת שינויי האקלים על שונית האלמוגים
-
1:06:27
ד"ר ארז ריבק - חידוד הדמות בשמים ובעיניים