¿Es útil el uso común de la informática de 'ignorar constantes' cuando se compara la computación clásica con la computación cuántica?

Daniel Sank mencionó en un comentario , respondiendo a (mi) opinión que la aceleración constante de en un problema que admite un algoritmo de tiempo polinómico es escasa, que$10^8$

La teoría de la complejidad está demasiado obsesionada con los límites de escalamiento de tamaño infinito. Lo que importa en la vida real es qué tan rápido obtienes la respuesta a tu problema.

En Ciencias de la Computación, es común ignorar las constantes en los algoritmos, y en general, esto ha resultado funcionar bastante bien. (Es decir, no son buenos y prácticos algoritmos. Espero que se me conceda (teóricos) algoritmos investigadores han tenido una bastante grande en este lado!)

Pero, entiendo que esta es una situación ligeramente diferente, ya que ahora somos:

1. No se comparan dos algoritmos que se ejecutan en la misma computadora, sino dos algoritmos (ligeramente) diferentes en dos computadoras muy diferentes .
2. Ahora estamos trabajando con computadoras cuánticas , para las cuales quizás las mediciones tradicionales de rendimiento pueden ser insuficientes.

En particular, los métodos de análisis de algoritmos son simplemente métodos . ¡Creo que los métodos informáticos radicalmente nuevos requieren una revisión crítica de nuestros métodos actuales de evaluación del rendimiento!

Entonces, mi pregunta es:

Al comparar el rendimiento de los algoritmos en una computadora cuántica versus los algoritmos en una computadora clásica, ¿es una buena práctica la práctica de 'ignorar' las constantes?

El uso común de la informática de 'ignorar constantes' solo es útil cuando las diferencias en el rendimiento de varios tipos de arquitectura de hardware o software pueden ignorarse con un poco de masaje. Pero incluso en la computación clásica, es importante tener en cuenta el impacto de la arquitectura (comportamiento de almacenamiento en caché, uso del disco duro) si desea resolver problemas difíciles o problemas grandes.

La práctica de ignorar las constantes no es una práctica motivada (en el sentido de ser afirmada continuamente) desde el punto de vista de la implementación. Está impulsado principalmente por un interés en un enfoque para el estudio de algoritmos que se comporta bien bajo composición y admite caracterizaciones simples, de una manera cercana a las matemáticas puras. Los teoremas de aceleración para las máquinas de Turing significaban que cualquier definición sensata no podía intentar precisar la complejidad de los problemas con demasiada precisión para llegar a una teoría sensata; y además, en la lucha por encontrar buenos algoritmos para problemas difíciles, los factores constantes no fueron la parte matemáticamente interesante ...

Este enfoque más abstracto para el estudio de algoritmos fue y es en gran medida fructífero. Pero ahora nos enfrentamos a una situación en la que tenemos dos modelos de cálculo, donde

• Uno se encuentra en un estado avanzado de madurez tecnológica (computación clásica); y
• Uno está en un estado muy inmaduro, pero está intentando realizar un modelo teórico que pueda conducir a mejoras asintóticas significativas (computación cuántica).

En este caso, podemos preguntarnos si tiene sentido considerar el beneficio asintótico, con o sin una cuidadosa contabilidad de los factores constantes. Debido al esfuerzo adicional que puede requerirse para realizar la computación cuántica escalable, no solo los factores escalares sino las "aceleraciones" polinómicas en el rendimiento teórico pueden eliminarse una vez que se tiene en cuenta toda la sobrecarga en la realización de un algoritmo cuántico.

En estos primeros días, también puede haber diferencias significativas en el rendimiento de los diferentes enfoques de la arquitectura cuántica. Esto podría hacer que la elección de la arquitectura sea tan importante (si no más importante) para qué tan bien funciona un algoritmo que el análisis asintótico, del mismo modo que le importaría mucho si realiza su cálculo convencional en una máquina von Neumann o en una red altamente distribuida con latencias significativas

Lo realmente importante para la computación práctica es, y siempre ha sido, no solo algoritmos, sino implementaciones de algoritmos : un algoritmo realizado de cierta manera, en una determinada arquitectura. La práctica común del análisis asintótico que ignora los factores constantes nos permite prestar atención a las razones matemáticas sistemáticas de las diferencias en el rendimiento de los algoritmos, y está prácticamente motivada en aquellas ocasiones en que las diferencias arquitectónicas no son tan grandes como para dominar el rendimiento práctico. .

Con respecto a las tecnologías cuánticas, no estamos en esa feliz situación en la que podemos pasar por alto los factores constantes en cualquier contexto práctico. Pero tal vez algún día podamos hacerlo. Este es el juego largo de las tecnologías de información cuántica: hasta ahora, casi el único juego que los científicos informáticos académicos han jugado alguna vez, en lo que respecta a la tecnología de información cuántica. Anticipando ese día cuando la tecnología cuántica encuentre su base, será bueno para nosotros continuar con el análisis asintótico, como una línea de investigación en el desempeño de los algoritmos cuánticos.

