The multiplicative depth of a logic network over the gate basis ${land, oplus, eg}$ 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 al
gorithm 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.
We generalize quantum circuits for the Toffoli gate presented by Selinger and Jones for functionally controlled NOT gates, i.e., $X$ gates controlled by arbitrary $n$-variable Boolean functions. Our constructions target the gate set consisting of Cli
fford gates and single qubit rotations by arbitrary angles. Our constructions use the Walsh-Hadamard spectrum of Boolean functions and build on the work by Schuch and Siewert and Welch et al. We present quantum circuits for the case where the target qubit is in an arbitrary state as well as the special case where the target is in a known state. Additionally, we present constructions that require no auxiliary qubits and constructions that have a rotation depth of 1.
We present a constructive SAT-based algorithm to determine the multiplicative complexity of a Boolean function, i.e., the smallest number of AND gates in any logic network that consists of 2-input AND gates, 2-input XOR gates, and inverters. In order
to speed-up solving time, we make use of several symmetry breaking constraints; these exploit properties of XAGs that may be useful beyond the proposed SAT-based algorithm. We further propose a heuristic post-optimization algorithm to reduce the number of XOR gates once the optimum number of AND gates has been obtained, which also makes use of SAT solvers. Our algorithm is capable to find all optimum XAGs for representatives of all 5-input affine-equivalent classes, and for a set of frequently occurring 6-input functions.
We present a completely automatic synthesis framework for oracle functions, a central part in many quantum algorithms. The proposed framework for resource-constrained oracle synthesis (ROS) is a LUT-based hierarchical method in which every step is sp
ecifically tailored to address hardware resource constraints. ROS embeds a LUT mapper designed to simplify the successive synthesis steps, costing each LUT according to the resources used by its corresponding quantum circuit. In addition, the framework exploits a SAT-based quantum garbage management technique. Those two characteristics give ROS the ability to beat the state-of-the-art hierarchical method both in number of qubits and in number of operations. The efficiency of the framework is demonstrated by synthesizing quantum oracles for Grovers algorithm.
We present a constructive method to create quantum circuits that implement oracles $|xrangle|yrangle|0rangle^k mapsto |xrangle|y oplus f(x)rangle|0rangle^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 ${land, oplus, 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_land(f)$ of the oracle function $f$, which is the minimum number of AND gates that is required to realize $f$ over the gate basis ${land, oplus, 1}$. There exists a quantum circuit computing $f$ with at most $4 c_land(f)$ $T$ gates using $k = c_land(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.
We present a collection of modular open source C++ libraries for the development of logic synthesis applications. These libraries can be used to develop applications for the design of classical and emerging technologies, as well as for the implementa
tion of quantum compilers. All libraries are well documented and well tested. Furthermore, being header-only, the libraries can be readily used as core components in complex logic synthesis systems.
We present a synthesis framework to map logic networks into quantum circuits for quantum computing. The synthesis framework is based on LUT networks (lookup-table networks), which play a key role in conventional logic synthesis. Establishing a connec
tion between LUTs in a LUT network and reversible single-target gates in a reversible network allows us to bridge conventional logic synthesis with logic synthesis for quantum computing, despite several fundamental differences. We call our synthesis framework LUT-based Hierarchical Reversible Logic Synthesis (LHRS). Input to LHRS is a classical logic network; output is a quantum network (realized in terms of Clifford+$T$ gates). The framework offers to trade-off the number of qubits for the number of quantum gates. In a first step, an initial network is derived that only consists of single-target gates and already completely determines the number of qubits in the final quantum network. Different methods are then used to map each single-target gate into Clifford+$T$ gates, while aiming at optimally using available resources. We demonstrate the effectiveness of our method in automatically synthesizing IEEE compliant floating point networks up to double precision. As many quantum algorithms target scientific simulation applications, they can make rich use of floating point arithmetic components. But due to the lack of quantum circuit descriptions for those components, it can be difficult to find a realistic cost estimation for the algorithms. Our synthesized benchmarks provide cost estimates that allow quantum algorithm designers to provide the first complete cost estimates for a host of quantum algorithms. Thus, the benchmarks and, more generally, the LHRS framework are an essential step towards the goal of understanding which quantum algorithms will be practical in the first generations of quantum computers.
A major hurdle to the deployment of quantum linear systems algorithms and recent quantum simulation algorithms lies in the difficulty to find inexpensive reversible circuits for arithmetic using existing hand coded methods. Motivated by recent advanc
es in reversible logic synthesis, we synthesize arithmetic circuits using classical design automation flows and tools. The combination of classical and reversible logic synthesis enables the automatic design of large components in reversible logic starting from well-known hardware description languages such as Verilog. As a prototype example for our approach we automatically generate high quality networks for the reciprocal $1/x$, which is necessary for quantum linear systems algorithms.
We investigate the subclass of reversible functions that are self-inverse and relate them to reversible circuits that are equal to their reverse circuit, which are called palindromic circuits. We precisely determine which self-inverse functions can b
e realized as a palindromic circuit. For those functions that cannot be realized as a palindromic circuit, we find alternative palindromic representations that require an extra circuit line or quantum gates in their construction. Our analyses make use of involutions in the symmetric group $S_{2^n}$ which are isomorphic to self-inverse reversible function on $n$ variables.
