# Shor's Number Factoring

Enter an integer in the box and our quantum emulator will factor your integer using Shor's algorithm. To learn more, have a look at our explanation which follows.

Results
N
a
No. Qubits
Order
Factors
Time per run (s)

We are emulating a quantum computer which, in conjunction with a classical computer, implements Peter Shor's complete factoring algorithm [Shor, 1998]. Shor's publication of his algorithm first propelled quantum computing into commercial attention since its implementation would mean the end of existing cryptographic protocols (to protect online payments, say) based precisely on the difficulty of factoring. The most well-known of these is the RSA cryptosystem.

First the classical computer randomly chooses a number between $$2$$ and $$N-1$$. In the results table we denote this by $$a$$. If $$a$$ shares a factor with the input $$N$$, then great you’ve just found a factor so you don’t need to run Shor’s algorithm. Otherwise we can get started and emulate the quantum computer. We emulate a quantum computer which uses quantum effects to generate fractions that are likely to be close to a random multiple of $$1/r$$ less than $$1$$. The bars in the above graph are based at these generated fractions multiplied by $$2^t$$, where $$t=2n$$ is the number of qubits used for measurement, and $$n$$ is the number of bits needed to represent $$N$$. Their height gives the frequency of generation. A green bar indicates that our classical computer was able to correctly calculate $$r$$ from the bar's fraction $$\psi$$. A red bar indicates it was not possible to find $$r$$ from $$\psi$$. That not all $$\psi$$ lead to $$r$$ is characteristic of the probabilistic nature of a quantum computer. If $$r$$ is even and $$x^{r/2}$$ does not give remainder $$N-1$$ upon division by $$N$$, then the greatest common factor of $$x^{r/2}-1$$ and $$N$$ gives a desired factor of $$N$$. In this case, the factors are given in the table above.

# Chemical Energy Estimation

Choose one of the chemical compounds below. Our quantum emulator will compute its ground state energy using the quantum phase estimation algorithm. Observe that in most instances the blue crosses decrease below the red line, what this means is explained below.

Select molecule

Here, our quantum emulator computes the ground state energy of molecules as prescribed by [Aspuru-Guzik et al., 2006] and uses the Bayesian quantum phase estimation algorithm of [Wiebe and Granade, 2016] at its core. Many molecular properties of interest, not least ionisation energies, can be easily obtained from its ground state energy, that is the lowest energy an electron may occupy. In our graph, the horizontal red line represents the error of the Hartree-Fock (HF) energy, a widely used classical approximation to the true ground state energy. Each one of the three traces shows the quantum computer's error following consecutive measurements for one run of the Bayesian quantum phase estimation algorithm. In most cases, the quantum computer surpasses the classical computer in accuracy after only a few measurements. For some runs, the accuracy does not exceed that of the classical computer - this is due to the intrinsic probabilistic nature of quantum computers and can be fixed by simply repeating the experiment. It is important to now caveat that while HF energies are commonly used, they are far from the "best known" classical solution. Our emulator uses OpenFermion.

R&D Team @ River Lane Research

Oscar Higgott

Daochen Wang

Stephen Brierley