|q⟩
Bad Qubits
Play
Quest
Questions
Learn
Playground
☕
← Question Bank
Multiple choice
In Shor's algorithm to factor
N
=
15
N=15
N
=
15
with base
a
=
7
a=7
a
=
7
, the order-finding step yields period
r
=
4
r=4
r
=
4
. The factors are obtained from
gcd
(
a
r
/
2
−
1
,
N
)
\gcd(a^{r/2} - 1, N)
g
cd
(
a
r
/2
−
1
,
N
)
and
gcd
(
a
r
/
2
+
1
,
N
)
\gcd(a^{r/2} + 1, N)
g
cd
(
a
r
/2
+
1
,
N
)
. Since
7
2
=
49
=
4
(
m
o
d
15
)
7^2 = 49 = 4 \pmod{15}
7
2
=
49
=
4
(
mod
15
)
, what nontrivial factor does
min
(
gcd
(
4
−
1
,
15
)
,
gcd
(
4
+
1
,
15
)
)
\min(\gcd(4-1,15), \gcd(4+1,15))
min
(
g
cd
(
4
−
1
,
15
)
,
g
cd
(
4
+
1
,
15
))
return?
15 (no factor found)
3
7 (the base
a
a
a
)
5 (taking the larger gcd instead of the minimum)
Check answer