The whole field was triggered by Shor's invention of his fameous factoring algorithm for quantum computers. 25 years and billions of $ later, it is still not possible to factor the number 15 by using this algorithm, and there are no visible reasons to believe that this wonderful breakthrough might happen within the next 25 years. This simple FACT gives us an idea of the perspectives for QC

8+ years ago I wrote this on my blog:

http://www.ebyte.it/stan/blog10c.html#10Aug19

Today, after 200 or so monographs and tens of thousands of papers, REAL quantum computers are just an illusion. Quantum computing is largly a theoretical concept. The actual computers harolded as "quantum" are just supercooled normal computers. No quantum computer so far solved any practical problem worth mentioning.

Now, I know that I will be violently attacked for these words. That is because there is so much money that keeps sinking into this black hole, and too many people love it. Plus, I am actually truly sorry, because I am a physicist and I love quantum physics, and I trust it. But quantum computers can not work because in a real world an infinity of interfering 'dirty' phenomena (decoherence through relaxation and external interactions in general) work against them. These are the same reasons that made analog computers loose the battle against digital ones, even in specialized fields where they appeared to be better suited. Real world is just too imperfect to rely on its numeric values without a huge amount of abstraction. In the end, quantum computing might well turn out to be the largest hoax in the history of technology.

It is much more likely that one of these days a kid will come up with a new and very fast algorithm for factorization of natural numbers and thus make the quantum Shor's algorithm redundant (there is no math proof that such a fast classical algorithm can not exist!). There are very very few problems for which we have a PROOF that the most efficient algorithm has been found. And factorization of natural numbers is NOT one of them.

But, Phillip, I like your notion of a problem that can be mathematically proved to require infinite time to solve by conventional computers. I do not say that it can't exist. Just if you know of any such problem (I don't), I would be most interested to know it, too.

The little bit of a mathematician in me says that problems (algorithms) requiring an infinite time to solve MIGHT exist. For sure, they can be defined. Like this for example:

A problem that can be (provably) solved in a finite number of computer steps is an FTP (finite time problem). If, however, in any finite number of steps, a solution of a problem can only be approximated (even using abstract, infinite-precision arithmetics), and if the approximation error converges to zero but (again provably) never becomes zero, than we have an ITP (infinite time problem).

There is no lack of FTP's; the only problem with most of them is to estimate the lower bound for the number of needed steps - we in general know the current state-of-the-arts but not the absolute lower bound (factorization of integers is a good example, but there are many others).

However, I have never encountered a practical example of a genuine and proved ITP, one which provably can not admit any FTP solution. Which, by itself, means nothing (except, maybe, that I am ignorant).

In these kinds of things, rigorous mathematical PROOFS are essential, without them we spawn mystic beliefs.

-------------

Regarding quantum computers: lots of people think that Google has quantum computers, mostly because they say they invest into quantum computing. They don't; they only have real big and fast classical supercomputers. But they love the mystic buzz about what they are doing - it is a free promotion.

Again, I would like to see the proofs of the many claims.

:-) Goldbach qualifies as "possible" ITP (yes, there are tons of those) but not a "proven", absolute ITP (I know none). For the simple reason that there is no proof that a finite proof (cum algorithm) of Goldbach does not exist.

That is why I insist on math proofs. Math has the capability to sometimes prove the existence of something (a solution, an algorithm) even though the object remains inaccessible. For example, there are well defined math constants whose existence was proved but whose value is extremely poorly known (OEIS lists many of them). I believe that something of that kind should be applicable to the math of algorithms as well. Though it might be exceedingly hard. So far, one always analyses just a specific proposed algorithm, not the whole set of possible algorithms, including those not yet discovered.

But we are getting off the track, Peter. I appreciated your comment above and will start following you. Though you will never sell to me "quantum simulated annealing". I do not buy that, and for good reasons, believe me :-)

Stan Sykora Here is the article which inspired this question:

Article Can quantum computing solve classically unsolvable problems?

It gives a critique of the claim made by T. D. Kieu, which includes notions of a problem which could not be solved in a finite amount of time by a classical computer. I asked the question to find out whether the claim had been found true or false.

What about companies like Google and IBM who have succeeded in creating small quantum computers with several bits? If they indeed have, then theoretically the only challenge is to increase the number of qubits. Also, what functions (if any) are similar between theoretical quantum computers and adiabatic quantum computers?

@Peter Breuer I believe it's not quite true that the only difference in quantum computers is that they are faster, albeit exponentially. If a full-fledged quantum computer did exist, this is my conjecture of how it would work: a number of particles are held in superposition. This means that each of the particles are in a simultaneous state of every value between one and zero. This is where the idea of qubits, bits that are both one and zero, comes from. Next, the particles are programmed using logic gates between them to define the calculation. Finally, the system is caused to collapse out of superposition and the final state of the particles is the solution. Thus, although exponential growth is one of the benefits of quantum computers, the second is that they are a form of analog, by nature. If you could set up each qubit to represent a part of the real world along with representative relationships, simulating complex systems becomes incredibly easy.

(This is all from someone who has never officially studied quantum mechanics, so this is nothing more than my intuitive interpretation of what I have read.)

The important bit is that all the calculations in a quantum computer are completed within the same instant as it collapses out of superposition. This removes time out of the equation. While this does limit them, you could possibly recreate structures similar to loops and conditional branching. Since time is not applicable, the closest semblance of a loop in a QC would be multiplying/increasing-in-general the solution of a group of code a certain amount of times, perhaps changing several values within it between the multiplications. I believe this can be done without time. To recreate conditional branching is easier. A probable solution would require one, or perhaps several gates controlling whether a certain group of gates are used or not in finding the solution.

So, the complexity of the program will probably be linearly limited.

It has been said that a functional quantum computer would be able to break the barrier of the traveling salesman problem. I should research how such a program would be structured.

The whole field was triggered by Shor's invention of his fameous factoring algorithm for quantum computers. 25 years and billions of $ later, it is still not possible to factor the number 15 by using this algorithm, and there are no visible reasons to believe that this wonderful breakthrough might happen within the next 25 years. This simple FACT gives us an idea of the perspectives for QC