# Has there been any truly ground breaking advance in quantum algorithms since Grover and Shor?

(Sorry for a somewhat amateurish question)

I studied quantum computing from 2004 to 2007, but I've lost track of the field since then. At the time there was a lot of hype and talk of QC potentially solving all sorts of problems by outperforming classical computers, but in practice there were really only two theoretical breakthroughs:

• Shor's algorithm, which did show significant speed up, but which had limited applicability, and wasn't really useful outside of integer factorization.
• Grover's algorithm, which was applicable to a wider category of problems (since it could be used to solve NP-Complete problems), but which only showed polynomial speed-up compared to classical computers.

Quantum annealing was also discussed, but it wasn't clear whether it was really better than classical simulated annealing or not. Measurement based QC and the graph state representation of QC were also hot topics, but nothing definitive had been proved on that front either.

Has any progress in the field of quantum algorithms been made since then? In particular:

• Have there been any truly ground breaking algorithms besides Grover's and Shor's?
• Has there been any progress in defining BQP's relationship to P, BPP and NP?
• Have we made any progress in understanding the nature of quantum speed up other than saying that "it must be because of entanglement"?
• It's good question, Alex. It certainly isn't amateurish. Sep 25 '18 at 20:56

Have there been any truly ground breaking algorithms besides Grover's and Shor's?

It depends on what you mean by "truly ground breaking". Grover's and Shor's are particularly unique because they were really the first instances that showed particularly valuable types of speed-up with a quantum computer (e.g. the presumed exponential improvement for Shor) and they had killer applications for specific communities.

There have been a few quantum algorithms that have been designed since, and I think three are particularly worthy of mention:

• The BQP-complete algorithm for evaluating the Jones polynomial at particular points. I mention this because, aside from more obvious things like Hamiltonian simulation, I believe it was the first BQP-complete algorithm, so it really shows the full power of a quantum computer.

• The HHL algorithm for solving linear equations. This is a slightly funny one because it's more like a quantum subroutine, with quantum inputs and outputs. However, it is also BQP-complete and it's receiving a lot of attention at the moment, because of potential applications in machine learning and the like. I guess this is the best candidate for truly ground breaking, but that's a matter of opinion.

• Quantum Chemistry. I know very little about these, but the algorithms have developed substantially since the time you mention, and it has always been cited as one of the useful applications of a quantum computer.

Has there been any progress in defining BQP's relationship to P, BPP and NP?

Essentially, no. We know BQP contains BPP, and we don't know the relation between BQP and NP.

Have we made any progress in understanding the nature of quantum speed up other than saying that "it must be because of entanglement"?

Even back when you were studying it originally, I would say it was more precisely defined than that. There are (and were) good comparisons between universal gate sets (potentially capable of giving exponential speed-up) and classically simulable gate sets. For example, recall that the Clifford gates produce entanglement but are classically simulable. Not that it's straightforward to state precisely what is required in a more pedagogical manner.

Perhaps where some progress has been made is in terms of other models of computation. For example, the model DQC1 is better understood - this is a model that appears to have some speed-up over classical algorithms but is unlikely to be capable of BQP-complete calculations (but before you get drawn into the hype that you might find online, there is entanglement present during the computation).

On the other hand, the "it's because of entanglement" sort of statement still isn't entirely resolved. Yes, for pure state quantum computation, there must be some entanglement because otherwise the system is easy to simulate, but for mixed separable states, we don't know if they can be used for computations, or if they can be efficiently simulated.

Also, one might try to ask a more insightful question: Have we made any progress in understanding which problems will be amenable to a quantum speed-up? This is subtly different because if you think that a quantum computer gives you new logic gates that a classical computer doesn't have, then it's obvious that to get a speed-up, you must use those new gates. However, it is not clear that every problem is amenable to such benefits. Which ones are? There are classes of problem where one might hope for speed-up, but I think that still relies on individual intuition. That can probably still be said about classical algorithms. You've written an algorithm x. Is there a better classical version? Maybe not, or maybe you're just not spotting it. That's why we don't know if P=NP.

• but for mixed separable states, we don't know if they can be used for computations, or if they can be efficiently simulated: what do you mean here exactly? If the states remain separable, why can they not be efficiently simulated? Does it not amount to simply simulating the pure separable states whose mixture gives the state? If they do not remain separable, then we go back to the case in which entanglement is involved.
– glS
Sep 22 '18 at 19:34
• @glS The question is how many pure states you need to describe the mixed state. If it’s a small number, your argument works, but what if it’s a large number? Sep 22 '18 at 19:47
• I thought a bound could be put on the number of separable pure states needed to decompose an arbitrary separable state? See physics.stackexchange.com/a/401770/58382
– glS
Sep 23 '18 at 10:46
• Ah, I get it, the number of pure separable states in the decomposition of a mixed state is bounded by roughly the square of the dimension of the Hilbert space, thus simulating an $n$-qubit state this way could require time exponential in $n$.
– glS
Sep 24 '18 at 9:37

The Kerenidis-Prakash algorithm was groundbreaking, until Ewin Tang fixed the ground back up: