Voor vele jaren, kwantumcomputers waren niet veel meer dan een idee. Vandaag, bedrijven, overheden en inlichtingendiensten investeren in de ontwikkeling van kwantumtechnologie. Robert Koning, hoogleraar voor de theorie van complexe kwantumsystemen aan de TUM, in samenwerking met David Gosset van het Institute for Quantum Computing aan de Universiteit van Waterloo en Sergey Bravyi van IBM, heeft nu een hoeksteen geplaatst in dit veelbelovende veld.

Conventionele computers gehoorzamen aan de wetten van de klassieke natuurkunde. Ze vertrouwen op de binaire getallen nul en één. Deze getallen worden opgeslagen en gebruikt voor wiskundige bewerkingen. In conventionele geheugeneenheden, elke bit - de kleinste informatie-eenheid - wordt weergegeven door een lading die bepaalt of de bit op één of nul wordt gezet.

In een kwantumcomputer echter, een bit kan tegelijkertijd nul en één zijn. Dit komt omdat de wetten van de kwantumfysica toestaan ​​dat elektronen meerdere toestanden tegelijk bezetten. Kwantumbits, of qubits, dus bestaan ​​in meerdere overlappende staten. Deze zogenaamde superpositie stelt kwantumcomputers in staat om in één klap bewerkingen uit te voeren op vele waarden, terwijl een enkele conventionele computer deze bewerkingen opeenvolgend moet uitvoeren. De belofte van quantum computing ligt in het vermogen om bepaalde problemen aanzienlijk sneller op te lossen.

Van vermoeden naar bewijs

König en zijn collega's hebben nu onomstotelijk het voordeel van kwantumcomputers aangetoond. Hiertoe, ze ontwikkelden een kwantumcircuit dat een specifiek moeilijk algebraïsch probleem kan oplossen. Het nieuwe circuit heeft een eenvoudige structuur:het voert slechts een vast aantal bewerkingen uit op elke qubit. Een dergelijke schakeling wordt een constante diepte genoemd. In hun werk, de onderzoekers bewijzen dat het probleem niet kan worden opgelost met behulp van klassieke circuits met constante diepte. Ze beantwoorden bovendien de vraag waarom het kwantumalgoritme elk vergelijkbaar klassiek circuit verslaat:het kwantumalgoritme maakt gebruik van de non-lokaliteit van de kwantumfysica.

Voorafgaand aan dit werk, het voordeel van kwantumcomputers was niet bewezen en ook niet experimenteel aangetoond - ondanks dat bewijs in deze richting wees. Een voorbeeld is het kwantumalgoritme van Shor, die het probleem van priemfactorisatie efficiënt oplost. Echter, het is slechts een complexiteitstheoretisch vermoeden dat dit probleem niet efficiënt kan worden opgelost zonder kwantumcomputers. Het is ook denkbaar dat voor klassieke computers de juiste aanpak simpelweg nog niet is gevonden.

Robert König beschouwt de nieuwe resultaten vooral als een bijdrage aan de complexiteitstheorie. "Ons resultaat laat zien dat kwantuminformatieverwerking echt voordelen biedt - zonder te hoeven vertrouwen op onbewezen complexiteitstheoretische vermoedens, "zegt hij. Buiten dit, het werk levert nieuwe mijlpalen op op weg naar kwantumcomputers. Door zijn eenvoudige structuur, het nieuwe kwantumcircuit is een kandidaat voor een experimentele realisatie op korte termijn van kwantumalgoritmen.