¿Las computadoras cuánticas resolverán el ajedrez?

18

La teoría es que hay más de 10 ^ 40 posiciones, y una computadora que funciona con una escala atómica tiene que ser increíblemente grande (como en una escala de galaxia grande), y mucho más allá de nuestro nivel actual de conocimiento.

Pero ahora, las computadoras cuánticas pronto estarán disponibles. Esta computadora puede tener 2 ^ n, en lugar de n bytes de espacio, debido a los estados cuánticos. Con este nuevo gran lugar para bases de tablas, ¿se resolverá el ajedrez? Por supuesto, esto llevará más avances en el futuro, pero ¿veremos bases de datos de 8 piezas en los próximos años?

Muchas preguntas sobre la posibilidad de resolver el ajedrez giran en el hecho de que no tenemos suficiente espacio en la computadora para llenarlas. ¿Las computadoras cuánticas cambiarán el status quo?

MikhailTal
fuente
10
"Pero ahora, las computadoras cuánticas pronto estarán disponibles" ¿Fuente de esto?
Cleveland
55
Como estudiante de física, déjame asegurarte que las computadoras cuánticas no se usarán para jugar al ajedrez en el corto plazo .
Danu
3
@Spork se podría decir lo mismo sobre "Un amigo mío me mostró un artículo"
Cleveland
3
@Cleveland, eso es tan obvio que dudo que mucha gente tenga mucha fe en él. El amigo probablemente estaba hablando de los juegos de Xbox 2015 de todos modos neowin.net/news/…
Spork
3
Una computadora cuántica no funciona almacenando información clásica por valor de 2 ^ n bits en n qubits y usándola como lo haría una computadora clásica.
JiK

Respuestas:

24

No soy un experto en computación cuántica, pero entiendo que no se espera que las computadoras cuánticas sean útiles para el ajedrez.

Los algoritmos cuánticos son muy buenos para encontrar aguja en un pajar: los tres algoritmos cuánticos son grandes algoritmo de factorización de Shor , el algoritmo de búsqueda de base de datos de Grover y el algoritmo de Deutsch-Jozsa, que esencialmente determina si una larga lista de números es todos ceros, todos unos o la mitad de cada uno. Todos estos problemas pueden verse como ejemplos de "He escondido algo: debes encontrarlo rápidamente". En la factorización, he "ocultado" los factores primos y debes encontrarlos; en la búsqueda en la base de datos, he ocultado una entrada con una clave dada en una tabla grande sin clasificar y debe encontrarla; en el problema resuelto por Deutsch – Jozsa, podría haber colocado una gran cantidad de ceros en una tabla de unos pero, con un algoritmo clásico, cuando has mirado la mitad de la tabla y has visto solo unos, podrías haber tenido mala suerte y miró la mitad "equivocada". Tenga en cuenta también que todos estos problemas podrían resolverse rápidamente con una computadora clásica irrealmente paralela: puede probar todos los factores en paralelo,

Resolver el ajedrez no es ni siquiera un poco como ninguno de estos problemas. Es una actividad fundamentalmente secuencial. Que mi movimiento sea bueno o no depende de lo que hagas en respuesta. Que su respuesta sea buena o no depende de lo que haga en respuesta a eso. Y así. Puede imaginarse que puede hacer la primera capa de la búsqueda al superponer los posibles movimientos. Pero entonces, ¿qué haces en la segunda capa? No puede simplemente tomar la superposición de todas las posiciones en las que podríamos estar después de dos capas porque eso ha olvidado la estructura de árbol. Por ejemplo, considere esta posición muy artificial, con el blanco para moverse:

NN - NN

Si olvidamos la estructura del árbol, Black está muy feliz. Él dice: "¡En dos capas, la mejor posición en la que puedo estar es que entregue jaque mate!" Esto es cierto, pero, por supuesto, las blancas nunca lo permitirán, ya que el mejor movimiento de las blancas es evitar que las negras hagan checkmating (o hagan cualquier otra cosa). El ajedrez no se trata de descubrir el mejor movimiento que puedas hacer en N ply: se trata de descubrir el mejor movimiento que tu oponente te permitirá jugar en N ply. Las computadoras cuánticas no parecen ser buenas en este razonamiento de ida y vuelta. Ni siquiera sabemos cómo resolver el ajedrez con una computadora clásica irrealmente paralela.

