Pour la Science № 563 - квантовые компьютеры
Большое досье про квантовые компьютеры. Пересказывать несерьёзно, но некоторые побочные моменты мне хочется отметить.
Интересный аргумент к вопросу о детерминизме (в контексте досье это было о квантовых компьютерах, но я тут же подумал и о разговорах о свободе воли): не важно даже, есть ли детерминизм в квантовых системах. Даже если он есть, мы не знаем с абсолютной точностью действующих физических законов. А следовательно мы не можем «взять первоначальные условия и просчитать будущее». Ну так и какая нам разница, по какой именно причине мы не можем просчитать будущее? Чем это концептуально отличается от недетрминизма?
Статья о задаче моделирования N квантовых тел - пример конкретной нужной задачи, в которой с одной стороны превосходство квантового компьютера очевидно, но при этом появляются какие-то алгоритмы для нормальных компьютеров, позволяющие и им делать какие-то вычисления. Если моделировать в лоб, то сложность волновой функции растёт экспоненциально N. Обычные компьютеры исторически справлялись с тривиальными конфигурациями (водород в вакууме - практически сферический конь), для интересных случаев долгое время надежда была только на квантовые компьютеры. Потом для 1-мерного варианта нашли решение (density matrix renormalization group). А потом нашли красивый хак (matrix product states): вместо того, чтобы описывать систему N-мерной матрицей (для тел с d возможными состояниями это d^N параметров), попробуем представить её в виде произведения N матриц меньшей размерности. И этот хак позволяет получать решения буквально на обычном компьютере.
Дальше авторы рассуждают о том, как именно можно было бы применить этот хак к системам большей размерности, а я вспомнил, как убил несколько недель на ровно этот же хак на работе. У нас самая ресурсоёмкая часть расчётов оперирует матрицей K*S, где K - количество клиентов в портфеле, а S - количество моделируемых сценариев. Очевидно, что подавляющее большинство операция одномерно либо по первому измерению (например, финансовые показатели не зависят от личности клиента: если мы заработали 3%, значит мы дали всем по 3%), либо по второму (например, показатели смертности - вероятность умереть зависит только от возраста, а он для каждого человека одинаков во всех наших сценариях). К сожалению, я наткнулся на операцию, которую я не смог выразить как последовательность одномерных операций (достаточно техническая вещь: распределение некоей суммы, которая зависит от сценария, но распределяется в зависимости от характеристик клиентов). А переводить на одномерные операторы только часть расчётов приводило к ужасной сложности кода - и я забил.
В статье при этом рассматривают ещё одну интересную мысль: работать не с общим случаем, а пытаться понять, какие упрощения оставляют нам все более-менее интересные варианты. Красивая иллюстрация: архиватор в общем случае не работает (Дирихле не даст соврать), но на практике все реальные файлы сжимаются. Тот же jpeg - все интересные человеку фотографии прекрасно компрессируются, и всем плевать, что в общем случае (белый шум) алгоритм никакого выигрыша не даёт. Точно так же и с системой N квантовых тел, если мы, например, работаем с их запутанностью. В общем случае да, каждая частица может быть запутана с любой из оставшихся. Но на практике нас интересуют только системы, где запутанность связывает частицы, находящиеся относительно недалеко друг от друга. И в этой формулировке вроде как получилось посчитать какие-то 2D конфигурации. Это тоже очень полезная мысль, надо постараться держать её в голове в следующий раз, когда я примусь решать на работе задачу «в общем виде». Привычка есть, и вообще сложно оставлять в голове возможность того, что мой алгоритм не работает в общем виде (последний пример: пост про Advent of Code 2022, где я возмущаюсь человеком, схалявившим в решении 16-й задачи, в то время как я искал общее решение - но у него при этом получился ответ, а у меня-то нат).
В этой же статье упоминают «нотацию Пенроуза» - английская Википедия рассказывает какие-то ужасы, в русской Википедии вообще тишина. Нашёл описание на другом сайте. Очень удобное графическое изображение операция с многомерными матрицами. Надо будет обязательно принести эту нотацию на работу!
Интересный аргумент к вопросу о детерминизме (в контексте досье это было о квантовых компьютерах, но я тут же подумал и о разговорах о свободе воли): не важно даже, есть ли детерминизм в квантовых системах. Даже если он есть, мы не знаем с абсолютной точностью действующих физических законов. А следовательно мы не можем «взять первоначальные условия и просчитать будущее». Ну так и какая нам разница, по какой именно причине мы не можем просчитать будущее? Чем это концептуально отличается от недетрминизма?
Статья о задаче моделирования N квантовых тел - пример конкретной нужной задачи, в которой с одной стороны превосходство квантового компьютера очевидно, но при этом появляются какие-то алгоритмы для нормальных компьютеров, позволяющие и им делать какие-то вычисления. Если моделировать в лоб, то сложность волновой функции растёт экспоненциально N. Обычные компьютеры исторически справлялись с тривиальными конфигурациями (водород в вакууме - практически сферический конь), для интересных случаев долгое время надежда была только на квантовые компьютеры. Потом для 1-мерного варианта нашли решение (density matrix renormalization group). А потом нашли красивый хак (matrix product states): вместо того, чтобы описывать систему N-мерной матрицей (для тел с d возможными состояниями это d^N параметров), попробуем представить её в виде произведения N матриц меньшей размерности. И этот хак позволяет получать решения буквально на обычном компьютере.
Дальше авторы рассуждают о том, как именно можно было бы применить этот хак к системам большей размерности, а я вспомнил, как убил несколько недель на ровно этот же хак на работе. У нас самая ресурсоёмкая часть расчётов оперирует матрицей K*S, где K - количество клиентов в портфеле, а S - количество моделируемых сценариев. Очевидно, что подавляющее большинство операция одномерно либо по первому измерению (например, финансовые показатели не зависят от личности клиента: если мы заработали 3%, значит мы дали всем по 3%), либо по второму (например, показатели смертности - вероятность умереть зависит только от возраста, а он для каждого человека одинаков во всех наших сценариях). К сожалению, я наткнулся на операцию, которую я не смог выразить как последовательность одномерных операций (достаточно техническая вещь: распределение некоей суммы, которая зависит от сценария, но распределяется в зависимости от характеристик клиентов). А переводить на одномерные операторы только часть расчётов приводило к ужасной сложности кода - и я забил.
В статье при этом рассматривают ещё одну интересную мысль: работать не с общим случаем, а пытаться понять, какие упрощения оставляют нам все более-менее интересные варианты. Красивая иллюстрация: архиватор в общем случае не работает (Дирихле не даст соврать), но на практике все реальные файлы сжимаются. Тот же jpeg - все интересные человеку фотографии прекрасно компрессируются, и всем плевать, что в общем случае (белый шум) алгоритм никакого выигрыша не даёт. Точно так же и с системой N квантовых тел, если мы, например, работаем с их запутанностью. В общем случае да, каждая частица может быть запутана с любой из оставшихся. Но на практике нас интересуют только системы, где запутанность связывает частицы, находящиеся относительно недалеко друг от друга. И в этой формулировке вроде как получилось посчитать какие-то 2D конфигурации. Это тоже очень полезная мысль, надо постараться держать её в голове в следующий раз, когда я примусь решать на работе задачу «в общем виде». Привычка есть, и вообще сложно оставлять в голове возможность того, что мой алгоритм не работает в общем виде (последний пример: пост про Advent of Code 2022, где я возмущаюсь человеком, схалявившим в решении 16-й задачи, в то время как я искал общее решение - но у него при этом получился ответ, а у меня-то нат).
В этой же статье упоминают «нотацию Пенроуза» - английская Википедия рассказывает какие-то ужасы, в русской Википедии вообще тишина. Нашёл описание на другом сайте. Очень удобное графическое изображение операция с многомерными матрицами. Надо будет обязательно принести эту нотацию на работу!