Abstract:
We present a computational problem with the following properties: (i) Every instance can be solved with near-certainty by a constant-depth quantum circuit using only nearest-neighbor gates in 3D even when its implementation is corrupted by noise. (ii) Any constant-depth classical circuit composed of unbounded fan-in AND, OR, as well as NOT gates, i.e., an AC0-circuit, of size smaller than a certain subexponential, fails to solve a uniformly random instance with probability greater than a certain constant. Such an advantage against unbounded fan-in classical circuits was previously only known in the noise-free case or without locality constraints. We overcome these limitations, proposing a quantum advantage demonstration amenable to experimental realizations. Subexponential circuit-complexity lower bounds have traditionally been referred to as exponential. We use the term colossal since our fault-tolerant 3D architecture resembles a certain Roman monument.
This is joint work with Xavier Coiteux-Roy and Robert Koenig, arXiv:2312.09209.
About EQSI
European Quantum Software Institute (EQSI) is an initiative for quantum software research and education in Europe.
The initiative unites 6 leading research institutions to conduct joint research projects and educational and outreach activities, in collaboration with providers of quantum computing infrastructure and industry partners interested in developing quantum algorithms.
EQSI activities include annual workshops and monthly online seminars.
Subscribe to the EQSI mailing list to receive the announcements of the EQSI Colloquium, as well as other news and events from EQSI: https://mlists.ist.utl.pt/mailman/listinfo/groups.pqi.eqsi-info