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:
