Quantum factoring algorithm.
The query complexity is lower in the case of Shor's algorithm than with a classical algorithm.
The tool can used by clicking on the images beside. It allows you to see Shor's algorithm, by choosing the parameters:
N : the number to factorise, and A, a number such as 1 < a < N.
Next using Euclid's algorithm (which is a poly-time algorithm) we compute the greatest common divisor b = gcd(a,N).
If b > 1 we are finished. Thus suppose b = 1 i.e. a and N are coprime.
Each time you click on the checkbox matching the first measure, you will get a new estimation of the period.
Note: It is implied that you know the principles of this algorithm.
For more details, cf. the end of this page.
Like for Simon's algorithm, in order to see the quantum entanglement, you only need to rollover the registers before the measure-checkbox.
Quantum Fourier transform
The circuit representing it is in the two last panels before the last measure.
To see what happens, you can enlarge the panels by clicking anywhere inside.
Then roll over from the bottom to the top of the base-vectors of the right panel: the matrix appears in the left panel.
For the moment, the qubits in input are not shown.
Note: This tool has still some little bugs
: no input controls,
sometimes strange random numbers,
unskilful zooms...
It can then be enhanced but the principle is there ;)
|
|
|
preamble
quantum algorithms
Deutsch-Jozsa
Shor