1

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?

Community
  • 1
  • 1
kptlronyttcna
  • 1,461
  • 1
  • 16
  • 22
  • 1
    You don't need 4^n bits to simulate an n-qubit quantum computer. BQP is in PSPACE. You can simulate an n-qubit quantum computers with O(n) bits, using path integrals. But, that said, path integrals will be even slower than the naive simulation that does require 2^n bits. – Craig Gidney Jan 14 '17 at 00:33

2 Answers2

0

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.

Ordoshsen
  • 650
  • 3
  • 15
-1

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

Rajeev Misra
  • 7
  • 2
  • 1
    The linked video doesn't make any sense - it must be a crackpot or a fraud. He is running Shor's algorithm on a quantum computer simulator (not a quantum computer), which means that there is *no* speedup compared to a classical algorithm. Extremely unlikely that he cracked RSA this way. Shor's algorithm requires way more *logical* qubits than any current quantum computer has, or likely will have in our lifetimes. – James Apr 27 '20 at 10:40