Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates

Quantum 8, 1530 (2024).

https://doi.org/10.22331/q-2024-11-20-1530

We explore the power of the unbounded Fan-Out gate and the Global Tunable gates generated by Ising-type Hamiltonians in constructing constant-depth quantum circuits, with particular attention to quantum memory devices. We propose two types of constant-depth constructions for implementing Uniformly Controlled Gates. These gates include the Fan-In gates defined by $|xrangle|branglemapsto |xrangle|boplus f(x)rangle$ for $xin{0,1}^n$ and $bin{0,1}$, where $f$ is a Boolean function. The first of our constructions is based on computing the one-hot encoding of the control register $|xrangle$, while the second is based on Boolean analysis and exploits different representations of $f$ such as its Fourier expansion. Via these constructions, we obtain constant-depth circuits for the quantum counterparts of read-only and read-write memory devices – Quantum Random Access Memory (QRAM) and Quantum Random Access Gate (QRAG) – of memory size $n$. The implementation based on one-hot encoding requires either $O(nlog^{(d)}{n}log^{(d+1)}{n})$ ancillae and $O(nlog^{(d)}{n})$ Fan-Out gates or $O(nlog^{(d)}{n})$ ancillae and $16d-10$ Global Tunable gates, where $d$ is any positive integer and $log^{(d)}{n} = logcdots log{n}$ is the $d$-times iterated logarithm. On the other hand, the implementation based on Boolean analysis requires $8d-6$ Global Tunable gates at the expense of $O(n^{1/(1-2^{-d})})$ ancillae.