Presentation
A Quantum Solver for the Boolean Matching Problem
DescriptionSolving the Boolean Matching (BMP) is one of the fundamental tasks in EDA: indeed it allows to match components from a technology library for functional equivalence against portions of a digital design. The equivalence under negation-permutation-negation of two Boolean functions requires the exploration of a super-exponential number of possible negations and permutations of input and output bits. Current solutions address the BMP via approximate methods, which still have a more than exponential worst-case time complexity.
In this work, we propose a quantum solver for the BMP achieving an exponential speedup in the exploration of the input negations, and devise a quantum sorting network to perform custom input permutations at runtime. We provide a fully detailed quantum circuit implementing our proposal, showing its costs in terms of the number of qubits and quantum gates.
We experimentally validated our solution both with a quantum circuit simulator and a physical quantum computer, a Rigetti ASPEN-M-2, employing the ISCAS benchmark suite, a de-facto standard for classical EDA.
In this work, we propose a quantum solver for the BMP achieving an exponential speedup in the exploration of the input negations, and devise a quantum sorting network to perform custom input permutations at runtime. We provide a fully detailed quantum circuit implementing our proposal, showing its costs in terms of the number of qubits and quantum gates.
We experimentally validated our solution both with a quantum circuit simulator and a physical quantum computer, a Rigetti ASPEN-M-2, employing the ISCAS benchmark suite, a de-facto standard for classical EDA.
Event Type
Work-in-Progress Poster
TimeTuesday, June 256:00pm - 7:00pm PDT
LocationLevel 2 Lobby
AI
Autonomous Systems
Cloud
Design
EDA
Embedded Systems
IP
Security