Skip to main content
Quantum Computing

Return to Question

tag to quantum algorithms added
Link
edit approved Jan 21, 2019 at 4:33
MartinQuantum
edit approved Jan 21, 2019 at 4:33
MartinQuantum
  • 765
  • 5
  • 9
edited tags
Link
Sanchayan Dutta
Sanchayan Dutta
  • 17.8k
  • 8
  • 49
  • 111
added 32 characters in body
Source Link
Sanchayan Dutta
Sanchayan Dutta
  • 17.8k
  • 8
  • 49
  • 111

How many logical qubits are needed to run Shor's algorithm efficiently on large integers (n$n > 2^10242^{1024}$)?

First, I know there are differences in logical qubits and physical qubits. It takes more physical qubits for each logical qubit due to quantum error.

Wikipedia states that it takes quantum gates of order O((log N)^2(log log N)(log log log N)$\mathcal{O}((\log N)^2(\log \log N)(\log \log \log N)$ using fast multiplication for Shor's Algorithm. That comes out to 1,510,745$1,510,745$ gates for 2^1024$2^{1024}$. Further down the article, it says that it usually take n^3$n^3$ gates for n$n$ qubits. This would mean it would take ~115~$115$ qubits.

However, I've run Shor's Algorithm as implemented in Q# samples using Quantum Phase Estimation and it comes out to 1025$1025$ qubits.

How many logical qubits are needed to run Shor's algorithm efficiently on large integers (n > 2^1024)?

First, I know there are differences in logical qubits and physical qubits. It takes more physical qubits for each logical qubit due to quantum error.

Wikipedia states that it takes quantum gates of order O((log N)^2(log log N)(log log log N) using fast multiplication for Shor's Algorithm. That comes out to 1,510,745 gates for 2^1024. Further down the article, it says that it usually take n^3 gates for n qubits. This would mean it would take ~115 qubits.

However, I've run Shor's Algorithm as implemented in Q# samples using Quantum Phase Estimation and it comes out to 1025 qubits.

How many logical qubits are needed to run Shor's algorithm efficiently on large integers ($n > 2^{1024}$)?

First, I know there are differences in logical qubits and physical qubits. It takes more physical qubits for each logical qubit due to quantum error.

Wikipedia states that it takes quantum gates of order $\mathcal{O}((\log N)^2(\log \log N)(\log \log \log N)$ using fast multiplication for Shor's Algorithm. That comes out to $1,510,745$ gates for $2^{1024}$. Further down the article, it says that it usually take $n^3$ gates for $n$ qubits. This would mean it would take ~$115$ qubits.

However, I've run Shor's Algorithm as implemented in Q# samples using Quantum Phase Estimation and it comes out to $1025$ qubits.

Source Link
LeWoody
LeWoody
  • 904
  • 1
  • 8
  • 14