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

14

Estamos en el advenimiento de la computación cuántica , con lenguajes cuánticos que anticipan computadoras cuánticas de hardware ahora disponibles en niveles altos y bajos para computadoras cuánticas simuladas. La computación cuántica trae nuevas funciones elementales como enredos y teletransportación de qubits, medición de qubits e imposición de superposición sobre qubits.

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

Por ejemplo, ¿las computadoras cuánticas proporcionarán una generación de números aleatorios verdaderos más ubicua? ¿Qué pasa con la generación de números pseudoaleatorios computacionalmente baratos? ¿La computación cuántica ayudará a acelerar la convergencia de MCMC o garantizará límites superiores en el tiempo de convergencia? ¿Habrá algoritmos cuánticos para otros estimadores basados ​​en muestreo?

Esta es una pregunta amplia, y las respuestas aceptables también serán amplias, pero felicitaciones si diferencian la computación cuántica y clásica. (Si esta es una pregunta demasiado amplia , por favor ayúdame a hacerla mejor).

Alexis
fuente
66
+1 Creo que es una buena e interesante pregunta. Dado que invita a muchas (y potencialmente especulativas) respuestas, está en el límite de qué tipo de pregunta funciona aquí. Comparte ese límite con algunos de nuestros hilos más populares y duraderos y, como esos, merece el estado CW.
whuber
77
Dado que el aprendizaje automático es una especie de subdisciplina de estadísticas, puede encontrar interesantes los algoritmos cuánticos para el aprendizaje automático supervisado y no supervisado .
Jakub Bartczuk
2
La informática más rápida siempre es valiosa, pero actualmente la informática cuántica se encuentra en una etapa infantil y todavía no la han superado. Aprecio esta pregunta porque me llevó a aprender algo al respecto. Hasta ahora me resulta difícil de entender.
Michael R. Chernick
1
¿Importa que la computación cuántica todavía esté en su infancia? Funciona y supera a la informática clásica cuando era un bebé. Tampoco no es tan importante, la aceleración puede ser exponencial para problemas tales como resolver ecuaciones matriciales o encontrar el inverso de funciones y cajas negras. Ahora solo necesitamos que crezca. Los algoritmos que pueden ejecutarse en tales computadoras futuras ya se han inventado desde hace décadas. Es simple (aunque muy amplio, solo piense en las ecuaciones matriciales) crear aplicaciones para estadísticas.
Sextus Empiricus el
1
Creo que el primer y más importante punto es que la computación cuántica teóricamente puede acelerar la aritmética en un grado significativo. ¿Es eso correcto? Si es así, todas las rutinas de álgebra lineal ya ven un beneficio.
AdamO

Respuestas:

1

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

Por cierto, los pasos intermedios; las iteraciones, en la optimización no se calcularían, solo el resultado final, al igual que cuando ocurre un campo de béisbol. Es decir, solo se produce la ruta real del béisbol, las rutas alternativas se excluyen automáticamente. Sin embargo, una diferencia entre una implementación estadística y un evento físico es que el error del cálculo estadístico se puede hacer tan pequeño como se desee aumentando arbitrariamente la precisión (p. Ej., A 65 decimales), y esto no suele lograrse físicamente . Por ejemplo, incluso una máquina de lanzamiento no lanzará una pelota de béisbol en un camino exactamente duplicado.

Carl
fuente
+1 gracias. ¿Diría que los métodos de Monte Carlo, los métodos de arranque y otros enfoques cuantitativos para las soluciones se ajustan a la etiqueta "fuerza bruta"?
Alexis
1
Potencialmente, pueden, pero no de la misma manera que la programación lineal. Por ejemplo, el método de Metrópolis y Ulam (simulación de Monte Carlo) fue aplicado originalmente por Ulam para calcular la masa crítica de la bomba atómica. Con la verdadera computación cuántica, una bomba simulada sufrirá una explosión simulada o no, aproximadamente a la misma velocidad que la explosión real. Por cierto, conocí a Ulam en 1964, era un chico joven en aquel entonces.
Carl
1
Gracias, ese punto sobre "explosión simulada" realmente ayuda, y creo que está construyendo mi intuición sobre este tema. También: D Wow!
Alexis
1

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

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

