\n",
" ## Circuit Construction of a Grover Oracle (click to expand)

\n",
"

\n",
"\n",
"For the next part of this chapter, we aim to teach the core concepts of the algorithm. We will create example oracles where we know $\\omega$ beforehand, and not worry ourselves with whether these oracles are useful or not. At the end of the chapter, we will cover a short example where we create an oracle to solve a problem (sudoku)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Amplitude Amplification\n",
"\n",
"So how does the algorithm work? Before looking at the list of items, we have no idea where the marked item is. Therefore, any guess of its location is as good as any other, which can be expressed in terms of a\n",
"uniform superposition: $|s \\rangle = \\frac{1}{\\sqrt{N}} \\sum_{x = 0}^{N -1} | x\n",
"\\rangle.$\n",
"\n",
"If at this point we were to measure in the standard basis $\\{ | x \\rangle \\}$, this superposition would collapse, according to the fifth quantum law, to any one of the basis states with the same probability of $\\frac{1}{N} = \\frac{1}{2^n}$. Our chances of guessing the right value $w$ is therefore $1$ in $2^n$, as could be expected. Hence, on average we would need to try about $N/2 = 2^{n-1}$ times to guess the correct item.\n",
"\n",
"Enter the procedure called amplitude amplification, which is how a quantum computer significantly enhances this probability. This procedure stretches out (amplifies) the amplitude of the marked item, which shrinks the other items' amplitude, so that measuring the final state will return the right item with near-certainty. \n",
"\n",
"This algorithm has a nice geometrical interpretation in terms of two reflections, which generate a rotation in a two-dimensional plane. The only two special states we need to consider are the winner $| w \\rangle$ and the uniform superposition $| s \\rangle$. These two vectors span a two-dimensional plane in the vector space $\\mathbb{C}^N.$ They are not quite perpendicular because $| w \\rangle$ occurs in the superposition with amplitude $N^{-1/2}$ as well.\n",
"We can, however, introduce an additional state $|s'\\rangle$ that is in the span of these two vectors, which is perpendicular to $| w \\rangle$ and is obtained from $|s \\rangle$ by removing $| w \\rangle$ and\n",
"rescaling. \n",
"\n",
"**Step 1**: The amplitude amplification procedure starts out in the uniform superposition $| s \\rangle$, which is easily constructed from $| s \\rangle = H^{\\otimes n} | 0 \\rangle^n$.\n",
"\n",
"![image2](images/grover_step1.jpg)\n",
"\n",
"\n",
"The left graphic corresponds to the two-dimensional plane spanned by perpendicular vectors $|w\\rangle$ and $|s'\\rangle$ which allows to express the initial state as $|s\\rangle = \\sin \\theta | w \\rangle + \\cos \\theta | s' \\rangle,$ where $\\theta = \\arcsin \\langle s | w \\rangle = \\arcsin \\frac{1}{\\sqrt{N}}$. The right graphic is a bar graph of the amplitudes of the state $| s \\rangle$.\n",
"\n",
"**Step 2**: We apply the oracle reflection $U_f$ to the state $|s\\rangle$.\n",
"\n",
"![image3](images/grover_step2.jpg)\n",
"\n",
"Geometrically this corresponds to a reflection of the state $|s\\rangle$ about $|s'\\rangle$. This transformation means that the amplitude in front of the $|w\\rangle$ state becomes negative, which in turn means that the average amplitude (indicated by a dashed line) has been lowered.\n",
"\n",
"**Step 3**: We now apply an additional reflection ($U_s$) about the state $|s\\rangle$: $U_s = 2|s\\rangle\\langle s| - \\mathbb{1}$. This transformation maps the state to $U_s U_f| s \\rangle$ and completes the transformation. \n",
"\n",
"![image4](images/grover_step3.jpg)\n",
"\n",
"Two reflections always correspond to a rotation. The transformation $U_s U_f$ rotates the initial state $|s\\rangle$ closer towards the winner $|w\\rangle$. The action of the reflection $U_s$ in the amplitude bar diagram can be understood as a reflection about the average amplitude. Since the average amplitude has been lowered by the first reflection, this transformation boosts the negative amplitude of $|w\\rangle$ to roughly three times its original value, while it decreases the other amplitudes. We then go to **step 2** to repeat the application. This procedure will be repeated several times to zero in on the winner. \n",
"\n",
"After $t$ steps we will be in the state $|\\psi_t\\rangle$ where: $| \\psi_t \\rangle = (U_s U_f)^t | s \\rangle.$\n",
"\n",
"How many times do we need to apply the rotation? It turns out that roughly $\\sqrt{N}$ rotations suffice. This becomes clear when looking at the amplitudes of the state $| \\psi \\rangle$. We can see that the amplitude of $| w \\rangle$ grows linearly with the number of applications $\\sim t N^{-1/2}$. However, since we are dealing with amplitudes and not probabilities, the vector space's dimension enters as a square root. Therefore it is the amplitude, and not just the probability, that is being amplified in this procedure.\n",
"\n",
"In the case that there are multiple solutions, $M$, it can be shown that roughly $\\sqrt{(N/M)}$ rotations will suffice.\n",
"\n",
"![image5](images/grover_circuit_high_level.png)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 2. Example: 2 Qubits \n",
"\n",
"Let's first have a look at the case of Grover's algorithm for $N=4$ which is realized with 2 qubits. In this particular case, only \n", "If we have our classical function $f(x)$, we can convert it to a reversible circuit of the form:\n", "

