[2][1=]linecolor=grey,backgroundcolor=grey!25,bordercolor=grey,#1linecolor=grey,backgroundcolor=grey!25,bordercolor=grey,#1todo:
linecolor=grey,backgroundcolor=grey!25,bordercolor=grey,#1#2
[2][1=]linecolor=blue,backgroundcolor=blue!25,bordercolor=blue,#1linecolor=blue,backgroundcolor=blue!25,bordercolor=blue,#1todo:
linecolor=blue,backgroundcolor=blue!25,bordercolor=blue,#1#2
[2][1=]linecolor=red,backgroundcolor=red!25,bordercolor=red,#1linecolor=red,backgroundcolor=red!25,bordercolor=red,#1todo:
linecolor=red,backgroundcolor=red!25,bordercolor=red,#1#2
[1]linecolor=green,backgroundcolor
=green!25,bordercolor=greenlinecolor=green,backgroundcolor
=green!25,bordercolor=greentodo: linecolor=green,backgroundcolor
=green!25,bordercolor=greenAlex: #1 [1]linecolor=blue,backgroundcolor
=blue!25,bordercolor=bluelinecolor=blue,backgroundcolor
=blue!25,bordercolor=bluetodo: linecolor=blue,backgroundcolor
=blue!25,bordercolor=blueMichael: #1

# The power of shallow-depth Toffoli and qudit quantum circuits

Alex B. Grilo1, Elham Kashefi1,2, Damian Markham1, Michael de Oliveira1,3,
1Sorbonne Université, CNRS, LIP6, France
2School of Informatics, University of Edinburgh, Scotland
3 International Iberian Nanotechnology Laboratory, Portugal
<EMAIL_ADDRESS>
###### Abstract

The relevance of shallow-depth quantum circuits has recently increased, mainly
due to their applicability to near-term devices. In this context, one of the
main goals of quantum circuit complexity is to find problems that can be
solved by quantum shallow circuits but require more computational resources
classically.

Our first contribution in this work is to prove new separations between
classical and quantum constant-depth circuits. Firstly, we show a separation
between constant-depth quantum circuits with quantum advice
$\mathsf{QNC}^{0}/\mathsf{qpoly}$, and $\mathsf{AC}^{0}[p]$, which is the
class of classical constant-depth circuits with unbounded-fan in and
$\pmod{p}$ gates. In addition, we show a separation between
$\mathsf{QAC}^{0}$, which additionally has Toffoli gates with unbounded
control, and $\mathsf{AC}^{0}[p]$. This establishes the first such separation
for a shallow-depth quantum class that does not involve quantum fan-out gates.

Secondly, we consider $\mathsf{QNC}^{0}$ circuits with infinite-size gate
sets. We show that these circuits, along with (classical or quantum) prime
modular gates, can implement threshold gates, showing that
$\mathsf{QNC}^{0}[p]=\mathsf{QTC}^{0}$. Finally, we also show that in the
infinite-size gateset case, these quantum circuit classes for higher-
dimensional Hilbert spaces do not offer any advantage to standard qubit
implementations.

##  1 Introduction

In the current landscape dominated by NISQ (Noisy Intermediate-Scale Quantum)
devices [34], understanding the computational power of shallow-depth quantum
circuits has both practical and theoretical relevance. From a practical
perspective, given the noisy aspect of near-term devices, focusing on tasks
that achieve quantum advantage in low depth is fundamental. From a theoretical
perspective, (classical) constant-depth circuits have been crucial in the
development of lower bound techniques, e.g. [39]. Thus, the combination of
these techniques, along with the computational capabilities of constant-depth
quantum circuits, enables the discovery of new quantum-classical separations
and, furthermore, allow a more comprehensive understanding of quantum
computational complexity classes [40, 24, 19].

The holy-grail in quantum circuit complexity is to find problems that can be
solved by shallow-depth quantum circuits and that cannot be solved by
polynomial-time classical computation. Unfortunately, there are several
caveats in the current approaches. Firstly, the current super-polynomial
quantum advantage proposals rely on computational assumptions, offering no
unconditional proof of quantum superiority. Secondly, some of these results
even require quantum gates with arbitrary accuracy, which cannot be
implemented in practice in real-world devices. This problem is amplified when
infinite gate sets are assumed [9, 3], since it has been shown that even if
precise quantum operations were feasible, the computational overhead for
classical control could destroy any quantum advantage [23].

More recently, there is a new line of research that has addressed some of
these issues, at the cost of achieving weaker statements. More concretely, the
seminal work of [6] has shown a problem that can be solved by constant-depth
quantum circuits ($\mathsf{QNC}^{0}$), and which cannot be solved by constant-
depth classical circuits with bounded fan-in ($\mathsf{NC}^{0}$). We would
like to highlight that while this separation is weaker (since the lower bound
is only against constant depth circuits), it is unconditional, which is rather
rare in complexity theory. Moreover, these proposals also have practical
interest with their extension to include fault-tolerance [7].

The result of [6] has also been extended to achieve better quantum/classical
separations: We currently have separations between quantum constant-depth
circuits and constant-depth classical circuits with unbounded fan-in
($\mathsf{AC}^{0}$), even if the classical circuit has access to $\pmod{2}$
gates ($\mathsf{AC}^{0}[2]$) [44].111We notice that in order to prove the
separation against classical circuits with parity gates, the quantum circuit
has access to quantum advice. In these results, showing the quantum upper
bound is fairly easy and the main difficulty is in the classical lower bound.
The main challenge lies in finding new classical lower bounds techniques that
allow us answer the question:

What is the largest class of classical circuits that we can separate from
constant-depth quantum circuits?

The main contribution of this work is to prove new separations between
constant-depth quantum circuits and constant-depth classical circuits.
Additionally, we revisit quantum circuits with infinite gateset and prove new
collapses of different quantum circuit classes.

###  1.1 Our contributions

Our first contribution is showing that a set of relation problems for which we
have constant-depth quantum circuits on qudits with quantum advice and is not
contained in $\mathsf{AC}^{0}[p]$.

######  Result 1.

(Informal; see Theorem 17) For all primes $p$, there exists a finite gate set
on qudits of dimension $p$ such that constant-depth quantum circuits with
quantum advice can solve relation problems that are intractable for any
polynomial-size $\mathsf{AC}^{0}[p]$ circuit, i.e.,
$\mathsf{QNC}_{p}^{0}/\mathsf{qpoly}\nsubseteq\mathsf{AC}^{0}[p].$

This result extends the $\mathsf{AC}^{0}[2]$ separation from [44] to general
primes. To prove it, we generalize the relation problems on modular operations
that have been used in [6, 44]. Roughly, our modular relation problems with
parameters $p,q\in\mathbb{N}$ consist of a pair of bit strings $(x,y)$ such
that $|x|\pmod{p}=0$ iff $|y|\pmod{q}=0$. Here, $|x|$ and $|y|$ represent the
Hamming weights of the respective bit strings. We show that by exploiting
higher-dimensional gate sets, we can solve these problems in constant-depth
quantum circuits with a copy of a high-dimensional GHZ state. At the same
time, we expand the classical lower bound to $\mathsf{AC}^{0}[p]$. However,
this separation achieves only a quantum/classical distinction regarding error
probabilities, which differ by a constant value. In order to improve these
separations, we then consider the parallel repetition of these modular
problems as proposed in [44, 13]. In our results, we simplify the proof of
[44] by considering the one-sided error of the quantum circuits and using
“seminal results” in circuit complexity such as the Vazirani XOR lemma [16]
and Razborov-Smolensky separations [41].

We follow by showing that $\mathsf{QAC}^{0}$ circuits, without quantum fanout
gates but permitting the fanout of classical information, can generate high-
dimensional GHZ states. For this, we employ optimal depth and size methods for
GHZ state creation, which is based on poor-man’s cat states and balanced
binary trees as the resource state entanglement structure. This gadget, along
with Result 1, allows us to show that for every prime $p$, there exists a
constant-depth quantum circuit employing Toffoli gates of dimension $p$ that
computes a relation unattainable by any polynomial-size $\mathsf{AC}^{0}[p]$
circuit. Moreover, when Toffoli gates of arbitrary arity can implement any
qubit operation, we attain an unconditional separation between this complexity
class and all $\mathsf{AC}^{0}[p]$ classes simultaneously. It is worth noting
that this aligns with the standard definition of $\mathsf{QAC}^{0}$ as
outlined in existing literature [32, 38, 14, 4] while including classical and
excluding quantum fanout, and that recent research and practical
demonstrations have suggested that some platforms quantum devices inherently
support multi-qubit operations which would enable the construction of multi-
qubit Toffoli gates [28, 20, 21, 8].

######  Result 2.

(Informal; see Theorem 18) For every prime $p$, there is a relation problem
that can be solved by $\mathsf{QAC}^{0}$ circuits without quantum fanout,
whereas any $\mathsf{AC}^{0}[p]$ circuit of polynomial size solves it with a
negligible probability. Therefore,
$\mathsf{QAC}^{0}\nsubseteq\mathsf{AC}^{0}[p]$ holds for all prime $p$.

This establishes the first separation between $\mathsf{QAC}^{0}$ and
$\mathsf{AC}^{0}[p]$ for any prime $p$, which was recently asked in [38]. We
notice that in order to achieve such a result with our techniques, it is
crucial to consider qudits of higher dimensions. Additionally, we remark that
$\mathsf{QAC}^{0}$ can generate a GHZ state without the need for unbounded
parity gates, as proposed in [38]. Our $\mathsf{QAC}^{0}$ circuits use quantum
measurements and adaptive operations to generate the quantum states.
Surprisingly, the capability to produce this state does not imply the
capability to compute the parity function. We conjecture that generating the
GHZ state through a unitary procedure (i.e. without measurements) would
require quantum fanout or parity gates. Thus, the question of whether the
parity function can be computed in $\mathsf{QAC}^{0}$ without fanout gates
remains open for further investigation [30].

Next, we provide some limitations on our techniques by showing a classical
upper bound on the modular relation problems that we consider.

######  Result 3.

(Informal; see Lemma 19) For every primes $p,q$, the modular relation problem
on strings $(x,y)$ such that $|x|\pmod{p}=0$ iff $|y|\pmod{q}=0$ can be solved
by $\mathsf{NC}^{0}[q]$ circuits. 222These circuits are composed of bounded
fan-in gates, as in $\mathsf{NC}^{0}$, but additionally contain a single
unbounded fan-in $\mathrm{MOD}_{p}$ gate.

We notice that this result was unknown even for $p=2$ and it characterizes
$\mathsf{AC}^{0}[p]$ as the largest constant-depth classical circuit class for
which a quantum-classical separation can be identified using our proposed
relation problems. To achieve separations against classes like
$\mathsf{TC}^{0}$ (or larger classes), one needs to consider a different class
of problems such as [19]. However, it is conjectured that this particular set
of modular relation problems is sufficient to achieve unconditional
separations between the aforementioned $\mathsf{AC}^{0}[p]$ classical circuit
classes and less powerful quantum circuit classes, such as $\mathsf{QNC}^{0}$.

We then switch gears and consider the class of constant-depth quantum circuits
with an infinite gateset and multi-qudit fanout.333For any prime $p$, multi-
qudit fanout for $p$-dimensional qudits is equivalent to $\mathrm{MOD}_{p}$
gates. In this setting, we show that for any prime $p$, we have the collapse
of the constant-depth quantum hierarchy for quantum circuits with
$p$-dimensional qudits, extending the qubit case [42].

######  Result 4.

(Informal; see Theorem 27) For all prime $p$, there exists an infinite gate
set on qudits of dimension $p$ such that constant depth quantum circuits built
with this gate set and unbounded fan-in $\mathrm{MOD}_{p}$ gates implement
quantum threshold gates in constant depth, i.e.,
$\mathsf{i}\text{-}\mathsf{QNC}_{p}^{0}[p]=\mathsf{i}\text{-}\mathsf{QTC}_{p}^{0}$.444As
we describe later, in our notation, the prefix $i-$ denotes that the gate set
is infinite, and the subscript $p$ denotes that the qudits have dimension $p$.
Additionally, $[p]$ means access to a quantum and $[p]_{c}$ to a classical
unbounded fan-in modular $p$ gate.

This result establishes computational equivalence across shallow-depth quantum
circuits when implemented on systems over prime-dimensional Hilbert spaces.
Specifically, our quantum circuits are constructed using Fourier transforms
over Abelian groups and this approach allows the creation of circuits for
functions over finite fields of the form
$\mathbb{F}_{p}^{n}\rightarrow\mathbb{F}_{p}$. These circuits allow the
execution of multi-qubit controlled logical operations.

Subsequently, we show that constant-depth quantum circuits implemented in
higher prime dimensions can be implemented with qubits with a multiplicative
overhead. This highlights that for any algorithm falling within these classes,
employing qudits instead of qubits offers no substantial computational
benefits—except perhaps for more straightforward hardware implementations and
better error-correcting schemes in Hilbert spaces of varying dimensions.

######  Result 5.

(Informal; see Theorem 30). For all primes $p$ and $q$, any constant depth
quantum circuit with gates on qudits of dimension $p$ and quantum threshold
gates can be replicated by a constant-depth quantum circuit over qubits, with
access to classical $\mathrm{MOD}_{q}$ gates,
$\mathsf{i}\text{-}\mathsf{QTC}_{p}^{0}\subseteq\mathsf{i}\text{-}\mathsf{QNC}_{2}^{0}[q]_{\mathsf{c}}$.

This result is achieved by mapping qudit operations onto tensor products of
qubits. The qudit operations are produced using exact unitary decomposition
methods, as previously demonstrated for qubits [37, 2]. Specifically, this
theorem implies that the qubit-specific hierarchy can be collapsed using any
arbitrary classical modular prime gate — a capability previously believed to
require either quantum fanout or multi-qubit parity gates. Consequently, we
have that $\mathsf{QNC}^{0}[p]_{\mathsf{c}}=\mathsf{QACC}^{0}$ holds for all
primes $p$. This significantly contrasts with classical analog circuit
classes, where adding different modular gates results in different complexity
classes.

From a practical standpoint, it also demonstrates that quantum circuits with
fixed-depth qubits, when augmented with unbounded fan-in classical prime
modular operations $\mathrm{MOD}_{p}$, can implement the quantum subroutines
of algorithms like factoring, which have been conjectured to convey
exponential quantum advantage [22, 10].

Finally, we leave as future work to extend Result 5 and show that any
$\mathsf{i}\text{-}\mathsf{QTC}_{p}^{0}$ circuit can be simulated by
$\mathsf{i}\text{-}\mathsf{QNC}_{q}^{0}$ circuits with additional classical
modular gates, for arbitrary primes $p$ and $q$. This would establish the
equivalence between all constant-depth quantum circuits over qudits of
different prime dimensions.

###  1.2 Organization

Section 2 delves into the study of shallow-depth quantum circuits with finite-
size gate sets. In this section, we introduce the concept of modular relation
problems and elucidate how quantum circuits can solve these problems.
Additionally, we establish the $\mathsf{AC}^{0}[p]$ lower bounds for the
circuit classes addressing these problems and conclude the section by defining
the $\mathsf{NC}^{0}[p]$ classical upper bounds for the relation problems
under consideration. In Section 3, we shift our focus to constant-depth
quantum circuits over qudits. This section explores the implications of
employing infinite-size gate sets and unbounded fan-in modular gates,
demonstrating both hierarchical collapses and computational equivalences
between qubit and qudit formulations.

We assume readers have a basic understanding of qudit quantum computation,
types of computational problems (such as decision, search, and sampling), and
classical constant-depth circuits. For additional information, refer to
Appendix A for an overview.

## Acknowledgments

