En kvantealgoritme er en algoritme designet for å kjøre på en realistisk modell for kvanteberegning . Den mest brukte modellen er kvantekretsen . [1] [2] Akkurat som en klassisk algoritme er en begrenset sekvens av instruksjoner, eller en trinn-for-trinn-prosedyre for å løse et problem, designet for å kjøre på en klassisk datamaskin, så er en kvantealgoritme en trinn-for-trinn prosedyre designet for å utføres på en kvantedatamaskin . Selv om alle klassiske algoritmer også kan kjøres på en kvantedatamaskin, [3]begrepet "kvantealgoritme" brukes vanligvis for de algoritmene som i seg selv fremstår som kvante, eller som bruker særegne egenskaper ved kvanteberegning som superposisjon av tilstander eller kvanteforviklinger .
De uavgjørelige problemene med klassiske datamaskiner forblir uavgjørelige selv med kvantedatamaskiner. [1] Det som gjør kvantealgoritmer verdig til interesse, er at de kan være i stand til å løse noen problemer raskere enn klassiske datamaskiner fordi superposisjonen av tilstander og kvanteforviklinger som utnyttes av kvantealgoritmer ikke kan simuleres effektivt på datamaskiner. klassikere ( quantum supremacy ) .
De mest kjente algoritmene er Shor-faktoriseringsalgoritmen og Grover-algoritmen for søk i en udifferensiert database. Shors algoritme kjører mye raskere enn den best kjente klassiske algoritmen for faktorisering, den generelle tallfeltsilen . [4] Grovers algoritme kjører kvadratisk raskere enn sekvensielt søk .