Do (useful) Quantum Computers exist at all? Best mathematical explanation of Grover's algorithm so far by 3Blue1Brown.

3Blue1Brown hat ein Video veröffentlicht, das den Grover-Quanten-Algorithmus geometrisch erklärt, wie Quanten-Computer NP-schwere Probleme viel schneller lösen könnten als klassische Computer. Wenn sie existieren würden.

Allerdings wäre der Grover-Algorithmus nicht so viel schneller als gedacht, der Speedup wäre eher in der Größenordnung von O(sqrt(N)), aber nicht O(log(N)) oder gar O(1) wie viele vermuten. Vereinfacht gesagt, bedeutet das, dass eine Operation, die klassisch zum Beispiel 10 Milliarden Schritte (10^10) benötigen würde, auf einem Quanten-Computer in nur 100K Schritten (10^5) lösbar wäre. Der Exponent halbiert sich, was eine dramatische Verbesserung ist, aber der Speedup wäre nicht logarithmisch.

Generell gibt es um Quanten-Computer einen extremen Hype, der nicht ganz der Realität gerecht wird, obwohl Big-Tech immer wieder behauptet Quanten-Computer mit Hunderten oder Tausenden qubits gebaut zu haben und den ganz großen Durchbruch geschafft haben, gibt es bis heute keinen Quanten-Computer, der eine sinnvolle Berechnung durchführen könnte.

Das Problem ist, dass Quanten-Algorithmen enorm heftige Annahmen über die Realität machen, um überhaupt funktionieren zu können.

Mathematisch wird angenommen, dass überlagerte Quantenzustände mit der Anzahl an Quanten unendlich in ihrer Komplexität skalieren, intern mit einer unendlichen Genauigkeit operieren und ihre Superposition auch nach unendlich vielen Schritten nicht verlieren.

Alle diese Annahmen sind vermutlich falsch. In der Realität kämpfen Quanten-Computer mit enormen Ungenauigkeiten (Noise), der Dekohärenz der Superposition, und sie skalieren nicht. Die Frage ist, ob das an der unzureichenden Implementierung und externen Störfaktoren liegt, oder ob es nicht sogar eine theoretische Grenze gibt.

Ich vermute, dass es in der Natur irgendwo einen Cutoff gibt und die internen überlagerten Zustände nicht unendlich exponentiell skalieren bzw. nicht unendlich genau rechnen, da man bereits bei einigen Hundert Quanten mehr interne Zustände hätte als das Universum Atome besitzt.

Was sagt ihr dazu? Denkt ihr, dass Quanten-Computer in ein paar Jahren Realität werden, oder gibt es ein theoretisches Limit, warum diese nicht weiter skalieren können?

But what is quantum computing? (Grover's Algorithm)

Video credit: 3Blue1Brown

Follow-up video

Video credit: 3Blue1Brown

English

3Blue1Brown has released a video explaining the Grover quantum algorithm geometrically, how quantum computers could solve NP-hard problems much faster than classical computers. If they existed.

However, the Grover algorithm would not be that much faster than thought, the speedup would be more in the order of O(sqrt(N)), but not O(log(N)) or even O(1) as many assume. Put simply, this means that an operation that would classically require 10 billion steps (10^10), for example, could be solved on a quantum computer in just 100K steps (10^5). The exponent is halved, which is a dramatic improvement, but the speedup would not be logarithmic.

In general, there is an extreme hype around quantum computers that does not quite match reality, although big tech keeps claiming to have built quantum computers with hundreds or thousands of qubits and making big breakthroughs, there is still no quantum computer that could perform a meaningful computation to this date.

The problem is that quantum algorithms make mind-boggling and insane assumptions about reality in order to function at all.

Mathematically, it is assumed that superimposed quantum states scale infinitely in complexity with the number of quanta, operate internally with infinite precision and do not lose their superposition even after an infinite number of steps.

All these assumptions are most probably wrong. In reality, quantum computers struggle with enormous inaccuracies (noise), the decoherence of their superposition, and they do not scale. The question is whether this is due to inadequate implementation and external interference factors, or whether there is a theoretical limit.

I suspect that there is a cutoff somewhere in nature and that the internal superimposed states do not scale exponentially to infinity or calculate with infinite precision to begin with, since even a few hundred quanta would result in more internal states than the universe has atoms. Mind-boggling.

What do you think? Do you think that quantum computers will become a reality in a few years, or is there a fundamental limit as to why they cannot scale further?

Posted Using INLEO