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?
11
$\begingroup$
$\endgroup$
-
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♦ Jul 18 '16 at 21:45
12
$\begingroup$
$\endgroup$
- 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.
answered Apr 20 '15 at 6:50
