Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question
5  
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 –  user2917198 Aug 7 at 12:32
3  
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. –  Sasho Nikolov Aug 7 at 14:41

3 Answers 3

up vote 12 down vote accepted

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:

  1. D: given n and k does n have a divisor d satisfying 1 < d <= k?
  2. D: given n and j is the j'th bit of the smallest 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.

share|improve this answer

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.

share|improve this answer

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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.