The Role of Multiplicative Complexity in Compiling Low T-count Oracle Circuits

We present a constructive method to create quantum circuits that implement oracles vertical bar x vertical bar y |0 (k) -> vertical bar x vertical bar y circle plus f(x)vertical bar 0 (k) for n-variable Boolean functions f with low T-count. In our method f is given as a 2-regular Boolean logic network over the gate basis {boolean AND,circle plus,1}. Our construction leads to circuits with a T-count that is at most four times the number of AND nodes in the network. In addition, we propose a SAT-based method that allows us to trade qubits for T gates, and explore the space/complexity trade-off of quantum circuits. Our constructive method suggests a new upper bound for the number of T gates and ancilla qubits based on the multiplicative complexity c boolean AND(f) of the oracle function f, which is the minimum number of AND gates that is required to realize f over the gate basis {boolean AND,circle plus,1}. There exists a quantum circuit computing f with at most 4c(boolean AND)(f) T gates using k=c(boolean AND)(f) ancillae. Results known for the multiplicative complexity of Boolean functions can be transferred. We verify our method by comparing it to different state-of-the-art compilers. Finally, we present our synthesis results for Boolean functions used in quantum cryptoanalysis.