Alessandro Tempia Calvino

Ashenhurst-Curtis decomposition (ACD) is a Boolean decomposition technique widely used in logic synthesis for tasks such as the decomposition of multi-valued relations, the encoding of multi-valued networks, and technology mapping into standard cells for ASICs and lookup tables (LUTs) for FPGAs. A recent truth-table-based implementation of ACD has proven effective for delay-driven LUT mapping while reducing the number of lookup tables, but it does not leverage the flexibility provided by don't-care conditions. In this paper, we enhance ACD by incorporating controllability don't-cares extracted from cuts. Exploiting these additional degrees of freedom, the proposed method increases the decomposition success rate of practical functions into 6-LUTs from 51% to 53.4% and lowers the average number of LUTs per decomposition from 2.50 to 2.46, with even larger gains for large fixed free sets, at only a 1.5x runtime overhead.

This paper addresses the challenge of reducing the number of nodes in Look-Up Table (LUT) networks, with two significant applications: minimizing node count to meet FPGA resource constraints, and area-oriented design space exploration for standard-cell designs, where collapsing a circuit into a LUT network, restructuring it, and remapping helps escape local minima. State-of-the-art substitution algorithms for LUT networks rely heavily on SAT solving, limiting the number of optimization attempts and the size of substitution sub-networks to one node. Conversely, our method relies on circuit simulation to increase the number of substitution candidates and enables substitutions with more than one node. Experimental results show the method identifies optimization opportunities overlooked by other methods, improving 11 out of 23 best-known results in the EPFL synthesis competition and yielding a 3.46% area reduction compared to the state-of-the-art.

Quantum oracle synthesis involves compiling arbitrary Boolean functions into quantum circuits using the gates supported by the target quantum computer. In fault-tolerant quantum computing, these gates (e.g., the Clifford+T library) must be further expressed by logical quantum error correction (QEC) code operations, a process known as back-end compilation. This paper enhances current XAG-based oracle synthesis techniques by establishing a link between the properties of XOR-AND-inverter graphs (XAGs) and the quality measures of back-end-compiled quantum oracles. This connection unlocks additional optimization opportunities: experimental results demonstrate average reductions of 4.49% in T count, 7.00% in logical time steps, and 14.89% in helper qubit count.