qSAT: Design of an Efficient Quantum Satisfiability Solver for Hardware Equivalence Checking
Preprint
Abstract
The use of Boolean Satisfiability (SAT) solver for hardware verification incurs exponential run-time in several instances. In this work we have proposed an efficient quantum SAT (qSAT) solver for equivalence checking of Boolean circuits employing Grover's algorithm. The Exclusive-Sum-of-Product based generation of the Conjunctive Normal Form equivalent clauses demand less qubits and minimizes the gates and depth of quantum circuit interpretation. The consideration of reference circuits for verification affecting Grover's iterations and quantum resources are also presented as a case study. Experimental results are presented assessing the benefits of the proposed verification approach using open-source Qiskit platform and IBM quantum computer.Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Noisy intermediate-scale quantum computersFrontiers of Physics, 2023
- Boolean satisfiability in quantum compilationPhilosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 2019
- Exact Synthesis of ESOP Forms2019
- A survey of SAT solverAIP Conference Proceedings, 2017
- Advantages of using relative-phase Toffoli gates with an application to multiple control Toffoli optimizationPhysical Review A, 2016
- A Meet-in-the-Middle Algorithm for Fast Synthesis of Depth-Optimal Quantum CircuitsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2013
- An overview of parallel SAT solvingConstraints, 2012
- Quantum counting1998
- Elementary gates for quantum computationPhysical Review A, 1995
- On the Complexity of Derivation in Propositional Calculus1983