text:
# Quantum Fan-out is Powerful

## 1 Introduction

In this paper, we study the power of shallow quantum circuits. Long quantum computations encounter various problems with decoherence, hence we want to speed them up as much as possible. We can exploit the following two types of parallelism:

1. Gates on different qubits can be applied at the same time.
2. Commuting gates can be applied to the same qubits at the same time.

The first approach is just the classical parallel computation. The second approach only makes sense when the gates applied on the same qubits commute, i.e. $`AB=BA`$, otherwise the outcome would be ambiguous. Being able to do this is a strong assumption, however there are models of quantum computers, in which it is physically feasible: ion-trap computers \[CZ95\] and bulk-spin resonance (NMR) \[GC97\]. The basic idea is that if two quantum gates commute, so do their Hamiltonians and therefore we can apply their joint operation by performing both evolutions at the same time. This type of research started after the Mølmer–Sørensen paper \[MS99\]. Recently, a Hamiltonian implementing the fan-out gate (which is crucial for all our simulations) has been proposed by Fenner \[Fen03\].

In our paper, we investigate how much the power of quantum computation would increase if we allow such commuting gates. The computation in the stronger model must be efficient, therefore we do not require the ability to perform any set of commuting gates. This is in accordance with standard quantum computation, where we also allow only some gates. We choose a representative, the so-called unbounded fan-out gate, which is a sequence of controlled-not gates sharing one control qubit. We call it fan-out, because if all target qubits are zero, then the gate copies the classical source bit into $`n`$ copies. We show that fan-out is in some sense universal for all sets of commuting gates. In particular, the joint operation of any set of commuting gates (that can be easily diagonalised) can be simulated by a constant-depth quantum circuit using just one-qubit and fan-out gates. To achieve this, we generalise the parallelisation method of \[MN02, GHMP02\] and adapt it to the constant-depth setting.

We state our results in terms of circuit complexity classes. Classically, the main classes computed by constant-depth, polynomial-size circuits are:

> $`\mathrm{NC}^0`$ with Not and bounded fan-in gates: And, Or,
> $`\mathrm{AC}^0`$ with Not and unbounded fan-in gates: And, Or,
> $`\mathrm{TC}^0`$ with Not and unbounded fan-in gates: And, Or, threshold\[t\] for all $`t`$,
> $`\mathrm{AC}^0[q]`$ with Not and unbounded fan-in gates: And, Or, mod\[q\],
> $`\mathrm{ACC}^0=_q\mathrm{AC}^0[q]`$.

The zero in the exponent means constant depth, in general $`\mathrm{NC}^k`$ means $`(\mathrm{log}^kn)`$-depth circuits. Several separations between these classes are known. Razborov \[Raz87\] proved that $`\mathrm{TC}^0`$ is strictly more powerful than $`\mathrm{ACC}^0`$. Using algebraic methods, Smolensky \[Smo87\] proved that $`\mathrm{AC}^0[q]\mathrm{AC}^0[q^{}]`$, where $`q,q^{}`$ are powers of distinct primes. In other words, threshold gates cannot be simulated by constant-depth circuits with unbounded fan-in Or gates, and mod\[q\] gates do not simulate each other.

The main quantum circuit classes corresponding to the classical classes are $`\mathrm{QNC}^0`$, $`\mathrm{QAC}^0`$, $`\mathrm{QTC}^0`$, and $`\mathrm{QACC}^0`$. We use subscript ‘f’ to indicate circuits where we allow the fan-out gate (e.g. $`\mathrm{QNC}_\mathrm{f}^0`$). Classically, fan-out (copying the result of one gate into inputs of other gates) is taken for granted. Surprisingly, in contrast to the classical case, some of the quantum circuit classes are the same. Moore \[Moo99\] proved that parity is equivalent to fan-out, i.e. $`\mathrm{QAC}_\mathrm{f}^0=\mathrm{QAC}^0[2]`$. Green et al. \[GHMP02\] proved that allowing mod\[q\] gates with different moduli always leads to the same quantum classes, i.e. $`\mathrm{QACC}^0=\mathrm{QAC}^0[q]`$ for every integer $`q2`$.

In this paper, we extend these results and show that even exact\[t\] gates (which output 1 if the input is of Hamming weight $`t`$, and 0 otherwise) can be approximated with polynomially small error by fan-out and single qubit gates in constant depth. Our simulations have polynomially small error. Since exact\[t\] gates can simulate And, Or, threshold\[t\], and mod\[q\] gates, we conclude that the bounded-error versions of the following classes are equal: $`\text{B-}\mathrm{QNC}_\mathrm{f}^0=\text{B-}\mathrm{QAC}_\mathrm{f}^0=\text{B-}\mathrm{QTC}_\mathrm{f}^0`$. The exact\[t\] gate can be approximated in constant depth thanks to the parallelisation method. However, the simulation is not so straightforward as for mod\[q\] in \[GHMP02\] and it works only with high probability.

We then introduce a so-called Or-reduction that converts $`n`$ input bits $`x`$ into $`\mathrm{log}n`$ output bits $`y`$ and preserves the Or function, i.e. $`x`$ is nonzero if and only $`y`$ is. We show how to implement it exactly in constant depth and use it to achieve exact computation of Or and exact\[t\] in log-star depth. (Circuits of log-star depth are defined in Section 5.) We also apply the Or-reduction to decrease the size of most of our circuits.

Our results concerning the threshold\[t\] gate have several interesting implications. Siu et al. \[SBKH93\] proved that sorting and integer arithmetic (addition and multiplication of $`n`$ integers, and division with remainder) are computable by constant-depth threshold circuits. It follows that all of them can be approximated in $`\text{B-}\mathrm{QNC}_\mathrm{f}^0`$.

The last contribution of our paper concerns the quantum Fourier Transform (QFT). Cleve and Watrous \[CW00\] published an elegant log-depth quantum circuit that approximates the QFT. By optimising their methods to use the fan-out gate, we can approximate the QFT in constant depth with polynomially small error. First, we develop a circuit for the QFT with respect to a power-of-2 modulus, and then, using a technique of \[HH99\], we show that the QFT with respect to arbitrary moduli can be approximated too. Hence the QFT is in $`\text{B-}\mathrm{QNC}_\mathrm{f}^0`$. The QFT has many applications, one of which is the phase estimation of an unknown quantum state.

Shor’s original algorithm for factoring \[Sho94\] uses the QFT and the modular exponentiation. Cleve and Watrous \[CW00\] have shown that it can be adapted to use modular multiplication of $`n`$ integers. Since we prove that both the QFT and arithmetic operations are in $`\text{B-}\mathrm{QNC}_\mathrm{f}^0`$, polynomial-time bounded-error algorithms with oracle $`\text{B-}\mathrm{QNC}_\mathrm{f}^0`$ can factorise numbers and compute discrete logarithms. We can make the following conclusions: First, if $`\text{B-}\mathrm{QNC}_\mathrm{f}^0`$ can be simulated by a $`\mathrm{BPP}`$ machine, then factoring can be done in polynomial time by bounded-error Turing machines. Second, since it unlikely that $`\mathrm{BQP}=\text{B-}\mathrm{QNC}_\mathrm{f}^0`$, factoring and discrete logarithms are likely not the hardest things quantum computers can do.

## 2 Quantum circuits with unbounded fan-out

Quantum circuits resemble classical reversible circuits. A quantum circuit is a sequence of quantum gates ordered into layers. The gates are consecutively applied in accordance with the order of the layers. Gates in one layer can be applied in parallel. The size of a gate is the number of affected qubits. The depth of a circuit is the number of layers and the size is the total size of all its gates. A circuit can solve problems of a fixed input size, so we define families of circuits containing one circuit for every input size. We consider only uniform families, whose description can be generated by a log-space Turing machine.

A quantum gate is a unitary operator applied to some subset of qubits. We usually use gates from a fixed universal basis (Hadamard gate, rotation by an irrational multiple of $`\pi `$, and the controlled-not gate) that can approximate any quantum gate with good precision \[ADH97\]. The qubits are divided into 2 groups: Input/output qubits contain the description of the input at the beginning and they are measured in the computational basis at the end. Ancilla qubits are initialised to $`|0`$ at the beginning and the circuits usually clean them at the end, so that the output qubits are in a pure state and the ancillas may be reused.

Since unitary evolution is reversible, every operation can be undone. Running the computation backward is called uncomputation and is often used for cleaning ancilla qubits.

### 2.1 Definition of quantum gates

Quantum circuits cannot use a naive quantum fan-out gate mapping every quantum superposition $`|\varphi |0\mathrm{}|0`$ to $`|\varphi \mathrm{}|\varphi `$ due to the no-cloning theorem \[WZ82\]. Such a gate is not linear, let alone unitary. Instead, our fan-out gate copies only classical bits and the effect on superpositions is determined by linearity. It acts as a controlled-not-…-not gate, i.e. it is an unbounded sequence of controlled-not gates sharing one control qubit. Parity is a natural counterpart of fan-out. It is an unbounded sequence of controlled-not gates sharing one target qubit.

###### Definition 1

The fan-out gate maps $`|y_1\mathrm{}|y_n|x|y_1x\mathrm{}|y_nx|x,`$ where $`xy=(x+y)mod2`$. The parity gate maps $`|x_1\mathrm{}|x_n|y|x_1\mathrm{}|x_n|y(x_1\mathrm{}x_n).`$

Example. As used in \[Moo99\], parity and fan-out can simulate each other in constant depth. The Hadamard gate is $`H=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}\hfill 1& \hfill 1\\ \hfill 1& \hfill 1\end{array}\right)`$ and it holds that $`H^2=I`$. If a controlled-not gate is preceded and succeeded by Hadamard gates on both qubits, it just turns around. Since parity is a sequence of controlled-not gates, we can turn around all of them in parallel. The circuit is shown in Figure 1.

In this paper, we investigate the circuit complexity of, among others, these gates:

###### Definition 2

Let $`x=x_1\mathrm{}x_n`$ and let $`|x|`$ denote the Hamming weight of $`x`$. The following $`(n+1)`$-qubit gates map $`|x|y|x|yg(x)`$, where $`g(x)=1`$ iff

| $`|x|>0`$: | Or, | $`|x|=n`$: | And (Toffoli), | $`|x|\frac{n}{2}`$: | majority, |
| --- | --- | --- | --- | --- | --- |
| $`|x|modq=0`$: | mod\[q\], | $`|x|t`$: | threshold\[t\], | $`|x|=t`$: | exact\[t\], |

A counting gate is any gate that maps $`|x|0^m|x||x|`$ for $`m=\mathrm{log}(n+1)`$.

### 2.2 Quantum circuit classes

###### Definition 3

$`\mathrm{QNC}_\mathrm{f}(d(n))`$ contains operators computed exactly (i.e. without error) by uniform families of quantum circuits with fan-out of depth $`\mathrm{O}\left(d(n)\right)`$, polynomial size, and over a fixed basis. $`\mathrm{QNC}_\mathrm{f}^k=\mathrm{QNC}_\mathrm{f}(\mathrm{log}^kn)`$. $`\text{R-}\mathrm{QNC}_\mathrm{f}^k`$ contains operators approximated with one-sided, and $`\text{B-}\mathrm{QNC}_\mathrm{f}^k`$ with two-sided, polynomially small error.

