¿Qué tipo de problemas estadísticos pueden beneficiarse de la computación cuántica?

Question

Estamos a punto de informática cuántica con lenguajes cuánticos que anticipan los ordenadores cuánticos de hardware ya disponibles en alta y bajo niveles para ordenadores cuánticos simulados. La computación cuántica aporta nuevas funciones elementales como enredo y teletransporte de qubits, medición de qubits, y la imposición de superposición en qubits.

¿Qué tipo de problemas estadísticos pueden beneficiarse de la computación cuántica?

Por ejemplo, ¿proporcionarán los ordenadores cuánticos una verdadera generación de números aleatorios más ubicua? ¿Y la generación de números pseudoaleatorios a bajo coste computacional? ¿Ayudará la computación cuántica a acelerar la convergencia MCMC o a garantizar límites superiores en el tiempo de convergencia? ¿Habrá algoritmos cuánticos para otros estimadores basados en el muestreo?

Se trata de una pregunta amplia, y las respuestas aceptables también lo serán, pero hay que felicitarles si diferencian la computación cuántica de la clásica. (Si se trata de una demasiado amplio pregunta, por favor ayúdame a hacerla mejor).

Answer 1

Acerca de la computación cuántica

La informática cuántica utiliza la superposición y el entrelazamiento.

• Superposición significa que el estado de un sistema es una colección de múltiples estados que se superponen. Intuitivamente se puede ver que la computación cuántica se basa en la mecánica ondulatoria y que el estado del sistema es una onda. En el caso de las ondas, podemos imaginar múltiples ondas superpuestas.

  La superposición permite manipular varios ondas (superpuestas) a la vez en un solo operación.

• Enredo significa que los estados de múltiples componentes del sistema están vinculados por una única ecuación/función de onda.

  Por ejemplo, cuando se crean dos elecciones en un único suceso, la suma de sus espines (uno debe estar hacia arriba y el otro hacia abajo) podría estar vinculada debido a las reglas de conservación (similares a la conservación de la energía o el momento).

  El gran problema filosófico del entrelazamiento está en el colapso de la función de onda. Ocurre cuando se realiza una medición del estado de la función de onda (que descompone el estado superpuesto en un único estado).

  • El "problema" filosófico es que el evento del colapso de la función de onda instantáneamente colapsa el estado de todos los componentes enredados a gran distancia
  • Además hay un problema sobre la interpretación de este colapso de la función de onda (y esto está más relacionado con la superposición). El colapso de la función de onda no es algo que se siga de otros principios/mecanismos básicos, en base a los cuales podamos obtener una comprensión intuitiva. Es más bien un axioma o un principio básico. Para la computación cuántica no importa. Simplemente funciona. Pero la mente humana siente que debería haber algo más detrás de este colapso. Se siente un poco, endeble. El colapso de la función de onda es nuestro "átomo" actual que intentamos dividir en partes.

  El entrelazamiento permite aumentar exponencialmente el número de estados que modelan las funciones de onda superpuestas.

El poder de la informática cuántica

El poder de la computación cuántica reside en la combinación de superposición y entrelazamiento. El sitio $n$ bits cuánticos entrelazados crean $2^n$ diferentes estados del sistema que se superponen entre sí. La superposición nos permite manipular (hacer cálculos con) todos de esos $2^n$ estados simultáneamente . El contraste con la computación no cuántica es que habría que repetir los cálculos $2^n$ tiempos para cada estado por separado.

No hay almuerzo gratis

Tenga en cuenta que no se trata de un almuerzo gratuito. Un ordenador cuántico no es determinista, sino que dará una respuesta diferente cada vez según una cierta distribución.

Podemos manipular múltiples ondas superpuestas formadas por los bits enredados al mismo tiempo. Pero no podemos conozca el estado/amplitud de todas esas ondas superpuestas. Una vez que leemos el estado del sistema sólo conseguimos leer un solo de todos los estados superpuestos del sistema. Se trata del colapso de la función de onda cuando las múltiples ondas superpuestas se convierten en la onda de un único estado.

El comportamiento de este colapso es probabilístico. La probabilidad de observar/colapsar un estado concreto dependerá de la función de onda. Los algoritmos para la computación cuántica están hechos de tal manera que parten de una onda que codifica el $2^n$ estados con una probabilidad más o menos igual. Debido a las manipulaciones/cómputos, el algoritmo acaba con los estados que están cerca de la solución como los que tienen más probabilidades de ser observados.

¿Qué tipo de prestaciones?

Cálculos básicos

Hay varias manipulaciones algebraicas básicas que la computación cuántica puede acelerar. Todas las estadísticas que utilizan este tipo de manipulaciones se beneficiarán de la computación cuántica.

