microsoft/qdk
Publicmirrored fromhttps://github.com/microsoft/qdkAvailable
katas/content/grovers_search/examples/GroversSearchAlgorithmDemo.qs
89lines · modecode
| 1 | namespace Kata { |
| 2 | open Microsoft.Quantum.Convert; |
| 3 | open Microsoft.Quantum.Diagnostics; |
| 4 | open Microsoft.Quantum.Math; |
| 5 | |
| 6 | @EntryPoint() |
| 7 | operation GroversSearchAlgorithmDemo() : Unit { |
| 8 | // Experiment with the parameters to explore algorithm behavior in different conditions! |
| 9 | let n = 3; |
| 10 | let prefix = [false, true, false]; |
| 11 | let markingOracle = Oracle_StartsWith(_, _, prefix); |
| 12 | for iterations in 0 .. 9 { |
| 13 | mutable success = 0; |
| 14 | for _ in 1 .. 100 { |
| 15 | let res = GroversSearch(n, markingOracle, iterations); |
| 16 | if BoolArrayAsInt(prefix) == BoolArrayAsInt(res) { |
| 17 | set success += 1; |
| 18 | } |
| 19 | } |
| 20 | Message($"{iterations} iterations - {success}% success rate"); |
| 21 | } |
| 22 | } |
| 23 | |
| 24 | operation GroversSearch( |
| 25 | n : Int, |
| 26 | markingOracle : (Qubit[], Qubit) => Unit is Adj + Ctl, |
| 27 | iterations : Int |
| 28 | ) : Bool[] { |
| 29 | use qs = Qubit[n]; |
| 30 | |
| 31 | // Operation that prepares the state |all⟩. |
| 32 | let meanStatePrep = ApplyToEachCA(H, _); |
| 33 | |
| 34 | // The phase oracle. |
| 35 | let phaseOracle = ApplyMarkingOracleAsPhaseOracle(markingOracle, _); |
| 36 | |
| 37 | // Prepare the system in the state |all⟩. |
| 38 | meanStatePrep(qs); |
| 39 | |
| 40 | // Do Grover's iterations. |
| 41 | for _ in 1 .. iterations { |
| 42 | // Apply the phase oracle. |
| 43 | phaseOracle(qs); |
| 44 | |
| 45 | // Apply "reflection about the mean". |
| 46 | ReflectionAboutState(qs, meanStatePrep); |
| 47 | } |
| 48 | |
| 49 | // Measure to get the result. |
| 50 | return ResultArrayAsBoolArray(MResetEachZ(qs)); |
| 51 | } |
| 52 | |
| 53 | operation Oracle_StartsWith(x : Qubit[], y : Qubit, p : Bool[]) : Unit is Adj + Ctl { |
| 54 | ApplyControlledOnBitString(p, X, x[... Length(p) - 1], y); |
| 55 | } |
| 56 | |
| 57 | operation ApplyMarkingOracleAsPhaseOracle( |
| 58 | markingOracle : (Qubit[], Qubit) => Unit is Adj + Ctl, |
| 59 | qubits : Qubit[]) |
| 60 | : Unit is Adj + Ctl { |
| 61 | use minus = Qubit(); |
| 62 | within { |
| 63 | X(minus); |
| 64 | H(minus); |
| 65 | } apply { |
| 66 | markingOracle(qubits, minus); |
| 67 | } |
| 68 | } |
| 69 | |
| 70 | operation ReflectionAboutState( |
| 71 | qs : Qubit[], |
| 72 | statePrep : Qubit[] => Unit is Adj + Ctl) |
| 73 | : Unit is Adj + Ctl { |
| 74 | within { |
| 75 | Adjoint statePrep(qs); |
| 76 | } apply { |
| 77 | ConditionalPhaseFlip(qs); |
| 78 | } |
| 79 | } |
| 80 | |
| 81 | operation ConditionalPhaseFlip(qs : Qubit[]) : Unit is Adj + Ctl { |
| 82 | within { |
| 83 | ApplyToEachA(X, qs); |
| 84 | } apply { |
| 85 | Controlled Z(qs[1 ...], qs[0]); |
| 86 | } |
| 87 | R(PauliI, 2.0 * PI(), qs[0]); |
| 88 | } |
| 89 | } |