What is the basic idea behind how quantum computation is supposed to work?

Question

As far as I know that QM is probability-based and Feynman proposed a quantum computer (QC) as an emulator for fast computation. Reading the introductory articles, I just do not get the essence of the speedup. I understand the q-bits and such but basically, what is the idea?

Does Feynman simply mean that instead of computing the function of how something behaves (the frequency of oscillations for instance) from a complex model we just build the model physically and observe the behaviour? I see that even simple probabilistic problems may produce involved computations. Marginally more complex problem (its model) can demand prohibitively more complex computation. Does QC just builds a physical model and replaces the computation with measurement?

Answer 1

Building an analog of a system and watching its evolution is sure one possible thing. It can be used to simulate quantum systems with quantum systems that are easier to control. This is known under the term of quantum simulation and it is being developed right now.

But quantum computation is far more than that. You can use it to calculate even completely classical things using shortcuts through quantum physics. That is, of course, probabilistic but it can still work very efficiently. And it works the same way classical computers do - you have some logic gates and applying a specific sequence of these gates to a memory register gives you the result.

The main power of quantum computation lies in the superposition principle. This makes it possible to use tricks such as

• massive parallelism that makes it possible to, e.g., get function values for several input values simultaneously, making it possible to make conclusions about its global behaviour after a single run of the function,

• constructive and destructive interference that can eliminate incorrect results and enhance the correct one during a computation,

• entanglement which can be, again, used to determine some global properties of mathematical functions more efficiently than with a classical computer.

If you still feel unsure about quantum computation and want to understand it better, I suggest you look at some specific quantum algorithms and try to understand how the features of quantum mechanics are exploited in them.