# Quantum advantage in temporally flat measurement-based quantum computation

Michael de Oliveira<EMAIL_ADDRESS>University of Minho, Department
of Computer Science, Braga, Portugal  INESC TEC, Braga, Portugal
International Iberian Nanotechnology Laboratory (INL) Av. Mestre Jose Veiga,
4715-330, Braga, Portugal  Luís Soares Barbosa  University of Minho,
Department of Computer Science, Braga, Portugal  INESC TEC, Braga, Portugal
International Iberian Nanotechnology Laboratory (INL) Av. Mestre Jose Veiga,
4715-330, Braga, Portugal  Ernesto F. Galvão  International Iberian
Nanotechnology Laboratory (INL) Av. Mestre Jose Veiga, 4715-330, Braga,
Portugal  Instituto de Física, Universidade Federal Fluminense Av. Gal. Milton
Tavares de Souza s/n, Niterói, RJ, 24210-340, Brazil

###### Abstract

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.

##  1 Introduction

One of the primary motivations for studying quantum information and
computation, along with the search for practical advantage, is to clarify the
longstanding question of what generates the classical-quantum separation in
information processing power [1]. Phenomena such as non-locality and
contextuality have been identified as possible sources of quantum
computational advantage [2, 3, 4], among others [5, 6, 7]. It appears that no
single phenomenon can be associated with all forms of quantum information
processing advantage, so it is important to identify and study quantum
advantage in different models and regimes.

In this pursuit, the measurement-based quantum computation (MBQC) model, first
presented by Raussendorf and Briegel in [8] as a sequence of adaptively
selected single-qubit measurements on a highly entangled quantum state, is a
natural setting to study quantum-to-classical separations. In particular, it
allows for demonstrations that specific structures of non-local correlations
between qubits are necessary for universal quantum computation [9].
Nevertheless, a temporal structure for the measurements is simultaneously
imposed to achieve universality [10, 11, 12]. This means statically selected
measurements are not computationally expressive enough to implement arbitrary
quantum algorithms, even with access to highly correlated resource states. A
judicious choice of side classical computation and control is essential for
universality in the MBQC model.

The importance of time structure in measurement-based quantum computation is
not fully understood. For instance, it is conjectured that classical computers
cannot efficiently simulate instantaneous quantum polynomial (IQP) circuits
[13], despite the fact that these circuits of commuting gates have no temporal
structure, and can be implemented with no adaptivity in MBQC [14]. These
results have motivated the study of temporally flat computation for
demonstrations of quantum advantage [15, 16, 17]. Despite having an output
distribution that is hard to simulate classically, no practical application
for IQP circuits has been found. Even for quantum circuits with temporal
order, constant improvements in classical simulation techniques contribute to
enlarging the classes of circuits that are classically efficiently simulable.

This paper studies non-adaptive MBQC computations which have no temporal
structure for the measurement operators. In this setting, there exist circuits
with quantum advantage, defined as those that cannot be efficiently simulated
classically [18, 19]. Here we will be interested in investigating how this
model can be applied to decision problems. Previously, in references [10, 20,
21, 22, 23] this model was studied with the goal of evaluating Boolean
functions. In the next section we briefly describe the main results we obtain
here, relating to the use of non-adaptive MBQC for the evaluation of Boolean
functions.

###  1.1 Our results

For temporally unstructured MBQC computations, we propose new constructions
that synthesize quantum circuits for the deterministic evaluation of Boolean
functions. These constructions reduce the number of qubits required in the GHZ
resource states used, especially for the case of symmetric Boolean functions.
We also improve the circuit synthesis process, removing an exponential scaling
of previous constructions on the degree of the Boolean function [21, 22].
Regarding the complexity of the single-qubit measurements, we also
characterize the maximum level of the Clifford hierarchy required for
deterministic Boolean function evaluation.

######  Theorem 1.

(Informal) Any Boolean function $f$ can be evaluated deterministically in the
non-adaptive MBQC model using measurement operators of the
$\mathsf{deg}(f)$-level of the Clifford hierarchy.

This result describes a measure of complexity for the evaluation of Boolean
functions in the model while defining the type of measurement operators
necessary to maximally violate a multipartite Bell inequality with dichotomic
observables and outcomes [20]. Furthermore, this strengthens the idea that the
degree of a Boolean function that can be computed with certain given quantum
resources introduces a hierarchy for quantum correlations, connecting measures
of computational complexity with measures of non-classicality beyond the
binary characterization, as suggested in [22].

We translate the abstract description of the quantum circuits obtained from
the constructions into specific circuits based on a fixed gate set. Also, we
characterize how the solutions produced by the constructions are related to
various circuit complexity measures. This enabled us to prove a quantum over
classical separation on the circuit level for the computations of a specific
class of Boolean functions with degree two.

######  Theorem 2.

(Informal) Any classical circuit with unary and binary Boolean operators with
single fan out computes symmetric Boolean functions $f$ with
$\mathsf{deg}(f)=2$ with $\Theta(n*\log_{2}(n))$ gates and circuit width. In
contrast, realizations of the non-adaptive MBQC model compute these functions
with $\Theta(n)$ gates and circuit width.

The proof compares these quantum circuits with the length of the classical
Boolean formulas, which describe classical circuits without a memory. The
comparison is indeed very strong in the sense that the quantum circuit also
does not use any memory (see Figure 1 for a pictorial representation of this
subclass of circuits). Interestingly, this result also has an interpretation
in terms of Bell inequalities. In particular, the evaluation of the specific
family of Boolean functions for which we identify quantum advantage
corresponds to maximal violations of generalized Svetlichny inequalities [24].
Therefore, a maximal violation of these inequalities starting from a specific
size implies a corresponding circuit separation 111Recall that the separation
in Theorem 2 is proven to hold asymptotically. Therefore, there is a minimum
problem size above which all the quantum circuits are more efficient than the
best classical circuits.. More precisely, any quantum state that can be
prepared and measured with linearly bounded quantum circuits that violate
these inequalities maximally implies a corresponding circuit separation.

Figure 1: Illustration of the circuit classes for which we prove a separation
in Theorem 2. For the classical class, the input can be copied only in the
copy section, which precedes the logical operator section. For the quantum
circuits, the same occurs. This prevents the circuits from employing the copy
operation at any point in time, which would replicate the effect of memory in
the circuits.

Finally, we extend the previous analysis to higher degree symmetric Boolean
functions, and conjecture that these have no advantage with respect to
classical circuits.

######  Conjecture 1.

(Informal) Symmetric Boolean functions $f$ with $\mathsf{deg}(f)\geq 3$
evaluated within the non-adaptive MBQC model do not entail circuits with
better scalings than classical circuits with unary and binary Boolean
operators with single fan out.

This conjecture is based on several independent results. The first is the
exponential lower bound proven in [20] for the general $\mathsf{AND}$ function
which is symmetric and has an instance for any possible degree. Then, on the
same level, we conjecture and provide numerical support that symmetric Boolean
functions require quantum states whose size scales at a greater rate than the
corresponding number of classical bits required in the optimal classical
circuits for the same computations. Furthermore, we show that with the
Clifford$+$T gate set the necessary measurement operators cannot be
synthesized exactly, and always need to be approximated. In contrast, there is
no difficulty in computing the same function deterministically with classical
circuits. This illustrates some of the restrictions resulting from the imposed
flat temporal order.

###  1.2 Related work

Non-local games.  Computations within the non-adaptive MBQC model were proven
to have a one-to-one correspondence to multi-party Bell inequalities with
dichotomic observables and outcomes [20]. Therefore, the classical and the
quantum bounds determined in previous works for this type of Bell inequalities
immediately translate to computational efficiencies of the respective
functions in the non-adaptive MBQC model [25]. For the quantum bounds, we
obtain the maximal efficiency that can be obtained from quantum resources to
compute the respective Boolean functions, and equivalently, the same happens
for classical bounds. From this relation, we can compare our work with a large
spectrum of results and techniques on the optimal strategies for non-local
games [25, 26, 27].

For instance, in [28, 29], the authors consider arbitrary symmetric non-local
games, which correspond to the symmetric Boolean functions we study here.
Their results complement our own in the probabilistic setting. We determined
the size of the quantum resource to obtain deterministic computations. At the
same time, they considered the efficiency obtained if a quantum resource with
a size equal to the input string is evaluated, with the additional comparison
to a classical resource of the same size. Their main results show a mean
advantage of $\sqrt{\log(n)}$ between the use of classical or quantum
resources. Moreover, the magnitude of this separation appears to be similar to
the separation demonstrated in Theorem 2 due to the $\log(n)$ term. Still, it
is not comparable to our results, given that they consider the classical limit
based on measurement-based computations with classical resources, while we
allow for arbitrary classical circuits without memory.

Furthermore, in the study of communication complexity, the non-local boxes
usually employed can be interpreted as non-adaptive MBQC computations [30].
This observation relates this model to results obtained in the study of non-
local boxes. The study of this relationship is two-fold. First, in references
[31, 32, 33], the hypothesis of axiomatizing quantum mechanics with
information-theoretical principles intends to limit the quantum correlations
allowed with these principles. Therefore, the resulting limits to the non-
local boxes’ efficiencies also relate to the maximal efficiency of the
corresponding non-adaptive MBQC computations [34, 35, 36]. On the other hand,
non-local games defined on a non-binary set of observables and outcomes can be
interpreted as a generalization of the non-adaptive MBQC model to qudits ,
together with the respective classical linear side processors [37, 38].

Quantum circuits. A breakthrough result by Bravyi, Gosset, and König [39]
shows that a class of relation problems can be solved in constant depth with a
quantum circuit, while requiring logarithmic depth in a classical computer
[39]. This result has been extended in various manners [40, 41]. In [42], the
analysis is extended from worst-case difficulty to average-case difficulty. In
[43], the probability with which a classical circuit correctly computes the
relation problem was exponentially reduced with the size of the input string.
Dealing with the same separation, the works of [44, 45] have made it more
robust against noise.

The first connection of our work to these results is that the proof relies on
non-local games that are fundamental to the separation. These are naturally
described with the non-adaptive MBQC model, which could be used to extend the
relation problems with different non-local games, as done in [43].
Nevertheless, a direct connection to these circuit separations can be made
with the work of [46]. In this paper, the authors present the parity halving
problem $PHP:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{n}$, defined for all
$x\in\\{0,1\\}^{n}$ with even Hamming weight and $|y|\in\\{0,1\\}^{n}$ as

$|x|/2\equiv|y|\ \mod\ 2\ ,$ (1)

with $|x|$ and $|y|$ describing the Hamming weight of the respective
bitstrings. The authors prove that this relation problem can be computed in
$QNC/poly$ while not being computable with any circuit of the $AC^{0}$ class.
Furthermore, this is precisely a sub-problem of the relation problem built in
the quantum circuit that we use to prove a quantum advantage for a decision
problem. In particular, the Hamming weight of the input string and the output
string from the measurement layer performed on the GHZ state describes the
full parity halving problem $FPHP:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{n+1}$,
defined for all $x\in\\{0,1\\}^{n}$ and $|y|\in\\{0,1\\}^{n}$ as

$\begin{cases}|x|/2\equiv|y|\ mod\ 2,\ \ |x|\mod\ 2=0\\\ |x-1|/2\equiv|y|\
mod\ 2,\ \ |x|\mod\ 2=1\end{cases}\ .$ (2)

We translate this into a decision problem by taking the parity of the output
string $|y|$ of this relation (Figure 2). Interestingly, using a sub-circuit
with a quantum advantage respective to the local relation problem does not
imply an advantage for the equivalent decision problem. Only the inverse
implication would be unconditionally true.

Another related work concerning shallow quantum circuits is that of [47]. Here
constant-depth quantum circuits that solve a sampling problem related to the
class of symmetric Boolean functions we have explored are proposed. In
addition, an advantage to the best constant depth circuits has been identified
for these problems.

x_1 & [5, nwires=5]FPHP y_1 [wires=5][1.7cm]⨁_circuit
x_2 y_2
⋮ ⋮ f(x)
x_n y_n
y_n+1  Figure 2: Circuit for evaluating the symmetric Boolean functions with
degree two built from the FPHP relation by the composition of a classical
circuit that computes the parity.

From another perspective, the quantum advantage for the decision problem we
identified is described in terms of the number of gates and the width of the
circuits. Various related results have been obtained for circuit width. For
instance, in [48], the authors prove a quantum advantage using the same
symmetric Boolean function of degree two that we adress here. The advantage
regarding the equivalent classical model is proven by fixing a width size for
the computational space and showing that these computations can be computed
with greater efficiency in an actual quantum device, IBM’s quantum computer.
Therefore, our result can be interpreted as the computation of the same
function without any width restriction but with a temporal restriction on the
time ordering for the quantum circuit (all the measurements have to commute).

Finally, quantum width advantages for a class of symmetric Boolean functions
in the setting of branching programs were demonstrated in [49]. In particular,
these functions separate optimally quantum and classical branching programs
and are generalizations of the symmetric Boolean function we used in the proof
of Theorem 2.

###  1.3 Document organization

The remainder of the document is organized as follows. Section 2 provides the
background for the non-adaptive measurement-based quantum computation model.
Section 3 introduces our new constructions to select the measurement
instructions for Boolean function evaluation. Subsequently, Section 4 analyses
theoretical resource bounds for the model, providing the technical proof of
Theorem 1 and support for Conjecture 1. Section 5 translates the model into
realizable computations in the form of circuits, providing the technical proof
of Theorem 2 and additional support for Conjecture 1. Finally, section 6
concludes with a brief discussion of the results.

##  2 Background

###  2.1 The non-adaptive measurement-based quantum computation model

The definition of the non-adaptive MBQC (NMQC⊕) model builds upon that of the
MBQC model [20]. In general terms, the MBQC model is a universal quantum
computing model which performs computations by a sequence of measurements on a
highly entangled quantum state [8, 9, 50]. The measurement operators applied
during the computation must be selected adaptively, depending on previous
measurement outcomes. The NMQC⊕ model differs from the general MBQC in that it
does not allow for measurement adaptivity. Therefore, it cannot select
subsequent measurement operators assuming knowledge about the outcome of
previous measurements. Without the capacity to adapt, the order of single-
qubit measurements performed on the resource state is not defined, and the
temporal structure becomes flat [13, 51].

Furthermore, in the usual MBQC model [8, 9], each measurement is chosen using
a limited classical side computer capable only of linear computations. Thus,
in NMQC⊕ this linear side computer can immediately determine all the
measurement bases required for the computation based on the input string.
Then, the selected measurement operators are applied to the resource,
producing a set of outcome values. These outcomes are fed again into a linear
side computer, which delivers the final output of the entire computational
process. A detailed description of the model can be given as a procedure
consisting of the following three main stages:

##### Stage 1.

A classical input string $x\in\\{0,1\\}^{n}$ is pre-processed by a linear side
computer generating a binary output $s_{i}\in\\{0,1\\}$ for each qubit $i$ of
the resource state, with $k$ qubits. Without loss of generality, this
computation for each qubit is given by the general linear expression,

$s_{i}=L_{i}(x)=a_{i_{0}}\oplus\bigoplus_{j\in S_{i}}\big{(}a_{i_{j}}\oplus
x_{j}\big{)}$ (3)

for all $i\in\\{0,1,...,k-1\\}$, with $a_{i_{j}}\in\\{0,1\\}$, and $\
S_{i}\subseteq[n]$.

##### Stage 2.

To each bit-value of $s_{i}\in\\{0,1\\}$ we associate a single-qubit
measurement operator on the equator of the Bloch sphere as,

$M_{i}(s_{i})=\cos(\theta_{i}+\phi_{i}*s_{i})\sigma_{x}+\sin(\theta_{i}+\phi_{i}*s_{i})\sigma_{y}$
(4)

for all $i\in\\{0,1,...,k-1\\}$, with $\sigma_{x}$ and $\sigma_{y}$ standing
for the Pauli $X$ and $Y$ operator, respectively, and angles $\theta_{i}$ and
$\phi_{i}$ defining the specific measurement operators. In the measurement of,

$M_{0}(s_{0})\otimes M_{1}(s_{1})\otimes...\otimes
M_{i}(s_{i})\otimes...\otimes M_{k-1}(s_{k-1})\ ,$ (5)

