forked from cda-tum/mqt-core
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathGrover.cpp
116 lines (100 loc) · 3 KB
/
Grover.cpp
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include "algorithms/Grover.hpp"
namespace qc {
/***
* Private Methods
***/
void Grover::setup(QuantumComputation& qc) const {
qc.x(static_cast<Qubit>(nDataQubits));
for (std::size_t i = 0; i < nDataQubits; ++i) {
qc.h(static_cast<Qubit>(i));
}
}
void Grover::oracle(QuantumComputation& qc) const {
Controls controls{};
for (std::size_t i = 0; i < nDataQubits; ++i) {
controls.emplace(static_cast<Qubit>(i), targetValue.test(i)
? Control::Type::Pos
: Control::Type::Neg);
}
qc.mcz(controls, static_cast<Qubit>(nDataQubits));
}
void Grover::diffusion(QuantumComputation& qc) const {
for (std::size_t i = 0; i < nDataQubits; ++i) {
qc.h(static_cast<Qubit>(i));
}
for (std::size_t i = 0; i < nDataQubits; ++i) {
qc.x(static_cast<Qubit>(i));
}
qc.h(0);
Controls controls{};
for (Qubit j = 1; j < nDataQubits; ++j) {
controls.emplace(j);
}
qc.mcx(controls, 0);
qc.h(0);
for (auto i = static_cast<std::make_signed_t<Qubit>>(nDataQubits - 1); i >= 0;
--i) {
qc.x(static_cast<Qubit>(i));
}
for (auto i = static_cast<std::make_signed_t<Qubit>>(nDataQubits - 1); i >= 0;
--i) {
qc.h(static_cast<Qubit>(i));
}
}
void Grover::fullGrover(QuantumComputation& qc) const {
// create initial superposition
setup(qc);
// apply Grover iterations
for (std::size_t j = 0; j < iterations; ++j) {
oracle(qc);
diffusion(qc);
}
// measure the resulting state
for (std::size_t i = 0; i < nDataQubits; ++i) {
qc.measure(static_cast<Qubit>(i), i);
}
}
/***
* Public Methods
***/
Grover::Grover(std::size_t nq, std::size_t s) : seed(s), nDataQubits(nq) {
name = "grover_" + std::to_string(nq);
addQubitRegister(nDataQubits, "q");
addQubitRegister(1, "flag");
addClassicalRegister(nDataQubits);
mt.seed(seed);
std::bernoulli_distribution distribution{};
for (std::size_t i = 0; i < nDataQubits; i++) {
if (distribution(mt)) {
targetValue.set(i);
}
}
expected = targetValue.to_string();
std::reverse(expected.begin(), expected.end());
while (expected.length() > nqubits - 1) {
expected.pop_back();
}
std::reverse(expected.begin(), expected.end());
if (nDataQubits <= 2) {
iterations = 1;
} else if (nDataQubits % 2 == 1) {
iterations = static_cast<std::size_t>(std::round(
PI_4 * std::pow(2., static_cast<double>(nDataQubits + 1) / 2. - 1.) *
std::sqrt(2)));
} else {
iterations = static_cast<std::size_t>(
std::round(PI_4 * std::pow(2., static_cast<double>(nDataQubits) / 2.)));
}
fullGrover(*this);
}
std::ostream& Grover::printStatistics(std::ostream& os) const {
os << "Grover (" << nqubits - 1 << ") Statistics:\n";
os << "\tn: " << nqubits << "\n";
os << "\tm: " << getNindividualOps() << "\n";
os << "\tseed: " << seed << "\n";
os << "\tx: " << expected << "\n";
os << "\ti: " << iterations << "\n";
os << "--------------" << "\n";
return os;
}
} // namespace qc