Кіріспе
Сызықтық алгебрадағы негізді инволютивті өзгерту
Хадамард түрлендіруі (сонымен қатар Уолш-Хадамард түрлендіруі, Хадамард-Радемахер-Уолш түрлендіруі, Уолш түрлендіруі немесе Уолш-Фурье түрлендіруі деп те аталады) – Фурье түрлендірулерінің жалпыланған класының мысалы. Ол 2^(m) нақты санға (немесе кешенді, немесе гиперкешенді сандарға) ортогональды, симметриялық, инволютивті, сызықтық операция жасайды, бірақ Хадамард матрицаларының өзі таза нақты сандар болып табылады. Хадамард түрлендіруін 2-өлшемді дискретті Фурье түрлендірулерінен (DFT) құралған деп қарастыруға болады, және ол шын мәнінде 2 × 2 × ⋯ × 2 × 2 өлшемі бар көпөлшемді DFT-ге тең. Тағы бір тәсіл – Хадамард түрлендіруін Буль тобындағы Фурье түрлендірмесі ретінде қарау. Фурье түрлендіруін шекті (абельдік) топтарда қолдану арқылы, функцияның Фурье түрлендірмесі мына функциямен анықталады:
мұндағы – топтың кейіптемесі. Әр кейіптеме мына түрде болады: , мұндағы көбейту – биттік тізбектердегі бульдік көбейту, сондықтан кіріс дерегін -мен (Понтрягин дуалдығы) сәйкестендіре аламыз және мына арқылы анықтай аламыз:
Бұл – және кіріс деректері биттік тізбектер ретінде қарастырылғандағы Хадамард түрлендіруі. Жоғарыдағы формула бойынша, Хадамард түрлендіруі кешенді сандар векторын сол жағынан Хадамард матрицасымен көбейтуге тең, эквиваленттілік -нің элементінің индексіне сәйкес келетін биттік тізбекті кіріс ретінде алып, -нің сәйкес элементін шығыс ретінде алу арқылы көрінеді. Мұны әдеттегі дискретті Фурье түрлендіруімен салыстырыңыз, ол кешенді сандар векторына қолданылғанда циклдік топтың кейіптемелерін пайдаланады.
Compare this to the usual discrete Fourier transform which when applied to a vector of complex numbers instead uses characters of the cyclic group .
Есептеу күрделілігі
Классикалық доменде Хадамард түрлендіруі жылдам Хадамард түрлендіру алгоритмін қолдана отырып операциялар арқылы есептелуі мүмкін. Кванттық доменде Хадамард түрлендіруі уақыт ішінде есептелуі мүмкін, себебі ол параллельдеуге болатын кванттық логикалық қақпа.
Кванттық есептеудің қолданбалары
Хадамард трансформациясы кванттық есептеулерде кеңінен қолданылады. 2 × 2 Хадамард трансформациясы – Хадамард қақпасы деп аталатын кванттық логикалық қақпа, ал n кубиттік тізілімнің әрбір кубитіне Хадамард қақпасын параллель түрде қолдану Хадамард трансформациясына баламалы болады.
Хадамар қақпасы
Кванттық есептеуде Хадамард қақпасы – бір кубитты бұру, кубит негіздік күйлерін |0⟩ және |1⟩ екі суперпозициялық күйге тең салмақпен |+⟩ және |-⟩ есептеу негіздік күйлеріне бейімдейді. Әдетте фазалар Дирак нотациясы бойынша былай таңдалады:
in Dirac notation. This corresponds to the transformation matrix
in the basis, also known as the computational basis. The states and are known as and respectively, and together constitute the polar basis in quantum computing.
|0⟩ → (|0⟩ + |1⟩)/√2
|1⟩ → (|0⟩ - |1⟩)/√2
in Dirac notation. This corresponds to the transformation matrix
in the basis, also known as the computational basis. The states and are known as and respectively, and together constitute the polar basis in quantum computing.
Бұл есептеу негізінде де белгілі, мына трансформация матрицасына сәйкес келеді:
in Dirac notation. This corresponds to the transformation matrix
in the basis, also known as the computational basis. The states and are known as and respectively, and together constitute the polar basis in quantum computing.
```
1/√2 1/√2
1/√2 -1/√2
```
in Dirac notation. This corresponds to the transformation matrix
in the basis, also known as the computational basis. The states and are known as and respectively, and together constitute the polar basis in quantum computing.
|0⟩ және |1⟩ күйлері сәйкесінше |+⟩ және |-⟩ деп аталады, және олар кванттық есептеудегі полярлық негізді құрайды.
in Dirac notation. This corresponds to the transformation matrix
in the basis, also known as the computational basis. The states and are known as and respectively, and together constitute the polar basis in quantum computing.
Хадамард қақпасының операциялары
Хадамард қақпасының 0 немесе 1 кубитқа бір рет қолданылуы кванттық күйді тудырады, оны өлшегенде 0 немесе 1 бірдей ықтималдықпен алынады (алғашқы екі операцияда көрсетілгендей). Бұл стандартты ықтималдық есептеу моделінде әділ монетаны лақтырумен бірдей. Дегенмен, егер Хадамард қақпасы қатарынан екі рет қолданылса (соңғы екі операцияда іс жүзінде осылай жасалған), соңғы күй бастапқы күймен толық сәйкес келеді.
Басқа қолданбалар
Хадамард трансформациясы деректерді шифрлауда, сондай-ақ көптеген сигнал өңдеу және деректерді сығыстыру алгоритмдерінде, мысалы JPEG XR және MPEG 4 AVC қолданылады. Видеосығыстыру қолданыстарында, ол әдетте абсолютті түрлендірілген айырмашылықтардың қосындысы түрінде қолданылады. Бұл сондай-ақ кванттық есептеудегі көптеген алгоритмдердің маңызды құрамы болып табылады. Хадамард трансформациясы НМР, массалық спектрометрия және кристаллография сияқты тәжірибелік әдістерде де қолданылады. Одан әрі, ол псевдо кездейсоқ матрицалық айналымдар алу үшін жергілікті сезімтал хэштеудің кейбір түрлерінде пайдаланылады.