Integer Factorization by Quantum Measurement

🧮 Summary

1. Build a Quantum Hilbert Space from the Tensor product $\tilde{H}={\tilde{H}}_1\otimes {\tilde{H}}_2$ of two systems given by Hamiltonians ${\tilde{H}}_1$ and ${\tilde{H}}_2$. For a chosen $m\in {\mathbb{Z}}^{+}$
   1. ${\tilde{H}}_1$ has eigenvalues given by $\log p_i,i\in \{1,2,...m\}$
   2. ${\tilde{H}}_2$ has eigenvalues given by $\log j,j\in \{1,2,...m\}$
   3. The two systems above can be realised using either Supersymmetric Quantum Mechanics. This can be done more efficiently using a result from Quantum algorithm for nonlinear differential equations
2. We build a Measurement operator with energy level $\log N$. Given our initial setup of $\tilde{H}$, $|\log N⟩$ is described as ${\sum }_{i,j}|\log p_i⟩|\log j⟩$. After measurement, we get a value $|\log p_i⟩$, i.e. we get a prime factor of $N$ 🎉

The above only describes the algorithm used. The paper also addresses physical implementation and Time Complexity considerations.