on resource state $\ket{\Psi_{k}}$, each one of these measurements yields a
binary output $m_{i}\in\\{-1,1\\}$, with an associated probability for all
$i\in\\{0,1,...,k-1\\}$. The result of this process is a string $x_{m}$ of
symbols $\pm 1$ with length $k$ composed of eigenvalues of the measurement
operators $\otimes_{i=0}^{k-1}M_{i}(s_{i})$,

$x_{m}=m_{0},m_{1},\ldots,m_{i},\ldots,m_{k-1}\ \ \text{with}\
m_{i}\in\\{-1,1\\}\ .$ (6)

##### Stage 3.

In the final stage, the auxiliary linear side processor is employed again to
compute the binary output based on the previously obtained string $x_{m}$,

$L_{f}(x_{m})=a_{0}\oplus\bigoplus_{i=1}^{k}\big{(}a_{i}\oplus
g(m_{i})\big{)}$ (7)

where $g(x)=\dfrac{1-x}{2}$ acts as a renormalization function to map the $\pm
1$ outcomes to the more usual bit values $0$ and $1$. The complete process is
illustrated in Figure 3 (a), summarizing the different stages of the NMQC⊕
model.

Figure 3: (a) The complete NMQC⊕ procedure. The input string
$x\in\\{0,1\\}^{n}$ is shared with each linear function of the pre-processing
stage. Then the binary values $s_{i}$ are forwarded to the measurement
process, determining a specific measurement operator on all qubits. In the
end, the measurement results are fed into a linear function to compute the
result of the NMQC⊕ computation. (b) Representation of a digital circuit
composed of NAND gates that are implemented using individual NMQC⊕
computations.

###  2.2 Measurement assignments

The lack of adaptivity prevents NMQC⊕ from being a universal model for quantum
computation, as MBQC is. Nevertheless, Anders and Browne demonstrated that it
could evaluate the NAND gate deterministically with a 3-qubit GHZ state and
measurements of its stabilizer group. This particular gate is special because
it describes a complete gate set for a universal classical computer.
Consequently, any Boolean function can be computed by composing layers of
NMQC⊕ evaluations (Figure 3 (b)). However, by composing different NMQC⊕
computations, the whole computational process becomes adaptive. This
implication can be easily understood as the result of a specific NAND gate
will define the measurement operators of the NAND gates to its outputs are fed
into. Therefore, we will focus mainly on the computation capabilities of the
NMQC⊕ model without any compositions.

Subsequent to the work of Anders and Browne, which introduced the main ideas,
the first detailed description of the NMQC⊕ model was presented by Hoban et
al. in [20]. This work examines the set of instructions necessary for each
stage of the model, the measurement assignments, in order to deterministically
evaluate Boolean functions. Formally,

######  Definition 1.

(Measurement assignment). A measurement assignment for a NMQC⊕ computation is
composed by a set of linear functions $L_{i}$, a set of dichotomic measurement
operators $M_{i}(s_{i})$, for all $i\in\\{0,1,...,k-1\\}$, a final linear
function $L_{f}$ and a resource state $\Psi_{k}$, which takes the form of a
$k$-qubit quantum state.

In the same work, the authors proved that there is a measurement assignment
for any Boolean function, $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$, which
deterministically evaluates the function in the NMQC⊕ model. These measurement
assignments require general GHZ states as a resource state [52, 53]. Moreover,
such highly entangled quantum states were proven to be the most efficient
resource state for these computations, concerning the number of required
qubits [54, 20], as stated in the following theorem.

######  Theorem 3.

[20] In NMQC⊕ with quantum resources, any Boolean function $f(x)$, on an
arbitrary n-bit string $x$, can be computed with unit probability. This can be
achieved with the resource state
$\frac{1}{\sqrt{2}}\big{(}\ket{0}^{\otimes(2^{n}-1)}+\ket{1}^{\otimes(2^{n}-1)}\big{)}$
i.e. a $(2^{n}-1)$ qubit generalised GHZ state.

This result proves that classical universality can be achieved within the
NMQC⊕ model, without the need to compose various layers of NMQC⊕ computations.
Furthermore, it motivates the following research question

"What are the measurement assignments for an arbitrary Boolean function?"

Hoban et al. state that their proof for Theorem 3 also provides a constructive
method to discover valid measurement assignments. We argue that this process
is computationally too expensive, as it searches over all possible
combinations of linear functions for the pre-processing stage and over a
continuum for all the angles of the measurement stage. This assertion will be
supported by the complexity analysis of the constructions proposed in [21,
22], and which are much more computationally efficient than the original
proposal in [20].

In the remainder of this section, we will review two different constructions
that can be used to derive specific measurement assignments for a Boolean
function. The two methods were introduced in [21], while the second
construction was reintroduced independently in [22].

##### Construction 1: The Fourier representation ($\mathcal{FR}$) ([21])

The first construction merges two ideas to derive a method that yields a
measurement assignment for any Boolean function,
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$. It starts by verifying that the
expected value of a measurement operator composed of single-qubit measurements
on a general GHZ state, $\Psi_{GHZ}$, can be described with a cosine function,

$\displaystyle\bra{\Psi_{GHZ}^{k}}\otimes_{i=1}^{k}M_{i}(s_{i})\ket{\Psi_{GHZ}^{k}}=\cos\big{(}\sum_{i=1}^{k}\theta_{i}+\phi_{i}s_{i}\big{)}=\cos\big{(}\underbrace{\sum_{i=1}^{k}\theta_{i}+\phi_{i}L_{i}(x)}_{\mathsf{poly_{f}(x)}}\big{)}\
,$ (8)

whose assignment in a multi-linear polynomial,
$\mathsf{poly_{f}}:\\{0,1\\}^{n}\rightarrow\pi(\mathbb{R})$ [54].

######  Definition 2.

(Multi-linear polynomial). A multi-linear polynomial is a function
$\mathsf{poly}_{f}:\\{1,-1\\}^{n}\rightarrow\mathbb{C}$ that can be written
as,

$\mathsf{poly}_{f}(x)=\sum_{S\subseteq[n]}c_{S}^{\ast}\prod_{i\in S}x_{i}$ (9)

where each $c_{S}^{\ast}$ is a complex number.

This polynomial has real coefficients $\theta_{i}$ and $\phi_{i}$, which
relate to the parameters of the measurement operators from Equation (4), and
the binary variables $s_{i}$ related to the binary values from Equation (3)
that select the measurement bases. Thus, finding measurement assignments that
compute a specific Boolean function is equivalent to finding the corresponding
multi-linear polynomials. In particular, a valid polynomial has to map each
input $x\in\\{0,1\\}^{n}$ to a multiple of $\pi$ that is congruent modulo two
to the output of the Boolean function. Then, the total measurement operator
maps to the eigenvalue corresponding to the output of the Boolean function,
for all $f(x):\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ and $x\in\\{0,1\\}^{n}$,

$\displaystyle\bra{\Psi_{GHZ}^{k}}\otimes_{i=1}^{k}M_{i}(L_{i}(x))\ket{\Psi_{GHZ}^{k}}=\cos\big{(}\underbrace{\sum_{i=1}^{k}\theta_{i}+\phi_{i}L_{i}(x)}_{\mathsf{poly_{f}(x)}}\big{)}=(-1)^{f(x)}\
.$ (10)

The existence of such a multi-linear polynomial is guaranteed for every semi-
Boolean function ($f_{\ast}:\\{0,1\\}^{n}\rightarrow\mathbb{R}$) [55]. A
specific instance can be computed through the Walsh-Hadamard transform
$\mathcal{F}$, which is the Fourier transform on the Boolean group
$(\mathbb{Z}/2\mathbb{Z})^{n}$ 222A description for the Walsh-Hadamard
transform is given in Appendix A.1.. This transformation yields the Fourier
coefficients ($\widehat{f}(S)$) given an ordered vector with all the possible
input strings evaluated by the Boolean function,

$\frac{1}{2^{n}}\mathcal{F}^{T}\left(\begin{matrix}f(x_{0})\\\ f(x_{1})\\\
\vdots\\\ f(x_{2^{n}-1})\\\ f(x_{2^{n}})\\\
\end{matrix}\right)=\begin{bmatrix}\widehat{f}(S_{0})\\\ \widehat{f}(S_{1})\\\
\vdots\\\ \widehat{f}(S_{2^{n}-1})\\\ \widehat{f}(S_{2^{n}})\\\ \end{bmatrix}\
.$ (11)

These are the coefficients of the corresponding multi-linear polynomial,
$c_{S}^{\ast}=\widehat{f}(S)$. Therefore, for all
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ and $x\in\\{0,1\\}^{n}$,

$\mathsf{poly_{f}}(x)=\pi*\Big{(}\sum_{S\subseteq[n]}{\widehat{f}(S)*g^{-1}\Big{(}\bigoplus_{i\in
S}x_{i}\Big{)}}\Big{)}=\pi*f(x)\ .$ (12)

The multi-linear polynomial $\mathsf{poly_{f}}$ 333We will use throughout the
text the $\mathsf{poly}_{f}$ notation as the description of a multi-linear
polynomial that computes a function $f$. obtained through this process can be
used to construct a measurement assignment that computes the Boolean function
deterministically in the NMQC⊕ model. The resource state will be a general GHZ
state of $k$ qubits,

$\ket{\Psi_{GHZ}^{k}}=\dfrac{1}{\sqrt{2}}\big{(}\ket{0}^{\otimes
k}+\ket{1}^{\otimes k}\big{)}\ ,$ (13)

with $k$ standing for the sparsity of the multi-linear polynomial
$\mathsf{poly_{f}}$, defined as follows.

######  Definition 3.

(Sparsity). The sparsity of a multi-linear polynomial
$\mathsf{poly_{f}}:\\{0,1\\}^{n}\rightarrow\mathbb{R}$ is designated as the
number of non-zero Fourier coefficients,

