In this talk, we introduce the magic pentagram problem (MPP), and sketch the proof showing that the MPP can be solved by QNC^0 circuit, but not by any NC^0 circuit.
Here, QNC^0/NC^0 is the classe of polynomial-size and constant-depth quantum/classical circuits with bounded fan-in gates (unbounded fan-out gates are allowed in NC^0 circuits).
Therefore, the MPP is an example showing a quantum advantage with shallow circuits.
This is a joint work with Haesol Han, Jeonghyeon Shin, Minjin Choi and Byung Chan Kim.

(줌 주소: 개별공지)