Básicamente, la computación cuántica es capaz de reducir el número de cálculos aplicando cálculos simultáneos. Por ejemplo, al calcular una transformada discreta de Fourier con $2^n$ componentes, el algoritmo cuántico puede utilizar $n$ bits que codifican estos $2^n$ componentes, y por las manipulaciones, en esos $n$ bits que efectivamente está haciendo manipulaciones en el $2^n$ componentes.

¿Qué problemas?

Los problemas que más se beneficiarán de este cálculo simultáneo son los problemas a gran escala que actualmente están limitados por la potencia de cálculo (y que pueden ser en paralelo ). Por ejemplo, problemas de aprendizaje automático, simulaciones Monte Carlo o problemas con una gran dimensionalidad. Los dos primeros de estos tres también son no deterministas (lo que reduce el punto débil de un ordenador cuántico) y son como si el ordenador cuántico hiciera aproximaciones utilizando una estimación basada en la suerte.

Tal vez sería mejor preguntar qué tipo de problemas estadísticos (que requieren muchos cálculos) son los siguientes no ¿se beneficiará de la computación cuántica? Probablemente no mucho.

Answer 2

Los métodos de fuerza bruta tienen más probabilidades de beneficiarse por lo que es la computación cuántica. ¿Por qué? Una posible explicación física de la trayectoria de una pelota de béisbol lanzada es que se exploran automáticamente todas las trayectorias cuánticas posibles y se elige la trayectoria que menos energía gasta, es decir, la trayectoria de menor resistencia disponible, y todo eso se hace sin tener que construir una calculadora; los cálculos son inefables. Generalizando; la naturaleza puede verse como una calculadora cuántica. Así, aquellos problemas que son similares, los que hacen optimización, como la minimización de regresión de algún criterio sea que la bondad de ajuste o otros (la bondad del ajuste está, en algunos casos, mal planteada) son los que se beneficiarán.

BTW, los pasos intermedios; las iteraciones, en la optimización no se calcularían, sólo el resultado final, igual que cuando se produce un lanzamiento de béisbol. Es decir, sólo se produce la trayectoria real de la pelota de béisbol, las trayectorias alternativas se excluyen automáticamente. Una diferencia entre una implementación estadística y un evento físico es, sin embargo, que el error del cálculo estadístico puede hacerse tan pequeño como se desee aumentando arbitrariamente la precisión, (por ejemplo, a 65 decimales), y esto no es típicamente alcanzable físicamente. Por ejemplo, ni siquiera una máquina lanzadora lanzará una pelota de béisbol en una trayectoria exactamente duplicada.

Answer 3

Me ha gustado la respuesta anterior sobre el béisbol. Pero yo sería prudente sobre lo que la computación cuántica podría hacer bien.

Parece que podría ir muy bien en cosas como descifrar esquemas criptográficos y similares: ser capaz de superponer todas las soluciones y luego colapsar sobre la real podría ir bastante rápido.

Pero en los años 80 -hace ya mucho tiempo- había una empresa muy conocida llamada Thinking Machines. Véase este artículo: https://en.wikipedia.org/wiki/Thinking_Machines_Corporation

La idea tenía un tufillo a computación cuántica. Utilizaba un hipercubo n-dimensional. Imagínese cuatro microprocesadores (muy sencillos) conectados en un cuadrado. Cada uno de ellos podría realizar un cálculo y compartir el resultado con el procesador anterior (en el sentido contrario a las agujas del reloj), posterior (en el sentido de las agujas del reloj) u opuesto (en sentido transversal). Imaginemos 8 procesadores en un cubo que puede ampliar este concepto a tres dimensiones (cada procesador puede compartir su resultado con uno o varios de los otros 7): 3 a lo largo de un vértice del cubo; tres a través de la cara de un cuadrado del que forme parte el procesador, y uno en diagonal en el espacio 3).

Ahora lleva esto, a quizás 64 procesadores en un hipercubo de 6 dimensiones.

Esta era una de las ideas más candentes de la época (junto con la máquina Lisp de 34 bits que Symbolics lanzó al mercado y el extraño sistema de memoria caché de Kendall Square Research, ambos con páginas en wikipedia que merece la pena leer).

