<p>Does Shor's algorithm produce factors of a $n$-bit number and discrete log modulo $n$-bit prime in $O((\log n)^{2+\epsilon})$ bit operations using fast multiplication? I am trying to read from <a href="https://en.wikipedia.org/wiki/Shor%27s_algorithm" rel="nofollow">wikipedia</a>. If not what is the 'right' number of comparable 'bit' operations in the classical model? </p>

<p>What is the hidden constant in $O((\log n)^{2+\epsilon})$?</p>

<p>As far as we know the $2$ in the exponent could be brought down to $1$. There have been many techniques in classical factoring/discrete log calculation that tried to reduce complexity over many decades. Has there been any attempt to bring the exponent from $2$ down to $1$? Or is there a proof that $2$ is the best that can be done?</p>

CC BY-SA 3.0
2015-07-31T11:32:49.700Z
Could you provide the reference for that bound?
Juan Bermejo Vega
CC BY-SA 3.0
2015-07-31T12:52:17.017Z
Yes, people have tried to bring the exponent on the $\log$ down. And there's no proof that 2 is the best possible.
Peter Shor 
CC BY-SA 3.0
2015-07-31T13:04:47.027Z
@PeterShor Thank you is there a reference on such attempted lower bounds or upper bounds?
Turbo
CC BY-SA 3.0
2015-07-31T16:30:42.293Z
Since people don't usually write up unsuccessful attempts, one wouldn't expect to find references.
Peter Shor 
CC BY-SA 3.0
2015-07-31T23:23:18.447Z
@PeterShor Thank you. Is the hidden constant very small?
Turbo
CC BY-SA 3.0
2016-08-11T08:35:47.253Z
@PeterShor I think $2$ cannot be lowered.
Turbo
<quantum-computing>
Two questions on Shor's algorithm
Turbo
# Two questions on Shor's algorithm

(Asked by: username_0 on 2015-07-31)

Does Shor's algorithm produce factors of a $n$-bit number and discrete log modulo $n$-bit prime in $O((\log n)^{2+\epsilon})$ bit operations using fast multiplication? I am trying to read from [wikipedia](https://en.wikipedia.org/wiki/Shor%27s_algorithm). If not what is the 'right' number of comparable 'bit' operations in the classical model?

What is the hidden constant in $O((\log n)^{2+\epsilon})$?

As far as we know the $2$ in the exponent could be brought down to $1$. There have been many techniques in classical factoring/discrete log calculation that tried to reduce complexity over many decades. Has there been any attempt to bring the exponent from $2$ down to $1$? Or is there a proof that $2$ is the best that can be done?

**Tags:** quantum-computing

> **Comments:**
> **username_1**: Could you provide the reference for that bound?  
> **username_2**: Yes, people have tried to bring the exponent on the $\log$ down. And there's no proof that 2 is the best possible.  
> **username_0**: @PeterShor Thank you is there a reference on such attempted lower bounds or upper bounds?  
> **username_2**: Since people don't usually write up unsuccessful attempts, one wouldn't expect to find references.  
> **username_0**: @PeterShor Thank you. Is the hidden constant very small?  
> **username_0**: @PeterShor I think $2$ cannot be lowered.  

---

## 0 answers

