Grover quantum search

Each Grover iteration – oracle sign flip followed by inversion about the mean – rotates the state by 2 theta in the plane spanned by the marked and unmarked uniform states. The N = 4, M = 1 case gives theta = pi/6 and success probability exactly 1 after a single query.

Usage

GroverS(oracle, N)

Arguments

oracle

Length-N vector of 0/1 marks.

N

Search space size.

Value

List with estimate, p_success, p_closed_form, p_path, k_opt, theta, n, method.

Details

Formula: P(k) = sin^2((2k + 1) theta), sin theta = sqrt(M/N), k* = round(pi/(4 theta) - 1/2).

References

Grover (1996), A fast quantum mechanical algorithm for database search, STOC '96, pp. 212-219. doi:10.1145/237814.237866

Examples

oracle <- rep(0, 8)
oracle[4] <- 1
GroverS(oracle, N = 8)
#> $estimate
#> [1] 0.9453125
#> 
#> $p_success
#> [1] 0.9453125
#> 
#> $p_closed_form
#> [1] 0.9453125
#> 
#> $p_path
#> [1] 0.1250000 0.7812500 0.9453125
#> 
#> $k_opt
#> [1] 2
#> 
#> $theta
#> [1] 0.3613671
#> 
#> $n
#> [1] 8
#> 
#> $method
#> [1] "P(k) = sin^2((2k+1) theta), sin theta = sqrt(M/N), Grover (1996)"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"