thyung / qiskit_factorization Goto Github PK

This project explains Shor's algorithm for factorization, the mathematics principle, link to quantum mechanics and implementation the algorithm with qiskit. There are 4 chapters where first 3 explain the concept and last chapter is executable jupyter notebook using qiskit. https://qiskit.org/documentation/getting_started.html provides qiskit installation instruction.

1. Chapter 1 describes the steps of Shor's algorithm.
2. Chapter 2 explains the mathematics principle of transforming factorization problem to period finding.
3. Chapter 3 shows that given unitary operator to calculate $f_N(x)=a^x \mod N$ and QFT, one can find the period of $f_N(x)$
4. Chapter 4 implements QFT and unitary operator $f_N$ with qiskit.

Some examples were run with qiskit qasm_simulator on M1 Macbook, Pixelbook and i7-4790 ubuntu PC. The CPU time grows exponentially with number of qubits. In the test, N fits within $2^n$ and $x$ in $a^x \mod N$ run over a range of $2^{n_x}$.

Remark *: due to unknown reason, allocate (n, nx)=(4, 8) qubits caused M1 and i7-4790 run forever while (n, nx)=(5, 8) run normally.

N. David Mermin, Quantum Computer Science: An Introduction

Vlatko Vedral, Adriano Barenco and Artur Ekert, Quantum Networks for Elementary Arithmetic Operations

Stackexchange, Is there a simple, formulaic way to construct a modular exponentiation circuit?

Qiskit get start