11
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 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, 2015 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, 2015 at 4:03
  • $\begingroup$ As far as I know, none. We need new algorithms. (cf Yuval's first comment.) $\endgroup$
    – Raphael ♦
    Apr 20, 2015 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, 2015 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, 2016 at 21:45

1 Answer 1

Reset to default
13
$\begingroup$
  • 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.
Improve this answer
$\endgroup$

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.