patternModerate
What type of algorithms are faster with a quantum computer?
Viewed 0 times
whatarewithalgorithmstypefastercomputerquantum
Problem
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?
Solution
- 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.
Context
StackExchange Computer Science Q#41581, answer score: 13
Revisions (0)
No revisions yet.