Professor Henry Yuen ved Columbia University bygger en «fullstendig kvante» kompleksitetsteori for problemer der både input og output er kvantemekaniske. Etter tre tiår med klassiske rammer peker arbeidet mot nye grenser for kvantecomputing – fra kryptografi til sorte hull. Ferske resultater knytter tilsynelatende ulike kvanteproblemer sammen gjennom Uhlmanns teorem.

Hvorfor dagens teori ikke holder

I over 30 år har forskere brukt klassisk kompleksitetsteori for å finne problemer der kvantedatamaskiner slår klassiske maskiner. Denne tilnærmingen har en grunnleggende svakhet: den antar at både input og output er klassiske tallstrenger.

«Tradisjonell kompleksitetsteori er bare stille om dette,» forklarer Yuen. «Kanskje trenger vi en separat teori for å forstå denne andre klassen av problemer.»

Mot en «fullstendig kvante» teori

Yuen, professor i informatikk, var i 2020 med på å bevise et viktig resultat i tradisjonell kompleksitetsteori. Nå leder han en ambisiøs innsats for å utvikle en «fullstendig kvante» teori som kan håndtere uvanlige input- og outputtyper. Forskningen har implikasjoner for felt så forskjellige som kryptografi og sorte hulls fysikk.

Det største åpne spørsmålet er det Yuen kaller «unitary synthesis problemet»:

• Hvis vi visste alt om tradisjonell kompleksitetsteori, ville det fortelle oss alt om fullstendig kvante kompleksitetsteori?
• Eller er disse to verdenene logisk uavhengige?

Når ulike kvanteproblemer viser seg å være ett

I en fersk artikkel har Yuen og kolleger vist at mange tilsynelatende ikke-relaterte kvanteproblemer faktisk er ekvivalente i kompleksitet. Sentralt i bevisene står Uhlmanns teorem, et fundament i kvanteinformasjonsteori om hvordan man kan transformere sammenfiltrede kvantetilstander.

Teamet fant at så ulike utfordringer som dekoding av Hawking-stråling fra sorte hull, komprimering av kvanteinformasjon og kvante-bit commitment i realiteten er det samme problemet i forkledning.

«Uhlmann-transformasjonen er navet som alle disse andre tingene stråler ut fra,» forklarer Yuen.

Kryptografi møter fysikk

Den praktiske utfordringen kommer tydelig frem i kvante-bit commitment. Mens klassiske systemer svekkes av rå regnekraft, kan kvanteversjoner være annerledes – og vanskeligere å angripe.

«Problemet virker mindre matematisk og mer fysisk,» sier Yuen.

Fra restaurantgulv til kvantekompleksitet

Yuens personlige vei er like uventet som forskningen han driver. Han er sønn av flyktninger fra Kambodsja som flyktet fra folkemordet på 1970-tallet. Foreldrene drev en restaurant i Sør-California, der Yuen jobbet gjennom oppveksten. Programmering begynte han med fordi han ville lage dataspill.

«Jeg får nyte dette privilegiet å tenke på matematikk og kvantfysikk, og jobbe med andre som er interessert i disse ekstremt nisje og vanvittig obskure temaene,» reflekterer han. «Det er så langt fra det de måtte gå gjennom.»

Nytt språk, nye verktøy

Å bygge et helt nytt teoretisk rammeverk skiller seg fra å arbeide innenfor etablert teori. Her er det ikke gitte spørsmål eller ferdige veier til bevis.

«Ingen gir deg et teorem og sier 'Her, bevis det,'» forklarer Yuen. «Vi vet ikke engang nødvendigvis hva de riktige spørsmålene er. Men å finne det riktige språket er virkelig viktig, selv om du ikke beviser noe særlig teknisk. Å ikke ha det riktige språket forhindrer deg faktisk i å tenke klart.»

Aktuelle arbeider og konferanser

I tillegg til arbeidet med Uhlmann-transformasjoner har Yuen nylig publisert flere artikler som skal presenteres på de prestisjetunge konferansene QIP 2026, ITCS 2026 og STOC 2025. Arbeidene dekker blant annet:

• Lokale transformasjoner av sammenfiltring
• Tilfeldige unitære operasjoner i konstant kvantetid
• Hardhet ved læring av kvantekretser med kryptografiske anvendelser

Hovedpoeng: Ved å sette Uhlmanns teorem i sentrum og stille spørsmålet om unitary synthesis problemet, kan Yuen være i ferd med å gi feltet språket det trenger for å forstå kvantecomputingens fulle potensial – og dets grenser. Kilder: Quanta Magazine, Henry Yuens forskningsside ved Columbia University.