David Richerby
fuente
1
No lo pondría más allá de la computación cuántica ... hemos visto un gran progreso en otros problemas de búsqueda de gráficos, como usar el recocido cuántico para resolver el problema del vendedor ambulante. ¿Quizás alguna persona inteligente puede descubrir cómo hacer algo similar en el ajedrez? gizmag.com/d-wave-quantum-computer-supercomputer-ranking/27476
tbischel
2
@tbischel Pero el ajedrez, una búsqueda de árbol de confrontación, no se parece en nada al TSP, que es otro problema de la aguja en un pajar. Además, tenga en cuenta que las afirmaciones de DWave son, digamos, bastante controvertidas . Hay al menos dos grupos que han escrito simulaciones de recocido cuántico que superan a DWave cuando se ejecutan en una computadora portátil común, por ejemplo.
David Richerby
2
No niego que actualmente no exista un equivalente cuántico para decir búsqueda alfa beta ... pero dado que los algoritmos de computación cuántica aún están en su infancia, eso no significa que nunca lo serán. Por ejemplo: web.ist.utl.pt/luis.tarrataca/publications/… En cuanto a DWave, reconozco la controversia que existe ya que su modelo para la computación cuántica es diferente a los modelos estándar ... Me acercaría a ellos con cautela, aunque lo hacen tener clientes como Google, NASA y la NSA.
tbischel
¿El recocido cuántico no resolvería el ajedrez?
Behrang Saeedzadeh
-1

Debe verbalizarse lo que significa exactamente "una solución para el ajedrez".
Entonces entenderemos exactamente qué podemos sacar del hipotético solucionador de ajedrez de caja negra (BBCS).
Alimentaremos a BBCS con la posición del tablero de ajedrez.
BBCS escupirá un número entero X. 0 significa que no hay solución para esa posición (o la posición en sí no es legítima) Otro número entero significa el menor número de movimientos para transformar la posición original en una posición de jaque mate en una cooperativa Ajedrez. La solución definitiva para el ajedrez será solo un número entero, lo que significa el número exacto de movimientos desde la posición inicial del ajedrez hasta la posición de jaque mate. ¿Es una tarea para la computadora cuántica? NO SÉ. Como David Richerby busca: el ajedrez no es para el control de calidad. Pero cuando debemos encontrar un número entero X para declarar "compañero en movimientos X" parece más bien encontrar una aguja en el pajar ... ¿Me equivoco?

usuario21914
fuente
-3

Advertencia justa: esta respuesta contiene números especulativos, y puede estar desactivada por órdenes de magnitud.

Es posible, pero poco probable.

El problema no es necesariamente si las computadoras cuánticas podrán o no "paralelizarse" en esa medida. El problema es uno de física simple, uno que incluso las computadoras cuánticas no pueden sortear de manera realista. En pocas palabras, hay un número limitado de cálculos que se pueden realizar. Esto fue respondido por Thomas Pornin en Security.SE, y cito algunas de sus respuestas aquí:

Veamos una perspectiva más mundana. Parece justo suponer que, con la tecnología existente, cada operación elemental debe implicar de alguna manera el cambio de al menos una puerta lógica. La potencia de conmutación de una sola puerta CMOS es aproximadamente C * V 2, donde C es la capacitancia de carga de la puerta y V es el voltaje al que opera la puerta. A partir de 2011, una puerta muy alta final será capaz de ejecutar con una tensión de 0,5 V y una capacidad de carga de unos pocos femtofaradios ( "femto" que significa "10 -15 "). Esto lleva a un consumo mínimo de energía por operación de no menos de, por ejemplo, 10-15 J. El consumo total de energía mundial actual es de alrededor de 500 EJ (5 * 10 20J) por año (o eso dice este artículo ). Suponiendo que la producción total de energía de la Tierra se desvía a un solo cálculo durante diez años, obtenemos un límite de 5 * 10 36 , que está cerca de 2 122 .

Entonces hay que tener en cuenta los avances tecnológicos. Dada la tendencia actual sobre las preocupaciones ecológicas y el pico del petróleo , la producción total de energía no debería aumentar mucho en los próximos años (digamos no más de un factor de 2 hasta el año 2040, que ya es la pesadilla de un ecólogo). Por otro lado, hay avances tecnológicos en el diseño de circuitos integrados. La ley de Moore establece que puede instalar el doble de transistores en una superficie de chip determinada cada dos años. Una visión muy optimista es que esta duplicación del número de transistores se puede hacer con un consumo de energía constante, lo que se traduciría en reducir a la mitad el costo de energía de una operación primaria cada dos años. Esto llevaría a un gran total de 2 138en el año 2040 , y esto es para un solo cálculo de diez años que moviliza todos los recursos de todo el planeta.

