Introduksjon
Kvantedatamaskiner får mye hype, men sannheten er at vi fortsatt ikke er sikre på hva de vil være gode for. Disse enhetene utnytter den særegne fysikken til den subatomære verdenen og har potensial til å utføre beregninger som vanlige, klassiske datamaskiner rett og slett ikke kan. Men det har vist seg vanskelig å finne eksempler på algoritmer med en klar "kvantefordel" som muliggjør ytelse utenfor rekkevidden til klassiske maskiner.
I det meste av 2010-årene følte mange informatikere at en bestemt gruppe applikasjoner hadde en god sjanse til å finne denne fordelen. Visse dataanalyseberegninger ville vært eksponentielt raskere når de ble knust av en kvantedatamaskin.
Så kom Ewin Tang. Som 18 år gammel nyutdannet høyskoleutdannet i 2018 fant hun en ny måte for klassiske datamaskiner å løse disse problemene på, smeller ned fordelen kvantealgoritmene hadde lovet. For mange som jobber med kvantedatamaskiner, Tangsitt arbeid var et oppgjør. "En etter en ble disse superspennende brukssakene nettopp drept," sa Chris Cade, en teoretisk informatiker ved det nederlandske kvanteberegningsforskningssenteret QuSoft.
Men én algoritme overlevde uskadd: en kvantevri på en matematisk nisjetilnærming for å studere "formen" til data, kalt topologisk dataanalyse (TDA). Etter en mengde artikler i september, mener forskere nå at disse TDA-beregningene ligger utenfor rekkevidden til klassiske datamaskiner, kanskje på grunn av en skjult forbindelse til kvantefysikk. Men denne kvantefordelen kan bare oppstå under svært spesifikke forhold, og trekker den praktiske i tvil.
Seth Lloyd, en kvantemekanisk ingeniør ved Massachusetts Institute of Technology som medskapte kvante-TDA-algoritmen, husker dens opprinnelse levende. Han og medfysiker Paolo Zanardi deltok på et kvantefysikkverksted i en idyllisk by i Pyreneene i 2015. Noen dager etter konferansen hoppet de over foredrag for å henge på hotellets uteplass mens de prøvde å vikle hodet rundt en "gal abstrakt" matematisk teknikk de hadde hørt om for å analysere data.
Zanardi hadde forelsket seg i matematikken som lå til grunn for TDA, som var forankret i topologi, en gren av matematikken som er opptatt av funksjoner som forblir når former klemmes, strekkes eller vris. "Dette er en av de grenene av matematikk som bare gjennomsyrer alt," sa Vedran Dunjko, en kvantedataforsker ved Universitetet i Leiden. "Det er overalt." Et av feltets sentrale spørsmål er antall hull i en gjenstand, kalt et Betti-tall.
Topologi kan strekke seg utover våre kjente tre dimensjoner, slik at forskere kan beregne Betti-tallene i fire-, 10- og til og med 100-dimensjonale objekter. Dette gjør topologi til et tiltalende verktøy for å analysere formene til store datasett, som også kan inkludere hundrevis av dimensjoner av korrelasjoner og sammenhenger.
Introduksjon
Foreløpig kan klassiske datamaskiner bare beregne Betti-tall opp til rundt fire dimensjoner. På den pyreneiske hotellterrassen forsøkte Lloyd og Zanardi å bryte den barrieren. Etter omtrent en uke med diskusjon og skriblekte ligninger, hadde de bare beinene til en kvantealgoritme som kunne estimere Betti-tallene i datasett med svært høye dimensjoner. De publisert det i 2016, og forskere ønsket det velkommen inn i gruppen av kvanteapplikasjoner for dataanalyse som de mente hadde en meningsfull kvantefordel.
I løpet av to år var TDA den eneste som ikke hadde blitt påvirket av Tangs arbeid. Mens Tang innrømmer at TDA er "genuint forskjellig fra de andre", ble hun og andre forskere lurt på i hvilken grad flukten kan ha vært et lykketreff.
Dunjko og kollegene hans bestemte seg for å ta en ny sjanse for å finne en klassisk algoritme for TDA som kunne slå ut kvantefordelen. For å gjøre det forsøkte de å bruke Tangs metoder på denne spesielle applikasjonen, uten å vite hva som ville skje. «Vi var egentlig ikke sikre. Det var grunner til å tro at denne kanskje overlever 'tangiseringen',» husket han.
Overlevde det gjorde. I resultater ble først lagt ut som et forhåndstrykk i 2020 og publisert i oktober i Quantum, Dunjkos team viste at TDAs overlevelse ikke var tilfeldig. For å finne en klassisk algoritme som kan holde tritt med kvantealgoritmen, "må du gjøre noe annet enn å bare blindt bruke Ewin Tangs [prosess] til Seth Lloyds algoritme," sa Cade, en av medforfatterne av avisen.
Vi vet ikke sikkert at klassiske algoritmer ikke kan hamle opp med TDA, men vi kan komme dit snart. "Av de fire trinnene vi må ta for å bevise dette ... kanskje vi har gjort tre," sa Marcos Crichigno, en teoretisk fysiker ved oppstarten QC Ware. Det beste beviset så langt kommer fra en artikkel han la ut i fjor med Cade som viser at en lignende topologisk beregning kan ikke løses effektivt av klassiske datamaskiner. Crichigno jobber for tiden med å bevise det samme resultatet for TDA spesifikt.
Crichigno mistenker at TDAs motstandskraft peker på en iboende – og helt uventet – forbindelse til kvantemekanikk. Denne koblingen kommer fra supersymmetri, en teori i partikkelfysikk som foreslår en dyp symmetri mellom partiklene som utgjør materie og de som bærer krefter. Det viser seg, som fysikeren Ed Witten forklarte på 1980-tallet, at topologiens matematiske verktøy lett kan beskrive disse supersymmetriske systemene. Inspirert av Wittens arbeid har Crichigno vært det invertering av denne forbindelsen ved å bruke supersymmetri for å studere topologi.
«Det er galt. Det er en veldig, virkelig, veldig merkelig forbindelse, sier Dunjko, som ikke var involvert i Crichignos arbeid. «Jeg får gåsehud. Bokstavelig."
Denne skjulte kvanteforbindelsen kan være det som skiller TDA fra resten, sa Cade, som har jobbet med Crichigno om dette. "Dette er egentlig et kvantemekanisk problem, selv om det ikke ser ut som det," sa han.
Men mens TDA fortsatt er et eksempel på kvantefordel for nå, har nyere forskning fra Amazon Nettjenester, Google og Lloyds laboratorium ved MIT har betydelig begrenset de mulige scenariene der fordelen er mest åpenbar. For at algoritmen skal løpe eksponentielt raskere enn klassiske teknikker - den vanlige baren for en kvantefordel - må antallet høydimensjonale hull være utenkelig stort, i størrelsesorden billioner. Ellers er algoritmens tilnærmingsteknikk ganske enkelt ikke effektiv, og fjerner enhver meningsfull forbedring i forhold til klassiske datamaskiner.
Det er "et vanskelig sett med forhold å finne" i data fra den virkelige verden, sa Cade, som ikke var involvert i noen av de tre papirene. Det er vanskelig å vite sikkert om disse forholdene eksisterer i det hele tatt, så foreløpig har vi bare vår intuisjon, sa Ryan Babbush, en av seniorforfatterne på Googles studie, og verken han eller Cade forventer at disse forholdene er vanlige.
Tang, nå doktorgradsstudent ved University of Washington, tror ikke TDA er den praktiske kvanteapplikasjonen feltet ser etter, gitt disse begrensningene. "Jeg tror feltet som helhet har blitt omformet" for å gå bort fra algoritmejakt, sa hun. Hun forventer at kvantedatamaskiner vil være mest nyttige for å lære om kvantesystemer selv, ikke for å analysere klassiske data.
Men forskerne bak det siste arbeidet ser ikke på TDA som en blindvei. Under et Zoom-møte mellom alle forskerteamene etter at de nylige fortrykkene gikk opp, "hadde hver enkelt av oss en idé om hva vi skulle gjøre videre," sa Dunjko, som jobbet med Googles team. Crichigno håper for eksempel at å avhøre denne forbindelsen mellom topologi og kvantemekanikk vil gi mer uventede kvanteproblemer som kan være spesielt egnet for kvanteberegning.
Det er alltid trusselen om en kreativ ny klassisk tilnærming som gjør det Tang og Dunjko ikke kunne, og til slutt reduserer TDA. «Jeg ville ikke satse på huset mitt, bilen min eller katten min» på at dette ikke vil skje, sa Dunjko. "Men historien er ikke død. Jeg tror det er hovedgrunnen til at jeg ikke er bekymret i det hele tatt.»
