;;;; An example of Grover's algorithm (quantum search)
(in-package :cl-quantum/examples)

(defun count-grover-iterations (bits targets)
  "Count the number of iterations it takes to have a high probability of finding
TARGETS in a search space of 2^BITS."
  (values (floor (* (/ pi 4) (sqrt (/ (ash 1 bits) targets))))))

(defun make-grover-circuit (bits target)
  "Generate a quantum circuit that runs Grover's algorithm over a state of BITS
bits and finds when the state is equal to TARGET."
  (assert (> (ash 1 bits) target)
          (bits target)
          "Target bit of ~s out of range for state with ~s bits." target bits)
  (with-build-circuit bits
    ;; Setup
    (loop for i below bits do (:h i))

    (loop
      repeat (count-grover-iterations bits 1)
      do
         ;; Oracle
         (loop for i below bits
               for cur = (logand (ash target (- i)) 1)
               when (zerop cur)
                 do (:x i))
         (:ncz 0 (loop for i from 1 below bits collect i))
         (loop for i below bits
               for cur = (logand (ash target (- i)) 1)
               when (zerop cur)
                 do (:x i))

         ;; Diffuser
         (loop for i below bits do (:h i))
         (loop for i below bits do (:x i))
         (:ncz 0 (loop for i from 1 below bits collect i))
         (loop for i below bits do (:x i))
         (loop for i below bits do (:h i)))))