Nye computeralgoritmer udvider grænserne for en kvantefremtid

Quantum computing lover at udnytte de mærkelige egenskaber ved kvantemekanik i maskiner, der vil overgå selv de mest kraftfulde supercomputere i dag. Men omfanget af deres anvendelse, det viser sig, er ikke helt klart.

For fuldt ud at realisere potentialet ved kvanteberegning, videnskabsmænd skal starte med det grundlæggende:udvikling af trinvise procedurer, eller algoritmer, for kvantecomputere til at udføre simple opgaver, som factoring af et tal. Disse simple algoritmer kan så bruges som byggesten til mere komplicerede beregninger.

Prasanth Shyamsundar, en postdoktoral forskningsassistent ved Institut for Energis Fermilab Quantum Institute, har gjort netop det. I et fortrykt papir udgivet i februar, han annoncerede to nye algoritmer, der bygger på eksisterende arbejde på området for yderligere at diversificere de typer problemer, kvantecomputere kan løse.

"Der er specifikke opgaver, der kan udføres hurtigere ved hjælp af kvantecomputere, og jeg er interesseret i at forstå, hvad det er, " sagde Shyamsundar. "Disse nye algoritmer udfører generiske opgaver, og jeg håber, de vil inspirere folk til at designe endnu flere algoritmer omkring dem."

Shyamsundars kvantealgoritmer, i særdeleshed, er nyttige, når du søger efter en specifik post i en usorteret samling af data. Overvej et legetøjseksempel:Antag, at vi har en stak på 100 vinylplader, og vi pålægger en computer at finde det eneste jazzalbum i stakken.

klassisk, en computer skal undersøge hver enkelt plade og træffe en ja-eller-nej-beslutning om, hvorvidt det er det album, vi leder efter, baseret på et givent sæt søgekriterier.

"Du har en forespørgsel, og computeren giver dig et output, "Sagde Shyamsundar." I dette tilfælde, forespørgslen er:Opfylder denne post mit sæt kriterier? Og output er ja eller nej. "

At finde den pågældende post kan kun tage nogle få forespørgsler, hvis den er tæt på toppen af ​​stakken, eller tættere på 100 forespørgsler, hvis posten er tæt på bunden. Gennemsnitlig, en klassisk computer ville finde den korrekte post med 50 forespørgsler, eller halvdelen af ​​det samlede antal i stakken.

En kvantecomputer, på den anden side, ville lokalisere jazzalbummet meget hurtigere. Dette skyldes, at det har evnen til at analysere alle posterne på én gang, ved hjælp af en kvanteeffekt kaldet superposition.

Med denne ejendom, antallet af forespørgsler, der skal til for at finde jazzalbummet, er kun omkring 10, kvadratroden af ​​antallet af poster i stakken. Dette fænomen er kendt som quantum speedup og er et resultat af den unikke måde, kvantecomputere gemmer information på.

Kvantefordelen

Klassiske computere bruger lagerenheder kaldet bits til at gemme og analysere data. En bit kan tildeles en af ​​to værdier:0 eller 1.

Kvanteversionen af ​​dette kaldes en qubit. Qubits kan også være enten 0 eller 1, men i modsætning til deres klassiske modstykker, de kan også være en kombination af begge værdier på samme tid. Dette er kendt som superposition, og giver kvantecomputere mulighed for at vurdere flere poster, eller stater, samtidigt.

"Hvis en enkelt qubit kan være i en superposition på 0 og 1, det betyder, at to qubits kan være i en superposition af fire mulige tilstande, " sagde Shyamsundar. Antallet af tilgængelige stater vokser eksponentielt med antallet af brugte qubits.

Virker stærk, ret? Det er en stor fordel, når man nærmer sig problemer, der kræver omfattende computerkraft. Ulempen, imidlertid, er, at superpositioner er sandsynlige i naturen - hvilket betyder, at de ikke vil give definitive output om de individuelle tilstande selv.

Tænk på det som en møntflip. Når du er i luften, møntens tilstand er ubestemt; den har 50 % sandsynlighed for at lande enten hoveder eller haler. Først når mønten når jorden, sætter den sig i en værdi, der kan bestemmes præcist.

