Fix grover's search formula

[AbeerVaishnav13]

Fixed the formula for calculating number of iterations in grover's search algorithm.

[tgehr]

Thank you for your interest in contributing to Silq, but In what sense is this a fix? As far as I can tell, the only case where this changes nIterations with the current simulator is n=1. The number of iterations is changed from 0 to 1, and this is merely because of imperfect floating-point accuracy in the simulator. However, if n=1, it does not matter how many times one runs the loop, as the success probability does not change. (The optimal number of iterations would be 1/2.)

If we let θ:=2*asin(2^(-n/2)), then after k iterations, our machine state is cos(θ/2+kθ)·|α⟩ + sin(θ/2+kθ)·|β⟩ for |α⟩ := 1/sqrt(2^n-1) ∑(v≠w⋆) |v⟩ (uniform superposition of non-solutions) and |β⟩ := |w⋆⟩ (solution). Ideally, we want to reach the state cos(π/2)·|α⟩+sin(π/2)·|β⟩=|β⟩, so we want to get θ/2+nIterations·θ=π/2. Solving for nIterations, we obtain nIterations=π/(2·θ)-1/2. Unfortunately, nIterations has to be an integer, so we have to round this: nIterations:=round(π/(2·θ)-1/2). Whether for n=1, you pick 0 or 1 is a matter of rounding convention. In particular, it is valid to set nIterations:=floor(π/(2·θ)).

Note that your formula is an approximation to our formula. Your approximation formula is indeed precise enough to give correct results after rounding. However, we have not used this approximation as we think it is less enlightening. Why do you think we should use it?

[AbeerVaishnav13]

Thank you for your reply @tgehr. I now understood the usage of the already given formula. I am still a novice in Quantum Algorithms and was confused when I saw the formula nIterations:=round(π/(2·θ)-1/2). My apologies. Thanks for the clarification.

[AbeerVaishnav13]

SILQ seems to be a great language to me as a Quantum Computing enthusiast. Although, when I was looking into the code for Grover's algorithm and tried to tinker with it to make the oracle function f as an input into the grover() function, I noticed that there's no way to define a Multi-Controlled U gate apart from listing down the individual qubits in the if statement like so:

if qs[0] && qs[1] && qs[2] {
    ancilla := X(ancilla);
}
... //omitted

This feature is really helpful but the point of this fails when there are say more than 7-8 qubits that I want as control qubits, as the code will be too long. Also, this limits the usage as in this case, the Oracle has to be created manually for each search term within the domain of 2^n entries. Is there a solution to this which I'm not able to figure out, or is it a feature yet to be added in the language?

[tgehr]

Well, it does not require built-in language support, but something like the following all function will probably be added to the standard library at some point:

def all[n:!ℕ](x:𝔹^n)lifted{
    r:=1:𝔹;
    for i in 0..n{ r&=x[i]; }
    return r;
}

n:=3;
def main(){
    qs:=vector(n,0:𝔹);
    for i in 0..n{ qs[i]:=H(qs[i]); }
    ancilla:=all(qs);
    return (qs,ancilla);
}

(You can of course also do ancilla:=0:𝔹; if all(qs){ ancilla :=X(ancilla); }, but the above is more concise in this case.)

You can also inline everything:

n:=3;
def main(){
    qs:=vector(n,0:𝔹);
    for i in 0..n{ qs[i]:=H(qs[i]); }
    ancilla:=0:𝔹;
    x:=1:𝔹;
    for i in 0..n{ x&=qs[i]; }
    if x{
        ancilla:=X(ancilla);
    }
    forget(x); // uncompute x based on qs
    return (qs,ancilla);
}

The forget(x) statement will soon not be required. (We will improve type checking for return statements, such that it automatically figures out that x has to be uncomputed before we can return the other parts of the state.)

[AbeerVaishnav13]

Thank you for the help @tgehr :D