Hard computing problem kan muligvis kun løses af kvantecomputere

(Phys.org) - Forskere har introduceret et nyt computerproblem og vist, at det ville være ekstremt svært, hvis ikke umuligt, for en klassisk computer at løse, men i teorien kunne det effektivt løses ved hjælp af kvanteteknikker. Problemet, som kaldes gaussisk bosonprøveudtagning, er en ny version af bosonprøvetagning, hvilket er et lignende computerproblem, der blev introduceret for et par år siden med det formål at demonstrere de potentielle fordele ved kvantecomputere frem for klassiske.

Forskerne i den nye undersøgelse, Craig S. Hamilton et al., fra det tjekkiske tekniske universitet i Prag og universitetet i Paderborn i Tyskland, har udgivet et papir om gaussisk bosonprøvetagning i et nylig nummer af Fysisk gennemgangsbreve .

Samlet set, det gaussiske boson -prøveudtagningsproblem ligner meget det oprindelige boson -prøveudtagningsproblem, som blev foreslået i 2011 af Scott Aaronson og Alex Arkhipov. I begge problemer, opgaven er at finde sandsynligheden for at måle bestemte mønstre af fotoner, der kommer fra et optisk system, givet en bestemt inputkonfiguration af fotoner. I kompleksitetsteorien, bosonprøvetagning formodes at være et #P-hårdt problem, hvilket gør det ekstremt usandsynligt, at det kunne løses af en klassisk computer.

Selvom der i øjeblikket ikke findes en kvantecomputer, der er i stand til at løse bosonprøveudtagningsproblemet, flere forskergrupper har forsøgt at implementere og løse problemet ved hjælp af kvanteoptiske eksperimenter. En af de største udfordringer for disse eksperimenter er at generere et stort antal enkeltfotoner. Da perfekt deterministiske kilder til enkeltfotoner ikke er tilgængelige i øjeblikket, alle de hidtil udførte eksperimenter har brugt fotonkilder, der er sandsynlige snarere end deterministiske.

Ulempen ved at bruge probabilistiske fotonkilder er, at omkostningerne ved at generere fotonerne skaleres eksponentielt, når antallet af fotoner stiger. Indtil nu, det største antal fotoner, der bruges, er fem, hvilket ikke er nok til endegyldigt at demonstrere fordelen ved at bruge kvantecomputere. (Yderligere understreger vanskeligheden ved at demonstrere en kvantefordel på dette område, en nylig undersøgelse har vist, at klassiske computere kan simulere boson -prøveudtagningsproblemet ved hjælp af 30 fotoner, tyder på, at kvantemetoderne har mere at bevise end tidligere antaget.)

I et forsøg på at gøre det lettere at opnå et større antal fotoner i bosonprøveeksperimentforsøg, forskerne i den nye undersøgelse kiggede specifikt på bosonprøvetagning ved hjælp af gaussiske stater. Selvom gaussiske stater allerede har været brugt eksperimenter, deres gaussiske natur blev aldrig specifikt undersøgt. Disse stater har fordelen ved at være billigere at producere i eksperimenter.

"Den største fordel ved vores protokol er muligheden for at bruge flere af de genererede fotoner fra vores inputtilstande, "Hamilton fortalte Phys.org." Det betyder, hvis fotonnummer er den største hindring for eksperimentelle, det burde være lettere at demonstrere en kvantefordel ved hjælp af gaussiske stater. "

Et af hovedresultaterne i den nye undersøgelse er, at på trods af at det er lettere at implementere eksperimentelt, Gaussisk bosonprøveudtagning er stadig et #P-hårdt problem og så, som bosonprøvetagning, har også potentiale til at fungere som en platform, der illustrerer fordelene ved kvanteberegning. Specifikt, forskerne viser, at Gaussisk bosonprøvetagning er relateret til en matrixfunktion kaldet Hafnian, et problem så svært, at i øjeblikket ingen klassisk computer effektivt kan tilnærme en løsning.

Samlet set, resultaterne tyder på, at gaussisk bosonprøvetagning kan have flere eksperimentelle og teoretiske fordele i forhold til generel bosonprøveudtagning, og vil sandsynligvis give forskere et andet værktøj til at undersøge, hvor de skal trække grænsen mellem kvante- og klassisk computing.

© 2017 Phys.org