Shor algorithm, Grover algorithm & QEC
På senaste föreläsningen i Kvantinfon gick vi igenom tre mycket relevanta och intressanta saker - Shors algoritm, Grovers algoritm samt QEC (Quantum Error Correction).
Shors algoritm är en algoritm som visar att en kvantdator effektivt kan primtalsfaktorisera stora tal - en av de saker som gjorde att intresset för kvantdatorer blev stort för en tid sen eftersom detta skulle kunna användas för att exempelvis avlyssna mycket information som skickas på internet. Det är förvisso inte bevisat att en klassisk dator Inte kan primtalsfaktorisera effektivt, det är bara ingen som har kommit på någon algorim för det (än).
I den aspekten är Grovers algoritm mycket spännande, ty det är matematiskt bevisat att en klassisk dator inte (någonsin) kommer att kunna bli lika effektiv som den. Grovers algoritm är en så kallad sökalgoritm - givet ett "orakel", en funktion som i vårt exempel antar 0 för alla N st värden utom ett där den tar värdet 1 istället, kan vi med Grovers algoritm hitta detta värde (med en viss sannolikhet) med O(sqrt(N)) beräkningar, till skillnad från en klassisk dator som kommer att behöva O(N) beräkningar. Det kanske inte låter som mycket effektivare - skalning med potens 1/2 istället för potens 1 - men det coola är just att det är bevisat att en klassisk dator aldrig kommer att bli lika effektiv som en kvantdator på detta.
Sist men inte minst pratade vi alltså om QEC - Quantum Error Correction - och detta var något mycket coolare än jag först trott! För att sammanfatta var det var - om vi istället för att lagra informationen vi vill lagra på 1 qubit lagrar den på 5 st qubits, kan vi utföra en viss följd av operationer för att få bort all eventuell brusinducerad dekoherens (förutsatt att dessa operationer utförs mycket snabbare än dekoherenstiderna T_1 och T_2). Detta är hur coolt som helst eftersom ett av de stora problemen med att få en kvantdator som fungerar "en längre stund" just är dekoherens - men med QEC kan vi alltså (endast i teorin än så länge, men ändå) få bort dessa problem!
Vi får lära oss så mycket intressant i denna kurs ^_^