The latest version of this notebook is available on https://github.com/qiskit/qiskit-tutorial.
Giacomo Nannicini and Rudy Raymond (based on this paper)
Grover search is one of the most popular algorithms used for searching a solution among many possible candidates using Quantum Computers. If there are $N$ possible solutions among which there is exactly one solution (that can be verified by some function evaluation), then Grover search can be used to find the solution with $O(\sqrt{N})$ function evaluations. This is in contrast to classical computers that require $\Omega(N)$ function evaluations: the Grover search is a quantum algorithm that provably can be used search the correct solutions quadratically faster than its classical counterparts.
Here, we are going to illustrate the use of Grover search to solve a combinatorial problem called Exactly-1 3-SAT problem. The Exactly-1 3-SAT problem is a NP-complete problem, namely, it is one of the most difficult problems that are interconnected (meaning that if we solve any one of them, we essentially can solve all of them). Unfortunately, there are many natural problems that are NP-complete, such as, the Traveling Salesman Problem (TSP), the Maximum Cut (MaxCut) and so on. Up to now, there is no classical and quantum algorithm that can efficiently solve such NP-hard problems.
We begin with an example of the Exactly-1 3-SAT problem. Then, we show how to design an evaluation function which is also known as the oracle (or, blackbox) which is essential to Grover search. Finally, we show the circuit of Grover search using the oracle and present their results on simulator and real-device backends.
The Exactly-1 3-SAT problem is best explained with the following concrete problem. Let us consider a Boolean function $f$ with three Boolean variables $x_1, x_2, x_3$ as below.
$$ f(x_1, x_2, x_3) = (x_1 \vee x_2 \vee \neg x_3) \wedge (\neg x_1 \vee \neg x_2 \vee \neg x_3) \wedge (\neg x_1 \vee x_2 \vee x_3) $$In the above function, the terms on the right-hand side equation which are inside $()$ are called clauses. Each clause has exactly three literals. Namely, the first clause has $x_1$, $x_2$ and $\neg x_3$ as its literals. The symbol $\neg$ is the Boolean NOT that negates (or, flips) the value of its succeeding literal. The symbols $\vee$ and $\wedge$ are, respectively, the Boolean OR and AND. The Boolean $f$ is satisfiable if there is an assignment of $x_1, x_2, x_3$ that evaluates to $f(x_1, x_2, x_3) = 1$ (or, $f$ evaluates to True). The Exactly-1 3-SAT problem requires us to find an assignment such that $f = 1$ (or, True) and there is exactly one literal that evaluates to True in every clause of $f$.
A naive way to find such an assignment is by trying every possible combinations of input values of $f$. Below is the table obtained from trying all possible combinations of $x_1, x_2, x_3$. For ease of explanation, we interchangably use $0$ and False, as well as $1$ and True.
| $x_1$ | $x_2$ | $x_3$ | $f$ | Comment |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | Not a solution because there are three True literals in the second clause |
| 0 | 0 | 1 | 0 | Not a solution because $f$ is False |
| 0 | 1 | 0 | 1 | Not a solution because there are two True literals in the first clause |
| 0 | 1 | 1 | 1 | Not a solution because there are three True literals in the third clause |
| 1 | 0 | 0 | 0 | Not a solution because $f$ is False |
| 1 | 0 | 1 | 1 | Solution. BINGO!! |
| 1 | 1 | 0 | 1 | Not a soluton because there are three True literals in the first clause |
| 1 | 1 | 1 | 0 | Not a solution because $f$ is False |
From the table above, we can see that the assignment $x_1x_2x_3 = 101$ is the solution fo the Exactly-1 3-SAT problem to $f$. In general, the Boolean function $f$ can have many clauses and more Boolean variables.
Here, we describe a method to construct a circuit to check the assignment of Exactly-1 3-SAT problem. The circuit can then be used as a blackbox (or, oracle) in Grover search. To design the blackbox, we do not need to know the solution to the problem in advance: it suffices to design a blackbox that checks if the assignment results in $f$ evaluates to True or False. It turns out that we can design such a blackbox efficiently (in fact, any NP-complete problem has the property that although finding the solution is difficult, checking the solution is easy).
For each clause of $f$, we design a sub-circuit that outputs True if and only if there is exactly one True literal in the clause. Combining all sub-circuits for all clauses, we can then obtain the blackbox that outputs True if and only if all clauses are satisfied with exactly one True literal each.
For example, let us consider the clause $(x_1 \vee \neg x_2 \vee x_3)$. It is easy to see that $y$ defined as
$$ y = x_1 \oplus \neg x_2 \oplus x_3 \oplus ( x_1 \wedge \neg x_2 \wedge x_3), $$import matplotlib.pyplot as plt %matplotlib inline import numpy as npis True if and only if exactly one of $x_1$, $\neg x_2$, and $x_3$ is True. Using two working qubits, $y$ can be computed by the following sub-circuit. Below, $x_1x_2x_3$ is renamed as $q_1q_2q_3$, $q_4$ is used as a working qubit, and $q_5$ is used to store the value of $y$.
In [1]:
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
# importing Qiskit
from qiskit import Aer, IBMQ
from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister
from qiskit import available_backends, execute, register, get_backend, compile
from qiskit.tools import visualization
from qiskit.tools.visualization import circuit_drawer
In [2]:
q = QuantumRegister(6)
qc = QuantumCircuit(q)
qc.x(q[2])
qc.cx(q[1], q[5])
qc.cx(q[2], q[5])
qc.cx(q[3], q[5])
qc.ccx(q[1], q[2], q[4])
qc.ccx(q[3], q[4], q[5])
qc.ccx(q[1], q[2], q[4])
qc.x(q[2])
circuit_drawer(qc)
Out[2]:
In the sub-circuit above, the three ccx gates on the right are used to compute $( q_1 \wedge \neg q_2 \wedge q_3)$ and write the result to $q_5$, while the three cx gates on the left are used to compute $q_1 \oplus \neg q_2 \oplus q_3$ and write the result to $q_5$. Notice that the right-most ccx gate is used to reset the value of $q_4$ so that it can be reused in the succeeding sub-circuits.
From the above sub-circuit, we can define a blackbox function to check the solution of the Exactly-1 3-SAT problem as follows.
In [3]:
def black_box_u_f(circuit, f_in, f_out, aux, n, exactly_1_3_sat_formula):
"""Circuit that computes the black-box function from f_in to f_out.
Create a circuit that verifies whether a given exactly-1 3-SAT
formula is satisfied by the input. The exactly-1 version
requires exactly one literal out of every clause to be satisfied.
"""
num_clauses = len(exactly_1_3_sat_formula)
for (k, clause) in enumerate(exactly_1_3_sat_formula):
# This loop ensures aux[k] is 1 if an odd number of literals
# are true
for literal in clause:
if literal > 0:
circuit.cx(f_in[literal-1], aux[k])
else:
circuit.x(f_in[-literal-1])
circuit.cx(f_in[-literal-1], aux[k])
# Flip aux[k] if all literals are true, using auxiliary qubit
# (ancilla) aux[num_clauses]
circuit.ccx(f_in[0], f_in[1], aux[num_clauses])
circuit.ccx(f_in[2], aux[num_clauses], aux[k])
# Flip back to reverse state of negative literals and ancilla
circuit.ccx(f_in[0], f_in[1], aux[num_clauses])
for literal in clause:
if literal < 0:
circuit.x(f_in[-literal-1])
# The formula is satisfied if and only if all auxiliary qubits
# except aux[num_clauses] are 1
if (num_clauses == 1):
circuit.cx(aux[0], f_out[0])
elif (num_clauses == 2):
circuit.ccx(aux[0], aux[1], f_out[0])
elif (num_clauses == 3):
circuit.ccx(aux[0], aux[1], aux[num_clauses])
circuit.ccx(aux[2], aux[num_clauses], f_out[0])
circuit.ccx(aux[0], aux[1], aux[num_clauses])
else:
raise ValueError('We only allow at most 3 clauses')
# Flip back any auxiliary qubits to make sure state is consistent
# for future executions of this routine; same loop as above.
for (k, clause) in enumerate(exactly_1_3_sat_formula):
for literal in clause:
if literal > 0:
circuit.cx(f_in[literal-1], aux[k])
else:
circuit.x(f_in[-literal-1])
circuit.cx(f_in[-literal-1], aux[k])
circuit.ccx(f_in[0], f_in[1], aux[num_clauses])
circuit.ccx(f_in[2], aux[num_clauses], aux[k])
circuit.ccx(f_in[0], f_in[1], aux[num_clauses])
for literal in clause:
if literal < 0:
circuit.x(f_in[-literal-1])
# -- end function
Another important procedure in Grover search is to have an operation that perfom the inversion-about-the-average step, namely, it performs the following transformation:
$$ \sum_{j=0}^{2^{n}-1} \alpha_j |j\rangle \rightarrow \sum_{j=0}^{2^{n}-1}\left(2 \left( \sum_{k=0}^{k=2^{n}-1} \frac{\alpha_k}{2^n} \right) - \alpha_j \right) |j\rangle $$The above transformation can be used to amplify the probability amplitude $\alpha_s$ when s is the solution and $\alpha_s$ is negative (and small), while $\alpha_j$ for $j \neq s$ is positive. Roughly speaking, the value of $\alpha_s$ increases by twice the average of the amplitudes, while others are reduced. The inversion-about-the-average can be realized with the sequence of unitary matrices as below:
$$ H^{\otimes n} \left(2|0\rangle \langle 0 | - I \right) H^{\otimes n} $$The first and last $H$ are just Hadamard gates applied to each qubit. The operation in the middle requires us to design a sub-circuit that flips the probability amplitude of the component of the quantum state corresponding to the all-zero binary string. The sub-circuit can be realized by the following function, which is a multi-qubit controlled-Z which flips the probability amplitude of the component of the quantum state corresponding to the all-one binary string. Applying X gates to all qubits before and after the function realizes the sub-circuit.
In [4]:
def n_controlled_Z(circuit, controls, target):
"""Implement a Z gate with multiple controls"""
if (len(controls) > 2):
raise ValueError('The controlled Z with more than 2 ' +
'controls is not implemented')
elif (len(controls) == 1):
circuit.h(target)
circuit.cx(controls[0], target)
circuit.h(target)
elif (len(controls) == 2):
circuit.h(target)
circuit.ccx(controls[0], controls[1], target)
circuit.h(target)
# -- end function
Finally, the inversion-about-the-average circuit can be realized by the following function:
In [5]:
def inversion_about_average(circuit, f_in, n):
"""Apply inversion about the average step of Grover's algorithm."""
# Hadamards everywhere
for j in range(n):
circuit.h(f_in[j])
# D matrix: flips the sign of the state |000> only
for j in range(n):
circuit.x(f_in[j])
n_controlled_Z(circuit, [f_in[j] for j in range(n-1)], f_in[n-1])
for j in range(n):
circuit.x(f_in[j])
# Hadamards everywhere again
for j in range(n):
circuit.h(f_in[j])
# -- end function
Here is a circuit of the inversion about the average on three qubits.
In [6]:
qr = QuantumRegister(3)
qInvAvg = QuantumCircuit(qr)
inversion_about_average(qInvAvg, qr, 3)
circuit_drawer(qInvAvg)
Out[6]:
The complete steps of Grover search is as follow.
Repeat for $T$ times:
Apply the blackbox function
Apply the inversion-about-the-average function
Measure to obtain the solution
The code for the above steps is as below:
In [7]:
"""
Grover search implemented in Qiskit.
This module contains the code necessary to run Grover search on 3
qubits, both with a simulator and with a real quantum computing
device. This code is the companion for the paper
"An introduction to quantum computing, without the physics",
Giacomo Nannicini, https://arxiv.org/abs/1708.03684.
"""
def input_state(circuit, f_in, f_out, n):
"""(n+1)-qubit input state for Grover search."""
for j in range(n):
circuit.h(f_in[j])
circuit.x(f_out)
circuit.h(f_out)
# -- end function
# Make a quantum program for the n-bit Grover search.
n = 3
# Exactly-1 3-SAT formula to be satisfied, in conjunctive
# normal form. We represent literals with integers, positive or
# negative, to indicate a Boolean variable or its negation.
exactly_1_3_sat_formula = [[1, 2, -3], [-1, -2, -3], [-1, 2, 3]]
# Define three quantum registers: 'f_in' is the search space (input
# to the function f), 'f_out' is bit used for the output of function
# f, aux are the auxiliary bits used by f to perform its
# computation.
f_in = QuantumRegister(n)
f_out = QuantumRegister(1)
aux = QuantumRegister(len(exactly_1_3_sat_formula) + 1)
# Define classical register for algorithm result
ans = ClassicalRegister(n)
# Define quantum circuit with above registers
grover = QuantumCircuit()
grover.add(f_in)
grover.add(f_out)
grover.add(aux)
grover.add(ans)
input_state(grover, f_in, f_out, n)
T = 2
for t in range(T):
# Apply T full iterations
black_box_u_f(grover, f_in, f_out, aux, n, exactly_1_3_sat_formula)
inversion_about_average(grover, f_in, n)
# Measure the output register in the computational basis
for j in range(n):
grover.measure(f_in[j], ans[j])
# Execute circuit
backend = Aer.get_backend('qasm_simulator')
job = execute([grover], backend=backend, shots=1000)
result = job.result()
# Get counts and plot histogram
counts = result.get_counts(grover)
visualization.plot_histogram(counts)
We have seen that the simulator can find the solution to the combinatorial problem. We would like to see what happens if we use the real quantum devices that have noise and imperfect gates.
However, due to the restriction on the length of strings that can be sent over the network to the real devices (there are more than sixty thousands charactes of QASM of the circuit), at the moment the above circuit cannot be run on real-device backends. We can see the compiled QASM on real-device ibmqx5 backend as follows.
In [8]:
IBMQ.load_accounts()
In [10]:
# get ibmq_16_rueschlikon configuration and coupling map
backend = IBMQ.get_backend('ibmq_16_melbourne')
backend_config = backend.configuration()
backend_coupling = backend_config['coupling_map']
# compile the circuit for ibmq_16_rueschlikon
grover_compiled = compile(grover, backend=backend, coupling_map=backend_coupling, seed=1)
grover_compiled_qasm = grover_compiled.experiments[0].header.compiled_circuit_qasm
print("Number of gates for", backend.name(), "is", len(grover_compiled_qasm.split("\n")) - 4)
The number of gates is in the order of thousands which is above the limits of decoherence time of the current near-term quantum computers. It is a challenge to design a quantum circuit for Grover search to solve large optimization problems.
In addition to using too many gates, the circuit in this notebook uses auxiliary qubits. It is left as future work to improve the efficiency of the circuit as to make it possible to run it in the real devices. Below is the original circuit.
In [11]:
circuit_drawer(grover)
Out[11]:
[1] "A fast quantum mechanical algorithm for database search", L. K. Grover, Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (STOC 1996)
[2] "Tight bounds on quantum searching", Boyer et al., Fortsch.Phys.46:493-506,1998