Kvantesuperpositioner fungerer på samme måde. De er en kombination af individuelle stater, hver med deres egen sandsynlighed for at dukke op, når de måles.

Men processen med at måle vil ikke nødvendigvis kollapse superpositionen til den værdi, vi leder efter. Det afhænger af sandsynligheden forbundet med den korrekte tilstand.

"Hvis vi opretter en superposition af poster og måler det, vi får ikke nødvendigvis det rigtige svar, " sagde Shyamsundar. "Det vil bare give os en af ​​posterne."

For fuldt ud at udnytte den hurtigere kvantecomputere giver, derefter, videnskabsmænd skal på en eller anden måde være i stand til at udtrække den korrekte post, de leder efter. Hvis de ikke kan, fordelen i forhold til klassiske computere er tabt.

Forstærkning af sandsynligheden for korrekte tilstande

Heldigvis, forskere udviklede en algoritme for næsten 25 år siden, der vil udføre en række operationer på en superposition for at forstærke sandsynligheden for visse individuelle tilstande og undertrykke andre, afhængigt af et givet sæt søgekriterier. Det betyder, at når det er tid til at måle, superpositionen vil højst sandsynligt kollapse til den tilstand, de søger efter.

Men begrænsningen af ​​denne algoritme er, at den kun kan anvendes til booleske situationer, eller dem, der kan forespørges med et ja eller nej output, som at søge efter et jazzalbum i en stak af flere plader.

Scenarier med ikke-boolske output udgør en udfordring. Musikgenrer er ikke præcist defineret, så en bedre tilgang til jazzpladeproblemet kan være at bede computeren om at vurdere albummene efter, hvor "jazzy" de er. Dette kunne se ud som at tildele hver post en score på en skala fra 1 til 10.

Tidligere, videnskabsmænd ville være nødt til at konvertere ikke-boolske problemer som dette til dem med boolske output.

"Du ville indstille en tærskel og sige, at enhver tilstand under denne tærskel er dårlig, og enhver tilstand over denne tærskel er god, " sagde Shyamsundar. I vores jazzpladeeksempel, det ville svare til at sige noget vurderet mellem 1 og 5 ikke er jazz, mens alt mellem 5 og 10 er.

Men Shyamsundar har udvidet denne beregning, så en boolsk konvertering ikke længere er nødvendig. Han kalder denne nye teknik den ikke-boolske kvanteamplitude amplifikationsalgoritme.

"Hvis et problem kræver et ja-eller-nej svar, den nye algoritme er identisk med den forrige, " sagde Shyamsundar. "Men dette bliver nu åbent for flere opgaver; der er en masse problemer, der kan løses mere naturligt i form af en score i stedet for et ja-eller-nej output."

En anden algoritme introduceret i avisen, kaldet kvantemiddel-estimeringsalgoritmen, giver forskere mulighed for at estimere den gennemsnitlige bedømmelse af alle optegnelser. Med andre ord, den kan vurdere hvor "jazzy" stakken er som helhed.

Begge algoritmer gør op med at skulle reducere scenarier til beregninger med kun to typer output, og i stedet give mulighed for en række udgange til mere præcist at karakterisere information med en kvantehastighed i forhold til klassiske beregningsmetoder.

Procedurer som disse kan virke primitive og abstrakte, men de bygger et væsentligt grundlag for mere komplekse og nyttige opgaver i kvantefremtiden. Inden for fysikken, de nyligt introducerede algoritmer kan i sidste ende tillade videnskabsmænd at nå målfølsomhed hurtigere i visse eksperimenter. Shyamsundar planlægger også at udnytte disse algoritmer til brug i kvantemaskinelæring.

Og uden for videnskabens område? Mulighederne mangler endnu at blive opdaget.

"Vi er stadig i de tidlige dage af kvantecomputere, "Shyamsundar sagde, bemærker, at nysgerrighed ofte driver innovation. "Disse algoritmer vil have en indflydelse på, hvordan vi bruger kvantecomputere i fremtiden."