3
$\begingroup$

I've been learning Qiskit and I decided to implement Beauregard's 2n+3 description of Shor's algorithm to factor an n-bit integer.

I've successfully created a modular multiplication gate, using my reading of Beauregard's paper. By applying this multiple times, I can achieve exponentiation. For example for 7^x (mod 15), my gates will generate the correct cycle of 7, 4, 13, 1.

Putting these things together, I've been trying to construct the circuit to estimate the period of my gate. This is the model for a circuit that Shor and Beauregard described. I have opted to use an additional 2n qubits as controls, rather than deal with measurement resetting, as is required for the '2n + 3 qubits' claim.

What I do not understand is why my circuit does not give the correct measurements. When I run the circuit, I get an odd assortment of values that do not correspond to correct multiples of the reciprocal of the period: s*Q/r for integers s and Q=2^a is the power of two corresponding to the number of controls. The values it currently gives are clustered near 11111111 and 0000000.

I attach an image for the circuit diagram below. I have used my own implementation of the Fourier transform, but I am satisfied that this is correct as it can successfully inverse the inbuilt version.

Would you be able to suggest to me some other avenues that I could go down, to see how I might learn to correct my errors and understand why my circuit is incorrect? Diagram of circuit for Shor's algorithm

EDIT: As reccomended, I will post the script creating the above circuit diagram and generating the incorrect outputs I've described.

This code is written in Qiskit and takes input integers. The input integers are the number to factor (15), the 'guess' integer, which I have labelled as 'addend'. This is (7). Finally, it also takes the multiplicative inverse of the addend within the modulus. This would be (13) as 13 * 7 = 1 (mod 15).

The script: https://codeberg.org/eecily/Shor/src/branch/main/shor_algorithm

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Could you post the code? Without being able to tell how you've implemented your oracles it's pretty difficult to tell you where you've gone wrong. Also with make sure the endianness of your output is being correctly interpreted. It's commonly overlooked. $\endgroup$ Commented Mar 1 at 18:35
  • $\begingroup$ @broncosaurus Yes, that is a terribly good idea. I have edited my post to include a link to a CodeBerg repository, including the Qiskit script. I include it here as well: codeberg.org/eecily/Shor/src/branch/main/shor_algorithm edit: the endianness was definitely my first port of call, however I do not presently see that this would be the case. They are just measurements clusered around either 00000000 or 11111111, not inbetween at all. $\endgroup$ Commented Mar 2 at 12:04

1 Answer 1

Reset to default
3
$\begingroup$

After running your code, it seems that your IQFT is implemented incorrectly I replaced lines 363 through 366 of the linked file with

from qiskit.circuit.library import QFT iqft = QFT(2*nqubits).inverse()

and am getting the correct result. I also removed a number of print statements and the specifications of using a Nvidia GPU but I don't believe this is affecting the output.

It's important to note that QFTs can be different in terms of their chosen basis and their endianness. The method "iqft_me" does not flip the endianness of the system back which is needed for the qubits to have the correct basis. Please the image for the difference.

enter image description here

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.