My question is definitely regarding quantum-speedup but the quantum-speedup tag is confined to algorithms... and my question is definitely not on algorithms. So, this is just my best shot at tagging.

This article in Physics World discusses quantum speedup and makes some pretty provocative statements (examples below).

It also tells me that people in a forum like this one might feel as follows: “Some feel that this debate about the “how” of quantum computation is a red herring. “Researchers attending most conferences in quantum computing never mention these issues, or only in discussions over beer”.

Here are some of those "provocative statements".

“None of the explanations for how quantum computers achieve speed-up is universally accepted.”

“If it’s not from the vastness of Hilbert space, not from entanglement and not interference, then what? “As far as I am aware, right now it’s pretty silent in the theatre where this question is played out – that’s because the main candidates are all dead...”

Here are two specific questions. As a worker in this field, does the following statement from the 2014 Physics World article match your own perception here in 2018? If not, what are the favored candidates today? And again, this is not a question about speedups obtained via algorithmic refinement. Why exclude algorithmic refinement? See "Footnote".

"Deutsch’s notion of quantum parallelism has stuck – the standard explanation in popular descriptions of quantum-computing speed-up is still that massively parallel computation takes place..."

Footnote: Why exclude algorithmic refinements? Again from that article: “Designing good quantum algorithms is a very difficult task,” Van den Nest agrees. “I believe this task could be made lighter if we were to arrive at a systematic understanding of the possible ways to move from classical to quantum computing” – in other words, if we had a better grasp of which aspect of quantum physics the advantages ultimately stem from."

I just noticed that link is going be unfamiliar (to me too). So I vetted it just a little. The home page says: "Dr. Franco Nori is a RIKEN Chief Scientist, heading the “Theoretical Quantum Physics Laboratory” at the “Cluster for Pioneering Research” at Riken, Saitama, Japan. He is also at the University of Michigan, Ann Arbor, USA"

  • $\begingroup$ It is not just nonzero entanglement because of Gottesman-Knill theorem. Similarly that seems like the way to approach this kind of question. What can you do classically? If you can do some aspect classically, then it cannot be the cause of speedup, at least not by itself. $\endgroup$ – AHusain Oct 18 '18 at 20:05
  • 2
    $\begingroup$ What is your question? The only question mark I found in your article is inside a quote. $\endgroup$ – user1271772 Oct 18 '18 at 21:54
  • 1
    $\begingroup$ This post needs a bit of work, I think. It seems potentially opinion- based, and on top of not asking a definite question (as user1271772 notes), is very close to asking multiple questions. $\endgroup$ – Niel de Beaudrap Oct 19 '18 at 6:14
  • $\begingroup$ Welcome to Quantum Computing SE! Just to let you know, we're not a site for discussions as you'd have in a traditional 'forum' and instead we're designed for asking and answering specific, objective questions, If you want to take the tour to get what we're about in more detail, feel free to do so and if you edit this post so it contains a question we can objectively answer (as opposed to something to discuss), it'll automatically get put in a reopen queue. In the meantime, I'm putting this on hold in order to help prevent opinionated arguments that might not say what you're looking for $\endgroup$ – Mithrandir24601 Oct 19 '18 at 7:20
  • $\begingroup$ The same things can often be said about design of classical algorithms. There is no systematic understanding of fast classical algorithms. In fact proving general results about algorithmic speed ups is not easy. Also, I don't think that the argument made in the article about entanglement is in good faith. The paper by Van den Nest quoted in the article clearly states that the problem arises because we don't have good ways to measure multipartite entanglement. The recent paper "Quantum advantage with shallow circuits" gives an explicit instance where multipartite entanglement helps. $\endgroup$ – biryani Oct 19 '18 at 10:52

Browse other questions tagged or ask your own question.