# What type of algorithms are faster with a quantum computer?

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?

• I suggest you rephrase your question. You are really asking which problems can be solved faster with quantum computers. – Yuval Filmus Apr 20 '15 at 3:59
• 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. – Yuval Filmus Apr 20 '15 at 4:03
• As far as I know, none. We need new algorithms. (cf Yuval's first comment.) – Raphael Apr 20 '15 at 8:46
• it is not actually proven that factoring is faster, only conjectured, etc., its an open question P ?= BQP etc – vzn Apr 20 '15 at 15:17
• – 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.