Kvantalgoritm

Från Wikipedia
Hoppa till navigering Hoppa till sök

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 kvantintrassling.

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[redigera | redigera wikitext]

Noter och referenser[redigera | redigera wikitext]

  1. ^ Nielsen, M.; Chuang, I. (2000). Quantum Computation and Quantum Information. Cambridge University Press. ISBN 0-521-63503-9 
  2. ^ Mosca, M. (2008). ”Quantum Algorithms”. 'arXiv:0808.0369 [quant-ph]'. 

Externa länkar[redigera | redigera wikitext]

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