$\mathsf{sparsity}(\mathsf{poly_{f}})=\mathsf{sparsity}\big{(}\mathcal{F}(f)\big{)}=\sum_{S\subseteq[n]\setminus[0]}\delta\big{(}\widehat{f}(S)\big{)},\
\ \delta(x)=\left\\{\begin{array}[]{ll}1&x\neq 0\\\ 0&otherwise\\\
\end{array}\right.\ ,$ (14)

which results from applying the Fourier transform $\mathcal{F}$ to the semi-
Boolean function, $f_{\ast}:\\{0,1\\}^{n}\rightarrow\mathbb{R}$, such that,
for all $x\in\\{0,1\\}$, $f_{\ast}(x)=\mathsf{poly}_{f_{\ast}}(x)$.

In the pre-processing stage (Stage 1), the linear Boolean functions which
select the measurement operators, are all the parity bases
($\bigoplus_{l\subseteq S}x_{l}$), corresponding to non-zero Fourier
coefficient ($\widehat{f}(S_{i})\neq 0$) of $\mathsf{poly_{f}}$,

$s_{i}=L_{i}(x)=\bigoplus_{l\subseteq S_{i}}x_{l}\ ,$ (15)

with $i\in\\{0,1,...,k-1\\}$. The angles of the measurement operators, from
Equation (4) in Stage 2, are built from the non-zero Fourier coefficients that
constructed the multi-linear polynomial resorting to Equation (12), such that,
for all $i\in\\{0,1,...,k-1\\}$,

$\theta_{i}=\dfrac{\pi}{k}*\sum_{S\subseteq[n]}\widehat{f}(S)\ .$ (16)

Notice that each $\theta_{i}$ always has the same value for all measurement
operators. Only the values of $\phi_{i}$ change, and these angles are defined
by the corresponding non-zero coefficients of the polynomial,

$\phi_{i}=-2\pi*\widehat{f}(S_{i})\ ,$ (17)

for all $i\in\\{0,1,...,k-1\\}$. Therefore, each non-zero Fourier coefficient
$\widehat{f}(S_{i})$ links a specific parity basis $L_{i}(x)=\bigoplus_{l\in
S_{i}}x_{l}$ to the corresponding measurement operator $M_{i}(s_{i})$, which
will be applied to one of the qubits of the resource state.

Finally, the linear Boolean function of the post-processing stage, Stage 3,
will be the linear sum of all the measurement outcomes ($m_{i}$),

$L_{f}(x_{m})=\bigoplus_{i=1}^{k}g(m_{i})\ ,$ (18)

for all Boolean functions, with a measurement assignment determined directly
by the equivalent multi-linear polynomial.

######  Example 1.

For the $\mathsf{AND}$ function with input strings of size two,
$\mathsf{AND}(x_{1},x_{2})=x_{1}*x_{2}$, the discrete Fourier transform
applied to the corresponding truth table computes the Fourier coefficients,

$\frac{1}{4}\begin{bmatrix}1&-1&\ \ 1&\ \ 1\\\ 1&\ \ 1&\ \ 1&-1\\\
1&-1&-1&-1\\\ 1&\ \ 1&-1&\ \ 1\\\ \end{bmatrix}*\begin{bmatrix}0\\\ 0\\\ 0\\\
1\\\ \end{bmatrix}=\begin{bmatrix}\ \ 1/4\\\ -1/4\\\ -1/4\\\ \ \ 1/4\\\
\end{bmatrix}\ .$ (19)

These are used to build the corresponding multi-linear polynomial resorting to
Equation (12),

$\mathsf{poly_{\mathsf{AND}}}(x)=\dfrac{1}{2}x_{1}+\dfrac{1}{2}x_{2}-\dfrac{1}{2}x_{1}\oplus
x_{2}\ .$ (20)

Then, the coefficients of the polynomial are used to create the measurement
assignment. In this case, the polynomial translates to a 3-qubit GHZ state,
$\ket{\Psi_{GHZ}^{3}}=1/\sqrt{2}\big{(}\ket{0}^{\otimes 3}+\ket{1}^{\otimes
3}\big{)}$, the linear functions

$L_{1}(x)=x_{1},\ L_{2}(x)=x_{2},\ and\ L_{3}(x)=x_{1}\oplus x_{2}\ ,$ (21)

and the corresponding measurement operators

$M_{1}(s_{1})=(\neg s_{1})\sigma_{x}+s_{1}\sigma_{y},\ M_{2}(s_{2})=(\neg
s_{2})\sigma_{x}+s_{2}\sigma_{y}\ and\ M_{3}(s_{3})=(\neg
s_{3})\sigma_{x}-s_{3}\sigma_{y}\ .$ (22)

Moreover, the $\mathsf{AND}$ function evaluated on all possible inputs, for
$x\in\\{0,1\\}^{2}$, in the NMQC⊕ model is equal to,

$\displaystyle\sigma_{x}\otimes\sigma_{x}\otimes\ \
\sigma_{x}\ket{\Psi_{GHZ}^{3}}=+\ket{\Psi_{GHZ}^{3}},\
\sigma_{x}\otimes\sigma_{y}\otimes-\sigma_{y}\ket{\Psi_{GHZ}^{3}}=+\ket{\Psi_{GHZ}^{3}}$
$\displaystyle\sigma_{y}\otimes\sigma_{x}\otimes-\sigma_{y}\ket{\Psi_{GHZ}^{3}}=+\ket{\Psi_{GHZ}^{3}},\
\sigma_{y}\otimes\sigma_{y}\otimes\ \
\sigma_{x}\ket{\Psi_{GHZ}^{3}}=-\ket{\Psi_{GHZ}^{3}}\ .$

Yielding the correct correspondence between the resulting eigenvalues and the
input strings, such that the final state is equal to
$(-1)^{\mathsf{AND}(x_{1},x_{2})}\ket{\Psi_{GHZ}^{3}}$.

This first construction, taken from [21] was presented with a detailed
translation from a valid multi-linear polynomial, for a specific Boolean
function, to a correct and deterministic measurement assignment. The
construction is characterized by a process that finds a multi-linear
polynomial, which in this case is the Walsh-Hadamard transform. The subsequent
constructions differ precisely in the process of finding an equivalent multi-
linear polynomial for the function. Thus, it is this process alone that
distinguishes between them, as the conversion from the multi-linear polynomial
to the measurement assignment will be always the same in every case.
Therefore, this process will not be repeated for the next constructions.

##### Construction 2: The extended Fourier representation ($\mathcal{EF}$)
([21, 22])

The second construction presented in [21], equivalent to the construction
introduced in [22], applies the discrete Fourier transform using a different
representation of the Boolean function, the Algebraic Normal Form (ANF).

######  Definition 4.

(Algebraic Normal Form). Any Boolean function
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ can be expressed uniquely as,

$f(x)=\bigoplus_{S\subseteq[n]}c_{S}\prod_{i\in S}x_{i}$ (23)

with $c_{S}\in\\{0,1\\}$.

Given the ANF of a Boolean function, this construction applies the Walsh-
Hadamard transform to each monomial ($\prod_{i\in S}x_{i}$). The resulting
multi-linear polynomials are summed to assemble a single multi-linear
polynomial representing the desired Boolean function. This process constructs
a correct multi-linear polynomial and the corresponding correct measurement
assignment due to the additivity property of the Walsh-Hadamard transform,

$\displaystyle\mathsf{poly_{f}}(x)$
$\displaystyle=\pi*\frac{1}{2^{n}}\mathcal{F}^{T}\bigg{(}\bigoplus_{S\subseteq[n]}c_{S}\prod_{i\in
S}x_{i}\bigg{)}$ (24)
$\displaystyle\equiv\pi*\sum_{S\subseteq[n]}c_{S}*\frac{1}{2^{n}}\mathcal{F}^{T}\bigg{(}\prod_{i\in
S}x_{i}\bigg{)}\ .$ (25)

In summary, we described two constructions that produce correct measurement
assignments for any Boolean function. The measurement assignments obtained
from them may differ. In particular, the sparsity of the multi-linear
polynomials is the main difference and one of the most significant properties
related to the efficiency of the NMQC⊕ model. Generally, the $\mathcal{EF}$
construction produces sparser polynomials than the $\mathcal{FR}$
construction. This separation can be exponentially large for some families of
Boolean functions 444We designate as families of Boolean functions a set of
Boolean functions with a precise description and a single instance for each
input string size. The general $\mathsf{AND}$ is an example of a family of
Boolean functions. [21, 56] . Thus, asymptotically the $\mathcal{EF}$
construction is identified as the construction that produces the most
efficient measurement assignments.

##  3 Evaluation of Boolean functions in the NMQC⊕ model

This section presents new constructions for the deterministic evaluation of
Boolean function in the NMQC$\oplus$ model. First, we introduce a new
construction for symmetric Boolean functions (SBF). Then, we demonstrate how
this new method can be integrated into another construction, yielding more
efficient NMQC$\oplus$ computations for arbitrary Boolean functions.

###  3.1 Symmetric Boolean functions

In Boolean functions analysis [55], the set of symmetric Boolean functions
i.e., those which are invariant under permutations of the input strings, was
studied for various properties and applications in computer science [57, 58,
59, 60]. As a result of this property, the ANF representation has the
following form, for all $x\in\\{0,1\\}^{n}$,

$f(x)=c_{0}\oplus c_{1}*C^{1}(x)\oplus c_{2}*C^{2}(x)\oplus
c_{3}*C^{3}(x)\oplus...\oplus
c_{n}*C^{n}(x)=\bigoplus_{k=0}^{n}c_{k}*C^{k}(x),$ (26)

where each $c_{k}\in\\{0,1\\}$ and the $C^{k}(x)$ terms represent the complete
symmetric functions (CSF), defined as

######  Definition 5.

(Complete symmetric function). The complete symmetric function (CSF) of
dimension $k$, $C^{k}(x):\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ is defined as the
sum, modulo 2, of all terms with degree equal to $k$, i.e.

$C^{k}(x)=\bigoplus_{i_{1}=1}^{n-k+1}x_{i_{1}}\Big{(}\bigoplus_{i_{2}=i_{1}+1}^{n-k+2}x_{i_{2}}\big{(}\
\ ...\ \ (\bigoplus_{i_{N}=i_{k-1}+1}^{n}x_{i_{N}})\big{)}\Big{)}\ .$ (27)

These functions are the building blocks used to generate the entire set of
symmetric Boolean functions [61], according to Equation (26). Therefore, a
construction that renders multi-linear polynomials for the CSF functions will
be universal for the set of symmetric Boolean functions.

##### Construction 3: CSF Representation ($\mathcal{CSF}$)

We propose a new construction that builds a multi-linear polynomial for an
arbitrary symmetric Boolean function. This construction takes advantage of the
decomposition established in the following lemma.

######  Lemma 1.

All complete symmetric functions $C^{k}$, for an arbitrary dimension $k$, can
be decomposed as the product of complete symmetric functions with a dimension
equal to power of two, i.e. for all $x\in\\{0,1\\}^{n}$

$C^{k}(x)=\bigwedge_{r\in R_{k}}C^{2^{r}}(x),$ (28)

with $R_{k}\subseteq[\left\lceil\log(k)\right\rceil]$, such that $\sum_{r\in
R_{k}}2^{r}=k$.

###### Proof.

See Appendix B. ∎

This decomposition demonstrates that a subset of CSFs is sufficient to build
the entire set of symmetric Boolean functions using the logical operators
$\mathsf{AND}$ ($\wedge$) and $\mathsf{XOR}$ ($\oplus$).

######  Proposition 1.

For any symmetric Boolean function $f$, there is an equivalent multi-linear
polynomial $\mathsf{poly}_{f}$ that can be built solely by composing multi-
linear polynomials from the subset of complete symmetric functions which have
a degree equal to a power of two, such that, for all $x\in\\{-1,1\\}^{n}$

$\mathsf{poly}_{f}(x)=\sum_{i=0}^{n}c_{i}\bigg{(}\prod_{r\in
R_{i}}\text{\large$\mathcal{GC}$}\Big{(}C^{2^{r}}(x)\Big{)}\bigg{)},$ (29)

with $R_{i}\subseteq[\left\lceil\log(i)\right\rceil]$, such that $\sum_{r\in
R_{i}}2^{r}=i$ and $\mathcal{GC}$ any general construction that generates
multi-linear polynomial for CSFs.

###### Proof.

The representation of SBF used in Equation (26) can be adapted to depend
uniquely on the CSF set with a degree equal to a power of two. Recall that
this translation is possible by Lemma 1. Then, any general construction
$\mathcal{GC}$ produces valid multi-linear polynomials for these two
representations,

$\displaystyle\mathsf{poly}_{f}(x)$
$\displaystyle=\text{\large$\mathcal{GC}$}\Big{(}\bigoplus_{i=0}^{n}c_{i}*C^{i}\Big{)}=\text{\large$\mathcal{GC}$}\Big{(}\bigoplus_{i=0}^{n}c_{i}\Big{(}\bigwedge_{r\in
R_{i}}C^{2^{r}}(x)\Big{)}\Big{)},$ (30)

with $R_{i}\subseteq[\left\lceil\log(i)\right\rceil]$, such that $\sum_{r\in
R_{i}}2^{r}=i$. Then, additivity can be used to push the application of the
general construction from the entire expression to the CSFs, given that the
linear sum $\oplus$ and the Real sum $+$ coincide for Boolean functions and
their multi-linear polynomials,

$\displaystyle\text{\large$\mathcal{GC}$}\Big{(}\bigoplus_{i=0}^{n}c_{i}\Big{(}\bigwedge_{r\in
R_{i}}C^{2^{r}}(x)\Big{)}\Big{)}\equiv\sum_{i=0}^{n}c_{i}*\text{\large$\mathcal{GC}$}\Big{(}\bigwedge_{r\in
R_{i}}C^{2^{r}}(x)\Big{)},$ (31)

Subsequently, we will resort to a lemma from [21] that defines the translation
from a conjunction operation on the function to the equivalent operation on
multi-linear polynomials. In particular, this lemma shows that, for a set of
Boolean function $f_{1},f_{2},...,f_{k}$ with common input variables
$x_{1},x_{2},...,x_{n}$, their composition by logical $\mathsf{AND}\ (\wedge)$
is equivalent to the product of the corresponding multi-linear polynomials,

$\bigwedge_{j=1}^{k}f_{j}(x)=\prod_{j=1}^{k}poly_{f_{j}}(x)\ \ .$ (32)

Consequently, a valid multi-linear polynomial can be built from the
polynomials with the CSFs of dimension equal to a power of two alone,

$\displaystyle\mathsf{poly}_{f}(x)\equiv\sum_{i=0}^{n}c_{i}*\text{\large$\mathcal{GC}$}\Big{(}\bigwedge_{r\in
R_{i}}C^{r}(x)\Big{)}\equiv\sum_{i=0}^{n}c_{i}\Big{(}\prod_{r\in
R_{i}}\text{\large$\mathcal{GC}$}\Big{(}C^{r}(x)\Big{)}\Big{)}.$ (33)

Finally, note that the construction used to build these polynomials has only
to be general in respect to any CSF with a degree equal to a power of two. ∎

The same decomposition holds for the equivalent multi-linear polynomials as
proven by in Proposition 1 using the multiplication and addition over the
Reals. Thus, it describes a valid method to generate a multi-linear polynomial
for an arbitrary symmetric Boolean function, defining our new construction.

This construction introduces modularity into the process of determining valid
multi-linear polynomials. Consequently, to build these mathematical objects
for symmetric functions, one can use any valid construction or known multi-
linear polynomials, which are equivalent to the CSF in the decomposition.
Therefore, the sparsest representations could be combined to attain the most
efficient NMQC⊕ computations. For instance, if one uses the $\mathcal{EF}$
construction from section 2.2 to compute multi-linear polynomials for
symmetric Boolean functions, the same polynomials would result from the
$\mathcal{CSF}$ construction. However, suppose one uses the multi-linear
polynomial presented in [20] for the $C^{2}$ function whenever it appears in
the decomposition. In that case, the final multi-linear polynomials will
always be sparser than any polynomials determined by either the $\mathcal{FR}$
or the $\mathcal{EF}$ constructions. This motivates the search for sparser
polynomials for this specific set of CSF, with a degree equal to a power of
two.

##### CSF polynomials

The $\mathcal{CSF}$ construction stresses the importance of determining
efficient representations for the subset of CSF on the entire set of symmetric
Boolean functions. Therefore, we identified a general form for the multi-
linear polynomials corresponding to the CSFs, which have a degree equal to a
power of two. We also proved that these are correct for any input size
considering the CSFs with a degree lower or equal to 64, as proved in the
lemma below. Therefore, to the authors’ knowledge, these are the most compact
multi-linear polynomial known for those CSFs.

######  Lemma 2.

For $k=2,4,8,16,32$ and $64$, the general form of multi-linear polynomials
represented by Equation (34) correctly computes the corresponding complete
symmetric function $C^{k}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ for all
$x\in\\{0,1\\}^{n}$, using a general GHZ state as a resource, with the NMQC⊕
model.

$\displaystyle\begin{split}\mathsf{poly}_{C^{k}}(x)=\frac{\pi}{2^{k-1}}\Bigg{(}\sum_{j=1}^{k/2}\binom{n-k/2-j}{k/2-j}(-1)^{j}\bigg{(}\sum_{S_{i}\subseteq[n],|S_{i}|=j}\bigoplus_{i\in
S_{i}}x_{i}-\sum_{S_{i}\subseteq[n],|S_{i}|=n-j+1}\bigoplus_{i\in S_{i}}x_{i}\
\bigg{)}\Bigg{)}\end{split}$ (34)

###### Proof.

See in Appendix C. ∎

######  Example 2.

The complete symmetric function of degree $4$ is defined for all
$x\in\\{0,1\\}^{n}$ as

$C^{4}(x)=\bigoplus_{i_{1}=1}^{n-3}x_{i_{1}}\bigg{(}\bigoplus_{i_{2}=i_{1}+1}^{n-2}x_{i_{2}}\bigg{(}\bigoplus_{i_{3}=i_{2}+1}^{n-1}x_{i_{3}}\bigg{(}\bigoplus_{i_{4}=i_{3}+1}^{n}x_{i_{4}}\bigg{)}\bigg{)}\bigg{)}\
,$ (35)

and the corresponding multi-linear polynomials have the following form

$\mathsf{poly}_{C^{4}}(x)=\frac{\pi}{8}\Big{(}\big{(}n-3\big{)}*\Big{(}\sum_{i=0}^{n}x_{i}-\bigoplus_{j=0}^{n}x_{j}\Big{)}+\sum_{i=0}^{n}\Big{(}\big{(}\bigoplus_{j=0}^{n}x_{j}\big{)}*x_{i}\Big{)}-\Big{(}\sum_{i=0}^{n}\sum_{j=i}^{n}x_{i}\oplus
x_{j}\Big{)}\Big{)}$ (36)

for all $x\in\\{0,1\\}^{n}$. Moreover, their sparsity is computed by

$\mathsf{sparsity}\big{(}\mathsf{poly}_{C^{4}}(x)\big{)}=\binom{n}{2}+2*\binom{n}{1}+1=\frac{n^{2}}{2}+\frac{3n}{2}+1=\mathcal{O}(n^{2})\
,$ (37)

Therefore, this reduces the number of qubits required for the NMQC$\oplus$
computation, compared to the previously result in [22] that scales
asymptotically with $\Theta(n^{3})$ .

The combination of the $\mathcal{CSF}$ construction with the CSF polynomials
translates to a new set of sparse multi-linear polynomials, which are
equivalent to symmetric Boolean functions. Consequently, these polynomials
reduce the number of qubits required for the deterministic evaluation of
symmetric Boolean functions in the NMQC⊕ model. As a concrete example, in
Appendix E we show that with this construction, the $C^{5}$ function taking
input strings of size $|n|=6$ demands a 43-qubit GHZ state, whereas the
previous best solution resorts to a 63-qubit GHZ state [22].

###  3.2 General Boolean functions

Could we some up with a procedure to find measurement assignments for general
Boolean functions, and not just for the symmetric ones? Ideally, this
procedure should find the sparsest multi-linear polynomials while requiring a
small computational effort. These conditions guarantee that the classical pre-
processing is not excessively time-consuming and that the NMQC⊕ computations
are as efficient as possible. In this subsection, we propose a new procedure
that reduces the cost of determining the measurement assignments, compared to
the $\mathcal{EF}$ construction from section 2.2. This reduction is achieved
without compromising the efficiency of the measurement assignments, given that
the generated multi-linear polynomials have equal or even smaller sparsities.

##### Construction 4: The Krawtchouk representation ($\mathcal{KR}$)

This solution uses the ANF of the Boolean functions to translate each monomial
($\prod_{i\in S}x_{i}$), to a multi-linear polynomial. However, in contrast to
previous techniques, this translation resorts to the symmetric properties of
these monomials. First, one can notice that all these terms are symmetric
Boolean functions if evaluated independently. Therefore, it is possible to
translate each of them to their simplified value vector [57] using a function
$\nu:(\\{0,1\\}^{n}\rightarrow\\{0,1\\})\rightarrow\\{0,1\\}^{n+1}$, defined
as

$\displaystyle\nu\bigg{(}\prod_{i\in S}x_{i}\bigg{)}=$
$\displaystyle\delta_{|S|}\bigg{(}\sum_{i\in S}x_{i}\bigg{)}$ (38)
$\displaystyle=$
$\displaystyle\big{(}\underbrace{0}_{0},\underbrace{0}_{1},\ldots,\underbrace{0}_{|S|-1},\underbrace{1}_{|S|}\big{)}\
,$ (39)

with $|S|\subseteq[n]$ and $\delta_{|S|}$ the Kronecker delta function at
$|S|$.

######  Definition 6.

(Simplified value vector). The simplified value vector of a symmetric Boolean
function ($v_{f}:\mathbb{N}\rightarrow\\{0,1\\}$) is defined as a function
mapping the Hamming weights of the input string to the corresponding Boolean
values

$v_{f}(|x|)=f(x),$ (40)

and recall that $|x|=\sum_{i=1}^{n}x_{i}$ stands for the Hamming weight of
$x$. Thus, the bit-string $v_{f}$ of length $n+1$ unambiguously determines the
symmetric function,

$v_{f}=\\{\underbrace{v_{0}}_{|x|=0},\ \underbrace{v_{1}}_{|x|=1},\
\underbrace{v_{2}}_{|x|=2},\ ...\ ,\ \underbrace{v_{n}}_{|x|=n}\\}\ .$ (41)

Given this compact representation for each monomial, one can translate such
vectors to a multi-linear polynomial using the Krawtchouk transform
($\mathcal{K}:\mathbb{Z}^{n}\rightarrow\mathbb{R}^{n}$), described in Appendix
A.2. This transform computes the $n+1$ different Fourier coefficients of an
arbitrary symmetric semi-Boolean function
$f_{\ast}:\\{0,1\\}^{n}\rightarrow\mathbb{R}$, such that,

$\frac{1}{2^{n}}\mathcal{K}^{T}\left(\begin{matrix}v_{f}(0)\\\ v_{f}(1)\\\
\vdots\\\ v_{f}(n)\\\ \end{matrix}\right)=\begin{bmatrix}\widehat{f}(|S|=0)\\\
\widehat{f}(|S|=1)\\\ \vdots\\\ \widehat{f}(|S|=n)\\\ \end{bmatrix}\ .$ (42)

In a subsequent step, the multi-linear polynomial equivalent to the monomials,
which are symmetric Boolean functions, will be constructed using the computed
Fourier coefficients as follows,

$\mathsf{poly}_{f}(x)=\pi*\Big{(}\sum_{i=0}^{n}\widehat{f}(|S|=i)*\sum_{S_{j}\subseteq[n],|S_{j}|=i}g^{-1}\Big{(}\bigoplus_{l\subseteq
S_{j}}x_{l}\Big{)}\Big{)}\ .$ (43)

In the end, each of the resulting polynomials is summed, or subtracted, from
the others to obtain the final multi-linear polynomial that represents the
queried function,

$\displaystyle\mathsf{poly_{f}}(x)$
$\displaystyle=\pi*\sum_{S\subseteq[n]}(-1)^{t_{S}}*c_{S}*\frac{1}{2^{n}}\mathcal{K}^{T}\bigg{(}\nu\bigg{(}\prod_{i\in
S}x_{i}\bigg{)}\bigg{)}$ (44)
$\displaystyle=\pm\mathsf{poly_{1}}(x)\pm\mathsf{poly_{2}}(x)\pm...\pm\mathsf{poly_{n}}(x)\equiv
f(x)\ .$ (45)

with $t_{S}\in\\{0,1\\}$.

Additionally, it will be necessary to prove that valid measurement assignments
are generated for the intended Boolean functions. To do so, we show that the
multi-linear polynomials obtained for each monomial using Equation (43) are
correct, and these can be summed or subtracted to build the final multi-linear
polynomial. These two proofs are sufficient for our purpose because these are
the only differences we have introduced with respect to the $\mathcal{EF}$
construction.

######  Lemma 3.

Any symmetric semi-Boolean function,
$f_{\ast}:\\{0,1\\}^{n}\rightarrow\mathbb{R}$, has at most $n+1$ different
Fourier coefficients that can be computed using the Krawtchouk transformation
of dimension $n+1$, with $\mathcal{O}(n^{5})$ operations.

###### Proof.

The proof of this lemma is given in Appendix D. ∎

Thus, Lemma 3 proves that the multi-linear polynomials created for each
monomial are correct. Finally, the fact that one can use the computed
polynomials, multiplied or not by a factor of $-1$, relates to the simple
observation that they are equivalent to the modular two operation,
$\mathsf{poly}_{f_{\ast}}(x)\ mod\ 2=-\mathsf{poly}_{f_{\ast}}(x)\ mod\ 2$.
Therefore, being positive or negative does not change the parity of the angle,
which determines the result of the NMQC⊕ computation (Equation (10)). Hence,
one can use this new degree of freedom to reduce the number of qubits
necessary to evaluate the selected Boolean function. These reductions can be
achieved by attributing signs to the polynomials, $(-1)^{t_{S}}$, such that
sets containing equal parity bases have their coefficients summing to zero.
Consequently, this would remove the necessity to use these specific qubits
that would otherwise be part of the resource and required to be measured. A
simple demonstration of this new possibility is provided in Example 3 where we
allocated the signs such that one qubit could be removed from that specific
NMQC⊕ computation. Furthermore, one could now define heuristics that attempt
to cancel out as many coefficients as possible. We leave, however, the search
for such heuristics for future work.

######  Example 3.

For the function $h:\\{0,1\\}^{3}\rightarrow\\{0,1\\}$ with input strings of
size three,

$h(x_{1},x_{2},x_{3})=x_{1}*x_{2}\oplus x_{2}*x_{3}\ ,$ (46)

the Krawtchouk transform applied to the simplified value vector to each
monomial computes the Fourier coefficients,

$\frac{1}{4}\begin{bmatrix}1&\ \ 2&\ \ 1\\\ 1&\ \ 0&-1\\\ 1&-2&\ \ 1\\\
\end{bmatrix}*\underbrace{\begin{bmatrix}0\\\ 0\\\ 1\\\
\end{bmatrix}}_{\nu(x_{1}*x_{2})}=\begin{bmatrix}1/4\\\ -1/4\\\ 1/4\\\
\end{bmatrix}\ ,\ \frac{1}{4}\begin{bmatrix}1&\ \ 2&\ \ 1\\\ 1&\ \ 0&-1\\\
1&-2&\ \ 1\\\ \end{bmatrix}*\underbrace{\begin{bmatrix}0\\\ 0\\\ 1\\\
\end{bmatrix}}_{\nu(x_{2}*x_{3})}=\begin{bmatrix}1/4\\\ -1/4\\\ 1/4\\\
\end{bmatrix}\ .$ (47)

These are used to build the respective multi-linear polynomials using Equation
(43),

$\mathsf{poly_{x_{1}x_{2}}}(x)=\pm\Big{(}\dfrac{1}{2}x_{1}+\dfrac{1}{2}x_{2}-\dfrac{1}{2}x_{1}\oplus
x_{2}\Big{)}\ and\
\mathsf{poly_{x_{2}x_{3}}}(x)=\pm\Big{(}\dfrac{1}{2}x_{2}+\dfrac{1}{2}x_{3}-\dfrac{1}{2}x_{2}\oplus
x_{3}\Big{)}\ .$ (48)

Then, the resulting polynomials are combined to obtain the multi-linear
polynomial equivalent to $h(x)$,

$\displaystyle\mathsf{poly_{h}}(x)$
$\displaystyle=+\Big{(}\dfrac{1}{2}x_{1}+\dfrac{1}{2}x_{2}-\dfrac{1}{2}x_{1}\oplus
x_{2}\Big{)}-\Big{(}\dfrac{1}{2}x_{2}+\dfrac{1}{2}x_{3}-\dfrac{1}{2}x_{2}\oplus
x_{3}\Big{)}$ (49)
$\displaystyle=\dfrac{1}{2}x_{1}+\cancel{\dfrac{1}{2}x_{2}}-\cancel{\dfrac{1}{2}x_{2}}-\dfrac{1}{2}x_{3}-\dfrac{1}{2}x_{1}\oplus
x_{2}+\dfrac{1}{2}x_{2}\oplus x_{3}$ (50)
$\displaystyle=\dfrac{1}{2}x_{1}-\dfrac{1}{2}x_{3}-\dfrac{1}{2}x_{1}\oplus
x_{2}+\dfrac{1}{2}x_{2}\oplus x_{3}\ .$ (51)

This polynomial is then used to create the corresponding measurement
assignment. In this case, it translates to a 4-qubit GHZ state,
$\ket{\Psi_{GHZ}^{4}}=1/\sqrt{2}\big{(}\ket{0}^{\otimes 4}+\ket{1}^{\otimes
4}\big{)}$, the linear functions

$L_{1}(x)=x_{1},\ L_{2}(x)=x_{3},\ L_{3}(x)=x_{1}\oplus x_{2},\ and\
L_{4}(x)=x_{2}\oplus x_{3}\ ,$ (52)

and the corresponding measurement operators

$\displaystyle M_{1}(s_{1})=(\neg s_{1})\sigma_{x}+s_{1}\sigma_{y},\
M_{2}(s_{2})=(\neg s_{2})\sigma_{x}-s_{2}\sigma_{y},\ $ (53) $\displaystyle
M_{3}(s_{3})=(\neg s_{3})\sigma_{x}-s_{3}\sigma_{y},\ and\ M_{4}(s_{4})=(\neg
s_{4})\sigma_{x}+s_{4}\sigma_{y}\ .$ (54)

Moreover, the function evaluated on all possible inputs, for
$x\in\\{0,1\\}^{3}$, in the NMQC⊕ model is equal to
$(-1)^{h(x_{1},x_{2},x_{3})}\ket{\Psi_{GHZ}^{5}}$ as intended. Notice also
that assigned the positive sign to one of the polynomials and the negative
sign to the other in Equation (49). This specific attribution removed a term
($x_{2}$ in Equation (50)) that would otherwise demand an extra qubit of the
resource state.

Concerning the computational cost of determining the measurement assignments,
this construction avoids resorting to the Fourier transform, which computes a
number of Fourier coefficients that is exponential in $n$, the size of the
input string. Furthermore, as proven in Lemma 3, there are only $n+1$
different Fourier coefficients that characterize symmetric Boolean functions.
Thus, it is only necessary to select $n+1$ lines of the Fourier matrix to
determine these coefficients. That is precisely one of the reductions applied
to obtain the Krawtchouk transform and explains one of the computational
advantages of this solution. Additionally, the transformation does not use
these $n+1$ lines of the Fourier matrix to determine the coefficients.
Alternatively, each line of the Krawtchouk transformation computes the
demanded Fourier coefficients based on the simplified value vector of the SBF.
Therefore, it reduces the determination of each Fourier coefficient to a
counting problem that can be solved in polynomial time. This observation
entails another exponential advantage with respect to the approach bared on
the Fourier transform.

In order to quantify the advantage behind the use of the Krawtchouk transform,
we need to characterize the cost of the approach that uses the Fourier
transform. This cost is defined by the degree of the Boolean function.

######  Definition 7.

(Degree). The degree of a Boolean function $f$ is equal to the cardinality of
the largest monomial in its ANF,

$\mathsf{deg}(f)=max\\{|S|\ |\ c_{S}\neq 0\\}$ (55)

In particular, one needs a Fourier matrix of size $2^{\mathsf{deg(f)}}\times
2^{\mathsf{deg(f)}}$ to translate the largest monomial into a multi-linear
polynomial. This process enforces the existence of at least
$2^{\mathsf{2deg(f)}}$ operations to determine the coefficient of this
singular term, imposing a run-time complexity lower bound of
$\Omega(2^{\mathsf{2deg(f)}})$ to this method. In addition, one must consider
that it will be necessary to compute the multi-linear polynomials of all the
other monomials ($m=\sum_{s\in[n]}c_{S}$) and then sum them all to form the
resulting polynomial. Accounting for these additional operations, we roughly
estimate the computational cost of the $\mathcal{EF}$ construction to be
$\mathcal{O}\big{(}poly(m)*2^{\mathsf{2deg(f)}}\big{)}$555The term $poly(m)$
represent a function of the type $f(x)=x^{c}$ with $c\in\mathbb{N}$.. In
contrast, for the Krawtchouk transform, the computational effort equivalent to
determining the Fourier coefficients of the largest monomial is defined by
applying a matrix of size $(\mathsf{deg}(f)+1)\times(\mathsf{deg}(f)+1)$.
Furthermore, the entries of this matrix are determined in polynomial time, as
proven by Lemma 3. Thus, the process used to determine all the necessary
Fourier coefficients decreases from an exponential to a polynomial magnitude.

Although we have found a significant reduction in one of the subprocesses
necessary to determine the measurement assignments, there is still an
unavoidable exponential scaling with respect to the degree of the Boolean
function.

######  Proposition 2.

For any Boolean function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$, a measurement
assignment for the NMQC⊕ model can be determined with a computational
complexity that scales exponentially with the degree of the Boolean function
and polynomially with the number of monomials, $m=\sum_{s\in[n]}c_{S}$, in its
ANF representation, i.e.
$\mathcal{O}\Big{(}m*\Big{(}(\mathsf{deg}(f)+1)^{5}+2^{\mathsf{deg}(f)}\Big{)}\Big{)}$.

###### Proof.

The Krawtchouk transform gives the number of operations required to determine
all the necessary Fourier coefficients. This matrix has
$(\mathsf{deg}(f)+1)^{2}$ entries, which can be computed with at most
$(\mathsf{deg}(f)+1)^{3}$ operations. Therefore, in total, there are at most
$m*(\mathsf{deg}(f)+1)^{5}$ operations, as proven by Lemma 3 to determine all
the necessary Fourier coefficients. These coefficients build the multi-linear
polynomials equivalent to the monomials $m$ in the ANF of the Boolean
function, using Equation (43). Subsequently, there is an additional cost due
to the need to sum the coefficients related to the multi-linear polynomials
resulting from the various monomials. This specific process assembles the
final multi-linear polynomial and has at most $m*2^{\mathsf{deg}(f)}$
operations. The exponential term $2^{\mathsf{deg}(f)}$ results from the
minimal sparsity for the largest monomial in the Boolean function. That this
is the minimal sparsity is proven by a theorem in [21] showing that the
sparsity of any Boolean function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ is at
least $2^{\mathsf{deg}(f)}$. Combining the two terms, we arrive at the cost
value described in the proposition. ∎

The bound proven in Proposition 2 shows that the $\mathcal{KR}$ construction
is almost as efficient as it could be to determine the measurement assignments
that result from this technique. This statement is justified by demonstrating
that the computational effort of determining the multi-linear polynomials
regarding their sparsity is at most polynomial. Therefore, exponential
scalings only exist because the object we are constructing is of exponential
size. In contrast, the Fourier transform introduces an additional exponential
effort to determine each one of the Fourier coefficients. Thus, determining
valid measurement assignments with this transformation implies a computational
effort of exponential size with respect to the sparsity of the multi-linear
polynomials. Furthermore, this result highlights the importance of finding and
employing constructions that produce sparse multi-linear polynomials. These
reduces the number of qubits for the NMQC⊕ computation and, in principle,
facilitates the process of determining their measurement assignments.

Parameterized construction 1: The symmetric complements
($\mathcal{SC}(\zeta)$) This construction merges all the contributions we have
presented so far. In particular, it incorporates the advantage of the
$\mathcal{CSF}$ construction to determine sparse-multi-linear polynomials for
symmetric Boolean functions, with the computational reductions obtained with
the $\mathcal{KR}$ construction.

The construction starts from the ANF of a Boolean function
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ and creates two additional Boolean
functions based on a previously selected symmetrization function $\zeta$.

######  Definition 8.

(Symmetrization function). A symmetrization function is a function
$\zeta:\big{(}\\{0,1\\}^{n}\rightarrow\\{0,1\\}\big{)}\rightarrow\big{(}\\{0,1\\}^{n}\rightarrow\\{0,1\\}\big{)}$
that receives an arbitrary Boolean function,
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$, and maps it to a symmetric Boolean
function, $f_{\mathsf{sym}}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$, such that
$\zeta(f(x))=f_{\mathsf{sym}}(x)$, for all $x$.

The first Boolean function we need to define is the symmetrized function of
$f$ respective to $\zeta$. This function is computed by applying the
symmetrization function $\zeta$ to $f$ in order to obtain $f_{\mathsf{sym}}$.
Then, the complement of $f$ with respect to its symmetrized function
$f_{\mathsf{sym}}$, designated as $\mathbf{\tilde{\text{$f$}}}$, has to be
computed.

######  Definition 9.

($\mathbf{\tilde{\text{$f$}}}(x)$). The complement of $f$ with respect to the
symmetrization function $\zeta$ is defined as,

$\mathbf{\tilde{\text{$f$}}}(x)=f(x)\oplus\zeta(f(x))=f(x)\oplus
f_{\mathsf{sym}}(x)\ .$ (56)

The construction translates all three Boolean functions $f(x),\ \zeta(f(x)),$
and $f(x)\oplus\zeta(f(x))$ to multi-linear polynomials. The $\zeta(f)$
function is translated using the $\mathcal{CSF}$ construction, given that it
is a symmetric Boolean function, while for $f$ and
$\mathbf{\tilde{\text{$f$}}}$ the $\mathcal{KR}$ construction is employed to
generate the following polynomials

$f(x),\ \mathbf{\tilde{\text{$f$}}}(x)\ \xmapsto{\ \mathcal{KR}\ }\
\mathsf{poly}_{f_{1}}(x),\ \mathsf{poly}_{\mathbf{\tilde{\text{$f$}}}}(x);\ \
\ \ \zeta(f)(x)\ \xmapsto{\ \mathcal{CSF}\ }\ \mathsf{poly}_{\zeta(f)}(x)\ .$
(57)

From the resulting multi-linear polynomials, two valid solutions can be built.
The first is $\mathsf{poly}_{f_{1}}$ which derives directly from $f$ using the
$\mathcal{KR}$ construction. The second solution results from the linear sum
of $\mathsf{poly}_{\mathbf{\tilde{\text{$f$}}}}(x)$ and
$\mathsf{poly}_{\zeta(f)}(x)$, provided that
$\mathbf{\tilde{\text{$f$}}}(x)\oplus\zeta(f)(x)=f(x)$. In the end, the
sparsest of the two multi-linear polynomials will be used to generate the
measurement assignment for the NMQC⊕ computation,

$\mathsf{poly}_{f}=min\big{\\{}\mathsf{sparsity}\big{(}\mathsf{poly}_{f_{1}}\big{)},\
\mathsf{sparsity}\big{(}\mathsf{poly}_{\mathbf{\tilde{\text{$f$}}}}(x)+\mathsf{poly}_{\zeta(f)}(x)\big{)}\big{\\}}.$
(58)

In order to demonstrate how advantageous this construction could be, we will
select a specific symmetrization function $\zeta_{C}$. This symmetrization
function takes the Boolean function $f$ and introduces all the missing terms
such that if there is a term of degree $k$ in its ANF, then the corresponding
CSF $C^{k}$ will occur in its symmetrized version.

######  Definition 10.

($\zeta_{C}(x)$). The symmetrization function
$\zeta_{C}(x):\big{(}\\{0,1\\}^{n}\rightarrow\\{0,1\\}\big{)}\rightarrow\big{(}\\{0,1\\}^{n}\rightarrow\\{0,1\\}\big{)}$
is defined as

$\zeta_{C}(f(x))=\bigoplus_{k\in T}c_{k}*C^{k}(x),\ with\ T=\\{|S|\ |\
c_{S}\neq 0\\}.$ (59)

We can, then, use this function $f$ to generate a multi-linear polynomial for
an arbitrary Boolean function. In particular, we shall consider a class of
Boolean functions for which there is an asymptotical advantage of this new
constriction over all the previously described.

######  Definition 11.

($[AC^{k}]$). The class of almost complete symmetric functions $[AC^{k}]$ is
composed by families of Boolean functions $f$ such that,

$f(x)\in[AC^{k}]\implies f(x)=C^{k}(x)\bigoplus_{i=0}^{t}\Bigg{(}\prod_{j\in
S_{i}}x_{j}\Bigg{)}$ (60)

with $|S_{i}|=k$ for all $i\in[0,t]$, $x\in\\{0,1\\}^{n}$ and
$k,t\in\mathbb{N}$.

Function in this class miss only a fixed set of terms is missing to be
precisely equal to a complete symmetric function $C^{k}$.

######  Lemma 4.

All families of Boolean functions in the $[AC^{k}]$ class have multi-linear
polynomials with sparsities that scale at most with the same asymptotical rate
as its symmetrized function $C^{k}$.

###### Proof.

Suppose the $\mathcal{SC}$ construction is used to compute the multi-linear
polynomials for a family of Boolean functions $f$ contained in the class of
$[AC^{k}]$. In this case, these will result from combining two other multi-
linear polynomials: the multi-linear polynomials corresponding to the
symmetrized Boolean functions $\zeta_{C}(f)$ and multi-linear polynomials
corresponding to the complement of $f$ with regard to $\zeta_{C}(f)$,
$\mathbf{\tilde{\text{$f$}}}$. These particular functions will be by the
definitions of $[AC^{k}]$ and $\zeta_{C}$ equal to some CSF $C^{k}$ for the
former, and equal to some constant number terms
($\bigoplus_{i=0}^{t}(\prod_{j\in S_{i}}x_{j})$) for latter. Hence, the multi-
linear polynomials resulting from the $\zeta_{C}(f)$ have sparsities equal to
$C^{k}$, and the polynomials corresponding to the complement
$\mathbf{\tilde{\text{$f$}}}$ have a constant sparsity. Therefore,
assymptotically, only the multi-linear polynomials corresponding to the
symmetrized functions contribute to their sparsity. ∎

The first observation that follows from Lemma 4 is that for specific elements
in the $[AC^{k}]$ class, one can take direct advantage of the sparse CSF
polynomials described in Section 3.1 to lessen their upper bound. In Example,
4, a specific family of Boolean functions was defined for which the best qubit
scaling went from $\Theta(n^{64})$ to $\Theta(n^{32})$ simply with the use of
the $\mathcal{SC}$ construction with the $\zeta_{C}$ function and a CSF
polynomial. Furthermore, similar reductions are feasible for the whole
$[AC^{k}]$ class. In contrast, the $\mathcal{EF}$ construction and similar
techniques were utterly blind to the possibility of inheriting the sparsity of
SBFs.

######  Example 4.

Consider function $AC^{64}(x)=C^{64}(x)\oplus x_{1}x_{2}....x_{64}$, which is
built using a CSF function and a constant term added to it. If one uses the
$\mathcal{EF}$ construction, the resulting multi-linear polynomials have the
following form,

$poly_{AC^{64}(x)}=\Bigg{(}\sum_{i=0}^{64}c_{i}\bigg{(}\sum_{S\subseteq[n],|S|=i}\bigoplus_{j\in
S}x_{j}\bigg{)}\Bigg{)}-poly_{x_{1}x_{2}...x_{64}}(x)$ (61)

with a sparsity of
$\mathsf{sparsity}(poly_{AC^{64}(x)})=\sum_{i=0}^{64}\binom{n}{i}-1$, that
scales asymptotically with $\Theta(n^{64})$. Suppose the $\mathcal{SC}$
construction is used on the same function. In this case, it builds different
multi-linear polynomials using the symmetrized function $\zeta_{C}(AC^{64})$,
which is exactly equal to $C^{64}$ and the complement
$\mathbf{\tilde{\text{$AC^{64}$}}}$, which is equal to the term
$x_{1}x_{2}...x_{64}$. Therefore the resulting multi-linear polynomials will
have the following form

$poly_{AC^{64}(x)}=\Bigg{(}\sum_{i=0}^{32}c_{i}\bigg{(}\sum_{S\subseteq[n],|S|=i}\bigoplus_{j\in
S}x_{j}-\sum_{S\subseteq[n],|S|=n-i+1}\bigoplus_{j\in
S}x_{j}\bigg{)}\Bigg{)}+poly_{x_{1}x_{2}...x_{64}}(x)\ ,$ (62)

which has a sparsity of
$\mathsf{sparsity}(poly_{AC^{64}(x)})=2\sum_{i=1}^{31}\binom{n}{i}+\binom{n}{32}+\sum_{j=33}^{64}\binom{64}{j}$,
that scales asymptotically with $\Theta(n^{32})$, and which determines the
number of qubits necessary to evaluate the Boolean function deterministically
in the NMQC⊕ model.

In summary, the construction proposed entails the possibility of exploring SBF
to generate more efficient NMQC⊕ computations, not only for symmetric but also
for general Boolean functions. From a practical point of view, we introduced a
specific symmetrization function $\zeta_{C}$ to demonstrate the impact the
construction could have on a whole class of Boolean families $[AC^{k}]$ by
reducing the computational requirements of all their elements regarding an
evaluation in the NMQC⊕ model. However, there is plenty of space for
improvement in selecting and creating other symmetrization functions. One
could define more elaborated functions that symmetrize the arbritary Boolean
functions so that classes larger than $[AC^{k}]$ are reduced. Consequently,
further study of this construction is in order to illustrate its potential
advantages.

##  4 Bounding the resources for the NMQC⊕ model

This section discusses bounds on the resources needed for the deterministic
evaluation of Boolean functions in the NMQC⊕ model. For that, we will analyze
the Clifford hierarchy of the measurement operators, and the sparsity of the
resource state. Both measures follow naturally from the definition of the
model, which performs computations via measurements applied to a resource
state with auxiliary linear computations. In particular, these measures will
be examined in light of the new constructions proposed in the previous
section, producing mainly new upper bounds for the NMQC⊕ model.

###  4.1 Clifford hierarchy of the measurement operators

The measurement operators required for deterministic computations in the NMQC⊕
model are described by Equation (4) as single qubit rotation around the Bloch
sphere. In particular, they can be decomposed into a unitary operation $U_{i}$
and a measurement on the computational basis,

$M_{i}$ & = U_i .

Therefore, the corresponding unitaries $U_{i}$ capture the complexity of the
measurement operations imposed by the Boolean function in the NMQC⊕ model
666Interestingly, determining the complexity of unitary operations has been an
important research topic in quantum computing, with extensive applications
from circuit synthesis to quantum error correcting codes [62, 63, 64, 65]..
Intuitively, operations are considered simple if they require a small number
of gates and low-depth circuits to be executed. In contrast, other more
complex unitaries require more computational resources [66, 65, 67]. In order
to obtain a better characterization, Gottesman and Chuang proposed the
Clifford hierarchy to define specific levels of complexity for unitary
operations [68].

######  Definition 12.

(Clifford hierarchy). The Clifford hierarchy is defined recursively as

$Cl_{k}:=\\{\ U\ |\ UPU^{\dagger}\in Cl_{k-1},\ \forall P\in\mathcal{P}\\}$
(63)

for $\mathcal{P}$ the Pauli group.

This specific hierarchy has been connected to several fundamental results. For
instance, the second level of the hierarchy, $Cl_{2}$, defines the Clifford
group, which was proven to be efficiently simulable by classical computers, a
result known as the Gottesman-Knill theorem [69]. It is also known that any
element of the third level, $Cl_{3}$, together with the Clifford group
generates a universal gate set for quantum computation. For instance, the gate
set Clifford$+$T is often used as a universal gate set, denoting by T the
unitary from the third level of the hierarchy [70, 65].

For the NMQC⊕ model, it was proven that the level of the measurement operators
in the Clifford hierarchy directly bounds the complexity of the Boolean
functions that can be evaluated deterministically. More precisely, in [22],
the authors prove that any measurement assignment with measurement operators
belonging to at most the $k$th level of Clifford hierarchy cannot
deterministically compute Boolean functions of degree greater than $k$. This
result defines a lower bound on the hierarchy level required for deterministic
computations.

Reciprocal to this finding, we determine an upper bound for the highest level
of the Clifford hierarchy required for a particular Boolean function. For
that, we define the granularity of semi-Boolean functions, given that this
quantity determines the type of measurement operators used in a measurement
assignment (Equation (17) and Equation (4)).

######  Definition 13.

(Granularity). The granularity of a semi-Boolean function
$f_{\ast}:\\{0,1\\}^{n}\rightarrow\mathbb{R}$ is given by

$\mathsf{gran}(f)=max_{S\subseteq[n]}\
\mathsf{gran}\big{(}\widehat{f}(S)\big{)}\ $ (64)

with the granularity of each Fourier coeficient or any rational number being
equal to the smallest $k$ such that $\widehat{f}(S)*2^{k}\in\mathbb{N}.$

Then, we prove that the $\mathcal{KR}$ construction always produces
measurement assignments based on semi-Boolean functions that have a
granularity bounded by the degree of the Boolean function.

######  Lemma 5.

All Fourier coefficients of a multi-linear polynomial resulting from the
$\mathcal{KR}$ construction applied to a Boolean function $f$ have their
granularity $\mathsf{gran}\big{(}\widehat{f}(S)\big{)}$ bounded by
$\mathsf{deg}(f)$.

###### Proof.

The Fourier transform applied to each monomial ($\prod_{k\in S_{j}}x_{k}$) in
the ANF of the Boolean function generates a multi-linear polynomial
$\mathsf{poly}_{i}$ with Fourier coefficients $\widehat{f}(S_{j,1})$ of the
type $\frac{l_{S_{j,k}}}{2^{i}}$, with $S_{j,k}\subseteq S_{j}$,
$k\in[2^{i}]$, and $i=\mathsf{deg}\big{(}\prod_{k\in S_{j}}x_{k}\big{)}$ by
definition of the Fourier transformation [55]. Therefore, the same is true for
the Krawtchouk transform, which computes the same Fourier coefficients.

Then, all such individual polynomials are summed or subtracted based on the
coefficients $c_{i}\in\\{0,1\\}$ to generate the final multi-linear
polynomial,

$\displaystyle\underbrace{(-1)^{c_{1}}\bigg{(}\overbrace{\frac{l_{S_{1,1}}}{2^{i_{1}}}}^{\widehat{f}(S_{1,1})}\bigoplus_{k\in
S_{1,1}}x_{k}+\frac{l_{S_{1,2}}}{2^{i_{1}}}\ldots+\ldots+\frac{l_{S_{1},i_{1}}}{2^{i_{1}}}\ldots\bigg{)}}_{\mathsf{poly}_{1}}+$
(65)
$\displaystyle\underbrace{(-1)^{c_{2}}\bigg{(}\frac{l_{S_{2,1}}}{2^{i_{2}}}\ldots+\frac{l_{S_{2,2}}}{2^{i_{2}}}\ldots+\ldots+\frac{l_{S_{2},i_{2}}}{2^{i_{2}}}\ldots\bigg{)}}_{\mathsf{poly}_{2}}+\ldots=\mathsf{poly}_{f}\
.$ (66)

Therefore the resulting Fourier coefficients ($\widehat{f}(S)$) for each of
the parity bases ($\bigoplus_{k\subseteq S}x_{k}$) in the final multi-linear
polynomial are equal to the sum of all non-zero Fourier coefficients that have
the same parity base in the multi-linear polynomials resulting from each
monomial,
$\frac{l_{S}}{t}=\sum_{S_{j,k}=S}\frac{(-1)^{c_{j}}*l_{S_{j,k}}}{2^{i_{j}}}$.
Consequently, the denominator $t$ of the resulting value is equal to the least
common multiple between all denominators, given that we are summing and
subtracting rational numbers. Additionally, all the denominators are of the
form $\frac{1}{2^{i}}$, for which the
$l.c.m(\frac{1}{2^{i_{1}}},\frac{1}{2^{i_{2}}},...,\frac{1}{2^{i_{n}}})=max(\frac{1}{2^{i_{1}}},\frac{1}{2^{i_{2}}},...,\frac{1}{2^{i_{n}}})$.
This proves that, for any Fourier coefficient in the final multi-linear
polynomial, the corresponding denominator is at most equal to the largest
denominator present in the sum. Thus, the largest denominator is at most equal
to the denominators of the monomials defining the degree of the Boolean
function, which implies that the resulting Fourier coefficients have a
denominator that is at most equal to $\frac{1}{2^{\mathsf{deg}(f)}}$, proving
the lemma. ∎

In addition, we relate the level of the Clifford hierarchy of measurement
operators with the angles’ granularity using the semi-Clifford hierarchy.

######  Definition 14.

(Semi-Clifford hierarchy). A gate $U$ is in the semi-Clifford hierarchy of
level-k if $U=A_{1}DA_{2}$, such that $A_{1},A_{2}\in Cl_{2}^{N}$ are Clifford
gates and $D\in Cl_{k}^{N}$ is the diagonal. The set of k-th level Clifford
gates is denoted by $SCl_{k}^{N}$.

######  Lemma 6.

All measurement operators of type
$M=\cos\big{(}\phi\big{)}\sigma_{x}+\sin\big{(}\phi\big{)}\sigma_{y}$ are in
the level-$\mathsf{gran}\big{(}\phi\big{)}+1$ of the Clifford hierarchy.

###### Proof.

This type of operator can be characterized by the semi-Clifford hierarchy,
given that it can be decomposed as,

$\displaystyle I*M_{i}*\sigma_{x}$
$\displaystyle=I\big{(}\cos\big{(}\phi\big{)}\sigma_{x}+\sin\big{(}\phi\big{)}\sigma_{y}\big{)}\sigma_{x}$
(67)
$\displaystyle=\cos\big{(}\phi\big{)}I-i\sin\big{(}\phi\big{)}\sigma_{z})$
(68) $\displaystyle=R_{Z}\big{(}\phi\big{)}\ ,$ (69)

