Under många år, kvantdatorer var inte mycket mer än en idé. I dag, företag, regeringar och underrättelsetjänster investerar i utvecklingen av kvantteknologi. Robert König, professor i teori om komplexa kvantsystem vid TUM, i samarbete med David Gosset från Institute for Quantum Computing vid University of Waterloo och Sergey Bravyi från IBM, har nu placerat en hörnsten i detta lovande område.

Konventionella datorer följer den klassiska fysikens lagar. De förlitar sig på de binära talen noll och ett. Dessa nummer lagras och används för matematiska operationer. I konventionella minnesenheter, varje bit – den minsta informationsenheten – representeras av en laddning som avgör om biten är satt till ett eller noll.

I en kvantdator, dock, en bit kan vara både noll och en på samma gång. Detta beror på att kvantfysikens lagar tillåter elektroner att ockupera flera tillstånd samtidigt. Kvantbitar, eller qubits, existerar således i flera överlappande tillstånd. Denna så kallade superposition tillåter kvantdatorer att utföra operationer på många värden i ett svep, medan en enda konventionell dator måste utföra dessa operationer sekventiellt. Löftet om kvantberäkning ligger i förmågan att lösa vissa problem betydligt snabbare.

Från gissningar till bevis

König och hans kollegor har nu definitivt visat fördelen med kvantdatorer. För detta ändamål, de utvecklade en kvantkrets som kan lösa ett specifikt svårt algebraiskt problem. Den nya kretsen har en enkel struktur - den utför bara ett fast antal operationer på varje qubit. En sådan krets kallas att ha ett konstant djup. I sitt arbete, forskarna bevisar att det aktuella problemet inte kan lösas med klassiska kretsar med konstant djup. De svarar vidare på frågan om varför kvantalgoritmen slår alla jämförbara klassiska kretsar:Kvantalgoritmen utnyttjar kvantfysikens icke-lokalitet.

Före detta arbete, fördelen med kvantdatorer var varken bevisad eller experimentellt demonstrerad – trots att bevis pekade i denna riktning. Ett exempel är Shors kvantalgoritm, som effektivt löser problemet med primtalsfaktorisering. Dock, det är bara en komplexitetsteoretisk gissning att detta problem inte kan lösas effektivt utan kvantdatorer. Det är också tänkbart att man helt enkelt ännu inte hittat rätt tillvägagångssätt för klassiska datorer.

Robert König betraktar de nya resultaten främst som ett bidrag till komplexitetsteorin. "Vårt resultat visar att kvantinformationsbehandling verkligen ger fördelar - utan att behöva förlita sig på obevisade komplexitetsteoretiska gissningar, " säger han. Utöver detta, arbetet ger nya milstolpar på vägen mot kvantdatorer. På grund av sin enkla struktur, den nya kvantkretsen är en kandidat för en kortsiktig experimentell realisering av kvantalgoritmer.