Første bevis på kvantecomputerfordel

I mange år, kvantecomputere var ikke meget mere end en idé. I dag, virksomheder, regeringer og efterretningsbureauer investerer i udviklingen af ​​kvanteteknologi. Robert König, professor i teorien om komplekse kvantesystemer på TUM, i samarbejde med David Gosset fra Institute for Quantum Computing ved University of Waterloo og Sergey Bravyi fra IBM, har nu placeret en hjørnesten på dette lovende område.

Konventionelle computere overholder lovene i klassisk fysik. De er afhængige af de binære tal nul og et. Disse tal gemmes og bruges til matematiske operationer. I konventionelle hukommelsesenheder, hver bit - den mindste informationsenhed - repræsenteres af en ladning, der bestemmer, om bit er sat til en eller nul.

I en kvantecomputer, imidlertid, lidt kan være både nul og en på samme tid. Dette skyldes, at kvantefysikkens love tillader elektroner at besætte flere tilstande ad gangen. Quantum bits, eller qubits, eksisterer således i flere overlappende tilstande. Denne såkaldte superposition gør det muligt for kvantecomputere at udføre operationer på mange værdier i et slag, der henviser til, at en enkelt konventionel computer skal udføre disse operationer i rækkefølge. Løftet om kvanteberegning ligger i evnen til at løse visse problemer betydeligt hurtigere.

Fra formodning til bevis

König og hans kolleger har nu endegyldigt demonstreret fordelen ved kvantecomputere. Til denne ende, de udviklede et kvantekredsløb, der kan løse et specifikt vanskeligt algebraisk problem. Det nye kredsløb har en enkel struktur - det udfører kun et fast antal operationer på hver qubit. Et sådant kredsløb omtales som at have en konstant dybde. I deres arbejde, forskerne beviser, at problemet ved hånden ikke kan løses ved hjælp af klassiske kredsløb med konstant dybde. De besvarer endvidere spørgsmålet om, hvorfor kvantealgoritmen slår ethvert sammenligneligt klassisk kredsløb:Kvantealgoritmen udnytter ikke-lokaliteten af ​​kvantefysikken.

Inden dette arbejde, kvantecomputernes fordel var hverken bevist eller eksperimentelt demonstreret - på trods af at beviser pegede i denne retning. Et eksempel er Shors kvantealgoritme, som effektivt løser problemet med primfaktorisering. Imidlertid, det er blot en kompleksitetsteoretisk formodning, at dette problem ikke effektivt kan løses uden kvantecomputere. Det kan også tænkes, at den rette fremgangsmåde simpelthen endnu ikke er fundet for klassiske computere.

Robert König betragter de nye resultater primært som et bidrag til kompleksitetsteorien. "Vores resultat viser, at kvanteinformationsbehandling virkelig giver fordele-uden at skulle stole på ubeviste kompleksitetsteoretiske formodninger, "siger han. Udover dette, arbejdet giver nye milepæle på vejen til kvantecomputere. På grund af sin enkle struktur, det nye kvantekredsløb er en kandidat til en nærtidseksperimentel realisering af kvantealgoritmer.