Remark. The circuits below are over a fixed universal basis, unless explicitly mentioned otherwise. Some of our circuits need arbitrary one-qubit gates to be exact. For simplicity, we sometimes include several fixed-size gates (e.g. the binary Or gate and controlled one-qubit gates) in our set of basis gates. This inclusion does not influence the asymptotic depth of our circuits, since every $`s`$-qubit quantum gate can be decomposed into a sequence of one-qubit and controlled-not gates of length $`\mathrm{O}\left(s^34^s\right)`$ \[BBC+95\].

For every one-qubit gate $`U`$, there exist one-qubit gates $`A,B,C`$ and a rotation $`P=R_\mathrm{z}\left(\alpha \right)`$ such that the controlled gate $`U`$ is computed by the constant-depth circuit shown in Figure 2 \[BBC+95, Lemma 5.1\]. If a qubit controls more one-qubit gates, then we can still use this method in constant depth. We just replace the controlled-not gate by the fan-out gate and the rotations $`P`$ are multiplied.

## 3 Parallelisation method

In this section, we describe a general parallelisation method for achieving very shallow circuits. We then apply it to the rotation by Hamming weight and the rotation by value, and show how to compute them in constant depth.

### 3.1 General method

The unbounded fan-out gate is universal for commuting gates in the following sense: Using fan-out, gates can be applied to the same qubits at the same time whenever (1) they commute, (2) we know the basis in which they all are diagonal, and (3) we can efficiently change into the basis. The method reduces the depth, but may in general require the use of ancilla qubits.

###### Lemma 1

\[HJ85, Theorem 1.3.19\] For every set of pairwise commuting unitary gates, there exists an orthogonal basis in which all the gates are diagonal.

###### Theorem 2

\[MN02, GHMP02\] Let $`\{U_i\}_{i=1}^n`$ be pairwise commuting gates on $`k`$ qubits. Gate $`U_i`$ is controlled by qubit $`|x_i`$. Let $`T`$ be a gate changing the basis according to Lemma 1. There exists a quantum circuit with fan-out computing $`U=_{i=1}^nU_i^{x_i}`$ having depth $`\mathrm{max}_{i=1}^n\mathrm{depth}(U_i)+4\mathrm{depth}(T)+2`$, size $`_{i=1}^n\mathrm{size}(U_i)+(2n+2)\mathrm{size}(T)+2n`$, and using $`(n1)k`$ ancillas.

Proof. Consider a circuit that applies all $`U_i`$ sequentially. Put $`TT^{}=I`$ between $`U_i`$ and $`U_{i+1}`$. The circuit is shown in Figure 3. Take $`V_i=T^{}U_iT`$ as new gates. They are diagonal in the computational basis, hence they just impose some phase shifts. Multiple phase shifts on entangled states multiply, so can be applied in parallel. We use fan-out gates twice: first to create $`n`$ entangled copies of target qubits and then to destroy the entanglement. The final circuit with the desired parameters is shown in Figure 4.  $`\mathrm{}`$

Example. As used in \[Moo99\], it is simple to prove that mod\[q\] $`\mathrm{QNC}_\mathrm{f}^0`$. Each input qubit controls one increment modulo $`q`$ on a counter initialised to $`0`$. At the end, we obtain $`|x|modq`$. The modular increments commute and thus can be parallelised. Since $`q`$ is fixed, changing the basis and the increment can both be done in constant depth.

### 3.2 Rotation by Hamming weight and value

In this paper, we often use a rotation by Hamming weight $`R_\mathrm{z}\left(\phi |x|\right)`$ and a rotation by value $`R_\mathrm{z}\left(\phi x\right)`$, where $`R_\mathrm{z}\left(\alpha \right)`$ is one-qubit rotation around the $`z`$-axis by angle $`\alpha `$: $`R_\mathrm{z}\left(\alpha \right)=|00|+e^{i\alpha }|11|`$. They can both be computed in constant depth.

###### Lemma 3

For every angle $`\phi `$, there exist constant-depth, linear-size quantum circuits with fan-out computing $`R_\mathrm{z}\left(\phi |x|\right)`$ and $`R_\mathrm{z}\left(\phi x\right)`$ on input $`x=x_{n1}\mathrm{}x_1x_0`$.

Proof. The left circuit in Figure 5 shows how to compute the rotation by Hamming weight. Each input qubit controls $`R_\mathrm{z}\left(\phi \right)`$ on the target qubit, hence the total angle is $`\phi |x|`$. These controlled rotations are parallelised using the parallelisation method.

The right circuit shows the rotation by value. It is similar to the rotation by Hamming weight, only the input qubit $`|x_j`$ controls $`R_\mathrm{z}\left(\phi 2^j\right)`$, hence the total angle is $`\phi _{j=0}^{n1}2^jx_j=\phi x`$.  $`\mathrm{}`$

Remark. The construction uses rotations $`R_\mathrm{z}\left(\phi \right)`$ for arbitrary $`\phi `$. However, we are only allowed to use a fixed set of one-qubit gates. It is easy to see that every rotation can be approximated with polynomially small error by $`R_\mathrm{z}\left(\theta q\right)=\left(R_\mathrm{z}\left(\theta \right)\right)^q`$, where $`\mathrm{sin}\theta =\frac{3}{5}`$ and $`q`$ is a polynomially large integer \[ADH97\]. These $`q`$ rotations commute, so can be applied in parallel and the depth is preserved. The approximation can be kept down to polynomially small error while increasing the size of the circuit only polynomially.

## 4 Constant-depth approximate circuits

### 4.1 Or gate

It is easy to see that the rotation by Hamming weight of a string $`y`$ of length $`m`$ with angle $`\phi =\frac{2\pi }{m}`$ can be used to distinguish the zero string $`y=0^m`$ from strings with approximately $`\frac{m}{2}`$ ones. We, however, want to distinguish the zero string from all nonzero strings. It turns out that if we compute $`m=\mathrm{O}\left(n\mathrm{log}n\right)`$ rotations by Hamming weight of the input $`x`$ with angles distributed evenly around the circle, we obtain a string $`y`$ that is either zero (for $`x=0^n`$), or has expected Hamming weight $`\frac{m}{2}`$ (for $`x0^n`$). By combining these two results, we can approximate the Or gate and, with a minor modification, also the exact\[t\] gate in constant depth.

Let $`w_0`$ and let $`\phi `$ be an angle. Define a notation for the following one-qubit state:

$$|\mu _\phi ^w=(HR_\mathrm{z}\left(\phi w\right)H)|0=\frac{1+e^{i\phi w}}{2}|0+\frac{1e^{i\phi w}}{2}|1.$$
(1)
By Lemma 3, $`|\mu _\phi ^{|x|}`$ can be computed in constant depth and linear size.

###### Theorem 4

Or $`\text{R-}\mathrm{QNC}_\mathrm{f}^0`$. In particular, Or can be approximated with one-sided error $`\frac{1}{n}`$ in constant depth and size $`\mathrm{O}\left(n^2\mathrm{log}n\right)`$.

Proof. Let $`n`$ denote the size of the input $`x`$. Let $`m=an`$, where $`a`$ will be chosen later. For all $`k\{0,1,\mathrm{},m1\}`$, compute in parallel $`|y_k=|\mu _{\phi _k}^{|x|}`$ for angle $`\phi _k=\frac{2\pi }{m}k`$. If $`|y_k`$ is measured in the computational basis, the expected value of the outcome $`Y_k\{0,1\}`$ is

$$E[Y_k]=\left|\frac{1e^{i\phi _k|x|}}{2}\right|^2=\left|e^{i\phi _k|x|}\right|\frac{\left|e^{i\phi _k|x|}+e^{i\phi _k|x|}2\right|}{4}=\frac{1\mathrm{cos}(\phi _k|x|)}{2}.$$

If all these $`m`$ qubits $`|y`$ are measured, the expected Hamming weight of all $`Y`$’s is

