Modelos de Computación Cuántica

La computación cuántica reemplaza los bits clásicos por estados cuánticos que pueden superponerse y entrelazarse, definiendo modelos como el circuito cuántico y la clase de complejidad BQP que parecen resolver algunos problemas más rápido que cualquier método clásico.

Definition

Un modelo de computación cuántica procesa información almacenada en cúbits cuyos estados son vectores unitarios en un espacio complejo; la computación aplica puertas cuánticas reversibles para crear superposición y entrelazamiento, y una medición final produce un resultado clásico con probabilidades establecidas por el estado cuántico.

Scope

Este tema abarca los cúbits y las puertas cuánticas, el modelo de circuito cuántico y su equivalencia con la máquina de Turing cuántica, la clase de complejidad BQP de computación cuántica eficiente y su relación con las clases clásicas, algoritmos fundamentales como la factorización de Shor y la búsqueda de Grover, y el papel de la medición y la decoherencia en la definición del modelo.

Core questions

• ¿Cómo cambian la superposición y el entrelazamiento lo que una computación puede hacer?
• ¿Cuál es la relación entre la clase cuántica eficiente BQP y las clases clásicas?
• ¿Para qué problemas ofrecen los algoritmos cuánticos una aceleración demostrable o aparente?
• ¿Cómo restringen la medición y el principio de no clonación la computación cuántica?

Key theories

Modelo de circuito cuántico y BQP

La computación cuántica eficiente se captura mediante circuitos cuánticos de tamaño polinomial sobre un conjunto de puertas universal, definiendo la clase BQP, que contiene P y se cree que la extiende, aunque aún se encuentra dentro de PSPACE.

Aceleraciones cuánticas

El algoritmo de Shor factoriza enteros en tiempo polinomial y el algoritmo de Grover busca en un espacio no estructurado con una aceleración cuadrática, demostrando ventajas concretas del modelo cuántico para tareas específicas.

Clinical relevance

Los modelos cuánticos guían el diseño de hardware y algoritmos cuánticos; el algoritmo de factorización de Shor amenaza los criptosistemas de clave pública cuya seguridad se basa en la dificultad de la factorización, lo que motiva el desarrollo de la criptografía postcuántica, mientras que la simulación cuántica promete avances en química y ciencia de materiales.

History

Feynman propuso usar sistemas cuánticos para simular la física en 1982, y Deutsch formalizó la máquina de Turing cuántica en 1985. El algoritmo de factorización de Shor de 1994 y el algoritmo de búsqueda de Grover de 1996 mostraron aceleraciones concretas, convirtiendo la computación cuántica en una rama importante de la teoría de la complejidad y un motor del esfuerzo experimental.

Debates

¿Qué tan grande es la ventaja cuántica y es físicamente realizable a escala?

Las computadoras cuánticas computan las mismas funciones que las clásicas, por lo que la cuestión es la eficiencia. La relación precisa entre BQP y las clases clásicas no está resuelta, y si se pueden construir grandes computadoras cuánticas tolerantes a fallos a pesar de la decoherencia sigue siendo una cuestión científica y de ingeniería abierta.

Key figures

• Richard Feynman
• David Deutsch
• Peter Shor
• Lov Grover

Seminal works

• nielsenChuang2010
• aroraBarak2009

Frequently asked questions

¿Las computadoras cuánticas computan cosas que las computadoras clásicas no pueden?

No. Las computadoras cuánticas resuelven exactamente la misma clase de problemas que las computadoras clásicas; la diferencia es la velocidad. Para ciertos problemas, como la factorización de números grandes, el modelo cuántico parece ser drásticamente más rápido, pero no extiende el límite de lo que es computable en principio.

¿Por qué la computación cuántica es importante para la criptografía?

El algoritmo de Shor permitiría a una gran computadora cuántica factorizar enteros grandes y computar logaritmos discretos de manera eficiente, rompiendo los sistemas de clave pública que aseguran gran parte de la comunicación actual. Esta perspectiva ha impulsado la búsqueda de esquemas postcuánticos basados en problemas que se consideran difíciles incluso para máquinas cuánticas.