[Solved]: What type of algorithms are faster with a quantum computer?

Problem Detail: 

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?

Asked By : hgund

Answered By : Luke Mathieson

• 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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41581

 Ask a Question

 Download Related Notes/Documents