The Boolean satisfiability problem asks for an assignment of Boolean-variable values that makes a given Boolean expression true. It provides a compact search problem for translating a classical task into quantum terms. section 6.0
A quantum treatment follows this workflow:
- Convert the classical satisfiability task into a quantum formulation. section 6.0
- Apply a quantum search algorithm, such as Grover’s algorithm. section 6.0
- Evaluate the quantum program and compare it with the best classical algorithm on large instances. section 6.0
Figure 6.1 To solve a classical problem on a quantum computer, we start by converting the problem to its “quantum” formulation to which we can apply a quantum algorithm. After this, we implement the algorithm itself as a quantum program. Finally, we evaluate the performance of the quantum program and compare it to that of the best classical algorithm for solving the same problem. This way, we can see whether this quantum algorithm offers a practical advantage over the classical approaches.
Follow the pipeline from classical problem formulation through quantum implementation to performance comparison. section 6.0
