[Перевод] Как π объединяет сталкивающиеся блоки и квантовый алгоритм поиска
Любопытный физик обнаружил неожиданную связь между теорией о столкновении блоков и знаменитым квантовым алгоритмом поиска
Что общего у цифр числа π, сталкивающихся блоков и квантовых алгоритмов поиска? Больше, чем вы могли бы подумать. Эту связь обеспечивают две шутливых научных работы — одна от 2003 года, а вторая — от декабря 2019. Совместно они объединяют миры динамики, геометрии и квантовых вычислений, показывая, как даже самые абстрактные математические загадки могут удивительным образом обнаруживать связь с физикой.
Блокировка
Чтобы начать понимать эти связи, представьте себе два металлических блока, каждый из которых весит по 1 кг. Они находятся на поверхности без трения, справа от неподвижной стены. Ближайший к стене блок неподвижен, второй скользит к нему, приближаясь справа. Неизбежно должна произойти серия столкновений; предположим, что кинетическая энергия в столкновениях не пропадает. При таких идеальных условиях данный процесс будет проистекать примерно так:
Правый блок соударяется с левым, передавая ему весь импульс. Левый блок отскакивает от стены, возвращается к правому для ещё одного столкновения и ещё одной полной передачи импульса.
Однако если увеличить массу правого блока, ситуация станет более интересной. Если он весит 100 кг, с каждым столкновением он будет передавать только небольшую часть своего импульса меньшему блоку, и вместо количество столкновений возрастёт с 3 до 31.
При соотношении масс 10 000 к 1 ситуация разрешится уже после 314 столкновений.
Увеличивайте разницу, умножая массу на 100, и вы сможете наблюдать шокирующую тенденцию: количество столкновений всё ближе начнёт приближаться к числу π.
Григорий Галперин, математик из университета Восточного Иллинойса первым заметил это явление [в 1993 году]. В 2003 году он объяснил его, визуализируя движения блоков через движущуюся точку, чьи координаты по х обозначают местоположение одного блока, а по у — второго. Траектория движения точки по плоскости связана с полукругом, откуда и появляется π.
Примечательный результат, пусть эти идеальные условия и делают его вроде бы бесполезным. Однако если в математике отбросить неряшливость реального мира, можно найти чистую закономерность, раскрывающую неожиданные связи с другими областями науки.
В 2019 году я публиковал набор из трёх видео, объясняющих полученные Гальпериным результаты, и среди тех, кто их посмотрел, оказался Адам Браун, исследователь из Google и физик из Стэнфордского университета. Через несколько месяцев на конферении от отвёл меня в сторону, чтобы поделиться своим наблюдением. К своему восторгу он обнаружил, что математика, описывающая динамику этих блоков, с определённой точки зрения становится идентичной математике, описывающей один из наиболее известных квантовых алгоритмов.
Квантовый подход
Это приводит нас ко второй части головоломки: как работает квантовый поиск.
Допустим, у вас имеется длинный список имён без сортировки — допустим, миллион — и вам надо найти конкретное имя. Других вариантов, кроме как проверять одно имя за другим, пока вы не наткнётесь на нужное, у вас нет. В среднем это займёт у вас полмиллиона итераций. Иногда больше, иногда меньше, однако в любом случае это займёт у вас какое-то время.
Компьютер мог бы заняться этим поиском вместо вас, но проблема больших списков в том, что количество времени на их обработку будет расти пропорционально их размеру. По крайней мере, при работе классического компьютера. Но в 1996 году Лов Гровер, работавший в лабораториях Белла, описал, как квантовый компьютер может выполнить такой поиск гораздо быстрее, и не более, чем за 1000 шагов. В общем случае, квантовый компьютер справится со списком длиной N за π/4 √N шагов. Заметьте, что с ростом числа N количество шагов работы у квантового компьютера растёт медленнее, чем у классического.
Подобная эффективность поиска возможна потому, что квантовый компьютер обрабатывает все элементы списка одновременно. Однако он не просто делает то же самое, что делал бы классический компьютер, только одновременно.
Классический компьютер отвечает на вопрос: «Является ли 21-й элемент списка тем именем, что мне нужно?» И повторяет его для каждой позиции списка, от 0 до 999 999. Прямолинейно, но не очень эффективно.
А вот алгоритм Гровера работает со списком методом, который сначала кажется странным, но в итоге оказывается более полезным. Классический компьютер может просто считывать биты из памяти. Неопределённости, присутствующие в квантовых вычислениях, приводят к тому, что нельзя напрямую вытащить компоненты вектора, с которым вы работаете. Каждая позиция в списке обладает дополнительной вероятностной структурой. Вы не смотрите, какое имя стоит на данной позиции, вы измеряете весь список целиком, получая случайную позицию — индекс — в соответствии с вероятностями. Из-за лежащей в основе квантовой механики, вместо того, чтобы напрямую работать с вероятностными значениями, мы работаем с числами, квадрат которых соответствует вероятности получить индекс, соответствующий искомому имени.
Как вообще может пригодиться прочтение случайного индекса? Искусство квантовых вычислений состоит в манипуляции со списком вероятностей, выстраивающей шансы в вашу пользу. В нашем примере это значит придумать способ (что и делает алгоритм Гровера) получить число, связанное с индексом разыскиваемого вами имени, близкое к единице, так, чтобы все остальные числа были близки к нулю. Тогда, прочитывая этот список и получая в ответ индекс, вы с большой вероятностью будете знать, что именно он соответствует тому имени, что вы ищете.
Инструменты квантовых вычислений состоят из операций, которые исследователь может применять к этому списку вероятностей. В математике такой список называется вектором. Часто удобно представлять себе вектор в виде точки в системе координат, или в виде стрелочки, нарисованной от начала координат к этой точке.
Двухкомпонентный вектор можно изобразить в виде стрелочки в двумерном пространстве. Вектор с 1 000 000 компонент живёт в ошеломляющем 1 000 000-мерном пространстве. Операции, проводимые квантовым компьютером, выглядят, как повороты и перевороты этой стрелки. Численно каждая операция обозначается матрицей.
Квантовые вычисления особенно быстры потому, что каждая операция производится с вектором вероятностей целиком, а не проходит его покомпонентно. Гровер обнаружил хитрый способ манипулировать заданным вектором при помощи пары перемежающихся операций, в результате чего получится вектор с нужными нам вероятностями. Важно, что общее количество требуемых операций оказывается гораздо меньше размера списка.
Если вам сложно представить, как это может работать — вы такой не один. Поэтому Адам Браун так радовался, обнаружив способ представлять себе эти абстрактные манипуляции с вектором в терминах более понятной головоломки.
Скрытые связи
Вышло так, что при просмотре моих видео о вычислении числа π при помощи сталкивающихся блоков у Брауна на уме как раз был алгоритм Гровера, поэтому он сразу заметил их связь. «Если целый день провести за размышлениями на тему квантового поиска, то всё начинает казаться квантовым поиском, — сказал Браун, — и так случайно совпало, что данный случай действительно оказался связанным с квантовым поиском».
И если работа Галперина о столкновениях блоков использовала пространство, кодировавшее местоположение каждого блока, то связь с квантовым поиском Гровера начинается с вектора, чьи компоненты х и у кодируют скорость каждого блока. Каждое столкновение блоков переводится в определённую операцию над этим вектором, меняющую его компоненты. К примеру, когда левый блок сталкивается со стеной, изменяя направление на противоположное, это значит, что компонент у нашего вектора умножается на -1, а компонент х остаётся неизменным. С геометрической точки зрения это выглядит как отражение вектора относительно оси х.
Точно так же при столкновении двух блоков изменение их скоростей похоже на ещё один переворот этого вектора, только смещённый относительно центра. При продолжении симуляции левый блок снова столкнётся со стеной, что приведёт к ещё одному развороту по оси х. Очередное столкновение блоков означает ещё один переворот. В итоге, при достаточном количестве столкновений, вектор будет заполнять знакомую кривую: окружность.
Браун заметил, что если правильно описать эту ситуацию, то две этих операции, меняющихся в одну и другую стороны, идентичны двум операциям, которые использовал Гровер в своём квантовом алгоритме поиска.
Чтобы понять, как это происходит, представьте себе большой правый блок в виде множества килограммовых, склеенных вместе. Затем вместо двумерного вектора, описывающего каждую скорость, мы получим N-мерный вектор, где N — общее количество мелких блоков, включая и изолированный блок слева. Каждый из мелких блоков соответствует имени в несортированном списке, а отдельный блок слева — целевому имени.
В своей работе Браун доказал, что тот способ, которым эти столкновения блоков меняют вектор, их описывающий, абсолютно идентичен тому способу, которым алгоритм Гровера меняет квантовый вектор, обозначающий несортированный список имён. Момент в системе сталкивающихся блоков, когда большой блок собирается развернуться, и почти вся энергия системы находится в мелком блоке, соответствует моменту в алгоритме Гровера, когда почти вся вероятность находится в имени, которое вам нужно найти.
То, что при подсчёте столкновений появляется число π, отражено в работе алгоритма Гровера: π/4 √N шагов. Квадратный корень в выражении также отражает, насколько далеко продвигается подсчёт цифр числа π (в степенях 10) после умножения массы большого блока на 10.
«Пока что это просто диковинка, — сказал Браун. — Но в физике мы научились тому, что чем больше способов размышлять о проблеме у нас есть, тем больше идей мы можем подсмотреть — так что, надеюсь, что этот факт когда-нибудь пригодится. У нас есть мало хороших альтернативных способов визуализации алгоритма Гровера.
Эти связи подчёркивают возможности универсального языка математики. Использование векторов для кодирования состояния физической системы работает как на крупных масштабах столкновений блоков, так и на микромасштабах квантовых состояний. Многие фундаментальные идеи в математике, на первый взгляд кажущиеся неприятно оторванными от реальности, оказываются мощными инструментами, поскольку если опустить физические подробности в одной из областей, можно обнаружить её скрытые связи с другой.
