Close Encounters with Boolean Functions of Three Different Kinds

Junhong Nie, Wei Zi

Quantum oracle of Boolean functions is one of the central bridges between classical and quantum algorithms, but the study focusing at quantum circuit optimization of such oracle is yet closed. In this paper, we propose nearly optimal tradeoffs among circuit size, circuit depth and ancilla count, for quantum oracles of three kinds of Boolean functions: general total Boolean functions with output size $b$: with $1\le m\leΘ\left(\frac{2^n}{n}\right)$ ancilla, size $\mathcal{O}\left(\frac{b2^n}{\log(n+m)}\right)$, depth $\mathcal{O}\left(\frac{b2^n}{n+m}\right)$; partial Boolean functions of effective support size $d$ and output size $b$: with $Θ\left(\log d\right)\le m\le Θ\left(d\right)$ ancilla, size $\mathcal{O}\left(n\log d+bd\right)$, depth $\mathcal{O}\left(\frac{n\log n\log d}{n+m}+\log n+\frac{d(\log d+b\log m)}{m}\right)$; sparse Boolean functions of true input size $d$: with $Θ\left(\log n+\log d\right)\le m\leΘ\left(\frac{nd}{\log d}\right)$ ancilla, size $\mathcal{O}\left(n^2\log d+\frac{nd}{\log(\log d+m/n)}\right)$, depth $\mathcal{O}\left(\frac{n^2\log n\log d}{n+m}+\log n+\frac{nd}{m}\right)$. All the size and depth bounds are asymptotically optimal up to logarithmic factors in the corresponding ancilla count regions. We hope these results find applications in scenarios where classical procedures are needed to be embedded into quantum circuits, such as QROM implementation and quantum algorithm design.

Sergei Kurgalin, Sergei Borzunov

Noga Alon, Amit Weinstein

Jie Zhang, Qiaoyan Wen

A construction of all kinds of quantum Boolean functions with one qubit is proposed. Base on these quantum Boolean functions, all kinds of local quantum Boolean functions (the natural generalization of linear classical Boolean functions) are given. Furthermore some infinite families of quantum Boolean functions with any qubits are obtained together.

Weng-Long Chang, Athanasios V. Vasilakos

Shanqi Pang, Qingjuan Zhang, Xiao Lin

The existing construction methods of Quantum Boolean functions (QBFs) are extended and simplified. All QBFs with one qubit and all local QBFs with any qubits are constructed. And we propose the concept of Generalized quantum Boolean functions (GQBFs). We find all GQBFs with one qutrit and all kinds of local GQBFs with any qutrits. The number of each of the four kinds of functions above is uncountably infinitely many. By using diagonal matrices, we obtain uncountably infinitely many non-local QBFs with any qubits and GQBFs with any qutrits. Infinitely many families of GQBFs with any qudits are obtained from the properties of projection matrices of known saturated orthogonal arrays.