To view this live seminar via Zoom, visit:
https://umass-amherst.zoom.us/j/440256942
Abstract: I will present a 2019 paper by Ran Raz and Avishay Tal that proves the existence of an oracle that separates BQP--the class of problems efficiently solvable on a quantum computer--from the polynomial hierarchy. This paper constructs a probability distribution that locally looks uniform but has global correlations. They give a quantum algorithm that can distinguish between samples drawn from this distribution and those from the uniform distribution, and they show that no PH machine can do the same. This implies the existence of an oracle that separates BQP and PH. I will go over the quantum computing basics necessary to understand their quantum algorithm.