Hi all,
Tomorrow Johannes Weidenfeller will tell us about his thesis project with Elisa on shallow quantum circuits: https://ethz.zoom.us/j/362994444. Here is the abstract:
In a recent breakthrough, Bravyi, Gosset and König (Science, 2018) proved an unconditional separation between the complexity classes of constant-depth quantum circuits QNC0, also called *shallow quantum circuits*, and their classical counterparts NC0. This result has since then been extended to a number of different computational problems. In this talk, we introduce so-called *higher-dimensional generalised GHZ states*, which are multipartite entangled states in a superposition of pure GHZ-like states, and explore their non-local properties. We further discuss the main ideas behind proving a separation in the setting of *arithmetic problems*, which generalise the *Parity Halving problem*, previously introduced by Watts, Kothari, Schaeffer and Tal (STOC 2019).
“Quantum advantage with shallow circuits” (Sergey Bravyi, David Gosset, and Robert König): https://arxiv.org/abs/1704.00690 "Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits” (Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal): https://arxiv.org/abs/1906.08890
Best,
-joe