Il fatto che proprietà quantistiche quali la polarizzazione di un fotone e lo spin di un elettrone abbiano la capacità di assumere stati "intermedi", le sovrapposizioni, significa che la logica a due valori della computazione binaria è inadeguata per descriverne il comportamento. Agli inizi degli anni novanta è stato coniato il termine qubit, abbreviazione di quantum bit, per descrivere l'unità di memoria quantistica. Un qubit è come un bit classico poiché può immagazzinare uno 0 o un 1, ma ha anche la capacità di contenere una sovrapposizione di stati.

Per capire in che modo questi stati arricchiscono le capacità di un computer è utile spiegare brevemente la notazione. I simboli |0> e |1> sono etichette che contrassegnano gli stati quantistici di un qubit e rappresentano i numeri 0 e 1. La manifestazione fisica di questi stati dipende dall'hardware: nel caso della luce polarizzata, potrebbe significare polarizzazione orizzontale e verticale. Da notare che è l'osservatore a scegliere la rappresentazione. Nel caso di un unico qubit, per rappresentare una particolare sovrapposizione di |0> e |1> si scrive |0> + |1> (che non coincide con 0 + 1). Nel caso della luce polarizzata |0> + |1> rappresenta la luce polarizzata a metà strada tra l'orizzontale e la verticale, ovvero stati sovrapposti. Il generico stato a|0> + b|1> rappresenta una sovrapposizione in cui le ampiezze sono a e b. Se un fascio di fotoni nello stato a|0> + b|1> passa attraverso un filtro orizzontale il numero di fotoni che attraversano il filtro sarà proporzionale al modulo quadro di a.

Il calcolo avviene considerando l'evoluzione nel tempo degli stati governati dalle equazioni della meccanica quantistica che tiene conto di tutte le sovrapposizioni, è per questo che il calcolo non è Turing computabile. Inoltre i fotoni possono essere correlati, entagled. I fotoni entangled sono fotoni che essendo stati generati insieme condividono molte proprietà quantistiche. L'entanglement è la caratteristica essenziale che rende la computazione quantistica molto più potente della computazione classica.

Se si piazzano due filtri polarizzati ai lati di una sorgente di fotoni entagled, si scopre che quando questi hanno la stessa angolazione, ogni fotone passa soltanto se il suo gemello fa altrettanto. Le particelle entangled sembrano condividere qualche informazione su che cosa fare di fronte a filtri polarizzati. I fotoni si scambiano informazione istantaneamente. Se si misurano soltanto i fotoni che emergono da un lato della sorgente, la polarizzazione di ogni singolo fotone è casuale e questo rende impossibile prevedere il risultato di una qualsiasi misurazione individuale nel fascio. Tuttavia, se si misurano le polarizzazioni di entrambi i fotoni di una coppia utilizzando una coppia di cristalli di calcite orientati nello stesso modo, si scopre che ogni fotone si comporta sempre come il proprio gemello. Se un fotone emerge lungo il percorso del fascio ordinario nel primo cristallo, allora possiamo prevedere con certezza che il suo gemello emergerà lungo il percorso del fascio ordinario nel secondo cristallo.

Si dice che i risultati sono perfettamente correlati. Non vi è modo di spiegare la forza della correlazione tra le polarizzazioni in termini di informazione classica. Nessun messaggio o segnale viene scambiato tra le due particelle. L'apparente capacità dei sistemi quantistici di agire a distanza è nota come non località. Alcuni teorici, in particolare David Bohm e i suoi seguaci, hanno cercato di spiegare gli effetti quantistici non locali in termini di variabili nascoste usando un "potenziale" che viaggia istantaneamente da un punto all'altro dello spazio, ma le idee di questo genere cozzano contro la teoria della relatività che esclude segnali più veloci della luce. Benché il fenomeno EPR sembri dare origine a una interazione istantanea tra due oggetti indipendentemente dalla distanza che li separa, non concede in alcun modo di inviare segnali a velocità superiore a quella della luce. Feynman indicò l'effetto EPR come prova dell'esistenza di fenomeni quantistici che non si possono imitare esattamente su un computer classico, se questo deve funzionare in modo completamente locale. Un computer quantistico esibirebbe questa notevole proprietà.