  Several classes of quantum circuits have been shown to provide a quantum
computational advantage under certain assumptions. The study of ever more
restricted classes of quantum circuits capable of quantum advantage is
motivated by possible simplifications in experimental demonstrations. In this
paper we study the efficiency of measurement-based quantum computation with a
completely flat temporal ordering of measurements. We propose new constructions
for the deterministic computation of arbitrary Boolean functions, drawing on
correlations present in multi-qubit Greenberger, Horne, and Zeilinger (GHZ)
states. We characterize the necessary measurement complexity using the Clifford
hierarchy, and also generally decrease the number of qubits needed with respect
to previous constructions. In particular, we identify a family of Boolean
functions for which deterministic evaluation using non-adaptive MBQC is
possible, featuring quantum advantage in width and number of gates with respect
to classical circuits.
