I've seen in multiple places stating that factoring is in BQP and referencing Shor's algorithm, but Shor's algorithm is not solving a decision problem. How can factoring be restated in a decision problem? And is there a paper which shows that Shor's algorithm implies this decision problem is in BQP?
$\begingroup$
$\endgroup$
2
-
5$\begingroup$ As Jeffrey Shality said, it is indeed in BQP. I just want to point you to some online discussions: rjlipton.wordpress.com/2011/01/23/… rjlipton.wordpress.com/2011/01/25/factoring-is-in-bqp $\endgroup$– user2917198Commented Aug 7, 2014 at 12:32
-
4$\begingroup$ This seems to be all addressed on wikipedia (en.wikipedia.org/wiki/…). How to turn factoring into a decision problem is definitely not research level. I am not sure the quantum part is either, but Lipton did need a clarification, so I guess that's fine. $\endgroup$– Sasho NikolovCommented Aug 7, 2014 at 14:41
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
0
Here the goal is to construct a decision problem D so that (a) if you can factor you can solve the decision problem in polynomial time and (b) if you can solve the decision problem you can factor in polynomial time. There are a number of ways to do this. To name just two:
- D: given n and k, does n have a divisor d satisfying 1 < d <= k?
- D: given n and j, is the j'th bit of the smallest nonunit divisor of n equal to 1?
If you can solve 1, then you can identify d using binary search. Once you have d, you can then continue with n/d until the complete factorization is achieved. 2 is similar.
$\begingroup$
$\endgroup$
Yes, there is a paper by John Watrous, which formally addresses the concerns raised on Lipton's blog (reported in user2917198's comment).
Here is the reference: J. Watrous. An introduction to quantum information and quantum circuits. ACM SIGACT News 42(2): 52–67, 2011. https://cs.uwaterloo.ca/~watrous/Papers/IntroductionQuantumCircuits.pdf
As pointed out in the Introduction of the paper, the issues are not specific to Factoring/BQP, but more in general, «they concerns basic manipulations of quantum circuits».
If you just wanted to see how to cast the factoring problem in a decision problem, refer to Jeffrey Shallit's answer.
answered Aug 7, 2014 at 14:24
$\begingroup$
$\endgroup$
1
In fact, given natural numbers $x$ and $N$, deciding whether $x$ is a square modulo $N$ or not is a typical decision problem. If you can solve this problem efficiently, then you can factor $N$ efficiently, too.
-
5$\begingroup$ No. This is the quadratic residuosity problem, which is assumed intractable, but not known to be as hard as factoring. You are confusing it with the problem of computing square roots modulo $N$, which is equivalent to factoring up to randomized polynomial-time reductions, but is not a decision problem. $\endgroup$ Commented Nov 5, 2014 at 16:03
$\begingroup$
$\endgroup$
If I understand correctly, factoring can be encoded as SAT decision problem and then recover the actual solution. For unknown $x,y$ and given $N$, encode to SAT the problem $ x \cdot y = N, x > 1 , y > 1$. Basically all you need is an adder circuit and few gates. Call the resulting formula $\phi$. If $\phi$ is satisfiable, then $N$ is composite. Set the first bit of $x$ to $1$ and check if $\phi'$ is satisfiable. If it is, you guessed correctly and try with the second bit. Otherwise set it to $0$ and continue with the second bit. This is linear in the numbers of bits.
(Actually in practice real SAT solvers will give you the complete solution if it exists).