noting that $R_{Z}\Big{(}\frac{\pi l}{2^{j}}\Big{)}$ is a diagonal unitary
gate of level-$2^{j+1}$ in the Clifford hierarchy [66], while $I,\sigma_{x}\in
Cl_{2}$. We conclude that gates of the form $M$ are in the
$\mathsf{gran}\big{(}\phi_{i}\big{)}$-level of the semi-Clifford hierarchy.
Additionally, in [65] it was proven that $Cl_{k}^{1}=SCl_{k}^{1}$, such that
all $M\in SCl_{2^{i+1}}^{1}=Cl_{2^{i+1}}^{1}$. Therefore we have proven that a
measurement operator of the type of $M$ is in the
$\mathsf{gran}\big{(}\phi\big{)}$-level of the Clifford hierarchy. ∎

Finally, it is possible to define an upper bound on the level of the Clifford
hierarchy of the measurement operators necessary for deterministic evaluations
of Boolean functions.

######  Theorem 4.

For any Boolean function $f$, the $\mathcal{KR}$ construction generates
deterministic NMQC⊕ evaluations that use measurement operators belonging to at
most the $\mathsf{deg}(f)$-level of the Clifford hierarchy

###### Proof.

With Lemma 5 it is possible to bound the granularity of the Fourier
coefficients determined by the Krawtchouk transform for an arbitrary Boolean
function. These coefficients then define the angle of the measurement operator
based on Equation (17). Therefore, it is equally possible to bound the
granularity of all the angles used in the measurement assigned by the degree
of the Boolean function. In addition, the granularity of $\theta_{i}$ from
Equation (4) can be made equal to zero with a linear shift of the Boolean
function (a free operation). Consequently, the granularity
$\mathsf{gran}(\theta_{i}+\phi_{i})$ of the total angle defining the
measurement operator can be bounded by $\mathsf{deg}(f)-1$. Now, it suffices
to use Lemma 6 to bound the level of the Clifford hierarchy of the selected
measurement operators. This finishes the proof given that the Krawtchouk
transform always generates measurement assignments that evaluate the intended
Boolean function deterministically. ∎

This result demonstrates that minimizing the Clifford hierarchy of the
measurement operators is always possible and that the degree of the Boolean
function alone defines the minimum and maximum level required. For the upper
bound, we used the granularity of the Fourier spectrum, which abstractly was
the same concept used in [22] for the lower bound. Furthermore, in Boolean
analysis, the granularity of the Fourier spectrum is also used to prove lower
bounds [56]. However, in those cases, only Boolean functions are considered.
In contrast, for the NMQC⊕ model, due to the symmetry of the cosine function,
there is a large class of equivalent semi-Boolean functions that compute the
intended Boolean functions correctly. Therefore, these results can not be
translated to the NMQC⊕ model. Nevertheless, it was with the concept of the
minimum possible granularity of all the possible semi-Boolean functions that
the author of [21] proved a lower bound for the sparsity of arbitrary Boolean
functions. In the end, we highlight the importance of these measures to bound
the necessary resources for the deterministic evaluation of Boolean functions
in NMQC⊕.

###  4.2 Lower bound conjecture for symmetric Boolean functions

The previous section introduced several methods to determine measurement
assignments that deterministically compute a given Boolean function in the
NMQC⊕ model. Moreover, all these solutions consider the general GHZ state as
the resource, which was proven to be the optimal resource [20, 54].
Nevertheless, no construction guarantees that the sparsest polynomials are
created. This indicates that determining the minimum number of qubits
necessary to evaluate a Boolean function is a nontrivial problem.
Additionally, it is possible to show that each Boolean function in the model
is equivalent to a Bell inequality [20]. Therefore, one could suspect that the
difficulty of the former problem is associated to the known hardness of the
latter one [71]777Determining the maximal violation of a Bell inequality
obtained from measurements on a quantum state was proven to be NP-hard even in
the tripartite case [72]. Nonetheless, finding lower bounds for specific
subsets of Boolean functions was proven possible in [20], and it would be
exciting to extend these results further.

Finding the smallest possible resource is generally a complex problem because
there are an infinite number of valid measurement assignments for a particular
Boolean function. In particular, all these solutions exist because the phase
introduced after the measurement process, which defines the result of the
computation, is invariant with respect to a $2\pi$ rotation (see Equation
(10)). Therefore, various multi-linear polynomials of type
$\mathsf{poly}:\\{0,1\\}^{n}\rightarrow\pi\mathbb{Z}$ are equivalent in the
model when all their outputs correspondingly map to the same equivalence class
of the quotient set $\pi(\mathbb{Z}/2\mathbb{Z})$. Consequently, the minimum
number of qubits necessary to evaluate a Boolean function in the NMQC⊕ model
can be defined by the sparsest element in this set.

######  Definition 15.

(Minimal sparsity). The minimum number of qubits necessary for the
deterministic evaluation of a Boolean function
$f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ in the NMQC⊕ model can be defined as the
sparsest multi-linear polynomial equivalent to the function, i.e.

$min\Big{\\{}\mathsf{sparsity}\big{(}\mathcal{F}(g)\big{)}\Big{|}\
g:\\{0,1\\}^{n}\rightarrow\mathbb{Z}\ s.\ t.\ \forall_{x\in\\{0,1\\}^{n}}\
f(x)\equiv g(x)\mod 2\Big{\\}}\ .$ (70)

Fortunately, while the number of multi-linear polynomials equivalent to the
Boolean functions is infinite, the effective search space is finite [55].
Nevertheless, the size of the search space is double exponential with the size
of the input string [22]. Thus, an exhaustive search for the sparsest multi-
linear polynomials is not feasible.

Despite this tremendously ample search space, there are some restrictions that
can make the problem considerably simpler for the set of SBF. More precisely,
we will impose the constraint that only symmetric measurement assignments are
allowed for their evaluation.

######  Definition 16.

(Symmetric measurement assignment). A symmetric measurement assignment for an
NMQC⊕ computation is composed of a set of linear functions $L$, which is
limited to having either all parity bases of a specific size or none,

$L=\Big{\\{}\bigoplus_{l\in S}x_{l}\ \Big{|}\ S\subseteq[n],\ |S|\in
T\Big{\\}},\ with\ T\subseteq[n]\ ,$ (71)

and the corresponding dichotomic measurement operators, which have to be equal
for all parity bases of the same size, i.e. $|S_{i}|=|S_{j}|\implies
M_{i}(x)=M_{j}(x)\ .$

Furthermore, all symmetric measurement assignments for an NMQC⊕ computation
are equivalent to a symmetric multi-linear polynomial
($\mathsf{poly}_{\mathsf{sym}}:\\{0,1\\}^{n}\rightarrow\mathbb{R}$) of the
following form:

$\mathsf{poly}_{\mathsf{sym}}(x)=\pi*\bigg{(}\sum_{i\in
T}\widehat{f}(|S|=i)*\sum_{S_{j}\subseteq[n],|S_{j}|=i}g^{-1}\bigg{(}\bigoplus_{l\subseteq
S_{j}}x_{l}\bigg{)}\bigg{)},\ with\ T\subseteq[n]\ \ .$ (72)

Therefore, with this restriction, the multi-linear polynomials that describe
SBF have at most $n+1$ different Fourier coefficients concerning the size of
the input string $n$. Unfortunately, the set of solutions is still of an
exponential size to perform a search. Nevertheless, knowing the particular
polynomials with the smallest sparsities is not necessary to determine lower
bounds. It is sufficient to independently learn the sparsities of the
polynomials with the smallest sparsities. Hence, one could define a decision
problem that only questions if there is a multi-linear polynomial equivalent
to the SBF with a particular sparsity. Fortunately, the combinations of this
restriction with the $\mathcal{KR}$ transform allow us to define an algorithm
able of answering this decision problem in polynomial time.

######  Lemma 7.

An algorithm with polynomial scaling runtime can decide whether there exists a
symmetric multi-linear polynomial with a selected subset of non-zero Fourier
coefficients, $F=\big{\\{}\widehat{f}(|S|=i)\ \big{|}\ i\in T,\
T\subseteq[n]\big{\\}}$, that computes a particular symmetric Boolean function
deterministically in the NMQC⊕ model.

###### Proof.

The proof is presented in Appendix F. ∎

Furthermore, this algorithm can be employed to identify the order of magnitude
of the sparsity of an arbitrary SBF in polynomial time (For more details, see
Appendix G). Subsequently, applying these processes to the set of CSF
functions led to the following conjecture,

######  Conjecture 2.

The number of qubits in a GHZ state necessary for the deterministic evaluation
of a complete symmetric function $C^{k}$, with an $n$ bit input string and a
symmetric measurement assignment, scales as $\Omega(n^{\left\lfloor
k/2\right\rfloor-1})$.

Support: This conjecture is supported empirically by a numerical verification
process which was applied to all CSF that can be defined with an input size up
to 345 bits. The details of this numerical verification process are presented
in Appendix G. Additionally, the conjecture is consistent with the lower bound
for the $C^{2}$ function and the $\mathsf{AND}$ function. In particular, for
the latter, each CSF function is exactly equal to the function for a specific
input size, as for all $k\in\mathbb{N}$ and $|x|=k$ ,
$C^{k}(x)=\mathsf{AND}(x)$.

Remember that the set of CSFs behaves as a building block for all SBFs,
Equation (26). Therefore, the correctness of this conjecture implies an
equivalent lower bound for families of SBF with a constant degree.

######  Corollary 1.

Any family of symmetric Boolean functions defined with a constant degree and
evaluated with a symmetric measurement assignment in the NMQC⊕ model requires
a number of qubits which is asymptotically bounded by
$\Omega(n^{\left\lfloor\mathsf{deg}(f)/2\right\rfloor-1})$.

Support: This corollary follows directly from Conjecture 2 and the definition
of SBF’s.

From an abstract point of view, the conjecture and the respective numerical
support further strengthen the idea that the degree of the Boolean function
and the size of the input string determine the number of qubits necessary for
deterministic computations in the NMQC⊕ model. Moreover note that the symmetry
condition was not imposed on the lower bounds obtained previously. However,
the optimal measurements assignments for the SBF $\mathsf{AND}$ and $C^{2}$
are symmetric. It remains to be proven, but it could be possible that the
optimal measurement assignments for SBFs concerning the minimum number of
qubits are always symmetric. Supposing that this last hypothesis and the
conjecture were both proven true, then the multi-linear polynomials presented
in Lemma 2 would be optimal and generate the most resource-efficient
measurement assignments for the respective SBFs in the NMQC⊕ model.

###  4.3 Qubit count for symmetric Boolean functions

In the previous subsection, we conjectured a lower bound for the number of
qubits in a GHZ state required for an NMQC⊕ evaluation of symmetric Boolean
functions. Complementary to this result, comparing this bound with the
existing upper bound is particularly interesting. For this, it will be
necessary to define new upper bounds based on our proposed constructions and
their corresponding multi-linear polynomials.

Formerly, the upper bound for SBF resulted from the $\mathcal{EF}$
construction presented in [21]. In particular, this construction generates
multi-linear polynomials that had a sparsity equal to
$\sum_{i=0}^{\mathsf{deg}(f)}\binom{n}{i}$, which entails an asymptotical
scaling of $\mathcal{O}\big{(}n^{\mathsf{deg}(f)}\big{)}$. Recently, Frembs et
al. [22] presented a sparser description for the multi-linear polynomials
representing CSFs that directly reduces the sparsity of the multi-linear
polynomials used for SBFs. More precisely, the proposed multi-linear
polynomials have a sparsity of
$\mathsf{sparsity}(C^{k}(x))=\sum_{i=0}^{k-1}\binom{n}{i}$, which translates
to an asymptotical scaling for SBF equivalent to
$\mathcal{O}\big{(}n^{\mathsf{deg}(f)-1}\big{)}$. Futhermore, this last upper
bound was the best known up to now, to the best of our knowledge.

In order to find new upper bounds, it is necessary to define the impact of the
$\mathcal{CSF}$ construction on the sparsity of the multi-linear polynomials
generated for SBFs. For this purpose, we must consider that this construction
creates multi-linear polynomials using the subset of CSFs with a degree equal
to a power of two exclusively. Therefore, it can be proven that the sparsity
of the resulting multi-linear polynomials also depends uniquely on the same
set.

######  Lemma 8.

The sparsity of any multi-linear polynomial equivalent to a symmetric Boolean
function $f$ is bounded as

$\mathsf{sparsity}\big{(}f(x)\big{)}\leq\sum_{i=0}^{n}c_{i}\prod_{r\in
R_{i}}\Big{(}\mathsf{sparsity}\big{(}C^{2^{r}}(x)\big{)}+1\Big{)},$ (73)

with $R_{i}\subseteq[\left\lceil\log(i)\right\rceil]$, such that $\sum_{r\in
R_{i}}2^{r}=i$.

###### Proof.

A valid multi-linear polynomial can be generated for any SBF based on Equation
(26) and the general decomposition defined in Proposition 1. Therefore, the
sparsity of SBF is always upper bounded by the sparsity of the polynomials
built from this representation. In particular, the same expression directly
defines the relation between the resulting polynomial’s sparsity and that of
the CSFs used. ∎

Consequently, for families of SBF with a constant degree, the asymptotic upper
bound depends only on the subset of CSFs with degrees that are powers-of-two,

$\mathsf{sparsity}\big{(}f(x)\big{)}=\mathcal{O}\bigg{(}\prod_{r\in
R_{d}}\mathsf{sparsity}\big{(}C^{2^{r}}(x)\big{)}\bigg{)}$ (74)

with $R_{d}\subseteq[n]$, such that $\sum_{r\in
R_{d}}2^{r}=\mathsf{deg}\big{(}f\big{)}$. The fact that only the CSF function
with the largest degree is considered can be explained by the fact that the
CSFs polynomials have monotonically increasing sparsity.

Subsequently, this bound has to be combined with the minimal sparsities known
for the CSF with a degree equal to a power of two. In particular, for
instances with a degree equal to or smaller than 64, the most compact multi-
linear polynomials are the ones identified in Lemma 2, and, for higher degree
functions, are the ones described in [22],

$\mathsf{sparsity}\Big{(}C^{2^{r}}(x)\Big{)}=sparsity\Big{(}C^{k}(x)\Big{)}=\begin{cases}\mathcal{O}\big{(}n^{2^{r-1}}\big{)}=\mathcal{O}\big{(}n^{k/2}\big{)}\Leftarrow&r=2,3,4,5,6\\\
\mathcal{O}\big{(}n^{2^{r}-1}\big{)}=\mathcal{O}\big{(}n^{k-1}\big{)}\Leftarrow&r>6\end{cases},$
(75)

with $2^{r}=k$. Therefore when these instances are used to determine the
asymptotic sparsities of CSF with arbitrary degrees, we obtain the following
bounds,

$\mathsf{sparsity}\Big{(}C^{k}(x)\Big{)}=\mathcal{O}\big{(}n^{\rho}\big{)},\
with\ \rho=\Bigg{(}{\sum_{r\in R_{k},r\leq 6}2^{r-1}+\sum_{r\in
R_{k},r>6}2^{r}-1}\Bigg{)},$ (76)

with $R_{k}\subseteq[\left\lceil\log(k)\right\rceil]$, such that $\sum_{r\in
R_{k}}2^{r}=k$. Likewise, the same bounds will be valid for for SBFs with a
constant degree,

$\mathsf{sparsity}\big{(}f(x)\big{)}=\mathsf{sparsity}\big{(}C^{k}(x)\big{)},\
with\ k=\mathsf{deg}(f(x))\ .$ (77)

Notice that any CSF that resorts uniquely to the multi-linear polynomials from
Lemma 2 in their decomposition (Equation (28)) has an upper bound of
$\mathcal{O}(n^{k/2})$. This bound holds for all CSF with a degree equal to or
smaller than 127. For these instances the upper bound is tight to the
conjectured lower bound. This indicates that if the general form for multi-
linear polynomials identified in Lemma 2 is proven correct, then all CSF
functions would have an upper bound tight to the conjectured lower bound. Yet,
without this proof, the best upper bound is the one described by Equation
(76). In Figure 4 we represent this newly obtained upper bound, together with
the lower bound.

In summary, the CSF construction, in combination with the use of sparse multi-
linear polynomials, considerably lowers the number of qubits required to
evaluate SBF in the NMQC⊕, as well as the respective upper bounds.
Furthermore, the sparsities for SBF functions can be described as depending on
a subset of CSFs. This suggests that the effort to reduce the sparsities of
SBFs should be guided towards the subset of CSF.

Figure 4: Representation of the relations between the individual CSF (ordered
by degree) and the asymptotic growth rate of the GHZ state necessary for
deterministic evaluation with the NMQC⊕ model. The continuous black line
represents the most compact polynomials identified in [22]. The dashed dark
blue line represents the most compact polynomials constructed using the
decomposition from Proposition 1 and the multi-linear polynomials from Lemma
2. Additionally, the red triangles are the CSF computed exactly with the
polynomials from Lemma 2. Finally, the dotted grey line represents our
conjectured lower bound for the set of CSF (Conjecture 2).

