Analysis of a few Quantum Algorithms and Circuits related to Boolean Functions

Abstract

Boolean functions are fundamental to computation and presently play a crucial role in quantum information processing. This thesis presents two facets of Boolean functions in the context of quantum computing: (I) extending and applying the theoretical framework of Forrelation to cryptographic analysis, and (II) designing efficient quantum circuits for multi-controlled Toffoli gates and Boolean circuit implementations.

Given two Boolean functions $f$ and $g$, Forrelation, introduced by Aaronson (2010), measures the correlation between the truth table of $f$ and the Walsh-Hadamard transform of $g$ at the corresponding points. Here, we revisit the Forrelation framework to study several cryptographically significant spectra of Boolean functions, namely, the Walsh-Hadamard, the crosscorrelation, and the autocorrelation spectra.

We begin with adapting the 3-fold Forrelation formulation to sample the Walsh transform values, achieving a constant-factor improvement in query complexity over the Deutsch-Jozsa algorithm. This has direct applications in resiliency checking. Building on this, we propose a technique to estimate the crosscorrelation (and thereby the autocorrelation) at any desired point. Furthermore, we present, to the best of our knowledge, the first constant-query algorithm for sampling from the complete spectrum of crosscorrelation (and consequently, autocorrelation) using Forrelation. Next, we introduce nega-Forrelation, a variant based on the nega-Hadamard transform, and develop efficient quantum algorithms to estimate and sample from the nega-Hadamard and nega-crosscorrelation spectra. We further connect the hidden shift finding algorithm for bent functions (Rötteler, 2010) with the Forrelation algorithm and extend it to the case of negabent functions. Later, we generalize these cryptographic spectra and the Forrelation formulations for any natural number $m$, identifying the Forrelation and nega-Forrelation as special cases, and propose quantum algorithms towards their estimation.

In a related direction, we focus on the efficient implementation of multi-controlled Toffoli (MCT) gates, specifically optimizing the T depth, which is a crucial parameter for reducing circuit latency on near-term quantum devices with limited coherence times. We present an explicit trade-off between the Toffoli depth and the number of clean ancilla qubits, extending the conditionally clean ancilla technique. Further, we prove that the T depth in the Clifford+T decomposition of an $n$-MCT gate, via Toffoli, is lower bounded by $\lceil \log_2 n \rceil$, achieved through a complete binary tree structure. Later, we generalize the result to show that any arbitrary $n$-input, $m$-output Boolean function (specified by its Algebraic Normal Form) can be implemented with a quantum circuit having optimal T depth $\lceil \log_2 k \rceil$, where $k$ represents the algebraic degree of the function, which is upper bounded by the number of input variables $n$. This result has significant implications in S-box design and quantum implementations of block ciphers, such as AES.