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

Juna Salviati
3 min readJul 7, 2024

--

Photo by Carlos Irineu da Costa on Unsplash

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:

Grover for (Not(A) and B) OR (A and Not(B)) OR (A and B)

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:

Results for Grover on (Not(A) and B) OR (A and Not(B)) OR (A and B)

--

--

Juna Salviati

Full-time Human-computer interpreter. Opinions are my own.