##  5 Circuit realization of the NMQC⊕ model

###  5.1 NMQC⊕ circuits

This subsection translates the measurement assignments for the NMQC⊕ model
discussed in the paper into realizable computations. This analysis is
pertinent because the previous works related to this precise model have
discussed these computations at an abstract level only. In other words, they
do not describe them as circuits composed of elementary operations from a
fixed gate set. Here we provide a more complete picture of the computational
process, describing the necessary operations to create the GHZ states,
characterizing the circuits that compute the auxiliary linear functions, and
synthesizing or approximating the required measurement operators, keeping in
mind that the latter are rarely part of the fixed gate set.

This will enable a more direct comparison with fully classical circuits for
Boolean function evaluation, in particular with respect to depth, which is
associated with the temporal extension of these circuits.

######  Definition 17.

(Depth). The depth of an NMQC⊕ circuit is equal to the size of the longest
sequence of elementary gates, quantum or classical, in it.

The width of the circuits, which describes the maximal computational space
occupied during the execution of the circuits, will be equally important.
Generally, parallelizable processes can have a smaller depth but at the cost
of a larger width.

######  Definition 18.

(Width). The width of an NMQC⊕ circuit is equal to the largest number of
elementary gates, quantum or classical, executed simultaneously in it.

The last property that we will account for is the number of gates that the
circuits contain. This value relates to previous properties and is also an
essential element for general computations as it defines the cost of an
evaluation in absolute terms.

####  5.1.1 Linear pre- and post-processing circuits

The subroutine for the linear pre-processing computes all the linear functions
that are part of a specific measurement assignment for a Boolean function. In
particular, it contains a number of linear functions equal to the number of
necessary qubits in the GHZ state. This number is defined by the sparsity of
the multi-linear polynomial that generates the measurement assignment.
Furthermore, each of these linear functions, $L_{i}=\oplus_{i\in S}x_{i}$, can
be highly parallelized, creating a circuit composed of XOR gates with a depth
of $\log_{2}(|S|)$, a width of $|S|$, and a number of gates equal to $|S|-1$
(Figure 5 (a)). Consequently, the total subroutine is the parallel composition
of all linear functions (Figure 5 (b)). Thus, it has a depth of $max\\{|S|\
\big{|}\ \widehat{f}(S)\neq 0\\}$, a width of
$\sum_{S\subseteq[n]}|S|*\delta\big{(}\widehat{f}(S)\big{)}$, and a number of
gates equal to
$\sum_{S\subseteq[n]}\big{(}|S|-1\big{)}*\delta\big{(}\widehat{f}(S)\big{)}$,
based on the Fourier coefficients $\widehat{f}(S)$ of the multi-linear
polynomial $\mathsf{poly}_{f}(x)$ equivalent to the measurement assignment.

Likewise, the linear post-processing circuit of an NMQC⊕ computation is a very
simple subroutine. It solely sums all the measurement outcomes linearly,
computing the parity of the bit string. The computation of this linear
function can also be parallelized such that the circuit will have a depth of
$\log_{2}(k)$ with $k=\mathsf{sparsity}(\mathsf{poly}_{f})$888 We will label
$k$ as the sparsity of the multi-linear polynomial that defines the
measurement assignment repeatedly throughout this section. , a width of $k$,
and $k-1$ gates.

Figure 5: a) The general form and dimensions of a circuit computing a linear
function with $|S|$ inputs. b) Parallel composition of the linear functions in
the linear pre-processing routine.

####  5.1.2 GHZ state creation

Let us review two different circuit families used to create GHZ states. The
first one is more efficient considering the number of gates while having a
simpler process. However, the second compensates for the complexity and the
additional operations with the capacity to prepare a GHZ state with any number
of qubits in constant quantum depth.

(a) Construction in logarithmic quantum depth

The first construction, defined in [53], creates a $n$-qubit GHZ state from
$n$ qubits initially in the $\ket{0}$ state using only CNOT and H gates. For
that, it applies a single H gate to the first qubit and a sequence of CNOT
gates in a cascade pattern afterward. In particular, the first CNOT gate takes
the first qubit as the control qubit and the qubit in position $n/2$ as the
target. Then, in the second layer, two CNOT gates are applied, the first
qubits and the qubit in position $n/2$ action as control, and the qubits in
positions $n/4$ and $3n/4$ as the target qubits of these gates. This pattern
repeats layer after layer, applying twice the number of CNOT gates of the
previous layer while using the already entangled qubits as the control qubits
and non-entangled qubits as targets. For an illustration of this process, see
Figure 6 (a).

It is interesting to characterize this process for a specific
NMQC⊕computation. Given a GHZ state with a number of qubits equal to the
sparsity $k$ of the polynomial is necessary, the corresponding circuit will
have a depth of $\log_{2}(k)$, a width of $k$, and the circuit contains
$\mathcal{O}\big{(}k\big{)}$ gates.

(b) Construction in constant quantum depth

The second technique considered to create GHZ states is particularly
interesting because it uses only a constant number of quantum layers to
generate a GHZ with an arbitrary number of qubits [73, 46]. Nevertheless,
these fixed quantum layers have to be interleaved with classical computations
of logarithmic size, which results in a total depth - adding quantum and
classical processing - similar to the previous one. Also, the method relies on
adaptively chosen quantum operations, which depend on previously obtained
measurement outcomes. This adaptivity could be a problem as we are considering
a non-adaptive measurement-based quantum computation model. However, as this
adaptivity does not depend on the input string or the specific computation
that will be performed, we consider this a valid alternative.

The specific protocol presented in [73] creates a $n$-qubit GHZ state from $n$
qubits in the $\ket{0}$ state using six layers of quantum gates. The first
quantum layer applies $H$ gates to odd-numbered qubit wires. Then, the second
quantum layer applies $n/2$ CNOT gates between neighboring qubit pairs, with
odd-numbered control qubit wires and even-numbered target qubit wires. After
this process, $n/2$ Bell pairs were created. The third quantum layer applies
$n/2-1$ CNOT gates between the qubits of neighbouring Bell pairs, such that
one qubit of the Bell pair is a target qubit for the previous Bell pair, and
the other is the control qubit for the next Bell pair. Afterward, the next
quantum layer (the fourth) measures all the qubits which were target qubits of
the CNOT gates applied in the previous process. Then, the results of the
previous measurements define an $X$ correction that will be applied in the
fifth quantum layer. In particular, such $X$ corrections will be applied to
the qubits directly below the measured qubits, and they depend on the parity
of all the measurement outcomes previous to that specific qubit.
Simultaneously, in the fifth layer, the measured qubits are reset. Finally,
the sixth and final quantum layer entangles the qubits recycled to the
$\ket{0}$ state after the measurement, with the resulting quantum state. An
illustration of the whole process is depicted in Figure 6 (b).

In the end, for an NMQC⊕ computation, this process produces a quantum state
with a number of qubits defined by the sparsity of the respective multi-linear
polynomial. This implies that the depth of the respective circuit will be
$6+\log_{2}(k/2-1)$, with a width of $k$ and a total number of gates bounded
above by $\frac{k^{2}}{8}+\frac{11}{4}k-4$.

Figure 6: a) Logarithmic depth circuit for the creation of an 8-qubit GHZ
state with a recursive CNOT application pattern. b) Constant quantum depth
circuit with extra linear measurement post-processing the creation of an
8-qubit GHZ state.

####  5.1.3 Measurement operators

The measurement operators imposed by the measurement assignment are generally
not part of the gate set. Therefore, creating these operators from the
available gate set will be necessary. As is common in the literature, we will
consider the Clifford+$T$ gate-set. In particular, we need to generate single
qubit $Z$-rotations because these are always equal to the measurement
operators used by the model after applying a Pauli $X$ operator. Therefore,
the optimal circuit for the measurement operator has at most one extra
elementary gate, followed by the optimal circuit for a particular $Z$-rotation
(Figure 7). This observation allows us to use several established results on
the circuit synthesis of $Z$-rotations [74, 75, 76, 66].

$M_{i}$ & = X R_Z(tiπ2ni)

≈ X H T … S

Figure 7: Exact and approximated circuit synthesis of the measurement
operator. The former is based on arbitrary $R_{Z}$ rotations, the latter on
the Clifford+ $T$ gate set.

The first significant result is that no $R_{Z}(\frac{\pi}{2^{n}})$ operator
for $n\geq 2$ can be exactly synthesized using the Clifford+$T$ gate set [74,
76]. Therefore, using this gate set, Boolean functions with a degree greater
than two cannot be computed deterministically in the NMQC⊕ model.

######  Corollary 2.

No Boolean function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ with
$\mathsf{deg}(f)\geq 3$ can be computed deterministically with the NMQC⊕ model
realized with the Clifford+$T$ gate set.

###### Proof.

The proof follows from the fact that all the measurement operators necessary
for evaluating Boolean functions with a degree greater than two are in third
level or higher of the Clifford hierarchy, as proven in [22]. Therefore, each
one of these measurement operators is equivalent to a $Z$-rotation of
magnitude $\frac{\pi}{2^{n}}$ with $n\geq 2$. Thus, it is impossible to
synthesize these gates exactly with the Clifford+$T$ gate set [74, 76], and
the whole NMQC⊕ computation will have a non-zero error term. ∎

This critical implication imposes that higher degree Boolean functions can
only be computed with a certain accuracy that depends on the approximation of
the measurement operators.

For our purpose, we will need to define approximations that guarantee a
certain level of accuracy $\epsilon\in[0,1]$ of the NMQC⊕ computations. For
that, a relationship between the approximations of the $Z$-rotations and the
whole computation is required. From [74], it is possible to define the
approximation of a $Z$-rotation concerning the operator norm for an arbitrary
distance $\bigtriangleup$,

$\bigtriangleup\geq\Big{|}\Big{|}R_{Z}^{\ast}\Big{(}\frac{\pi*t}{2^{n}}\Big{)}\ket{\Psi}-R_{Z}\Big{(}\frac{\pi*t}{2^{n}}\Big{)}\ket{\Psi}\Big{|}\Big{|}\
.$ (78)

with $R_{Z}^{\ast}$ representing the approximated $Z$-rotation, using a
circuit with approximately $K+4\log_{2}(1/\bigtriangleup)$ 999$K$ is
approximately 10, and this value was proven to be lower bounded by -9.
Therefore, the algorithm from [74] produces approximations that are at most an
additive constant from the optimal $Z$-approximations.  $T$-gates. Therefore,
the approximation of each single measurement operator $M_{i}$, to be applied
to one of the $k$ qubits in GHZ state, is bounded by

$\displaystyle\bigtriangleup_{i}\geq\ $
$\displaystyle\Big{|}\Big{|}\bigotimes_{j=0}^{i-1}I_{j}\otimes
M_{i}\otimes\bigotimes_{l=i+1}^{k}I_{l}\ket{\Psi}-\bigotimes_{j=0}^{i-1}I_{j}\otimes
M_{i}^{\ast}\otimes\bigotimes_{l=i+1}^{k}I_{l}\ket{\Psi}\Big{|}\Big{|}$ (79)
$\displaystyle\geq\ $
$\displaystyle\Big{|}\Big{|}M_{i}\ket{\Psi}-M_{i}^{\ast}\ket{\Psi}\Big{|}\Big{|}$
(80) $\displaystyle\geq\ $
$\displaystyle\Big{|}\Big{|}\sigma_{x}R_{Z}\Big{(}\frac{\pi*t_{i}}{2^{n_{i}}}\Big{)}\ket{\Psi}-\sigma_{x}R_{Z}^{\ast}\Big{(}\frac{\pi*t_{i}}{2^{n_{i}}}\Big{)}\ket{\Psi}\Big{|}\Big{|}$
(81) $\displaystyle\geq\ $
$\displaystyle\Big{|}\Big{|}R_{Z}^{\ast}\Big{(}\frac{\pi*t_{i}}{2^{n_{i}}}\Big{)}\ket{\Psi}-R_{Z}\Big{(}\frac{\pi*t_{i}}{2^{n_{i}}}\Big{)}\ket{\Psi}\Big{|}\Big{|}\
.$ (82)

Then, we assume that all the measurement operators have the same error bound
$\bigtriangleup$. Also, as all these measurement operators commute, one can
interpret that they are applied sequentially, allowing us to bound the error
after all the measurements by the sum of all the individual errors [77],

$\displaystyle k*\bigtriangleup=\sum_{i=0}^{k}\bigtriangleup_{i}\geq\ $
$\displaystyle\Big{|}\Big{|}\bigotimes_{i=0}^{k}M_{i}\ket{\Psi}-\bigotimes_{i=0}^{k}M_{i}^{\ast}\ket{\Psi}\Big{|}\Big{|}$
(83) $\displaystyle\ .$ (84)

Finally, we can use the fact that the total deviation distance between the
resulting probability distributions between the ideal quantum state that
computes the Boolean function deterministically and the resulting quantum
state is at most four times the norm error defined for the quantum state [77],
such that,

$\displaystyle\epsilon$
$\displaystyle=(-1)^{f(x)}-\bra{\Psi_{GHZ}^{k}}\otimes_{i=1}^{k}M_{i}(s_{i})\ket{\Psi_{GHZ}^{k}}$
(85) $\displaystyle\geq 4*k*\bigtriangleup$ (86)

After determining the relation between the total error of the computations and
the local errors due to the measurement operators, one can define a specific
number of $T$ gates necessary for a certain precision $\epsilon$ of the NMQC⊕
computation. In particular, the corresponding circuit will have a depth of
$4*c*\log_{2}(\frac{4k}{\epsilon})=4*c*(2+\log_{2}(k)+\log_{2}(\frac{1}{\epsilon}))$
with $c$ equal to a constant that accounts for all the additional gates in the
circuit, which are generally proportional to the number of $T$ gates [70]
101010In reference [70], this constant appears to be close to 2.5. However,
for our analysis, we will leave it undefined. Additionally, we end up with a
width of $k$ and a total number of gates that is bounded by
$4*c*k*\log_{2}(\frac{4k}{\epsilon})$.

####  5.1.4 Depth, width and number of gates

To characterize the NMQC⊕ circuits, we will combine the previously described
subroutines. In particular, we will combine them to minimize the circuit
depth. Therefore, the linear pre-processing and the GHZ state generation will
be performed simultaneously, as they have no dependencies. Then, the results
of the linear functions define the set of operations that will be realized on
the GHZ-state qubits in the measurement process. Then, the linear post-
processing will compute the parity of the measurement outcomes to obtain the
output of the Boolean function. The whole process is represented in Figure 8.

With the architecture of the circuits defined, it is possible to characterize
the relevant properties resulting from specific measurement assignments. In
particular, the multi-linear polynomials associated with the measurement
assignments completely determine the circuits’ depth, width, and number of
gates.

######  Lemma 9.

Any Boolean function $f:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ with
$\mathsf{deg}(f)>2$ can be computed with accuracy $\epsilon\in[0,1]$ based on
a valid measurement assignment using a circuit composed of the Clifford+T gate
set with a depth of

$2*\log_{2}(k)+4*c*\Big{(}2+\log_{2}(k)+\log_{2}\Big{(}\frac{1}{\epsilon}\Big{)}\Big{)},$
(87)

a width of

$k+\sum_{S\subseteq[n]}\big{(}|S|-1\big{)}*\delta\big{(}\widehat{f}(S)\big{)}\
,$ (88)

and a number of gates bounded by

$\sum_{S\subseteq[n]}\big{(}|S|-1\big{)}*\delta\big{(}\widehat{f}(S)\big{)}+k*\Big{(}2+4*c*\Big{(}2+\log_{2}(k)+\log_{2}\Big{(}\frac{1}{\epsilon}\Big{)}\Big{)}\Big{)}\
.$ (89)

W.l.o.g $\widehat{f}(S)$ are the Fourier coefficient and $k$ the sparsity of
the multi-linear polynomial corresponding to the measurement assignment that
will be realized.

###### Proof.

Follows from the arguments above. ∎

It is essential to mention that we used the GHZ construction of Subsection
5.1.2 , with logarithmic depth. If constant quantum depth methods were used, a
slight difference in the depth and the number of gates will be introduced.
Nevertheless, the order of magnitude of the depth would not change. Moreover,
the depth necessary to approximate the measurement operators can, in
principle, be reduced with other circuit synthesis techniques [78, 79].
However, the width of the circuits would increase with the use of auxiliary
qubits. In addition, we recall that the proposed solution does not guarantee
the optimal realization of a given measurement assignment concerning each one
of the metrics for the circuits.

