How many qubits do I need to factor 15 using shor's algorithm?

Question

According to this, I understand we need 4^n bits to simulate an n-qubit quantum computer. I was wondering if it's possible to simulate shor's algorithms on a classical computer to factor 15? How many qubits is required to factor 15 using shor's algorithm?

Answer 1

Quantum computers much like classical ones can with n bits present 2^n different values. Shor's algorithm at the "Period-finding subroutine" uses two registers, possibly as big as 2n + 1 where n is number of bits needed to represent the number to factor. In total you need 4n + 2 qubits to run Shor's algorithm.

There was some work done on lowering the qubit requirements. That implementation works with just 2n + 3 qubits for general number.

To asnwer your question, you would need 4 classical (or quantum) bits to represent 15 and thus want 62 qubits with the basic algorithm (you would possibly not use some). There are of course some workarounds on this and there were successfull experimental implementations that used as few as 7 qubits because of special properties of 15 known beforehand, but that cannot be used on general number factored with Shor's algorithm.

When you simulate quantum computer on classical one, you usually want to represent it with state space where each base state corresponds with one possible output. This needs 2^n dimensional vectors of imaginary numbers, the actual number of bits depends on your implementation of vectors and imaginary numbers.

Answer 2

The answer to your question is - to factor 15 (5 bit number) you need two times that i.e. 10 Qubits.

Please see this video for details on how the shors algorithm works. That should clarify your doubts if you see it in action yourself.

The Largest Arbitrary RSA Modulo Cracked using a Pure/Undiluted/Reference Implementation of Shor's Algorithm as of 13th Dec 2018 is 2048 bits. RSA-2048 stands cracked. Please see the demo of the implementation which was used in cracking RSA - 2048 https://vimeo.com/306770425