Kvantdatorer del 2: algoritmer som bryter gränser

I den första delen beskrev vi hur kvantdatorer fungerar och varför de skiljer sig från vanliga datorer. Nu handlar det om vad de faktiskt kan göra bättre än klassiska datorer. För även om tekniken fortfarande är ung finns det redan algoritmer som visar hur kvantberäkning kan förändra arbetet med information och matematik. Faktum är att en av de väsentligaste skapades redan 1994...

I klassisk beräkning växer tiden som krävs för att lösa ett problem ofta i takt med storleken på problemet. Vissa uppgifter blir beräkningsmässigt orealistiska eftersom antalet möjliga lösningar växer exponentiellt. Kvantdatorer erbjuder en annan väg genom att kunna utforska många tillstånd samtidigt.

"Quantum computation is a distinctively new way of harnessing nature." David Deutsch, The Fabric of Reality (1997)

Shors algoritm och kryptografi

En av de mest kända kvantalgoritmerna är Shors algoritm, som kan faktorisera stora tal betydligt snabbare än klassiska metoder. Det här får stora konsekvenser eftersom mycket av dagens kryptering bygger på det enkla faktumet att faktorisering är extremt tidskrävande aktivitet.

Resursestimat visar att en felkorrigerad kvantdator i teorin skulle kunna knäcka den mycket utbredda krypteringsalgoritmen RSA 2048 på timmar, eller möjligen enstaka dagar, beroende på arkitektur och antaganden.

Att göra det skulle dock kräva hundratusentals till tiotals miljoner brusiga qubitar - dvs väldigt långt över dagens kvantdatorer. Insikten om detta har dock redan lett till ett intensivt arbete med nya former av säkra algoritmer som kan motstå kvantberäkning.

Grovers algoritm och sökning

På samma sätt som Shors algoritm förändrar kryptografin, förändrar Grovers algoritm sökning. Den erbjuder en kvadratisk förbättring i frågekomplexitet för att hitta en viss post i ett osorterat dataset. Istället för att prova varje alternativ i tur och ordning kan kvantdatorn hitta rätt svar på ungefär roten av antalet steg som annars skulle krävas. För stora sökproblem, optimering och maskininlärning innebär detta att vissa beräkningar kan bli tydligt snabbare.

Till exempel: om det finns en miljon möjliga alternativ (1 000 000) förväntas en klassisk dator hitta rätt halvvägs (500 000 försök) även om den i värsta fall tvingas prova alla. En kvantdator med Grovers algoritm behöver ungefär √1 000 000 ≈ 1 000 försök.

Simulering av naturen

Redan på 1980-talet föreslog Richard Feynman att det mest naturliga sättet att simulera naturen är med kvantmekanik. Klassiska datorer har svårt att beskriva molekyler och material eftersom antalet möjliga tillstånd växer mycket snabbt. Kvantdatorer kan däremot representera dessa tillstånd direkt, vilket gör dem användbara inom kemi, materialforskning och energiteknik.

Företag som IBM, Google och D Wave använder redan små kvantkretsar för att modellera förenklade versioner av katalysatorer, batterimaterial och proteinveckning.

Optimering och sannolikhet

Andra algoritmer som VQE (Variational Quantum Eigensolver) och QAOA (Quantum Approximate Optimization Algorithm) används för att hitta minimeringar i komplexa landskap. De kombinerar klassisk- och kvantberäkning i återkopplade loopar där den klassiska datorn justerar parametrar medan kvantdatorn mäter energitillstånd. Detta gör att problem inom logistik, portföljoptimering och schemaläggning kan angripas på helt nya sätt.

Än så länge fungerar dessa algoritmer bara på små system. Brus, fel och korta koherenstider gör det svårt att bygga ut tekniken. Men utvecklingen går hela tiden framåt.

I nästa del ska vi se hur kvantdatorer och artificiell intelligens börjar samverka och hur det kan förändra sättet vi utvecklar och tränar framtidens system.

//Emil