Computerteoretikere viser vejen til at verificere, at kvante slår klassisk

Mens flere forskergrupper rundt om i verden kapløb om at bygge en skalerbar kvantecomputer, Der er stadig spørgsmål om, hvordan opnåelsen af ​​kvanteoverherredømme vil blive verificeret.

Kvanteoverherredømme er det udtryk, der beskriver en kvantecomputers evne til at løse en beregningsopgave, der ville være uoverkommelig vanskelig for enhver klassisk algoritme. Det betragtes som en kritisk milepæl inden for kvanteberegning, men fordi selve karakteren af ​​kvanteaktivitet trodser traditionel bekræftelse, der har været parallelle bestræbelser på at finde en måde at bevise, at kvanteoverherredømme er blevet opnået.

Forskere ved University of California, Berkeley, har netop vejet ind ved at give et førende praktisk forslag kendt som random circuit sampling (RCS) et kvalificeret godkendelsesstempel med vægten af ​​kompleksitetsteoretiske beviser bag sig. Tilfældig kredsløbssampling er den teknik, Google har fremsat for at bevise, om den har opnået kvanteoverlegenhed med en 72-qubit computerchip kaldet Bristlecone, afsløret tidligere i år.

UC Berkeley computerteoretikere offentliggjorde deres bevis for RCS som en verifikationsmetode i et papir offentliggjort mandag, 29. okt. i journalen Naturfysik .

"Behovet for stærke beviser for kvanteoverherredømme er undervurderet, men det er vigtigt at slå det fast, " sagde undersøgelsens hovedforsker Umesh Vazirani, Roger A. Strauch professor i elektroteknik og datalogi ved UC Berkeley. "Udover at være en milepæl på vejen til nyttige kvantecomputere, quantum supremacy er en ny form for fysikeksperiment til at teste kvantemekanik i et nyt regime. Det grundlæggende spørgsmål, der skal besvares for et sådant eksperiment, er, hvor sikre kan vi være på, at den observerede adfærd virkelig er kvante og ikke kunne have været replikeret med klassiske midler. Det er det, vores resultater adresserer."

De andre efterforskere på dette papir er Adam Bouland og Bill Fefferman, både postdoc-stipendiater, og Chinmay Nirkhe, en ph.d. studerende, alle i Vaziranis teoretiske databehandlingsgruppe.

Investeringer i kvante er ved at blive varmere

Avisen kommer midt i accelereret aktivitet i regeringen, akademi og industri inden for kvanteinformationsvidenskab. Kongressen overvejer National Quantum Initiative Act, og sidste måned, US Department of Energy og National Science Foundation annoncerede næsten 250 millioner dollars i tilskud til støtte for forskning i kvantevidenskab og -teknologier.

På samme tid, Lawrence Berkeley National Laboratory og UC Berkeley annoncerede dannelsen af ​​Berkeley Quantum, et partnerskab designet til at accelerere og udvide innovation inden for kvanteinformationsvidenskab.

Indsatsen er høj, efterhånden som den internationale konkurrence inden for kvanteforskning stiger, og behovet for stadig mere komplekse beregninger vokser. Med ægte kvanteberegning, problemer, der er upraktiske for selv de hurtigste supercomputere til dato, kunne være relativt effektive at løse. Det ville være en game-changer inden for kryptografi, simuleringer af molekylære og kemiske interaktioner og maskinlæring.

Kvantecomputere er ikke begrænset af de traditionelle 0'er og 1'ere af en traditionel computers bits. I stedet, kvantebits, eller qubits, kan kode 0'er, 1s og enhver kvantesuperposition af de to for at skabe flere tilstande samtidigt.

Da Google afslørede Bristlecone, den sagde, at det empiriske bevis på dets kvanteoverherredømme ville komme gennem tilfældig kredsløbsprøvetagning, en teknik, hvor enheden ville bruge tilfældige indstillinger til at opføre sig som et tilfældigt kvantekredsløb. For at være overbevisende, der skal også være stærke beviser for, at der ikke er nogen klassisk algoritme, der kører på en klassisk computer, der kunne simulere et tilfældigt kvantekredsløb, i hvert fald inden for rimelig tid.

Registrering af kvanteaccenter

Vaziranis team henviste til en analogi mellem outputtet fra det tilfældige kvantekredsløb og en streng af tilfældige stavelser på engelsk:selvom stavelserne ikke danner sammenhængende sætninger eller ord, de vil stadig have en engelsk "accent" og vil være genkendeligt anderledes end græsk eller sanskrit.

De viste, at det faktisk er svært for en klassisk computer at producere et tilfældigt output med en "kvanteaccent" gennem en teknisk kompleksitetsteoretisk konstruktion kaldet "worst-to-average-case-reduktion."

Det næste trin var at verificere, at en kvanteenhed faktisk talte med en kvanteaccent. Dette bygger på Goldilocks-princippet - en 50-qubit-maskine er stor nok til at være kraftfuld, men lille nok til at blive simuleret af en klassisk supercomputer. Hvis det er muligt at verificere, at en 50-qubit-maskine taler med en kvanteaccent, så ville det give stærke beviser for, at en 100-qubit maskine, hvilket ville være uoverkommeligt svært at simulere klassisk, ville gøre det, såvel.

Men selv hvis en klassisk supercomputer var programmeret til at tale med en kvante accent, ville det være i stand til at genkende en native speaker? Den eneste måde at verificere højttalerens output er ved en statistisk test, sagde Berkeley-forskerne. Google-forskere foreslår at måle graden af ​​matchning med en metrik kaldet "cross-entropi difference". En krydsentropi-score på 1 ville være et ideelt match.

Den påståede kvanteanordning kan anses for at opføre sig som et ideelt kvantekredsløb med tilføjet tilfældig støj. Fefferman og Bouland siger, at krydsentropi-scoren vil bekræfte ægtheden af ​​kvanteaccenten, forudsat at støjen altid tilføjer entropi til outputtet. Dette er ikke altid tilfældet – for eksempel hvis støjprocessen fortrinsvis sletter 0'er frem for 1'er, det kan faktisk reducere entropien.

"Hvis Googles tilfældige kredsløb genereres af en proces, der tillader sådanne sletninger, så ville krydsentropien ikke være et gyldigt mål for kvanteoverherredømme, " sagde Bouland. "Det er til dels derfor, det vil være meget vigtigt for Google at fastlægge, hvordan dens enhed afviger fra et rigtigt tilfældigt kvantekredsløb."

Disse resultater er et ekko af arbejde, som Vazirani udførte i 1993 med sin elev Ethan Bernstein, åbne døren til kvantealgoritmer ved at præsentere speedups fra kvantecomputere, der overtræder et grundlæggende princip for datalogi kaldet Extended Church-Turing-afhandlingen.

Peter Shor fra Bell Labs tog deres arbejde et skridt videre ved at vise, at et meget vigtigt praktisk problem, heltalsfaktorisering, kunne blive eksponentielt fremskyndet af en kvantecomputer.

"Denne sekvens giver en skabelon for kapløbet om at bygge fungerende kvantecomputere, " sagde Vazirani. "Kvanteoverherredømme er en eksperimentel krænkelse af Extended Church-Turing-afhandlingen. Når det er opnået, den næste udfordring bliver at designe kvantecomputere, der kan løse praktisk brugbare problemer."