Kvantecomputer haves (næsten) – software ønskes
Verdens største softwarefirma, Microsoft, lancerede i denne uge et projekt, der baseret på dansk forskning skal skabe en kvantecomputer inden for få år.
Dermed bliver der sat nye muskler bag arbejdet med at løse de mange hardwareproblemer, der står i vejen for denne nye type computer – men også softwaresiden skal tænkes helt forfra, hvis en kvantecomputer skal finde nye løsninger på tekniske problemer
En af det 20. århundrede mest markante fysikere, Richard Feynman, stillede på en konference i 1981 spørgsmålet: Hvilken slags computer skal vi bruge til at simulere fysik? Han kom frem til, at dette måtte være en kvantecomputer.
Feynman sluttede sit foredrag på denne måde:
»Naturen er ikke klassisk, basta, så hvis du vil lave en simulering af naturen, så må du gøre den kvantemekanisk, og det er sørme et vidunderligt problem, for det er ikke let.«
Dels er det at bygge en kvantecomputer kompliceret, og hvordan man skulle programmere den, havde man ingen idé om på Feynmans tid.
Selv om andre forskere havde lignende tanker om kvantecomputere noget før eller på samme tid, er det ikke helt skævt at regne Feynmans foredrag 1981 for kvantecomputerens fødselstidspunkt.
Fra Turing til Deutsch
I 1980’erne og 1990’erne levede tanken om kvantecomputere primært videre i hovederne på teoretiske fysikere og dataloger.
Artiklen fortsætter efter grafikken
Man kan sammenligne denne periode med tiden efter 1936, hvor Alan Turing teoretisk beskrev principperne for en universel computer, og indtil de første computere opstod efter Anden Verdenskrig baseret på John von Neumanns arkitektur.
Skal man udpege pendanten til Alan Turing, må det blive den britiske fysiker David Deutsch, der i 1985 lavede en præcis beskrivelse af en universel kvante-Turing-maskine.
Han var også blandt de første til at vise, hvordan en kvantecomputer i teorien kunne løse en opgave mere simpelt end en klassisk computer. Deutschs algoritme er i hovedtræk gengivet i illustrationen. 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.
Ligefrem at kalde det en killerapplikation for kvantecomputere er nok så meget sagt, også selv om David Deutsch sammen med Richard Jozsa i 1992 lavede en version af algoritmen, der har en streng på N bit som input. Det kan med en klassisk computer tage op til 2N-1 +1 beregninger at vise, om funktionen er af den ene eller anden type. Deutsch-Jozsa-algoritmen kræver kun én beregning.
Og videre til Shor og Grover
Anderledes stor opmærksom fik kvantealgoritmer, som blev udviklet af den amerikanske matematiker Peter Shor i 1994 og den indisk-amerikanske datalog Lov Grover i 1995.
Shor viste, at en kvantecomputer meget hurtigt og effektivt kan faktorisere tal som er et produkt af to primtal. De mest almindelige krypteringsværktøjer, der benyttes i dag, er baseret på det forhold, at der er meget svært – i praksis umuligt hvis tallet er stort nok – med en klassisk computer.
Groves algoritme er meget effektiv til at løse telefonbogsproblemet. 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. En telefonbog med N personer kan i værste tilfælde kræve N opslag. Med en kvantecomputer og Grovers algoritme er der højst brug for √N opslag. Hvis N er 1.000.000 er √N=1.000 – en markant forbedring.
Men generelt mangler der gode kvantealgoritmer, og dataloger og matematikere er ikke engang sikre på, hvilke former for problemer der kan løses effektivt med en kvantecomputer, og hvilke selv en sådan må give op over for.
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.
Men det er en nemmere og hurtigere løsning ved søgning i telefonbøger.
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.
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.
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.
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.”
..."