Kvantecomputer haves (næsten) – software ønskes

I en god gammeldags telefonbog, hvor personer er opført alfabetisk, er det let at finde telefonnummeret på en person, men meget svær at finde personens navn, hvis man kun kender telefonnummeret

I en computer indexeres normalt efter både navn, telefonnummer, og andre oplysninger. Det betyder, at der kun behøves log(n) opslag, uanset hvad der søges på. Ofte gemmer man hele telefonbogen i en lang streng, hvor der til hvert tegn er tilknyttet en pointer. Så er muligt at søge på alt i strengen, også delstrenge - og hele telefonbogen, kan gemmes i en lang smøre. Søgningen tager kun O(log(n)). Det smarte ved denne metode, er at der også nemt søges på strenge der ligner, hvor f.eks. et tegn afviger, ved der først laves en hovedsøgning, og herefter en ekstra søgning på resten. Det er nemt, da der kan søges på enhver delstreng i teksten, uanset længden.

Det er totalt irrelevant for forståelsen af grovers algoritme.

Det er totalt irrelevant for forståelsen af grovers algoritme.

Men det er en nemmere og hurtigere løsning ved søgning i telefonbøger.

Den løser på elegant vis problemet med at bestemme, om en funktion leverer et konstant output for alle input eller et balanceret output i form af både 0 og 1.

Medmindre din hjerne er ret speciel, eller du ved noget jeg ikke ved, så er udsagnet volapyk. Venligst fortæl mig mere om denne funktions forskellige væremåder i form af konstant- eller balanceret -output. Telefonbogsanalogien taler om værste tilfælde. Hvad er det i middel? Det kunne jo være at første opslag gav match. Jeg har en lumsk fornemmelse af at der findes metoder, der klarer dette meget bedre end kvantefysikerne tror. Det kunne involvere matricer. Vi kan stadig modtage data fra disse rumfartøjer som er på vej ud i intetheden. Deres såkaldte fotoner må være ualmindeligt lange i tid og rum, for der kan ikke være mange fotoner tilbage efter denne lange rejse.

I en computer indexeres normalt efter både navn, telefonnummer, og andre oplysninger. Det betyder, at der kun behøves log(n) opslag, uanset hvad der søges på.

Ja Jens, men der skal indexeres først. Hvis man modtager enorme mængder data, og kun har brug for at slå op i dem få gange, inden man skal slå op i en ny bunke data næste gang, så kan indexering hver gang ikke betale sig.

Telefonbogen var et eksempel. Der kunne også være tale om et register over reservedele eller byggematerialer eller medicin med enorme mængder af oplysninger for hver enhed. At indexere alle disse oplysninger på kryds og tværs kunne ende med et index langt større end selve den indexerede datamængde.

Det kan en kvantecomputer åbenbart gennemsøge i en fart uden indexering, og det er dét der er pointen.

Hvis man modtager enorme mængder data, og kun har brug for at slå op i dem få gange, inden man skal slå op i en ny bunke data næste gang, så kan indexering hver gang ikke betale sig.

For hver data du modtager er indexering en O(log(n)) funktion, og det er det samme som, at indexering ikke tager tid (datalogisk). Flaskehalsen er modtagehastigheden, ikke beregningskompleksiteten.

At indexere alle disse oplysninger på kryds og tværs kunne ende med et index langt større end selve den indexerede datamængde.

Ja, plads er den største ulempe. Worst case, er at gemme alt i en enorm lang streng, og det kræver en pointer per tegn. Altså, et index der er ca. 4 gange så stor som datamængden.

Jeg vil nok ikke bruge kvantemekanik til telefonbogsproblemet. Men, der er mange matematiske funktioner, der ikke lader sig indexere.

Der er masser af viden om, hvordan man programmerer en kvantecomputer, men man har ikke noget hardware at køre programmerne på. Og jeg har på fornemmelsen, at man aldrig får bygget en universel kvantecomputer, der kan konkurrere med klassiske computere. Det er ikke de enkelte kvantegates, der er problemet -- dem kan man sagtens lave. Problemet er støj og dekoherens, som betyder, at en tilstand, hvor et ikke-trivielt antal kvantebit er entangled, vil falde sammen til en klassisk tilstand efter ganske få operationer. De tiltag jeg har set til støjkorrigering virker ikke realistiske: Antallet af gates til støjkorrigering er mange gange større end antallet af gates, der bærer information.

Jeg vil ikke afvise, at man kan lave computere, der kan udnytte kvanteeffekter til særlige typer programmering -- f.eks. simuleret nedkøling, som D-Wave angiveligt gør. Men colour me sceptic, når det angår en universel kvantecomputer.

Hej Torben

Kig på:

July 21, 2016, scitechdaily.com: Yale Researchers Cross the “Break Even” Point in Preserving a Bit of Quantum Information: Citat: "... “This is the first error correction to actually detect and correct naturally occurring errors,” said Robert Schoelkopf, Sterling Professor of Applied Physics and Physics at Yale, director of the Yale Quantum Institute, and principal investigator of the study. “It is just the beginning of using QEC [Quantum Error Correction] for real computing. Now we need to combine QEC with actual computations.” ... Co-lead author Andrei Petrenko, who is a Yale graduate student, added: “In our experiment we show that we can protect an actual superposition and the QEC doesn’t learn whether the qubit is a zero or a one, but can still compensate for the errors.” ..."