# Requirements for Achieving a Quantum Speedup

We usually talk about the power of a quantum computer by examining the separation between sets of gates that we know we can efficiently simulate on a classical computer (i.e. problems in the class BPP), and universal gate sets which, by definition, can implement any quantum algorithm, including BQP-complete algorithms. So, assuming a separation between BPP and BQP, there is a separation in the power of the algorithms that can be implemented with these gate sets, and the separation between these gate sets can be as simple as the availability of one gate (two classic examples are the Clifford gates + the $\pi/8$ phase gate, and Toffoli+Hadamard). In effect, you need a universal gate set in order to gain a computational speed-up. However, this is specifically about algorithms with polynomial running times.

What are the requirements that distinguish the power of a quantum computer which is intended solely to provide a polynomial speed-up on a problem outside BPP? For example, a device built solely for the purpose of implementing a Grover's search. Presumably the D-Wave machines fall into this category.

To be clear, I require a speed-up that changes the scaling relation. If there's a classical algorithm that requires time $O(2^n)$, then obviously there are many different ways of physically implementing it which have different running times, but all will be $O(2^n)$. I'm interested in identifying what it is in a quantum computer that permits a better scaling (but not a reduction to polynomial time running).

Asked another way: think about the D-wave machine (although I am not aiming to be limited to just talking about this case), which we believe is doing something coherent, and for a given problem size, seems to be quite speedy, but we don't know how it scales. Can we know a priori, from details of its architecture, that it at least has the potential to provide a speed-up over classical? If it were universal for quantum computation, then it certainly would have that potential, but universality probably isn't necessary in this context.

Part of what I'm struggling to get my head around, even in terms of defining the question properly, is that we don't have to have a universal gate set because it doesn't necessarily matter if the gate set can be efficiently simulated on a classical computer, just so long as the overhead in performing the simulation is similar or worse than the speedup itself.

• To facilitate the answer: is the polynomial speed-up the hard requirement here, or would a linear speed-up also be satisfactory? – agaitaarino Apr 13 '18 at 5:37
• @DaftWullie If we always talk about the computational complexity by space/time complexity, then does this means essentially complexity is related with spacetime structure? And accordingly the speedup of quantum computer beyond classical computers (in our trivial 4D spacetime structure) is based on their capability to break the trivial spacetime structure (by entanglement for example)? Then we need to check how a quantum algorithm can warp the spacetime and create spacetime shortcuts to speedup the computation. – XXDD Oct 30 '18 at 7:08
• @XXDD Comments are not a place to ask a new question. However, what you're essentially asking (I guess) is whether new physics (such as the unification of gravity with quantum) yields new models of computation. On the other hand, some reasoning along these lines leads you to physical limits - how densely can I store information (before it turns into a black hole). how quickly can I perform a two-bit operation (two bits, as small as possible, but communicating at the speed of light)? These things are readily answered... – DaftWullie Oct 30 '18 at 7:49
• @DaftWullie You are absolutely right. I was just wondering that maybe the speedup of QC can only be understood if we know how spacetime geometry is constructed from quantum information, so we can answer your question from a geometric perspective since complexity is just distance there. – XXDD Oct 30 '18 at 8:19
• @XXDD spacetime is flat in quantum information. – DaftWullie Oct 30 '18 at 8:23