Framtidens kvantdatorer lovar att lösa komplexa problem snabbare än vanliga datorer. Till exempel, de kan faktorisera stora tal exponentiellt snabbare än klassiska datorer, vilket skulle göra det möjligt för dem att bryta koder i det mest använda kryptografisystemet. Det finns andra potentiella tillämpningar för kvantdatorer, för, som att lösa komplicerade kemiproblem som involverar molekylers mekanik. Men exakt vilka typer av applikationer är bäst för kvantdatorer, som fortfarande kan vara ett decennium eller mer från att bli verklighet, är fortfarande en öppen fråga.

I en ny Caltech-studie, accepterat av Institute of Electrical and Electronics Engineers (IEEE) 2017 Symposium on Foundations of Computer Science, forskare har visat att kvantberäkning kan vara användbar för att påskynda lösningarna till "semidefinita program, " en allmänt använd klass av optimeringsproblem. Dessa program inkluderar så kallade linjära program, som används, till exempel, när ett företag vill minimera risken för sin investeringsportfölj eller när ett flygbolag effektivt vill tilldela besättningar till sina flygningar.

Studien presenterar en ny kvantalgoritm som kan påskynda lösningar på semidefinita problem, ibland exponentiellt. Kvantalgoritmer är uppsättningar instruktioner som talar om för kvantdatorer vad de ska göra för att lösa problem.

"Ett av målen med kvantberäkningar är att påskynda beräkningar till nivåer som vida överstiger vad klassiska datorer kan göra, säger Fernando Brandão, Bren-professorn i teoretisk fysik vid Caltech. Brandãos medförfattare är Krysta Svore från Microsoft, som delvis finansierade studien.

Den nya kvantalgoritmen skulle särskilt, avsevärt snabba upp semidefinita program som används för att lära sig okända kvanttillstånd. Brandão säger att den här typen av "kvantinlärningsproblem" står inför forskare som studerar stora kvantsystem i en mängd olika system som supraledande kvantbitar, som är kvantinformationsenheter som liknar datorbitar som skulle fungera baserat på supraledande teknologi. De semidefinita programmen används för att ge en beskrivning av hur kvantmaterien beter sig, och detta, i tur och ordning, gör det möjligt för forskarna att bättre förstå de bisarra tillstånden i den subatomära världen.

"Denna typ av applikation är en bra kandidat för användning i kvantberäkningar, " säger Brandão. "Vi är fortfarande långt ifrån att känna till alla tillämpningar av kvantberäkning, och det är en del av spänningen - det finns möjligheter som vi inte ens har drömt om än."

Studien, betitlad, "Quantum Speed-ups för Semidefinite Programmering, " finansierades av Microsoft, National Science Foundation, och Caltech.