Pero en la década de 1980, que fue hace mucho tiempo, había una compañía de alto perfil llamada Thinking Machines. Vea este artículo: https://en.wikipedia.org/wiki/Thinking_Machines_Corporation

Toda la idea tenía un olor a computación cuántica. Se utilizó una disposición de hipercubos n-dimensional. Imagine, si lo desea, cuatro (muy simples) microprocesadores conectados en un cuadrado. Cada uno podría hacer un cálculo, luego compartir el resultado con el procesador antes (en sentido antihorario), después (en sentido horario) o enfrente (en sentido contrario). Luego imagine 8 procesadores en un cubo que pueden expandir ese concepto a tres dimensiones (cada procesador ahora puede compartir su salida con uno o más de otros 7: 3 a lo largo de un vértice del cubo; tres en la cara de un cuadrado el procesador era parte de, y una diagonal en 3 espacios).

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

Esta fue una de las ideas más populares de la época (junto con la máquina Lisp de 34 bits dedicada que sacó Symbolics y el sistema de memoria solo de caché ligeramente extraño presentado por Kendall Square Research, ambos tienen páginas de Wikipedia que vale la pena leer).

El problema era que había precisamente uno, y solo un algoritmo que realmente funcionaba bien en la arquitectura TM: una Transformada Rápida de Fourier usando lo que se llamó el "Algoritmo de Mezclado Perfecto". Fue una idea genial de cómo usar una técnica de máscara binaria, el algoritmo a medida y la arquitectura para procesar en paralelo un FFT de una manera brillantemente inteligente y rápida. Pero no creo que hayan encontrado otro uso único para ello. (vea esta pregunta relacionada: /cs/10572/perfect-shuffle-in-parallel-processing )

He existido el tiempo suficiente para darme cuenta de que las tecnologías que parecen brillantes y poderosas a menudo terminan sin resolver un problema (o suficientes problemas) para que sean útiles.

Hubo muchas ideas brillantes en ese momento: TM, Symbolics, KSR, así como Tandem (desaparecido) y Stratus (sorprendentemente, todavía vivo). Todos pensaron que estas empresas, al menos algunas , tomarían el mundo y revolucionarían la informática.

Pero, en cambio, tenemos FaceBook.

eSurfsnake
fuente
Tienes razón al llamar la atención, y me gusta tu perspectiva histórica, eSurfsnake. Crecí en el condado de Santa Clara cuando se convirtió en Silicon Valley ... Hace tiempo que aprecio profundamente la computación universal. Una de las razones por las que las estadísticas me conmueven es porque la probabilidad —la verdadera aleatoriedad— está fuera del dominio de la computación. Podemos simularlo ... muy bien para muchos propósitos, pero hay aspectos de la naturaleza, aparentemente, que no son computación. La computación cuántica parece ofrecer operaciones elementales que tampoco son computación de Turing ... así que quiero entender qué significan tales herramientas.
Alexis
@Alexis En realidad, las computadoras cuánticas no tienen ninguna habilidad de super-Turing. Cualquier problema que se pueda calcular usando una computadora cuántica también se puede calcular usando una computadora clásica, que se deduce del hecho de que las computadoras clásicas pueden simular computadoras cuánticas. Pero, hay algunos problemas conocidos que pueden ser resueltos de manera más eficiente usando computadoras cuánticas.
user20160
@ user20160 La aleatoriedad verdadera es una habilidad super-Turing. La superposición es una habilidad super-Turing. La simulación no es la cosa misma.
Alexis
@Alexis No estoy seguro si estamos hablando de lo mismo, pero lo que quiero decir con super-Turing es la capacidad de calcular una función que una máquina de Turing no puede. Curiosamente, la aleatoriedad verdadera no brinda la capacidad de calcular ninguna función que no pueda calcularse de manera determinista. Estoy completamente de acuerdo en que la simulación no es la cosa en sí, sino que está en el corazón mismo de la equivalencia computacional (donde abstraemos la cosa en sí). Si la máquina A puede simular la máquina B, entonces A puede calcular cualquier función que B pueda. Más en Nielsen y Chuang. Computación cuántica e información cuántica
usuario20160
0