We acknowledge helpful discussions with Robin Kothari, Johannes Frank,
Sathyawageeswar Subramanian, Leandro Mendes and Min-Hsiu Hiseh on an early
version of these results. MdO is supported by National Funds through the FCT -
Fundação para a Ciência e a Tecnologia, I.P. (Portuguese Foundation for
Science and Technology) within the project IBEX, with reference PTDC/CCI-
COM/4280/2021, and via CEECINST/00062/2018 (EFG). ABG is supported by ANR JCJC
TCS-NISQ ANR-22-CE47-0004. ABG, EK and DM are supported by the PEPR integrated
project EPiQ ANR-22-PETQ-0007 part of Plan France 2030.

##  2 Shallow depth quantum circuits with finite-size gate sets

In this section, we show new separations between quantum shallow circuits and
classical ones. More precisely in Section 2.1, we introduce the classes of
quantum circuits considered in our work. Then, in Section 2.2, we prove the
quantum upper bounds, and in Section 2.3, we prove the classical lower bounds.
We combine these results in Section 2.4 in order to achieve our new
separations. Finally, in Section 2.5, we discuss the limitations of our
techniques.

###  2.1 Definitions

The initial circuit class under examination comprises a gate set defined by a
finite collection of gates and is restricted to single qudit control gates,
encompassing standard universal gate sets like the Clifford+T gate set.

######  Definition 1 ($\mathsf{QNC}_{d}^{0}$).

For $d\in\mathbb{N}$, let $\mathcal{H}^{d}$ denote a $d$-dimensional Hilbert
space. $\mathcal{G}_{d}$ being a finite set of quantum gates that operate on
$\mathcal{H}^{d}$, while $\mathcal{C}_{d}$ represents a fixed number of gates
that act on one qudit, controlled by another qudit. We define
$\mathsf{QNC}_{d}^{0}$ as the class of quantum circuits with constant depth
and polynomial size, employing a gate set compiled from the combination of
$\mathcal{G}_{d}$ and $\mathcal{C}_{d}$.

The subsequent class to be analyzed will supplement the finite number of qudit
gates with their multi-qudit controlled variants. This introduces an
alternative characterization for the quantum counterpart of $\mathsf{AC}^{0}$
that has not been addressed in prior literature and guarantees a fairer
comparison between the quantum and classical constant-depth circuit classes.

######  Definition 2 ($\mathsf{QAC}_{d}^{0}$).

For $d\in\mathbb{N}$, let $\mathcal{H}^{d}$ denote a $d$-dimensional Hilbert
space. Let $\mathcal{G}_{d}$ represent a finite set of gates acting on
$\mathcal{H}^{d}$, which are permitted unbounded classical fanout—defined as
the ability to replicate a gate’s output indefinitely, allowing its use as
input for numerous other gates—when these gates are characterized as maps from
basis states to basis states with classical inputs. Let $\mathcal{T}_{d}$
denote a fixed number of multi-qudit controlled gates acting on a single
qudit. We define $\mathsf{QAC}_{d}^{0}$ as the class of quantum circuits with
a constant depth and polynomial size, using a gate set drawn from the
combination of $\mathcal{G}_{d}$ and $\mathcal{T}_{d}$.

In this work, we also consider the complexity classes
$\mathsf{i}\text{-}\mathsf{QNC}_{d}^{0}$ and
$\mathsf{i}\text{-}\mathsf{QAC}_{d}^{0}$. These variants of
$\mathsf{QNC}_{d}^{0}$ and $\mathsf{QAC}_{d}^{0}$ incorporate the full set of
one-qudit unitaries. We will provide a formal definition of these classes in
Section A.3.

Additionally, we consider access to quantum advice, which is a quantum state
that depends on the input size but not on the input. In particular, we
consider $\mathsf{QNC}_{d}^{0}/\mathsf{qpoly}$, which consists of
$\mathsf{QNC}_{d}^{0}$ with a polynomial-size quantum advice.

We also examine extensions of certain constant-depth circuit classes,
including unbounded fan-in modular operations. For example, the class
$\mathsf{i}\text{-}\mathsf{QNC}_{d}^{0}[p]$ integrates
$\mathsf{i}\text{-}\mathsf{QNC}_{d}^{0}$ circuits with an additional quantum
modular gate defined as follows,

$\mathsf{qMOD}_{p}\ket{x_{0},x_{1},\ldots,x_{n}}:=\ket{x_{0}+(x_{1}+\ldots+x_{n})\mod
p,x_{1},\ldots,x_{n}\mod p}.$ (1)

Finally, we use the suffix $[p]_{c}$ to denote the inclusion of a classical
unbounded fan-in modular gate $\mathrm{MOD}_{p}$ in these circuit classes.

We now define the notion of modular relation problems.

######  Definition 3 (Modular relation problem).

The modular relations problem
$\mathcal{R}_{q,p}^{m}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{m}$ is defined as

$\mathcal{R}_{q,p}^{m}(x)=\left\\{y\ \big{|}\ y\in\mathbb{F}_{2}^{m},\
|y|\pmod{q}=0\text{ iff }|x|\pmod{p}=0\right\\}.$ (2)

This class of problems subsumes the relation problem used in [6, 44], which
uses $\mathcal{R}_{2,4}^{o(n^{2})}$ for the $\mathsf{NC}^{0}$ and the
$\mathsf{AC}^{0}$ separations, and [44], that uses
$\mathcal{R}_{2,3}^{o(n^{2})}$ for their $\mathsf{AC}^{0}[2]$ separation.

In this work, we also consider the parallel repetitions of these relation
problems.

######  Definition 4 (Parallel-k modular relation problem).

A modular relation problems $k$-$\mathcal{R}_{q,p}^{m}:\\{0,1\\}^{n\cdot
k}\rightarrow\\{0,1\\}^{m\cdot k}$ are defined as,

$k\text{-}\mathcal{R}_{q,p}^{m}(x_{1},...,x_{k})=\Big{\\{}(y_{1},...,y_{k})\
\Big{|}\forall x_{i}\in\mathbb{F}_{2}^{n},\ y_{i}\in\mathbb{F}_{2}^{m},\
|y_{i}|\pmod{q}=0\text{ iff }|x_{i}|\pmod{p}=0\Big{\\}}.$

Finally, we also define two key orthogonal bases for qudit states that will be
used in our works. The first one is an extension of the qubit X-basis for
qudits.

######  Definition 5 (Qudit orthogonal X-basis).

The qudit orthogonal X-basis can be described by the set of states,

$\ket{X_{d}^{m}}=\frac{1}{\sqrt{d}}\sum_{j=0}^{d-1}\omega^{j\cdot m}\ket{j}\ $
(3)

with $\omega=e^{\frac{i2\pi}{d}}$ and $m\in\\{0,1,...,d-1\\}$.

The second orthogonal basis is tailored specifically for qudit GHZ states and
will be necessary for the analysis of the quantum circuits we will present.

######  Definition 6 (Qudit-GHZ orthogonal X-basis).

The qudit-GHZ orthogonal X-basis can be defined by the set of states,

$\ket{\mathsf{GHZ}_{d,n}^{m}}=\frac{1}{\sqrt{d}}\sum_{j=0}^{d-1}\omega^{j\cdot
m}\ket{j}^{\otimes n}\ $ (4)

with $\omega=e^{\frac{i2\pi}{d}}$ and $m\in\\{0,1,...,d-1\\}$.

Finally, we state two technical lemmas regarding these bases that are needed
in our results.

######  Lemma 7.

$\braket{X_{d}^{m}}{X_{d}^{n}}=\braket{\mathsf{GHZ}_{d}^{m}}{\mathsf{GHZ}_{d}^{n}}=\delta_{m,n}$.

###### Proof.

All the elements of the qudit orthogonal X-basis can be represented as,

$\ket{X_{d}^{m}}=\frac{1}{\sqrt{d}}\sum_{i=0}^{d-1}\omega^{i\cdot m}\ket{i}\
=\mathsf{F}_{d}\ket{m}\ .$ (5)

This yields that,

$\braket{X_{d}^{m}}{X_{d}^{n}}=\bra{m}\mathsf{F}_{d}\mathsf{F}_{d}^{\dagger}\ket{n}.$
(6)

Combining this with the fact that the
$\mathsf{F}_{d}^{\dagger}\mathsf{F}_{d}\ket{m}=\ket{m}$, we obtain that
$\braket{X_{d}^{m}}{X_{d}^{n}}=\delta_{m,n}$. The same result holds for the
qudit-GHZ orthogonal X-basis, given that the bases are simply a tensor product
over $n$ elements of the same bases as in the qudit X-basis. ∎

######  Lemma 8.

$\mathsf{F}_{d}^{\otimes
n}\ket{\mathsf{GHZ}_{d,n}^{m}}=\frac{1}{\sqrt{d^{n-1}}}\sum\limits_{\begin{subarray}{c}x\in\mathbb{F}_{d}^{n}\\\
|x|\mod d=-m\end{subarray}}\ket{x}$.

###### Proof.

By considering the effect of the operator on the basis states we determine
that,

$\displaystyle\mathsf{F}_{d}^{\otimes n}\ket{\mathsf{GHZ}_{d}^{m}}$
$\displaystyle=\frac{1}{\sqrt{d}}\sum_{i=0}^{d-1}\big{(}\omega^{i\cdot
m}\mathsf{F}_{d}^{\otimes n}\ket{i}^{\otimes n}\big{)}$ (7)
$\displaystyle=\frac{1}{\sqrt{d}}\sum_{i=0}^{d-1}\omega^{i\cdot
m}\big{(}\frac{1}{\sqrt{d^{n}}}\sum_{x\in\\{0,1,...,d-1\\}^{n}}\omega^{i\cdot|x|}\ket{x}\big{)}$
(8)
$\displaystyle=\frac{1}{\sqrt{d^{n+1}}}\sum_{x\in\\{0,1,...,d-1\\}^{n}}\sum_{i=0}^{d-1}\omega^{i\cdot(m+|x|)}\ket{x}\
$ (9)

with $|x|=\sum_{i=0}^{n-1}x_{i}\mod d$. This implies that for all the inputs
$x$ for which $m+|x|\mod d=0$ the value of $\omega^{i\cdot(m+|x|)}=1$. In
contrast, for inputs $x$ for which $m+|x|\mod d\neq 0$ we will use the
geometric progression to demonstrate first that the sum of all roots of unity
is equal to zero,

$\sum_{i=0}^{d-1}\omega^{i}=\frac{1-\omega^{d}}{1-\omega}=0\ .$ (10)

Then, with one more step, we can show that the same is true for the amplitudes
of the inputs considered,

$\displaystyle\sum_{i=0}^{d-1}\omega^{i\cdot(m+|x|)}=\frac{1-\omega^{d\cdot(m+|x|)}}{1-\omega^{m+|x|}}=0\
.$ (11)

Finally, this implies that only for values that $m+|x|\mod d=0$ the amplitude
of the respective basis states $\ket{x}$ are non-zero. This produces exactly
the states,

$\frac{1}{\sqrt{d^{n-1}}}\sum_{x\in X}\ket{x},\ with\ X=\big{\\{}y\ |\
y\in\\{0,1,...,d-1\\}^{n},\ |y|\mod d=-m\big{\\}}\ .$ (12)

∎

###  2.2 Quantum upper bounds

In this subsection, we introduce lower bounds for the probability that
$\mathsf{QNC}^{0}$ circuits with quantum advice and $\mathsf{QAC}^{0}$
circuits can solve the modular relation problems.

####  2.2.1 Shallow depth quantum circuits with advice

In this subsection, we will introduce quantum circuits with a quantum advice
that compute $\mathcal{R}_{q,p}^{q\cdot n}$ with a one-sided error.

######  Theorem 9.

For all fixed and distinct primes $p$ and $q$, $\mathcal{R}_{q,p}^{q\cdot n}$
can be solved in $\mathsf{QNC}_{q}^{0}/\mathsf{qpoly}$ with one-sided error at
most $\frac{1-\cos(\frac{2\pi}{p})}{q}$.

###### Proof.

The circuit for $\mathcal{R}_{q,p}^{q\cdot n}$ problem is described in Figure
1.

The initial state is $\ket{x}\ket{\mathsf{GHZ}_{q,n}^{0}}$, where the GHZ
state is the quantum advice of the circuit. Then, we apply a layer of $n$
control-$Z$ rotations on the $n$ qubits with a phase equal to
$\frac{2\pi}{p}$. The $i$-th bit of the input $x$ acts as the control qubit to
the control-$Z$ with the target being the $i$-th qubit of the GHZ state.

The first register is then

$\ket{\psi^{(1)}}=\frac{1}{\sqrt{q}}\Big{(}\sum_{i=0}^{q-2}\ket{i}^{\otimes
n}+e^{i\frac{2\pi|x|}{p}}\ket{q-1}^{\otimes
n}\Big{)}=\sum_{i=0}^{q-1}c_{i}\ket{\mathsf{GHZ}_{q,n}^{i}},$ (13)

with the second equality being the decomposition of $\ket{\psi^{(1)}}$ in the
qudit-GHZ orthogonal X-basis.

If we apply $F^{\otimes n}_{q}$ to $\ket{\psi^{(1)}}$, we have

$\displaystyle\ket{\psi^{(2)}}=\mathsf{F}_{q}^{\otimes n}\ket{\psi^{(1)}}$
$\displaystyle=\sum_{i=0}^{q-1}c_{i}\ (\mathsf{F}_{q}^{\otimes
n}\ket{\mathsf{GHZ}_{q,n}^{i}})=\sum_{i=0}^{q-1}c_{i}\sum_{\begin{subarray}{c}z\in[q]^{n}\\\
|z|\mod q=-i\end{subarray}}\ket{z},$

where the last equality comes from Lemma 8.

Our goal is to compute the probability of measuring this state and get an
output $y$ such that $|y|\pmod{p}=0$. For that, notice that $c_{0}$ is:

$\displaystyle\braket{\mathsf{GHZ}_{q,n}^{0}}{\psi^{(1)}}$
$\displaystyle=\frac{1}{\sqrt{q}}\sum_{i=0}^{q-1}\bra{i}^{\otimes
n}\frac{1}{\sqrt{q}}\Big{(}\sum_{i=0}^{q-2}\ket{i}^{\otimes
n}+e^{i\frac{2\pi|x|}{p}}\ket{q-1}^{\otimes
n}\Big{)}=\frac{q-1+\cos(\frac{2\pi|x|}{p})}{q}\ .$ (14)

We then divide that analysis into two cases:

  1. 1.

If $|x|\mod p=0$, $(c_{0})^{2}$ equals 1. Consequently, measuring
$\ket{\psi_{2}}$ leads to a string $y$ such that $|y|\mod q=0$.

  2. 2.

If $|x|\mod p\neq 0$, we have
$c_{0}^{2}\leq\frac{q-1+\cos(\frac{2\pi|x|}{p})}{q}$. This implies that with a
probability of least $\frac{1-\cos(\frac{2\pi}{p})}{q}$, it holds that
$|y|\mod q\neq 0$.

The remaining step consists of mapping $y\in[q]^{n}$ to bit-strings
$y^{\prime}\in\\{0,1\\}^{q\cdot n}$ such that the Hamming weight is preserved.
This can be done with extra ancilla qubits by mapping each $y_{i}\in[q]$ to
the bit-string $1^{y_{i}}0^{q-y_{i}}$. We denote the circuit that performs
such an operation as $C(q,2)$. ∎

Figure 1: Parameterized quantum circuit class for values $q$, $p$, and $n$,
incorporating the advice quantum state $\ket{\mathsf{GHZ}_{q,n}^{0}}$, which
solves the $\mathcal{R}_{q,p}^{q\cdot n}$ with bounded one-sided error.

####  2.2.2 Shallow depth quantum circuits with Toffoli gates

We show now that quantum circuits of constant depth built with multi-qudit
controlled operations along with intermediate measurements can generate qudit-
GHZ states, demonstrating that $\mathsf{QAC}_{q}^{0}$ (without advice) can
solve $\mathcal{R}_{q,p}^{q\cdot n}$ with a one-sided error.