$$E[|Y|]=E\left[\underset{k=0}{\overset{m1}{}}Y_k\right]=\frac{m}{2}\frac{1}{2}\underset{k=0}{\overset{m1}{}}\mathrm{cos}(\frac{2\pi k}{m}|x|)=\{\begin{array}{cc}\text{0}\hfill & \text{if }|x|=0\text{,}\hfill \\ \frac{m}{2}\hfill & \text{if }|x|0\text{.}\hfill \end{array}$$

The qubits $`|y`$ are actually not measured, but their Hamming weight $`|y|`$ controls another rotation on a new ancilla qubit $`|z`$. So compute $`|z=|\mu _{\mathrm{\hspace{0.17em}2}\pi /m}^{|y|}`$. Let $`Z`$ be the outcome after $`|z`$ is measured. If $`|y|=0`$, then $`Z=0`$ with certainty. If $`\left||y|\frac{m}{2}\right|\frac{m}{\sqrt{n}}`$, then

$$P[Z=0]=\left|\frac{1+e^{i\frac{2\pi }{m}|y|}}{2}\right|^2=\frac{1+\mathrm{cos}\left(\frac{2\pi }{m}|y|\right)}{2}\frac{1\mathrm{cos}\frac{2\pi }{\sqrt{n}}}{2}=\mathrm{O}\left(\frac{1}{n}\right).$$

Assume that $`|x|0`$. We want to upper-bound the probability of the bad event that $`|Y|`$ is not close to $`\frac{m}{2}`$. Since $`0Y_k1`$, we can use Hoeffding’s Lemma 5 below and obtain $`P\left[\left||Y|\frac{m}{2}\right|\epsilon m\right]\frac{1}{2^{\epsilon ^2m}}.`$ Fix $`a=\mathrm{log}n`$ and $`\epsilon =\frac{1}{\sqrt{n}}`$. Now, $`P\left[\left||y|\frac{m}{2}\right|\frac{m}{\sqrt{n}}\right]\frac{1}{2^{m/n}}=\frac{1}{2^a}=\frac{1}{n}.`$ The probability that we observe the incorrect result $`Z=0`$ is at most the sum of the probabilities of the two bad events, i.e. $`\mathrm{O}\left(\frac{1}{n}\right)`$. Hence

$$P[Z=0]=\{\begin{array}{cc}1\hfill & \text{if }|x|=0\text{,}\hfill \\ \mathrm{O}\left(\frac{1}{n}\right)\hfill & \text{if }|x|0\text{.}\hfill \end{array}$$

The circuit has constant depth and size $`\mathrm{O}\left(mn\right)=\mathrm{O}\left(n^2\mathrm{log}n\right)`$. It is outlined in Figure 6. The figure is slightly simplified: unimportant qubits and uncomputation of ancillas are omitted.  $`\mathrm{}`$

###### Lemma 5 (Hoeffding \[Hoe63\])

If $`Y_1,\mathrm{},Y_m`$ are independent random variables bounded by $`a_kY_kb_k`$, then, for all $`\epsilon >0`$,

$$P\left[\left|SE[S]\right|\epsilon m\right]2\mathrm{exp}\frac{2m^2\epsilon ^2}{_{k=1}^m(b_ka_k)^2},\text{where }S=_{i=k}^mY_k\text{.}$$

Remark. Since the outcome $`z`$ of the circuit in Figure 6 is a classical bit, we can save it in an ancilla qubit by applying a controlled-not gate and clean $`|y`$ by uncomputation. It remains to prove that the intermediate qubits $`|y`$ need not be measured, in order to be able to uncompute them. We show above that the output qubit is a good approximation of the logical Or, provided $`|y`$ is immediately measured. By the principle of deferred measurement, we can use controlled quantum operations and measure $`|y`$ at the end. However, the output bit is close to a classical bit (the distance depends on the error of the computation), thus it is only slightly entangled with $`|y`$, and hence it does not matter whether $`|y`$ is measured.

###### Definition 4

Let $`\mathrm{log}^{(k)}x`$ denote the $`k`$-times *iterated logarithm* $`\mathrm{log}\mathrm{log}\mathrm{}\mathrm{log}x`$. The *log-star function*, $`\mathrm{log}^{}x`$, is the maximum number of iterations $`k`$ such that $`\mathrm{log}^{(k)}x`$ exists and is real.111The log-star of the estimated number of atoms in the universe is 5. Consequently, for the computational problems we consider in this paper, the log-star is in practice at most 5.

Remark. If we require error $`\frac{1}{n^c}`$, we create $`c`$ copies and compute the exact Or of them by a binary tree of Or gates. The tree has depth $`\mathrm{log}c=\mathrm{O}\left(1\right)`$. In Section 6.1, we show how to approximate Or in constant depth and size $`\mathrm{O}(n\mathrm{log}^{(k)}n)`$ for any constant $`k`$. In Section 6.2, we show how to compute Or exactly in log-star depth and linear size.

### 4.2 Exact\[t\] and threshold\[t\] gates

###### Theorem 6

exact\[t\] $`\text{R-}\mathrm{QNC}_\mathrm{f}^0`$.

Proof. We slightly modify the circuit for Or. As outlined in Figure 7, by adding the rotation $`R_\mathrm{z}\left(\phi t\right)`$ to the rotation by Hamming weight in the first layer, we obtain $`|\mu _\phi ^{|x|t}`$ instead of $`|\mu _\phi ^{|x|}`$. The second layer stays the same. If the output qubit $`|z`$ is measured, then

$$P[Z=0]=\{\begin{array}{cc}1\hfill & \text{if }|x|=t\text{,}\hfill \\ \mathrm{O}\left(\frac{1}{n}\right)\hfill & \text{if }|x|t\text{.}\hfill \end{array}$$

We obtain an approximation of the exact\[t\] gate with one-sided polynomially small error.  $`\mathrm{}`$

Remark. Other gates are computed from the exact\[t\] gate by standard methods. For example, threshold\[t\] can be computed as the parity of exact\[$`t`$\], exact\[$`t+1`$\], …, exact\[$`n`$\]. The depth stays constant and the size is just $`n`$-times bigger, i.e. $`\mathrm{O}\left(n^3\mathrm{log}n\right)`$, hence threshold\[t\] $`\text{B-}\mathrm{QNC}_\mathrm{f}^0`$. In Section 6.3, we show how to approximate exact\[t\], threshold\[t\], and counting in constant depth and size $`\mathrm{O}\left(n\mathrm{log}n\right)`$.

### 4.3 Arithmetic operations

Using threshold gates, one can do arithmetic operations in constant depth. The following circuits take as part of the input an ancilla register in state $`|0`$ and output the result of the computation in that register.

###### Theorem 7

The following functions are in $`\text{B-}\mathrm{QNC}_\mathrm{f}^0`$: addition and multiplication of $`n`$ integers, division of integers with remainder, and sorting of $`n`$ integers.

Proof. By \[SBKH93\], these functions are computed by constant-depth,222The depths are really small, from 2 to 5. polynomial-size threshold circuits. A threshold circuit is built of weighted threshold gates. It is simple to prove that the weighted threshold gate (with polynomially large integer weights) also is in $`\text{B-}\mathrm{QNC}_\mathrm{f}^0`$. One only needs to rotate the phase of the quantum state in Lemma 3 by integer multiples of the basic angle.  $`\mathrm{}`$

In the following section, we require a reversible version of modular addition.

###### Definition 5

Let $`q`$ be an $`n`$-bit integer and $`x_1,\mathrm{},x_m_q`$. The *reversible addition* gate maps $`add^m:|q|x_1\mathrm{}|x_m|q|x_1\mathrm{}|x_{m1}|y`$, where $`y=\left(_{i=1}^mx_i\right)modq`$.

###### Lemma 8

$`add^m\text{B-}\mathrm{QNC}_\mathrm{f}^0`$.

Proof. By Theorem 7, $`y=(_{i=1}^mx_i)modq`$ can be approximated in constant depth and polynomial size. The result is, however, stored into ancilla qubits. Hence we have to erase $`x_m`$, which we may achieve by first negating the contents in $`y`$ by $`|y|y`$, computing the sum $`w=y+_{i=1}^{m1}x_i`$ in a fresh ancilla, do a bitwise control-not of $`w`$ into $`x_m`$, uncompute $`w`$, and finally re-negate $`y`$. We then swap the ancillas $`|y`$ with the erased qubits in $`|x_m`$.  $`\mathrm{}`$

### 4.4 Quantum Fourier transform

The QFT is a very powerful tool used in several quantum algorithms, e.g. factoring of integers and computing the discrete logarithm \[Sho94\].

###### Definition 6

The quantum Fourier transform with respect to modulus $`q`$ performs the Fourier transform on the quantum amplitudes of the state, i.e. it maps

$$F_q:|x|\psi _x=\frac{1}{\sqrt{q}}\underset{y=0}{\overset{q1}{}}\omega ^{xy}|y\text{, where }\omega =e^{2\pi i/q}\text{,}$$
(2)
for $`x\{0,1,\mathrm{},q1\}`$ and it behaves arbitrarily on the other states.

#### 4.4.1 QFT with a power-of-2 modulus

Let $`q=2^n`$. Coppersmith has shown in \[Cop94\] how to compute the QFT in quadratic depth, quadratic size, and without ancillas. The depth has further been improved to linear \[folklore\]. Cleve and Watrous have shown in \[CW00\] that the QFT can be approximated with error $`\epsilon `$ in depth $`\mathrm{O}\left(\mathrm{log}n+\mathrm{log}\mathrm{log}\frac{1}{\epsilon }\right)`$ and size $`\mathrm{O}\left(n\mathrm{log}\frac{n}{\epsilon }\right)`$. They also show that if only gates acting on a constant number of qubits are allowed (in particular, the fan-out gate is not allowed), logarithmic depth is necessary. We show that the approximate circuit for the QFT from \[CW00\] can be compressed to constant depth, if we allow the fan-out gate.

###### Theorem 9

QFT $`\text{B-}\mathrm{QNC}_\mathrm{f}^0`$.

Proof. The operator $`F_{2^n}:|x|\psi _x`$ can be computed by composing:

| 1. | Fourier state construction (QFS): | $`|x|0\mathrm{}|0`$ | $`|x|\psi _x|0\mathrm{}|0`$ |
| --- | --- | --- | --- |
| 2. | Copying Fourier state (COPY): | $`|x|\psi _x|0\mathrm{}|0`$ | $`|x|\psi _x\mathrm{}|\psi _x`$ |
| 3. | Uncomputing phase estimation (QFP): | $`|\psi _x\mathrm{}|\psi _x|x`$ | $`|\psi _x\mathrm{}|\psi _x|0`$ |
| 4. | Uncomputing COPY: | $`|\psi _x\mathrm{}|\psi _x|0`$ | $`|\psi _x|0\mathrm{}|0`$ |

The following lemmas show that each of these individual operators is in $`\text{B-}\mathrm{QNC}_\mathrm{f}^0`$.  $`\mathrm{}`$

###### Lemma 10

QFS $`\mathrm{QNC}_\mathrm{f}^0`$.

Proof. QFS maps $`|x|0|x|\psi _x`$. Define $`|\rho _r=\frac{|0+e^{2\pi ir}|1}{\sqrt{2}}`$. It is simple to prove that $`|\psi _x=|\rho _{x/2^1}|\rho _{x/2^2}\mathrm{}|\rho _{x/2^n}`$.

$`|\psi _x`$ $`=`$ $`{\displaystyle \frac{1}{\sqrt{2^n}}}{\displaystyle \underset{y=0}{\overset{2^n1}{}}}\omega ^{xy}|y={\displaystyle \frac{1}{\sqrt{2^n}}}{\displaystyle \underset{y=0}{\overset{2^n1}{}}}{\displaystyle \underset{k=1}{\overset{n}{}}}\omega ^{x2^{nk}y_{nk}}|y_{nk}`$
$`=`$ $`{\displaystyle \frac{1}{\sqrt{2^n}}}{\displaystyle \underset{k=1}{\overset{n}{}}}{\displaystyle \underset{b=0}{\overset{1}{}}}(\omega ^{2^{nk}x})^b|b={\displaystyle \underset{k=1}{\overset{n}{}}}{\displaystyle \frac{|0+e^{2\pi ix/2^k}|1}{\sqrt{2}}}={\displaystyle \underset{k=1}{\overset{n}{}}}|\rho _{x/2^k}.`$
The $`n`$ qubits $`|\rho _{x/2^k}`$ can be computed from $`x`$ in parallel as follows: $`|\rho _{x/2^k}=R_\mathrm{z}\left(\frac{2\pi }{2^k}x\right)\frac{|0+|1}{\sqrt{2}}`$ is computed by the rotation by value (Lemma 3) in constant depth and linear size.  $`\mathrm{}`$

###### Lemma 11

COPY $`\text{B-}\mathrm{QNC}_\mathrm{f}^0`$.

Proof. COPY maps $`|\psi _x|0\mathrm{}|0|\psi _x\mathrm{}|\psi _x`$. Take the reversible addition gate modulo $`2^n`$: $`(add_{2^n}^2)|y|x=|y|(x+y)mod2^n`$. It is simple to prove that $`add^1|\psi _y|\psi _x=|\psi _{x+y}|\psi _x`$.

$`|\psi _y|\psi _x`$ $`=`$ $`{\displaystyle \frac{1}{2^n}}{\displaystyle \underset{l,k=0}{\overset{2^n1}{}}}\omega ^{ly+kx}|l|k_{add^1}{\displaystyle \frac{1}{2^n}}{\displaystyle \underset{l,k}{}}\omega ^{ly+kx}|l|kl`$
$`=`$ $`{\displaystyle \frac{1}{2^n}}{\displaystyle \underset{l,m}{}}\omega ^{ly+(m+l)x}|l|m={\displaystyle \frac{1}{2^n}}{\displaystyle \underset{l,m}{}}\omega ^{l(x+y)+mx}|l|m=|\psi _{x+y}|\psi _x.`$
Hence $`add^1|\psi _0|\psi _x=|\psi _x|\psi _x`$. The state $`|\psi _0=H^n|0^n`$ is easy to prepare in constant depth. Furthermore, $`(add_{2^n}^m)^1|\psi _0\mathrm{}|\psi _0|\psi _x=|\psi _x\mathrm{}|\psi _x|\psi _x`$, because the addition of $`m1`$ numbers into one register is equivalent to $`m1`$ consecutive additions of one number. Each such a reversible addition copies $`|\psi _x`$ into 1 register. Note that the $`add_{2^n}^m`$ gate performs all these additions in parallel. By Lemma 8, the reversible addition gate is in $`\text{B-}\mathrm{QNC}_\mathrm{f}^0`$.  $`\mathrm{}`$

###### Lemma 12

QFP $`\text{B-}\mathrm{QNC}_\mathrm{f}^0`$.

Proof. QFP maps $`|\psi _x\mathrm{}|\psi _x|0|\psi _x\mathrm{}|\psi _x|x`$. By Cleve and Watrous \[CW00, Section 3.3\], we can compute $`x`$ with probability at least $`1\epsilon `$ from $`\mathrm{O}\left(\mathrm{log}\frac{n}{\epsilon }\right)`$ copies of $`|\psi _x`$ in depth $`\mathrm{O}\left(\mathrm{log}n+\mathrm{log}\mathrm{log}\frac{1}{\epsilon }\right)`$ and size $`\mathrm{O}\left(n\mathrm{log}\frac{n}{\epsilon }\right)`$. Use $`\epsilon =\frac{1}{\mathrm{poly}(n)}`$. It is simple to convert their circuit into constant depth, provided we have fan-out. The details are sketched below.

The input consists of $`m=\mathrm{O}\left(\mathrm{log}\frac{n}{\epsilon }\right)`$ copies of $`|\psi _x=|\rho _{x/2^1}|\rho _{x/2^2}\mathrm{}|\rho _{x/2^n}`$. Measure each $`|\rho _{x/2^k}`$ $`\frac{m}{2}`$ times in the basis $`\{|\rho _{0.01},|\rho _{0.11}\}`$ and $`\frac{m}{2}`$ times in the Hadamard basis $`\{|\rho _{0.00},|\rho _{0.10}\}`$. The state $`|\rho _{x/2^k}=\frac{1}{\sqrt{2}}(|0+e^{2\pi i(0.x_{k1}\mathrm{}x_1x_0)})`$ lies on the middle circle of the Bloch sphere; it is shown in Figure 8. If $`|\rho _{x/2^k}`$ is in the white region, then the measurement in the first basis tells whether $`x_{k1}=0`$ or $`1`$ with probability at least $`\frac{3}{4}`$. If $`|\rho _{x/2^k}`$ is in the shaded region, then the measurement in the Hadamard basis tells whether $`x_{k1}=x_{k2}`$ or $`\neg x_{k2}`$ (denoted by P, N) with probability at least $`\frac{3}{4}`$.

For each $`k`$, perform the majority vote and obtain the correct answer $`z_k\{0,1,\mathrm{P},\mathrm{N}\}`$ with error probability at most $`\frac{1}{2^m}=\frac{\epsilon }{n}`$. The probability of having any error is at most $`n`$ times bigger, i.e. at most $`\epsilon `$. Compute $`x_{n1}\mathrm{}x_1x_0`$ from $`z_{n1}\mathrm{}z_1z_0`$ in constant depth. The bit $`x_k`$ is computed as follows:

1. If $`z_kz_{k1}\mathrm{}z_{l+1}\{\mathrm{P},\mathrm{N}\}`$ and $`z_l\{0,1\}`$, compute the parity of the number of N’s and add it to $`z_l`$ (assuming $`z_1=0`$), otherwise return 0.
2. Check and compute all prefixes $`l`$ in parallel and take the logical Or of the results.

All the gates used (fan-out, parity, And, Or, majority) are in $`\text{B-}\mathrm{QNC}_\mathrm{f}^0`$.  $`\mathrm{}`$

#### 4.4.2 QFT with an arbitrary modulus

Let $`q2^n`$. Cleve and Watrous have shown in \[CW00\] that the QFT can be approximated with error $`\epsilon `$ in depth $`\mathrm{O}\left((\mathrm{log}\mathrm{log}q)(\mathrm{log}\mathrm{log}\frac{1}{\epsilon })\right)`$ and size $`\mathrm{poly}(\mathrm{log}q+\mathrm{log}\frac{1}{\epsilon })`$. We show that their circuit can also be compressed into constant depth, if we use the fan-out gate. The relation between quantum Fourier transforms with different moduli was described in \[HH99\].

Remark. We actually implement a slightly more general operation, when $`q`$ is not a fixed constant, but an $`n`$-bit input number. This generalised QFT maps $`|q|x|q|\psi _x`$. The register $`|q`$ is implicitly included in all operations. We will henceforth omit it and the generalised operations are denoted simply by QFTq, QFSq, COPY$`{}_{q}{}^{}{}_{}{}^{m}`$, and QFPq.

###### Theorem 13

QFTq $`\text{B-}\mathrm{QNC}_\mathrm{f}^0`$.

Proof. Let $`|\mathrm{dummy}_{q,x}`$ denote an unspecified quantum state depending on two parameters $`q,x`$. The operator $`F_q^{}:|x|\psi _x|\mathrm{dummy}_{q,0}`$ can be computed by composing:

| 1. | QFSq: | $`|x`$ | $`|x|\psi _x|\mathrm{dummy}_{q,x}`$ |
| --- | --- | --- | --- |
| 2. | COPY$`{}_{q}{}^{}{}_{}{}^{m+1}`$: |  | $`|x|\psi _x|\mathrm{dummy}_{q,x}\left(|\psi _x|\mathrm{dummy}_{q,0}\right)^m`$ |
| 3. | Uncomputing QFSq: |  | $`|x\left(|\psi _x|\mathrm{dummy}_{q,0}\right)^m`$ |
| 4. | Uncomputing QFPq: |  | $`\left(|\psi _x|\mathrm{dummy}_{q,0}\right)^m`$ |
| 5. | Uncomputing COPY$`{}_{q}{}^{}{}_{}{}^{m}`$: |  | $`|\psi _x|\mathrm{dummy}_{q,0}`$, |

where empty registers are omitted for clarity. The state $`|\mathrm{dummy}_{q,0}`$ is not entangled with $`|x`$ and hence it can be traced out. We obtain the quantum Fourier transform $`F_q`$. The following lemmas show that each of these individual operators is in $`\text{B-}\mathrm{QNC}_\mathrm{f}^0`$.  $`\mathrm{}`$

###### Lemma 14

QFS$`{}_{q}{}^{}\text{B-}\mathrm{QNC}_\mathrm{f}^0`$.

Proof. QFSq maps $`|x|0|x|\psi _x|\mathrm{dummy}_{q,x}`$ for some “garbage” state $`|\mathrm{dummy}_{q,x}`$. We will show that QFSq is well approximated by a QFS with a power-of-2 modulus of the magnitude $`q^3`$. Let $`n=\mathrm{log}q`$. Take $`N=3n`$ and extend $`x`$ by leading zeroes into $`N`$ bits. Using Lemma 10, perform QFS$`_{2^N}`$ and obtain the state $`|x\frac{1}{\sqrt{2^N}}_{y=0}^{2^N1}e^{\frac{2\pi i}{2^N}xy}|y.`$

Set $`u=2^N/q`$ and apply integer division by $`u`$ to the second register, i.e. map $`|y|y_1|y_2`$, where $`y_1=y/u\{0,1,\mathrm{},q\}`$ and $`y_2=ymodu`$. This can be done reversibly in constant depth by a few applications of Theorem 7 using the method from Lemma 8. The quantum state can be written as

$$\frac{1}{\sqrt{2^N}}\underset{y=0}{\overset{2^N1}{}}e^{\frac{2\pi i}{2^N}xy}|y_1|y_2=\frac{1}{\sqrt{2^N}}\underset{y_1=0}{\overset{q1}{}}\underset{y_2=0}{\overset{u1}{}}e^{\frac{2\pi i}{2^N}x(y_1u+y_2)}|y_1|y_2+|w,$$

where $`|w=\frac{1}{\sqrt{2^N}}_{z=0}^{v1}e^{\frac{2\pi i}{2^N}x(qu+z)}|q|z`$ and $`v=2^Nmodu=2^Nqu=2^Nmodq<q`$. The sum has been rearranged using $`y=y_1u+y_2`$. Now, $`|w=\sqrt{\frac{v}{2^N}}=\mathrm{O}\left(2^n\right)`$ is exponentially small and so it can be neglected. Decompose the quantum state into the tensor product

$$\frac{1}{\sqrt{q}}\underset{y_1=0}{\overset{q1}{}}e^{\frac{2\pi i}{q}(\frac{q}{2^N}u)xy_1}|y_1\sqrt{\frac{q}{2^N}}\underset{y_2=0}{\overset{u1}{}}e^{\frac{2\pi i}{2^N}xy_2}|y_2.$$

Now, $`u`$ is exponentially close to $`\frac{2^N}{q}`$, because $`\frac{q}{2^N}u=\frac{2^Nv}{2^N}=1\mathrm{O}\left(2^{2n}\right)`$. Since $`\frac{xy_1}{q}=\mathrm{O}\left(2^n\right)`$, the replacement of $`\frac{qu}{2^N}`$ by 1 in the exponent causes only exponentially small error $`\mathrm{O}\left(2^n\right)`$. Hence the quantum state is exponentially close to

$$\frac{1}{\sqrt{q}}\underset{y=0}{\overset{q1}{}}e^{\frac{2\pi i}{q}xy}|y\frac{1}{\sqrt{u}}\underset{z=0}{\overset{u1}{}}e^{\frac{2\pi i}{2^N}xz}|z=|\psi _x|\mathrm{dummy}_{q,x}.$$

The “garbage” state $`|\mathrm{dummy}_{q,x}`$ arises as a byproduct of the higher precision $`3n`$-bit arithmetic. We clean it up later by uncomputing QFSq after copying $`|\psi _x`$; see the proof of Theorem 13. It actually gets replaced by $`|\mathrm{dummy}_{q,0}=\frac{1}{\sqrt{u}}_{z=0}^{u1}|z`$, which does not depend on $`x`$ and it thus causes no harm. We have approximated QFSq in constant depth.  $`\mathrm{}`$

###### Lemma 15

COPY$`{}_{q}{}^{m}\text{B-}\mathrm{QNC}_\mathrm{f}^0`$.

Proof. COPY$`{}_{q}{}^{}{}_{}{}^{m}`$ maps $`|\psi _x|0\mathrm{}|0|\psi _x(|\psi _x|\mathrm{dummy}_{q,0})^{(m1)}`$. The proof is similar to the proof of Lemma 11. First, prepare $`m1`$ states $`|\psi _0|\mathrm{dummy}_{q,0}`$ by applying QFSq to $`|0|0`$ (Lemma 14). Second, use the inverse of the reversible addition modulo $`q`$ to map $`(add_q^m)^1:|\psi _0\mathrm{}|\psi _0|\psi _x|\psi _x\mathrm{}|\psi _x|\psi _x`$ (Lemma 8).  $`\mathrm{}`$

###### Lemma 16

QFP$`{}_{q}{}^{}\text{B-}\mathrm{QNC}_\mathrm{f}^0`$.

Proof. QFPq maps $`|\psi _x\mathrm{}|\psi _x|0|\psi _x\mathrm{}|\psi _x|x`$. We use an idea similar to the proof of Lemma 14. Let $`n=\mathrm{log}q`$ and $`N=3n`$. Extend $`|\psi _x`$ by leading zeroes to $`N`$ bits and apply $`F_{2^N}^{}`$ to them (Theorem 9). We obtain many copies of the state

$$F_{2^N}^{}(|0|\psi _x)=\frac{1}{\sqrt{2^Nq}}\underset{z=0}{\overset{2^N1}{}}\left(\underset{y=0}{\overset{q1}{}}e^{\frac{2\pi i}{2^N}zy+\frac{2\pi i}{q}xy}\right)|z.$$

The exponent can be rewritten to $`2\pi i(\frac{x}{q}\frac{z}{2^N})y`$. Intuitively, if $`|z2^N\frac{x}{q}|\frac{2^N}{8q}`$, then $`|\frac{x}{q}\frac{z}{2^N}|\frac{1}{8q}`$, the absolute value of the angle in the exponent is at most $`\frac{\pi }{4}`$ for every $`y\{0,1,\mathrm{},q1\}`$, and the amplitudes sum up constructively. If $`z`$ is not close to $`2^N\frac{x}{q}`$, then the amplitudes interfere destructively. The quantum state has most of its amplitude on the good $`z`$’s. So we compute reversibly by division with remainder an estimate $`x^{}=\frac{zq}{2^N}+\frac{1}{2}`$. A detailed analyzis shows that $`P[x^{}=x]\frac{1}{2}+\delta `$ for some constant $`\delta `$ \[CW00, HH99\]. Here we do not present the details, because our goal is the compression of the circuit from \[CW00\] into constant depth.

We transform all $`m=\mathrm{O}\left(\mathrm{log}\frac{n}{\epsilon }\right)`$ input quantum states $`|\psi _x`$ into $`m`$ independent estimates $`|x^{}`$. We then estimate all bits of $`x`$ one-by-one from these $`m`$ estimates by majority gates. Each bit of $`x`$ is wrong with probability at most $`2^m=2^{\mathrm{log}\frac{n}{\epsilon }}=\frac{\epsilon }{n}`$. The probability of having an error among the $`n`$ bits of $`x`$ is thus at most $`\epsilon `$. Finally, save the estimation of $`x`$ in the target register and uncompute the divisions and the quantum Fourier transforms. With probability at least $`1\epsilon `$, the mapping QFPq has been performed. Use $`\epsilon =\frac{1}{\mathrm{poly}n}`$.  $`\mathrm{}`$

### 4.5 Quantum phase estimation

The method of computing QFT$`_{2^n}`$ can be also used for phase estimation.

###### Theorem 17

Given a gate $`S_x:|y|\varphi |yR_\mathrm{z}\left(\frac{2\pi x}{2^n}y\right)|\varphi `$ for basis states $`|y`$, where $`x_{2^n}`$ is unknown, we can determine $`x`$ with probability at least $`1\epsilon `$ in constant depth, size $`\mathrm{O}\left(n\mathrm{log}\frac{n}{\epsilon }\right)`$, and using the $`S_x`$ gate $`\mathrm{O}\left(n\mathrm{log}\frac{n}{\epsilon }\right)`$ times.

Proof. Obtain an estimate of $`x`$ by applying the QFP to $`\mathrm{O}\left(\mathrm{log}\frac{n}{\epsilon }\right)`$ copies of the quantum state $`|\psi _x=|\rho _{x/2^1}|\rho _{x/2^2}\mathrm{}|\rho _{x/2^n}`$. Each $`|\rho _{x/2^k}`$ can be computed by one application of $`S_x`$ to $`|2^{nk}\frac{|0+|1}{\sqrt{2}}`$, because $`|\rho _{x/2^k}=R_\mathrm{z}\left(\frac{2\pi x}{2^k}\right)\frac{|0+|1}{\sqrt{2}}=R_\mathrm{z}\left(\frac{2\pi x}{2^n}2^{nk}\right)\frac{|0+|1}{\sqrt{2}}`$.  $`\mathrm{}`$

## 5 Exact circuits of small depth

In the previous section, we have shown how to approximate the exact\[t\] gate in constant depth. In this section, we show how to compute it exactly in log-star depth. The circuits in this section use arbitrary one-qubit gates instead of a fixed basis, otherwise they would not be exact.

###### Lemma 18

The function Or on $`n`$ qubits can be reduced exactly to Or on $`m=\mathrm{log}(n+1)`$ qubits in constant depth and size $`\mathrm{O}\left(n\mathrm{log}n\right)`$.

Proof. We use a technique similar to the proof of Theorem 4. Recall the quantum state $`|\mu _\phi ^w`$ defined by equation (1) on page 1. For $`k\{1,2,\mathrm{},m\}`$, compute in parallel $`|y_k=|\mu _{\phi _k}^{|x|}`$ for angle $`\phi _k=\frac{2\pi }{2^k}`$. Let $`|y=|y_1y_2\mathrm{}y_m`$.

* If $`|x|=0`$, then $`y|0^m=1`$, because $`|y_k=|0`$ for each $`k`$.
* If $`|x|0`$, then $`y|0^m=0`$, because at least one qubit $`y_k`$ is one with certainty. Take the unique decomposition of $`|x|`$ into a product of a power of 2 and an odd number: $`|x|=2^a(2b+1)`$ for $`a,b_0`$. Then

$$1|y_{a+1}=\frac{1e^{i\phi _{a+1}|x|}}{2}=\frac{1e^{i\frac{2\pi }{2^{a+1}}2^a(2b+1)}}{2}=\frac{1e^{i\pi (2b+1)}}{2}=\frac{1e^{i\pi }}{2}=1.$$

It follows that $`x`$ is non-zero if and only if $`y`$ is. Hence the original problem is exactly reduced to a problem of logarithmic size.  $`\mathrm{}`$

###### Theorem 19

exact\[t\] $`\mathrm{QAC}_\mathrm{f}^0`$.

Proof. Using the methods from Theorem 6 and Lemma 18, exact\[t\] can also be reduced to Or of logarithmic size. The reduction has constant depth and size $`\mathrm{O}\left(n\mathrm{log}n\right)`$. Hence exact\[t\] is $`\mathrm{QNC}_\mathrm{f}^0`$-reducible to Or, or simply exact\[t\] $`\mathrm{QAC}_\mathrm{f}^0`$, because $`\mathrm{QAC}_\mathrm{f}^0`$ includes both $`\mathrm{QNC}_\mathrm{f}^0`$ and the Or gate.  $`\mathrm{}`$

###### Theorem 20

exact\[t\] $`\mathrm{QNC}_\mathrm{f}(\mathrm{log}^{}n)`$, i.e. exact\[t\] can be computed exactly in log-star depth and size $`\mathrm{O}\left(n\mathrm{log}n\right)`$.

Proof. Apply the reduction used in Lemma 18 in total $`(\mathrm{log}^{}n)`$-times, until the input size is at most $`2`$. Compute and save the outcome, and clean ancillas by uncomputation. The circuit size is $`\mathrm{O}\left(n\mathrm{log}n\right)`$.  $`\mathrm{}`$

## 6 Circuits of small size

In this section, we decrease the size of some circuits. We allow the use of arbitrary one-qubit gates instead of a fixed basis.

### 6.1 Constant depth approximation of Or

In this section, we apply the reduction from Lemma 18 repeatedly to shrink the circuit for Or. We first reduce the size of the circuit to $`\mathrm{O}\left(n\mathrm{log}n\right)`$. We then develop a recurrent method that reduces the size even further. Let us define a useful notation.

###### Definition 7

Let $`x=x_1x_2\mathrm{}x_n`$. By Or-reduction $`nm`$ with error $`\epsilon `$ we mean a quantum circuit mapping $`|x|0^m|x|\phi `$ such that, if $`|x|=0`$, then $`|\phi =|0^m`$ and, if $`|x|0`$, then $`0^m|\phi \epsilon `$.

The Or-reduction preserves the logical Or of qubits, i.e. $`|x|=0`$ iff $`|\phi |=0`$ with high probability. Theorem 4 provides an Or-reduction $`n1`$ with error $`\frac{1}{n}`$, constant depth, and size $`n^2\mathrm{log}n`$. Lemma 18 provides an Or-reduction $`n\mathrm{log}n`$ with error $`0`$, constant depth, and size $`n\mathrm{log}n`$.

###### Lemma 21

There is an Or-reduction $`n1`$ with error $`\frac{1}{n}`$, constant depth, and size $`n\mathrm{log}n`$.

Proof. Divide the input into $`\frac{\sqrt{n}}{\mathrm{log}n}`$ blocks of size $`\sqrt{n}\mathrm{log}n`$. First, reduce each block by Lemma 18 to $`\frac{1}{2}\mathrm{log}n+\mathrm{log}\mathrm{log}n=\mathrm{O}\left(\mathrm{log}n\right)`$ qubits in constant depth and size $`\sqrt{n}\mathrm{log}^2n`$. In total, we obtain $`\sqrt{n}`$ new qubits in size $`n\mathrm{log}n`$. Second, compute the logical Or by Theorem 4 in constant depth, size $`\sqrt{n}^2\mathrm{log}\sqrt{n}=\mathrm{O}\left(n\mathrm{log}n\right)`$, and error $`\frac{1}{\sqrt{n}}`$. To amplify the error to $`\frac{1}{n}`$, repeat the computation twice and return 1 if any of them returns 1 (the error is one-sided). The circuit size is doubled.  $`\mathrm{}`$

The circuit size can be reduced to $`\mathrm{O}(n\mathrm{log}^{(d)}n)`$ for any constant number $`d`$ of iterations of the logarithm. The trick is to divide input qubits into small blocks and perform the reduction step on each of them. The number of variables is reduced by a small factor and we can thus afford to apply a circuit of a slightly bigger size. It we repeat this reduction step $`d`$ times, we obtain the desired circuit.

###### Theorem 22

There exist constants $`c_1,c_2`$ such that for every $`d`$, there is an Or-reduction $`n1`$ with error $`\frac{1}{n}`$, depth $`c_1d`$, and size $`c_2dn\mathrm{log}^{(d)}n`$.

Proof. By induction on $`d`$: we have already verified the case $`d=1`$ in Lemma 21. For the induction step: Divide $`n`$ input qubits into $`n/\mathrm{log}^{(d1)}n`$ blocks of $`\mathrm{log}^{(d1)}n`$ qubits. Using Lemma 18, reduce each block to $`\mathrm{log}^{(d)}n`$ qubits in constant depth and size $`c_2\mathrm{log}^{(d1)}n\mathrm{log}^{(d)}n`$. Total size is $`c_2n\mathrm{log}^{(d)}n`$. We obtain $`\frac{n}{\mathrm{log}^{(d1)}n}\mathrm{log}^{(d)}n=o(n)`$ new qubits. Using the induction hypothesis, compute their logical Or in depth $`c_1(d1)`$ and size $`c_2(d1)\left(\frac{n}{\mathrm{log}^{(d1)}n}\mathrm{log}^{(d)}n\right)\mathrm{log}^{(d1)}o(n)c_2(d1)n\mathrm{log}^{(d)}n`$. Together, it takes depth $`c_1d`$ and size $`c_2dn\mathrm{log}^{(d)}n`$.

The only approximate step is the final application of Lemma 21 for $`d=1`$. It is applied on $`\frac{n}{\mathrm{log}n}\mathrm{log}^{(d)}n`$ variables, hence the error is $`\mathrm{O}\left(\mathrm{log}n/n\right)`$. It can be amplified to $`\frac{1}{n}`$ by running the computation twice.  $`\mathrm{}`$

### 6.2 Log-star depth computation of Or

Our best constant-depth circuit for Or is described by Theorem 22. It is approximate and it has slightly super-linear size. In this section, we show that we can achieve an exact circuit of linear size if we relax the restriction of constant depth. We consider $`d`$ in Theorem 22 a slowly growing function of $`n`$ instead of a constant. Now we can use an Or-reduction better than Lemma 21. Theorem 20 provides an Or-reduction $`n1`$ with error $`0`$, log-star depth, and size $`n\mathrm{log}n`$.

###### Lemma 23

There exist constants $`c_1,c_2`$ such that for every $`d`$, there is an Or-reduction $`n1`$ with error $`0`$, depth $`c_1d+\mathrm{log}^{}n`$, and size $`c_2dn\mathrm{log}^{(d)}n`$.

Proof. The same as of Theorem 22, but use the Or-reduction from Theorem 20 instead of Lemma 21 in the last layer (for $`d=1`$). The size stays roughly the same, the circuit becomes exact, and the depth is increased by an additional term of $`\mathrm{log}^{}n`$.  $`\mathrm{}`$

###### Theorem 24

There is an Or-reduction $`n1`$ with error $`0`$, log-star depth, and linear size.

Proof. Divide the input into $`\frac{n}{\mathrm{log}^{}n}`$ blocks of size $`\mathrm{log}^{}n`$. Compute the logical Or of each block by a balanced binary tree of depth $`\mathrm{log}(\mathrm{log}^{}n)<\mathrm{log}^{}n`$ and in linear size. Using Lemma 23 with $`d=\mathrm{log}^{}n`$, compute the logical Or of $`\frac{n}{\mathrm{log}^{}n}`$ new qubits in log-star depth and size $`\mathrm{O}\left(\mathrm{log}^{}n\frac{n}{\mathrm{log}^{}n}\mathrm{log}^{(\mathrm{log}^{}n)}n\right)=\mathrm{O}\left(n\right)`$.  $`\mathrm{}`$

### 6.3 Approximation of counting and threshold\[t\]

In this section, we use the QFT for the parallelisation of increments. This allows us to approximate the Hamming weight of the input in smaller size $`\mathrm{O}\left(n\mathrm{log}n\right)`$.

###### Definition 8

The increment gate maps $`\mathrm{Incr}_n:|x|(x+1)mod2^n.`$

###### Lemma 25

The increment gate is diagonal in the Fourier basis and its diagonal form is in $`\mathrm{QNC}^0`$.

Proof. Let $`\omega =e^{2\pi i/2^n}`$ and let $`|x`$ be any computational basis state. It is simple to prove the following two equations:

1. $`\mathrm{Incr}_n=F_{2^n}^{}D_nF_{2^n}`$ for diagonal $`D_n=_{y=0}^{2^n1}\omega ^y|yy|`$.

$$F^{}DF|x=F^{}D\frac{\underset{y=0}{\overset{2^n1}{}}\omega ^{xy}|y}{\sqrt{2^n}}=F^{}\frac{\underset{y=0}{\overset{2^n1}{}}\omega ^{(x+1)y}|y}{\sqrt{2^n}}=|(x+1)mod2^n.$$
2. $`D=R_\mathrm{z}\left(\pi \right)R_\mathrm{z}\left(\pi /2\right)\mathrm{}R_\mathrm{z}\left(\pi /2^{n1}\right)`$.

$`D|x`$ $`=`$ $`\omega ^x|x={\displaystyle \underset{k=1}{\overset{n}{}}}\omega ^{2^{nk}x_{nk}}|x_{nk}={\displaystyle \underset{k=1}{\overset{n}{}}}(e^{2\pi i/2^k})^{x_{nk}}|x_{nk}=`$
$`=`$ $`{\displaystyle \underset{k=1}{\overset{n}{}}}R_\mathrm{z}\left(2\pi /2^k\right)|x_{nk}=\left(R_\mathrm{z}\left(\pi \right)\mathrm{}R_\mathrm{z}\left(\pi /2^{n1}\right)\right)|x.`$

We conclude that $`\mathrm{Incr}=F^{}DF`$, and that $`D`$ is a tensor product of one-qubit operators.  $`\mathrm{}`$

Remark. The addition of a fixed integer $`b`$ is as hard as the increment. By Lemma 25, $`\mathrm{Incr}^b=F^{}D^bF`$ and $`\left(R_\mathrm{z}\left(\phi \right)\right)^b=R_\mathrm{z}\left(\phi b\right)`$, hence the diagonal version of the addition of $`b`$ is also in $`\mathrm{QNC}^0`$.

###### Theorem 26

Counting can be approximated in constant depth and size $`\mathrm{O}\left(n\mathrm{log}n\right)`$.

Proof. Compute the Hamming weight of the input. Each input qubit controls one increment on an $`m`$-qubit counter initialised to $`0`$, where $`m=\mathrm{log}(n+1)`$. The increments $`\mathrm{Incr}_m`$ are parallelised (Theorem 2 and Lemma 25), so we apply the quantum Fourier transform $`F_{2^m}`$ twice (Theorem 9) and the $`n`$ constant-depth controlled $`D_m`$ gates in parallel. The size is $`\mathrm{O}\left(\mathrm{poly}(m)+nm\right)=\mathrm{O}\left(n\mathrm{log}n\right)`$.  $`\mathrm{}`$

Remark. threshold\[t\] is equal to the most significant qubit of the counter if we align it to a power of 2 by adding a fixed integer $`2^mt`$. exact\[t\] can be computed by comparing the counter with $`t`$.

## 7 Concluding remarks

### 7.1 Comparison with randomised circuits

Let us compare our results for quantum circuits with similar results for classical randomised circuits. We consider randomised circuits with bounded fan-in of Or and And gates, and unbounded fan-out and parity (similar to the quantum model). Classical lower bounds are folklore and we attach the proofs for the convenience of the reader in Appendix A.

| Gate | Randomised | Quantum |
| --- | --- | --- |
| Or and threshold\[t\] exactly | $`\mathrm{\Theta }\left(\mathrm{log}n\right)`$ | $`\mathrm{O}\left(\mathrm{log}^{}n\right)`$ |
| mod\[q\] exactly | $`\mathrm{\Theta }\left(\mathrm{log}n\right)`$ | $`\mathrm{\Theta }\left(1\right)`$ |
| Or with error $`\frac{1}{n}`$ | $`\mathrm{\Theta }\left(\mathrm{log}\mathrm{log}n\right)`$ | $`\mathrm{\Theta }\left(1\right)`$ |
| threshold\[t\] with error $`\frac{1}{n}`$ | $`\mathrm{\Omega }\left(\mathrm{log}\mathrm{log}n\right)`$ | $`\mathrm{\Theta }\left(1\right)`$ |

### 7.2 Relations of quantum circuit classes

We have shown that $`\text{B-}\mathrm{QNC}_\mathrm{f}^0=\text{B-}\mathrm{QAC}_\mathrm{f}^0=\text{B-}\mathrm{QACC}^0=\text{B-}\mathrm{QTC}_\mathrm{f}^0`$ (Theorem 6). If we allow arbitrary one-qubit gates, then also $`\mathrm{QTC}_\mathrm{f}^0=\mathrm{QAC}_\mathrm{f}^0\mathrm{QNC}_\mathrm{f}(\mathrm{log}^{}n)`$ (Theorems 19 and 20). Several open problems of \[GHMP02\] have thus been solved. Only little is known about classes that do not include the fan-out gate. For example, we do not know whether $`\mathrm{TC}^0\mathrm{QTC}^0`$, we only know that $`\mathrm{TC}^0\mathrm{QTC}_\mathrm{f}^0`$. It is simple to prove that parity is in $`\mathrm{TC}^0`$. Take the logical Or of exact, exact, exact, …, and compute exact\[$`k`$\] from threshold\[$`k`$\] and threshold\[$`k+1`$\]. However, this method needs fan-out to copy the input bits and hence it is not in $`\mathrm{QTC}^0`$.

Fang et al. proved \[FFG+03\] a lower bound for fan-out. In particular, they showed that logarithmic depth is needed to approximate parity using only a constant number of ancillas. Unfortunately, their method breaks down with more than a linear number of ancillas and it cannot be extended to other unbounded fan-in gates such as majority or threshold\[t\].

### 7.3 Upper bounds for $`\text{B-}\mathrm{QNC}_\mathrm{f}^0`$

Shor’s original factoring algorithm \[Sho94\] uses modular exponentiation and the quantum Fourier transform modulo $`2^n`$ followed by a polynomial-time deterministic algorithm. The modular exponentiation $`a^x`$ can be replaced by multiplication of some subset of numbers $`a`$, $`a^2`$, $`a^4`$, …, $`a^{2^{n1}}`$ \[CW00\]. The $`n`$ numbers $`a^{2^k}`$ can be quickly precomputed classically.

Since both multiplication of $`n`$ numbers (Theorem 7) and the QFT (Theorem 9) are in $`\text{B-}\mathrm{QNC}_\mathrm{f}^0`$, there is a polynomial-time bounded-error classical algorithm with oracle $`\text{B-}\mathrm{QNC}_\mathrm{f}^0`$ factoring numbers, i.e. factoring $`\mathrm{RP}[\text{B-}\mathrm{QNC}_\mathrm{f}^0]`$. If $`\text{B-}\mathrm{QNC}_\mathrm{f}^0\mathrm{BPP}`$,333In this context, $`\text{B-}\mathrm{QNC}_\mathrm{f}^0`$ denotes the set of languages decided with bounded error by constant-depth quantum circuits with fan-out. then factoring $`\mathrm{RP}[\mathrm{BPP}]\mathrm{BPP}[\mathrm{BPP}]=\mathrm{BPP}`$. Discrete logarithms can be computed in a similar way using modular exponentiation and the quantum Fourier transform modulo general $`q`$ \[Sho94\]. Since QFT$`{}_{q}{}^{}\text{B-}\mathrm{QNC}_\mathrm{f}^0`$ (Theorem 13), we conclude that also discrete-log $`\mathrm{RP}[\text{B-}\mathrm{QNC}_\mathrm{f}^0]`$.

### 7.4 Open problems

We propose the following open problems on computational aspects of multi-qubit gates:

1. Is there a constant-depth exact circuit for Or?
2. Is there a constant-depth linear-size circuit for Or?
3. Are there exact circuits with a fixed basis?
4. Can we simulate unbounded fan-out in constant depth using unbounded fan-in gates, e.g. threshold\[t\] or exact\[t\]?

## Acknowledgements

We thank Harry Buhrman, Hartmut Klauck, and Hein Röhrig at CWI in Amsterdam, and Fred Green at Clark University in Worcester for plenty of helpful discussions, and Ronald de Wolf at CWI for help with writing the paper. We thank Klaus Mölmer and Brian King for discussions on physical implementations of multi-qubit gates. We are grateful to Schloss Dagstuhl, Germany, for providing an excellent environment, where part of this work was carried out. We thank the anonymous reviewers for their valuable comments.

## Appendix A Lower bounds on classical circuits

Using the polynomial method \[Bei93\], we prove several lower bounds on the depths of deterministic circuits. We consider circuits with fan-in of Or and And gates at most 2, and unbounded fan-out and parity, the same as in the quantum model.

Basically, the value of each bit computed by a circuit can be computed by a multi-linear polynomial (over the field $`_2`$) in the input bits. We are interested in the degree of such a polynomial; by proving a lower bound on the degree, we also lower-bound the depth of the circuit. It is simple to prove that the polynomial computing a Boolean function is unique.

Each input bit $`x_k\{0,1\}`$ is computed by the polynomial $`x_k`$ of degree 1. The Not gate computes the polynomial $`1p(x)`$, where $`p(x)`$ is the polynomial computing its argument, and the degree is unchanged. The And gate computes the polynomial $`p_1(x)p_2(x)`$ and the two degrees are summed. The parity gate computes the polynomial $`(p_1(x)+\mathrm{}+p_k(x))mod2`$ of degree equal to the maximum degree among the arguments.

###### Lemma 27

The output of a circuit of depth $`d`$ has degree at most $`2^d`$.

Proof. By induction: by adding a new layer, we can at most double the degree when using the And gate.  $`\mathrm{}`$

And of $`n`$ bits is computed by a (unique) polynomial $`x_1x_2\mathrm{}x_n`$ of degree $`n`$. Hence every circuit computing And has depth at least $`\mathrm{log}n`$. It is simple to prove by contradiction that also Or, threshold\[t\], and exact\[t\] have full degree $`n`$. Smolensky has proved a much stronger result \[Smo87\], which implies that also the degree of mod\[q\] for $`q>2`$ is $`n`$.

Randomised circuits have access to random bits and may produce the result with a small error. Some functions are computed in smaller depth in this model.

###### Lemma 28

Or can be computed with one-sided error $`\frac{1}{2}`$ by a randomised circuit of depth 2. The error can be decreased to $`\frac{1}{n}`$ in additional depth $`\mathrm{log}\mathrm{log}n`$.

Proof. Take $`n`$ random bits and output the parity $`x_1r_1x_2r_2\mathrm{}x_nr_n`$. If $`|x|=0`$, then the circuit always outputs 0. If $`|x|>0`$, then the probability that the parity is odd is equal to $`\frac{1}{2}`$. If we perform the computation $`(\mathrm{log}n)`$-times using independent random bits, we decrease the probability of error to $`(\frac{1}{2})^{\mathrm{log}n}=\frac{1}{n}`$. This can be done in additional depth $`\mathrm{log}\mathrm{log}n`$ by a balanced binary tree of Or gates.  $`\mathrm{}`$

By Yao’s principle \[Yao77\], if we have a randomised circuit with error less than $`2^n`$, then there exists an assignment of random bits such that the result is always correct. That is there exists a deterministic circuit of the same shape. Hence also randomised circuits computing the logical Or with exponentially small error have depth at least $`\mathrm{log}n`$.

###### Lemma 29

Every circuit computing Or with error $`\frac{1}{n}`$ has depth at least $`\mathrm{log}\mathrm{log}n`$.

Proof. Assume the converse: there exists a circuit of depth $`d<\mathrm{log}\mathrm{log}n`$ with error $`\frac{1}{n}`$. By computing the logical Or independently $`\frac{n}{\mathrm{log}n}`$-times, we can reduce the error to $`(\frac{1}{n})^{\frac{n}{\mathrm{log}n}}=2^n`$. This can be done in additional depth $`\mathrm{log}\frac{n}{\mathrm{log}n}=\mathrm{log}n\mathrm{log}\mathrm{log}n`$. The total depth of this circuit is $`\mathrm{log}n\mathrm{log}\mathrm{log}n+d<\mathrm{log}n`$. However, by Yao’s principle, the depth has to be at least $`\mathrm{log}n`$.  $`\mathrm{}`$


format: text

text:
# References

Self-duality of the asymptotic relaxation states of fluid and plasmas
F. Spineanu and M. Vlad

Association Euratom-MER Romania
National Institute of Laser, Plasma and Radiation Physics, MG-36 Magurele,
Bucharest, Romania
(*e-mail: florin@drfc.cad.cea.fr, madi@drfc.cad.cea.fr*)

## Abstract

The states of asymptotic relaxation of $`2`$-dimensional fluids and plasma present a high degree of regularity and obey to the $`\mathrm{sinh}`$-Poisson equation. We find that embedding the classical fluid description into a field-theoretical framework, the same equation appears as a manifestation of the self-duality.

The states generated by externally driving (stirring) an ideal fluid can have very irregular form. It is however known from experiments and numerical simulations that after suppressing the drive the system evolves to states with high degree of order, essentially consisting of few large vortices, with very regular geometry. These states are attained after long time evolution and are not due to the residual dissipation. The process consists of vortex merging, which is an essentially topological event where the weak dissipation only allows the reconnection of the field lines but does not produce significant energy loss from the fluid motion. Inferring from results of numerical simulations, Montgomery *et al.* ,  have proved that the scalar stream function $`\psi `$ describing the motion in two-dimensional space obeys in the far asymtotic regime (where the regular structures are dominant) the *sinh*-Poisson equation

$$\mathrm{\Delta }\psi +\gamma \mathrm{sinh}\left(\beta \psi \right)=0$$
(1)
where $`\gamma `$ and $`\beta `$ are *positive* constants. The relations of $`\psi `$ to the velocity and vorticity are $`𝐯=\psi \times \widehat{𝐞}_z`$ , $`\omega =\times 𝐯=^2\psi \widehat{𝐞}_z`$ where $`\widehat{𝐞}_z`$ is the unitary vector perpendicular to the plane. With these variables, the Euler equations for the two dimensional ideal incompressible fluid are

$`{\displaystyle \frac{\omega }{t}}+\left(𝐯\right)\omega `$ $`=`$ $`\mathrm{𝟎}`$ (2)
$`𝐯`$ $`=`$ $`0`$
We will try to develop a field-theoretical model of the stationary asymptotic relaxed states, *i.e.* we look for a model that could provide a derivation of Eq.(1). This will be done progressively, examining models ellaborated for closely related problems and collecting the relevant suggestions that could allow us to write a Lagrangian density.

In the study of the two-dimensional Euler fluids, and in particular in explaining the origin of Eq.(1), an important model consists of a system of $`N`$ discrete vorticity filaments perpendicular on plane, having circular transversal section of radius $`a`$ and carrying the vorticity $`\omega _i`$, $`i=1,N`$. A very comprehensive account of this system is given by Kraichnan and Montgomery  where the correspondence between the continuous and discrete representations of vorticity is discussed in detail. The motion in plane of the $`k`$-th filament of coordinates $`𝐫_k(r_k^1,r_k^2)(x_k,y_k)`$ is given by

$$\frac{dr_k^i}{dt}=\epsilon ^{ij}\frac{}{r_k^j}\underset{n=1,nk}{\overset{N}{}}\omega _nG\left(𝐫_k𝐫_n\right),i,j=1,2,k=1,N$$
(3)
where the summation is over all the other filaments’ positions $`𝐫_n`$, $`nk`$, and $`\epsilon ^{ij}`$ is the antisymmetric tensor in two dimensions. As shown in Ref. $`G\left(𝐫_k𝐫_n\right)`$ can be approximated for $`a`$ small compared to the space extension of the fluid, $`L`$, $`aL`$, as the Green function of the Laplacian

$$G(𝐫,𝐫^{})\frac{1}{2\pi }\mathrm{ln}\left(\frac{\left|𝐫𝐫^{}\right|}{L}\right)$$
(4)
The statistical properties of the system of discrete vortices have been examined using the Liouville theorem and the conservation of energy and momentum . The model consists of an equal number of positive and negative vortices with equal absolute magnitudes $`\left|\omega _i\right|=\left|\omega \right|`$, in contact with a thermal bath of temperature $`T`$. The possibility of the generation of two supervortices of opposite signs arises when $`T`$ is *n*egative and sufficiently large. When the *most probable state* is attained for a stationary configuration the stream function $`\psi `$ is shown to verify the $`\mathrm{sinh}`$-Poisson equation (1). These statistical considerations remain the reference explanation for the appearence of this equation in this context.

Highly ordered states have been obtained by numerical simulations for other systems in two spatial dimensions: systems of filaments of electric current in $`2`$-dimensional MHD, guiding centre particles. The asymptotic states are found to be described by scalar functions obeying Liouville equation or $`\mathrm{sinh}`$-Poisson equation. The theoretical approach which permitted to explain this result was based on the extremum of the entropy over a statistical ensemble of states of a set of discrete objects under the constraints which express the conservation of the invariants of motion and with a negative temperature.

In the equations of motion (3) the right hand side contains the *curl* of the Laplacian Green’s function (4) (we take $`L=1`$)

$$\epsilon ^{ij}_jG(𝐫,𝐫^{})=\epsilon ^{ij}_j\frac{1}{2\pi }\mathrm{ln}r=\frac{1}{2\pi }\epsilon ^{ij}\frac{r^j}{r^2}$$
(5)
$$^2\frac{1}{2\pi }\mathrm{ln}r=\delta ^2\left(r\right)$$

The term in right hand side of (3) can be seen as a vector potential $`𝐚(𝐫,t)`$. The “magnetic” field $`\times 𝐚`$ is a sum of Dirac $`\delta `$ functions at the locations of the vortices. If we take equal strength $`\omega `$ for all vortices this potential appears as the “statistical potential” and has a topological interpretation . From (5) it can be rewritten

$$\frac{1}{2\pi }\epsilon ^{ij}\frac{r^j}{r^2}=\frac{1}{2\pi }_i\mathrm{arctan}\frac{y}{x}=\frac{1}{2\pi }_i\theta $$
(6)
where $`𝐫=(x,y)=(r\mathrm{cos}\theta ,r\mathrm{sin}\theta )`$. The “magnetic” flux through a surface limitted by a large circle is proportional with the number of vortices. The topological nature of this potential suggests that it can be naturally derived in a topological framework, *i.e.* from a Lagrangian density of the Chern-Simons type,

$$=\frac{1}{4}\epsilon ^{\mu \alpha \beta }A_\nu F_{\alpha \beta }$$
(7)
where $`F_{\alpha \beta }=_\alpha A_\beta _\beta A_\alpha `$. In the analysis for the two-dimensional Euler equation (as in the investigation of similar systems), the vorticity-type functions $`\omega `$ are expressed as the Lapacian operator applied on a scalar function and this naturally invokes the Green function of the Laplacian. Then this approach suggests that the intrinsically determined motion of the fluid can be projected onto two distinct parts of a new model: objects (vortices) and interaction between them (the potential obtained from the Green function). The fact that the interaction potential can be derived from a Chern-Simons topological action suggests that, in order to embedd the original Euler fluid system into a larger field theoretical context, we need (a) a “matter” part in the Lagrangian, which should provide the free dynamics of the vortices; (b) the Chern-Simons term, to describe the free dynamics of the field; (c) the interaction term of the (Chern-Simons-) field and the matter. The main requirement to this field-theoretical extension of the original Euler fluid model is to reproduce the discrete vortices and their equation of motion.

Jackiw and Pi ,  have examined a model of $`N`$ interacting particles (of charges $`e_s`$) moving in plane described by the Lagrangian

$$L=\underset{s=1}{\overset{N}{}}\frac{1}{2}m_s𝐯_s^2+\frac{1}{2}d^2r\epsilon ^{\alpha \beta \gamma }\left(_\alpha A_\beta \right)A_\gamma d^2rA_\mu j^\mu $$
(8)
where $`m_s𝐯_s=𝐩_se_s𝐀\left(𝐫_s|𝐫_1,𝐫_2,\mathrm{},𝐫_N\right)`$, $`𝐀(𝐫_s|𝐫_1,𝐫_2,\mathrm{},𝐫_N)(a_s^i(𝐫_1,𝐫_2,\mathrm{},𝐫_N)_{i=1,2}`$ and $`a_s^i(𝐫_1,𝐫_2,\mathrm{},𝐫_N)=\frac{1}{2\pi }\epsilon ^{ij}_{qs}^Ne_q\frac{r_s^jr_q^j}{\left|𝐫_s𝐫_q\right|^2}`$. The matter current is defined as $`j^\mu (\rho ,𝐣)=_{s=1}^Ne_sv_s\delta \left(𝐫𝐫_s\right)`$, $`v_s^\mu =(1,𝐯_s)`$ with the metric $`(1,1,1)`$. By varying the action we obtain the following equations

$$\frac{1}{2}\epsilon ^{\alpha \beta \gamma }F_{\alpha \beta }=\epsilon ^{\gamma \alpha \beta }_\alpha A_\beta =j^\gamma $$

$$B=\rho $$
(9)
$$E^i=\epsilon ^{ij}j^j$$
(10)
Here $`B=\epsilon ^{ij}_jA_i`$. In these equations the potential appears as being generated by the matter, *i.e.* by the “current” of particles. We note that the Eq.(9) connects the matter density with the curl of the potential. This is important since in order to derive it in the context of the quantum version of their model, Jackiw and Pi have shown that one needs to include a nonlinear self-interaction of the wave function representing the matter field. The self-interaction of the scalar matter field is of the type $`\phi ^4`$. The canonical momentum expression becomes the covariant derivative in the field theory version. Even at this point where we only have some hints, it is suggestive to look for possible identifications between the fluid variables and the field theoretical variables of the model of Jackiw and Pi. The fluid variables are: the scalar potential $`\psi `$, the velocity $`v^i=\epsilon ^{ij}_j\psi `$ and the vorticity $`\omega =\epsilon ^{ij}_iv_j`$. In order to check the possibility that the fluid model can be embedded into the field theory just described we identify

$$\omega \rho =\mathrm{\Psi }^{}\mathrm{\Psi }$$
(11)
$$v^iA^i$$
(12)
Consider the relation between the vector potential $`𝐀`$ and the density $`\rho `$, obtained from Eq.(9)

$$^i_iA^j=\epsilon ^{jk}_k\rho $$

or, writting symbolically the Green function of the Laplace operator for argument $`𝐫𝐫^{}`$ as the inverse of the operator at the left, we have

$$A^j(𝐫,t)=\epsilon ^{jk}_kd^2r^{}\left(^i_i\right)_{rr^{}}^1\rho (𝐫^{},t)$$
(13)
Since $`\omega =^2\psi `$ (where $`^2^i_i`$) we have formally $`\psi =\left(^2\right)^1`$ $`\omega `$ and use this formula to calculate the right side term of (13) taking into account the identification (11)

$$\epsilon ^{jk}_kd^2r^{}\left(^i_i\right)_{rr^{}}^1\omega \left(𝐫^{}\right)=\epsilon ^{jk}_k\psi =v^j$$

which confirms (12). It results that if we assume the identification (11) the equation (9) obtained form the Lagrangian is precisely the *definition* of the vorticity vector.

One important hint from the model of Jackiw and Pi is the idea to represent a classical quantity as the modulus of a fictitious complex scalar field, as in Eq.(11) and derive dynamical equations from a Lagrangian density expressed in terms of this field. The substitution of the dynamics expressed in terms of usual mechanical quantities by the richer dynamics of the amplitude and phase of the complex scalar field is an example of embedding of one theory into a larger framework and relies on the example of quantum mechanics.

In Ref.() the $`\mathrm{sinh}`$-Poisson equation is derived in a field theoretical model where instead of the topological coupling two complex scalar fields are considered. In that model the dynamics of the two scalar fields is independent except that the self-interaction depends on both. Combining this suggestion with the one exposed in the previous paragraph, we will take the density $`\rho `$ (which we identify with the local value of the vorticity $`\omega `$ as in Eq.(11) ) as a two-component complex field $`\mathrm{\Psi }`$

$$\rho [\mathrm{\Psi }^{},\mathrm{\Psi }]$$

where $`\mathrm{\Psi }=\left(\begin{array}{c}\varphi _1\\ \varphi _2\end{array}\right)`$. Keeping the same structure of the Lagrangian density as in the previous example but extending to a non-Abelian $`SU\left(2\right)`$ gauge field we have ,

$$=\epsilon ^{\mu \nu \rho }tr\left(_\mu A_\nu A_\rho +\frac{2}{3}A_\mu A_\nu A_\rho \right)+itr\left(\mathrm{\Psi }^{}D_0\mathrm{\Psi }\right)\frac{1}{2}tr\left(\left(D_i\mathrm{\Psi }\right)^{}D_i\mathrm{\Psi }\right)+\frac{1}{4}tr\left([\mathrm{\Psi }^{},\mathrm{\Psi }]\right)^2$$
(14)
where the potantial $`A`$ takes values in the algebra of the group $`SU\left(2\right)`$. This form incorporates and adapt all the suggestions from the previous models: (a) the first term is the general non-Abelian expression of the Chern-Simons term; (b) it uses the covariant derivatives ($`\mu =0,1,2`$, $`i=1,2`$) for the minimal coupling

$$D_\mu \mathrm{\Psi }=_\mu \mathrm{\Psi }+[A_\mu ,\mathrm{\Psi }]$$

(c) Finally, it includes a scalar self-interaction of $`\phi ^4`$ type. Analogous to the case treated by Jackiw and Pi for the $`U\left(1\right)`$ gauge field (8), in Ref. it is shown that the Hamiltonian density corresponding to the Lagrangian density (14) is

$$=\frac{1}{2}tr\left(\left(D_i\mathrm{\Psi }\right)^{}\left(D_i\mathrm{\Psi }\right)\right)\frac{1}{4}tr\left([\mathrm{\Psi }^{},\mathrm{\Psi }]^2\right)$$
(15)
since the Chern-Simons term does not contribute to the energy density (being first order in the time derivatives). The equations of motion are

$$iD_0\mathrm{\Psi }=\frac{1}{2}𝐃^2\mathrm{\Psi }\frac{1}{2}[[\mathrm{\Psi },\mathrm{\Psi }^{}],\mathrm{\Psi }]$$
(16)
$$F_{\mu \nu }=\frac{i}{2}\epsilon _{\mu \nu \rho }J^\rho $$
(17)
Using the notation $`D_\pm D_1\pm iD_2`$ the first term in (15) can be written

$$tr\left(\left(D_i\mathrm{\Psi }\right)^{}\left(D_i\mathrm{\Psi }\right)\right)=tr\left(\left(D_{}\mathrm{\Psi }\right)^{}\left(D_{}\mathrm{\Psi }\right)\right)+\frac{1}{2}tr\left(\mathrm{\Psi }^{}[[\mathrm{\Psi },\mathrm{\Psi }^{}],\mathrm{\Psi }]\right)$$

The last term comes from Eq.(17) and from the definition $`J^0=[\mathrm{\Psi },\mathrm{\Psi }^{}]`$. Then the energy density is

$$=\frac{1}{2}tr\left(\left(D_{}\mathrm{\Psi }\right)^{}\left(D_{}\mathrm{\Psi }\right)\right)0$$
(18)
and the Bogomol’nyi inequality is saturated at *self-duality*

$$D_{}\mathrm{\Psi }=0$$
(19)
$$_+A_{}_{}A_++[A_+,A_{}]=[\mathrm{\Psi },\mathrm{\Psi }^{}]$$
(20)
The first equation results from the minimum in Eq.(18) and the second is actually Eq.(17) with the definitions

$`J^0`$ $`=`$ $`[\mathrm{\Psi }^{},\mathrm{\Psi }]`$
$`J^i`$ $`=`$ $`{\displaystyle \frac{i}{2}}\left([\mathrm{\Psi }^{},D_i\mathrm{\Psi }][\left(D_i\mathrm{\Psi }\right)^{},\mathrm{\Psi }]\right)`$
The *static* solutions of the *self-duality* equations (19, 20) are derived in , using the algebraic *ansatz*:

$$A_i=\underset{a=1}{\overset{r}{}}A_i^aH_a$$

$$\mathrm{\Psi }=\underset{a=1}{\overset{r}{}}\psi ^aE_a+\psi ^ME_M$$

where $`H_a`$ are the Cartan subalgebra generators for the gauge Lie algebra, $`E_a`$ are the simple-root step operators and $`E_M`$ is the step operator corresponding to minus the maximal root . The rank of the algebra is noted $`r`$, and $`r=1`$ for $`SU\left(2\right)`$. Then

$$[\mathrm{\Psi }^{},\mathrm{\Psi }]=\underset{a=1}{\overset{r}{}}\left|\psi ^a\right|^2H_a+\left|\psi ^M\right|^2H_M$$
(21)
The equations (19, 20) lead to the affine Toda equations

$$^2\mathrm{ln}\rho _a+\underset{b=1}{\overset{r+1}{}}\stackrel{~}{C}_{ab}\rho _b=0$$
(22)
for $`a=1,r`$, plus the index for $`M`$, *i.e.* $`a=1,2`$. $`\stackrel{~}{C}_{ab}`$ is the extended Cartan matrix

$$\stackrel{~}{C}_{ab}=\frac{2\alpha ^{\left(a\right)}\alpha ^{\left(b\right)}}{\left|\alpha ^{\left(b\right)}\right|^2},a,b=1,2$$

where $`\alpha ^{\left(a\right)}`$ are the simple root vectors of the algebra $`su\left(2\right)`$, and in addition the minus maximal root. The equations (22) can be written in detail for $`\rho _1\left|\psi ^1\right|^2`$, $`\rho _2\left|\psi ^M\right|^2`$

$`\mathrm{\Delta }\mathrm{ln}\rho _1+2(\rho _1\rho _2)`$ $`=`$ $`0`$ (23)
$`\mathrm{\Delta }\mathrm{ln}\rho _2+2(\rho _1+\rho _2)`$ $`=`$ $`0`$
and this gives the relation

$$\mathrm{\Delta }\mathrm{ln}\left(\rho _1\rho _2\right)=0$$

or

$$\rho _2=\text{const}\rho _1^1$$
(24)
since the exponential of a linear term is excluded by the conditions on a circle at infinity. Using Eq.(21) we have to identify

$$\omega =\rho _1\rho _2$$
(25)
whose equation is obtained from equations in (23) using (24) const$`=1`$ (see bellow)

$$\mathrm{\Delta }\mathrm{ln}\rho _1+2(\rho _1\rho _1^1)=0$$
(26)
The substitution $`\left|\beta \right|\psi \mathrm{ln}\rho _1`$ leads both equations (25) and (26) to the form

$$\mathrm{\Delta }\psi +\frac{4}{\left|\beta \right|}\mathrm{sinh}\left(\left|\beta \right|\psi \right)=0$$
(27)
Choosing a constant different of unity in Eq.(24) imposes a linear substitution of the stream function : $`\psi \psi ^{}\gamma +\beta \psi `$ and modifies the factor multiplying the $`\mathrm{sinh}`$ function in Eq.(27).

We have constructed the Lagrangian density (14) with a standard structure of matter-gauge field interaction and incorporating suggestions from models relevant for our objective. The aim was to reproduce the model of fluid vortex filaments supposed to be a faithfull representation of the original Euler fluid dynamics. The fundamental step in the derivation of the $`\mathrm{sinh}`$-Poisson equation is the assumption that the energy density (18) is minimum (which is equivalent to minimizing the *action* for these stationary solution) *i.e.* in the condition of *self-duality*.

We conclude that the Euler fluid equations can be embedded into a field theoretical framework via the discrete model of vortex filaments. This framework is able to provide the equation obeyed by the scalar stream function at stationarity and this is precisely the equation inferred from numerical experiments. The particularity of the field theoretical framework is that it shows that the asymptotic states consisting of regular vortices correspond to *self-dual* states in field theory. This might have deep significance and deserves further investigation.

One must also note that the statistical-theoretical model able to explain the $`\mathrm{sinh}`$-Poisson equation , , ,  appears to have strong and deep connections with the self-duality. It should be carefully considered as a possible approach in the study of models where self-duality is known to exist, like $`O\left(n\right)`$ or Self-Dual Yang-Mills theory.

Aknowledgement. This work has been presented at the *Forum of Theory* organized by the Department de Recherche sur la Fusion Controlee, CEA-Cadarache, in Aix-en-Provence, France (July 2001). The authors are grateful to the organizers for inviting them to this meeting.