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

Abstract

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 $|x⟩|b⟩\mapsto |x⟩|b\oplus f(x)⟩$ for $x\in \{0,1{\}}^n$ and $b\in \{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 $|x⟩$, 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(n{\log }^{(d)}n{\log }^{(d+1)}n)$ ancillae and $O(n{\log }^{(d)}n)$ Fan-Out gates or $O(n{\log }^{(d)}n)$ ancillae and $16d-10$ Global Tunable gates, where $d$ is any positive integer and ${\log }^{(d)}n=\log \cdots \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.