4
$\begingroup$

I edited the question since this comment was (rightly) made:

There are few things that are more annoying than questions where the question text is not self-contained.

So:
Quantum supremacy has been reached quite recently.
It is said that a quantum computer, because of its stronger computing power can simulate physical processes much faster than a classical computer.
Now, quantum computers make a huge amount of different permutations of whatever. How does this relate to physical processes?
For example, a classical computer can compute the trajectory of an object in our solar system with high accuracy. I can't see how a quantum computer can do this job by performing permutations with incredible speed. So I'm not asking if a QC can perform this simulation faster but if it can be calculated at all by a QC.

So here is my question: Is the collection of physical processes that can be simulated by a quantum computer limited to specific processes or is a quantum computer, in principle, capable to perform the same calculations (of every physical process) a classical computer is capable of?

I don't know that much about quantum programming (or programming in general), so an additional question could be if the algorithms used in a quantum computer program are similar to those used in a classical one but this I better ask on the appropriate site (specially dedicated to all stuff related to quantum computers).

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ I am not an expert at quantum computing. But I would assume this kind of computing would make less approximations than the calculations you are suggesting (the trajectory of an object in our solar system). $\endgroup$
    – Winston
    Commented Aug 26, 2020 at 22:20
  • 1
    $\begingroup$ About your assertion that quantum supremacy has been reached: ibm.com/blogs/research/2019/10/on-quantum-supremacy $\endgroup$
    – Winston
    Commented Aug 26, 2020 at 23:35
  • $\begingroup$ You need to add more details: Do you mean what is written in your question (capable to perform the same simulations), or what is written in your title (simulate all physical processes faster). If the latter, (i) please fix the question, and (ii) what do you mean by "faster" - 1 second faster? 2 times faster? Quadratically faster, exponentially faster, ...? $\endgroup$
    – Norbert Schuch
    Commented Aug 29, 2020 at 18:59
  • $\begingroup$ @NorbertSchuch As I stated in my question, for example predicting the trajectories of objects (approached in a Newtonian way, not to speak of GR). Not if they can be performed faster, but if they can be performed at all, which, according to your answer is yes, but I'm not sure about that. $\endgroup$
    – Deschele Schilder
    Commented Aug 29, 2020 at 22:43
  • $\begingroup$ Thanks for the clarification. Do you mind updating your title? And why are you not sure about that? $\endgroup$
    – Norbert Schuch
    Commented Aug 29, 2020 at 22:52

3 Answers 3

Reset to default
6
$\begingroup$

Yes, a quantum computer is capable of carrying out all computations a classical computer can do.

Classical computers act on classical bitstrings $x_1x_2\dots x_N$, e.g. 01010010.... The action of a gate/operation on a classical input is to map such a bitstring to a different one. Any classical computation can be expressed as a sequence of reversible operations. Then, the action of any classical gate/operation is a reversible action on the bitstring, that is, a permutation. Typically, we will only consider gates acting on very few bits.

A quantum computer acts on qubits. These can be in any basis state $|x_1x_2\dots x_N\rangle$, as well as superpositions thereof. Gates are unitary transformations acting on a few qubits.

If you now initialize your quantum computer into a basis state $|x_1x_2\dots x_N\rangle$ and only act with permutations - a special case of unitaries - then your quantum computer effectively carries out the classical computation.

So yes, a quantum computer is capable of carrying out all computations a classical computer can do -- and more.

Improve this answer
$\endgroup$
12
  • $\begingroup$ The question in the title asks about whether such computations are always faster on a quantum computer. $\endgroup$
    – probably_someone
    Commented Aug 27, 2020 at 15:50
  • $\begingroup$ @probably_someone There is few things which are more annoying than questions where the question text is not self-contained. To quote: "My question: Is the collection of physical processes that can be simulated by a quantum computer limited to specific processes or is a quantum computer, in principle, capable to perform the same calculations as a classical computer is capable of?", which is what my answer addresses. $\endgroup$
    – Norbert Schuch
    Commented Aug 27, 2020 at 16:12
  • $\begingroup$ @probably_someone Also, note that faster alone is rather meaningless. You just need to increase the clock rate of your computer by 1% and - voila! - all computations run faster! $\endgroup$
    – Norbert Schuch
    Commented Aug 29, 2020 at 18:57
  • $\begingroup$ If you specify a particular definition of "faster" (i.e. takes less logic gate operations for large problem sizes), then it becomes possible to say something unambiguous. $\endgroup$
    – probably_someone
    Commented Aug 29, 2020 at 20:12
  • $\begingroup$ @probably_someone I'm curious how it becomes possible to say something unambiguous, without solving some big open problem in (quantum) computational complexity. (Unless you ask for a sufficiently strong separation, of course). $\endgroup$
    – Norbert Schuch
    Commented Aug 29, 2020 at 20:30
3
$\begingroup$

The question has two aspects: the formal computer science/mathematical aspect, and the practical aspect.

On the formal computer science aspect, classical computing is a strict subset of quantum computing. That means that anything a classical computer can do, a quantum computer can also do, and furthermore it means that the quantum computer will not be slower than the classical one, when measured in terms of number of operations and memory elements required for a given task.

However, from a practical point of view, quantum computers are designed to tackle a set of problems for which they are not just equal to but better than classical computers. Here 'better than' means 'exponentially faster than'. In order to get access to this speed-up, the quantum computer must exploit quantum superposition and entanglement, and this requires extreme precision and protection of the computing elements from noise. The requirements are much more severe than for classical computing, and as a result the quantum computer will typically have a much slower clock rate or basic logic gate rate, and the design is not well-suited to tackling the sorts of problems that do not exploit entanglement. Thus in practice quantum computers are not fast at tasks that cannot exploit the quantum speed-up, and that means most tasks in practice. But the tasks which can be speeded up include some that have very wide-ranging application, especially to scientific research.

To summarise, quantum computers can do everything that classical computers can do, but in practice you would choose a classical computer for some tasks because its design allows it a faster gate rate (and it is cheaper to build).

Improve this answer
$\endgroup$
1
  • $\begingroup$ But what about 30 or more years from now? (To put in conversely: The currently existing quantum computers can essentially do almost nothing a classical computer can do.) $\endgroup$
    – Norbert Schuch
    Commented Aug 30, 2020 at 10:44
-3
$\begingroup$

If the Church-Turing thesis is correct, then it's possible. Conversely, if it cannot, then the C-T thesis would be wrong. This would be huge news in the field of computing!

I have heard no news of such a fundamental breakthrough in computing theory, and Wikipedia has not either.

Improve this answer
$\endgroup$
5
  • $\begingroup$ It may be fundamental, but that doesn't mean a QC is indeed capable to do so. $\endgroup$
    – Deschele Schilder
    Commented Aug 30, 2020 at 6:50
  • $\begingroup$ This is plain wrong. QCs can run any classical reversible circuit, and any classical computation can be expressed as a reversible circuit. $\endgroup$
    – Norbert Schuch
    Commented Aug 30, 2020 at 8:44
  • $\begingroup$ @NorbertSchuch Is this comment meant for me? $\endgroup$
    – Deschele Schilder
    Commented Aug 30, 2020 at 19:53
  • $\begingroup$ @descheleschilder No, that's why I did not add an @[...]. It is meant for the answer, which is plain wrong: This has nothing to do with the Church-Turing thesis. $\endgroup$
    – Norbert Schuch
    Commented Aug 30, 2020 at 22:04
  • $\begingroup$ @NorbertSchuch That's clear. Over and out. $\endgroup$
    – Deschele Schilder
    Commented Aug 30, 2020 at 22:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.