Istnieje kilka modeli obliczeń kwantowych, z których najczęściej stosowanymi są obwody kwantowe. Inne modele obejmują kwantową maszynę Turinga, wyżarzanie kwantowe i adiabatyczne obliczenia kwantowe. Większość modeli opiera się na kwantowym bicie lub „kubicie”, co jest nieco analogiczne do bitu w obliczeniach klasycznych. Kubit może znajdować się w stanie kwantowym 1 lub 0 lub w superpozycji stanów 1 i 0. Kiedy jednak jest mierzony, zawsze wynosi 0 lub 1; prawdopodobieństwo każdego wyniku zależy od stanu kwantowego kubitu bezpośrednio przed pomiarem. Jednym z modeli, który nie wykorzystuje kubitów, są obliczenia kwantowe o zmiennej ciągłej.
Wysiłki zmierzające do zbudowania fizycznego komputera kwantowego koncentrują się na technologiach, takich jak transmony, pułapki jonowe i topologiczne komputery kwantowe, które mają na celu tworzenie wysokiej jakości kubitów.[3]: 2–13 Kubity te mogą być zaprojektowane inaczej, w zależności od pełnego model obliczeniowy, czy stosowane są kwantowe bramki logiczne, wyżarzanie kwantowe lub adiabatyczne obliczenia kwantowe. Obecnie istnieje wiele istotnych przeszkód w konstruowaniu użytecznych komputerów kwantowych. Utrzymanie stanów kwantowych kubitów jest szczególnie trudne, ponieważ cierpią one na dekoherencję kwantową. Dlatego komputery kwantowe wymagają korekcji błędów.
Każdy problem obliczeniowy, który można rozwiązać za pomocą klasycznego komputera, można również rozwiązać za pomocą komputera kwantowego. I odwrotnie, każdy problem, który można rozwiązać za pomocą komputera kwantowego, można również rozwiązać za pomocą komputera klasycznego, przynajmniej w zasadzie, mając wystarczająco dużo czasu. Innymi słowy, komputery kwantowe są zgodne z tezą Churcha-Turinga. Oznacza to, że chociaż komputery kwantowe nie zapewniają żadnych dodatkowych przewag nad komputerami klasycznymi pod względem obliczalności, algorytmy kwantowe dla niektórych problemów mają znacznie mniejszą złożoność czasową niż odpowiadające im znane algorytmy klasyczne. W szczególności uważa się, że komputery kwantowe są w stanie szybko rozwiązać pewne problemy, których żaden klasyczny komputer nie byłby w stanie rozwiązać w żadnym możliwym czasie – wyczyn znany jako „supremacja kwantowa”. Badanie złożoności obliczeniowej problemów w odniesieniu do komputerów kwantowych jest znane jako teoria złożoności kwantowej.