- 21,755
- 46
- 8 Ноя 2022
Задачи, на которые раньше уходили годы, теперь решаются за считанные минуты.
Квантовые вычисления , как и классические компьютеры середины прошлого века, переживают этап становления. Аппаратная часть уже достаточно развита, чтобы решать ограниченный круг задач, но истинный прогресс возможен только при появлении новых алгоритмов.
Как раз над этим плотно работают теоретики IBM Research, которым удалось разработать метод , демонстрирующий заметное ускорение по сравнению с лучшими классическими подходами. Основой для прорыва стала связь между квантовой физикой и математикой, а именно — использование теории групп и обобщённого преобразования Фурье.
Исследователи обращают внимание, что природа подчиняется определённым законам симметрии. Эти симметрии описываются в математике с помощью групп, а их представления позволяют анализировать поведение частиц и систем. Для квантовых вычислений это особенно важно, поскольку симметрии помогают находить скрытые закономерности и использовать их для оптимизации вычислений. Команда IBM построила алгоритм, который применяет представления симметрической группы — набора всех перестановок элементов, аналогичных перестановке карт в колоде.
Традиционно такие структуры описываются матрицами, каждая из которых отражает конкретное преобразование системы. Некоторые из этих представлений можно разложить на более простые, называемые неприводимыми. Взаимодействие между ними определяется так называемыми коэффициентами Кронекера, вычисление которых на обычных компьютерах чрезвычайно трудоёмко. Именно здесь квантовые системы могут проявить преимущество.
Авторы новой работы показали, что оценка этих коэффициентов относится к особому классу задач QXC — «квантовому приближённому счёту». Это разновидность проблем, где квантовые методы позволяют быстрее оценивать количество решений, чем классические алгоритмы.
Чтобы построить эффективный метод, физики обратились к старому инструменту — квантовому преобразованию Фурье, лежащему в основе алгоритма Шора и метода фазовой оценки. Но в отличие от стандартных «абелевых» случаев, где порядок операций несущественен, новая схема работает с некоммутативными структурами, то есть с системами, где перестановка элементов меняет результат.
Так появилась реализация обобщённого квантового преобразования Фурье для симметрической группы, способная вычислять коэффициенты Кронекера с существенно меньшими затратами. По оценке разработчиков, предложенный алгоритм обеспечивает сверхполиномиальное ускорение по сравнению с лучшими классическими решениями.
Даже после того, как математик Грета Панова из Университета Южной Калифорнии уточнила анализ и показала, что ускорение имеет полиномиальный характер, разница в эффективности всё равно оказалась впечатляющей: при параметре k=3 квантовый метод требует порядка n¹⁰ операций против n³⁷ у классического.
Результат вызвал интерес не только у специалистов по вычислительной физике, но и у теоретических математиков. Работа открывает путь к пересмотру старых задач алгебраической комбинаторики , связанных с таблицами Юнга и структурой симметрических групп.
Возможность использовать квантовые подходы для анализа таких систем создаёт редкий мост между чистой математикой и физикой, а также может стать основой для будущих алгоритмов, выходящих за рамки существующих представлений о вычислениях.
Квантовые вычисления , как и классические компьютеры середины прошлого века, переживают этап становления. Аппаратная часть уже достаточно развита, чтобы решать ограниченный круг задач, но истинный прогресс возможен только при появлении новых алгоритмов.
Как раз над этим плотно работают теоретики IBM Research, которым удалось разработать метод , демонстрирующий заметное ускорение по сравнению с лучшими классическими подходами. Основой для прорыва стала связь между квантовой физикой и математикой, а именно — использование теории групп и обобщённого преобразования Фурье.
Исследователи обращают внимание, что природа подчиняется определённым законам симметрии. Эти симметрии описываются в математике с помощью групп, а их представления позволяют анализировать поведение частиц и систем. Для квантовых вычислений это особенно важно, поскольку симметрии помогают находить скрытые закономерности и использовать их для оптимизации вычислений. Команда IBM построила алгоритм, который применяет представления симметрической группы — набора всех перестановок элементов, аналогичных перестановке карт в колоде.
Традиционно такие структуры описываются матрицами, каждая из которых отражает конкретное преобразование системы. Некоторые из этих представлений можно разложить на более простые, называемые неприводимыми. Взаимодействие между ними определяется так называемыми коэффициентами Кронекера, вычисление которых на обычных компьютерах чрезвычайно трудоёмко. Именно здесь квантовые системы могут проявить преимущество.
Авторы новой работы показали, что оценка этих коэффициентов относится к особому классу задач QXC — «квантовому приближённому счёту». Это разновидность проблем, где квантовые методы позволяют быстрее оценивать количество решений, чем классические алгоритмы.
Чтобы построить эффективный метод, физики обратились к старому инструменту — квантовому преобразованию Фурье, лежащему в основе алгоритма Шора и метода фазовой оценки. Но в отличие от стандартных «абелевых» случаев, где порядок операций несущественен, новая схема работает с некоммутативными структурами, то есть с системами, где перестановка элементов меняет результат.
Так появилась реализация обобщённого квантового преобразования Фурье для симметрической группы, способная вычислять коэффициенты Кронекера с существенно меньшими затратами. По оценке разработчиков, предложенный алгоритм обеспечивает сверхполиномиальное ускорение по сравнению с лучшими классическими решениями.
Даже после того, как математик Грета Панова из Университета Южной Калифорнии уточнила анализ и показала, что ускорение имеет полиномиальный характер, разница в эффективности всё равно оказалась впечатляющей: при параметре k=3 квантовый метод требует порядка n¹⁰ операций против n³⁷ у классического.
Результат вызвал интерес не только у специалистов по вычислительной физике, но и у теоретических математиков. Работа открывает путь к пересмотру старых задач алгебраической комбинаторики , связанных с таблицами Юнга и структурой симметрических групп.
Возможность использовать квантовые подходы для анализа таких систем создаёт редкий мост между чистой математикой и физикой, а также может стать основой для будущих алгоритмов, выходящих за рамки существующих представлений о вычислениях.
- Источник новости
- www.securitylab.ru
