Por supuesto, QC puede resolver problemas en P de manera eficiente. Por definición, los problemas en P son eficientes. La pregunta es si QC puede resolver problemas no en P de manera eficiente (es decir, en tiempo P).
Algunos problemas seguro, pero otros no tanto. Creo que mucha criptografía está segura del ataque sensible de QC.
Las afirmaciones de que el control de calidad de trabajo matará a la criptografía se basan en cómo funcionan formas específicas de criptografía de clave pública, especialmente aquellas que dependen de funciones de trampillas como la factorización o logaritmos discretos. Pero por razones prácticas, la criptografía de clave pública se utiliza principalmente para el intercambio de claves y para fines similares. La criptografía simétrica no se beneficia tanto del poder del control de calidad, por lo que no es probable que se vea afectada. Además, existen algoritmos de intercambio de claves y claves públicas que no dependen de las funciones de trampillas que se sabe que son vulnerables al control de calidad.
- ¿Crees que el gobierno de los EE. UU. (O ha) construido / construido una computadora cuántica en secreto para que puedan descifrar lo que quieran?
- ¿Cómo se considera la física cuántica física normal?
- Cómo explicarle a un niño cómo funcionan las computadoras cuánticas
- Cuando los "espiritistas" dicen que la mecánica cuántica es evidencia de que la realidad se ve afectada por qué y cómo pensamos, ¿tienen razón?
- ¿Cuándo podemos esperar computadoras cuánticas disponibles para el mercado de consumo?
La forma en que QC acelera en ciertos problemas es que es posible manipular los estados qubit de manera que la superposición favorezca los estados “correctos” pero no incorrectos. Por ejemplo, al factorizar un número como 21, los qubits se cargan con una superposición de todos los posibles (2–19), luego se manipulan los estados, y al final los estados 3 y 7 tienen una alta probabilidad, pero el 5, 11 y 13 estados tienen baja probabilidad. Verificar el estado de los qubits lo colapsará en 3 o 7 con más frecuencia que cualquier otra cosa.
Es difícil decir cómo se podría aplicar esto a muchos problemas. Hasta donde yo sé, no hay un algoritmo de control de calidad conocido para ningún problema NP-completo, por ejemplo.
