Οι κβαντικοί υπολογιστές θα εκμεταλλεύονταν τους παράξενους κανόνες της κβαντικής μηχανικής για να επεξεργάζονται την πληροφορία κατά τρόπους αδύνατους για έναν συνήθη υπολογιστή.
Θα έλυναν ορισμένα συγκεκριμένα προβλήματα, όπως η ανάλυση ακεραίων σε γινόμενο πρώτων παραγόντων, δραματικά ταχύτερα απ’ ό,τι ξέρουμε να τα λύνουμε με τους σημερινούς υπολογιστές, αλλά η ανάλυση δείχνει ότι στα περισσότερα προβλήματα οι κβαντικοί υπολογιστές δεν θα υπερείχαν έναντι των συμβατικών παρά μόνον ελαφρώς.
Εξωτικές τροποποιήσεις στους γνωστούς νόμους της φυσικής θα επέτρεπαν την κατασκευή υπολογιστών οι οποίοι θα μπορούσαν να λύνουν αποδοτικά μεγάλες κλάσεις δύσκολων προβλημάτων. Αυτές οι τροποποιήσεις, εντούτοις, φαίνονται απίθανες. Στον πραγματικό κόσμο, η αδυνατότητα αποδοτικής επίλυσης τούτων των προβλημάτων ίσως θα έπρεπε να ληφθεί ως βασική φυσική αρχή.
