Skip to content
Tutorials Center
My learning

Topics

Lesson 36 of 39 ยท Projects and Practice

Project: A Grover SAT Solver

Build a complete Grover solver for Boolean satisfiability problems: turn a formula into an oracle, count solutions, pick the iteration count and sample answers.

In this project you build a reusable solver that takes a Boolean formula in conjunctive normal form (CNF), finds satisfying assignments with Grover's algorithm and reports how it performs. SAT is the classic NP-complete problem: given a formula like (x1 or not x2) and (x2 or x3), find true/false values making it true. Checking a candidate is cheap, which is exactly the shape Grover needs: an oracle that recognizes a solution.

You will practice four skills: turning a problem into an oracle, choosing the iteration count, running a noisy-shot experiment, and handling an unknown number of solutions.

Plan

  1. Represent a CNF formula as a list of clauses of signed integers (3 means x3, -2 means not x2).
  2. Build the oracle: a diagonal matrix with -1 on every satisfying assignment.
  3. Run Grover iterations on a state vector.
  4. Measure many shots, verify answers classically, and compare with random guessing.
  5. Handle the case where you do not know how many solutions exist.
flowchart LR
    A["CNF formula"] --> B["Oracle: sign flip on satisfying inputs"]
    B --> C["Grover iterations"]
    C --> D["Sample shots"]
    D --> E["Verify classically"]
    E -->|"no solution found"| F["Retry with a different iteration count"]

The solver loop: build, amplify, sample, verify, retry.

Step 1 and 2: formula and oracle

Qubit i represents variable x(i+1). A bit string is an assignment. The oracle only needs a classical function satisfied(assignment); on hardware you would compile it to reversible gates (each clause is an OR built from Toffoli gates plus ancilla qubits, and a final AND collects the clauses), which multiplies the gate count. Here we build the diagonal directly, which is the same operator.

Python Formula to oracle: list the solutions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With 16 assignments and only two solutions, brute force is trivial, but the same code structure scales to the point where only Grover's quadratic speed-up could help (and where building the oracle becomes the real cost).

Step 3: Grover iterations and iteration count

With M solutions among N assignments, the angle satisfies sin(theta) = sqrt(M / N) and the best iteration count is round(pi / (4 * theta) - 1/2). The solver below computes M by classical enumeration (only possible in this toy), runs the iterations and reports the success probability.

Python The solver: oracle, diffusion, sampling

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check the numbers: for the 4-variable formula the Grover success probability should be close to 1, far above the random-guess rate. For the 10-variable instance the number of solutions is small, so Grover needs only a handful of iterations, versus about 1024 / M random guesses.

Step 4: stay honest about verification

Grover returns a candidate. Always verify it by evaluating the formula classically, which takes microseconds. The solver above only counts a sample as found if the oracle marks it. On real, noisy hardware some samples will be wrong, and verification filters them.

Step 5: you do not know M

In practice you do not know how many solutions exist, so you cannot compute the optimal iteration count. Two standard fixes:

  • Quantum counting. Apply phase estimation to the Grover iteration to estimate theta, hence M.
  • Exponential search (Boyer-Brassard-Hoyer-Tapp). Try random iteration counts from a growing range; on average you find a solution in O(sqrt(N / M)) oracle calls without ever knowing M.
Python BBHT search: find a solution without knowing M

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Extensions

  1. Gate-level oracle. Build the clause OR and final AND from X, CNOT and Toffoli gates with ancilla qubits; compare the qubit and gate count with the diagonal trick. How does it change the overall cost?
  2. Other problems. Graph 3-coloring, Sudoku, or subset-sum all give a classical checker you can wrap as an oracle.
  3. Noise. Add a depolarizing error (see noise and decoherence) after each iteration and find the error rate at which Grover stops beating random guessing.
  4. Scaling plot. For random 3-SAT formulas at the hard clause ratio (about 4.27 clauses per variable), measure the Grover iteration count versus n, and compare with the cost of a simple classical DPLL solver.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the SAT oracle do in this project?

    It is a diagonal operator with -1 on satisfying assignments, the phase-flip oracle Grover needs.
  2. 2. Why must you verify the result classically?

    Success probability is high but not 1, and hardware noise adds errors; verification is a quick classical check.
  3. 3. What is the benefit of the BBHT search?

    Randomized iteration counts from a growing range handle an unknown number of solutions.
  4. 4. What usually dominates the real cost of a Grover SAT solver on hardware?

    The oracle needs many Toffoli gates and ancillas, and it is called sqrt(N) times.

Summary

  • A CNF formula becomes a phase oracle; Grover amplifies the satisfying assignments in about (pi/4) * sqrt(N/M) iterations.
  • Always verify candidates classically; use quantum counting or BBHT when M is unknown.
  • On hardware the oracle circuit, not Grover's diffusion, dominates the gate count.
  • Any problem with a fast checker can be wrapped this way, with only a quadratic speed-up.

Next: Project: A Shor Factoring Simulator