
grover search algorithm
Lov Grover developed the Grover search algorithm in 1996. It was the first quantum algorithm to demonstrate an advantage over classical algorithms. Grover’s algorithm was initially developed as a solution to the unstructured search problem. Grover’s randomized search algorithm uses quantum interference to locate a target item. It is designed to search an unsorted data database much faster than a classical algorithm.
The algorithm uses quantum interference and entanglement to locate the desired item faster than known classical’s. The algorithm uses a quantum computer to iteratively search a data set, flipping the phase of any desired item until it is detected. This process is done by applying the Grover iterate, a unitary operator, to the original state of the qubits. This algorithm is useful for solving problems such as finding a single item in an unsorted database or finding a global minimum of a function. It is also useful for finding collisions in hash functions. The Grover search algorithm has an advantage over classical algorithms as it can search an unsorted database in only O(√N) steps, compared to an O(N) step for classical algorithms.
A classic example of Grover’s algorithm is the fair sharing of gold pieces discovered by miners. Imagine 8 gold pieces with a total value of $144K. Grover’s algorithm can identify the best possible split between the miners, so each receives a share of the total-sum/2. This can be accomplished by following three steps in a quantum computing context.
In doing so, first, all shares must be put into an equal superposition of values. Then, an oracle function is applied, encoded with the problem’s solution. This is often implemented with a quantum Fourier transform. Finally, the values are identified and amplified repeatedly using Grover operators.
This example of Grover’s algorithm demonstrates the power of quantum computing to solve complex optimization problems efficiently. The algorithm can quickly identify the best possible solution for a given problem by harnessing the parallelism and superposition of quantum states.
This is a coded solution to the problem that is implemented at a high level.
class QCircuit:
def __init__(self):
# total to $144K
gold_prices = [7, 8, 9, 5, 11, 18, 33, 53]
# number of qubits
variables_wires = [0, 1, 2, 3, 4, 5, 6, 7]
# number of auxialry qubits
aux_oracle_wires = [8 ,9 ,10, 11, 12, 13, 14 ]
dev = qml.device("lightning.qubit", wires = variables_wires + aux_oracle_wires, shots=1)
@qml.qnode(dev)
def circuit(self):
# Equal superpoision of all possible configurations
for wire in self.variables_wires:
qml.Hadamard(wires = wire)
for _ in range(5):
# Apply Oracle that satisfies the solution to our problem
self.oracle(self.variables_wires, self.aux_oracle_wires)
# Repeat the apmplificaton using Grover operator
qml.GroverOperator(wires = self.variables_wires)
return qml.sample(wires = self.variables_wires)
def oracle(self, variables_wires, aux_oracle_wires):
def add_n_fourier(n, wires):
for j in range(len(wires)):
qml.RZ(k * np.pi / (2**j), wires=wires[j])
def value_second_partner():
qml.QFT(wires = self.aux_oracle_wires)
for wire in self.variables_wires:
qml.ctrl(add_n_fourier, control = wire)(self.gold_prices[wire], wires = self.aux_oracle_wires)
qml.adjoint(qml.QFT)(wires = self.aux_oracle_wires)
value_second_partner()
qml.FlipSign(sum(self.gold_prices) // 2, wires = self.aux_oracle_wires)
qml.adjoint(value_second_partner)()
After executing the code, the combined share for the second partner would be:
SUM(8,11,53) = 72
which is the encoded value for the gold-piece-1 + gold-piece-4 + gold-piece-8 from the initial gold prices list!
