Learning Functional Level Design: Grover¶
This is a step-by-step example of how to use the Classiq Platform at the functional level. The goal is to show you the advantages of high-level quantum design. We will do so be designing a search algortihm - Grover/Amplitude Amplification (we assume basic familiarity with the theory of the Grover operaotr).
As the name suggests, this algorithm searches for the answers to a specific question. The question we are intrested here is:
Given 2 non-negative integers a and b, smaller than 4, what pairs of (a,b) are summed up to 4 ? i.e. (a,b) for which a+b=4
Of course the problem is very simple and the solutions are: {(3,1),(2,2),(1,3)}. But the main advantages of high-level quantum algortihm design are manifested even here! Some real world example for a search problems can be finding a specfic song in a data base from only listening to a few seconds (the SHAZAM App)
The Final Circuit¶
Let's start from the final circuit we will receive and then go through the processes of building it! This way we will understand the algortihm in a better way.
So this is the full circuit:
The circuit represents the algorithm, the functional model we design. In our example, we can see that it is composed from two types of functional blocks: state preperation and Grover operator.
The way we build models is by:
Defining the functional blocks
Defining an high-level functional model that will contain the functional blocks
Wiring the blocks within the high-level functional model
1. Defining the Functional Blocks¶
State preperation¶
Let's start from the first two blocks of the state preperations we have on the right:
We want to have two state preparation objects, each of them acts on a different register of qubits. One register will represent the value of $a$ and one the value of $b$.
The way we define these objects is with the StatePreparation object. This object receives the desired probability distribution and an error metric for the implementaions (since we usually have the trade-off of accuracy vs. depth of implementation, so we want to hace the minimal implemenation that perform our desired state preperation up to a given error).
What are the probability distributions? Because we know $a,b$ can be in the range [0,3] with 4 different optional values (0,1,2,3), the registers representing their values must conatin 2 qubits. We know for sure that the neither $a=0$ nor $b=0$. Hence we can initiate the registers as uniformly distributed over the values $1,2,3$:
prob_a = [0, 1 / 3, 1 / 3, 1 / 3]
prob_b = [0, 1 / 3, 1 / 3, 1 / 3]
And the state preparation object that will create this probability distribution:
from classiq.builtin_functions import StatePreparation
sp_a = StatePreparation(probabilities=prob_a, error_metric={"KL": {"upper_bound": 0.1}})
sp_b = StatePreparation(probabilities=prob_b, error_metric={"KL": {"upper_bound": 0.1}})
Above we defined the error metric to be according to the Kullback-Leibler (KL) divergence metric, with the upper bound being 0.1.
The Grover operator¶
The second functional block we have is the Grover operator, that repeats twice. The reason for the two repetitions is due to the number of solutions we expect (5).
Unlike the StatePreparation operator, the GroverOperator is composed from several functional blocks by themselves, where some of them we need to define. These are:
- The
ArithmeticOracle StatePreparationover the register of $a$ and $b$- Diffuser
- Another
StatePreparationover the register of $a$ and $b$
The Arithmetic Oracle¶
At the heart of the Grover operator lies the Arithmetic Oracle. This Oracle is a sub-quantum algorithm that marks states that are the desired solution in the following way:
$|x\rangle\rightarrow (-1)^{f(x)}|x\rangle$
where $f(x)=1$ if $x$ is a solution and $f(x)=0$ otherwise. One should treat $x$ as $x=(a,b)$, such that a solution $f(x)=f((a,b))=1$ if and only if $a+b=4$.
There are multiple ways of implementing a desired oracle, and the implementaion depends on many parmeters such as the number of auxilary qubits, and might be complicates. This is the reason it is usually referred as a 'black box'!
But someone needs to implements this black box according to your availble resources and needs, and this is exactly one of the things the Classiq Platform does for you! It optimizes an implementaion of an Oracle specifically designed for your needs, and all you need to do is to just define them..
When defining the Oracle, we need to define two things: the expression we are searching for, and how the values are incorporated into the search - via quantum registers.
In addition, we want to tell the Classiq Platform that we want to optimize the uncomputation. That is, the implementaion of the oracle includes some auxillary qubits that our "value registers" are getting entangles to during the algorithm. We need to un-entangle them in order to not ruin the calculation - this is the uncomputation.
from classiq import RegisterUserInput
from classiq.builtin_functions import ArithmeticOracle
# How many qubits are per register of a and b?
num_of_qubits = 2
# Defining the oracle
oracle = ArithmeticOracle(
expression="a+b==4",
definitions={
"a": RegisterUserInput(size=num_of_qubits),
"b": RegisterUserInput(size=num_of_qubits),
},
uncomputation_method="optimized",
)
The oracle is a Python object that will be incorporated into our high-level functional model later on.
The State Preparation¶
Above we have defined state preperations, but they were applied on the two registers of $a$ and $b$ seperately. We want to apply one general state preperation for the general Grover operator that encompasses the two registers we have.
Therefore, we will use the Kronecker product (outer product): $p_{ab}=p_a \otimes p_b$, defined by the Numpy package, and then build another StatePreparation object:
import numpy as np
prob_ab = np.kron(prob_b, prob_a)
sp_ab = StatePreparation(
probabilities=prob_ab, error_metric={"KL": {"upper_bound": 0.1}}
)
The Diffuser¶
In the above implementation, the diffuser is a general one:
$2|0\rangle\langle0|-\mathbb{I}$.
Therefore, there is no need to define it in particular.
The complete Grover Operator¶
Having all the building blocks of the GroverOperator, the grover object can be defined now:
from classiq.builtin_functions import GroverOperator
grover = GroverOperator(oracle_params=oracle, state_preparation_params=sp_ab)
How many times the Grover operator will be repeated? This is defined according to the following equation:
$[\frac{\pi}{4}\sqrt{\frac{N}{M}}]$,
where $N$ is the number of possible values the two registers can collectively have ($3^2$), and $M$ is the number of solutions (3).
Therefore, in our case
total_num_of_qubits = 2 * num_of_qubits
N = 3**2
M = 3
num_of_iterations = int(np.round(np.pi / 4 * np.sqrt(N / M)))
print("#iterations =", num_of_iterations)
2. Defining the High-Level Functional Model¶
The high-level functional model encapsulates all the functionalities of our algorithm, and specifically all the building blocks we have defined. The model is stored within an instance of the Model object:
from classiq import Model
model = Model()
In this tutorial we simply want to take samples on all the qubits from the resulting circuit.
model.sample()
3. Wiring the Blocks within the High-Level Functional Model¶
Now that we have all the building blocks for our model, we need to wire them up. Let's have another look on the final circuit to guide us: