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?


4 Answers 4


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


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.


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$ Nov 5, 2014 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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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