Southwest Quantum Information and Technology

Adaptive measurement-based quantum computation of classical Boolean functions: Exponential reductions in space-time resources

Presenting Author: Austin Daniel, University of New Mexico CQuIC
Contributing Author(s): Akimasa Miyake

We study the resource costs required to compute a variety of nonlinear Boolean functions via adaptive measurement-based quantum computation (MBQC) with a mod-2 linear classical side-processor, better known as \(l2\)-MBQC. We give an explict example of how constant-depth quantum circuits with the aid of mid-circuit measurements can compute the so-called mod-3 function on \(n\)-bits---and more generally mod-\(p\) functions for any prime \(p\)---using an \(O(n)\) qubit resource state and a constant number of rounds of interaction with the classical side-processor. In constrast, we show that the same task requires \(\Omega(2^n)\) qubits in the nonadaptive setting. Our results also give an oracular separation between the power of constant-depth quantum circuits and constant-depth classical circuits with unbounded fan-in NAND and mod-\(p\) gates.

(Session 3 : Thursday from 2:15 pm - 2:45 pm)