$O\left(f\left[N\right]\right)$$N$

$10^{10}$

$\approx300$

No puede ignorar los factores constantes al comparar la computación cuántica con la computación clásica. Son muy grandes

Por ejemplo, aquí hay una imagen de algunas diapositivas que presenté el año pasado:

Las cosas en la parte inferior son fábricas de estado mágico. Tienen una huella de 150K qubits físicos. Dado que la compuerta AND usa 150K qubits por 0.6 milisegundos, suponemos que el volumen espacio-tiempo de una compuerta AND cuántica es del orden de 90 qubit segundos.

Uno de los objetivos de mis compañeros de trabajo es usar 1 CPU por cada 100 qubits cuando se realiza la corrección de errores. Entonces podríamos decir que 90 segundos qubit requieren 0.9 cpu segundos de trabajo. Hemos hecho que las construcciones cuánticas sean varias veces más eficientes desde que se hizo la imagen de arriba, así que llamémosla 0.1 cpu segundos.

(Hay muchas suposiciones que intervienen en estas estimaciones. Qué tipo de arquitectura, tasas de error, etc. Solo estoy tratando de transmitir una idea de orden de magnitud).

Se necesitan 63 puertas AND para realizar una adición de 64 bits. 63 * 0.1 cpu segundos ~ = 6 cpu segundos. Cuánticamente, una adición de 64 bits cuesta más que un segundo de CPU. Clásicamente, una adición de 64 bits cuesta menos que un nanosegundo de CPU. Hay fácilmente una diferencia de factor constante de 10 mil millones aquí. Si compara con una máquina clásica paralela, como una GPU, los números empeoran aún más. No puede ignorar factores constantes con tantos dígitos.

Por ejemplo, considere el algoritmo de Grover, que nos permite buscar una entrada satisfactoria para una función en evaluaciones sqrt (N) de la función en lugar de N evaluaciones. Agregue el factor constante de 10 mil millones y resuelva dónde la computadora cuántica comienza a requerir menos evaluaciones:

El algoritmo de Grover no puede paralelizar las evaluaciones, y las evaluaciones requieren al menos una puerta AND, por lo que básicamente solo comienza a ver los beneficios de tiempo de CPU cuando la búsqueda lleva decenas de millones de años.

A menos que hagamos que los factores constantes sean mucho mejores, nadie usará la búsqueda de Grover para nada útil. En este momento, la situación cuántica vs clásica es una ventaja exponencial o una quiebra.

Si bien otras respuestas brindan buenos puntos, siento que todavía estoy en desacuerdo un poco. Entonces, compartiré mis propios pensamientos sobre este punto.

En resumen, creo que presentar la constante 'tal cual' es una oportunidad desperdiciada en el mejor de los casos. Quizás es lo mejor que podemos obtener por ahora, pero está lejos de ser ideal.

Pero primero, creo que una breve excursión es nessecary.

¿Cuándo tenemos un algoritmo efectivo?

$10^6$

1. $P$
2. $P^2$$P$
3. $P^2$

$P^2$$P$$P$$P^2$

Por lo tanto, no es irrazonable que nuestro algoritmo de basura parezca tener aceleraciones 'milagrosas'. Ahora, por supuesto, hay muchas técnicas de diseño de experimentos que pueden mitigar el riesgo, pero quizás algoritmos 'rápidos' más inteligentes que todavía fallan en muchos, ¡pero no hay suficientes ejemplos que puedan engañarnos! (también tenga en cuenta que supongo que ningún investigador es malicioso , ¡lo que empeora aún más las cosas!)

Entonces, ahora respondería: "Despiértame cuando haya una mejor métrica de rendimiento".

¿Cómo podemos hacerlo mejor, entonces?

Si podemos permitirnos probar nuestro algoritmo de 'caja negra' en todos los casos, no podemos dejarnos engañar por lo anterior. Sin embargo, esto es imposible para situaciones prácticas. (¡Esto se puede hacer en modelos teóricos!)

Lo que podemos en cambio hacer es crear una estadística de hipótesis para algunos parametrizado el tiempo de funcionamiento (por lo general para el tamaño de la entrada) para probar esto, tal vez adaptar nuestra hipótesis y probar de nuevo, hasta que consigamos una hipótesis que nos gusta y rechazar la hipótesis nula parece razonable. (Tenga en cuenta que probablemente haya otros factores involucrados que estoy ignorando. Soy prácticamente un matemático. El diseño de experimentos no es algo que esté dentro de mi experiencia)

$O(n^3)$

Entonces, ¿qué hacer con las constantes?

$10^9$

Creo que es más útil considerar la constante curiosa como una anomalía , es decir, es una afirmación que en sí misma justifica una mayor investigación. Creo que crear hipótesis basadas en modelos más generales que simplemente "nuestro algoritmo tarda X tiempo" es una buena herramienta para hacerlo. Entonces, aunque no creo que podamos simplemente asumir las convenciones de CS aquí, ignorar por completo el 'desdén' por las constantes también es una mala idea.