Udvikling af kvantealgoritmer til optimeringsproblemer

Fremtidens kvantecomputere lover at løse komplekse problemer hurtigere end almindelige computere. For eksempel, de kan faktorisere store tal eksponentielt hurtigere end klassiske computere, hvilket ville give dem mulighed for at bryde koder i det mest almindeligt anvendte kryptografisystem. Der er andre potentielle applikationer til kvantecomputere, også, såsom at løse komplicerede kemiproblemer, der involverer molekylers mekanik. Men præcis hvilke typer applikationer vil være bedst til kvantecomputere, som stadig kan være et årti eller mere fra at blive en realitet, er stadig et åbent spørgsmål.

I en ny Caltech undersøgelse, accepteret af Institute of Electrical and Electronics Engineers (IEEE) 2017 Symposium on Foundations of Computer Science, forskere har vist, at kvanteberegning kan være nyttig til at fremskynde løsningerne til "semidefinite programmer, " en meget brugt klasse af optimeringsproblemer. Disse programmer omfatter såkaldte lineære programmer, som bruges, for eksempel, når et selskab ønsker at minimere risikoen for sin investeringsportefølje, eller når et flyselskab effektivt ønsker at tildele besætninger til sine flyvninger.

Undersøgelsen præsenterer en ny kvantealgoritme, der kunne fremskynde løsninger på semidefinite problemer, nogle gange eksponentielt. Kvantealgoritmer er sæt instruktioner, der fortæller kvantecomputere, hvad de skal gøre for at løse problemer.

"Et af målene med kvanteberegning er at fremskynde beregningerne til niveauer, der langt overstiger, hvad klassiske computere kan, " siger Fernando Brandão, Bren-professoren i teoretisk fysik ved Caltech. Brandãos medforfatter er Krysta Svore fra Microsoft, som delvist finansierede undersøgelsen.

Den nye kvantealgoritme ville, i særdeleshed, fremskynde i høj grad semidefinite programmer, der bruges til at lære ukendte kvantetilstande. Brandão siger, at denne type "kvantelæring"-problem står over for forskere, der studerer store kvantesystemer i en række forskellige systemer, såsom superledende qubits, som er kvanteinformationsenheder, der ligner computerbits, der ville fungere baseret på superledende teknologi. De semibestemte programmer bruges til at give en beskrivelse af, hvordan kvantestoffet opfører sig, og dette, på tur, giver forskerne mulighed for bedre at forstå de bizarre tilstande i den subatomære verden.

"Denne type applikation er en god kandidat til brug i kvantecomputere, " siger Brandão. "Vi er stadig langt fra at kende alle anvendelserne af kvanteberegning, og det er en del af spændingen - der er muligheder, vi ikke engang har drømt om endnu."

Studiet, med titlen, "Quantum Speed-ups for Semidefinite Programmering, " blev finansieret af Microsoft, National Science Foundation, og Caltech.