Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
As Jeffrey Shality said, it is indeed in BQP. I just want to point you to some online discussions:… – user2917198 Aug 7 '14 at 12:32
This seems to be all addressed on wikipedia (…). 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 '14 at 14:41
up vote 16 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|cite|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.

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|cite|improve this answer

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.

share|cite|improve this answer
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. – Emil Jeřábek Nov 5 '14 at 16:03

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|cite|improve this answer

Your Answer


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.