¿Qué tipos 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 ", Kenneth S. Schmitz explica:

Los efectos cuánticos se vuelven importantes cuando la longitud de onda de De Broglie se vuelve comparable o es mayor que las dimensiones de la partícula. Cuando esto ocurre, las funciones de onda pueden superponerse, dando diferentes propiedades del sistema.

Los sistemas macroscópicos se pueden analizar mediante métodos clásicos, como explica esa página de Wikipedia:

Una consideración más refinada distingue a la mecánica clásica y cuántica sobre la base de que la mecánica clásica no reconoce que la materia y la energía no se pueden dividir en parcelas infinitamente pequeñas, de modo que la división fina revela características irreductiblemente granulares. El criterio de finura es si las interacciones se describen o no en términos de la constante de Planck. Hablando en términos generales, la mecánica clásica considera las partículas en términos matemáticamente idealizados, incluso tan finos como puntos geométricos sin magnitud, aún teniendo sus masas finitas. La mecánica clásica también considera materiales extendidos idealizados matemáticamente como geométricamente continuos 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. De muchas maneras, La mecánica clásica puede considerarse una teoría principalmente macroscópica. En una 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 son descritas por la mecánica cuántica.

   

Por ejemplo, ¿las computadoras cuánticas proporcionarán una generación de números aleatorios verdaderos más ubicua ?

No. No necesita una computadora para generar un número aleatorio verdadero , y usar una computadora cuántica para hacerlo sería un gran desperdicio de recursos sin una mejora en la aleatoriedad.

ID Quantique tiene SoC disponibles, tarjetas independientes y tarjetas PCIe a la venta por U $ 1200 a U $ 3500 . Es un poco más que fotones viajando a través de un espejo semitransparente, pero tiene suficientes propiedades aleatorias cuánticas para pasar AIS 31 ("Clases de funcionalidad y metodología de evaluación para el generador de números aleatorios (físicos) verdaderos - Versión 3.1 Sept 29 2001" .PDF ). Así es como describen su método:

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

QuintessenceLabs ofrece un sistema más rápido (1 Gbit / s) . Su generador de números aleatorios cuánticos "qStream" cumple con NIST SP 800-90A y cumple con los requisitos del borrador NIST SP 800 90B y C. Utiliza diodos de túnel Esaki . Sus productos son nuevos y los precios aún no están disponibles públicamente.

También están disponibles los sistemas de Comscire por varios cientos a miles de dólares. Sus métodos y patentes PCQNG y post-quantum RNG 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án disponibles pronto.

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

Si quiere decir "computacionalmente barato" como en pocas instrucciones y ejecución rápida = sí.

Si quiere decir que cualquier computadora es un medio económico para generar verdaderos números aleatorios = no.

Cualquier propiedad implementado NGRQ no producirá seudo números aleatorios.

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

Dejaré que alguien más lo tome por el momento.

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

Probablemente.

Edite y mejore esta respuesta Wiki.

Rob
fuente
No estoy seguro de estar de acuerdo con el "verdadero desperdicio de recursos" para un verdadero y confiable RNG. Por un lado, el pseudo-RNG lleva tiempo, que se acumula rápidamente en el trabajo de simulación a gran escala. Por otro lado, RNG toma memoria , y del mismo modo para el trabajo de simulación a gran escala. Tener una fuente rápida y garantizada de aleatoriedad verdadera de una distribución conocida no parece tan derrochador. Además, otras soluciones para el verdadero RNG no impiden que las computadoras cuánticas también brinden dicha solución.
Alexis