Vastestofkwantumchip weet het meestal zeker: 15 = 3 x 5

De University of California in Santa Barbara claimt dat het voor het eerst een getal heeft ontbonden in zijn priemfactoren met een vastestofkwantumcomputer. Na 150 duizend keer draaien concludeerde de kwantumcomputer dat het getal 15 het product is van 3 en 5. Althans, in 48 procent van de gevallen, maar dat is lang niet slecht aangezien het theoretische maximum op 50 procent ligt. Het werk is gepubliceerd in Nature Physics.

Het ontbinden van een getal dat zijn priemfactoren is het klassieke probleem waarvoor kwantumcomputers naar voren geschoven worden. De tijd die nodig is voor het oplossen van deze berekening groeit zeer snel met de grootte van het getal in de klassieke wiskunde. Met een kwantumcomputer gaat dat echter exponentieel sneller, volgens een methode die bekendstaat als het algoritme van Shor.

De Santa Barbara-onderzoekers kozen het getal 15 omdat het het kleinste nummer is waarvoor Shor werkt, namelijk een oneven product van twee priemgetallen. Het probleem van factoriseren is met name relevant voor asymmetrische (publieke-sleutel)cryptografie. Om deze versleuteling te breken zou een klassieke computer langer dan de leeftijd van het universum moeten rekenen om een getal te ontbinden. Shor op en kwantumcomputer zou dat terugbrengen naar minuten.