Grover Quantum Search on the Dynex Platform

7 min readJun 10, 2024

Grover’s search algorithm was originally proposed for circuit-based quantum computers. A crucial part of it is to query an oracle — a black-box unitary operation. We demonstrate the application of Grover’s algorithm on the Dynex Neuromorphic Quantum Computing platform.

Source code: A complete Jupyter Notebook of the implementation is available on our Dynex GitHub.

The Grover Search Algorithm

Grover’s search algorithm is a quantum algorithm designed to search an unsorted database or solve unstructured search problems with quadratic speedup compared to classical algorithms. In classical computing, finding a specific item in an unsorted list of N items requires O(N) time in the worst case. Grover’s algorithm, however, can accomplish this task in O(√N) time. The algorithm operates by initializing a superposition of all possible states and then iteratively amplifying the probability amplitude of the correct solution while diminishing the amplitudes of the incorrect ones. This process is achieved through the application of two main operations: the Oracle, which marks the correct solution, and the Diffusion operator, which amplifies the marked state’s probability. After approximately √N iterations, measuring the quantum state yields the correct solution with high probability. Grover’s algorithm exemplifies the power of quantum computing to solve specific problems more efficiently than classical counterparts, making it a cornerstone of quantum search techniques.

We will be focussing on the practical implementation of the algorithm, for the mathematical background we refer to the Wikipedia article about Grover’s algorithm.

Implementation in Python

We start with implementing the required packages and modules:

import numpy as np
import os
import dynex
import random
from tqdm import tqdm
from dwave.samplers import SimulatedAnnealingSampler
from dimod import BinaryQuadraticModel, SampleSet
import matplotlib.pyplot as plt

Grover’s search algorithm begins by initializing a quantum circuit where all qubits are placed in a superposition state. This is achieved on gate based quantum machines by applying the Hadamard gate to each qubit or on neuromorphic quantum based systems by constructing a QUBO matrix with multiple low-energy solutions, creating an equal probability amplitude for every possible state in the quantum system. This superposition allows the algorithm to explore multiple solutions simultaneously, leveraging the parallelism inherent in quantum computing. The following function initialises the quantum circuit in superposition state:

def initialize_qubo(matrix_size):
    '''
    Function to create a quantum circuit with all variables in superposition
    '''
    # Initialize a QUBO matrix with zeros
    size = matrix_size
    qubo = np.zeros((size, size))
    
    # Construct a QUBO matrix with multiple low-energy solutions
    for i in range(size):
        qubo[i, i] = -1  # Encourages x_i to be 1
    
    # Add off-diagonal elements to create interactions between different variables
    # Ensuring multiple solutions can be done by having multiple possible pairs or sets that minimize the energy
    for i in range(size):
        for j in range(i+1, size):
            qubo[i, j] = 1.0 / (matrix_size-1) * 2 # off-diagonal interactions

    # Symmetrize the matrix to ensure QUBO properties
    qubo = (qubo + qubo.T) / 2
    
    return qubo

This function creates and initiates a quantum circuit with all variables in superposition, spinning between -1.0 and +1.0. To validate the function, we run this circuit multiple times and measure the variable voltages:

# Define our parameters:
qubits = 32;
shots = 2000;

# Create the quantum circuit:
Q = initialize_qubo(qubits)
bqm = BinaryQuadraticModel.from_qubo(Q)

# Run the circuit and measure results:
solver = SimulatedAnnealingSampler()
sampleset = solver.sample(bqm, num_reads=shots, annealing_time=1000)
res = np.zeros(qubits)
cnt = 0;
for s in sampleset.record:
    for i in range(0, len(s.sample)):
        if s[0][i]==1:
            res[i]+=1
    cnt += 1;

plt.title('Number of positive spins ('+str(cnt)+' shots)');
plt.bar(list(sampleset.first.sample), res, alpha=0.2);
plt.axhline(y=cnt/2, color='b', linestyle='--');

print(res, 'shots:',cnt)

We can observe that the number of positive spins correctly averages at 50% of the number of shots. Following the initialization, the algorithm iteratively applies the Grover Oracle and the Diffusion Operator to manipulate the amplitude distribution. The Oracle marks the correct solution by flipping its amplitude, while the Diffusion Operator amplifies the probability of this marked state. Through these iterations, the probability of measuring the correct solution increases, leading to its identification in fewer steps compared to classical search methods. This process exemplifies the power of quantum superposition and interference, foundational principles that enable Grover’s algorithm to achieve its quadratic speedup.

The Grover Oracle

The Grover Oracle is a crucial component of Grover’s search algorithm, responsible for marking the correct solution among the possible candidates in a quantum search problem. It is a quantum subroutine designed to flip the sign of the amplitude of the correct solution’s quantum state, effectively distinguishing it from all other states. The Oracle achieves this by utilizing a black-box function, often represented as 𝑂(𝑥), which outputs 1 for the target solution and 0 for all other inputs. This phase inversion is essential for the iterative amplification process in Grover’s algorithm, as it sets the stage for the subsequent Diffusion operator to increase the probability of measuring the correct solution. By precisely marking the target state, the Grover Oracle enables the algorithm to converge towards the correct solution with quadratic speedup, highlighting its fundamental role in the efficiency of quantum search.

def grover_oracle(target_index, num_elements):
    '''
    Grover Oracle black box function which marks the correct solution 
    among the possible candidate in a quantum search problem
    '''
    # Initialise all qubits in superposition:
    Q = initialize_qubo(num_elements);
    # O(x) function outputs 1 for the target solution and 0 for all other inputs:
    for q in range(0,num_elements):
        Q[q,q] = 2.0
    # Flip sign for target index:
    Q[(target_index, target_index)] = -2.0
    return Q

