🧠 Solving 3-SAT via Quantum Algorithms

📍 EPFL – Bachelor in Computer Science, Year 3 (2023)
👥 Team: Matthias Wyss, Hugo Jeannin
🔗 Code Repository: GitHub Repository

In this project, we explored quantum approaches to solving the NP-complete 3-SAT problem using Grover’s algorithm and Quantum Phase Estimation (QPE). The 3-SAT problem involves determining if there exists a satisfying assignment for a boolean formula in conjunctive normal form with three literals per clause.

We implemented an oracle that encodes 3-SAT clauses as quantum gates, allowing us to apply Grover’s algorithm to search for satisfying assignments. Additionally, QPE was used to estimate the number of solutions to the problem. Simulations were performed using Qiskit on IBM quantum backends, and the results were compared with classical methods to evaluate the potential quantum speedup.

🛠 Tools & Libraries:

🧠 Techniques: