2
$\begingroup$

The best deterministic factorization algorithm that is currently known runs in $O(N^{\frac{1}4+\epsilon})$ arithmetic steps.

Randomness and quantumness improves upon this.

I believe Quadratic/Number field sieve run in randomized subexponential time. What is it that quantumness provides that sieve techniques cannot provide? What exact barrier does Shor's algorithm break that randomness cannot?

Improve this question
$\endgroup$
1
  • 5
    $\begingroup$ Those three questions are not very related and probably should be separate questions.... $\endgroup$
    – usul
    Commented Jul 12, 2015 at 13:31

1 Answer 1

Reset to default
-1
$\begingroup$

What is it that quantumness provides that sieve techniques cannot provide?

It is more a question why quantum computers are believed to be more powerful than classical computation models. Short: Quantum computers provide superpositions of quantum states.

Randomized algorithms are restricted to be in a certain state with some (constant) error probablility. Quantumness provides the posibility of evaluating function on every possible state and afterwards measuring a certain state with some error probability.

What exact barrier does Shor's algorithm break that randomness cannot?

The quantum states represent the accepted states as well as the rejected states. Shor's algorithm evaluates the accepting states in such an extent that the accepting states are more likely to be measured. Also the quantum algorithm can manipulate all states at the same time. A randomized algorithm is bound to increase the probability of being in such a accepting state, looping often enough to get a certain probability (or extending some other variable).

Improve this answer
$\endgroup$
2
  • $\begingroup$ I think the answer is too vague to be of any help, although to be fair, the question is too broad as well. If I would replace factoring with almost any other problem, the same answer would hold. I believe also that definitively answering the questions posed is extremely difficult, since it would require essentially proving that $\mathbb{BPP} \neq \mathbb{BQP}$, since we cannot even exclude the possibility of an efficient deterministic algorithm for factoring, let alone a randomized one. The best I would hope as an answer is some kind of intuition. $\endgroup$
    – chazisop
    Commented Jul 14, 2015 at 9:36
  • 1
    $\begingroup$ chazisop is right, the answer does not really solve the question. Although i believe for the problem of factorization the question can be answered comparing shor to the sieve algorithms. Taken quantumness provides a solution for the abelian hidden subgroup problem, which cannot in such a way be computed with classical computation models. $\endgroup$
    – Fleeep
    Commented Jul 14, 2015 at 10:21

Your Answer

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

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