Lowering the T-depth of Quantum Circuits By Reducing the Multiplicative Depth Of Logic Networks

Abstract

The multiplicative depth of a logic network over the gate basis $\{\wedge ,\oplus ,\neg \}$ is the largest number of $\wedge$ 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.

arXiv comment8 pages, 3 figures

References in corpus (6)

• Quantum Computing in the NISQ era and beyond
• A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
• Novel constructions for the fault-tolerant Toffoli gate
• Quantum computation with realistic magic state factories
• Faster Quantum Number Factoring via Circuit Synthesis
• The EPFL Logic Synthesis Libraries

Cited by in corpus (2)

• T-count and T-depth of any multi-qubit unitary
• A (quasi-)polynomial time heuristic algorithm for synthesizing T-depth optimal circuits