8.7 KiB
8.7 KiB
Written in QScript via Quantum Playground
You can run the full simulation for this after compiling here.
Shor's Algorithm
// QScript version of an example from libquantum library.
num_regs = 4
proc swaptheleads width
for i = 0; i < width; i++
CNot i, width + i
CNot width + i, i
CNot i, width + i
endfor
endproc
proc swaptheleads_omuln_controlled control, width
for i = 0; i < width; i++
Toffoli control, width + i, 2 * width + i + 2
Toffoli control, 2 * width + i + 2, width + i
Toffoli control, width + i, 2 * width + i + 2
endfor
endproc
proc test_sum compare, width
if compare & (1 << (width - 1))
CNot 2 * width - 1, width - 1
SigmaX 2 * width - 1
CNot 2 * width - 1, 0
else
SigmaX 2 * width - 1
CNot 2 * width - 1, width - 1
endif
for i = (width - 2) ; i > 0; i--
if compare & (1 << i) //is bit i set in compare?
Toffoli i + 1, width + i, i
SigmaX width + i
Toffoli i + 1, width + i, 0
else
SigmaX width + i
Toffoli i + 1, width + i, i
endif
endfor
if compare & 1
SigmaX width
Toffoli width, 1, 0
endif
Toffoli 2 * width + 1, 0, 2 * width //set output to 1 if enabled and b < compare
if compare & 1
Toffoli width, 1, 0
SigmaX width
endif
for i = 1; i <= (width - 2) ; i++
if compare & (1 << i) //is bit i set in compare?
Toffoli i + 1, width + i, 0
SigmaX width + i
Toffoli i + 1, width + i, i
else
Toffoli i + 1, width + i, i
SigmaX width + i
endif
endfor
if compare & (1 << (width - 1))
CNot 2 * width - 1, 0
SigmaX 2 * width - 1
CNot 2 * width - 1, width - 1
else
CNot 2 * width - 1, width - 1
SigmaX 2 * width - 1
endif
endproc
// This is a semi-quantum fulladder. It adds to b_in
// a c-number. Carry-in bit is c_in and carry_out is
// c_out. xlt-l and L are enablebits. See documentation
// for further information
proc muxfa a, b_in, c_in, c_out, xlt_l, L, total //a,
if a == 0//00
Toffoli b_in, c_in, c_out
CNot b_in, c_in
endif
if a == 3//11
Toffoli L, c_in, c_out
CNot L, c_in
Toffoli b_in, c_in, c_out
CNot b_in, c_in
endif
if a == 1//01
Toffoli L, xlt_l, b_in
Toffoli b_in, c_in, c_out
Toffoli L, xlt_l, b_in
Toffoli b_in, c_in, c_out
Toffoli L, xlt_l, c_in
Toffoli b_in, c_in, c_out
CNot b_in, c_in
endif
if a == 2//10
SigmaX xlt_l
Toffoli L, xlt_l, b_in
Toffoli b_in, c_in, c_out
Toffoli L, xlt_l, b_in
Toffoli b_in, c_in, c_out
Toffoli L, xlt_l, c_in
Toffoli b_in, c_in, c_out
CNot b_in, c_in
SigmaX xlt_l
endif
endproc
// This is just the inverse operation of the semi-quantum fulladder
proc muxfa_inv a, b_in, c_in, c_out, xlt_l, L, total //a,
if a == 0//00
CNot b_in, c_in
Toffoli b_in, c_in, c_out
endif
if a == 3//11
CNot b_in, c_in
Toffoli b_in, c_in, c_out
CNot L, c_in
Toffoli L, c_in, c_out
endif
if a == 1//01
CNot b_in, c_in
Toffoli b_in, c_in, c_out
Toffoli L, xlt_l, c_in
Toffoli b_in, c_in, c_out
Toffoli L, xlt_l, b_in
Toffoli b_in, c_in, c_out
Toffoli L, xlt_l, b_in
endif
if a == 2//10
SigmaX xlt_l
CNot b_in, c_in
Toffoli b_in, c_in, c_out
Toffoli L, xlt_l, c_in
Toffoli b_in, c_in, c_out
Toffoli L, xlt_l, b_in
Toffoli b_in, c_in, c_out
Toffoli L, xlt_l, b_in
SigmaX xlt_l
endif
endproc
// This is a semi-quantum halfadder. It adds to b_in
// a c-number. Carry-in bit is c_in and carry_out is
// not necessary. xlt-l and L are enablebits. See
// documentation for further information
proc muxha a, b_in, c_in, xlt_l, L, total //a,
if a == 0//00
CNot b_in, c_in
endif
if a == 3//11
CNot L, c_in
CNot b_in, c_in
endif
if a == 1//01
Toffoli L, xlt_l, c_in
CNot b_in, c_in
endif
if a == 2//10
SigmaX xlt_l
Toffoli L, xlt_l, c_in
CNot b_in, c_in
SigmaX xlt_l
endif
endproc
// just the inverse of the semi quantum-halfadder
proc muxha_inv a, b_in, c_in, xlt_l, L, total //a,
if a == 0//00
CNot b_in, c_in
endif
if a == 3//11
CNot b_in, c_in
CNot L, c_in
endif
if a == 1//01
CNot b_in, c_in
Toffoli L, xlt_l, c_in
endif
if a == 2//10
SigmaX xlt_l
CNot b_in, c_in
Toffoli L, xlt_l, c_in
SigmaX xlt_l
endif
endproc
//
proc madd a, a_inv, width
total = num_regs * width + 2
for i = 0; i < width - 1; i++
if (1 << i) & a
j = 1 << 1
else
j = 0
endif
if (1 << i) & a_inv
j += 1
endif
muxfa j, width + i, i, i + 1, 2 * width, 2 * width + 1, total
endfor
j = 0
if (1 << (width - 1)) & a
j = 2
endif
if (1 << (width - 1)) & a_inv
j += 1
endif
muxha j, 2 * width - 1, width - 1, 2 * width, 2 * width + 1, total
endproc
proc madd_inv a, a_inv, width
total = num_regs * width + 2
j = 0
if (1 << (width - 1)) & a
j = 2;
endif
if (1 << (width - 1)) & a_inv
j += 1;
endif
muxha_inv j, width - 1, 2 * width - 1, 2 * width, 2 * width + 1, total
for i = width - 2; i >= 0; i--
if (1 << i) & a
j = 1 << 1
else
j = 0
endif
if (1 << i) & a_inv
j += 1
endif
muxfa_inv j, i, width + i, width + 1 + i, 2 * width, 2 * width + 1, total
endfor
endproc
proc addn N, a, width //add a to register reg (mod N)
test_sum N - a, width //xlt N-a
madd (1 << (width)) + a - N, a, width //madd 2^K+a-N
endproc
proc addn_inv N, a, width //inverse of add a to register reg (mod N)
CNot 2 * width + 1, 2 * width //Attention! cnot gate instead of not, as in description
madd_inv (1 << (width)) - a, N - a, width //madd 2^K+(N-a)-N = 2^K-a
swaptheleads width
test_sum a, width
endproc
proc add_mod_n N, a, width //add a to register reg (mod N) and clear the scratch bits
addn N, a, width
addn_inv N, a, width
endproc
proc emul a, L, width
for i = width - 1; i >= 0; i--
if (a >> i) & 1
Toffoli 2 * width + 2, L, width + i
endif
endfor
endproc
proc muln N, a, ctl, width //ctl tells, which bit is the external enable bit
L = 2 * width + 1
Toffoli ctl, 2 * width + 2, L
emul a % N, L, width
Toffoli ctl, 2 * width + 2, L
for i = 1; i < width; i++
Toffoli ctl, 2 * width + 2 + i, L
add_mod_n N, ((1 << i) * a) % N, width
Toffoli ctl, 2 * width + 2 + i, L
endfor
endproc
proc muln_inv N, a, ctl, width //ctl tells, which bit is the external enable bit
L = 2 * width + 1
a = QMath.inverseMod(N, a)
for i = width - 1; i > 0; i--
Toffoli ctl, 2 * width + 2 + i, L
add_mod_n N, N - ((1 << i) * a) % N, width
Toffoli ctl, 2 * width + 2 + i, L
endfor
Toffoli ctl, 2 * width + 2, L
emul a % N, L, width
Toffoli ctl, 2 * width + 2, L
endproc
proc mul_mod_n N, a, ctl, width
muln N, a, ctl, width
swaptheleads_omuln_controlled ctl, width
muln_inv N, a, ctl, width
endproc
proc exp_mod_n N, x, width_input, width
SigmaX 2 * width + 2
for i = 1; i <= width_input; i++
f = x % N //compute
for j = 1; j < i; j++
f *= f //x^2^(i-1)
f = f % N
endfor
mul_mod_n N, f, 3 * width + 1 + i, width
endfor
endproc
proc FindFactors N
x = 0
if N < 15
Print "Invalid number!"
Breakpoint
endif
width = QMath.getWidth(N * N)
swidth = QMath.getWidth(N)
for x; (QMath.gcd(N, x) > 1) || (x < 2); x
x = Math.floor(Math.random() * 10000) % N
endfor
Print "Random seed: " + x
for i = 0; i < width; i++
Hadamard i
endfor
ShiftLeft 3 * swidth + 2
exp_mod_n N, x, width, swidth
for i = 0; i < 3 * swidth + 2; i++
MeasureBit i
endfor
ShiftRight 3 * swidth + 2
InvQFT 0, width
for i = 0; i < width / 2; i++
CNot i, width - i - 1
CNot width - i - 1, i
CNot i, width - i - 1
endfor
for trycnt = 100; trycnt >= 0; trycnt--
Measure
c = measured_value
if c == 0
Print "Measured zero, try again."
continue
endif
q = 1 << width
Print "Measured " + c + " (" + c / q + ")"
tmp = QMath.fracApprox(c, q, width)
c = tmp[0];
q = tmp[1];
Print "fractional approximation is " + c + "/" + q
if (q % 2 == 1) && (2 * q < (1 << width))
Print "Odd denominator, trying to expand by 2."
q *= 2
endif
if q % 2 == 1
Print "Odd period, try again."
continue
endif
Print "Possible period is " + q
a = QMath.ipow(x, q / 2) + 1 % N
b = QMath.ipow(x, q / 2) - 1 % N
a = QMath.gcd(N, a)
b = QMath.gcd(N, b)
if a > b
factor = a
else
factor = b
endif
if (factor < N) && (factor > 1)
Display "<h2>Success: " + factor + " " + N / factor
Breakpoint
else
Print "Unable to determine factors, try again."
continue
endif
endfor
endproc
VectorSize 22
FindFactors 15