Why can't quantum computation replace classical computation?

Question

I am not a total novice of quantum computation (have read the first 6 chapters of Nielsen and Chuang, though not familiar with every part), but there are some fundamental questions that I don't know answers well. One question that has bothered me is that I often hear comments which say that quantum computers can not be regarded as a replacement for classical ones.

However, we also know that all classical circuits can be simulated by quantum circuits. Put it another way, every Boolean function $f:\{0,1\}^k\to\{0,1\}$ can be computed by using a quantum circuit.

So, how to correctly understand the problems that a quantum computer might encounter when doing a classical computer's job? I know a strong restriction on quantum computing is that we can't read the resulting qubits state directly, but has to use quantum measurement so that we can only get one of the computational basis states probabilistically. However, I don't see this is a difficulty if what we want to do is only to compute a Boolean function.

Following are some possible answers I've thought of:

1. Quantum computers can do everything classical computers do, but no more efficiently if we only use the standard technique to simulate classical circuits. Quantum computers outperform classical ones only when special quantum algorithms exploiting superpositions of quantum states are applied, such as the quantum Fourier transform (QFT).

2. In Nielsen and Chuang (Section 5.1), it says QFT cannot replace classical discrete Fourier transform. Besides the problem that the amplitudes cannot be directly accessed by measurement, it points out that the worse problem is that "there is in general no way to efficiently prepare the original state to be Fourier transformed." Maybe such kind of problems is important for many applications.

Are the above answers right? Are there other important reasons quantum computers cannot replace the classical ones?

Answer 1

In the general case, I think the first answer you listed is pretty accurate. At the moment, quantum hardware is expensive and replacing classical with quantum would imply simulating the billions of transistors present in modern computers. If we have efficient algorithms to perform these tasks, why would we bother on performing the exact same algorithms with the same exact techniques but with way more expensive hardware? We are not getting any performance improvement.

That's why it is very often said that quantum computers will not replace classical computers, but rather be of help to classical computers. Take for example Shor's algorithm. This algorithm is divided into a classical and a quantum part. The quantum part performs something that cannot be efficiently done in a classical computer: estimate the phase of an eigenvector of a unitary operator. Then, the classical part uses this result to finish factorizing. VQE has a similar dynamic, where the quantum part simulates the molecule and a classical optimizer tweaks the parameters of the circuit.

Something else to consider is the probabilistic nature of quantum computers. Eventhough error correction techniques are being developed and better hardware is being developed, the probabilistic nature of quantum computing will always be there. On the other side, classical computers have very small error rates, which make them suitable very reliable. And the probabilistic nature of quantum computers isn't something bad, it is one of the things that makes them so powerful, but it isn't the best option to run the classical algorithms and software developed.

tl;dr: No, quantum computers will not replace classical computers. Both systems coexist and each will specialize on those tasks they can do better.

Answer 2

In my opinion, quantum computers can't replace classical computers, because there are many tasks where classical algorithms are optimized, so why do we replace something which works quickly and accurately with something which works quickly but it doesn't have the same precision? It is more logical to use quantum computers only where classical computers fail in terms of performance

Answer 3

Sure, you can achieve quantum supremacy, meaning you can do certain tasks way faster on quantum computers than on any classical supercomputers.

But the physical implementation of a quantum computer is hard because of many things: small decoherence time of qubits, some amount of error in implementing quantum gates (which will be increased if you add more and more gates), noise.

Now, just to do a simple addition on a quantum computer is a tedious task. See elementary operation.

And a classical computer does millions of computations per second. To achieve this on a quantum computer, you will probably need millions of gates as you need to convert certain gates to elementary gates. And quantum computers do have some limitations which I mentioned earlier.

So, in my opinion, it is physically impossible to simulate a classical computer on a quantum computer.

Answer 4

Contrary to the hypothesis and the other answers here, I don't think there is any reason why quantum computation can not replace classical computation. It certainly won't in the near future, but who's to say what the rate of progress will be?

One has to understand the two main proponents behind classical computation devices in use today: transistors and photolithography. They created the digital revolution that allows you to carry a device with billions of computational gates in your pocket. 70 years ago you could only have 20,000 transistors in a complete room. 70 years is not a very long time in the big picture.

Who's to say what the state of computational devices will be in a 1000 years? Perhaps a strategy as effective as photolithography will be found for the construction of quantum computers, perhaps not.

As for your two guesses....

Quantum computers can do everything classical computers do, but no more efficiently if we only use the standard technique to simulate classical circuits.

This is misleading. There is a linear time and space mapping from a classical circuit to a quantum circuit. How 'efficient' either of those is depends entirely on the constants involved. Right now the constants for quantum machines are awful, but that may change.

In Nielsen and Chuang (Section 5.1), it says QFT cannot replace classical discrete Fourier transform. Besides the problem that the amplitudes cannot be directly accessed by measurement, it points out that the worse problem is that "there is in general no way to efficiently prepare the original state to be Fourier transformed." Maybe such kind of problems is important for many applications.

You certainly can do a classical Discrete Fourier Transform on a quantum computer (as you can any other classical algorithm). The point of N&C is not to say that quantum computers can't do classical DFT, their point is that QFT is a distinct algorithm with different input/output assumptions.

Answer 5

Your question talks about the theoretical capabilities of theoretical computers. Anyone who says that quantum computers won't replace classical computers is probably talking about the actual capabilities of actual computers.

Obviously, current quantum computers can't replace current classical computers. I doubt that that will ever change. The reason is that quantum computations have to happen in perfect thermodynamic isolation from the environment, and that severely limits the hardware design space. Quantum computing hardware could only compete in speed with classical hardware on classical algorithms if the optimal point in the quantum design space happened to coincide with the optimal point in the much larger classical design space, and I see no reason why that would happen.

Quantum hardware might de-facto replace classical hardware if it had enough advantages to compensate for the price/performance disadvantage. But I don't know of a single CPU-intensive task that people routinely run on personal or business computers that would be sped up by any known quantum algorithm. There are scientific applications (simulation of quantum systems, at least), but I think most people would have no reason to pay a premium for a quantum-capable processor unless someone discovers a killer app.