-
Notifications
You must be signed in to change notification settings - Fork 0
/
Program.qs
88 lines (79 loc) · 3.02 KB
/
Program.qs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
namespace QGroversAlgorithm {
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Intrinsic;
open Microsoft.Quantum.Measurement;
open Microsoft.Quantum.Math;
open Microsoft.Quantum.Convert;
open Microsoft.Quantum.Arithmetic;
open Microsoft.Quantum.Arrays;
open Microsoft.Quantum.Preparation;
@EntryPoint()
operation FactorizeWithGrovers(number: Int): Unit {
let markingOracle = MarkDivisor(number, _, _);
let phaseOracle = ApplyMarkingOracleAsPhaseOracle(markingOracle, _);
let size = BitSizeI(number);
let nSolutions = 4;
let nIterations = Round(PI() / 4.0 * Sqrt(IntAsDouble(size) / IntAsDouble(nSolutions)));
use (register, output) = (Qubit[size], Qubit());
mutable isCorrect = false;
mutable answer = 0;
repeat {
RunGroversSearch(register, phaseOracle, nIterations);
let res = MultiM(register);
set answer = BoolArrayAsInt(ResultArrayAsBoolArray(res));
markingOracle(register, output);
if MResetZ(output) == One and answer != 1 and answer != number {
set isCorrect = true;
}
ResetAll(register);
} until isCorrect;
Message($"The number {answer} is a factor of {number}.");
}
operation MarkDivisor(dividend: Int,
divisorRegister: Qubit[],
target: Qubit): Unit is Adj+Ctl {
let size = BitSizeI(dividend);
use (dividendQubits, resultQubits) = (Qubit[size], Qubit[size]);
let xs = LittleEndian(dividendQubits);
let ys = LittleEndian(divisorRegister);
let result = LittleEndian(resultQubits);
within{
ApplyXorInPlace(dividend, xs);
DivideI(xs, ys, result);
ApplyToEachA(X, xs!);
}
apply{
Controlled X(xs!, target);
}
}
operation PrepareUniformSuperpositionOverDigits(digitReg: Qubit[]): Unit is Adj + Ctl {
PrepareArbitraryStateCP(ConstantArray(10, ComplexPolar(1.0, 0.0)), LittleEndian(digitReg));
}
operation ApplyMarkingOracleAsPhaseOracle(markingOracle: (Qubit[], Qubit) => Unit is Adj,
register: Qubit[]): Unit is Adj {
use target = Qubit();
within {
X(target);
H(target);
} apply {
markingOracle(register, target);
}
}
operation RunGroversSearch(register: Qubit[],
phaseOracle: ((Qubit[]) => Unit is Adj),
iterations: Int): Unit {
ApplyToEach(H, register);
for _ in 1 .. iterations {
phaseOracle(register);
ReflectAboutUniform(register);
}
}
operation ReflectAboutUniform(inputQubits: Qubit[]): Unit {
within {
ApplyToEachA(H, inputQubits);
ApplyToEachA(X, inputQubits);
} apply {
Controlled Z(Most(inputQubits), Tail(inputQubits));
}
}
}