# The quantum (a)muse(ment) #3: random numbers in an interval

*What if we use Grover to generate random numbers in an interval?*

Following up on Alessandro Berti’s post about Grover and on my previous random numbers generation post, I tried to use Grover as a filter to generate numbers in a custom interval.

The idea here is really simple: to synthesize an oracle for a boolean expression individuating an interval.

# Writing the boolean expression for the interval

Let’s say we want to generate numbers between 1 and 3.

ABY

000

011 # Not(A) and B

101 # A and Not(B)

111 # A and B

Then the boolean formula for the oracle should be:

Y = (Not(A) and B) OR (A and Not(B)) OR (A and B)

# Writing the oracle

To write an oracle suitable to apply Grover, we have to obtain an expression where we have a set of positive/negated clauses connected with ANDs where the literals are positive/negated.

That form can be obtained by applying De Morgan.

It is very easy to observe that

Expr = Not(Not(Expr))

So

Y = Not(Not(Y))

That is:

Y = Not(Not(Not(A) and B) And Not(A and Not(B)) And Not(A and B))

To synthesize a circuit for that boolean expression we have to take in account a “couple of things”:

## - Expressing AND

CCNOT gate (Toffoli) flips the target qubit if both control qubits are |1> so it can be used as an AND gate.

## - Negating a control qubit

It is possible to negate a control qubit by applying an X operator before and after the qubit itself (as in Not(A) and B).

## - Negating a conjunction

Negating a conjunction is equivalent to applying a CCNOT gate to control qubits and negating the target qubit (as in Not(A and B)).

## - AND for multiple expressions

If we want to compute something like:

Expr1 AND Expr2 AND Expr3

we have to store intermediate results in a “working qubit”.

So, given the previous instructions, it is possible to compose an oracle for Grover to select only random numbers between 1 and 3:

# Checking results

Running the simulation, we get the following results, which show that the circuit tends to select numbers in the interval [1,3] but in some cases it is still possible to select 0: