Os computadores quânticos resolverão o xadrez?

18

A teoria é que existem mais de 10 ^ 40 posições, e um computador que trabalha com uma escala atômica precisa ser impossivelmente grande (como na grande escala da galáxia) e muito além do nosso nível atual de conhecimento.

Mas agora, os computadores quânticos estarão disponíveis em breve. Este computador pode ter 2 ^ n, em vez de n bytes de espaço, devido a estados quânticos. Com este novo espaço para mesas, o xadrez será resolvido? Obviamente, isso exigirá mais avanços no futuro, mas veremos oito bancos de dados nos próximos anos?

Muitas questões sobre a possibilidade de resolver o xadrez giram no fato de que não temos espaço suficiente no computador para preenchê-las. Os computadores quânticos mudarão o status quo?

MikhailTal
fonte
10
"Mas agora, computadores quânticos estarão disponíveis em breve" Fonte sobre isso?
Cleveland
5
Como estudante de física, garanto-lhe que os computadores quânticos não serão usados ​​para jogar xadrez tão cedo .
Danu
3
@Spork você poderia dizer o mesmo sobre "Um amigo meu me mostrou um artigo"
Cleveland
3
@ Cleveland, que é tão óbvio que duvido que muitas pessoas depositem muita fé nisso. O amigo provavelmente estava falando sobre os jogos de 2015 para o Xbox de qualquer maneira neowin.net/news/…
Spork
3
Um computador quântico não funciona armazenando informações clássicas no valor de 2 ^ n bits em n qubits e usando-as como um computador clássico faria.
Jik

Respostas:

24

Não sou especialista em computação quântica, mas meu entendimento é que não se espera que computadores quânticos sejam úteis para o xadrez.

Algoritmos quânticos são muito bons em encontrar agulhas em palheiros: os três grandes algoritmos quânticos são algoritmo de fatoração de Shor , algoritmo de pesquisa de banco de dados de Grover eo algoritmo de Deutsch-Jozsa, que essencialmente determina se uma lista longa de números é todos os zeros, todos os um ou metade de cada um. Todos esses problemas podem ser vistos como exemplos de "Eu escondi algo: você deve encontrá-lo rapidamente". Na fatoração, "ocultei" os fatores principais e você deve encontrá-los; na pesquisa de banco de dados, ocultei uma entrada com uma determinada chave em uma grande tabela não classificada e você deve encontrá-la; no problema resolvido por Deutsch – Jozsa, eu poderia ter colocado um grande número de zeros em uma tabela de uns, mas, com um algoritmo clássico, quando você olhou para metade da tabela e viu apenas alguns, pode ter tido apenas azar e olhou para a metade "errada". Observe também que todos esses problemas podem ser resolvidos rapidamente por um computador clássico irrealisticamente paralelo: você pode tentar todos os fatores em paralelo,

Resolver o xadrez não é nem um pouco como qualquer um desses problemas. É uma atividade fundamentalmente seqüencial. Se minha decisão é boa ou não, depende do que você faz em resposta. Se sua resposta é ou não boa, depende do que eu faço em resposta a isso. E assim por diante. Você pode imaginar que pode fazer a primeira dobra da pesquisa, superpondo os movimentos possíveis. Mas então o que você faz na segunda dobra? Você não pode simplesmente assumir a superposição de todas as posições em que poderíamos estar depois de duas camadas, porque isso esqueceu a estrutura da árvore. Por exemplo, considere esta posição muito artificial, com branco para mover:

NN - NN

Se esquecermos a estrutura da árvore, Black ficará muito feliz. Ele diz: "Em duas dobras, a melhor posição em que posso estar é entregando xeque-mate!" Isso é verdade, mas, é claro, as brancas nunca permitirão isso, já que a melhor jogada das brancas é aquela que impede as pretas de fazer checkmating (ou fazer qualquer outra coisa). O xadrez não é descobrir a melhor jogada que você pode fazer no Nly: é sobre descobrir o melhor lance que o seu oponente permitirá que você jogue no Nly. Os computadores quânticos não parecem ser bons nesse raciocínio alternativo. Nem sabemos como resolver o xadrez com um computador clássico irrealisticamente paralelo.

David Richerby
fonte
1
Eu não colocaria isso na computação quântica ... vimos grandes progressos em outros problemas de tipos de pesquisa de gráficos, como o uso do recozimento quântico para resolver o problema do vendedor ambulante. Talvez uma pessoa inteligente possa descobrir como fazer algo semelhante no xadrez? gizmag.com/d-wave-quantum-computer-supercomputer-ranking/27476
tbischel
2
@tbischel Mas o xadrez, uma pesquisa de árvores contraditória, não se parece em nada com o TSP, que é outro problema do tipo agulha no palheiro. Além disso, observe que as reivindicações da DWave são, digamos, bastante controversas . Há pelo menos dois grupos que escreveram simulações quânticas de recozimento que superam o DWave quando executados em um laptop comum, por exemplo.
David Richerby
2
Não nego que atualmente não exista um equivalente quântico para dizer a pesquisa alfa beta ... mas, dado que os algoritmos de computação quântica ainda estão em sua infância, isso não significa que nunca existam. Por exemplo: web.ist.utl.pt/luis.tarrataca/publications/… Quanto ao DWave, reconheço a controvérsia, pois o modelo para computação quântica é diferente dos modelos padrão ... Eu os abordaria com cautela, embora eles o façam tem clientes como Google, NASA e NSA.
tbischel
O recozimento quântico não resolveria o xadrez?
Lambda
-1

Deve ser verbalizado o que exatamente significa "uma solução para o xadrez".
Então entenderemos o que exatamente podemos obter do hipotético solucionador de xadrez de caixa preta (BBCS).
Vamos alimentar o BBCS com a posição do tabuleiro de xadrez.
O BBCS cuspirá um número inteiro X. 0 significa que não há solução para essa posição (ou a posição em si não é legítima). Outro número inteiro significa o menor número de movimentos para transformar a posição original em uma posição de xeque-mate em uma cooperativa. jogo de xadrez. A solução definitiva para o xadrez será apenas um número inteiro, o que significa o número exato de movimentos da posição inicial do xadrez para uma posição de xeque-mate. É uma tarefa para computadores quânticos? SEI LÁ. Como a pesquisa de David Richerby - xadrez não é para CQ. Mas quando precisamos encontrar um único número inteiro X para declarar "posicionamento em X movimentos", parece mais como encontrar uma agulha no palheiro ... Estou errado?

user21914
fonte
-3

Aviso justo: Esta resposta contém números especulativos e pode ser desativada por ordens de magnitude.

É apenas possível, mas improvável.

A questão não é necessariamente se os computadores quânticos poderão ou não "paralelizar" nessa extensão. O problema é da física simples, que nem mesmo os computadores quânticos conseguem entender. Simplificando, há um número limitado de cálculos que podem ser realizados. Isso foi respondido por Thomas Pornin no Security.SE, e cito algumas de suas respostas aqui:

Vamos olhar para uma perspectiva mais mundana. Parece justo supor que, com a tecnologia existente, cada operação elementar deva de alguma forma implicar a troca de pelo menos um portão lógico. A potência de comutação de uma única porta CMOS é de cerca de C * V 2, onde C é a capacitância de carga da porta e V é a tensão na qual a porta opera. A partir de 2011, um portão de gama alta poderá funcionar com uma tensão de 0,5 V e uma capacitância de carga de algumas femtofarads ("femto" significa "10 -15 "). Isso leva a um consumo mínimo de energia por operação de, pelo menos, 10 a 15 J. O consumo total de energia mundial atual é de cerca de 500 EJ (5 * 10 20J) por ano (ou assim diz este artigo ). Supondo que a produção total de energia da Terra seja desviada para um único cálculo por dez anos, obtemos um limite de 5 * 10 36 , que é próximo a 2 122 .

Então você deve levar em consideração os avanços tecnológicos. Dada a tendência atual de preocupações ecológicas e o pico do petróleo , a produção total de energia não deve aumentar muito nos próximos anos (digamos, apenas um fator de 2 até o ano 2040 - já o pesadelo de um ecologista). Por outro lado, há progresso tecnológico no design de circuitos integrados. A lei de Moore afirma que você pode colocar o dobro de transistores em uma determinada superfície de chip a cada dois anos. Uma visão muito otimista é que essa duplicação do número de transistores pode ser feita com consumo de energia constante, o que se traduz em reduzir pela metade o custo de energia de uma operação elementar a cada dois anos. Isso levaria a um total geral de 2 138no ano de 2040 - e isso é para um único cálculo de dez anos que mobiliza todos os recursos de todo o planeta.

