Kompleksitetstest giver nyt perspektiv på små kvantecomputere

State-of-the-art kvanteenheder er endnu ikke store nok til at blive kaldt computere i fuld skala. Den største omfatter kun et par dusin qubits - en ringe tælling i forhold til milliarder af bits i en almindelig computers hukommelse. Men støt fremgang betyder, at disse maskiner nu rutinemæssigt samler 10 eller 20 qubits og snart kan holde styr over 100 eller flere.

I mellemtiden, forskere har travlt med at drømme om anvendelser til små kvantecomputere og kortlægge landskabet af problemer, de vil være egnede til at løse. Et oplæg af forskere fra Joint Quantum Institute (JQI) og Joint Center for Quantum Information and Computer Science (QuICS), udgivet for nylig i Fysisk gennemgangsbreve , hævder, at et nyt ikke-kvanteperspektiv kan hjælpe med at skitsere grænserne for dette landskab og potentielt endda afsløre ny fysik i fremtidige eksperimenter.

Det nye perspektiv involverer et matematisk værktøj - et standardmål for beregningsvanskeligheder kendt som prøveudtagningskompleksitet - der måler, hvor let eller svært det er for en almindelig computer at simulere resultatet af et kvanteeksperiment. Fordi forudsigelserne om kvantefysik er sandsynlige, et enkelt eksperiment kunne aldrig bekræfte, at disse forudsigelser er korrekte. Du skal udføre mange eksperimenter, ligesom du skulle vende en mønt mange gange for at overbevise dig selv om, at du holder hverdag, upartisk nikkel.

Hvis en almindelig computer tager en rimelig tid at efterligne et kørsel af et kvanteeksperiment - ved at producere prøver med omtrent de samme sandsynligheder som den virkelige ting - er prøvetagningskompleksiteten lav; hvis det tager lang tid, prøvetagningskompleksiteten er høj.

Få forventer, at kvantecomputere med mange qubits vil have lav prøveudviklingskompleksitet - trods alt kvantecomputere forventes at være mere kraftfulde end almindelige computere, så det burde være svært at simulere dem på din bærbare computer. Men selvom kvantecomputernes magt stadig er ubevist, at udforske crossoveren fra lav kompleksitet til høj kompleksitet kunne tilbyde frisk indsigt om mulighederne for tidlige kvanteenheder, siger Alexey Gorshkov, en JQI og QuICS Fellow, der er medforfatter til det nye papir.

"Prøveudtagningskompleksitet er fortsat et undervurderet værktøj, "Gorshkov siger, hovedsagelig fordi små kvanteenheder først for nylig er blevet pålidelige. "Disse enheder foretager nu i det væsentlige kvanteprøver, og simulering af dette er kernen i hele vores felt. "

For at demonstrere nytten af ​​denne tilgang, Gorshkov og flere samarbejdspartnere beviste, at prøveudtagningskompleksitet sporer den let-til-hårde overgang af en opgave, som små og mellemstore kvantecomputere forventes at udføre hurtigere end almindelige computere:bosonprøvetagning.

Bosoner er en af ​​de to familier af grundlæggende partikler (den anden er fermioner). Generelt kan to bosoner interagere med hinanden, men det er ikke tilfældet med boson -prøveudtagningsproblemet. "Selvom de ikke interagerer i dette problem, bosoner er sådan set bare interessante nok til at gøre bosonprøvetagning værd at studere, "siger Abhinav Deshpande, en kandidatstuderende ved JQI og QuICS og hovedforfatter af papiret.

I boson -prøveudtagningsproblemet, et fast antal identiske partikler får lov til at hoppe rundt på et gitter, spredt sig ud i kvanteoverlejringer over mange netsteder. At løse problemet betyder prøveudtagning fra denne udtværede kvantesandsynlighedssky, noget en kvantecomputer ikke ville have problemer med at gøre.

Deshpande, Gorshkov og deres kolleger beviste, at der er en skarp overgang mellem, hvor let og svært det er at simulere bosonprøveudtagning på en almindelig computer. Hvis du starter med et par godt adskilte bosoner og kun lader dem hoppe kort rundt, prøveudtagningskompleksiteten er stadig lav, og problemet er let at simulere. Men hvis du venter længere, en almindelig computer har ingen chance for at fange kvanteadfærden, og problemet bliver svært at simulere.

Resultatet er intuitivt, Deshpande siger, da bosonerne på korte tidspunkter stadig er relativt tæt på deres udgangspositioner, og der ikke er fremkommet meget af deres "kvantitet". I længere tid, selvom, der er en eksplosion af muligheder for, hvor en given boson kan ende. Og fordi det er umuligt at skelne to identiske bosoner fra hinanden, jo længere du lader dem hoppe rundt, jo mere sandsynligt er det, at de stille og roligt bytter plads og komplicerer kvantesandsynlighederne yderligere. På denne måde, det dramatiske skift i prøveudtagningskompleksiteten hænger sammen med en ændring i fysikken:Tingene bliver ikke for hårde, før bosoner hopper langt nok til at skifte sted.

Gorshkov siger, at det kan hjælpe med at afdække fysiske overgange i andre kvanteopgaver eller eksperimenter ved at lede efter ændringer som dette i prøveudtagningskompleksiteten. Omvendt mangel på stigende kompleksitet kan udelukke en kvantefordel for enheder, der er for fejlbehæftede. På den ene eller anden måde, Gorshkov siger, fremtidige resultater fra dette perspektivskifte bør være interessante. "Et dybere kig på brugen af ​​stikprøvekompleksitetsteori fra datalogi til at studere kvantefysik i mange legemer er nødt til at lære os noget nyt og spændende om begge felter, " han siger.