The Diffussion Operator

The Diffusion Operator, also known as the Grover Diffusion Operator or the Inversion about the Mean, is a key component in Grover’s search algorithm that amplifies the probability amplitude of the correct solution. After the Oracle marks the correct state by flipping its amplitude, the Diffusion Operator performs an inversion about the average amplitude of all states. This process enhances the marked state’s amplitude while reducing the amplitudes of the incorrect states, effectively concentrating the probability distribution towards the correct solution. Mathematically, it involves reflecting the quantum state vector through the uniform superposition state. By repeatedly applying the Oracle and the Diffusion Operator, Grover’s algorithm iteratively increases the likelihood of measuring the correct solution. The Diffusion Operator is thus vital in the quadratic speedup achieved by the algorithm, enabling it to solve search problems more efficiently than classical methods.

def initialise_diffusion_operator(num_bits):
    '''
    Initialises the Diffusion operator which amplifies the 
    probability amplitude of the correct solution
    '''
    Q = {}
    for i in range(2**num_bits):
        Q[(i, i)] = 1
    return Q

Grover Quantum Search on Dynex

Putting it all together, we will apply Grover’s search algorithm to find an element in a unstructured dataset as defined as:

# Define the dataset and target value
dataset = [12, 5, 7, 14, 6, 11, 9, 10, 13, 2, 3, 8, 4, 15, 0, 1, 16, 17, 
           18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31]
target_value = 15

Next we convert the dataset to binary format (if needed) and find the target index:

# Convert the dataset to a binary format if needed and find the target index
num_elements = len(dataset)
num_bits = int(np.ceil(np.log2(num_elements)))
target_index = dataset.index(target_value)
print('num_elements:',num_elements,'num_bits:',num_bits,'target_index:',target_index)

>> num_elements: 32 num_bits: 5 target_index: 13

We construct and initialise our Grover quantum circuit:

# Create Oracle
oracle_qubo = grover_oracle(target_index, num_elements)
oracle_bqm = BinaryQuadraticModel.from_qubo(oracle_qubo)

# Create Diffusion QUBO
diffusion_qubo = initialise_diffusion_operator(num_bits)
diffusion_bqm = BinaryQuadraticModel.from_qubo(diffusion_qubo)

The following function performs a Grover iteration by querying the oracle and applying the diffusion operator to the output:

def grover_iteration(oracle_bqm, diffusion_bqm):
    '''
    Grover iteration step querying the oracle and applying the 
    diffusion operator. Each step requires two sample calls to 
    the Dynex platform
    '''
    # Apply the oracle
    sampleset_oracle = dynex.sample(oracle_bqm, mainnet=False, 
                        num_reads=1000, annealing_time = 1000, logging=False)
    best_sample = sampleset_oracle.first.sample

    # Update the diffusion operator to reflect the oracle's output
    for v in diffusion_bqm.variables:
        diffusion_bqm.add_linear(v, -2 * best_sample[v])
   
    # Apply the diffusion operator
    sampleset_diffusion = dynex.sample(diffusion_bqm, mainnet=False, num_reads=1000, annealing_time = 1000, logging=False)
    
    return sampleset_diffusion, diffusion_bqm

And finally perform Grover’s algorithm:

# Perform Grover's algorithm iterations
num_iterations = int(np.pi / 4 * np.sqrt(num_elements))
print('num_iterations (max SQRT of elements):',num_iterations)
for _ in tqdm(range(num_iterations)):
    sampleset, diffusion_bqm = grover_iteration(oracle_bqm, diffusion_bqm)

# Output the result
best_sample = sampleset.first.sample

# Convert the binary sample to an index
best_index = list(best_sample.values()).index(1);

print("Best sample: ", best_sample)
print("Best index: ", best_index)
print("Dataset value at best index: ", dataset[best_index], 
                                    'target was',target_value)
print("Energy: ", sampleset.first.energy)

if dataset[best_index]==target_value:
    print('SUCCESS. GROVER SEARCH FOUND THE TARGET VALUE IN',
                                num_iterations,'ITERATIONS');

>> num_iterations (max SQRT of elements): 4
>> Best sample:  {0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 0, 8: 0, 9: 0, 10: 0, 11: 0, 12: 0, 13: 1, 14: 0, 15: 0, 16: 0, 17: 0, 18: 0, 19: 0, 20: 0, 21: 0, 22: 0, 23: 0, 24: 0, 25: 0, 26: 0, 27: 0, 28: 0, 29: 0, 30: 0, 31: 0}
>> Best index:  13
>> Dataset value at best index:  15 target was 15
>> Energy:  -29.0
>> SUCCESS. GROVER SEARCH FOUND THE TARGET VALUE IN 4 ITERATIONS

We can visualise the qubit voltages at the end of the Grover iterations:

plt.title('Qubit voltages after '+str(num_iterations)+' Grover iterations');
plt.bar(list(best_sample), list(best_sample.values()), alpha=0.2);

The Dynex Grover Search algorithm demonstrated remarkable efficiency by finding the solution in a database of 32 elements in just 4 iterations. This performance aligns perfectly with the expected quadratic speedup of Grover’s algorithm, which theoretically requires 𝑂(𝑁) iterations, where
𝑁 is the number of elements. In this case, 32 approximates to 4, illustrating that the Dynex implementation achieved optimal performance. This is significantly faster than traditional linear search methods, which would typically require up to 32 iterations to find the target element in the worst case. The successful application of the Dynex Grover Search algorithm not only validates the theoretical speedup of quantum search algorithms but also underscores the potential of quantum computing to outperform classical approaches in solving complex search problems.

Further Reading: