A Grover-meets-Simon Approach to Match Vector Boolean Functions

The Boolean Matching Problem via NP -Equivalence requires determining whether two Boolean functions are equivalent or not up to a permutation and negation of the input binary variables. Its solution is a fundamental step in the Electronic Design Automation (EDA) tool chains commonly used for digital circuit design. In fact, the library-mapping step of an EDA workflow requires matching parts of the gate-level design (netlist) with the components available in a technology library, considering them as Boolean functions, while taking into account that permutations and negations of input variables can be efficiently implemented through rewiring and the use of inverters. For n-to-n vector Boolean functions, where n is the number of input and output variables, the search space of possible negations and permutations is super-exponential in size, while the O(n!n2^{2n}) time complexity of classical approaches allows solving only small instances of the NP -problem, often limited to n-to-1 Boolean functions (executing O(n!2^{2n}) bit operations). This work presents a quantum algorithm for matching n-to-n vector Boolean functions by effectively combining the Grover-meets-Simon approach with an original and novel use of the Simon solver without the constraints imposed by its usual premises. We provide a fully detailed quantum circuit implementing our proposal, calculate its cost by evaluating key performance indicators for circuit synthesis and show a superpolynomial speedup over classical solutions. Finally, we validate our approach on the Boolean functions included in the ISCAS benchmark suite, which are of practical interest in EDA.