Lowering the T-depth of Quantum Circuits By Reducing the Multiplicative Depth Of Logic Networks
This work addresses a bottleneck in quantum computing and cryptography by optimizing circuit depth, though it appears incremental as it builds on existing synthesis techniques.
The paper tackles the problem of reducing the multiplicative depth in logic networks, which directly lowers the T-depth of quantum circuits, resulting in improvements over state-of-the-art methods and hand-optimized circuits for instances like AES, SHA, and floating-point arithmetic.
The multiplicative depth of a logic network over the gate basis $\{\land, \oplus, \neg\}$ is the largest number of $\land$ gates on any path from a primary input to a primary output in the network. We describe a dynamic programming based logic synthesis algorithm to reduce the multiplicative depth in logic networks. It makes use of cut enumeration, tree balancing, and exclusive sum-of-products (ESOP) representations. Our algorithm has applications to cryptography and quantum computing, as a reduction in the multiplicative depth directly translates to a lower $T$-depth of the corresponding quantum circuit. Our experimental results show improvements in $T$-depth over state-of-the-art methods and over several hand-optimized quantum circuits for instances of AES, SHA, and floating-point arithmetic.