To achieve these qudit GHZ states, we use a specialized entanglement structure
built upon “poor-man’s cat states,” as referenced in [44, 3, 25].
Specifically, poor-man’s cat states are formulated using graphs where the
number of vertices is equal to the state’s qubit count, and the edge
configuration guarantees a unique path between all vertices. In our work, we
fix this graph to balanced binary trees $\mathcal{B}_{n}$ and extend these
quantum states to higher dimensions.

######  Definition 10 (Binary tree-structured poor-man’s qudit state).).

Let $q$ be a prime. We consider the balanced binary tree
$\mathcal{B}_{n}=(V,E)$, where $V=\\{1,...,n\\}$ and
$E=\\{\\{i,\left\lfloor\frac{i}{2}\right\rfloor\\}:i\in\\{2,...,n\\}\\}$. As
an example, we depict $\mathcal{B}_{6}$ in Figure 2.

We define a binary tree-structured poor-mans qudit state
$\ket{\mathsf{BPM}_{q,n}}$ as follows

$\ket{\mathsf{BPM}_{q,n}}=\frac{1}{\sqrt{q^{n}}}\sum_{e_{2},...,e_{n},v_{1}\in\mathbb{F}_{q}}\ket{e_{2},...,e_{n}}\ket{v_{1},v_{2},v_{3},\ldots,v_{n}},$
(15)

where each $v_{i}$, $i\in\\{2,...,n\\}$ is recursively defined as

$\displaystyle v_{i}=e_{i}-v_{\lfloor\frac{i}{2}\rfloor}.$ (16)

$1$$2$$4$$e_{3}$$5$$e_{4}$$e_{1}$$3$$6$$e_{5}$$e_{2}$ Figure 2: Representation
of $\mathcal{B}_{6}$.

We now show that these states can be created using constant-depth quantum
circuits.

######  Lemma 11.

For $n\in\mathbb{N}$, $\ket{\mathsf{BPM}_{q,n}}$ can be prepared in
$\mathsf{QNC}_{q}^{0}$.

###### Proof.

For creating this state, we start with a single qudit for each vertex and edge
in $\mathcal{B}_{n}$, i.e., we have $|V|+|E|$ qudits, where the $i$-th qudit,
for $1\leq i\leq n-1$ corresponds to the edge
$\\{i+1,\lfloor\frac{i+1}{2}\rfloor\\}$ and the $i$-th qudit, for $n\leq i\leq
2n-1$ corresponds to the vertex $i-n+1$. We label qudits by their
corresponding vertices/edges.

We start by applying the Fourier gate $\mathsf{F}_{q}$ to each of the vertex
qudits and then, for edge $e=\\{u,v\\}\in E$ we apply a
$\mathsf{SUM}_{u,e}$555The $\mathsf{SUM}_{i,j}$ gate serves as the qudit
equivalent of the $\mathsf{CNOT}$ gate and operates according to
$\mathsf{SUM_{i,j}}\ket{n}_{i}\ket{m}_{j}=\ket{n}\ket{n+m}$. and
$\mathsf{SUM}_{v,e}$. The overall state after these operations is:

$\displaystyle\sum_{v_{1},...,v_{n}\in\mathbb{F}_{q}}\frac{1}{\sqrt{q^{n}}}\ket{(v_{1}+v_{2}),(v_{1}+v_{3})...,(v_{n}+v_{\frac{n}{2}})}\otimes\ket{v_{1},v_{2},v_{3},\ldots,v_{n}}$
(17)
$\displaystyle=\sum_{e_{1},v_{1},v_{3}...,v_{n}\in\mathbb{F}_{q}}\frac{1}{\sqrt{q^{n}}}\ket{e_{1},(v_{1}+v_{3})...,(v_{n}+v_{\frac{n}{2}})}\otimes\ket{v_{1},e_{1}-v_{1},v_{3},\ldots,v_{n}}$
(18)
$\displaystyle=\sum_{e_{1},e_{2},v_{1},v_{4}...,v_{n}\in\mathbb{F}_{q}}\frac{1}{\sqrt{q^{n}}}\ket{e_{1},e_{2}...,(v_{n}+v_{\frac{n}{2}})}\otimes\ket{v_{1},e_{1}-v_{1},e_{2}-v_{1},v_{4},\ldots,v_{n}}$
(19) $\displaystyle...$ (20)
$\displaystyle\sum_{e_{1},...,e_{n-1},v_{1}\in\mathbb{F}_{q}}\frac{1}{\sqrt{q^{n}}}\ket{e_{1},...,e_{n-1}}\otimes\ket{v_{1},e_{1}-v_{1},e_{2}-v_{1},\ldots,e_{n-1}-v_{\frac{n}{2}}}$
(21) $\displaystyle=\ket{\mathsf{BPM}_{q,n}},$ (22)

where all operations are $\pmod{q}$ and all the equalities hold by rewriting
the elements in $\mathbb{F}_{q}$.

Finally, given that the $\mathsf{F}_{q}$ gates are all applied in parallel to
the vertex qudits, and the chromatic number of a balanced binary tree is equal
to 3, all the $\mathsf{SUM}_{i,j}$ gates can be parallelized in order to be
implemented in constant depth. ∎

We now show that these states can be easily converted to GHZ states.

######  Lemma 12.

There is a $\mathsf{QAC}_{q}^{0}$ circuit $C_{n}$ that maps
$\ket{\mathsf{BPM}_{q,n}}$ to the n-qudit state
$\ket{\mathsf{GHZ}_{q,n}^{0}}$.

###### Proof.

In the circuit $C_{n}$, we first measure the edge qudits leading to the output
string $e_{1}...e_{n-1}\in\mathbb{F}^{n-1}_{q}$. The collapsed quantum state
is

$\ket{e_{1},...,e_{n-1}}\otimes\frac{1}{\sqrt{q}}\sum_{v_{1}\in\mathbb{F}_{q}}\ket{v_{1},v_{2},...,v_{n}}.$
(23)

where $v_{i}=e_{i}-v_{\lfloor\frac{i}{2}\rfloor}$. Notice that by opening this
recurrence relation, we have that

$\displaystyle
v_{i}=\sum_{j=0}^{depth(i)-1}(-1)^{depth(i)-depth(q^{j}(i))}e_{q^{j}(i)}+(-1)^{depth(i)+1}v_{1},$
(24)

where $depth(i)$ denotes the depth of node $i$ in the tree and $q^{j}(i)$
denotes the $j$-th predecessor of $i$ in the tree.

We notice that for each $i$, the value
$c_{i}:=\sum_{j=0}^{depth(i)-1}(-1)^{depth(i)-depth(q^{j}(i))}e_{q^{j}(i)}$
can be computed by $poly(n)$-size $\mathsf{AC}^{0}$ circuits on input, since
it depends on at most $\log(n)$ values $e_{j}$. In this case, a $poly(n)$-size
$\mathsf{AC}^{0}$ exists that computes $c_{1}...c_{n}$. Given these
corrections, we can apply the gate $\mathsf{X}^{c_{i}}$ to the $i$-th vertex
qubit (which is a classically-controlled $\mathsf{X}$ gate), and the resulting
state is:

$\ket{e_{1},...,e_{n-1}}\otimes\frac{1}{\sqrt{q}}\sum_{v_{1}\in\mathbb{F}_{q}}\bigotimes_{i=1}^{n}\ket{(-1)^{depth(i)}v_{1}}.$
(25)

Finally, we can apply the following operation to the qudits corresponding to
the vertex of odd depth: $V\ket{m}=\ket{p-m}$ and the result state is

$\ket{e_{1},...,e_{n-1}}\otimes\frac{1}{\sqrt{q}}\sum_{v_{1}\in\mathbb{F}_{q}}\ket{v_{1}}^{\otimes
n}\qed.$

The reduction we previously discussed cannot be achieved using
$\mathsf{QNC}^{0}$ or $\mathsf{i}\text{-}\mathsf{QNC}^{0}$ circuits since they
cannot implement the essential corrections needed to transition from the poor
man’s cat states to the GHZ states. In contrast, we explore the additional
computational power of $\mathsf{QAC}^{0}$ circuits and show that they can
produce the qudit GHZ states through a process involving mid-circuit
measurements. As a consequence, we can show the following.

######  Theorem 13.

For any distinct primes $p$ and $q$, a $\mathsf{QAC}_{q}^{0}$ circuit can
solve $\mathcal{R}_{q,p}^{q\cdot n}$ with one-sided error at most
$\frac{1-\cos(\frac{2\pi}{p})}{q}$.

###### Proof.

Combining Lemma 11 and Lemma 12, we obtain that $\mathsf{QAC}_{q}^{0}$
circuits can create qudit GHZ states of the type
$\ket{\mathsf{GHZ}_{q,n}^{0}}$. In addition, all the $\mathsf{QNC}_{q}^{0}$
circuits of Theorem 9 are contained in $\mathsf{QAC}_{q}^{0}$. Therefore, all
modular relation problems of the form $\mathcal{R}_{q,p}^{q\cdot n}$ fixed
prime numbers $p$ and $q$ can be solved by $\mathsf{QAC}^{0}$ circuits. ∎

###  2.3 Classical lower bounds

In this subsection, we prove the classical lower bounds for
$\mathcal{R}_{p,q}^{q\cdot n}$. For that, we reduce it to computing
$\mathrm{MOD}_{p}$ function and use the Razborov-Smolensky separations
(Theorem 35) for $\mathsf{AC}^{0}[q]$. Then, we consider the
$k$-$\mathcal{R}_{q,p}^{q\cdot n}$ problem, and we show that
$\mathsf{AC}^{0}[q]$ circuits can solve them with only a negligible
probability at best by using the Vazirani-XOR lemma.

######  Lemma 14.

