Kvantalgoritm

En kvantalgoritm är en algoritm som löper på en realistisk beräkningsmodell för en kvantdator, där den mest använda modellen är beräkningsteorins kvantkretsmodell.^[1][2] En klassisk (icke-kvant) algoritm är en bestämd följd av instruktioner, eller ett stegvist förfarande att lösa ett problem, där varje steg eller instruktion kan utföras på en klassisk dator. På samma sätt är en kvantalgoritm en stegvis metod, där varje steg kan genomföras på en kvantdator. Fastän alla klassiska algoritmer även kan utföras på en kvantdator, så används termen kvantalgoritm vanligen för de algoritmer som förefaller inbegripa kvanta, eller använder någon väsentlig beräkningsmässig kvantegenskap såsom kvantöverlagring eller kvantsammanflätning.

Alla problem som kan lösas på en kvantdator kan lösas på en klassisk dator. Speciellt förblir problem som är obestämbara med klassiska datorer även obestämda med kvantdatorer. Det som gör kvantalgoritmer intressanta är att de skulle kunna lösa vissa problem betydligt snabbare än klassiska algoritmer.

Se även

• Primtalstest

Referenser

1. Nielsen, M.; Chuang, I. (2000). Quantum Computation and Quantum Information. Cambridge University Press. ISBN 0-521-63503-9
2. Mosca, M. (9 oktober 2008). ”Quantum Algorithms”. https://arxiv.org/abs/0808.0369.

Externa länkar

• The Quantum Algorithm Zoo: En vältäckande lista över kvantalgoritmer som ger "speedup" över de snabbast kända klassiska algoritmerna.