El problema era que había precisamente un algoritmo, y sólo uno, que funcionaba bien en la arquitectura TM: una Transformada Rápida de Fourier utilizando lo que se llamó el "Algoritmo de Barajado Perfecto". Era una idea genial de cómo utilizar una técnica de máscara binaria, el algoritmo a medida y la arquitectura para procesar en paralelo una FFT de una forma brillantemente inteligente y rápida. Pero no creo que le hayan encontrado otra utilidad. (véase esta pregunta relacionada: https://cs.stackexchange.com/questions/10572/perfect-shuffle-in-parallel-processing )

Llevo el tiempo suficiente para darme cuenta de que las tecnologías que parecen brillantes y potentes a menudo acaban por no resolver un problema (o suficientes problemas) para que sean útiles.

En aquella época había muchas ideas brillantes: TM, Symbolics, KSR, así como Tandem (desaparecida) y Stratus (sorprendentemente, aún viva). Todo el mundo pensaba que estas empresas, al menos algunos de ellos- se apoderaría del mundo y revolucionaría la informática.

Pero, en lugar de eso, tenemos FaceBook.

Answer 4

¿Qué tipo de problemas estadísticos pueden beneficiarse de la computación cuántica?

En la página 645 de " Química Física: Conceptos y Teoría " explica Kenneth S. Schmitz:

Los efectos cuánticos adquieren importancia cuando la longitud de onda de de Broglie es comparable o superior a las dimensiones de la partícula. Cuando esto ocurre, las funciones de onda pueden solaparse, dando lugar a diferentes propiedades del sistema.

Sistemas macroscópicos pueden analizarse por métodos clásicos, como explica esa página de Wikipedia:

Una consideración más refinada distingue la mecánica clásica de la cuántica sobre la base de que la mecánica clásica no reconoce que la materia y la energía no pueden dividirse en parcelas infinitesimalmente pequeñas, de modo que, en última instancia, la división fina revela características irreduciblemente granulares. El criterio de finura es si las interacciones se describen o no en términos de la constante de Planck. A grandes rasgos, la mecánica clásica considera partículas en términos matemáticamente idealizados incluso tan finas como puntos geométricos sin magnitud, que siguen teniendo sus masas finitas. La mecánica clásica también considera los materiales extendidos matemáticamente idealizados como geométricamente continuamente sustanciales. Tales idealizaciones son útiles para la mayoría de los cálculos cotidianos, pero pueden fallar por completo para moléculas, átomos, fotones y otras partículas elementales. En muchos sentidos, la mecánica clásica puede considerarse una teoría principalmente macroscópica. En la escala mucho más pequeña de átomos y moléculas, la mecánica clásica puede fallar, y las interacciones de las partículas se describen entonces mediante la mecánica cuántica.

Por ejemplo, ¿proporcionarán los ordenadores cuánticos más omnipresente ¿Generación real de números aleatorios?

No. No se necesita un ordenador para generar un verdadero número aleatorio, y utilizar un ordenador cuántico para hacerlo sería un enorme derroche de recursos sin ninguna mejora en la aleatoriedad.

ID Quantique dispone de SoC, autónomos y tarjetas PCIe en venta para de U \$1200 to U\$ 3500 . Es algo más que fotones viajando a través de un espejo semitransparente, pero tiene suficiente propiedades aleatorias cuánticas pasar AIS 31 ("Clases de funcionalidad y metodología de evaluación del generador real (físico) de números aleatorios - Versión 3.1 29 Sept 2001" .PDF ). Así es como describen su método:

Quantis es un generador físico de números aleatorios que explota un proceso elemental de óptica cuántica. Los fotones -partículas de luz- se envían uno a uno a un espejo semitransparente y se detectan. Estos eventos exclusivos (reflexión - transmisión) se asocian a valores de bits "0" - "1". Esto nos permite garantizar un sistema verdaderamente imparcial e impredecible.

Un sistema más rápido (1 Gbit/s) es el que ofrece QuintessenceLabs . Su generador cuántico de números aleatorios "qStream" cumple con la norma NIST SP 800-90A y satisface los requisitos del borrador NIST SP 800 90B y C. Utiliza Diodos túnel Esaki . Sus productos son nuevos y los precios aún no se han hecho públicos.

También están disponibles sistemas de Comscire de varios cientos a un par de miles de dólares. Su PCQNG y RNG post-cuántico métodos y patentes se explican en su sitio web.

Quantum Numbers Corp. ha desarrollado un dispositivo del tamaño de un chip para producir rápidamente (1 Gbit/s) números aleatorios cuánticos que, según afirman, estará disponible en breve.

¿Qué hay de la generación de números pseudoaleatorios computacionalmente baratos?

Si te refieres a "computacionalmente barato" como en pocas instrucciones y rápida ejecución = sí.

Si te refieres a que cualquier ordenador es un medio barato para generar verdaderos números aleatorios = no.

Cualquier propiedad implementada QRNG no producirá pseudo números aleatorios.

¿Ayudará la computación cuántica a acelerar Convergencia de Markov Chain Monte Carlo (MCMC) o garantizar límites superiores en el tiempo de convergencia?

Dejaré que otro lo intente por ahora.

¿Habrá algoritmos cuánticos para otros estimadores basados en el muestreo?

Probablemente.

Por favor, edita y mejora esta respuesta Wiki.