\n", "\n", "

\n", "If we initialise the 'output' qubit in the state $|{-}\\rangle$, the phase kickback effect turns this into a Grover oracle (similar to the workings of the Deutsch-Jozsa oracle):\n", "

\n", "\n", "

\n", "We then ignore the auxiliary ($|{-}\\rangle$) qubit.\n", "

\n", "- \n",
"
- \n", " Following the above introduction, in the case $N=4$ we have \n", "\n", "$$\\theta = \\arcsin \\frac{1}{2} = \\frac{\\pi}{6}.$$\n", "\n", " \n", "
- \n", " After $t$ steps, we have $$(U_s U_\\omega)^t | s \\rangle = \\sin \\theta_t | \\omega \\rangle + \\cos \\theta_t | s' \\rangle ,$$where $$\\theta_t = (2t+1)\\theta.$$\n", "\n", " \n", "
- \n", " In order to obtain $| \\omega \\rangle$ we need $\\theta_t = \\frac{\\pi}{2}$, which with $\\theta=\\frac{\\pi}{6}$ inserted above results to $t=1$. This implies that after $t=1$ rotation the searched element is found.\n", " \n", "

"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"grover_circuit = initialize_s(grover_circuit, [0,1])\n",
"grover_circuit.draw()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Apply the Oracle for $|w\\rangle = |11\\rangle$. This oracle is specific to 2 qubits:"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"

"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"grover_circuit.cz(0,1) # Oracle\n",
"grover_circuit.draw()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We now want to apply the diffuser ($U_s$). As with the circuit that initializes $|s\\rangle$, we'll create a general diffuser (for any number of qubits) so we can use it later in other problems. "
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"tags": [
"thebelab-init"
]
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"

"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Diffusion operator (U_s)\n",
"grover_circuit.h([0,1])\n",
"grover_circuit.z([0,1])\n",
"grover_circuit.cz(0,1)\n",
"grover_circuit.h([0,1])\n",
"grover_circuit.draw()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This is our finished circuit."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 2.1.1 Experiment with Simulators \n",
"\n",
"Let's run the circuit in simulation. First, we can verify that we have the correct statevector:"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/latex": [
"$\\displaystyle \n",
"$$ |\\psi\\rangle =\\begin{bmatrix}\n",
"0 \\\\\n",
"0 \\\\\n",
"0 \\\\\n",
"1\\end{bmatrix} $"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"sim = Aer.get_backend('aer_simulator')\n",
"# we need to make a copy of the circuit with the 'save_statevector'\n",
"# instruction to run on the Aer simulator\n",
"grover_circuit_sim = grover_circuit.copy()\n",
"grover_circuit_sim.save_statevector()\n",
"qobj = assemble(grover_circuit_sim)\n",
"result = sim.run(qobj).result()\n",
"statevec = result.get_statevector()\n",
"from qiskit_textbook.tools import vector2latex\n",
"vector2latex(statevec, pretext=\"|\\\\psi\\\\rangle =\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As expected, the amplitude of every state that is not $|11\\rangle$ is 0, this means we have a 100% chance of measuring $|11\\rangle$:"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"

