Skip navigation

상단메뉴

글로벌메뉴

좌측메뉴

학술행사

검색

Seminars

Seminar
FIELD Comp.Sciences:Information Science
DATE November 09 (Tue), 2021
TIME 10:00-12:00
PLACE 7323
SPEAKER 오창훈
HOST Lim, Youngrong
INSTITUTE University of Chicago
TITLE [GS_CS_QI] Classical simulation of bosons sampling using dynamical programming
ABSTRACT We study the computational complexity of boson sampling as linear-optical circuits' depth. We propose a classical algorithm for boson sampling using dynamical programming based on graph structure of a given circuit and characterize its computational complexity for different circuit depths. Notably, for linear-optical circuits composed of local random beam-splitters, we find a sharp transition of its complexity as a circuit's depth increases: polynomial, sub-exponential, and exponential time cost. In addition, we show by numerically implementing the CHOG validation test of Gaussian boson sampling that our algorithm can spoof a small size version of the recent Gaussian boson sampling experiments with the same structure. Thus, spatial locality of a linear-optical circuit allows a classical sampler to spoof the test and it is crucial to implement a global Haar-random circuit to rigorously demonstrate quantum advantages.
FILE  
  • list

date

~