¿Reduce la computación cuántica la complejidad computacional de un problema?

Sí, en algunos casos.

Si por complejidad computacional se entiende el “orden de complejidad”, relacionado con el número de operaciones y el tiempo para resolver un problema, entonces el orden de complejidad de algunos algoritmos cuánticos para algunos problemas computacionales es sustancialmente menor que cualquier algoritmo clásico en un ordenador convencional.

Algoritmo cuántico - Wikipedia, la enciclopedia libre

Voy a poner como ejemplo el algoritmo de Shor, que sirve para descomponer en factores un número N y tiene un orden de complejidad O( (log N)^3 ) y un espacio de “memoria” necesario del orden O(log(N)).
Sin embargo, descomponer en factores con algoritmos clásicos tiene un orden de complejidad alrededor de O(N) o bien O(raíz de N)

Ejemplo:
Tenemos una clave criptográfica RSA que consiste en el producto de 2 números primos muy grandes. Si dicho producto es un número de 1024 bits, entonces este número N sería cercano a 2^1024 = 2^(2^10), es decir, un número de unas 308 cifras decimales. El número de operaciones clásicas para descomponerlo en factores sería del orden de 10 elevado a 154… Un ordenador actual, suponiendo 10 GHz (10 000 millones de ciclos por segundo), aún teniendo 8 núcleos, realizaría unos 80 000 millones de operaciones por segundo, cercano a 10 elevado a 11. Si unimos todos los ordenadores del mundo, unos 1000 millones, o tirando por lo alto, 100 000 millones, serían 10 elevado a 11 el número de ordenadores y en conjunto realizarían 10^22 operaciones por segundo… pero como serían necesarias 10^154, entonces se tardaría unos 10^132 segundos… una cantidad astronómica. Un año son unos 32 millones de segundos… tirando por lo alto, unos 100 millones de segundos = 10^8 segundos. Así que se tardaría 10^124 años… millones de millones de millones de años.
Sin embargo, con un algoritmo cuántico, serían unos (log N)^3
log N = 1024… 1024^3 son unos 1000 millones de operaciones o pasos…
Si cada paso tarda una décima de segundo serían alrededor de 100 millones de segundos, que serían unos 3 años.
En otras palabras, lo que con ordenadores clásicos era inabordable, con uno cuántico sería factible… Imagina mensajes secretos de espías o, más bien, las claves para cualquier mensaje pasado o futuro cifrado con una clave, que sean totalmente descifrados en 3 años.
El problema es que no existen, que se sepa, claro, ordenadores cuánticos de 1024 qubits… Y, aparte, se recomienda usar claves de 2048 bits, que requerirían, aún con un ordenador cuántico 8 veces más de tiempo: 24 años con la suposición anterior de que cada operación se hiciese en una décima de segundo.

Existen otro tipo de problemas en los que los ordenadores cuánticos suponen una gran reducción de complejidad, pero no todo problema supone una drástica mejora, al menos, que se sepa.