Ese es el número máximo absoluto de operaciones elementales que posiblemente se pueden hacer. Ahora veamos cuántas posiciones de ajedrez hay ...

Hagamos algunos números rápidos. Cada uno de los 64 cuadrados puede estar vacío o contener una de las 12 piezas diferentes (R, K, B, Q, K y P en blanco y negro), por lo que el número total de posiciones que puede establecer es como máximo

13 64 = 196053476430761073330659760423566015424403280004115787589590963842248961.

Eso es aproximadamente 2 x 10 71 posiciones diferentes. Por supuesto, esta es una gran sobreestimación, porque la mayoría de las posiciones son falsas (debemos eliminar las posiciones con tres o más reyes, nueve o más peones blancos, peones en el octavo rango, controles cuádruples, etc.). Tomemos la raíz cuadrada:

13 32 = 442779263776840698304313192148785281,

o aproximadamente 5 x 10 35 . Al sacar la raíz cuadrada, estamos pretendiendo que para cada posición legal hay un Universo de ajedrez con distintas posiciones falsas. Esto es probablemente una subestimación, por lo que la verdadera respuesta debe estar en algún lugar entre estos dos números. Ahora podemos decir con confianza que las computadoras no pueden estudiar todas las posiciones legales en un tiempo razonable. Incluso el "pequeño" 13 32 es demasiado grande ...

Ese número más pequeño termina en algún lugar alrededor de 2 120 más o menos.

Supongamos que representamos nuestros tableros con una cadena de 64 bytes. (Prácticamente se manejaría de manera un poco diferente, pero sigamos con esto por ahora). Si recuerdo mis matemáticas correctamente, una computadora cuántica podría representar esto con una cadena de 8 bytes, o 64 bits. Esto nos deja con un total de 2 126 a 2 130 operaciones elementales solo para almacenar cada posición legal y posible .

Mira eso por un momento. No estamos haciendo nada útil con la información, estamos simplemente almacenarla. Y para hacerlo, estamos movilizando los recursos de todo el planeta . No importa dónde se encuentre físicamente el almacenamiento. Ignora todo el tema del enfriamiento. Deje de lado el tema de la transmisión de datos. Estamos desviando suficiente energía para iluminar la Luna solo para almacenar las posiciones.

Con las expectativas más optimistas, una computadora cuántica podría resolver el ajedrez, a costa de los recursos de todo el planeta. Siendo realistas, eso no sucederá.

Jonathan Garber
fuente
1
Las computadoras cuánticas no tienen ningún problema con la capacidad. La cosa 2 ^ n vs n, entonces 2 ^ 120 posiciones en una cadena de 64 bytes, es 2 ^ 126 posiciones, o 2 ^ 129. una computadora cuántica necesita solo 129 partículas cuánticas para eso (teóricamente). Dado que tendremos la tecnología para la computación cuántica hasta entonces, probablemente la computación no tomará todos los recursos planetarios o todo el espacio planetario. La computadora que puede hacer esto probablemente no será más grande que una habitación grande.
MikhailTal
1
Esto parece ser un malentendido sobre cómo funcionan las computadoras cuánticas. Según tengo entendido, los qbits representan una superposición de todos los estados, donde un único cálculo (transición de puerta de lectura) opera en todos los estados simultáneamente, devolviendo un resultado probabilísticamente. El argumento anterior se aplica a los paradigmas CMOS más tradicionales.
tbischel
Creo que la verdadera pregunta es se puede representar gráficamente en busca encajar en un paradigma de computación cuántica ... He oído que hay buenos resultados para resolver el problema del viajante con los ordenadores cuánticos, así que tal vez hay un acercamiento
tbischel
2
@ JonathanGarber ¿Cómo obtienes 2 ^ 126 o 2 ^ 130? Y no entiendo cómo las puertas CMOS están relacionadas con la estimación de los requisitos de energía de una computadora cuántica.
JiK
3
Esta respuesta es fundamentalmente incorrecta porque se trata completamente de computadoras clásicas y la pregunta es sobre computadoras cuánticas.
David Richerby