Enhancing Grover's Search for solving Satisfiability (SAT) Problems

  • Context: Grover’s Search has been successfully used to provide quadratic speedups compared to brute force solving of SAT equations. It can also be used when uniformly sampling from a large searchspace. In the future, quantum computers will be robust enough to run real world examples. Quantum software should be ready by then.

     

    Goal: Enhance the existing Qiskit implementation of Grover’s Search for uniform random sampling of configuration spaces by introducing more logic circuits (e.g. Fredkin) and generating openQASM code directly instead of using Qiskit. Currently only NNF gates (and, or, not) are implemented. The resulting circuits may be evaluated in terms of max depth and width compared to the previous implementations.

     

    Requirements: Linear algebra, Boolean Logic, Python, (Basic knowledge of gate based quantumcomputing is beneficial but can be acquired during the thesis)