Введение

Инволютивное изменение базиса в линейной алгебре

Преобразование Адамара (также известное как преобразование Уолша — Адамара, преобразование Адамара — Радемахера — Уолша, преобразование Уолша или преобразование Уолша — Фурье) является примером обобщенного класса преобразований Фурье. Оно выполняет ортогональную, симметричную, инволюционную, линейную операцию над 2^(m) действительными числами (или комплексными, или гиперкомплексными числами, хотя сами матрицы Адамара являются чисто вещественными). Преобразование Адамара можно рассматривать как построенное из дискретных преобразований Фурье (ДПФ) размера 2 и, фактически, эквивалентно многомерному ДПФ размера 2 × 2 × ⋯ × 2 × 2. Другой подход — рассматривать преобразование Адамара как преобразование Фурье на булевой группе. Используя преобразование Фурье на конечных (абелевых) группах, преобразование Фурье функции — это функция , определяемая как

где — символ каждой группы, где умножение — булевое скалярное произведение на битовых строках, поэтому мы можем отождествить вход в с (двойственность Понтрягина) и определить как

Это преобразование Адамара , рассматривая вход в и как булевы строки. В терминах вышеуказанной формулировки, где преобразование Адамара умножает слева вектор из комплексных чисел на матрицу Адамара , эквивалентность видна, если принять, что принимает в качестве входных данных битовую строку, соответствующую индексу элемента , и выдает соответствующий элемент . Сравните это с обычным дискретным преобразованием Фурье, которое при применении к вектору из комплексных чисел вместо этого использует символы циклической группы .

Комплексность вычислений

В классической области преобразование Адамара можно вычислить за операций, используя алгоритм быстрого преобразования Адамара. В квантовой области преобразование Адамара можно вычислить за время, поскольку это квантовый логический вентиль, который можно распараллелить.

Приложения квантовых вычислений

Трансформация Адамара широко используется в квантовых вычислениях. Двумерная (2 × 2) трансформация Адамара является квантовым логическим элементом, известным как вентиль Адамара, и применение вентиля Адамара к каждому кубиту n-кубитного регистра параллельно эквивалентно трансформации Адамара.

Хадамардские ворота

В квантовых вычислениях, ворота Адамара — это вращение на один кубит, которое отображает базисные состояния кубита |0⟩ и |1⟩ в два состояния суперпозиции с равными весами базисных состояний |0⟩ и |1⟩. Обычно фазы выбираются так, чтобы

в нотации Дирака. Это соответствует матрице преобразования

в базисе |0⟩ и |1⟩, также известном как вычислительный базис. Состояния |0⟩ и |1⟩ известны как |+⟩ и |−⟩ соответственно, и вместе они образуют полярный базис в квантовых вычислениях.

Операции в воротах Хадамарда

Одно применение шлюза Адамара к кубиту, находящемуся в состоянии 0 или 1, приведет к квантовому состоянию, которое при измерении даст 0 или 1 с равной вероятностью (как видно из первых двух операций). Это аналогично подбрасыванию честной монеты в стандартной вероятностной модели вычислений. Однако, если шлюз Адамара применить дважды подряд (что эффективно происходит в последних двух операциях), то конечное состояние всегда будет совпадать с начальным.

Другие применения

Трансформация Адамара также используется в шифровании данных, а также во многих алгоритмах обработки сигналов и сжатия данных, таких как JPEG XR и MPEG 4 AVC. В приложениях сжатия видео она обычно используется в форме суммы абсолютных значений преобразованных разностей. Она также является ключевой частью значительного числа алгоритмов в квантовых вычислениях. Трансформация Адамара также применяется в экспериментальных методах, таких как ЯМР, масс-спектрометрия и кристаллография. Кроме того, она используется в некоторых версиях локально-чувствительного хеширования для получения псевдослучайных матричных вращений.