The Role of Multiplicative Complexity in Compiling Low $T$-count Oracle Circuits
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
We present a constructive method to create quantum circuits that implement oracles <tex>$\vert x\rangle\vert y\rangle\vert 0\rangle^{k}\mapsto\vert x\rangle\vert y\oplus f(x)\rangle\vert 0\rangle^{k}$</tex> for <tex>$n$</tex>-variable Boolean functions <tex>$f$</tex> with low <tex>$T$</tex>-count. In our method <tex>$f$</tex> is given as a 2-regular Boolean logic network over the gate basis <tex>$\{\wedge, \oplus, 1\}$</tex>. Our construction leads to circuits with a <tex>$T$</tex>-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 <tex>$T$</tex> gates, and explore the space/complexity trade-off of quantum circuits. Our constructive method suggests a new upper bound for the number of <tex>$T$</tex> gates and ancilla qubits based on the multiplicative complexity <tex>$c_{\wedge}(f)$</tex> of the oracle function <tex>$f$</tex>, which is the minimum number of AND gates that is required to realize <tex>$f$</tex> over the gate basis <tex>$\{\wedge, \oplus, 1\}$</tex>. There exists a quantum circuit computing <tex>$f$</tex> with at most <tex>$4c_{\wedge}(f)T$</tex> gates using <tex>$k=c_{\wedge}(f)$</tex> 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.