10:45
11:45
In this talk, we will explore the role played by coherence in reaching quantum computational advantage. We introduce path coherence, a measure of coherent paths interferences and derive a simple classical algorithm for estimating quantum transition amplitudes the complexity of which scales exponentially with path coherence. This allows us to describe a wide class of circuits for which probability estimation is tractable classically and to identity a computational complexity transition from ⊕L to BQP.
Room 178