{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "using Yao, BitBasis, LinearAlgebra, SparseArrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider a binary function which is always equal 0 except a single value u.\n",
    "\n",
    "![f(x)](https://miro.medium.com/max/1400/1*PNDtyY7UDMWqMJXADOsluA.png)\n",
    "\n",
    "We want to find $u$.\n",
    "\n",
    "(Assuming Grover’s algorithm has access to an oracle function which can compute f(x) simultaneously)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10-element Array{BitStr{8,Int64},1}:\n",
       " 11110011 ₍₂₎\n",
       " 11110011 ₍₂₎\n",
       " 11110011 ₍₂₎\n",
       " 11110011 ₍₂₎\n",
       " 11110011 ₍₂₎\n",
       " 11110011 ₍₂₎\n",
       " 10110011 ₍₂₎\n",
       " 11110011 ₍₂₎\n",
       " 11110011 ₍₂₎\n",
       " 11110011 ₍₂₎"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function oracle(u::T) where T<:Unsigned\n",
    "    n = ceil(Int, log(2, u)) # Use only as many bits as necessary\n",
    "    v = ones(ComplexF64, 1<<n)\n",
    "    v[u+1] *= -1 # Flip the value we're looking for\n",
    "    Diagonal(v)\n",
    "end\n",
    "\n",
    "function grovers(Uf::AbstractBlock{n}, iter::Int) where n\n",
    "    gen = repeat(n, H)\n",
    "    reflect0 = control(n, -collect(1:n-1), n=>-Z) # I-2|0><0|\n",
    "    repeating_circuit = chain(Uf, gen, reflect0, gen)\n",
    "\n",
    "    reg = zero_state(n) |> gen\n",
    "    for i = 1:iter\n",
    "        reg |> repeating_circuit\n",
    "    end\n",
    "    reg\n",
    "end\n",
    "grovers(matblock(oracle(0b11110011)), 10) |> r -> measure(r,nshots=10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "All 10 shots have converged on the expected 8-bit value.\n",
    "\n",
    "------\n",
    "\n",
    "The only slightly tricky bit about the above is the `reflect0` circuit which is less than obvious. Just to make sure it's doing what it should, I just wanted to compare its matrix with the matrix built from first principles."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "16×16 Diagonal{Int64,Array{Int64,1}}:\n",
       " -1  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅\n",
       "  ⋅  1  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅\n",
       "  ⋅  ⋅  1  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅\n",
       "  ⋅  ⋅  ⋅  1  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅\n",
       "  ⋅  ⋅  ⋅  ⋅  1  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅\n",
       "  ⋅  ⋅  ⋅  ⋅  ⋅  1  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅\n",
       "  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  1  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅\n",
       "  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  1  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅\n",
       "  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  1  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅\n",
       "  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  1  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅\n",
       "  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  1  ⋅  ⋅  ⋅  ⋅  ⋅\n",
       "  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  1  ⋅  ⋅  ⋅  ⋅\n",
       "  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  1  ⋅  ⋅  ⋅\n",
       "  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  1  ⋅  ⋅\n",
       "  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  1  ⋅\n",
       "  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  ⋅  1"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "N=4\n",
    "Int.(real.(mat(control(N, -collect(1:N-1), N=>-Z))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "16×16 Array{Int64,2}:\n",
       " -1  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0\n",
       "  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0\n",
       "  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0  0\n",
       "  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0  0\n",
       "  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0  0\n",
       "  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0  0\n",
       "  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0  0\n",
       "  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0  0\n",
       "  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0  0\n",
       "  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0  0\n",
       "  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0  0\n",
       "  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0  0\n",
       "  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0  0\n",
       "  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  0\n",
       "  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1  0\n",
       "  0  0  0  0  0  0  0  0  0  0  0  0  0  0  0  1"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ZERO1 = [1, 0]\n",
    "ZERO(n) = foldl(kron, fill(ZERO1, n))\n",
    "Int.(real.(sparse(I, 16, 16) - 2*ZERO(4)*ZERO(4)'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Yep, they are the same."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.4.1",
   "language": "julia",
   "name": "julia-1.4"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.4.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}