Grover’s Algorithm
Contents
Grover’s Algorithm¶
Grover’s Algorithm is a quantum algorithm for unsorted search. Given a circuit that can detect the target element, Grover’s Algorithm searches all possible binary inputs to find the target.
Unsorted Search¶
The Unsorted Search problem takes two inputs and returns one output.
Input 1: A one input function that returns true or false.
Input 2: A fixed size for the input in binary.
Output: A binary value that will cause the function to return True.
A simple version of this problem is “Guess the number”. What 8 bit binary value will cause the following function to return true.
def find(x):
return (x-5==0)
There is only one value that will make this return true. That value is \(5\) which is 0000 0101 as an 8-bit binary number.
The worst case situation is to enumerate and try all possible combinations. Number of Bits is \(n\). Number of possible inputs is \(2^n\). The worse case is to try all \(2^n\) problems. For an 8-bit answer this means trying 256 different combinations. If the input was a 128-bit integer, then we would have \(2^{128}=340,282,366,920,938,463,463,374,607,431,768,211,456\) possible cases to check.
A SAT Solver is a practical application of the unsorted search problems. The SAT Solver Problem is to “find the setting of boolean variable to make a logical expression true.”
Input: A Boolean Expression in \(n\) variables
Output: A setting of the variables that make the expression true
SAT Solvers are in a class of problem called NP-Complete. As far as we know, a classical computer can only solve this problems in worst case \(O(2^n)\). If SAT could be solved faster every NP-Complete problem can be solved faster.
There are many NP-Complete problems that are of interest to computer scientists.
Knapsack Problem: Give a set of things with weights and benefits, how can you minimize the benefit within a weight limit.
Traveling Salesmen Problem: What is the optimal path to visit and set of cities and end at the starting point.
Exam Scheduling: Given a collection of students and exams, schedule them such that no student has to take two exams at once.
Minesweeper: Find all the bombs on a mindsweeper board
Super Mario: Get Mario to the end of any level.
Since SAT Solvers can solve all of these problems, they are big business. SAT Competitions are held every year to determine the fastest SAT Solver. Making the fastest SAT solver is a big advance that will be used by many businesses. All these programs are just trying to decrease the time to search all \(2^n\). They will search all \(2^n\) possibilities in the worst case, they are just trying to do it as fast as possible.
To the best of our knowledge, It is impossible to solve the SAT problem on a general computer in less then \(O(2^n)\). A classical computer must try all possibilities in the worst case.
Grover’s Algorithm can solve unsorted search in \(O(\sqrt{2^n})\). This is a huge improvement over any algorithm that can be written on a classic computer.
Simple Question Circuit¶
To use Grover’s Algorithm, we need a classic logic circuit defined as a quantum circuit. We will use the example from above as our simple circuit.
def find(x):
return (x-3==0)
We will search 3-bit numbers. That means there are a total of \(2^3=8\) possible results. Not many to search, but enough to give us a good example.
We need a quantum circuit that finds the number 3. If the input matches the target, we will apply an X-gate to the result qubit. If the input does not match the target, we will not apply the X-get.
We have a three bit number, that means we need 4 qubits. Three for the inputs and one for the result.
We need to build a three qubit conjunction. This will require a working bit. Now we are up to 4 qubits. We compute \(q_0 \wedge q_1\) on \(q_5\). Then we compute \(q_5 \wedge q_3\) on \(q_4\) This puts \(q_4=(q_0 \wedge q_1) \wedge q_3)\). We need to clear the working qubit after using it.
The code for the 3-qubit conjunction is shown below.
#Three Qubit AND
qc.ccx(0,1,4)
qc.ccx(2,4,3)
qc.ccx(0,1,4)
#End Three QUBIT AND
To test that is works, we apply the H Gate to all three inputs. This way we can test that is works correctly.
The result of our experiment is shown below.
{
'0100': 242,
'0010': 281,
'0000': 260,
'1111': 263,
'0101': 238,
'0110': 276,
'0011': 269,
'0001': 219
}
We can write this as a truth table.
\(q_0\) |
\(q_1\) |
\(q_2\) |
\(q_3=(q_0 \wedge q_1 \wedge q_2)\) |
Count |
|---|---|---|---|---|
0 |
0 |
0 |
0 |
260 |
0 |
0 |
1 |
0 |
242 |
0 |
1 |
0 |
0 |
281 |
0 |
1 |
1 |
0 |
276 |
1 |
0 |
0 |
0 |
219 |
1 |
0 |
1 |
0 |
238 |
1 |
1 |
0 |
0 |
269 |
1 |
1 |
1 |
1 |
263 |
This result qubit was only equal to 1 when the three input bits were equal to one.
We can use this ciruit to create a function that matches any number. For example, it we want to match 3, in binary that is 011. We need to pick and order for our qubits.
\(q_2\) |
\(q_1\) |
\(q_0\) |
|---|---|---|
\(2^2\) bit |
\(2^1\) bit |
\(2^0\) bit |
Once we decide on this, we can make 011 because we need \(q_2=0\), \(q_1=1\), \(q_0=1\). We just need to apply an X gate to \(q_2\). We also need to undo the X gate so we can use that qubits original value again later.
The python code to return true on 3 is given below.
#Start of Number Selection
#Set Bits we need to be 0
qc.x(2)
#Three Qubit AND
qc.ccx(0,1,4)
qc.ccx(2,4,3)
qc.ccx(0,1,4)
#End Three QUBIT AND
#undo bit set
qc.x(2)
#End of Number Selection
The circuit is shown. Again we apply H gates to all inputs to get a quick test that the circuit works.
The results are shown below.
{
'0111': 242,
'0010': 268,
'1011': 251,
'0110': 267,
'0100': 266,
'0000': 238,
'0001': 267,
'0101': 249
}
The important thing about these results is which have \(q_4=0\). Those are the values with the target we want to fine. There is only one value that starts with 1, it is '1011': 251. The input qubits are set to 011, which is our target 3!
This is a toy example. We made a circuit we can exactly predict the answer to. This would be a dumb search, but it is a great test. In reality, we would have a logical expression we did not know the answer to.
Grover’s Algorithm¶
To run Grover’s Algorithm, we need a search circuit. Specifically, we need a circuit that has \(x\) input qubits, \(1\) output qubit, and \(y\) working qubits. The circuit must make the following guarantees:
The inputs qubits are not changes by the search circuit.
The output qubit has the X Gate applied if and only if the target is found.
The working qubits are set to \(\left| 0 \right>\) at the beginning and end of the circuit. (We undo any changes we make.)
We already have a search circuit that matches these requirements built. We have a search circuit that targets the number 3.
We can wrap our circuit in two barriers. This will make it easier to distinguish as part of the full circuit.
#Start of Search Circuit
qc.barrier(range(0,5))
#Start of Number Selection
#Set Bits we need to be 0
qc.x(2)
#Three Qubit AND
qc.ccx(0,1,4)
qc.ccx(2,4,3)
qc.ccx(0,1,4)
#End Three QUBIT AND
#undo bit set
qc.x(2)
#End of Number Selection
qc.barrier(range(0,5))
#End of Search Circuit
The circuit generated is shown below.
We can know apply Grover’s Algorithm to our circuit. The first step to Grover’s Algorithm is to apply an X Gate to the result bit. In our case this is \(q_3\). We then apply the Hadamard Gate to all our input gates and our output gates. This puts the circuit in a superposition were all possible input values are represented with equal probability.
The following code is placed before the search circuit.
#Prepare for Grover
#1.) Apply X to result
qc.x(3)
#2.) Apply H to input qubits
qc.h(0)
qc.h(1)
qc.h(2)
#3.) Apply H to result qubit
qc.h(3)
#Start of Search Circuit
The circuit is now initialized.
After the search circuit execute, we apply a collection of gates called a Grover Diffuser.
#Start of Diffuser
qc.h(0)
qc.h(1)
qc.h(2)
qc.x(0)
qc.x(1)
qc.x(2)
#3 bit controlled Z
qc.ccx(0,1,4)
qc.cz(4,2)
qc.ccx(0,1,4)
#end 3-bit controlled Z
qc.x(0)
qc.x(1)
qc.x(2)
qc.h(0)
qc.h(1)
qc.h(2)
#End of Diffuser
The diffuser is shown alone below.
This circuit is getting pretty big. We can simplify our coding by breaking it into functions. We put the diffuser after the search circuit.
#Mark Boady - 2021
#Import the Libraries
from qiskit import *
#For simulations:
from qiskit import BasicAer
#Search for 3
def search(circuit):
#Start of Search Circuit
circuit.barrier(range(0,5))
#Start of Number Selection
#Set Bits we need to be 0
circuit.x(2)
#Three Qubit AND
circuit.ccx(0,1,4)
circuit.ccx(2,4,3)
circuit.ccx(0,1,4)
#End Three QUBIT AND
#undo bit set
circuit.x(2)
#End of Number Selection
circuit.barrier(range(0,5))
#End of Search Circuit
#Grover Setup
def setup(circuit):
#Prepare for Grover
#1.) Apply X to result
circuit.x(3)
#2.) Apply H to input qubits
circuit.h(0)
circuit.h(1)
circuit.h(2)
#3.) Apply H to result qubit
circuit.h(3)
#Diffuser
def diffuser(circuit):
#Start of Diffuser
circuit.h(0)
circuit.h(1)
circuit.h(2)
circuit.x(0)
circuit.x(1)
circuit.x(2)
#3 bit controlled Z
circuit.ccx(0,1,4)
circuit.cz(4,2)
circuit.ccx(0,1,4)
#end 3-bit controlled Z
circuit.x(0)
circuit.x(1)
circuit.x(2)
circuit.h(0)
circuit.h(1)
circuit.h(2)
#End of Diffuser
#Make a Circuit
qc = QuantumCircuit(5,4)
setup(qc)
search(qc)
diffuser(qc)
#Measure out results
qc.barrier(range(0,5))
qc.measure(0,0)
qc.measure(1,1)
qc.measure(2,2)
qc.measure(3,3)
#Matplot to make an image
qc.draw(output="mpl",filename="groverP2.png")
#Run our simulation!
#Create Simulator
backend_sim = BasicAer.get_backend('qasm_simulator')
#Run 2,048 tests
job_sim = execute(qc,backend_sim,shots=2048)
#Get the results
result_sim = job_sim.result()
#Show the count of each outcome
counts = result_sim.get_counts()
print(counts)
The circuit is shown below.
The results of this circuit are shown below.
{
'1011': 798,
'0011': 820,
'0111': 36,
'1110': 27,
'0000': 21,
'0010': 36,
'1100': 30,
'1101': 37,
'0101': 24,
'0100': 38,
'1010': 25,
'0110': 37,
'1001': 25,
'0001': 28,
'1000': 38,
'1111': 28
}
There are many different results here, but one stands out. There are 798 results that gave us 1011 and 820 give us 0011. Looking at just the last three bits, there are 1618 results that give us 011.
This brings us to the last two steps of Grover’s algorithm. We need to apply the search and diffuser repeatedly. Then we only measure the input bits. The number of times we need to apply the diffuser and search circuit is \( n \le \left \lceil \frac{\pi}{4} \sqrt{2^x} \right \rceil\).
We have a 3 qubit input which means \(\frac{\pi}{4} \sqrt{2^3}= 2.22\) applications of the diffuser.
We just need to add a loop to our functions.
#Make a Circuit
qc = QuantumCircuit(5,3)
setup(qc)
for i in range(0,2):
search(qc)
diffuser(qc)
#Measure out results
qc.barrier(range(0,5))
qc.measure(0,0)
qc.measure(1,1)
qc.measure(2,2)
The circuit gets very large.
The results are shown below.
{
'011': 1909,
'101': 16,
'001': 16,
'100': 22,
'000': 24,
'110': 21,
'010': 24,
'111': 16
}
Now one of the answers stands out drastically. There are 1909 tests that come back with 3 (011) and barely any for any other number. We just need to run multiple tests and we will quickly see a clear winner for the circuit.
The full source code is shown below.
#Mark Boady - 2021
#Import the Libraries
from qiskit import *
#For simulations:
from qiskit import BasicAer
#Search for 3
def search(circuit):
#Start of Search Circuit
circuit.barrier(range(0,5))
#Start of Number Selection
#Set Bits we need to be 0
circuit.x(2)
#Three Qubit AND
circuit.ccx(0,1,4)
circuit.ccx(2,4,3)
circuit.ccx(0,1,4)
#End Three QUBIT AND
#undo bit set
circuit.x(2)
#End of Number Selection
circuit.barrier(range(0,5))
#End of Search Circuit
#Grover Setup
def setup(circuit):
#Prepare for Grover
#1.) Apply X to result
circuit.x(3)
#2.) Apply H to input qubits
circuit.h(0)
circuit.h(1)
circuit.h(2)
#3.) Apply H to result qubit
circuit.h(3)
#Diffuser
def diffuser(circuit):
#Start of Diffuser
circuit.h(0)
circuit.h(1)
circuit.h(2)
circuit.x(0)
circuit.x(1)
circuit.x(2)
#3 bit controlled Z
circuit.ccx(0,1,4)
circuit.cz(4,2)
circuit.ccx(0,1,4)
#end 3-bit controlled Z
circuit.x(0)
circuit.x(1)
circuit.x(2)
circuit.h(0)
circuit.h(1)
circuit.h(2)
#End of Diffuser
#Make a Circuit
qc = QuantumCircuit(5,3)
setup(qc)
for i in range(0,2):
search(qc)
diffuser(qc)
#Measure out results
qc.barrier(range(0,5))
qc.measure(0,0)
qc.measure(1,1)
qc.measure(2,2)
#Matplot to make an image
qc.draw(output="mpl",filename="groverP3.png")
#Run our simulation!
#Create Simulator
backend_sim = BasicAer.get_backend('qasm_simulator')
#Run 2,048 tests
job_sim = execute(qc,backend_sim,shots=2048)
#Get the results
result_sim = job_sim.result()
#Show the count of each outcome
counts = result_sim.get_counts()
print(counts)