Esse é o número máximo absoluto de operações elementares que podem possivelmente ser feito. Agora vamos ver quantas posições de xadrez existem ...

Vamos fazer alguns números rápidos. Cada um dos 64 quadrados pode estar vazio ou conter uma das 12 peças diferentes (R, K, B, Q, K e P em preto e branco), portanto, o número total de posições que você pode definir é no máximo

13 64 = 196053476430761073330659760423566015424403280004115787589590963842248961.

Isso significa cerca de 2 x 10 71 posições diferentes. É claro que isso é uma superestimação enorme, porque a maioria das posições é falsa (devemos eliminar posições com três ou mais reis, nove ou mais peões brancos, peões na oitava fila, quadruplicar cheques, etc.). Vamos pegar a raiz quadrada:

13 32 = 442779263776840698304313192148785281,

ou cerca de 5 x 10 35 . Tomando a raiz quadrada, estamos fingindo que para cada posição legal existe um universo de xadrez no valor de posições falsas distintas. Provavelmente, essa é uma subestimação, portanto a resposta verdadeira deve estar entre esses dois números. Agora, podemos dizer com segurança que os computadores não podem estudar todas as posições legais em um tempo razoável. Até o "pequeno" 13 32 é muito grande ...

Esse número menor acaba sendo algo em torno de 2 120 ou mais.

Vamos supor que representamos nossas placas com uma cadeia de 64 bytes. (Praticamente isso seria tratado de maneira um pouco diferente, mas vamos continuar com isso por enquanto.) Se eu estiver lembrando minhas contas corretamente, um computador quântico poderá representá-lo com uma string de 8 bytes ou 64 bits. Isso nos deixa com um total de 2 126 a 2 130 operações elementares apenas para armazenar cada posição legal e possível .

Veja isso por um momento. Não estamos fazendo nada útil com as informações, apenas armazenando-as. E para isso estamos mobilizando os recursos de todo o planeta . Não importa onde o armazenamento está fisicamente localizado. Ignore toda a questão do resfriamento. Separe a questão da transmissão de dados. Estamos desviando energia suficiente para iluminar a Lua apenas para armazenar as posições.

Na expectativa mais otimista, um computador quântico pode ser capaz de resolver o xadrez, ao custo de todos os recursos do planeta. Realisticamente, isso não vai acontecer.

Jonathan Garber
fonte
1
Os computadores quânticos não têm problemas com a capacidade. A coisa 2 ^ n vs n, então 2 ^ 120 posições em uma cadeia de 64 bytes, é 2 ^ 126 posições ou 2 ^ 129. um computador quântico precisa apenas de 129 partículas quanta para isso (teoricamente). Como teremos a tecnologia para a computação quântica até então, provavelmente a computação não ocupará todos os recursos planetários ou todo o espaço planetário. O computador que pode fazer isso provavelmente não será maior que uma sala grande.
precisa saber é o seguinte
1
Parece que isso pode ser um mal-entendido de como os computadores quânticos funcionam. Pelo que entendi, qbits representam uma superposição de todos os estados, onde uma única computação (transição de porta de leitura) opera em todos os estados simultaneamente, retornando um resultado probabilisticamente. O argumento acima se aplica a paradigmas CMOS mais tradicionais.
precisa saber é o seguinte
Eu acho que a verdadeira questão é possível representar graficamente a pesquisa se encaixam em um quantum paradigma de computação ... Ouvi dizer que há bons resultados resolver o problema do caixeiro viajando com computadores quânticos, então talvez haja uma abordagem
tbischel
2
@JonathanGarber Como você obtém 2 ^ 126 ou 2 ^ 130? E não entendo como as portas do CMOS estão relacionadas à estimativa dos requisitos de energia de um computador quântico.
Jik
3
Essa resposta está fundamentalmente errada, porque é inteiramente sobre computadores clássicos e a questão é sobre computadores quânticos.
David Richerby