Onjuistheden "Quantumcomputerbedrijf krijgt flinke injectie"

[DigitalBrains]

Hallo,

Ik heb even een account geregistreerd om te wijzen op een fout die mij stoort.

Allereerst een foutje wat wellicht gewoon onduidelijk of slordig is.

Het gevolg is dat een quantumcomputer met n bits, 2ⁿ waardes kan uitdrukken, en daardoor stijgt de rekenkracht van deze machines exponentieel met het aantal qubits.

Dit klinkt voor mij als de beschrijving van gewone bits in een gewone computer. Met 8 bits, 2⁸ = 256 waardes, met 16 bits 2¹⁶ = 65536 waardes. Exponentieel in de lengte van het woord, gelukkig. Wellicht dat de schrijver een ander idee had bij het woord "waardes".

Maar de storende fout vind ik dit:

Het effect is dat bepaalde typen berekeningen, zoals die uit de beruchte klasse van NP-complete problemen - ... - met een quantumcomputer eenvoudig uit zijn te voeren.

Dat zou werkelijk de heilige graal zijn! NP-complete problemen eenvoudig oplossen! Wellicht dat de schrijver hierbij dacht aan Grover's algorithm, maar ook die is slechts in staat om een NP-compleet probleem kwadratisch sneller te maken, indrukwekkend, maar eenvoudig zou ik het niet noemen (sterker nog, nog steeds eindeloos veel moeilijker dan wat als "tractable" (te doen) beschouwd wordt, zoals P-problemen).

Ook op de gelinkte pagina over Grover gebruiken ze de woorden "heilige graal":

In addition, it can be used to solve NP-complete problems by performing exhaustive searches over the set of possible solutions. This would result in a considerable speed-up over classical solutions, even though it does not provide the "holy grail" of a polynomial-time solution.

Ik begin te denken dat het woord heilige graal een beetje te vaak gebruikt wordt in verband met NP-compleet .

Overigens heb ik zelf geen fluit verstand van quantum computing, maar ik heb een paar dingen geleerd over P/NP. Van Grover's algoritme weet ik niet meer dan dat het bestaat, en misschien dacht de schrijver daar ook wel helemaal niet aan. NP-compleet eenvoudig oplossen, ben ik echter zeker van dat dat nog zelfs niet aannemelijk gemaakt is, laat staan bewezen.

[Harm]

Voor zover ik weet is men hiermee bezig:

Rataplan schreef op woensdag 06 februari 2008 @ 12:58:
...en dat is natuurlijk omdat dat geen Spel- of Tikfoutje is (maar, inderdaad, een aperte blunder). Een apart topic voorkomt dat er hier over oplossingen gedebatteerd moet worden, volgende keer even rekening mee houden.

Ik ga even uitzoeken wie ik ervoor kan slaan en hoe we het op kunnen lossen.

Desalniettemin erg bedankt voor je opmerkingen!