Quantum supremacy og dens effektive certificering er vanskelig at opnå samtidigt

I et ironisk twist, fysikere har vist, at selve den egenskab, der kan bruges til at vise, at kvanteberegningsudstyr kan løse nogle problemer, som klassiske computere ikke også kan gøre det umuligt effektivt at bekræfte, at denne "kvanteoverherredømme" faktisk er opnået, til en lang række forskellige ordninger. I kvanteberegning, spørgsmålet om certificering er afgørende for formelt at kontrollere kvanteenheders overlegne computerkraft.

Holdet fra Tyskland, Dominik Hangleiter, Martin Kliesch, Jens Eisert, og Christian Gogolin, har udgivet et papir om deres arbejde med kvanteoverlegenhedscertificering i et nyligt nummer af Fysisk gennemgangsbreve.

"Vi beviser grundigt en intuition, som mange på området delte, nemlig, at certificering af stikprøveudtagningsordninger, der foreslås til en demonstration af kvanteoverherredømme, kræver eksponentielt mange prøver, "Hangleiter, ved det frie universitet i Berlin, fortalt Phys.org . "En af de mest spændende fund af vores arbejde er, at dette skyldes selve den egenskab, der gør det muligt at bevise omtrentlig prøveudtagningshårdhed i første omgang, nemlig, fladheden af ​​de stikprøvefordelinger. Vores arbejde peger også mod en potentiel vej ud af dette dilemma:interaktive eller kvantecertificeringsprotokoller. "

Udtrykket "quantum supremacy" refererer til muligheden for, at quantum computing devices kan løse nogle problemer, der praktisk talt er umulige for klassiske computere at løse. Et problem, der betragtes som uoverskueligt for klassiske computere, er tilfældig prøveudtagning fra visse meget flade fordelinger (hvor alle resultater er næsten lige så sandsynlige) over eksponentielt store datasæt.

I øjeblikket, ingen universel, fejltolerant kvantecomputer er tilgængelig til at eksperimentere med, men selv de begrænsede kvanteenheder, der er tilgængelige i dag, menes at være i stand til at udføre tilfældig prøveudtagning. Intuitivt, dette er fordi kvanteenheder kan forberede en tilstand i den korrekte superposition af alle elementer i et sæt, mens klassiske enheder skal have adgang til de eksponentielt mange sandsynligheder en efter en.

En af begrænsningerne for alle fysiske anordninger (kvante eller klassiske) er, at de kun er i stand til at tilnærme prøvetagning. Så for at demonstrere kvanteoverlegenhed, forskere skal vise, at en kvanteapparats omtrentlige prøveudtagning er tæt nok på ideel prøveudtagning, så den stadig er umulig at håndtere for klassiske computere.

Alle aktuelle beviser på dette koncept, som kaldes omtrentlig prøvehårdhed brug små andre øjeblikke. I tilfældig stikprøveopgave, en fordeling vælges tilfældigt. I det væsentlige, små andre øjeblikke betyder, at den tilfældigt valgte fordeling koncentrerer sig om den ensartede fordeling og derfor er meget flad.

I det nye papir, forskerne viser, at små andre øjeblikke også forbyder effektiv certificering fra prøverne alene. Det er, samplingsfordelinger med små sekundmomenter kan ikke certificeres med polynomisk mange prøver, men kræver i stedet eksponentielt mange prøver. Dette gør certificering ineffektiv og urealistisk at udføre på rimelig tid.

Resultaterne gælder for en række vidt anvendte prøveudtagningsordninger, herunder bosonprøvetagning og universel stikprøveudtagning blandt andre. Imidlertid, resultaterne betyder ikke, at effektiv certificering nødvendigvis er umulig på nogen måde. Forskerne håber, at i stedet, resultaterne vil motivere til udviklingen af ​​alternative certificeringsordninger, samt bevis for omtrentlig prøveudtagningshårdhed, der gælder for fordelinger med større sekundmomenter.

"Vores arbejde vejleder vejen til, hvor vi skal lede efter mulige certificeringsordninger, "Sagde Hangleiter." Især det giver ofte mening at bruge enhedsspecifik viden til at udnytte certificering. En forskningsretning er at udvikle enhedsspecifikke certificeringsordninger både til kvanteprøveudtagningsordninger, men tænker videre, også til mere detaljerede opgaver, der kan udføres på kvantecomputere.

"Kvantumprøveudtagningsordninger er meget 'rene' forslag til kvanteoverherredømme i den forstand, at de giver mulighed for et kompleksitetsteoretisk hårdhedsargument. Samtidig har de har ikke rigtige applikationer (endnu). En anden forskningsretning er at udvikle ordninger, der er mulige på kort sigt, men alligevel hårde, som også løser en nyttig opgave, samt at finde applikationer til de kendte prøveudtagningsordninger. "

© 2019 Science X Network