NECSTFridayTalk – A Quantum Approach to Match Boolean Functions to Classic Gate Library Elements
NECSTFridayTalk
Speaker: Marco Venere
DEIB PhD student
DEIB - NECSTLab Meeting Room (Bld. 20)
Online by Zoom
May 10th, 2024 | 11.30 am
Contact: Prof. Marco Santambrogio
Research Line: System architectures
Speaker: Marco Venere
DEIB PhD student
DEIB - NECSTLab Meeting Room (Bld. 20)
Online by Zoom
May 10th, 2024 | 11.30 am
Contact: Prof. Marco Santambrogio
Research Line: System architectures
Sommario
On May 10th, 2024 at 11.30 am a new appointment of NECSTFridayTalk series titled "A Quantum Approach to Match Boolean Functions to Classic Gate Library Elements" will take place at DEIB NECSTLab Meeting Room (Building 20) and on line by Zoom.
During this talk, we will have as speaker Marco Venere, PhD student in Information Technology at DEIB, Politecnico di Milano on the following about the talk:
Determining whether two Boolean functions are equivalent or not up to a permutation and/or a negation of the inputs, and a negation of the output is a fundamental step in Electronic Design Automation (EDA) tool-chains commonly employed for digital circuits design. Indeed, the library-mapping step of an EDA flow requires matching portions of the gate-level design (netlist) with the available components provided by a technology library, considering them as Boolean functions, while taking into account that input variable permutations and input/output variable negations can be efficiently implemented via rewiring and inverters. In this work, we propose the first quantum approach to solve the Negation-Permutation-Negation Boolean equivalence problem between n-input Boolean functions, providing a super-polynomial speedup with respect to the classical O(n! 2n+1) complexity. Our approach builds on the quantum solver for the Simon’s problem to reduce the complexity of the matching across negations, and on the design of quantum sorting networks to manage permutations efficiently. We provide a fully detailed quantum circuit implementing our proposal, showing its costs in terms of number of qubits and quantum gates. We experimentally validated our solution both with a quantum circuit simulator and running on a Rigetti ASPEN-M-2, employing the ISCAS benchmark suite, a de-facto standard for classical EDA.
During this talk, we will have as speaker Marco Venere, PhD student in Information Technology at DEIB, Politecnico di Milano on the following about the talk:
Determining whether two Boolean functions are equivalent or not up to a permutation and/or a negation of the inputs, and a negation of the output is a fundamental step in Electronic Design Automation (EDA) tool-chains commonly employed for digital circuits design. Indeed, the library-mapping step of an EDA flow requires matching portions of the gate-level design (netlist) with the available components provided by a technology library, considering them as Boolean functions, while taking into account that input variable permutations and input/output variable negations can be efficiently implemented via rewiring and inverters. In this work, we propose the first quantum approach to solve the Negation-Permutation-Negation Boolean equivalence problem between n-input Boolean functions, providing a super-polynomial speedup with respect to the classical O(n! 2n+1) complexity. Our approach builds on the quantum solver for the Simon’s problem to reduce the complexity of the matching across negations, and on the design of quantum sorting networks to manage permutations efficiently. We provide a fully detailed quantum circuit implementing our proposal, showing its costs in terms of number of qubits and quantum gates. We experimentally validated our solution both with a quantum circuit simulator and running on a Rigetti ASPEN-M-2, employing the ISCAS benchmark suite, a de-facto standard for classical EDA.
The NECSTLab is a DEIB laboratory, with different research lines on advanced topics in computing systems: from architectural characteristics, to hardware-software codesign methodologies, to security and dependability issues of complex system architectures.
Every week, the “NECSTFridayTalk” invites researchers, professionals or entrepreneurs to share their work experiences and projects they are implementing in the “Computing Systems”.