Although there is a large variability in the possible realizations of a
measurement assignment, we consider that the particular translations presented
unravel essential details and questions about the NMQC⊕ model. For instance,
one could question if there is another gate set that guarantees the exact
synthesis of the measurement operators. That existence would allow
deterministic computations for Boolean functions with an arbitrary degree.
However, in [66], various gate sets were considered, and none had a particular
advantage, nor could they exactly synthesize arbitrary $Z$-rotations. This
suggests that computing Boolean functions with an arbitrary degree could be a
general limitation of the NMQC⊕ model that only adaptivity can bypass.

Figure 8: A schematic representation of the circuit realization proposed for
the NMQC⊕ model. Vertically aligned processes are performed in parallel, while
horizontally aligned processes are performed sequentially.

###  5.2 Quantum vs. classical circuits

In this last subsection, we compare the known upper and lower bounds on
classical circuits for Boolean function evaluation with quantum circuits
evaluating the same functions in the NMQC⊕ model. In particular, this
comparison will focus on symmetric Boolean functions. This choice is justified
by the contributions to the case of symmetric Boolean functions discussed in
this paper and the many results on symmetric functions that can be found in
the classical circuit complexity literature [80, 81, 82, 83, 58].

####  5.2.1 Degree two symmetric Boolean functions

The translation of NMQC⊕ computations from an abstract description to explicit
circuits has shown that degree two Boolean functions are particularly
interesting as they evaluate deterministically. Thus, their circuits’ depth
and number of gates do not depend on a prescribed level of approximation
accuracy. Furthermore, we were fortunate to observe that some of these
functions stand on the edge of the best lower bounds known for their classical
circuit size [84]. In particular, this allows us to notice that there is at
least one family of symmetric Boolean functions of degree two with a
logarithmic advantage over any conceivable classical circuit. The advantage
exists in terms of width and number of gates, considering that the classical
circuits can be formed by Boolean operations from the full basis
$\\{\mathsf{AND},\mathsf{OR},\neg,\mathsf{XOR},\mathsf{NAND},etc.\\}$.

######  Theorem 5.

Any classical circuit with unary and binary Boolean operators with single fan
out computes the complete symmetric function of degree two $C^{2}$ with
$\Theta(n*\log_{2}(n))$ gates and circuit width. In contrast, realizations of
the NMQC⊕ model compute this function with $\Theta(n)$ gates and circuit
width.

###### Proof.

It will be necessary to show that the upper and lower bounds have the same
scaling rate for both functions in both circuit classes. Considering first the
classical circuits, we can relate the $C^{2}$ function with the counting
functions described in [84]. This is possible because these functions are
defined as $\mathsf{Count}(x,k)=1\ $if $\sum_{i=0}^{n}x_{i}\ mod\ k=0$.
Therefore

$\mathsf{Count}(x,4)=\neg\big{(}C^{2}(x)\big{)}\ \mathsf{AND}\
\neg\big{(}C^{1}(x)\big{)}$ (90)

provided that $C^{2}(x)$ and $C^{1}(x)$ represent the two least significant
bits of the Hamming weight $|x|$. Then it is possible to relate the length of
the Boolean formulas of $\mathsf{Count}(x,4)$ and $C^{1}(x)$ with the length
of the formulas for $C^{2}(x)$,

$\displaystyle L(\mathsf{Count}(x,4))$ $\displaystyle\leq
L(C^{2}(x))+L(C^{1}(x))$ (91) $\displaystyle
L(\mathsf{Count}(x,4))-L(C^{1}(x))$ $\displaystyle\leq L(C^{2}(x))\ .$ (92)

From these relations between the length of the formula and the lower bound of
$\varsigma n\log_{2}(\frac{n}{4})$ with $\varsigma\in[0,1]$ for
$L(\mathsf{Count}(x,4))$ and the exact scaling of $n$ for $L(C^{1}(x))$, we
obtain that $L(C^{2})\geq\varsigma n\big{(}\log_{2}(\frac{n}{4})-1\big{)}$
[84]. Thus, $\Omega\big{(}L(C^{2}(x)\big{)}=n*log(n)$.

The upper bound of $L(C^{2}(x))$ is simply obtained by considering the
following expression

$C^{2}(x)=\bigoplus_{i=1}^{log_{2}(n)}\Big{(}\bigwedge_{j=0}^{2^{i}-1}\Big{(}\bigoplus_{k=j*\frac{n}{2^{i}}}^{(j+1)\frac{n}{2^{i}}}x_{k}\Big{)}\Big{)}\
,$ (93)

from which we obtain that
$L(C^{2}(x))\leq\mathcal{O}\big{(}n*\log_{2}(n)\big{)}$. Consequently, we
conclude that $L(C^{2}(x)=\Theta\big{(}n*\log_{2}(n)\big{)}$. Finally, if
circuits are composed of unary and binary operators with a single fan-out, the
number of gates equals the Boolean formula’s length [80]. In addition, the
circuit width also scales with the size of the formula and the depth with
$\log_{2}(L(C^{2}(x))$.

For the NMQC⊕ circuit realization of the $C^{2}(x)$ function, one can consider
the multi-linear polynomials from Lemma 2. These have a sparsity of $n+1$ and
have been proven optimal in [20]. Therefore, the process described in section
5.1 translates these to quantum circuits with a number of gates and width of
$\Theta(n)$. Also, the computations are deterministic, given that the
measurement operators can be synthesized exactly for Boolean functions with a
degree equal to two. ∎

This separation is based on a single family of symmetric Boolean functions.
However, this can be enlarged to all the functions in the $[AC^{k}]$ class for
which the symmetrized function is $C^{2}$. The explanation is that all these
functions will have an NMQC⊕ realization with a number of gates scaling with
$n$ based on Lemma 4. On the other hand, classical circuits for those
functions scale with $n*\log_{2}(n)$ in width and number of gates.

Moreover, suppose one argues that this circuit separation is still not strong
enough because it misses to account for the necessary repetitions of the input
strings. For that matter, we can show that the process that generates these
repetitions for the NMQC⊕ circuits will always be more efficient. In
particular, it is sufficient to verify that the classical circuits require
more copies of the input string than the NMQC⊕ circuits. The classical
circuits require a number of copies scaling with $\log_{2}(n)$, while the
quantum solution requires only a single copy of the input string. This single
copy is enough because it can be used to compute the parity while the given
input string provides all the single bits that control the rotations necessary
to evaluate the function (Lemma 34). Therefore, if the cost related to this
process was included, the gap between the quantum and the classical circuits
would further increase.

Another possible counter-argument relates to the depth of the circuits. We
obtained a quantum circuit family for the specific $C^{2}$ function whose
depth scales with $2\log_{2}(n)$, while the classical circuit scales only with
$\log_{2}(n)+\log_{2}(\log_{2}(n))$. Consequently, they scale with the same
asymptotical rate of $\mathcal{O}(\log(n))$. Although one could argue that
there will be an asymptotical constant advantage equal to two in the classical
case, this constant depth advantage is insignificant compared to the
logarithmic width and gate advantage, which grows infinitely. Also, one could
exclude the GHZ state preparation from the evaluation process and address it
as polynomial size advice. This assumption is justified by state preparation
is independent of the input. In that case, the $C^{2}$ function could be
evaluated with a depth of $\log_{2}(n)+7$, producing a small additive
advantage of $\log_{2}(\log_{2}(n))$ in comparison to the optimal classical
circuits for which we do not know any equivalent advice.

######  Lemma 10.

Suppose an $n+1$-qubit GHZ state is provided for an NMQC⊕ computation. Then,
the complete symmetric function of degree two $C^{2}$ can be evaluated with a
depth equal to $\log_{2}(n)+7$.

###### Proof.

Considering the measurement assignment that results from the multi-linear
polynomial of Lemma 2, there are $n$ measurements that depend directly on the
input bits. These can be measured and their output linearly summed while the
linear side computer determines $\oplus_{i=0}^{n-1}x_{i}$. When the linear
side computer finishes, the last qubit is measured in the determined basis,
and the outcome will be included in the linear post-processing. Therefore, the
depth of the computations will be equal to or smaller than the depth of
operations associated with the measurements, plus the linear post-processing.
The measurement process for degree two Boolean function can be executed in 6
layers using only gates of the Clifford+$T$ gate set, given that the control
Pauli $X$ and $Y$ gates can be synthesized within that length. Thus, this
value is summed to the linear post-processing, which has a depth bounded by
$\log_{2}(n)+1$, obtaining a total depth bounded by $\log_{2}(n)+7$. ∎

We believe this is an interesting quantum-classical separation result because
it does not depend on any conjecture. Also, it is proven at the level of
circuits 111111Boolean formulas are a subclass of circuits because they lack
memory. Therefore, they are believed to be weaker than circuits that could
reuse sub-computations. However, it is still open if the class of poly-size
circuits is larger than the class of poly-size Boolean formulas [85]. , which
is typically very difficult to do based on the difficulty of proving classical
or quantum circuit lower bounds [86]. A related and stronger finding was the
breakthrough result of [39] that identified a class of search problems with a
more significant quantum-classical separation on the circuit level. Other
separations at the circuit level were found in cases where the computational
space was reduced [49, 48, 87]. These demonstrated a width advantage for
quantum circuits at a small and fixed size. In comparison, our result does
seem to indicate that this width advantage could scale for computations
without limited space. Other separations of larger magnitude have been found
[88, 89, 7, 90]. However, most of these are proven under the assumption of
black boxes or query complexity [86]. Thus, they are not proven under the more
physically realistic assumptions we consider here.

Furthermore, we observe that Theorem 5 implies that there exists a dimension
of the input string above which the NMQC⊕ evaluation of the $C^{2}$ functions
starts to be more efficient than any classical circuit evaluation based on
Boolean formulas. This point is particularly interesting because one can
relate this NMQC⊕ evaluation to the generalized Svetlichny inequalities
121212The connection of NMQC⊕ evaluations and Bell inequalities was
established in a one-to-one relation by the authors of [20].. Therefore, by
doing this, we conclude that starting from some specific number of qubits, a
maximal violation of the generalized Svetlichny inequalities, with a quantum
state and measurement operators that can be prepared with a linear number of
operations, simultaneously proves a circuit separation. This observation
connects separations related to communication problems to circuit problems.
Also, the magnitude of the separations is intriguing as one is exponential,
and the other is only logarithmic for the function at hand.

####  5.2.2  Higher degree symmetric Boolean functions

To analyze higher degree symmetric Boolean functions, we isolate first the
functions with degree three. This differentiation occurs because we identified
a family of symmetric Boolean functions that presents a logarithmic advantage
between the size of their measurement assignments and their optimal Boolean
formulas. In particular, this family of Boolean functions refers to the
$\mathsf{Count}(x,4)$ function described in the proof of Theorem 5. It is
possible to find measurement assignments for these functions with sparsity
equal to $2n+2$, based on Equation (90), Lemma 2 and Lemma 8. In addition,
their Boolean formulas are lower bounded by $\varsigma n\log_{2}(n)$, with
$\varsigma\in[0,1]$.

Although we identified a separation at an abstract level, it almost disappears
when these measurement assignments are translated to circuits. The depth of
the circuit has an additional term for functions with a degree equal to or
greater than three (Lemma 9). This implies that the depth of the resulting
circuits is at least twice the classical depth. Also, the number of gates will
scale efgas $n*\log_{2}(n)$, similarly to what happens in classical circuits.
Therefore, the remaining advantage presents itself with the width of the
quantum circuits being logarithmically smaller. However, the computation has
an error term that does not exist in the classical case. A fair comparison
would require the consideration of probabilistic classical circuits. We leave
the analysis between the probabilistic efgcase and circuits with different
depth and width relations for future work.

For higher degree functions, we use the bounds of the Boolean formulas
identified for the Counting functions, with the modular division fixed to a
power of two, to define upper bounds for the complete symmetric functions.

######  Lemma 11.

The Boolean formula of any CSF $L\big{(}C^{k}\big{)}$ is bounded by
$\mathcal{O}\big{(}n\log_{2}(n)^{\left\lfloor\log_{2}(k)\right\rfloor}\big{)}$.

###### Proof.

First, the relation between the Counting functions and the CSFs for powers of
two can be established by generalizing Equation (90) to
$\mathsf{Count}(x,2^{p})=\bigwedge_{i=1}^{p-1}\ \neg C^{2^{i}}$. Then, this
allows us to relate Boolean formulas such that

$\displaystyle L(C^{2^{p-1}})$ $\displaystyle\leq
L\big{(}Count(x,2^{p})\big{)}+L\Big{(}\bigwedge_{i=1}^{p-2}\ \neg
C^{2^{i}}\Big{)}$ (94) $\displaystyle\leq
L\big{(}Count(x,2^{p})\big{)}+\sum_{i=1}^{p-2}L\big{(}C^{2^{i}}\big{)}$ (95)

Then, one can establish the upper bounds recursively for all CSF of the form
$C^{2^{p}}$ by using these relations, starting from the fact that
$L(C^{1})=n$, and sequentially use the upper bounds of
$\mathsf{Count}(n,2^{p})$. In particular, the upper bounds of such Counting
functions are
$L(\mathsf{Count}(n,2^{p}))=\mathcal{O}\big{(}n*\log_{2}(n)^{p-1}\big{)}$.
Therefore, we obtain
$L\big{(}C^{2^{p}}\big{)}=\mathcal{O}\big{(}n*\log_{2}(n)^{p}\big{)}$ as the
upper bound for the corresponding Boolean formulas. Finally, using Lemma 1,
one can generalize the bound to arbitrary degrees of the CSFs given that

$\displaystyle L\big{(}C^{k}\big{)}\leq\sum_{r\in
R_{k}}L\big{(}C^{2^{r}}\big{)},$ (96)

with $R_{k}\subseteq[\left\lceil\log(k)\right\rceil]$, such that $\sum_{r\in
R_{k}}2^{r}=k$. This relation demonstrates that the largest CSFs present in
its decomposition into powers of two will define the upper bound, combining
this results with the bounds established for those values, we conclude the
proof. ∎

In comparison, our lower bound conjecture indicates that no symmetric
measurement assignment in the NMQC⊕ model can compute the CSF $C^{k}$ with
less than $n^{\left\lfloor k/2\right\rfloor-1}$ qubits (Conjecture G).
Therefore, unless our conjectured lower bound deviates immensely when non-
symmetric measurement assignments are considered, the NMQC⊕ computations have
a polynomial disadvantage compared to the classical circuits. In particular,
these would materialize in constant depth, polynomial width, and polynomial
gate advantages for the classical circuits.

Moreover, given the lower bounds known from [20, 21], and the previous
analysis, the NMQC⊕ model is suspected to be computationally inefficient for
higher degree Boolean functions. Actually, it cannot even evaluate those
functions deterministically with the Clifford+$T$ gate set (Corollary 2).
These results point to the importance of adaptivity for deterministic
computations for an MBQC model. Remember that if an adaptive process is
allowed, then a circuit composed of individual NMQC⊕ computations can
replicate any classical and deterministic circuit [10]. Similarly, the results
of [11] and [12] constructively describe the process of reaching determinism
via adaptive measurement patterns for universal quantum computations.

##  6 Discussion and conclusions

We investigated the problem of evaluating deterministically Boolean functions
in the NMQC⊕ model, providing new constructions and a more precise
understanding of the necessary instructions for each stage of the model. We
characterized the complexity of two resources in this model: the number of
required qubits in a GHZ state, and the required level of the Clifford
hierarchy for single-qubit measurements. Regarding the number of qubits in a
GHZ state, we lowered the upper bound for the number of qubits required to
evaluate the entire set of symmetric Boolean functions and conjectured a lower
bound for this same set, assuming symmetries between the instructions of the
process. Regarding the complexity of the measurements required, we proved an
upper bound on the level of the Clifford hierarchy. In particular, this bound
is proven to be tight to the boundary identified in [22], which limits the
degree of the Boolean functions that a set of operators can evaluate. In the
end, we translated the examined NMQC⊕ evaluations to possible circuit
realizations. This translation motivated our main result demonstrating a
circuit separation for a family of degree two SBFs. Moreover, we analyzed