Будут ли квантовые компьютеры решать шахматы?

18

Теория состоит в том, что существует более 10-40 позиций, и компьютер, который работает с атомным масштабом, должен быть невероятно большим (как в большом масштабе галактики) и намного превышать наш текущий уровень знаний.

Но теперь квантовые компьютеры скоро будут доступны. Этот компьютер может иметь 2 ^ n вместо n байтов пространства из-за квантовых состояний. Будут ли решены шахматы с этим новым большим местом для настольных баз? Конечно, в будущем для этого потребуются новые прорывы, но увидим ли мы 8-кусочные базы данных в следующие годы?

Многие вопросы о возможности решения шахмат связаны с тем, что у нас недостаточно компьютерного пространства для их заполнения. Изменит ли квантовые компьютеры статус-кво?

MikhailTal
источник
10
«Но теперь, квантовые компьютеры скоро будут доступны».
Кливленд
5
Будучи студентом-физиком, позвольте мне заверить вас, что квантовые компьютеры не будут использоваться для игры в шахматы в ближайшее время .
Дану
3
@Spork, вы можете сказать то же самое о «Мой друг показал мне статью»
Кливленд
3
@ Кливленд, что это так очевидно, я сомневаюсь, что многие люди поверили бы в это. Друг, вероятно , идет о 2015 Xbox играх все равно neowin.net/news/...
Spork
3
Квантовый компьютер не работает, сохраняя классическую информацию стоимостью 2 ^ n бит в n кубитах и ​​используя ее, как классический компьютер.
JiK

Ответы:

24

Я не специалист по квантовым вычислениям, но я понимаю, что квантовые компьютеры не должны быть полезны для шахмат.

Квантовые алгоритмы очень хороши при обнаружении игл в стогах: три больших квантовые алгоритмы факторизации алгоритм Шора , алгоритм поиска в базе данных Гровер и алгоритм Дойч-Jozsa, который по существу определяет, является ли длинный список чисел или всеми нулями, всеми единицами или половиной каждого. Все эти проблемы можно рассматривать как примеры: «Я что-то спрятал: вы должны найти это быстро». В факторизации я «спрятал» главные факторы, и вы должны их найти; при поиске в базе данных я спрятал запись с данным ключом в большой несортированной таблице, и вы должны найти ее; в задаче, решенной Дойч-Йозса, я мог бы поместить большое количество нулей в таблицу единиц, но с классическим алгоритмом, когда вы посмотрели половину таблицы и увидели только одну, вам, возможно, просто не повезло и посмотрел на «неправильную» половину. Также обратите внимание, что все эти проблемы могут быть быстро решены с помощью нереально параллельного классического компьютера: вы можете попробовать все факторы параллельно,

Решение шахмат даже не похоже ни на одну из этих проблем. Это принципиально последовательная деятельность. Будет ли мой ход хорошим или нет, зависит от того, что вы делаете в ответ. Будет ли ваш ответ хорошим, зависит от того, что я сделаю в ответ на это. И так далее. Вы можете себе представить, что вы можете сделать первый слой поиска, взяв суперпозицию возможных ходов. Но тогда что ты делаешь на втором сгибе? Вы не можете просто взять суперпозицию всех позиций, в которых мы могли бы находиться после двух слоев, потому что это забыло древовидную структуру. Например, рассмотрим эту очень искусственную позицию с белыми для перемещения:

NN - NN

Если мы забудем древовидную структуру, черные очень счастливы. Он говорит: «В двухслойном варианте лучшая позиция, в которой я могу быть, - это поставить мат!» Это правда, но, конечно, белые никогда не допустят этого, поскольку лучший ход белых - это то, что мешает черным матировать (или делать что-то еще). Шахматы не в том, чтобы определить лучший ход, который вы можете сделать в N ply, а в том, чтобы определить лучший ход, который ваш оппонент позволит вам сыграть в N ply. Кажется, что квантовые компьютеры не очень хороши в этом рассуждении типа «давай-и-бери». Мы даже не знаем, как решить шахматы с нереально параллельным классическим компьютером.

Дэвид Ричерби
источник
1
Я бы не стал отказываться от квантовых вычислений ... мы увидели значительный прогресс в других задачах типа поиска в графе, таких как использование квантового отжига для решения задачи коммивояжера. Может быть, какой-нибудь умный человек может понять, как сделать что-то подобное в шахматах? gizmag.com/d-wave-quantum-computer-supercomputer-ranking/27476
tbischel
2
@tbischel Но шахматы, поиск состязательного дерева, совсем не похожи на TSP, что является еще одной проблемой, связанной с иголкой в ​​стоге сена. Кроме того, обратите внимание, что утверждения DWave, скажем так, довольно противоречивы . Есть, по крайней мере, две группы, которые написали квантовые модели отжига, которые превосходят DWave, например, при работе на обычном ноутбуке.
Дэвид Ричерби
2
Я не отрицаю, что в настоящее время не существует квантового эквивалента альфа-бета-поиска ... но, учитывая, что алгоритмы квантовых вычислений все еще находятся в зачаточном состоянии, это не означает, что они никогда не будут. Например: web.ist.utl.pt/luis.tarrataca/publications/… Что касается DWave, я признаю, что противоречие существует, поскольку их модель для квантовых вычислений отличается от стандартных моделей ... Я бы осторожно подошел к ним, хотя они и делают есть такие клиенты, как Google, NASA и АНБ.
tbischel
Разве квантовый отжиг не решит шахматы?
Бехранг Саидзаде
-1

Оно должно быть выражено словами, что именно означает «решение шахмат».
Тогда мы поймем, что именно мы можем получить от гипотетического шахматного решателя черного ящика (BBCS).
Мы будем кормить BBCS шахматной доской.
BBCS будет выдавать целое число X. 0 означает, что для этой позиции не существует решения (или сама позиция недопустима). Другое целое число означает наименьшее количество ходов для преобразования исходной позиции в контрольную позицию в некооперативной шахматы. Конечным решением для шахмат будет просто целое число, которое означает точное количество ходов от начальной позиции шахмат до контрольной позиции. Это задача для квантового компьютера? ИДК. По словам Дэвида Ричерби, шахматы не для КК. Но когда мы должны найти одно целое число X, чтобы объявить "движения в мате в X", это больше похоже на поиск иголки в стоге сена ... Я ошибаюсь?

user21914
источник
-3

Справедливое предупреждение: этот ответ содержит умозрительные числа и может быть отклонен на порядки.

Это просто возможно, но вряд ли.

Вопрос не обязательно в том, смогут ли квантовые компьютеры "распараллелить" до такой степени. Проблема заключается в простой физике, которую даже квантовые компьютеры не могут реально обойти. Проще говоря, существует ограниченное количество вычислений, которые когда-либо могут быть выполнены. На это ответил Томас Порнин из Security.SE, и я привожу некоторые из его ответов здесь:

Давайте посмотрим на более приземленную перспективу. Представляется справедливым предположить, что при существующей технологии каждая элементарная операция должна как-то подразумевать переключение хотя бы одного логического элемента. Мощность переключения одного КМОП- затвора составляет около C * V 2, где C - емкость нагрузки затвора, а V - напряжение, при котором затвор работает. Начиная с 2011 года, затвор очень высокого класса сможет работать с напряжением 0,5 В и емкостью нагрузки в несколько фемтофарад («фемто» означает «10 -15 »). Это приводит к минимальному потреблению энергии на операцию не менее, скажем, 10 -15 Дж. Текущее общее мировое потребление энергии составляет около 500 ЭДж (5 * 10 20).J) в год (или так говорится в этой статье ). Предполагая, что общее производство энергии на Земле переключается на одно вычисление в течение десяти лет, мы получаем ограничение 5 * 10 36 , которое близко к 2 122 .

Тогда вы должны учитывать технологические достижения. Учитывая текущую тенденцию в отношении экологических проблем и пика добычи нефти , общее производство энергии не должно значительно увеличиться в последующие годы (скажем, не более чем в 2 раза до 2040 года - уже кошмар экологов). С другой стороны, есть технический прогресс в разработке интегральных микросхем. Закон Мура гласит, что вы можете устанавливать вдвое больше транзисторов на заданную поверхность чипа каждые два года. Очень оптимистичный взгляд на то , что это удвоение числа транзисторов может быть сделано при постоянном потреблении энергии, что бы перевести на сокращение наполовину затрат энергии элементарной операции каждые два года. Это приведет к общей сумме 2 138в 2040 году - и это для одного десятилетнего вычисления, которое мобилизует все ресурсы всей планеты.

То есть абсолютное максимальное число элементарных операций , которые могут , возможно , будут сделаны. Теперь давайте посмотрим, сколько там шахматных позиций ...

Давайте сделаем несколько быстрых номеров. Каждый из 64 квадратов может быть пустым или содержать одну из 12 различных фигур (R, K, B, Q, K и P в черно-белых тонах), поэтому общее количество позиций, которые вы можете установить, не должно превышать

13 64 = 196053476430761073330659760423566015424403280004115787589590963842248961.

Это примерно 2 х 10 71 разных позиций. Конечно, это огромная переоценка, потому что большинство позиций являются поддельными (мы должны исключить позиции с тремя или более королями, девятью или более белыми пешками, пешками восьмого ранга, четверными чеками и т. Д.). Давайте возьмем квадратный корень:

13 32 = 442779263776840698304313192148785281,

или около 5 х 10 35 . Взяв квадратный корень, мы притворяемся, что для каждой юридической позиции существует шахматная вселенная, ценная различными поддельными позициями. Вероятно, это недооценка, поэтому истинный ответ должен быть где-то между этими двумя числами. Теперь мы можем с уверенностью сказать, что компьютеры не могут изучить каждую юридическую позицию в разумные сроки. Даже «крошечный» 13 32 слишком большой ...

Это наименьшее число оказывается где-то около 2 120 или около того.

Давайте предположим, что мы представляем наши платы 64-байтовой строкой. (Практически это будет обрабатываться немного по-другому, но давайте пока продолжим.) Если я правильно запомнил свою математику, квантовый компьютер сможет представить это с помощью 8-байтовой строки или 64 бит. Это оставляет нам в общей сложности от 2 126 до 2 130 элементарных операций только для хранения каждой легальной и возможной позиции .

Посмотрите на это на мгновение. Мы не делаем ничего полезного с информацией, мы просто храним ее. И для этого мы мобилизуем ресурсы всей планеты . Не берите в голову, где физически расположен склад. Игнорировать всю проблему охлаждения. Отложите в сторону вопрос передачи данных. Мы отводим достаточно энергии, чтобы осветить Луну только для того, чтобы сохранить позиции.

При самых оптимистичных ожиданиях квантовый компьютер мог бы решать шахматы за счет ресурсов всей планеты. Реально этого не произойдет.

Джонатан Гарбер
источник
1
У квантовых компьютеров нет проблем с производительностью. 2 ^ n против n, то есть 2 ^ 120 позиций в 64-байтовой строке, это 2 ^ 126 позиций, или 2 ^ 129. квантовому компьютеру для этого нужно всего 129 квантовых частиц (теоретически). Поскольку до тех пор у нас будет технология квантовых вычислений, вероятно, вычисления не потребуют всех планетарных ресурсов или всего планетарного пространства. Компьютер, который может сделать это, вероятно, будет не больше, чем большая комната.
MikhailTal
1
Кажется, что это может быть неправильное понимание того, как работают квантовые компьютеры. Насколько я понимаю, кубиты представляют собой суперпозицию всех состояний, в которой одно вычисление (переход чтения затвора) воздействует на все состояния одновременно, возвращая результат вероятностно. Приведенный выше аргумент применим к более традиционным парадигмам CMOS.
tbischel
Я думаю, что реальный вопрос в том, может ли поиск по графу вписаться в парадигму квантовых вычислений ... Я слышал, что есть хорошие результаты решения проблемы коммивояжера с квантовыми компьютерами, так что, возможно, есть подход
tbischel
2
@JonathanGarber Как вы получаете 2 ^ 126 или 2 ^ 130? И я не понимаю, как КМОП-вентили связаны с оценкой энергопотребления квантового компьютера.
JiK
3
Этот ответ в корне неверен, потому что он полностью о классических компьютерах и вопрос о квантовых компьютерах.
Дэвид Ричерби