I am a beginning CS student and I am learning algorithms. I heard that even with quantum computers, that general sorting algorithms can never have better than $n\log n$ time. However, I also know that factoring algorithms would be a lot faster. In general terms what kind of algorithms would become substantially faster with quantum computers?

  • 1
    $\begingroup$ I suggest you rephrase your question. You are really asking which problems can be solved faster with quantum computers. $\endgroup$ – Yuval Filmus Apr 20 '15 at 3:59
  • 1
    $\begingroup$ Scott Aaronson (the quantum computing guru) has (two versions of a) talk about this subject exactly, titled *When exactly do quantum computers provide a speedup?". You can find it (or rather, them) here: scottaaronson.com/talks. $\endgroup$ – Yuval Filmus Apr 20 '15 at 4:03
  • $\begingroup$ As far as I know, none. We need new algorithms. (cf Yuval's first comment.) $\endgroup$ – Raphael Apr 20 '15 at 8:46
  • $\begingroup$ it is not actually proven that factoring is faster, only conjectured, etc., its an open question P ?= BQP etc $\endgroup$ – vzn Apr 20 '15 at 15:17
  • $\begingroup$ Closely related: Why and how is a quantum computer faster than a regular computer? $\endgroup$ – Gilles 'SO- stop being evil' Jul 18 '16 at 21:45
  • Shor's algorithm which puts FACTORING in BQP (bounded error quantum polynomial-time, effectively the quantum equivalent of P) also can be used to solve the DISCRETE LOGARITHM problem, where we want to find an integer $k$ such that $a^{k} = b$ where $a$ and $b$ are given, in (quantum) polynomial time. The DISCRETE LOGARITHM problem has the same status as the FACTORING problem in that we don't know whether they are polynomial-time solvable, so this might not be a speed up.
  • Grover's algorithm gives a quadratic speed up in searching unsorted lists (which can be used as a speed up for a lot of algorithms).
  • Simulating quantum systems is also in BQP, but exponentially slower on a classical TM.
  • Solving Pell's equation (not really one equation) is in BQP, another exponentially speed-up.
  • There's also a number of other, more obscure, problems that are in BQP, but appear not to be in P. Wocjan and Zhang give a good starting point to dig them up.
| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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