Vad är en kvantalgoritm?

En kvantalgoritm är en stegvis procedur utförd av en kvantdator. Trots att någon algoritm kan köras på en kvantdator, drar en kvantalgoritm fördel av de unika egenskaperna hos qubits, såsom kvantintrassering och kvantuppsättning.

Ett exempel på en kvantalgoritm är Shors algoritm, som kan användas för att hitta huvudfaktorerna i ett heltal. På en klassisk dator kör denna faktoriseringsprocess i NP (nondeterministisk polynom) tid, vilket innebär att ju svårare problemet blir, det exponentiellt längre det tar. På en kvantdator utförs det emellertid i polynomaltid, vilket gör problemskala linjärt snarare än exponentiellt, så factoring ett mycket stort antal blir inte oåtkomligt. De flesta moderna kryptografiska cifrar baseras på antagandet att factoring stora polynomier är ett NP-tidsproblem. Således är mycket stora siffror inte faktabla med tanke på en rimlig tid och ett rimligt antal resurser. Shors algoritm, som utförs på en kvantdator, skulle emellertid teoretiskt kunna bryta någon sådan kryptering, eftersom de stora siffrorna kunde förklaras i polynomaltiden.

Algoritm, Kryptering, Hårdvarubetecken, Kvantum, Kvantumdator, Qubit