"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"grover_circuit.measure_all()\n",
"\n",
"aer_sim = Aer.get_backend('aer_simulator')\n",
"qobj = assemble(grover_circuit)\n",
"result = aer_sim.run(qobj).result()\n",
"counts = result.get_counts()\n",
"plot_histogram(counts)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 2.1.2 Experiment with Real Devices \n",
"\n",
"We can run the circuit a real device as below."
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"tags": [
"uses-hardware"
]
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Running on current least busy device: ibmq_mumbai\n"
]
}
],
"source": [
"# Load IBM Q account and get the least busy backend device\n",
"provider = IBMQ.load_account()\n",
"provider = IBMQ.get_provider(\"ibm-q\")\n",
"device = least_busy(provider.backends(filters=lambda x: x.configuration().n_qubits >= 3 and \n",
" not x.configuration().simulator and x.status().operational==True))\n",
"print(\"Running on current least busy device: \", device)"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"tags": [
"uses-hardware"
]
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Job Status: job has successfully run\n"
]
}
],
"source": [
"# Run our circuit on the least busy backend. Monitor the execution of the job in the queue\n",
"from qiskit.tools.monitor import job_monitor\n",
"transpiled_grover_circuit = transpile(grover_circuit, device, optimization_level=3)\n",
"job = device.run(transpiled_grover_circuit)\n",
"job_monitor(job, interval=2)"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"tags": [
"uses-hardware"
]
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"

"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Get the results from the computation\n",
"results = job.result()\n",
"answer = results.get_counts(grover_circuit)\n",
"plot_histogram(answer)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We confirm that in the majority of the cases the state $|11\\rangle$ is measured. The other results are due to errors in the quantum computation. \n",
"\n",
"## 3. Example: 3 Qubits \n",
"\n",
"We now go through the example of Grover's algorithm for 3 qubits with two marked states $\\lvert101\\rangle$ and $\\lvert110\\rangle$, following the implementation found in Reference [2]. The quantum circuit to solve the problem using a phase oracle is:\n",
"\n",
"![image11](images/grover_circuit_3qubits.png)\n",
"\n",
"

- \n",
"
- \n", " Apply Hadamard gates to $3$ qubits initialized to $\\lvert000\\rangle$ to create a uniform superposition:\n", " $$\\lvert \\psi_1 \\rangle = \\frac{1}{\\sqrt{8}} \\left( \n", " \\lvert000\\rangle + \\lvert001\\rangle + \\lvert010\\rangle + \\lvert011\\rangle + \n", " \\lvert100\\rangle + \\lvert101\\rangle + \\lvert110\\rangle + \\lvert111\\rangle \\right) $$\n", " \n", "\n", "
- \n", " Mark states $\\lvert101\\rangle$ and $\\lvert110\\rangle$ using a phase oracle:\n", " $$\\lvert \\psi_2 \\rangle = \\frac{1}{\\sqrt{8}} \\left( \n", " \\lvert000\\rangle + \\lvert001\\rangle + \\lvert010\\rangle + \\lvert011\\rangle + \n", " \\lvert100\\rangle - \\lvert101\\rangle - \\lvert110\\rangle + \\lvert111\\rangle \\right) $$\n", " \n", "\n", "
- \n",
" Perform the reflection around the average amplitude:\n",
" \n",
"
- \n",
"
- Apply Hadamard gates to the qubits\n", " $$\\lvert \\psi_{3a} \\rangle = \\frac{1}{2} \\left( \n", " \\lvert000\\rangle +\\lvert011\\rangle +\\lvert100\\rangle -\\lvert111\\rangle \\right) $$\n", " \n", " \n", "
- Apply X gates to the qubits\n", " $$\\lvert \\psi_{3b} \\rangle = \\frac{1}{2} \\left( \n", " -\\lvert000\\rangle +\\lvert011\\rangle +\\lvert100\\rangle +\\lvert111\\rangle \\right) $$\n", " \n", "\n", "
- Apply a doubly controlled Z gate between the 1, 2 (controls) and 3 (target) qubits\n", " $$\\lvert \\psi_{3c} \\rangle = \\frac{1}{2} \\left( \n", " -\\lvert000\\rangle +\\lvert011\\rangle +\\lvert100\\rangle -\\lvert111\\rangle \\right) $$\n", " \n", "
- Apply X gates to the qubits\n", " $$\\lvert \\psi_{3d} \\rangle = \\frac{1}{2} \\left( \n", " -\\lvert000\\rangle +\\lvert011\\rangle +\\lvert100\\rangle -\\lvert111\\rangle \\right) $$\n", " \n", "
- Apply Hadamard gates to the qubits\n", " $$\\lvert \\psi_{3e} \\rangle = \\frac{1}{\\sqrt{2}} \\left( \n", " -\\lvert101\\rangle -\\lvert110\\rangle \\right) $$\n", " \n", "

\n",
"\n",
" - \n", " Measure the $3$ qubits to retrieve states $\\lvert101\\rangle$ and $\\lvert110\\rangle$\n", " \n", "

\n",
"## Details: Creating a General Diffuser (click to expand)

\n",
" \n",
"Remember that we can create $U_s$ from $U_0$:\n",
"\n",
"$$ U_s = H^{\\otimes n} U_0 H^{\\otimes n} $$\n",
"\n",
"And a multi-controlled-Z gate ($MCZ$) inverts the phase of the state $|11\\dots 1\\rangle$:\n",
"\n",
"$$\n",
"MCZ = \n",
"\\begin{bmatrix}\n",
" 1 & 0 & 0 & \\cdots & 0 \\\\\n",
" 0 & 1 & 0 & \\cdots & 0 \\\\\n",
" \\vdots & \\vdots & \\vdots & \\ddots & \\vdots \\\\\n",
" 0 & 0 & 0 & \\cdots & -1 \\\\\n",
"\\end{bmatrix}\n",
"\\begin{aligned}\n",
"\\\\\n",
"\\\\\n",
"\\\\\n",
"\\leftarrow \\text{Add negative phase to} \\; |11\\dots 1\\rangle\\\\\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"Applying an X-gate to each qubit performs the transformation:\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
"|00\\dots 0\\rangle & \\rightarrow |11\\dots 1\\rangle\\\\\n",
"|11\\dots 1\\rangle & \\rightarrow |00\\dots 0\\rangle\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"So:\n",
"\n",
"$$ U_0 = - X^{\\otimes n} (MCZ) X^{\\otimes n} $$\n",
"\n",
"Using these properties together, we can create $U_s$ using H-gates, X-gates, and a single multi-controlled-Z gate:\n",
"\n",
"$$ U_s = - H^{\\otimes n} U_0 H^{\\otimes n} = H^{\\otimes n} X^{\\otimes n} (MCZ) X^{\\otimes n} H^{\\otimes n} $$\n",
" \n",
"Note that we can ignore the global phase of -1.\n",
"\n",
"

"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [],
"source": [
"def diffuser(nqubits):\n",
" qc = QuantumCircuit(nqubits)\n",
" # Apply transformation |s> -> |00..0> (H-gates)\n",
" for qubit in range(nqubits):\n",
" qc.h(qubit)\n",
" # Apply transformation |00..0> -> |11..1> (X-gates)\n",
" for qubit in range(nqubits):\n",
" qc.x(qubit)\n",
" # Do multi-controlled-Z gate\n",
" qc.h(nqubits-1)\n",
" qc.mct(list(range(nqubits-1)), nqubits-1) # multi-controlled-toffoli\n",
" qc.h(nqubits-1)\n",
" # Apply transformation |11..1> -> |00..0>\n",
" for qubit in range(nqubits):\n",
" qc.x(qubit)\n",
" # Apply transformation |00..0> -> |s>\n",
" for qubit in range(nqubits):\n",
" qc.h(qubit)\n",
" # We will return the diffuser as a gate\n",
" U_s = qc.to_gate()\n",
" U_s.name = \"U$_s$\"\n",
" return U_s"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We'll now put the pieces together, with the creation of a uniform superposition at the start of the circuit and a measurement at the end. Note that since there are 2 solutions and 8 possibilities, we will only need to run one iteration. "
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"n = 3\n",
"grover_circuit = QuantumCircuit(n)\n",
"grover_circuit = initialize_s(grover_circuit, [0,1,2])\n",
"grover_circuit.append(oracle_ex3, [0,1,2])\n",
"grover_circuit.append(diffuser(n), [0,1,2])\n",
"grover_circuit.measure_all()\n",
"grover_circuit.draw()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 3.1.1 Experiment with Simulators \n",
"\n",
"We can run the above circuit on the simulator. "
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"

"
]
},
"execution_count": 15,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"aer_sim = Aer.get_backend('aer_simulator')\n",
"transpiled_grover_circuit = transpile(grover_circuit, aer_sim)\n",
"qobj = assemble(transpiled_grover_circuit)\n",
"results = aer_sim.run(qobj).result()\n",
"counts = results.get_counts()\n",
"plot_histogram(counts)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As we can see, the algorithm discovers our marked states $\\lvert101\\rangle$ and $\\lvert110\\rangle$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 3.1.2 Experiment with Real Devices \n",
"\n",
"We can run the circuit on the real device as below."
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"tags": [
"uses-hardware"
]
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"least busy backend: ibmq_mumbai\n"
]
}
],
"source": [
"backend = least_busy(provider.backends(filters=lambda x: x.configuration().n_qubits >= 3 and \n",
" not x.configuration().simulator and x.status().operational==True))\n",
"print(\"least busy backend: \", backend)"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"tags": [
"uses-hardware"
]
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Job Status: job has successfully run\n"
]
}
],
"source": [
"# Run our circuit on the least busy backend. Monitor the execution of the job in the queue\n",
"from qiskit.tools.monitor import job_monitor\n",
"transpiled_grover_circuit = transpile(grover_circuit, device, optimization_level=3)\n",
"job = device.run(transpiled_grover_circuit)\n",
"job_monitor(job, interval=2)"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"tags": [
"uses-hardware"
]
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"

"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Get the results from the computation\n",
"results = job.result()\n",
"answer = results.get_counts(grover_circuit)\n",
"plot_histogram(answer)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As we can (hopefully) see, there is a higher chance of measuring $\\lvert101\\rangle$ and $\\lvert110\\rangle$. The other results are due to errors in the quantum computation. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 4. Problems \n",
"\n",
"The function `grover_problem_oracle` below takes a number of qubits (`n`), and a `variant` and returns an n-qubit oracle. The function will always return the same oracle for the same `n` and `variant`. You can see the solutions to each oracle by setting `print_solutions = True` when calling `grover_problem_oracle`."
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"

"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"from qiskit_textbook.problems import grover_problem_oracle\n",
"## Example Usage\n",
"n = 4\n",
"oracle = grover_problem_oracle(n, variant=1) # 0th variant of oracle, with n qubits\n",
"qc = QuantumCircuit(n)\n",
"qc.append(oracle, [0,1,2,3])\n",
"qc.draw()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"1. `grover_problem_oracle(4, variant=2)` uses 4 qubits and has 1 solution. \n",
" a. How many iterations do we need to have a > 90% chance of measuring this solution? \n",
" b. Use Grover's algorithm to find this solution state.\n",
" c. What happens if we apply more iterations the number we calculated in problem 1a above? Why?\n",
"\n",
"2. With 2 solutions and 4 qubits, how many iterations do we need for a >90% chance of measuring a solution? Test your answer using the oracle `grover_problem_oracle(4, variant=1)` (which has two solutions).\n",
"\n",
"3. Create a function, `grover_solver(oracle, iterations)` that takes as input:\n",
" - A Grover oracle as a gate (`oracle`)\n",
" - An integer number of iterations (`iterations`)\n",
" \n",
" and returns a `QuantumCircuit` that performs Grover's algorithm on the '`oracle`' gate, with '`iterations`' iterations."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 5. Solving Sudoku using Grover's Algorithm \n",
"\n",
"The oracles used throughout this chapter so far have been created with prior knowledge of their solutions. We will now solve a simple problem using Grover's algorithm, for which we do not necessarily know the solution beforehand. Our problem is a 2×2 binary sudoku, which in our case has two simple rules:\n",
"\n",
"- No column may contain the same value twice\n",
"- No row may contain the same value twice\n",
"\n",
"If we assign each square in our sudoku to a variable like so:\n",
"\n",
"![2×2 binary sudoku, with each square allocated to a different variable](images/binary_sudoku.png)\n",
"\n",
"we want our circuit to output a solution to this sudoku.\n",
"\n",
"Note that, while this approach of using Grover's algorithm to solve this problem is not practical (you can probably find the solution in your head!), the purpose of this example is to demonstrate the conversion of classical [decision problems](https://en.wikipedia.org/wiki/Decision_problem) into oracles for Grover's algorithm.\n",
"\n",
"### 5.1 Turning the Problem into a Circuit\n",
"\n",
"We want to create an oracle that will help us solve this problem, and we will start by creating a circuit that identifies a correct solution. Similar to how we created a classical adder using quantum circuits in [_The Atoms of Computation_](https://qiskit.org/textbook/ch-states/atoms-computation.html), we simply need to create a _classical_ function on a quantum circuit that checks whether the state of our variable bits is a valid solution.\n",
"\n",
"Since we need to check down both columns and across both rows, there are 4 conditions we need to check:\n",
"\n",
"```\n",
"v0 ≠ v1 # check along top row\n",
"v2 ≠ v3 # check along bottom row\n",
"v0 ≠ v2 # check down left column\n",
"v1 ≠ v3 # check down right column\n",
"```\n",
"\n",
"Remember we are comparing classical (computational basis) states. For convenience, we can compile this set of comparisons into a list of clauses:"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"tags": [
"thebelab-init"
]
},
"outputs": [],
"source": [
"clause_list = [[0,1],\n",
" [0,2],\n",
" [1,3],\n",
" [2,3]]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We will assign the value of each variable to a bit in our circuit. To check these clauses computationally, we will use the `XOR` gate (we came across this in the atoms of computation)."
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {
"tags": [
"thebelab-init"
]
},
"outputs": [],
"source": [
"def XOR(qc, a, b, output):\n",
" qc.cx(a, output)\n",
" qc.cx(b, output)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Convince yourself that the `output0` bit in the circuit below will only be flipped if `input0 ≠ input1`:"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"

"
]
},
"execution_count": 22,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# We will use separate registers to name the bits\n",
"in_qubits = QuantumRegister(2, name='input')\n",
"out_qubit = QuantumRegister(1, name='output')\n",
"qc = QuantumCircuit(in_qubits, out_qubit)\n",
"XOR(qc, in_qubits[0], in_qubits[1], out_qubit)\n",
"qc.draw()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This circuit checks whether `input0 == input1` and stores the output to `output0`. To check each clause, we repeat this circuit for each pairing in `clause_list` and store the output to a new bit:"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"

"
]
},
"execution_count": 23,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Create separate registers to name bits\n",
"var_qubits = QuantumRegister(4, name='v') # variable bits\n",
"clause_qubits = QuantumRegister(4, name='c') # bits to store clause-checks\n",
"\n",
"# Create quantum circuit\n",
"qc = QuantumCircuit(var_qubits, clause_qubits)\n",
"\n",
"# Use XOR gate to check each clause\n",
"i = 0\n",
"for clause in clause_list:\n",
" XOR(qc, clause[0], clause[1], clause_qubits[i])\n",
" i += 1\n",
"\n",
"qc.draw()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The final state of the bits `c0, c1, c2, c3` will only all be `1` in the case that the assignments of `v0, v1, v2, v3` are a solution to the sudoku. To complete our checking circuit, we want a single bit to be `1` if (and only if) all the clauses are satisfied, this way we can look at just one bit to see if our assignment is a solution. We can do this using a multi-controlled-Toffoli-gate:"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"

"
]
},
"execution_count": 24,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Create separate registers to name bits\n",
"var_qubits = QuantumRegister(4, name='v')\n",
"clause_qubits = QuantumRegister(4, name='c')\n",
"output_qubit = QuantumRegister(1, name='out')\n",
"qc = QuantumCircuit(var_qubits, clause_qubits, output_qubit)\n",
"\n",
"# Compute clauses\n",
"i = 0\n",
"for clause in clause_list:\n",
" XOR(qc, clause[0], clause[1], clause_qubits[i])\n",
" i += 1\n",
"\n",
"# Flip 'output' bit if all clauses are satisfied\n",
"qc.mct(clause_qubits, output_qubit)\n",
"\n",
"qc.draw()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The circuit above takes as input an initial assignment of the bits `v0`, `v1`, `v2` and `v3`, and all other bits should be initialized to `0`. After running the circuit, the state of the `out0` bit tells us if this assignment is a solution or not; `out0 = 0` means the assignment _is not_ a solution, and `out0 = 1` means the assignment _is_ a solution.\n",
"\n",
"**Important:** Before you continue, it is important you fully understand this circuit and are convinced it works as stated in the paragraph above.\n",
"\n",
"### 5.2 Uncomputing, and Completing the Oracle\n",
"\n",
"We can now turn this checking circuit into a Grover oracle using [phase kickback](https://qiskit.org/textbook/ch-gates/phase-kickback.html). To recap, we have 3 registers: \n",
"- One register which stores our sudoku variables (we'll say $x = v_3, v_2, v_1, v_0$)\n",
"- One register that stores our clauses (this starts in the state $|0000\\rangle$ which we'll abbreviate to $|0\\rangle$)\n",
"- And one qubit ($|\\text{out}_0\\rangle$) that we've been using to store the output of our checking circuit. \n",
"\n",
"To create an oracle, we need our circuit ($U_\\omega$) to perform the transformation:\n",
"\n",
"$$\n",
"U_\\omega|x\\rangle|0\\rangle|\\text{out}_0\\rangle = |x\\rangle|0\\rangle|\\text{out}_0\\oplus f(x)\\rangle\n",
"$$\n",
"\n",
"If we set the `out0` qubit to the superposition state $|{-}\\rangle$ we have:\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
"U_\\omega|x\\rangle|0\\rangle|{-}\\rangle \n",
"&= U_\\omega|x\\rangle|0\\rangle\\otimes\\tfrac{1}{\\sqrt{2}}(|0\\rangle - |1\\rangle)\\\\\n",
"&= |x\\rangle|0\\rangle\\otimes\\tfrac{1}{\\sqrt{2}}(|0\\oplus f(x)\\rangle - |1\\oplus f(x)\\rangle)\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"If $f(x) = 0$, then we have the state:\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
"&= |x\\rangle|0\\rangle\\otimes \\tfrac{1}{\\sqrt{2}}(|0\\rangle - |1\\rangle)\\\\\n",
"&= |x\\rangle|0\\rangle|-\\rangle\\\\\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"\n",
"(i.e. no change). But if $f(x) = 1$ (i.e. $x = \\omega$), we introduce a negative phase to the $|{-}\\rangle$ qubit:\n",
"\n",
"$$\n",
"\\begin{aligned}\n",
"&= \\phantom{-}|x\\rangle|0\\rangle\\otimes\\tfrac{1}{\\sqrt{2}}(|1\\rangle - |0\\rangle)\\\\\n",
"&= \\phantom{-}|x\\rangle|0\\rangle\\otimes -\\tfrac{1}{\\sqrt{2}}(|0\\rangle - |1\\rangle)\\\\\n",
"&= -|x\\rangle|0\\rangle|-\\rangle\\\\\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"This is a functioning oracle that uses two auxiliary registers in the state $|0\\rangle|{-}\\rangle$:\n",
"\n",
"$$\n",
"U_\\omega|x\\rangle|0\\rangle|{-}\\rangle = \\Bigg\\{\n",
"\\begin{aligned}\n",
"\\phantom{-}|x\\rangle|0\\rangle|-\\rangle \\quad \\text{for} \\; x \\neq \\omega \\\\\n",
"-|x\\rangle|0\\rangle|-\\rangle \\quad \\text{for} \\; x = \\omega \\\\\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"To adapt our checking circuit into a Grover oracle, we need to guarantee the bits in the second register (`c`) are always returned to the state $|0000\\rangle$ after the computation. To do this, we simply repeat the part of the circuit that computes the clauses which guarantees `c0 = c1 = c2 = c3 = 0` after our circuit has run. We call this step _'uncomputation'_."
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"

"
]
},
"execution_count": 25,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"var_qubits = QuantumRegister(4, name='v')\n",
"clause_qubits = QuantumRegister(4, name='c')\n",
"output_qubit = QuantumRegister(1, name='out')\n",
"cbits = ClassicalRegister(4, name='cbits')\n",
"qc = QuantumCircuit(var_qubits, clause_qubits, output_qubit, cbits)\n",
"\n",
"def sudoku_oracle(qc, clause_list, clause_qubits):\n",
" # Compute clauses\n",
" i = 0\n",
" for clause in clause_list:\n",
" XOR(qc, clause[0], clause[1], clause_qubits[i])\n",
" i += 1\n",
"\n",
" # Flip 'output' bit if all clauses are satisfied\n",
" qc.mct(clause_qubits, output_qubit)\n",
"\n",
" # Uncompute clauses to reset clause-checking bits to 0\n",
" i = 0\n",
" for clause in clause_list:\n",
" XOR(qc, clause[0], clause[1], clause_qubits[i])\n",
" i += 1\n",
"\n",
"sudoku_oracle(qc, clause_list, clause_qubits)\n",
"qc.draw()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In summary, the circuit above performs:\n",
"\n",
"$$\n",
"U_\\omega|x\\rangle|0\\rangle|\\text{out}_0\\rangle = \\Bigg\\{\n",
"\\begin{aligned}\n",
"|x\\rangle|0\\rangle|\\text{out}_0\\rangle \\quad \\text{for} \\; x \\neq \\omega \\\\\n",
"|x\\rangle|0\\rangle\\otimes X|\\text{out}_0\\rangle \\quad \\text{for} \\; x = \\omega \\\\\n",
"\\end{aligned}\n",
"$$\n",
"\n",
"and if the initial state of $|\\text{out}_0\\rangle = |{-}\\rangle$,:\n",
"\n",
"$$\n",
"U_\\omega|x\\rangle|0\\rangle|{-}\\rangle = \\Bigg\\{\n",
"\\begin{aligned}\n",
"\\phantom{-}|x\\rangle|0\\rangle|-\\rangle \\quad \\text{for} \\; x \\neq \\omega \\\\\n",
"-|x\\rangle|0\\rangle|-\\rangle \\quad \\text{for} \\; x = \\omega \\\\\n",
"\\end{aligned}\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 5.3 The Full Algorithm\n",
"\n",
"All that's left to do now is to put this oracle into Grover's algorithm!"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"

"
]
},
"execution_count": 26,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"var_qubits = QuantumRegister(4, name='v')\n",
"clause_qubits = QuantumRegister(4, name='c')\n",
"output_qubit = QuantumRegister(1, name='out')\n",
"cbits = ClassicalRegister(4, name='cbits')\n",
"qc = QuantumCircuit(var_qubits, clause_qubits, output_qubit, cbits)\n",
"\n",
"# Initialize 'out0' in state |->\n",
"qc.initialize([1, -1]/np.sqrt(2), output_qubit)\n",
"\n",
"# Initialize qubits in state |s>\n",
"qc.h(var_qubits)\n",
"qc.barrier() # for visual separation\n",
"\n",
"## First Iteration\n",
"# Apply our oracle\n",
"sudoku_oracle(qc, clause_list, clause_qubits)\n",
"qc.barrier() # for visual separation\n",
"# Apply our diffuser\n",
"qc.append(diffuser(4), [0,1,2,3])\n",
"\n",
"## Second Iteration\n",
"sudoku_oracle(qc, clause_list, clause_qubits)\n",
"qc.barrier() # for visual separation\n",
"# Apply our diffuser\n",
"qc.append(diffuser(4), [0,1,2,3])\n",
"\n",
"# Measure the variable qubits\n",
"qc.measure(var_qubits, cbits)\n",
"\n",
"qc.draw(fold=-1)"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {
"scrolled": false
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
"

"
]
},
"execution_count": 27,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Simulate and plot results\n",
"aer_simulator = Aer.get_backend('aer_simulator')\n",
"transpiled_qc = transpile(qc, aer_simulator)\n",
"qobj = assemble(transpiled_qc)\n",
"result = aer_sim.run(qobj).result()\n",
"plot_histogram(result.get_counts())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"There are two bit strings with a much higher probability of measurement than any of the others, `0110` and `1001`. These correspond to the assignments:\n",
"```\n",
"v0 = 0\n",
"v1 = 1\n",
"v2 = 1\n",
"v3 = 0\n",
"```\n",
"and\n",
"```\n",
"v0 = 1\n",
"v1 = 0\n",
"v2 = 0\n",
"v3 = 1\n",
"```\n",
"which are the two solutions to our sudoku! The aim of this section is to show how we can create Grover oracles from real problems. While this specific problem is trivial, the process can be applied (allowing large enough circuits) to any decision problem. To recap, the steps are:\n",
"\n",
"1. Create a reversible classical circuit that identifies a correct solution\n",
"2. Use phase kickback and uncomputation to turn this circuit into an oracle\n",
"3. Use Grover's algorithm to solve this oracle"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 6. References \n",
"\n",
"1. L. K. Grover (1996), \"A fast quantum mechanical algorithm for database search\", Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (STOC 1996), [doi:10.1145/237814.237866](http://doi.acm.org/10.1145/237814.237866), [arXiv:quant-ph/9605043](https://arxiv.org/abs/quant-ph/9605043)\n",
"2. C. Figgatt, D. Maslov, K. A. Landsman, N. M. Linke, S. Debnath & C. Monroe (2017), \"Complete 3-Qubit Grover search on a programmable quantum computer\", Nature Communications, Vol 8, Art 1918, [doi:10.1038/s41467-017-01904-7](https://doi.org/10.1038/s41467-017-01904-7), [arXiv:1703.10535 ](https://arxiv.org/abs/1703.10535)\n",
"3. I. Chuang & M. Nielsen, \"Quantum Computation and Quantum Information\", Cambridge: Cambridge University Press, 2000."
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"### Version Information

"
],
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"import qiskit.tools.jupyter\n",
"%qiskit_version_table"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.7"
}
},
"nbformat": 4,
"nbformat_minor": 2
}

Qiskit Software | Version |
---|---|

Qiskit | 0.27.0 |

Terra | 0.17.4 |

Aer | 0.8.2 |

Ignis | 0.6.0 |

Aqua | 0.9.2 |

IBM Q Provider | 0.14.0 |

System information | |

Python | 3.7.7 (default, May 6 2020, 04:59:01) \n", "[Clang 4.0.1 (tags/RELEASE_401/final)] |

OS | Darwin |

CPUs | 8 |

Memory (Gb) | 32.0 |

Wed Jun 16 13:45:01 2021 BST |