Let $p$ and $q$ be two distinct primes. Any depth $d$ circuit in
$\mathsf{AC}^{0}[q]$ that solves the $\mathcal{R}_{q,p}^{q\cdot n}$ problem
with one-sided error probability at most $1/n^{\Omega(1)}$ has size
$\exp(n^{1/(2d-\Theta(1)})$.

###### Proof.

Let us suppose, for the purpose of a contradiction, that there exists a
circuit $C$ in $\mathsf{AC}^{0}[q]$ of depth $d-3$ and size equal to
$\exp(n^{1/(2d-\Theta(1))})$ that computes $\mathcal{R}_{q,p}^{q\cdot n}$,
with one-sided error probability at most $\frac{1}{n^{o(1)}}$. We will assume
here that $C$ computes the yes-instance with probability $1$, and the
arguments follow analogously if $C$ computed the no-instances with probability
$1$.

We will now prove that if such a $C$ exists, then there exists a
$\mathsf{AC}^{0}[q]$ circuit $C^{\prime}$ that computes the $\mathrm{MOD}_{p}$
function correctly with probability $1-negl(n)$. $C^{\prime}$ consists of
running $O(n^{2})$ times the circuit $C$ in parallel and then applying a
$\mathrm{MOD}_{q}$ gate to each output string, and then applying a
$\mathsf{NOR}$ gate to the output of this layer of $\mathrm{MOD}_{q}$ gates.
Figure 3 provides a representation of $C^{\prime}$.

If $|x|\mod p=0$, after running $C$ on $x$, the resulting strings $y_{i}$ are
such that $|y_{i}|\mod q=0$. Thus, the $\mathrm{MOD}_{q}$ gates to each of
these strings lead to output $0$. Therefore, after the $\mathsf{NOR}$ gate,
the result for this final bit will always be 1.

On the other hand, if $|x|\mod p\neq 0$, with probability $1/n^{o(1)}$, the
strings $y_{i}$ after running $C$ have the desired property $|y_{i}|\mod q\neq
0$. Therefore, with the same probability, the $\mathrm{MOD}_{q}$ gate applied
to this string will result in the Boolean value $1$, and the probability of at
least one of them being equal to $1$ is at least $1-negl(n)$. Therefore, the
output of the $\mathsf{NOR}$ gate is $0$ with probability $1-negl(n)$.

This leads to a depth-$d$ circuit and size $\exp(n^{1/(2d-\Theta(1))})$, that
computes $\mathrm{MOD}_{p}$ in $\mathsf{AC}[q]$, contradicting Theorem 35.
Thus, circuit $C$ with such properties cannot exist. ∎

$y_{m,n\cdot q}$

⋮

$y_{m,2}$$y_{m,1}$$y_{2,n\cdot q}$

⋮

$y_{2,2}$$y_{2,1}$$y_{1,n\cdot q}$

⋮

$y_{1,2}$$y_{1,1}$ $\mathrm{MOD}_{q}$$\mathrm{MOD}_{q}$$\mathrm{MOD}_{q}$

⋮

⋮

⋮

$\mathsf{NOR}$ Figure 3: Representation of a classical $\mathsf{AC}^{0}[q]$
circuit, parameterized by $q$ and $n$, that reduces a solution to the
$\mathcal{R}_{q,2}^{q\cdot n}$ problem to a solution of $\mathrm{MOD}_{2}(x)$,
where $x$ is the initial input string of size $n$.

Subsequently, we show that polynomial-sized $\mathsf{AC}^{0}[q]$ circuits
solve the parallel repetition of the modular relation problems with
probability close to zero. To obtain this bound, we focus on the success of
$\mathsf{AC}^{0}[q]$ circuits in computing the $\mathrm{MOD}_{2}$ function
with one-sided error.

######  Corollary 15.

The $\mathrm{MOD}_{2}$ function can not be solved by any one-sided error
$\mathsf{AC}^{0}[q]$ circuit with $q$ prime $q\neq 2$ with a probability
higher than $1/2+1/n^{\Omega(1)}$.

###### Proof.

Let’s assume there exists an $\mathsf{AC}^{0}[p]$ circuit that can solve the
Yes instances of the $\mathrm{MOD}_{2}$ perfectly, then we know by Lemma 14
that the No instances can almost be solved correctly with probability
$1/n^{o(1)}$. This implies any circuit of this type solves the
$\mathrm{MOD}_{2}$ function over a random input w.p. at most $1/2+1/n^{o(1)}$.
∎

Using all these tools, we can show that the class of $\mathsf{AC}^{0}[q]$
fails to compute completely parallel modular relation problems with a one-
sided error for some parameter regimes.

######  Lemma 16.

Let $q\neq 2$ be a prime and $k\in\Theta(\log(n))$. No $\mathsf{AC}^{0}[q]$
circuit can solve $k$-$\mathcal{R}_{q,2}^{q\cdot n}$ on at least
$\frac{1}{2}+\frac{1-\cos(\frac{2\pi}{p})}{2q}$ fraction of the parallel
instances with one-sided errors and a probability higher then
$n^{-\Omega(1)}$.

###### Proof.

Let us suppose that there exists a circuit $C\in\mathsf{AC}^{0}[q]$, where
$q\neq 2$, can solve the $k$-$\mathcal{R}_{q,2}^{q\cdot n}$ with the
properties of the statement. Then, we can construct a circuit $C^{\prime}$
that solves the following search problem

$k\text{-}\mathcal{D}_{2,2}(x_{1},...,x_{k})=\Big{\\{}(y_{1}^{\prime},...,y_{k}^{\prime})\
\Big{|}\forall x_{i}\in\mathbb{F}_{2}^{n},\ y_{i}^{\prime}\in\mathbb{F}_{2},\
y_{i}^{\prime}+|x_{i}|\pmod{2}=0\Big{\\}},$ (26)

with the same success, where $C^{\prime}$ is equal to $C$ with an extra layer
of $\mathrm{MOD}_{q}$ gates, thereby transforming the outcome strings from
$k$-$\mathcal{R}_{q,2}^{q\cdot n}$ into bits using the mapping
$\mathrm{MOD}_{q}(y_{i})=y_{i}^{\prime}$.

The circuit $C^{\prime}$ induces a probability distribution $\mathcal{X}$ on
$\\{0,1\\}^{k},$ corresponding on picking random
$x_{1},...,x_{k}\in\\{0,1\\}^{n}$ and outputting $k$ output bits as follows,

$\displaystyle(|x_{1}|+C_{1}^{\prime}(x_{1},\ldots,x_{n})\pmod{2},...,|x_{k}|+C_{k}^{\prime}(x_{1},\ldots,x_{n})\pmod{2}).$
(27)

Our goal now is to prove that $\mathcal{X}$ is close to a uniform distribution
$\\{0,1\\}^{k}$ on half of its bits, either for all $x_{i}$ with even or odd
Hamming weight, if we assume one-sided error. For that, we notice that we can
describe for all $S\subseteq[k]$ the following expectation value as

$\displaystyle\left|\mathbb{E}_{z\in\mathcal{X}}[(-1)^{\chi_{S}(z)}]\right|$
$\displaystyle=\frac{1}{2^{|S|\cdot
n}}\sum_{x_{1},...,x_{k}\in\mathbb{F}_{2}^{n}}(-1)^{\oplus_{i\in
S}(|x_{i}|+C_{i}^{\prime}(x_{1},\ldots,x_{n})\pmod{2})}$ (28)
$\displaystyle=\frac{1}{2^{|S|\cdot
n}}\sum_{x_{1},...,x_{k}\in\mathbb{F}_{2}^{n}}(-1)^{\left(\sum_{i\in
S}|x_{i}|+\sum_{i\in S}C_{i}^{\prime}(x_{1},\ldots,x_{n})\right)\pmod{2}},$
(29)

where $\chi_{S}(z)=\oplus_{i\in S}z_{i}$.

This allows us to bind the previous value for all the subsets $S$ based on the
number of times the following equation is fulfilled for uniformly selected
strings $x_{i}$,

$\sum_{i\in S}|x_{i}|\equiv\sum_{i\in S}C_{i}^{\prime}(x_{1},\ldots,x_{n})\mod
2.$ (30)

We observe that determining the values for the outcome bits $i\in S$ such that
the condition of Equation (30) is satisfied by an $\mathsf{AC}^{0}[q]$ circuit
$C^{\prime}$ is as hard as computing the parity function across the
concatenated input strings $||_{i\in S}x_{i}$. This assertion is supported by
the fact that a circuit, which, if capable of determining valid outcome bits
under the given condition, can be reduced to one that does compute the parity
of the concatenated input strings $||_{i\in S}x_{i}$ with a polynomial-size
$\mathsf{AC}^{0}[q]$ circuit. The latter follows from the fact that polynomial
size $\mathsf{AC}^{0}[q]$ circuits can effectively compute the parity of a
string of length $\log(n)$. Consequently, the probability that Equation (30)
is satisfied is directly related to the probability that an
$\mathsf{AC}^{0}[q]$ circuit computes the parity function across the
concatenated input strings $||_{i\in S}x_{i}$, albeit with a one-sided error.
This condition is met with a maximum probability of $1/2+n^{-\Omega(1)}/2$, as
inferred from Corollary 15. Therefore, we deduce that for any characteristic
function $\chi_{S}$, the value of $|\mathbb{E}_{x\in D}[(-1)^{\chi_{S}(x)}]|$
is limited by $\frac{1}{n^{\Omega(1)}}$, for all input strings of either even
or odd Hamming weight.

Now, we can apply Vazirani’s XOR Lemma (Lemma 38) to demonstrate that the
distribution $\mathcal{X}$ is at most $1/n^{\Omega(1)}\cdot 2^{k/2}$ deviated
in total variational distance from the uniform distribution, on those inputs.
Then, we can show by using the Chernoff bound that the event $X$ described as
sampling a string with at least $1/2+\frac{1-\cos(\frac{2\pi}{p})}{2q}$ of 0’s
from this distribution, has a probability that decreases with,

$\displaystyle\Pr\Big{(}X\Big{)}$
$\displaystyle<e^{-2\cdot(4/\frac{1-\cos(\frac{2\pi}{p})}{2q})^{2}(1/2)^{2}/(k^{2})}<e^{-\Omega(k^{2})}\
.$ (31)

Thus, we obtain that the distribution $\mathcal{X}$ contains the same string
with probability at most,

$n^{-\Omega(1)}\cdot 2^{k/2}+e^{-\Omega(k^{2})}=n^{-\Omega(1)+k/(2\log(n))}.$
(32)

Finally, we conclude that the previous value is bounded by $n^{\Omega(1)}$,
given that $k=\log(n)$. ∎

###  2.4 Separations

In this section, we combine the results from Section 2.2.1 and Section 2.3 to
achieve unconditional separation between the classical and quantum circuit
classes.

######  Theorem 17.

For each fixed prime $q$, there exists a relation problem that cannot be
solved by polynomial-size circuits $\mathsf{AC}^{0}[q]$ with success
probability at least $n^{-\Omega(1)}$, whereas there is a
$\mathsf{QNC}_{q}^{0}/\mathsf{qpoly}$ circuit and a $\mathsf{QAC}_{p}^{0}$
circuit that can solve it with probability of least $1-o(1)$.

###### Proof.

For the case where $q=2$, the result is derived from Theorem 6 in [44]. For
all $q\neq 2$, we apply the lower bounds and the respective instances of the
parallel modular relation problems $k$-$\mathcal{R}_{q,2}^{q\cdot n}$
discussed in Lemma 16. These instances establish that $\mathsf{AC}^{0}[q]$
circuits solve this set of problems with a probability of at most
$n^{-\Omega(1)}$.

In contrast, the $\mathsf{QNC}_{q}^{0}/\mathsf{qpoly}$ circuit, described in
Theorem 9, can solve each instance of the parallel repetition game with a one-
sided error of $\frac{1-\cos(\frac{2\pi}{p})}{q}$. Similarly,
$\mathsf{QAC}_{p}^{0}$ circuits achieve the same success probability, as
detailed in Theorem 13. By combining these individual solutions, we deduce
that the resulting global strategies effectively solve the
$k$-$\mathcal{R}_{q,2}^{q\cdot n}$ problems, as outlined in Lemma 16, with a
probability of at least $1-o(1)$. This follows by considering their respective
individual success probabilities and applying the Chernoff bounds. ∎

Remark: We implicitly used the fact that the $\mathrm{MOD}_{2}$ operation is
not contained in any other $\mathsf{AC}^{0}[q]$ class with $q\neq 2$, which
simplifies the proof since it allowed us to uniquely use Vazirani’s XOR Lemma.
However, we notice that the proof could follow with any other prime values and
modular functions.

One drawback of the previous results is that we need to pick a different qudit
dimension for each modular relation problem. However, if we consider infinite-
size gatesets, we can show that all the previous quantum circuits can be
implemented with qubits and prove the separation for $\mathsf{AC}^{0}[p]$ for
all primes $p$.

######  Theorem 18.

For all $p$ prime,
$\mathsf{i}\text{-}\mathsf{QAC}_{2}^{0}\nsubseteq\mathsf{AC}^{0}[p]$.

###### Proof.

From [37] and [2], we have that $\mathsf{QNC}_{p}^{0}$ circuits can be
implemented using single and two-qubit operations contained in
$\mathsf{i}\text{-}\mathsf{QNC}_{2}^{0}$. Furthermore, all quantum operations
in $\mathsf{QAC}_{p}^{0}$ used for the creation of the qudit-GHZ state in
Lemmas 11 and 12 are controlled on a constant number of qudits and therefore
these operations can be implemented $\mathsf{i}\text{-}\mathsf{QNC}_{2}^{0}$.

Finally, we need to show that corrections needed to transform the poor man’s
cat states into qudit-GHZ states can be executed in
$\mathsf{i}\text{-}\mathsf{QAC}_{2}^{0}$. As described in the proof of Lemma
12, these corrections can be realized using a classical $\mathsf{AC}^{0}$
circuit, which is encompassed by $\mathsf{i}\text{-}\mathsf{QAC}_{2}^{0}$.
Consequently, all quantum circuits from Theorems 13 and 17, for any prime $p$,
can be constructed using $\mathsf{i}\text{-}\mathsf{QAC}_{2}^{0}$ circuits. ∎

###  2.5 Classical upper bounds for modular relation problems

In this subsection, we consider the classical upper bound on the modular
relation problems, which indicates the limitations on the quantum/classical
separations using our techniques.

######  Lemma 19.

For any fixed primes $q$,$p$ and fixed $k_{1},k_{2},m\in\mathbb{N}$,
$\mathcal{R}_{q^{k_{1}},p^{k_{2}}}^{m}$ can be solved by an
$\mathsf{NC}^{0}[p]$ circuit.

###### Proof.

We start by showing that there exists an $\mathsf{NC}^{0}[p]$ circuit that
computes $\mathrm{MOD}_{p^{k_{1}}}$ for any $k_{1}\in\mathbb{N}$. We use the
$\mathsf{AC}^{0}[p]$ circuits described in [17] and argue that they can be
implemented in $\mathsf{NC}^{0}[p]$.

We prove this statement by induction on the exponent $k_{1}$, showing that any
$\mathrm{MOD}_{p^{j}}$ gate can be computed if we have access to
$\mathrm{MOD}_{p^{j-1}}$ gates. The circuit construction from [17] is as
follows:

  1. 1.

For each $i\in[n]$, compute $y_{i}=\mathrm{MOD}_{p_{j-1}}(x)$.

  2. 2.

For all $i\in{2,\ldots,n}$, compute $z_{i}=\mathsf{AND}(y_{i-1},\neg y_{i})$.

  3. 3.

Compute
$b_{j}=\mathsf{AND}(\mathrm{MOD}_{p^{j-1}}(\sum_{i\in{2,\ldots,n}}z_{i}),\mathrm{MOD}_{p}(|x|))=\mathrm{MOD}_{p^{j}}(x)$.

Given that the final value $b_{j}=\mathrm{MOD}_{p^{j}}(x)$ [17], in order to
show that $\mathrm{MOD}_{p^{j}}$ is in $\mathsf{NC}^{0}[p]$, we only need to
show that each of these three steps can be implemented in
$\mathsf{NC}^{0}[p]$. Let’s evaluate these steps:

  * •

The first step is inherently within $\mathsf{NC}^{0}[p]$ due to inductive
reasoning; given the prior case produced an $\mathrm{MOD}_{p^{j-1}}$ gate,
only the next steps need validation.

  * •

The second step can be achieved with an $\mathsf{NC}^{0}$ circuit since it
solely relies on bounded fan-in $\mathsf{AND}$ gates.

  * •

The third step follows since both modular gates are within
$\mathsf{NC}^{0}[p]$ from our induction, combined with the $\mathsf{AND}$ gate
having bounded fan-in.

Thus, any $\mathrm{MOD}_{p^{k_{1}}}$ gate can be implemented within
$\mathsf{NC}^{0}[p]$ provided that $k_{1}$ is a constant, which determines the
depth of the previously proposed circuit.

Finally, to prove our statement, i.e., to output a valid string for the
modular relation problem $\mathcal{R}_{q^{k_{1}},p^{k_{2}}}^{m}$, one needs to
use the $\mathsf{NC}^{0}[p]$ circuit to compute the value of
$\mathrm{MOD}_{p^{k_{1}}}(x)$ and then append it to a string like $0^{m-1}$.
We have that $|b_{k_{1}}0^{m-1}|\pmod{q^{k_{2}}}=0$ iff
$|x|\pmod{p^{k_{1}}}=0$. ∎

Given the containment of the $\mathsf{NC}^{0}[p]$ circuit classes within the
$\mathsf{AC}^{0}[p]$ classes, we have that all modular relation problems are
solvable by $\mathsf{TC}^{0}$ circuits.

######  Corollary 20.

For any primes $q$,$p$ and $k_{1},k_{2},m\in\mathbb{N}$,
$\mathcal{R}_{q^{k_{1}},p^{k_{2}}}^{m}$ can be solved in $\mathsf{TC}^{0}$.

##  3 Shallow depth quantum circuits with infinite-size gate sets

This section considers constant-depth quantum circuits utilizing qubits and
qudits, employing infinite gate sets and modular gates with unbounded fan-in
while exploring their equivalences.

###  3.1 Constant-depth qudit circuits with quantum modular operators

In this subsection, we extend [42] and [29], and prove that the hierarchy of
constant-depth quantum circuits with an infinite gateset over qudits collapses
when we have access to a multi-qubit quantum/classical modular gate with
unbounded fan-in gates.

We start by focusing on the quantum $\mathsf{OR}$ function, defined over
Hilbert spaces of prime dimension $p$ as follows,

$\mathsf{qOR}\ket{x_{1},x_{2},\ldots,x_{n}}:=\ket{x_{1}+\mathsf{OR}(x_{2},x_{3},\ldots,x_{n})\pmod{p},x_{2},\ldots,x_{n}}.$
(33)

with the classical $\mathsf{OR}$ operating over strings in $\mathbb{F}_{p}$
defined as follows666The intuition behind the $\mathsf{AND}$ and $\mathsf{OR}$
functions over strings in $\mathbb{F}_{p}$ is that, similar to the binary
case, the $\mathsf{AND}$ function discriminates against only one string, while
the $\mathsf{OR}$ function includes all strings except one.,

$\mathsf{OR}(x)=\begin{cases}1&\text{if }\sum_{i=1}^{n}x_{i}>0,\\\
0&\text{otherwise.}\end{cases}.$ (34)

We first claim that a qudit analog of Høyer’s and Špaleks $\mathsf{OR}$
reduction [22], which allows us to reduce the problem of computing
$\mathsf{qOR}$ on an arbitrary state to the evaluation of $\mathsf{qOR}$ on
another state with exponentially fewer qudits.

######  Lemma 21.

Let $p$ be a prime. There exists a $\mathsf{i}\text{-}\mathsf{QNC}_{p}^{0}[p]$
circuit $C$, such that for every $n$ qudit state
$\ket{\psi}=\sum_{x\in\mathbb{F}_{p}^{n}}\alpha_{x}\ket{x}$, we have

$C\ket{\psi}\ket{0}^{\otimes t}=\sum_{x\in\mathbb{F}_{p}^{n},\
y\in\mathbb{F}_{p}^{\log_{p}(n)}}\alpha_{x}\beta_{y,x}\ket{y}\ket{x}\ket{0}^{\otimes
t^{\prime}}=\ket{\psi^{*}}\ket{0}^{\otimes t^{\prime}},$ (35)

where and $\mathsf{qOR}\ket{0}\ket{\psi}=\mathsf{qOR}\ket{0}\ket{\psi^{*}}$
with respect to the first qudit, while the second $\mathsf{qOR}$ does operate
uniquely over the first $\log(n)$ qudits of $\ket{\psi^{*}}$.

###### Proof.

We describe now our circuit $C$. In the first step of this proposed circuit,
we have a layer of $n$ fanout gates, which are defined as follows

$\mathsf{fanout}_{p}\ket{x_{1},x_{2},\ldots,x_{n}}:=\ket{x_{1},(x_{1}+x_{2})\mod
p,\ldots,(x_{1}+x_{n})\mod p}.$ (36)

The $k$-th $\mathsf{fanout}_{p}$ gate is applied to the $k$-th qudit of
$\ket{\psi}$ and a fresh $\log_{p}(n)$-qudit state initialized on
$\ket{0}^{\otimes\log(n)}$777Note that this fanout gate can be equally created
from the $\mathsf{qMOD}_{p}$ gate,
$\mathsf{fanout}_{p}=(\mathsf{F}_{p})^{\otimes
n}\mathsf{qMOD}_{p}(\mathsf{F}_{p})^{\otimes n}$..

In parallel to these $\mathsf{fanout}_{p}$ gates, we create $\log_{p}(n)$
copies of $n$-qudit GHZ states. These can be created by an
$\mathsf{QNC}_{p}^{0}[p]$ circuit using the method proposed in [33]. We have
the following state

$\ket{\psi^{(1)}}=C_{step\ 1}\ket{\psi}\ket{0}^{\otimes
t}=\sum_{x\in\mathbb{F}_{p}^{n}}\alpha_{x}\ket{x}^{\otimes\log_{p}(n)}\ket{\mathsf{GHZ}_{p,n}^{0}}^{\otimes\log_{p}(n)}\ket{0}^{\otimes
t^{\prime}}.$ (37)

For each $1\leq k\leq\log_{p}(n)$, we apply $n$ controlled rotations, where
the $j$-th rotation of the $k$-th block will have as control the $j$-th qudit
of the $k$-th copy of $\ket{x}$ and its target is the $j$-th qudit of the
$k$-th GHZ state. The amplitude for all rotations in the $k$-th block is set
to a fixed value of $\frac{2\pi}{p^{k}}$. Importantly, these operations can be
implemented in constant depth due to the parallel copies of $\ket{x}$.

For a fixed $x$, this process modifies the $k$-th GHZ state to

$\displaystyle\left(\bigotimes_{i=1}^{n}\mathsf{R}_{Z}^{p}\bigg{(}\frac{2\pi
x_{i}}{p^{k}}\bigg{)}\right)\ket{\mathsf{GHZ}_{p,n}^{0}}$
$\displaystyle=\sum_{x\in\mathbb{F}_{p}^{n}}\alpha_{x}\bigg{(}\frac{1}{\sqrt{p}}\sum_{j=0}^{p-1}e^{i\cdot\big{(}j\cdot\frac{2\pi}{p}\cdot\frac{|x|}{p^{k}}\big{)}}\ket{j}^{\otimes
n}\bigg{)}$ (38)
$\displaystyle=\sum_{x\in\mathbb{F}_{p}^{n}}\alpha_{x}\sum_{j=0}^{p-1}c_{j,k,x}\ket{\mathsf{GHZ_{p,n}^{j}}},$
(39)

with
$(c_{j,k,x})^{2}=e^{i\big{(}j\big{(}\frac{2\pi}{p}(1-\frac{|x|}{p^{k}}\big{)}\big{)}}$.

Note that for $|x|=0$, all these GHZ states remain unchanged and are equal to
$\ket{\mathsf{GHZ}_{p,n}^{0}}$. However, in contrast, we will now prove that
for all basis states $\ket{x}$ with $|x|\geq 1$, one of the $\log_{p}(n)$ GHZ
states we started with ends up in the form $\ket{\mathsf{GHZ}_{p,n}^{m}}$,
where $m\neq 0$. In other words, for each nonzero $x$, there exists one value
of $k$ for which $c_{j,k,x}$ equals $1$ for a single value of $j$ and $0$ for
all others. Meanwhile, for the same value of $x$ and all other values of $k$,
$c_{j,k,x}$ takes non-unitary values for all values of $j$. To establish this,
we utilize the fact that any integer number $|x|$ can always be decomposed as

$|x|=p^{a_{x}}(p\cdot b_{x}+m_{x}),$ (40)

with $a_{x},b_{x}\in\mathbb{N}$ and $m_{x}\in[1,2,\ldots,p-1]$. Hence, if
$|x|>0$, then we have that

$\left(\bigotimes_{i=1}^{n}\mathsf{R}_{Z}^{p}\bigg{(}\frac{2\pi
x_{i}}{p^{(a_{x}+1)}}\bigg{)}\right)\ket{\mathsf{GHZ}_{p,n}^{0}}=\ket{\mathsf{GHZ}_{p,n}^{m_{x}}},$
(41)

with $m_{x}\neq 0$ by definition. Therefore, $c_{j=m_{x},k=a_{x},x}=1$ and
$c_{j\neq m_{x},k=a_{x},x}=0$, while for all the other GHZ states, these
coefficients $c_{j,k\neq a_{x},x}$ are non-unital as
$\frac{2\pi}{p}(1-\frac{|x|}{p^{k}}\big{)}$ is not a multiple of $2\pi$. Thus,
the state resulting from this set of controlled rotations is the following
form,

$\displaystyle\ket{\psi^{(2)}}=$ $\displaystyle C_{step\
2}\bigg{(}\sum_{x\in\mathbb{F}_{p}^{n}}\alpha_{x}\ket{x}^{\otimes\log_{p}(n)}\ket{\mathsf{GHZ}_{p,n}^{0}}^{\otimes\log_{p}(n)}\bigg{)}\otimes\ket{0}^{\otimes
t^{\prime}}$ (42) $\displaystyle=$
$\displaystyle\Bigg{(}\alpha_{0^{n}}\ket{0}^{\otimes
n\log_{p}(n)}\ket{\mathsf{GHZ}_{p,n}^{0}}_{0}\ket{\mathsf{GHZ}_{p,n}^{0}}_{1}\ldots\ket{\mathsf{GHZ}_{p,n}^{0}}_{\log_{p}(n)}+\sum_{x\in\mathbb{F}_{p}^{n}\setminus
0^{n}}\alpha_{x}\ket{x}^{\otimes\log_{p}(n)}$ (43)
$\displaystyle\ldots\left(\sum_{j=0}^{p-1}c_{j,a_{x},x}\ket{\mathsf{GHZ}_{p,n}^{j}}\right)\ket{\mathsf{GHZ}_{p,n}^{m_{x}}}_{(a_{x}+1)}\left(\sum_{j=0}^{p-1}c_{j,(a_{x}+2),x}\ket{\mathsf{GHZ}_{p,n}^{j}}\right)\ldots\Bigg{)}\otimes\ket{0}^{\otimes
t^{\prime}}.$ (44)

We then apply Fourier gates $\mathsf{F}_{p}^{\otimes n}$ to the qudits
initially entangled in GHZ states. Employing Lemma 8, we deduce that when
$|x|=0$, the resultant states form a superposition of strings with a Hamming
weight congruent to zero modulo $p$. Conversely, for $|x|\geq 0$, at least one
state transitions into a superposition of strings congruent modulo $p$ to the
inverse of $m_{x}$. It is important to note that since $m_{x}\mod p$ is
invariably non-zero, its additive inverse $-m_{x}\mod p$ is likewise non-zero.
Subsequently, we apply a $\mathsf{qMOD}_{p}$ gate with each of these states as
control and as a target a new single qudit in a freshly initialized
computational basis state $\ket{0}$ in our third register. The existence of
the state described earlier ensures the $\mathsf{qOR}$’s intended effect, as
at least one qudit in the third register will deterministically shift to a
basis different from $\ket{0}$. For $|x|\geq 0$, since the GHZ states prior to
the Fourier gates are superpositions in the Qudit-GHZ orthogonal X-basis,
these strings after the Fourier gates are superpositions that align modulo $p$
with potentially any value in $\mathbb{F}_{p}$. Consequently, in the third
register, all other qudits assume superpositions dependent on the input, yet
they do not influence the $\mathsf{qOR}$ operation.

Afterward, we apply a layer of the inverses of the Fourier gates
$\mathsf{F}_{p}^{\otimes n}$ to exactly the same qudits in the second register
as before, and consequently, they revert to the same states as described in
Equations 43 and 44, being for all $k\in\\{1,\ldots,\log(n)\\}$ of the form

$\sum_{x\in\mathbb{F}_{p}^{n}}\alpha_{x}\bigg{(}\frac{1}{\sqrt{p}}\sum_{j=0}^{p-1}e^{i\cdot\big{(}j\cdot\frac{2\pi}{p}\cdot\frac{|x|}{p^{k}}\big{)}}\ket{j}^{\otimes
n}\bigg{)}=\sum_{x\in\mathbb{F}_{p}^{n}}\alpha_{x}\sum_{j=0}^{p-1}c_{j,k,x}\ket{\mathsf{GHZ}_{p,n}^{j}}.$
(45)

This is possible because previously, we simply applied a $\mathsf{qMOD}_{p}$
with these states as control and did not change the target qudits. Thus, these
states return to the same bases and states after the use of the inverse
Fourier gates. Therefore, after these operations, we obtain the subsequent
state, for which we do not represent the qudits of the third register in its
position but next to each GHZ state that generated each one of them for a
simpler representation.

$\displaystyle C_{step\ 3}\ket{\psi^{(2)}}\ket{0}^{\otimes
t^{\prime}}=\Bigg{(}\alpha_{0^{n}}\ket{0}^{\otimes(n\cdot\log_{p}(n))}\ket{\mathsf{GHZ}_{p,n}^{0}}_{0}\ket{\mathsf{GHZ}_{p,n}^{0}}_{1}\ldots\ket{\mathsf{GHZ}_{p,n}^{0}}_{\log_{p}(n)}\ket{0}^{\otimes\log_{p}(n)}$
(46) $\displaystyle+\sum_{x\in\mathbb{F}_{p}^{n}\setminus
0^{n}}\alpha_{x}\ket{x}^{\otimes\log_{p}(n)}\ldots\left(\sum_{j=0}^{p-1}c_{j,a_{x},x}\ket{\mathsf{GHZ}_{p,n}^{j}}\ket{-j}\right)\ket{\mathsf{GHZ}_{p,n}^{m_{x}}}_{(a_{x}+1)}\ket{-m_{x}}$
(47)
$\displaystyle\left(\sum_{j=0}^{p-1}c_{j,(a_{x}+2),x}\ket{\mathsf{GHZ}_{p,n}^{j}}\ket{-j}\right)\ldots\Bigg{)}\otimes\ket{0}^{\otimes
t^{\prime\prime}}.$ (48)

At this stage, all the qudits in the three registers are entangled. However,
we can disentangle the first and third registers from the second, which
contains the GHZ states. This disentanglement can be achieved using the third
register that retains the phase information of the equivalent of the GHZ
states, creating the entanglement between these two registers. For that, we
use generalized controlled rotations, with the control based on the qudits of
the third register, applied to one qudit of the respective GHZ state of
amplitude $\frac{2\pi}{p^{k}}$. For simplicity, we will consider first the
effect on a single basis of $\ket{x}$,

$\displaystyle\alpha_{x}\ket{x}^{\otimes\log_{p}(n)}\ldots\left(\sum_{j=0}^{p-1}c_{j,a_{x},x}\left(\mathsf{CGR}\left(\frac{2\pi}{p^{k}}\right)\ket{\mathsf{GHZ}_{p,n}^{j}}\ket{-j}\right)\right)\ldots$
(49)
$\displaystyle=\alpha_{x}\ket{x}^{\otimes\log_{p}(n)}\ldots\left(\frac{1}{\sqrt{p}}\sum_{j=0}^{p-1}e^{i\cdot\big{(}j\cdot\frac{2\pi}{p}\cdot\frac{|x|}{p^{k}}\big{)}}\left(\mathsf{CGR}\left(\frac{2\pi}{p^{k}}\right)\ket{j}^{\otimes
n}\ket{-j}\right)\right)\ldots$ (50)
$\displaystyle=\alpha_{x}\ket{x}^{\otimes\log_{p}(n)}\ldots\left(\frac{1}{\sqrt{p}}\sum_{j=0}^{p-1}e^{i\cdot\big{(}j\cdot\frac{2\pi}{p}\cdot\frac{|x|}{p^{k}}\big{)}}e^{i\cdot\big{(}-j\cdot\frac{2\pi}{p}\cdot\frac{|x|}{p^{k}}\big{)}}\ket{j}^{\otimes
n}\ket{-j}\right)\ldots$ (51)
$\displaystyle=\alpha_{x}\ket{x}^{\otimes\log_{p}(n)}\ldots\left(\sum_{j=0}^{p-1}\ket{\mathsf{GHZ}_{p,n}^{0}}\ket{-j}\right)\ldots\
.$ (52)

Now as the previous transformation is independent of the respective basis
$\ket{x}$, we obtain the following state,

$\displaystyle C_{step\ 4}\ket{\psi^{(3)}}\ket{0}^{\otimes
t^{\prime\prime}}=\Bigg{(}\alpha_{0^{n}}\ket{0}^{\otimes(n\cdot\log_{p}(n))}\ket{\mathsf{GHZ}_{p,n}^{0}}_{0}\ket{\mathsf{GHZ}_{p,n}^{0}}_{1}\ldots\ket{\mathsf{GHZ}_{p,n}^{0}}_{\log_{p}(n)}\ket{0}^{\otimes\log_{p}(n)}$
(53) $\displaystyle+\sum_{x\in\mathbb{F}_{p}^{n}\setminus
0^{n}}\alpha_{x}\ket{x}^{\otimes\log_{p}(n)}\ldots\ket{\mathsf{GHZ}_{p,n}^{0}}\left(\sum_{j=0}^{p-1}c_{j,a_{x},x}\ket{-j}\right)\ket{\mathsf{GHZ}_{p,n}^{0}}_{(a_{x}+1)}\ket{-m_{x}}$
(54)
$\displaystyle\ket{\mathsf{GHZ}_{p,n}^{0}}\left(\sum_{j=0}^{p-1}c_{j,(a_{x}+2),x}\ket{-j}\right)\ldots\Bigg{)}\otimes\ket{0}^{\otimes
t^{\prime\prime}}.$ (55)

Consequently, we end up with $\log_{p}(n)$ GHZ states of the form
$\ket{\mathsf{GHZ}_{p,n}^{0}}$, which are no longer entangled with the other
registers, as intended. These states and the repetitions of the initial state
can be easily removed using the fanout gates and their inverses888The inverse
of the $\mathsf{fanout}_{p}$ gate is simply $(\mathsf{fanout}_{p})^{p-1}$.
obtaining the following state,

$\displaystyle\ket{\psi^{(5)}}=C_{step\
5}\ket{\psi^{(4)}}=\Bigg{(}\alpha_{0^{n}}\ket{0}^{\otimes(n+\log_{p}(n))}+\sum_{x\in\mathbb{F}_{p}^{n}\setminus
0^{n}}\alpha_{x}\ket{x}\ldots\left(\sum_{j=0}^{p-1}c_{j,a_{x},x}\ket{-j}\right)\ket{-m_{x}}$
(56)
$\displaystyle\left(\sum_{j=0}^{p-1}c_{j,(a_{x}+2),x}\ket{-j}\right)\ldots\Bigg{)}\otimes\ket{0}^{\otimes
t^{\prime\prime\prime}}=\sum_{x\in\mathbb{F}_{p}^{n},\
y\in\mathbb{F}_{p}^{\log_{p}(n)}}\alpha_{x}\beta_{y,x}\ket{x}\ket{y}\otimes\ket{0}^{\otimes
t^{\prime\prime\prime}}.$ (57)

Finally, if we take $\ket{\psi^{*}}$ as $\ket{\psi^{5}}$ with the first and
second register swapped, we obtain that the former state satisfies the
property $\mathsf{qOR}\ket{0}\ket{\psi}=\mathsf{qOR}\ket{0}\ket{\psi^{*}}$ on
the first qudit, with the second $\mathsf{qOR}$ applied only to the first
$\log(n)$ qudits. This is justified by that fact that the basis
$\ket{0}^{\otimes\log_{p}(n)}$ in $\ket{\psi^{*}}$ has the same amplitude as
the basis $\ket{0}^{\otimes n}$ in $\ket{\psi}$. The same principle forcefully
applies to set all the bases orthogonal to the previously described, as
demonstrated in Equations 56 and 57. Therefore, the effect of the
$\mathsf{qOR}$ function on the first qudit state is equal for both cases
considered completing the proof. ∎

The second step shows an exponential-size
$\mathsf{i}\text{-}\mathsf{QNC}_{p}^{0}$ circuit for $\mathsf{qOR}$. For that,
we use the following theorem on the representation of functions as a multi-
linear polynomial over $\mathbb{F}_{p}$, expanding previous uses of these
objects over $\mathbb{F}_{2}$ and $\mathbb{F}_{3}$ [29, 31, 27].

######  Theorem 22.

[26] Every function $f:\mathbb{F}_{p}^{n}\rightarrow\mathbb{R}$ can be
expressed as a polynomial

$f(x)=\sum_{k_{1},k_{2},\ldots,k_{n}\in\mathbb{F}_{p}}\widehat{f}(\chi_{k_{1},k_{2},\ldots,k_{n}})\cdot\chi_{k_{1},k_{2},\ldots,k_{n}}(x),$
(58)

with $\widehat{f}(\chi_{k_{1},k_{2},\ldots,k_{n}})$ being a real coefficient,
and $\chi_{k_{1},k_{2},\ldots,k_{n}}(x)$ multi-linear function in
$\mathbb{F}_{p}$.

We now extend the techniques of [42] to show that our exponential-size circuit
for $\mathsf{qOR}$.

######  Lemma 23.

For any prime $p$, $\mathsf{qOR}$ can be implemented on an n-qudit state using
$\mathcal{O}(n\cdot p^{n})$ operations in
$\mathsf{i}\text{-}\mathsf{QNC}_{p}^{0}[p]$.

###### Proof.

Let us describe the $\mathsf{i}\text{-}\mathsf{QNC}_{p}^{0}$ circuit that
computes $\mathsf{qOR}$. The first layer of the circuit consists of $n-1$
fanout gates, where the $i$-th gate is controlled by the $(i+1)$-th qudit of
the initial state to a new register initialized to $\ket{0}^{\otimes
p^{n-1}}$. This maps the initial state $\ket{0}\ket{\psi}\ket{0}^{\otimes t}$
to

$\displaystyle\ket{0}\sum_{x\in\mathbb{F}_{p}^{n-1}}\alpha_{x}\ket{x}(\ket{x_{2},\ldots,x_{n}})^{\otimes
p^{n-1}}\ket{0}^{\otimes t^{\prime}}.$ (59)

We then apply $p^{n-1}$ parallel $\mathsf{qMOD}_{p}$ gates, where the $i$-th
gate is applied on the $i$-th block of the previous state, and the
$\mathsf{qMOD}_{p}$ computes a different $\chi_{k_{1},k_{2},\ldots,k_{n}}$
leading to

$\displaystyle\ket{0}\sum_{x\in\mathbb{F}_{p}^{n}}\alpha_{x}\ket{x}\left(\bigotimes_{k_{1},...,k_{n-1}\in\mathbb{F}_{p}}\ket{x_{2},\ldots,x_{n}}\ket{\chi_{k_{1},k_{2},\ldots,k_{n-1}}(x_{2},...,x_{n})}\right)\ket{0}^{\otimes
t^{\prime}}.$ (60)

We then create a $\ket{\mathsf{GHZ}_{p,p^{n-1}}^{0}}$ state and we apply
generalized controlled rotations as follows. The $i$-th rotation has as
control the register where $\chi_{k_{1},k_{2},\ldots,k_{n}}(x_{2},...,x_{n})$
is computed and the target is the $i$-th qudit of the GHZ state. The angle of
the rotation is
$\widehat{f}_{\overline{\mathsf{OR}}}(\chi_{k_{1},k_{2},\ldots,k_{n}})$. These
angles are defined by the $\overline{\mathsf{OR}}$ function which is defined
as follows,

$\overline{\mathsf{OR}}(x)=\begin{cases}p-1&\text{if
}\sum_{i=1}^{n}x_{i}>0,\\\ 0&\text{otherwise.}\end{cases}$ (61)

and that we decompose, according to Theorem 22 as

$\overline{\mathsf{OR}}(x)=\sum_{k_{1},k_{2},\ldots,k_{n}\in\mathbb{F}_{p}}\widehat{f}_{\overline{\mathsf{OR}}}(\chi_{k_{1},k_{2},\ldots,k_{n}})\cdot\chi_{k_{1},k_{2},\ldots,k_{n}}(x)$
(62)

to obtain the following state on this last register,

$\displaystyle\ket{\overline{\mathsf{OR}}}$
$\displaystyle=\sum_{x\in\mathbb{F}_{p}^{n}}\alpha_{x}\bigg{(}\frac{1}{\sqrt{p}}\sum_{j=0}^{p-1}e^{j\cdot\frac{\pi}{p}\big{(}\sum_{k_{1},k_{2},\ldots,k_{n-1}\in\mathbb{F}_{p}}\widehat{f}_{\overline{\mathsf{OR}}}(\chi_{k_{1},k_{2},\ldots,k_{n-1}})\cdot\chi_{k_{1},k_{2},\ldots,k_{n-1}}(x_{2}\ldots
x_{n})\big{)}}\ket{j}^{\otimes p^{n-1}}\bigg{)}$
$\displaystyle=\sum_{x\in\mathbb{F}_{p}^{n}}\alpha_{x}\bigg{(}\frac{1}{\sqrt{p}}\sum_{j=0}^{p-1}e^{\frac{j\cdot\pi\cdot\overline{\mathsf{OR}}(x_{2}\ldots
x_{n})}{p}}\ket{j}^{\otimes
p^{n-1}}\bigg{)}=\sum_{x\in\mathbb{F}_{p}^{n}}\alpha_{x}\ket{\mathsf{GHZ}_{p,p^{n-1}}^{\overline{\mathsf{OR}}(x_{2},\ldots,x_{n})}}.$

In the last step, we apply the Fourier gate to all the qudits in the newly
created state in the third register and a single use of the quantum modular
gate $\mathsf{qMOD}_{p}$ from all the qudits to the first qudit in the state
$\ket{0}$. Using Lemmas 7 and 8, we obtain the state

$\displaystyle\sum_{x\in\mathbb{F}_{p}^{n}}\alpha_{x}\ket{\overline{\mathsf{OR}}(x_{2}\ldots
x_{n})^{-1}}\ket{x_{1},x_{2},\ldots,x_{n}}$
$\displaystyle\left(\bigotimes_{k_{1},...,k_{n-1}}\ket{x_{2},\ldots,x_{n}}\ket{\chi_{k_{1},k_{2},\ldots,k_{n-1}}(x_{2},...,x_{n})}\right)\
\Bigg{(}\frac{1}{\sqrt{p^{n-2}}}\sum_{\begin{subarray}{c}z\in\mathbb{F}_{p}^{n-1}\\\
|z|\mod
p=-\overline{\mathsf{OR}}(x_{2},\ldots,x_{n})\end{subarray}}\ket{z}\Bigg{)}.$

Next, we apply a $\mathsf{SUM}$ gate to the first qudit, with the first qudit
from the initial state $\ket{\psi}$. This ensures we obtain the expected
output state from applying $\mathsf{qOR}$ function on the input state
$\ket{\psi}$ given that
$-\overline{\mathsf{OR}}(x_{2},\ldots,x_{n})=\mathsf{OR}(x_{2},\ldots,x_{n})$.
Finally, we execute the inverse operations on the auxiliary qudits to decouple
these from the input state. We can do this because all operations acting on
the input state and auxiliary qudits are unitary. In addition, the inverse
operations of $\mathsf{fanout}_{p}$, $\mathsf{qMod}_{p}$, and of the
controlled rotations—are all within $\mathsf{QNC}_{p}^{0}[p]$. See Appendix
A.2.1 for details on the first two operations. ∎

We now prove our first collapse of the different classes on constant-depth
quantum circuits.

######  Theorem 24.

$\mathsf{i}\text{-}\mathsf{QNC}_{p}[p]=\mathsf{i}\text{-}\mathsf{QAC}_{p}[p]$,
for any $p$ prime.

###### Proof.

To prove this collapse, we need only to show that $\mathsf{qOR}$ and the
$\mathsf{qAND}$ operation can be implemented by an
$\mathsf{i}\text{-}\mathsf{QNC}_{p}[p]$ circuit. The latter gate is already
the Toffoli $\mathsf{X}$ gate, which we can use to obtain any other multi-
qudit Toffoli gate.

To implement $\mathsf{qOR}$, we integrate circuits $C_{1}$ and $C_{2}$ from
Lemmas 21 and 23, respectively. Circuit $C_{1}$ effectively reduces the number
of qudits in the state $\ket{\psi}$, generating a new state $\ket{\psi^{*}}$
that preserves the $\mathsf{qOR}$ output alongside a fresh $\ket{0}$, and
$C_{2}$ performs the actual $\mathsf{qOR}$ computation. By applying $C_{1}$ to
all qudits of $\ket{\psi}$ except the first, and subsequently feeding
$\ket{0}\ket{\psi^{*}}$ to $C_{2}$. The global output is generated by applying
the $\mathsf{SUM}$ gate to the first qudit
$\sum_{x\in[p^{n-1}]}\alpha_{x_{2},\ldots,x_{n}}\ket{\mathsf{OR}(x_{2},\ldots,x_{n})}$
resulting from $C_{2}$ and the first qudit of the initial $\ket{\psi}$ state.

To conclude the proof, we return all auxiliary qudits to their initial state,
$\ket{0}^{\otimes t}$. Initially, we observe that $\log(n)$ auxiliary qudits
arise from the $\mathsf{OR}$ reduction. We then apply the exponentially large
$\mathsf{qOR}$ operator, described in Lemma 23, to these $\log_{p}(n)$ qudits.
Importantly, this step does not introduce additional auxiliary qudits. Thus,
our goal now is to reverse the state of these $\log(n)$ auxiliary qudits to
$\ket{0}^{\otimes\log_{p}(n)}$, without impacting the result obtained from the
$\mathsf{qOR}$ operation. We notice that undoing the operation on the
$\log(n)$ qubits is possible since the operations of Lemma 21 can be reverted
even if the first and second registers are entangled with the qubit where the
$\mathsf{qOR}$ was applied. This implies that the $\log(n)$ qudits were
unnecessary to achieve the intended final state. Hence, we can reversibly
return these qudits to their initial state without losing any information.

The reversal process is straightforward. We follow the steps used to generate
these $\log_{p}(n)$ qudits but omit the application of the $\mathsf{qMOD}$
operator, as delineated in Lemma 21. Instead, we employ the
$\mathsf{qMOD}^{p-1}$ operator. This ensures that all qudits are restored to
the $\ket{0}$ state, completing the process unitarily. ∎

For the next collapse, we need to demonstrate that the quantum threshold gate
is in $\mathsf{i}\text{-}\mathsf{QNC}_{p}^{0}[p]$. For that, we first
demonstrate that the quantum version of the $\mathsf{Exact}_{k}$ function is
contained in the same circuit class.

######  Definition 25.

$\mathbf{\mathsf{Exact}}_{k}$. The $\mathsf{Exact}_{k}$ function is defined as
follows,

$\mathsf{Exact}_{k}(x)=\begin{cases}1&\text{if }\sum_{i=1}^{n}x_{i}=k\\\
0&\text{otherwise}\end{cases},$ (63)

and its quantum analog as the following operation over Hilbert spaces of prime
dimension $p$

$\mathsf{qExact}_{k}\ket{x_{1},x_{2},\ldots,x_{n}}:=\ket{x_{1}+\mathsf{Exact}_{k}(x_{2},x_{3},\ldots,x_{n})\pmod{p},x_{2},\ldots,x_{n}}.$
(64)

######  Lemma 26.

For any prime $p$, $\mathsf{qExact}$ can be implemented in
$\mathsf{i}\text{-}\mathsf{QNC}_{p}^{0}[p]$.

###### Proof.

We approach this problem once again using a constructive method, retaining
most elements from the circuit used for the $\mathsf{qOR}$ function. The
$\mathsf{qOR}$ function fundamentally discerns whether a computational basis
state has a Hamming weight of zero. However, the initial step involving the
$\mathsf{qOR}$ reduction will be modified. Previously, this reduction applied
controlled rotations to GHZ states, effectively implementing a rotation with
an amplitude proportional to the Hamming weight of the computational basis
states, denoted as $\frac{2\pi|x|}{p^{i}}$. The new circuit introduces
additional rotations to each $i$-th GHZ state with an amplitude of
$-\frac{2\pi k}{p^{i}}$ respectively. This supplemental rotation emulates the
behavior of the original circuit, equating the effects of a string with a
Hamming weight of zero to those of a string with a Hamming weight of $k$. As a
result, when these modified states are subsequently processed by the remaining
$\mathsf{qOR}$ circuitry, the outcome will precisely compute the
$\mathsf{qExact}_{k}$ function. ∎

Using Lemma 26, we push the collapse of Theorem 24 further to constant-depth
quantum circuits with threshold gates.

######  Theorem 27.

For any prime $p$,
$\mathsf{i}\text{-}\mathsf{QNC}_{p}[p]=\mathsf{i}\text{-}\mathsf{QTC}_{p}$.

###### Proof.

To prove this statement, it is sufficient to show that $\mathsf{qTH}_{k}$ can
be implemented in $\mathsf{i}\text{-}\mathsf{QNC}_{p}[p]$. The circuit for
$\mathsf{qTH}_{k}$ is composed of $n-k$ $\mathsf{qExact}_{t}$ operations
(described in Lemma 26) for which $t$ will range from $k$ to $n$. In this
setup, the fanout gate is employed to parallelize the application of the
$\mathsf{qExact}_{t}$ operations. As a result, we generate states of the form
$\sum_{x\in\mathbb{F}_{p}^{n-1}}\alpha_{x}\ket{\mathsf{Exact}_{k}(x_{2}\ldots
x_{n})}\ket{x}$ based on the input state
$\ket{\psi}=\sum_{x\in\mathbb{F}_{p}^{n}}\alpha_{x}\ket{0}^{\otimes(n-k)}\ket{x}$.

Subsequently, the $\mathsf{qOR}$ gate will be applied to all these states, and
a computational basis state $\ket{0}$, obtained with the following state,

$\displaystyle\sum_{x\in\mathbb{F}_{p}^{n}}\alpha_{x}$
$\displaystyle\ket{\mathsf{OR}(\mathsf{Exact}_{k}(x_{2}\ldots
x_{n}),\mathsf{Exact}_{k+1}(x_{2}\ldots
x_{n}),\ldots,\mathsf{Exact}_{n}(x_{2}\ldots x_{n}))}$ (65)
$\displaystyle\ket{\mathsf{Exact}_{k}(x_{2}\ldots
x_{n})}_{k}\ldots\ket{\mathsf{Exact}_{k}(x_{2}\ldots
x_{n})}_{n}\ket{x}^{\otimes(n-k)}$ (66)
$\displaystyle=\sum_{x\in\mathbb{F}_{p}^{n}}\alpha_{x}$
$\displaystyle\ket{\mathsf{TH}_{k}(x_{1}\ldots
x_{n})}\ldots\ket{x}^{\otimes(n-k)}\ .$ (67)

It requires only applying the $\mathsf{SUM}$ gate between the first qudit and
the first qudit of the state $\ket{\psi}$, and we obtain the state resulting
from applying the $\mathsf{qTH}_{k}$ on the input state $\ket{\psi}$. The last
step resumes applying all the inverse unitaries on the auxiliary qudits to
detangle those from the resulting state. Lastly, we apply the inverse
unitaries to all auxiliary qudits, disentangling them from the final state
while preserving the desired output. ∎

###  3.2 Constant-depth qudit circuits with classical modular operators

In this section, we consider the collapse of constant-depth circuits with
infinite-size quantum gate sets and classical modular gates.

We first show that quantum modular gates can be implemented with constant
depth measurement patterns and classical modular gates.

######  Lemma 28.

The $\mathsf{qMOD}_{p}$ gate can be implemented in
$\mathsf{i}\text{-}\mathsf{QNC}_{p}^{0}[p]_{\mathsf{c}}$.

###### Proof.

Our first step in this proof is to show that a circuit in
$\mathsf{i}\text{-}\mathsf{QNC}_{p}^{0}[p]_{\mathsf{c}}$ can implement the
$\mathsf{fanout}_{p}$ gate over an arbitrary quantum state,
$\ket{\psi}=\sum_{x\in\\{0,1,\ldots,p-1\\}^{n}}\alpha_{x}\ket{x}$.

For that, we first create an $\ket{\mathsf{GHZ}_{p,n}^{0}}$ state and apply a
$\mathsf{SUM}$ where the control-qudit is the first qudit of $\ket{\psi}$ and
the target is the first qudit of the GHZ state. This leads to the state,

$\ket{\psi^{(1)}}=\sum_{x\in\mathbb{F}_{p}^{n}}\alpha_{x}(\mathsf{I}^{\otimes
n}\otimes(\mathsf{X}_{p})^{x_{1}}\otimes\mathsf{I}^{\otimes(n-1)})\ket{x}\ket{\mathsf{GHZ}_{p}^{0}}\
.$ (68)

Subsequently, we measure the first qudit of the second register with outcome
$m_{1}\in\\{0,1,\ldots,p-1\\}$. The post-measured state will then be

$\ket{\psi^{(2)}}=\sum_{x\in\mathbb{F}_{p}^{n}}\alpha_{x}\ket{x_{1},x_{2}\ldots
x_{n},m_{1},(x_{1}+m_{1})\mod p,\ldots,(x_{1}+m_{1})\mod p}\ .$ (69)

We then apply $(\mathsf{X}_{p})^{-m_{1}}$ to each of the $n-1$ qudits of the
second register, leading to the state

$\ket{\psi^{(3)}}=\sum_{x\in\mathbb{F}_{p}^{n}}\alpha_{x}\ket{x_{1},x_{2},\ldots,x_{n},m_{1},x_{1},\ldots,x_{1}}\
.$ (70)

Using this state, we can apply a layer of $n-1$ parallel $\mathsf{SUM}$ gates
where the control gate is one of the $n-1$ last qudits, and the target is one
of the qudits from the $2$nd to the $n$-th qudit in the first register.
Resulting in the following state

$\ket{\psi^{(4)}}=\sum_{x\in\mathbb{F}_{p}^{n}}\alpha_{x}\ket{x_{1},(x_{2}+x_{1})\
\mathsf{mod}\ p,\ldots,(x_{n}+x_{1})\ \mathsf{mod}\
p,m_{1},x_{1},\ldots,x_{1}}\ ,$ (71)

which is equivalent to applying the $\mathsf{fanout}_{p}$ gate on state
$\ket{\psi^{(3)}}$.

The last step is to remove the entanglement between the first $n$ qudits and
the last $n-1$ ones. For that, we apply the Fourier gate to the last $n-1$
qudits, and we have

$\displaystyle\ket{\psi^{(5)}}=$
$\displaystyle\frac{1}{\sqrt{p^{n}}}\sum_{m_{2}\ldots
m_{n}\in\mathbb{F}_{p}^{n-1}}\sum_{x\in\mathbb{F}_{p}^{n}}\alpha_{x}\cdot
e^{i\frac{-2\pi x_{1}\left(\sum_{i=2}^{n}m_{i}\right)}{p}}$ (72)
$\displaystyle\ket{x_{1},(x_{2}+x_{1})\ \mathsf{mod}\
p,\ldots,(x_{n-1}+x_{1})\ \mathsf{mod}\ p,m_{1},\ldots,m_{n}}\ .$ (73)

We can then measure the last $n-1$ qudits with outcome
$m_{2},...,m_{n}\in\mathbb{F}_{p}$ to determine the value of
$\phi=-\sum_{i=2}^{n}m_{i}\pmod{p}$ and apply a controlled generalized
rotation $\mathsf{CGR}_{Z}^{p}$ with control on $x_{1}$ and parameterized by
$\phi$ to remove the relative phase introduced by the Fourier gates999The
value of $\phi$ is classical and can be determined using the classical
$\mathrm{MOD}_{p}$ gates with a binary outcome in the form of $p$ bits, with
only one of them being equal to $1$, determining the value $\phi$. . Tracing
out the measured states, we have the state

$\ket{\psi^{(6)}}=\sum_{x\in\mathbb{F}_{p}^{n}}\alpha_{x}\ket{x_{1},(x_{2}+x_{1})\
\mathsf{mod}\ p,\ldots,(x_{n}+x_{1})\ \mathsf{mod}\ p}\ .$ (74)

which corresponds to state $(\mathsf{fanout_{p}}\ket{\psi})$, as intended.

Finally, we only need to use the circuit that translates the
$\mathsf{fanout}_{p}$ gate to the $\mathsf{qMOD}_{p}$ gate, using simply the
standard translation presented by qubits [22] in higher dimensions with the
Fourier gates. This and the fact that all the sub-processes described
previously are contained in
$\mathsf{i}\text{-}\mathsf{QNC}_{p}^{0}[p]_{\mathsf{c}}$ completes the proof.
∎

Using this lemma and the results in the previous subsection we can prove the
following.

######  Lemma 29.

For any prime $p$,
$\mathsf{i}\text{-}\mathsf{QNC}_{p}[p]_{\mathsf{c}}=\mathsf{i}\text{-}\mathsf{QTC}_{p}$.

###### Proof.

It follows from Lemma 28 that
$\mathsf{i}\text{-}\mathsf{QNC}_{p}[p]_{\mathsf{c}}=\mathsf{i}\text{-}\mathsf{QNC}_{p}^{0}[p]$.
The result follows since
$\mathsf{i}\text{-}\mathsf{QTC}_{p}=\mathsf{i}\text{-}\mathsf{QNC}_{p}^{0}[p]$
from Theorem 27. ∎

Lemma 29 shows that the implementation of constant-depth MBQC over prime
dimensional qudits is capable of the same type of circuit collapses as all the
ones that have been demonstrated for qubits. Now we show how these circuit
classes compare to each other.

######  Theorem 30.

For any $p$ and $q$ prime.
$\mathsf{i}\text{-}\mathsf{QTC}_{p}^{0}\subseteq\mathsf{i}\text{-}\mathsf{QNC}_{2}^{0}[q]_{\mathsf{c}}$.

###### Proof.

The proof proceeds in two steps. Firstly, we show that
$\mathsf{i}\text{-}\mathsf{QNC}_{q}^{0}$ and
$\mathsf{i}\text{-}\mathsf{QNC}_{p}^{0}$ are contained in
$\mathsf{i}\text{-}\mathsf{QNC}_{2}^{0}$ for any primes $p$ and $q$. To
establish this, we need a mapping from the qudit basis to the qubit basis for
both prime dimensions, $p$ and $q$. For example, qutrits can be mapped to
qubits using the following correspondence:
$\ket{0}\rightarrow\ket{00},\ket{1}\rightarrow\ket{01}$ and
$\ket{2}\rightarrow\ket{11}$, utilizing only a subspace of the Hilbert space
of dimension 4. Consequently, any qudit can be translated into $2\lceil
p/2\rceil$ qubits. Additionally, any unitary operator over a Hilbert space of
dimensions $p$ and $2p$ can be mapped to a unitary operator over a Hilbert
space of dimensions $2\lceil p/2\rceil$ and $4\lceil p/2\rceil$. This new
operator applies the same transformation over the encoded qubit basis as the
original did over the qudits, while the basis ignored by the encoding is
operated by the identity locally.

This argument can be augmented with the demonstration that all such fixed
sizes can be constructed in constant depth using single and two-qubit gates,
as described in [37] and [2]. These methods prove that any unitary operator on
$k$ qubits can be synthesized using at most $\mathcal{O}(k^{3}4^{k})$ two-
qubit gates. This further suggests that all operations in
$\mathsf{i}\text{-}\mathsf{QNC}_{q}^{0}$ and
$\mathsf{i}\text{-}\mathsf{QNC}_{p}^{0}$ can be executed by an
$\mathsf{i}\text{-}\mathsf{QNC}_{2}^{0}$ circuit with a specific encoding for
each prime dimension.

Given that all operations in $\mathsf{i}\text{-}\mathsf{QNC}_{q}^{0}$ can be
achieved within $\mathsf{i}\text{-}\mathsf{QNC}_{2}^{0}$, it follows that all
operations in $\mathsf{i}\text{-}\mathsf{QNC}_{q}^{0}[q]_{\mathsf{c}}$ also
belong to $\mathsf{i}\text{-}\mathsf{QNC}_{2}^{0}[q]_{\mathsf{c}}$. This
implies that $\mathsf{i}\text{-}\mathsf{QNC}_{2}^{0}[q]_{\mathsf{c}}$ contains
the $\mathrm{MOD}_{p}$ gate. Coupled with the fact that
$\mathsf{i}\text{-}\mathsf{QNC}_{2}^{0}$ can implement all the operations in
$\mathsf{i}\text{-}\mathsf{QNC}_{p}^{0}$, we deduce that
$\mathsf{i}\text{-}\mathsf{QNC}_{2}^{0}[q]_{\mathsf{c}}$ can execute all
operations in $\mathsf{i}\text{-}\mathsf{QNC}_{p}^{0}[p]_{\mathsf{c}}$ for any
given prime $p$. The final piece to consider is Lemma 29, which allows us to
arrive at the desired result. ∎

Building on this result, we can also extend the quantum-classical separations
illustrated by [18] and [42], which separated
$\mathsf{i}\text{-}\mathsf{QNC}_{2}^{0}[2]$ from the classical
$\mathsf{AC}^{0}[p]$ classes.

######  Corollary 31.

For all $p$ and $q$ prime,
$\mathsf{i}\text{-}\mathsf{QNC}_{2}^{0}[q]_{\mathsf{c}}\nsubseteq\mathsf{AC}^{0}[p]$.

###### Proof.

The $\mathsf{i}\text{-}\mathsf{QNC}_{2}^{0}[q]_{\mathsf{c}}$ class contains
all the operations of $\mathsf{i}\text{-}\mathsf{QNC}_{q}^{0}$; therefore, it
contains all the operations in $\mathsf{i}\text{-}\mathsf{QTC}_{q}^{0}$, which
include all the $\mathrm{MOD}_{k}$ operations, with $k$ prime. This is
combined with Razborov-Smolensky separations (Theorem 35), which states that
all $\mathsf{AC}^{0}[p]$ classes fail to compute any $\mathrm{MOD}_{k}$ gate
other than the $\mathrm{MOD}_{p}$ gate with $p$ and $k$ being two distinct
prime numbers finishes the proof. ∎

## References

  * [1] Sanjeev Arora and Boaz Barak.  Computational complexity: a modern approach.  Cambridge University Press, 2009.
  * [2] Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter.  Elementary gates for quantum computation.  Phys. Rev. A, 52:3457–3467, Nov 1995.
  * [3] Adam Bene Watts and Natalie Parham.  Unconditional Quantum Advantage for Sampling with Shallow Circuits.  arXiv e-prints, page arXiv:2301.00995, January 2023.
  * [4] Debajyoti Bera.  A lower bound method for quantum circuits.  Information processing letters, 111(15):723–726, 2011.
  * [5] Robert Ivan Booth.  Measurement-based quantum computation beyond qubits.  Theses, Sorbonne Université, February 2022.
  * [6] Sergey Bravyi, David Gosset, and Robert König.  Quantum advantage with shallow circuits.  Science, 362(6412):308–311, 2018.
  * [7] Sergey Bravyi, Isaac Kim, Alexander Kliesch, and Robert Koenig.  Adaptive constant-depth circuits for manipulating non-abelian anyons.  arXiv preprint arXiv:2205.01933, 2022.
  * [8] Sergey Bravyi, Dmitri Maslov, and Yunseong Nam.  Constant-cost implementations of clifford operations and multiply-controlled gates using global interactions.  Physical Review Letters, 129(23):230501, 2022.
  * [9] Jop Briët, Harry Buhrman, Davi Castro-Silva, and Niels MP Neumann.  Noisy decoding by shallow circuits with parities: classical and quantum.  arXiv preprint arXiv:2302.02870, 2023.
  * [10] Dan Browne, Elham Kashefi, and Simon Perdrix.  Computational depth complexity of measurement-based quantum computation.  In Wim van Dam, Vivien M. Kendon, and Simone Severini, editors, Theory of Quantum Computation, Communication, and Cryptography, pages 35–46, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.
  * [11] Dan Browne, Elham Kashefi, and Simon Perdrix.  Computational depth complexity of measurement-based quantum computation.  In Wim van Dam, Vivien M. Kendon, and Simone Severini, editors, Theory of Quantum Computation, Communication, and Cryptography, pages 35–46, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.
  * [12] Daniel E Browne, Elham Kashefi, Mehdi Mhalla, and Simon Perdrix.  Generalized flow and determinism in measurement-based quantum computation.  New Journal of Physics, 9(8):250, aug 2007.
  * [13] Matthew Coudron, Jalex Stark, and Thomas Vidick.  Trading locality for time: certifiable randomness from low-depth circuits.  Communications in mathematical physics, 382:49–86, 2021.
  * [14] M. Fang, S. Fenner, F. Green, S. Homer, and Y. Zhang.  Quantum lower bounds for fanout.  Quantum Info. Comput., 6(1):46–57, jan 2006.
  * [15] Merrick Furst, James B Saxe, and Michael Sipser.  Parity, circuits, and the polynomial-time hierarchy.  Mathematical systems theory, 17(1):13–27, 1984.
  * [16] Oded Goldreich.  Three xor-lemmas—an exposition.  Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation: In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman, pages 248–272, 2011.
  * [17] Oded Goldreich.  On teaching the approximation method for circuit lower bounds.  Eletronical Colloquium on Computational Complexity, 2023.
  * [18] Frederic Green, Steven Homer, Cristopher Moore, and Christopher Pollett.  Counting, fanout and the complexity of quantum acc.  Quantum Info. Comput., 2(1):35–65, dec 2002.
  * [19] Daniel Grier and Luke Schaeffer.  Interactive shallow clifford circuits: Quantum advantage against nc¹ and beyond.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, page 875–888, New York, NY, USA, 2020. Association for Computing Machinery.
  * [20] Koen Groenland, Freek Witteveen, Kareljan Schoutens, and Rene Gerritsma.  Signal processing techniques for efficient compilation of controlled rotations in trapped ions.  New Journal of Physics, 22(6):063006, 2020.
  * [21] Nikodem Grzesiak, Andrii Maksymov, Pradeep Niroula, and Yunseong Nam.  Efficient quantum programming using ease gates on a trapped-ion quantum computer.  Quantum, 6:634, 2022.
  * [22] Peter Høyer and Robert Špalek.  Quantum fan-out is powerful.  Theory of Computing, 1(5):81–103, 2005.
  * [23] Yanglin Hu, Darya Melnyk, Yuyi Wang, and Roger Wattenhofer.  Space complexity of streaming algorithms on universal quantum computers.  In Theory and Applications of Models of Computation: 16th International Conference, TAMC 2020, Changsha, China, October 18–20, 2020, Proceedings 16, pages 275–286. Springer, 2020.
  * [24] Richard Jozsa.  An introduction to measurement based quantum computation.  NATO Science Series, III: Computer and Systems Sciences. Quantum Information Processing-From Theory to Experiment, 199:137–158, 2006.
  * [25] Zhenning Liu and Alexandru Gheorghiu.  Depth-efficient proofs of quantumness.  Quantum, 6:807, September 2022.
  * [26] Bao Luong.  Fourier analysis on finite Abelian groups.  Springer Science & Business Media, 2009.
  * [27] Jelena Mackeprang, Daniel Bhatti, Matty J Hoban, and Stefanie Barz.  The power of qutrits for non-adaptive measurement-based quantum computing.  New Journal of Physics, 25(7):073007, jul 2023.
  * [28] Dmitri Maslov and Yunseong Nam.  Use of global interactions in efficient quantum circuit constructions.  New Journal of Physics, 20(3):033018, 2018.
  * [29] Ryuhei Mori.  Periodic fourier representation of boolean functions.  arXiv preprint arXiv:1803.09947, 2018.
  * [30] Shivam Nadimpalli, Natalie Parham, Francisca Vasconcelos, and Henry Yuen.  On the Pauli Spectrum of QAC0.  arXiv e-prints, page arXiv:2311.09631, November 2023.
  * [31] Michael de Oliveira, Luís S. Barbosa, and Ernesto F. Galvão.  Quantum advantage in temporally flat measurement-based quantum computation.  Quantum, 8:1312, April 2024.
  * [32] Daniel Padé, Stephen Fenner, Daniel Grier, and Thomas Thierauf.  Depth-2 qac circuits cannot simulate quantum parity.  arXiv preprint arXiv:2005.12169, 2020.
  * [33] Filipa C. R. Peres.  The Pauli-based model of quantum computation with higher dimensional systems.  arXiv e-prints, page arXiv:2302.13702, February 2023.
  * [34] John Preskill.  Quantum Computing in the NISQ era and beyond.  Quantum, 2:79, August 2018.
  * [35] Robert Raussendorf and Hans J. Briegel.  A one-way quantum computer.  Phys. Rev. Lett., 86:5188–5191, May 2001.
  * [36] Robert Raussendorf and Hans J. Briegel.  Computational model underlying the one-way quantum computer.  Quantum Info. Comput., 2(6):443–486, oct 2002.
  * [37] Michael Reck, Anton Zeilinger, Herbert J. Bernstein, and Philip Bertani.  Experimental realization of any discrete unitary operator.  Phys. Rev. Lett., 73:58–61, Jul 1994.
  * [38] Gregory Rosenthal.  Bounds on the $qac^{0}$ complexity of approximating parity.  arXiv preprint arXiv:2008.07470, 2020.
  * [39] Benjamin Rossman, Rocco A. Servedio, and Li-Yang Tan.  Complexity theory column 89: The polynomial hierarchy, random oracles, and boolean circuits.  SIGACT News, 46(4):50–68, dec 2015.
  * [40] Atul Singh Arora, Andrea Coladangelo, Matthew Coudron, Alexandru Gheorghiu, Uttam Singh, and Hendrik Waldner.  Quantum Depth in the Random Oracle Model.  arXiv e-prints, page arXiv:2210.06454, October 2022.
  * [41] R. Smolensky.  Algebraic methods in the theory of lower bounds for boolean circuit complexity.  In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC ’87, page 77–82, New York, NY, USA, 1987. Association for Computing Machinery.
  * [42] Yasuhiro Takahashi and Seiichiro Tani.  Collapse of the hierarchy of constant-depth exact quantum circuits.  computational complexity, 25:849–881, 2016.
  * [43] Maarten Van den Nest, Akimasa Miyake, Wolfgang Dür, and Hans J. Briegel.  Universal resources for measurement-based quantum computation.  Phys. Rev. Lett., 97:150504, Oct 2006.
  * [44] Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal.  Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 515–526, 2019.

##  Appendix A Preliminaries

###  A.1 Classical circuit classes

Circuit classes form a crucial aspect of computational theory, helping to
categorize and understand the computational capabilities of various models.
Certain classical circuit classes emerge as especially relevant when studying
constant-depth quantum circuits. This subsection will list and define the main
classes of interest while also summarizing pertinent theorems associated with
them.

######  Definition 32 ($\mathsf{NC}^{k}$ class).

The $\mathsf{NC^{k}}$ class is defined as the computational problems that can
be solved in poly-logarithmic depth $log(n)^{k}$ using polynomially-many
gates. The gate set for this class comprises the following bounded fan-in
gates,

AND,OR,NOT$\\}$.$\\{$

######  Definition 33 ($\mathsf{AC}^{k}$ class).

The $\mathsf{AC^{k}}$ class is defined as the computational problems that can
be solved in poly-logarithmic depth $log(n)^{k}$ using polynomial-many gates.
The gate set for this class comprises the following unbounded fan-in gates,

AND,OR,NOT$\\}$.$\\{$

######  Definition 34.

$(\mathsf{AC}^{k}[p]\ \mathsf{class})$. The $\mathsf{AC}^{k}[p]$ class is
defined as the computational problems that can be solved in poly-logarithmic
depth $log(n)^{k}$ using polynomial-many gates. The gate set for this class
comprises the following unbounded fan-in gates,

AND,OR,$\mathrm{MOD}_{p}$,NOT$\\}$,$\\{$

with $\mathrm{MOD}_{p}$ gate defined as follows,

$\mathsf{MOD_{p}}(x)=\begin{cases}1&\text{if }\sum_{i=1}^{n}x_{i}\mod p=0\\\
0&\text{if }\sum_{i=1}^{n}x_{i}\mod p\neq 0\end{cases}.$ (75)

The Razborov-Smolensky separations between all the $\mathsf{AC}^{0}[p]$
classes will be fundamental to establishing new separations between these and
quantum constant depth circuit classes.

######  Theorem 35.

[41] Let $p$ be a prime number, and $q$ is not a power of $p$, then computing
$\mathrm{MOD}_{p}$ with a depth $d$, $\mathsf{AC}^{0}[q]$ circuit, requires
$\exp(\Omega(n^{1/2d}))$ size.

Furthermore, it should be noted that this theorem implies that when we
construct a graph using the $\mathsf{AC}^{0}[q]$ classes as vertices and draw
edges between pairs of classes that are not subsets of each other, we obtain a
complete graph. Thus, for each edge, at least two problems distinguish one
class from the other (see Figure 4).

$AC^{0}[2]$$AC^{0}[3]$$AC^{0}[5]$$AC^{0}[p]$$AC^{0}[q]$$\mathrm{MOD}_{2},\mathrm{MOD}_{3}$””$\mathrm{MOD}_{2},\mathrm{MOD}_{p}$””
$\mathrm{MOD}_{2},\mathrm{MOD}_{q}$””$\mathrm{MOD}_{p},\mathrm{MOD}_{q}$$\nsupseteqq\
,\ \nsubseteq$ Figure 4: Graph representation of $\mathsf{AC}^{0}[p]$ classes
with $p$ prime. Each edge denotes that the connected classes are distinct,
without one being a subset of the other. Along the edges, examples highlight
problems that are in one class but excluded from the other.

######  Definition 36 ($\mathsf{TC}^{k}$ class).

The $\mathsf{TC}^{k}$ class is defined as the computational problems that can
be solved in poly-logarithmic depth $log(n)^{k}$ using polynomial-many gates.
The gate set for this class comprises the following unbounded fan-in gates,

AND,OR,$\mathsf{TH}_{t}$,NOT$\\}$,$\\{$

with $\mathsf{TH}_{k}$ gate defined as follows,

$\mathsf{TH_{t}}(x)=\begin{cases}1&\text{if }\sum_{i=1}^{n}x_{i}\geq t\\\
0&\text{if }\sum_{i=1}^{n}x_{i}<t\end{cases}.$ (76)

We introduce a class that is not standard in circuit complexity literature but
holds significance for the discussions and results presented in this text.

######  Definition 37.

$(\mathsf{NC}^{0}[p]$ class$)$. The $\mathsf{NC}^{k}[p]$ class is defined as
the computational problems that can be solved in poly-logarithmic depth
$log(n)^{k}$ using polynomial-many gates. The gate set for this class
comprises the bounded fan-in $\mathsf{AND}$, $\mathsf{OR}$, $\mathsf{NOT}$
gates, and a single unbounded fan-in $\mathsf{Mod\ p}$ gates.

A considerable number of important results in computational complexity pertain
to the circuit classes we have defined, as well as their interrelations [15,
41, 39, 1]. Consequently, we will present the established containments for
these classes,

$\mathsf{NC}^{0}\subsetneq\mathsf{AC}^{0},\mathsf{NC}^{0}[p]\subsetneq\mathsf{AC}^{0}[p]\subsetneq\mathsf{TC}^{0}\subseteq\mathsf{NC}^{1}.$
(77)

This knowledge is crucial for comprehending the capabilities of each circuit
class and discerning the position of quantum circuit classes relative to them.

Lastly, we will present the Vazirani-XOR lemma, which is of great interest to
the study of parallel repeated games. This lemma is of particular interest for
the analysis of constant-depth circuits and will be used to improve our
classical hardness results.

######  Lemma 38.

(Vazirani’s XOR Lemma [16]). Let $D$ be a distribution on $\mathbb{F}_{2}^{m}$
and $\chi_{S}$ denote the parity function on the set $S\subseteq[m]$, defined
as $\chi_{S}(x)=\oplus_{i\in S}x_{i}$. If $|\mathbb{E}_{x\in
D}[(-1)^{\chi_{S}(x)}]|\leq\epsilon$ for every nonempty subset
$S\subseteq[m]$, then $D$ is $\epsilon\cdot 2^{m/2}$-close in statistical
distance to the uniform distribution over $\mathbb{F}_{2}^{m}$.

###  A.2 Quantum computation with qudits

We first review the basic operations on qudits, and then explain the qudit
MBQC model.

####  A.2.1 Qudit operations

In this preliminary section, we present the qudit gates that will be employed
in subsequent sections of the text to construct the quantum circuits essential
for our main proofs.

The first qudit operation that we will define will be a generalized version of
the qubit $X$ gate.

######  Definition 39 (X qudit gate).

The $\mathsf{X}$ gate for qudits is defined as follows,

$\mathsf{X}_{d}\ket{m}:=\ket{m+1\mod d}\ .$ (78)

Then a rotation about the Z axis will be defined as follows,

######  Definition 40 (Rotation Z qudit gate).

The rotation Z operator for qudits is defined as follows,

$\mathsf{R}_{Z}^{d}(\phi):=\sum_{j=0}^{d-1}e^{i(1-sgn(d-1-j)\phi)}\ket{j}\bra{j}\
.$ (79)

In addition, we will define and make use of a more complex rotation Z
operator.

######  Definition 41 (Generalized rotation Z qudit gate).

The generalized rotation Z operator for qudits is defined as follows,

$\mathsf{GR}_{Z}^{d}(\phi):=\sum_{j=0}^{d-1}e^{i(\phi j)}\ket{j}\bra{j}\ .$
(80)

The last single qudit operation will be the qudit Hadamard gate.

######  Definition 42 (Fourier gate).

The Fourier gate is defined as follows

$\mathsf{F}_{d}\ket{m}=\frac{1}{\sqrt{d}}\sum_{n\in\mathbb{Z}_{d}}w^{mn}\ket{n},$
(81)

with $w=e^{i\frac{2\pi}{d}}$.

Now the respective two qudit gates of interest are the qudit $\mathsf{CNOT}$
gate and the controlled rotation Z gate.

######  Definition 43 ($\mathsf{SUM}$ gate).

The $\mathsf{SUM}$ gate is defined as follows,

$\mathsf{SUM}\ket{n}\ket{m}=\ket{n}\ket{n+m}.$ (82)

######  Definition 44 (Controlled generalized rotation Z qudit gate).

The $\mathsf{CGR}_{Z}^{d}$ gate is defined as follows,

$\mathsf{CGR}_{Z}^{d}\ket{n}\ket{m}=\ket{n}(\mathsf{GR}_{Z}^{d})^{n}\ket{m}.$
(83)

The last two multi-qudit operations are the following.

######  Definition 45 ($\mathsf{fanout}_{p}^{-1}$).

The $\mathsf{fanout}_{p}^{-1}$ gate is defined as follows,

$\mathsf{fanout}_{p}^{-1}\ket{x_{0},x_{1},\ldots,x_{n}}:=\ket{x_{0},(p-x_{0})+x_{1}\mod
p,\ldots,(p-x_{0})+x_{n}\mod p},$ (84)

and can be implemented with $(\mathsf{fanout}_{p})^{p-1}$.

######  Definition 46 ($\mathsf{qMOD}_{p}^{-1}$).

The $\mathsf{qMOD}_{p}^{-1}$ gate is defined as follows,

$\mathsf{qMOD}_{p}^{-1}\ket{x_{0},x_{1},\ldots,x_{n}}:=\ket{x_{0}+(p-x_{1}+\ldots+x_{n})\mod
p,x_{1},\ldots,x_{n}\mod p},$ (85)

and can be implemented with $(\mathsf{qMOD}_{p})^{p-1}$.

####  A.2.2 Qudit MBQC

The measurement-based quantum computation (MBQC) model was first introduced in
[35, 36]. Unlike the standard circuit model, MBQC operates by performing
measurements on universal quantum resource states [43]. Although these two
models have a very different nature, they are computationally equivalent
modulo a polynomial overhead. In this work, the generalization of MBQC to
qudits [5] is especially relevant, since the circuits arising from this model
exactly characterize the circuit classes, which we will analyze in detail.

In qudit MBQC, quantum algorithms are commonly referred to as measurement
patterns. These patterns are defined by both a resource state and a distinct
set of measurement operators for each qudit in the resource state. A
noteworthy aspect is the existence of adaptivity, defined by the
interdependencies between the measurement operators and their resulting
outcomes. These interdependencies guide the information flow within the
quantum state, which experiences decoherence due to the measurements; this
guiding principle is termed ’flow.’ This flow can be succinctly represented as
a directed graph, denoted as $G=(V,E)$, where the vertices are associated with
the measurement operators, and the update conditions between operators and
results are represented by the edges of the graph [12]. The steps for
executing a measurement pattern are detailed below,

  1. 1.

Initialize a set of qudits, the number of which matches the count of vertices
$|V|$ in the graph, all set to the state $F_{p}\ket{0}$;

  2. 2.

Apply the entangling gates $E_{v_{i},v_{j}}$ between the necessary qudits to
produce the resource state.

  3. 3.

For each temporal layer $t_{i}$ in the flow, sequentially:

    1. (a)

Implement the Pauli corrections for each vertex in $t_{i}$, based on prior
measurement outcomes $M_{j<i}$ as dictated by the edges of graph $G$.

    2. (b)

Conduct the qudit measurement $M_{t_{i}}^{b}(\theta)$ within the same temporal
layer $t_{i}$ of the flow graph, for every time step $i$.

This model has been both the focus and inspiration for various works in
studying the complexity of constant-depth quantum circuits [19, 11, 40].
However, a detailed analysis exploring the computational differences within
the model, especially concerning the utilization of higher-dimensional
resource states and measurement operators, remained to be delved into [5].

###  A.3 Quantum circuit classes with infinite gatesets

######  Definition 47 ($\mathbf{\mathsf{i}\text{-}QNC_{d}^{0}}$).

For a given positive integer $d$, let $\mathcal{U}_{d}$ represent the set of
all unitary operators on a $d$-dimensional Hilbert space $\mathcal{H}^{d}$,
and let $\mathcal{C}_{d}$ denote the set of single qudit controlled gates from
$\mathcal{U}_{d}$. We define $\mathsf{i}\text{-}\mathsf{QNC}_{d}^{0}$ as the
class of quantum circuits with constant depth and polynomial size, using a
gate set drawn from the combination of $\mathcal{U}_{d}$ and
$\mathcal{C}_{d}$.

######  Definition 48 ($\mathbf{\mathsf{i}\text{-}QAC_{d}^{0}}$).

For a given positive integer $d$, let $\mathcal{U}_{d}$ represent all unitary
operators on a $d$-dimensional Hilbert space $\mathcal{H}^{d}$, and let
$\mathcal{T}_{d}^{k}$ denote a multi-qudit controlled gate selected from
$\mathcal{U}_{d}$. We define $\mathsf{i}\text{-}\mathsf{QAC}_{d}^{0}$ as the
class of quantum circuits with a constant depth and polynomial size, using a
gate set drawn from the combination of $\mathcal{U}_{d}$ and
$\mathcal{T}_{d}^{k}$ with unbounded classical fanout.