О красивом
(или как красивое оказалось оптимальным)
В 2016 выходит статья, где предлагается несколько симметричных алгоритмов матричного умножения. Авторы прямо в абстракте пишут
А потом в 2025 выходит работа, где тщательно оптимизировали численную устойчивость схем матричного умножения и пришли к той же самой симметричной схеме 2016 года! То есть, так получилось, что сначала скорее из соображений эстетики появившаяся схема, оказалась около оптимальной в плане численной устойчивости)
(или как красивое оказалось оптимальным)
В 2016 выходит статья, где предлагается несколько симметричных алгоритмов матричного умножения. Авторы прямо в абстракте пишут
Хотя эти новые алгоритмы не улучшают известные верхние границы (...), они красивы сами по себе
А потом в 2025 выходит работа, где тщательно оптимизировали численную устойчивость схем матричного умножения и пришли к той же самой симметричной схеме 2016 года! То есть, так получилось, что сначала скорее из соображений эстетики появившаяся схема, оказалась около оптимальной в плане численной устойчивости)
🔥26
О радугах
(наблюдение дисперсии в домашних условиях)
Если взять много небольших капелек (~ мм), то каждая из них будет работать и как линза, и как призма, создавая такой очаровательный ландшафт. Тут из-за влажности вот сконденсировались. Я удивился увидеть симметричные радуги [красный-фиолетовый-красный], по-моему никогда раньше такого не видел)
(наблюдение дисперсии в домашних условиях)
Если взять много небольших капелек (~ мм), то каждая из них будет работать и как линза, и как призма, создавая такой очаровательный ландшафт. Тут из-за влажности вот сконденсировались. Я удивился увидеть симметричные радуги [красный-фиолетовый-красный], по-моему никогда раньше такого не видел)
❤15🔥11
Графики каждый день (почти)
Как вы думаете, чему равна лучшая известная вычислительная сложность умножения двух n-bitных чисел?
Как вы думаете, какая вычислительная сложность у нахождения медианного значения в множестве из n чисел?
// медиана -- число, которое оказалось бы поседередине, после сортировки множества
// медиана -- число, которое оказалось бы поседередине, после сортировки множества
Anonymous Quiz
4%
O(n²)
44%
O(n log n)
42%
O(n)
9%
O(√n)
🔥5❤4
Forwarded from Мишанина
Thermodynamic computing
Сегодня хочу рассказать про статью компании Normal Computing о термодинамических вычислениях. Ребята делают ASIC(Application Specific Integrated Circuit), который может более быстро и энергоэффективно считать примитивы AI моделей. В статье представлен proof-of-concept такого чипа, демонстрируется выигрыш в скорости и энергоэффективности на порядок по сравнению с GPU Nvidia A6000. В будущем обещают улучшение энергоэффективности х1000
Авторы называют свою разработку physics-based ASIC, так как отказываются от цифровой логики в пользу более энергоэффективной и быстрой аналоговой логики. По сути делают классический симулятор: берут физическую систему, запускают её динамику, измеряют состояние, а потом по измеренным состояниям делают инверсию матрицы, считают детерминант или сэмплируют точки из нужного распределения (по сути алгоритм Метрополиса-Гастингса в железе). С точки зрения физики в демонстрационном чипе всё устроено просто: есть набор rlc-контуров(элементарные ячейки) с ёмкостной связью между ними. На rlc-контуры подаются токи i с некоторым шумом(пока от цифрового генератора), и динамика связанной системы контуров описывается системой стохастических дифференциальных уравнений Ланжевена. После установления равновесия можно измерить напряжения v и получить сэмплы из нужного нам нормального распределения.
Контроллируя силу связей(ёмкость конденсаторов), можно задавать матрицу ковариации нормального распределения для сэмплирования или матрицу, от которой хочется посчитать детерминант/обратную матрицу. Есть даже отдельная статья про термодинамическую линейную алгебру. В общем можно считать всё что душе угодно, что можно оценить как статистику от состояний системы
Things to consider
Interesting facts
Сегодня хочу рассказать про статью компании Normal Computing о термодинамических вычислениях. Ребята делают ASIC(Application Specific Integrated Circuit), который может более быстро и энергоэффективно считать примитивы AI моделей. В статье представлен proof-of-concept такого чипа, демонстрируется выигрыш в скорости и энергоэффективности на порядок по сравнению с GPU Nvidia A6000. В будущем обещают улучшение энергоэффективности х1000
Авторы называют свою разработку physics-based ASIC, так как отказываются от цифровой логики в пользу более энергоэффективной и быстрой аналоговой логики. По сути делают классический симулятор: берут физическую систему, запускают её динамику, измеряют состояние, а потом по измеренным состояниям делают инверсию матрицы, считают детерминант или сэмплируют точки из нужного распределения (по сути алгоритм Метрополиса-Гастингса в железе). С точки зрения физики в демонстрационном чипе всё устроено просто: есть набор rlc-контуров(элементарные ячейки) с ёмкостной связью между ними. На rlc-контуры подаются токи i с некоторым шумом(пока от цифрового генератора), и динамика связанной системы контуров описывается системой стохастических дифференциальных уравнений Ланжевена. После установления равновесия можно измерить напряжения v и получить сэмплы из нужного нам нормального распределения.
Контроллируя силу связей(ёмкость конденсаторов), можно задавать матрицу ковариации нормального распределения для сэмплирования или матрицу, от которой хочется посчитать детерминант/обратную матрицу. Есть даже отдельная статья про термодинамическую линейную алгебру. В общем можно считать всё что душе угодно, что можно оценить как статистику от состояний системы
Things to consider
💡 В текущей работе источником случайности является цифровой генератор, но можно подумать про сценарий, в котором случайность появляется за счёт дальнейшей миниатюризации компонент чипа. Например, при уменьшении транзистора увеличивается вероятность туннелирования электронов через gate, а также нагрев, что может делать процесс недетерминированным и ломать цифровую логику. Возможно, этот же эффект получится использовать для масштабирования термодинамических вычислений💡 Авторы отмечают, что использование нелинейности в виде транзистора может существенно расширить множество доступных задач. Например, появится возможность использовать методы оптимизации второго порядка вместо градиентного спуска при той же сложности для тренировки нейросеток❗️ Неидеальность электронных компонент и полносвязность архитектуры ограничивают масштабируемость и точность. Также сложность алгоритмов зависит от необходимой точности решения и времени установления равновесия в системе, которая определяется спектром матрицы связей(числом обусловленности)
Interesting facts
📌
Co-founder/CEO
Faris Sbahi
и chief scientist Normal Computing
Patrick Coles
также занимаются квантовыми вычислениями. У второго, например, есть
обзор по вариационным квантовым алгоритмам
почти на 4к цитирований
📌
Помимо Normal Computing термодинамические вычисления делают
Extropic.
У Lex Fridman есть
подкаст с
основателем Extropic Guillaume Verdon, который тоже кстати из квантовых вычислений пришёл
📌
Из чего-то похожего, но более зрелого есть стартап
Etched.
Они делают ASIC под архитектуру трансформера(T в названии ChatGPT). Утверждают, что один их чип Sohu заменяет 20 видеокарт H100. Разработка ASIC и их интеграция в существующую инфраструктуру обычно очень дорогая, интересно что из этого выйдет. Пока им дали 120М$, что, как будто, не очень много по меркам инвестиций в ИИ. Как я понял, сейчас основное ограничение чипа Etched в memory bandwidth, что делает его хуже карточек от Nvidia (скорость обработки данных у Etched выше, но сами данные подгружаются медленно)
📌
Оказывается, есть целый
журнал
от Nature про unconventional computing
📌
У Normal Computing есть библиотека
thermox
на JAX для моделирования термодинамического компьютера. Также они работают над
AI-решением
для ускорения разработки кастомных чипов
Please open Telegram to view this post
VIEW IN TELEGRAM
🔥17
Графики каждый день (почти)
О том как перемножать матрицы n×n (I. или как метрополисом оптимально по графу на 2⁶⁴ вершин шагал) На компьютере хорошо складывать числа, а не умножать, поэтому если бы умножать матрицы 2х2 можно было бы не за 8 умножений, а за 7, то всё стало бы немного…
This media is not supported in your browser
VIEW IN TELEGRAM
О том как перемножать матрицы III
(canonical polyadic decomposition онлайн, без регистрации)
Выше писал, что умножать матрицы 2х2 можно не за 8 умножений, а за 7. И аналогично для 3х3 есть алгоритм Ладермана, делающий 23 умножения, вместо 27. Два любопытных факта:
1. Не доказано, является ли он оптимальным, сейчас нижняя граница это 19 (link).
2. Поиск алгоритма сводится к декомпозиции 3D тензора
Tᵢⱼₖ = Σ uᵢvⱼwₖ (NP hard),
что аналогично решению системы дискретных уравнений на 621 неизвестную.
И через случайные блуждания по флип графу система решается за секунду, прямо на телефоне! Можете попробовать сами с моей визуализацией: https://qdiag.xyz/cpd/
(canonical polyadic decomposition онлайн, без регистрации)
Выше писал, что умножать матрицы 2х2 можно не за 8 умножений, а за 7. И аналогично для 3х3 есть алгоритм Ладермана, делающий 23 умножения, вместо 27. Два любопытных факта:
1. Не доказано, является ли он оптимальным, сейчас нижняя граница это 19 (link).
2. Поиск алгоритма сводится к декомпозиции 3D тензора
Tᵢⱼₖ = Σ uᵢvⱼwₖ (NP hard),
что аналогично решению системы дискретных уравнений на 621 неизвестную.
И через случайные блуждания по флип графу система решается за секунду, прямо на телефоне! Можете попробовать сами с моей визуализацией: https://qdiag.xyz/cpd/
🔥13👍6❤4
Допустим у вас есть батарейка и охапка транзисторов. Можно ли на транзисторах хранить информацию?
Anonymous Quiz
18%
Нет, нужен какой-нибудь носитель (e.g. магнитная лента)
82%
Да, на транзисторах можно хранить информацию
❤5
Графики каждый день (почти)
Кубик Рубика #math Вы взяли кубик Рубика, достаточно долго его крутили, бесконечно долго, и в какой-то момент решили остановиться. Если верить, что все позиции равновероятны, то получится такое распределение вероятности по расстоянию d до собранного состояния.…
Нашу статью взяли на NeurIPS 2025!
arxiv:2502.13266
Статья "A Machine Learning Approach That Beats Large Rubik's Cubes" про то как находить путь на больших графах в принципе, и про то как with zero human knowledge собирать Кубик Рубика 3x3, 4x4, 5x5, пятнашки до 6x6, ... и другие перестановочные пазлы в частности. Для понимания масштаба: кубик 5x5 это 10⁷⁴ состояний, а мы там находим достаточно короткий (лучший из опубликованных) путь сборки. Код к статье доступен на git cayleypy-cube.
Забавно что для меня это началось с этого поста 2 года назад, а потом списались с @Alexander_V_C (огромное ему спасибо) и как-то так и пошла интернет коллаборация. Собственно про метод писал здесь, и потом ещё подробнее напишу. Красиво, что просто немного случайно блуждая по графу, можно обучить модель очень хорошей эвристике, достаточной для ориентирования на широком классе графов.
Мне очень давно хотелось, чтобы какой-нибудь такой сюжет существующий из любопытства в рамках хобби добрался до рецензий. А тут не просто добрался, но и на A* конференцию, ещё и выдвинули на spotlight (топ 15% от принятых работ).
Воот)
arxiv:2502.13266
Статья "A Machine Learning Approach That Beats Large Rubik's Cubes" про то как находить путь на больших графах в принципе, и про то как with zero human knowledge собирать Кубик Рубика 3x3, 4x4, 5x5, пятнашки до 6x6, ... и другие перестановочные пазлы в частности. Для понимания масштаба: кубик 5x5 это 10⁷⁴ состояний, а мы там находим достаточно короткий (лучший из опубликованных) путь сборки. Код к статье доступен на git cayleypy-cube.
Забавно что для меня это началось с этого поста 2 года назад, а потом списались с @Alexander_V_C (огромное ему спасибо) и как-то так и пошла интернет коллаборация. Собственно про метод писал здесь, и потом ещё подробнее напишу. Красиво, что просто немного случайно блуждая по графу, можно обучить модель очень хорошей эвристике, достаточной для ориентирования на широком классе графов.
Мне очень давно хотелось, чтобы какой-нибудь такой сюжет существующий из любопытства в рамках хобби добрался до рецензий. А тут не просто добрался, но и на A* конференцию, ещё и выдвинули на spotlight (топ 15% от принятых работ).
Воот)
🔥71🎉29❤12
О том как в видеоигры играть
(или от AlphaZero к Dreamer)
Для начала вспоминим как компьютер играет в шахматы используя нейросетку (e.g. AlphaZero или NNUE Stockfish). Можно было бы на основе доски предсказывать куда походить, но это плохая идея — это можно сравнить с gpt до reasoning. Гораздо лучше на основе нейросетки отобрать несколько перспективных ходов, и проверить их — раскрыть дерево решений в их сторону. То есть мы не столько предсказываем по состоянию ход, сколько направляем поиск по дереву решений, и потом на основе этого уже принимаем решение — почти как reasoning в llm. Но чтобы это работало нам нужно уметь по состоянию системы + действию узнавать новое состояние системы, и для шахмат это делается очень просто, вызовом шахматного движка. Но как быть если это minecraft, starcraft, ... — какая-то большая игра, движок которой переписывать для нас не опция, но порассуждать хочется.
И тут помогают world models. Давайте научим другую нейросеть работать вместо движка, пусть она сама по состоянию системы + действию будет предсказывать что случится дальше. Только предсказывать картинку целиком смысла нет, нам не очень интересны в текстуры, графика, ... — куча всего лишнего. Мы лучше обучим третью нейросеть (автоэнкодер), которая будет сжимать-разжимать кадры в скрытое пространство. Получается концентрированная информация о системе в относительно низкоразмерном скрытом пространстве. И так мы получаем архитектуру DeepMind развивающую идеи AlphaZero на видеоигры — Dreamer. Сжали кадр, порассуждали что будет от наших действий исключительно на основе world model (вместо игрового движка), приняли решение — вот и всё)
P.S. Есть несколько идей, как можно было бы сделать потенциально более эффективным в плане требуемых данных и мощностей обучение world model, если вам было бы интересно чем-то таким поработать и есть какой-то опыт с нейросетками или собрать под это дело датасеты — пишите (@ka1242).
P.P.S. У меня работы ребят из google добывающих алмазы в minecraft вызывает исключительно детский восторг, к слову Dreamer v4 вышел буквально пару недель назад)
(или от AlphaZero к Dreamer)
Для начала вспоминим как компьютер играет в шахматы используя нейросетку (e.g. AlphaZero или NNUE Stockfish). Можно было бы на основе доски предсказывать куда походить, но это плохая идея — это можно сравнить с gpt до reasoning. Гораздо лучше на основе нейросетки отобрать несколько перспективных ходов, и проверить их — раскрыть дерево решений в их сторону. То есть мы не столько предсказываем по состоянию ход, сколько направляем поиск по дереву решений, и потом на основе этого уже принимаем решение — почти как reasoning в llm. Но чтобы это работало нам нужно уметь по состоянию системы + действию узнавать новое состояние системы, и для шахмат это делается очень просто, вызовом шахматного движка. Но как быть если это minecraft, starcraft, ... — какая-то большая игра, движок которой переписывать для нас не опция, но порассуждать хочется.
И тут помогают world models. Давайте научим другую нейросеть работать вместо движка, пусть она сама по состоянию системы + действию будет предсказывать что случится дальше. Только предсказывать картинку целиком смысла нет, нам не очень интересны в текстуры, графика, ... — куча всего лишнего. Мы лучше обучим третью нейросеть (автоэнкодер), которая будет сжимать-разжимать кадры в скрытое пространство. Получается концентрированная информация о системе в относительно низкоразмерном скрытом пространстве. И так мы получаем архитектуру DeepMind развивающую идеи AlphaZero на видеоигры — Dreamer. Сжали кадр, порассуждали что будет от наших действий исключительно на основе world model (вместо игрового движка), приняли решение — вот и всё)
P.S. Есть несколько идей, как можно было бы сделать потенциально более эффективным в плане требуемых данных и мощностей обучение world model, если вам было бы интересно чем-то таким поработать и есть какой-то опыт с нейросетками или собрать под это дело датасеты — пишите (@ka1242).
P.P.S. У меня работы ребят из google добывающих алмазы в minecraft вызывает исключительно детский восторг, к слову Dreamer v4 вышел буквально пару недель назад)
Завтра же объявят лауреатов Нобелевской премии по физике! Как думаете, какую область выберут?)
Final Results
23%
Квантовые симуляторы на холодных атомах (Bloch, Cirac, Zoller)
42%
Квантовые вычисления (Shor, Deutsch, DiVincenzo, Loss, Lukin)
15%
Оптические часы на холодных атомах (Katori, Ye)
7%
Twisted bilayer graphene (Jarillo-Herrero, MacDonald)
27%
Метаматериалы (Pendry, Smith)
8%
Астрохимия (Dishoeck)
18%
Космическая инфляция (Guth, Linde)
15%
Другое
🔥5
Графики каждый день (почти)
Завтра же объявят лауреатов Нобелевской премии по физике! Как думаете, какую область выберут?)
Нобелевская премия по физике 2025
(или о некоммутативности фазы и заряда)
И в этом году Нобелевская премия за эксперимент: демонстрация дискретных уровней энергии в current-biased переходе Джозефсона и наблюдение макроскопического туннелирования между ними.
Любопытно, что они именно коллеги, а октябре 1985 в PRL у них вышли совместные работы
Вообще очень интересно открывать эти работы с мыслью "через 40 лет это будет нобелевка".
Из этого появились современные сверхпроводниковые кубиты и подняли точность SQUID-магнитометров (два Джозефсоновских перехода в петле, одно из наиболее ярких коммерческих проявлений квантовых технологий), так что влияние на область действительно заметное)
(или о некоммутативности фазы и заряда)
И в этом году Нобелевская премия за эксперимент: демонстрация дискретных уровней энергии в current-biased переходе Джозефсона и наблюдение макроскопического туннелирования между ними.
Нобелевскую премию по физике 2025 получат Джон Кларк, Мишель Деворе и Джон Мартинису за открытие макроскопического квантово-механического туннелирования и квантования энергии в электрической цепи.
Любопытно, что они именно коллеги, а октябре 1985 в PRL у них вышли совместные работы
Measurements of Macroscopic Quantum Tunneling out of the Zero-Voltage State of a Current-Biased Josephson Junction
Energy-Level Quantization in the Zero-Voltage State of a Current-Biased Josephson Junction
Вообще очень интересно открывать эти работы с мыслью "через 40 лет это будет нобелевка".
Из этого появились современные сверхпроводниковые кубиты и подняли точность SQUID-магнитометров (два Джозефсоновских перехода в петле, одно из наиболее ярких коммерческих проявлений квантовых технологий), так что влияние на область действительно заметное)
🔥20❤9👍2
Когда-то этот канал начинался как обмен графиками однокурсников на физтехе (давно же это было). Интересно как обстоят дела сейчас — сколько здесь физиков/математиков/... . С какой областью/направлением вы себя ассоциируете?
Anonymous Poll
44%
физика
31%
математика
27%
computer science
26%
data science
26%
программирование
8%
биология
4%
химия
11%
другое
Потихоньку готовлюсь к конференции и хотелось сделать какое-нибудь демо. С радостью представляю вниманию .js реализацию описанного алгоритма: прямо у вас в браузере обученная в пределах 5 минут нейросетка найдёт близкий к оптимальному путь на графе в 10¹⁹ вершин за пару секунд — соберёт кубик Рубика 3×3×3 в среднем за 24 действия)
qdiag.xyz
Rubik's Cube Solver
Lightweight AI solving locally in your browser
🔥34❤10
О том как в шахматах ходят
Всем немного знакомым с шахматными правилами предлагаю посмотреть на распределение ходов: по горизонтали отложен номер клетки откуда ходили, а по вертикали отложено куда ходили, данные на основе 1M партий lichess. Чем ярче клеточка, тем чаще делали такой ход. Крупная сетка по сути делит доску на линии: на клетках от 1 до 8 стоят в начале фигуры белых, на клетках от 9 до 16 в начале стоят пешки белых, ... . Можно заметить, что со стороны черных и со стороны белых идёт достаточно симметричная игра.
Что вы тут видите? Какие ходы повторяются из партии в партию? Наиболее характерные выделил красным цветом. Мне очень нравится эта картинка тем, что в начале она выглядит скорее странно, но после пары минут становится до жути очевидной :)
1. Это рокировка O-O белого короля, просто e1-g1!
2. А тут уже лошади прыгают g1-f3, b1-c3
3. Восемь пешек, которые шагают на 1 или на 2 клетки, из партии в партию
Всем немного знакомым с шахматными правилами предлагаю посмотреть на распределение ходов: по горизонтали отложен номер клетки откуда ходили, а по вертикали отложено куда ходили, данные на основе 1M партий lichess. Чем ярче клеточка, тем чаще делали такой ход. Крупная сетка по сути делит доску на линии: на клетках от 1 до 8 стоят в начале фигуры белых, на клетках от 9 до 16 в начале стоят пешки белых, ... . Можно заметить, что со стороны черных и со стороны белых идёт достаточно симметричная игра.
Что вы тут видите? Какие ходы повторяются из партии в партию? Наиболее характерные выделил красным цветом. Мне очень нравится эта картинка тем, что в начале она выглядит скорее странно, но после пары минут становится до жути очевидной :)
2. А тут уже лошади прыгают g1-f3, b1-c3
3. Восемь пешек, которые шагают на 1 или на 2 клетки, из партии в партию
❤25🔥7
Я не нашёл генератор QR code, который бы не требовал от меня регистрации/просмотра рекламы/капчи/... — кошмар, мне просто текст/url в картинку нужно перевести. В общем сделал минималистичный вариант для себя, но вдруг и вам пригодится)
https://qdiag.xyz/qr/
// на телефоне из браузера tg скачивание файла шалит, а вот в chrome всё ок
https://qdiag.xyz/qr/
// на телефоне из браузера tg скачивание файла шалит, а вот в chrome всё ок
qdiag.xyz
QR Code Generator
Lightweight QR code generator
👍26🔥12❤10
О том из чего квантовые компьютеры собираются
(или о плотных подмножествах SU(2ⁿ))
Возьмём n кубитов и зададимся вопросом сделать с ними всё что угодно унитарное — реализовать некоторый квантовый алгоритм U через набор доступных гейтов {Gⱼ} (fig. a). Квантовый алгоритм U — просто унитарная 2ⁿ-мерная матрица, гейт Gⱼ — операция которую мы делаем с поднабором кубитов, тоже сводится к действию унитарной матрицы. То есть мы хотим представить одну матрицу U в виде произведения U=Gⱼ₁ Gⱼ₂ ... Gⱼₘ . Возникает естественный вопрос, а для какого вообще набора {Gⱼ} мы может так сделать?
Оказывается достаточным взять 3 вида матриц (fig. b): две действующие на один кубит (T,H) и одну действующую на два кубита (CNOT, изображается точкой с плюсом). Действуя ими на разные кубиты получается всего n(n-1)+2n доступных матриц {Gⱼ}. И ограничиваясь только такими матрицами, мы можем приблизить сколь угодно точно любую другую унитарную матрицу — то есть они образуют плотное подмножество SU(2ⁿ).
Было бы интересно подумать, а как для минимального m найти такое разложение U=Gⱼ₁ Gⱼ₂ ... Gⱼₘ — очередная, к слову, NP-complete задача.
// говоря про вид комплексных элементов z матрицы U (fig. c) — формула приведена в title, распределение построено для k=1, n_q={-1,0,1} (другие варианты в комментариях), собственно пост возник скорее из желания поделиться этими узорами)
// опечатка: сумма по q от 0, а не от 1
(или о плотных подмножествах SU(2ⁿ))
Возьмём n кубитов и зададимся вопросом сделать с ними всё что угодно унитарное — реализовать некоторый квантовый алгоритм U через набор доступных гейтов {Gⱼ} (fig. a). Квантовый алгоритм U — просто унитарная 2ⁿ-мерная матрица, гейт Gⱼ — операция которую мы делаем с поднабором кубитов, тоже сводится к действию унитарной матрицы. То есть мы хотим представить одну матрицу U в виде произведения U=Gⱼ₁ Gⱼ₂ ... Gⱼₘ . Возникает естественный вопрос, а для какого вообще набора {Gⱼ} мы может так сделать?
Оказывается достаточным взять 3 вида матриц (fig. b): две действующие на один кубит (T,H) и одну действующую на два кубита (CNOT, изображается точкой с плюсом). Действуя ими на разные кубиты получается всего n(n-1)+2n доступных матриц {Gⱼ}. И ограничиваясь только такими матрицами, мы можем приблизить сколь угодно точно любую другую унитарную матрицу — то есть они образуют плотное подмножество SU(2ⁿ).
Было бы интересно подумать, а как для минимального m найти такое разложение U=Gⱼ₁ Gⱼ₂ ... Gⱼₘ — очередная, к слову, NP-complete задача.
// говоря про вид комплексных элементов z матрицы U (fig. c) — формула приведена в title, распределение построено для k=1, n_q={-1,0,1} (другие варианты в комментариях), собственно пост возник скорее из желания поделиться этими узорами)
// опечатка: сумма по q от 0, а не от 1
❤20👍2🔥2🐳1
О том как пятнашки представить в виде группы перестановок
(а точнее S(n²-1) × Cₙ × Cₙ)
Допустим вам захотелось представить пятнашки в виде группы перестановок. Но проблема: что и куда переставлять зависит от положения 0 (пустой клетки). И вообще, для классических пятнашек это сделать не получится. Но если допустить периодические гран условия (да, мы теперь живём на торе), то всё можно.
Для этого рассмотрим следующую конструкцию: для квадрата n×n заполним его n² элементами, 0 в левом верхнем углу (на рисунке это синий квадрат); дальше повторим как на рисунке строки и столбцы этого квадрата до (2n-1)×(2n-1); установим рамку в положение (0,0). Внутренности синего квадрата это как раз будет группа S(n²-1), а положение рамки по x и y это Cₙ × Cₙ.
Теперь если мы хотим поменять местами с 0 (пустышкой) соседний элемент, то: (i) двигаем в эту сторону рамку, (ii) внутри синего квадрата делаем циклические перестановки (внутри столбцов|строк), не трогая 0. Собственно, внутренности рамки это и будет состояние пятнашек, а мы только что описали их набором перестановок!
Давайте для наглядности выпишем генераторы для n=3. Всего будет (n²-1)+(n)+(n) элементов.
и
// кстати, card(S_{n²}) = card(S_{n²-1} × C_n × C_n)
(а точнее S(n²-1) × Cₙ × Cₙ)
Допустим вам захотелось представить пятнашки в виде группы перестановок. Но проблема: что и куда переставлять зависит от положения 0 (пустой клетки). И вообще, для классических пятнашек это сделать не получится. Но если допустить периодические гран условия (да, мы теперь живём на торе), то всё можно.
Для этого рассмотрим следующую конструкцию: для квадрата n×n заполним его n² элементами, 0 в левом верхнем углу (на рисунке это синий квадрат); дальше повторим как на рисунке строки и столбцы этого квадрата до (2n-1)×(2n-1); установим рамку в положение (0,0). Внутренности синего квадрата это как раз будет группа S(n²-1), а положение рамки по x и y это Cₙ × Cₙ.
Теперь если мы хотим поменять местами с 0 (пустышкой) соседний элемент, то: (i) двигаем в эту сторону рамку, (ii) внутри синего квадрата делаем циклические перестановки (внутри столбцов|строк), не трогая 0. Собственно, внутренности рамки это и будет состояние пятнашек, а мы только что описали их набором перестановок!
Давайте для наглядности выпишем генераторы для n=3. Всего будет (n²-1)+(n)+(n) элементов.
state: [1, 2, 3, 4, 5, 6, 7, 8,
0, 2, 1, 0, 2, 1]
right: [2, 1, 4, 5, 3, 7, 8, 6,
8+2, 8+0, 8+1, 11+0, 11+1, 11+2]
down: [4, 5, 6, 7, 8, 3, 1, 2,
8+0, 8+1, 8+2, 11+2, 11+0, 11+1]
и
left, up получаются аналогично как обратные к right, down. Теперь чтобы сделать ход, нам достаточно применить заданную перестановку к набору элементов, независимо от положения пустышки. // кстати, card(S_{n²}) = card(S_{n²-1} × C_n × C_n)
🔥12❤8