Setting Up Your Black Hole Merger Simulation

Ta sama transformacja, zupełnie inna maszyna

Transformata Fouriera Kwantowa (FFK) oblicza dokładnie dyskretną transformatę Fouriera, którą znasz z przetwarzania sygnałów – mapuje wektor N = 2ⁿ amplitud kompleksowych na inny wektor N amplitud związany tym samym jądrem złożonym, jak klasyczna DFT. Zmienia się jedynie to, gdzie te amplitudy się znajdują. Klasyczny FFT przechowuje N liczb w tablicy; FFK działa na N amplitudach zakodowanych implicyjnie w superpozycji tylko n kubitów i robi to przy użyciu obwodu z O(n²) podstawowymi elementami – wielomianem względem liczby kubitów, znacznie mniej niż N log N = n·2ⁿ operacji potrzebnych do dotknięcia każdej amplitudy jawnie.

Definicja

Dla danego stanu bazowego |j⟩, gdzie j mieści się w przedziale od 0 do N-1, QFT generuje określoną superpozycję na każdy stan bazowy |k⟩, ważoną przez fazę zespoloną zależną od iloczynu jk:

QFT |j⟩ = (1/√N) Σ_{k=0}^{N-1} e^(2πi·jk/N) |k⟩ N = 2^n, j i k są liczbami całkowitymi z przedziału 0 .. N-1 Każda amplituda wyjściowa ma RÓWNA wielkość - 1/√N - zmienia się tylko faza. Warto zauważyć, że każda amplituda wyjściowa ma tę samą wielkość - cała informacja przenoszona przez transformację jest pakowana w fazach, a nie prawdopodobieństwach naiwnego pomiaru. Jest to zarówno moc, jak i ograniczenie QFT: odczyt stanu przekształconego bezpośrednim pomiarem rzuca niemal w całości tę informację fazową, co wyjaśnia, dlaczego QFT nigdy nie jest używana jako samodzielne narzędzie "odczyt spektra" - zawsze znajduje się ona na jednym etapie w większego algorytmu, który dalej manipuluje tymi fazami przed dokonaniem jakiegokolwiek pomiaru.

QFT |j⟩  =  (1/√N)  Σ_{k=0}^{N-1}  e^(2πi·jk/N)  |k⟩

N = 2^n,  j and k are n-bit integers 0 .. N-1
every output amplitude has EQUAL magnitude 1/√N - only the phase varies

Budowanie go z Hadamardów i kontrolowanych faz

Obwód realizujący QFT na n kubitach jest ciasnym, powtarzającym się wzorem: dla każdego kubitu zastosuj bramidło Hadamarda, a następnie kaskadę kontrolowanych rotacji fazowych R_k = diag(1, e^(2πi/2^k)), sterowanych przez wszystkie pozostałe kubity, z rotacją kąta halasującą co raz mniejszą w miarę oddalania się kolejnego kubita:

dla kubitu q = 0 .. n-1: zastosuj bramidło H do kubitu q dla każdego kubitu q' po q (odległość d = q'-q): zastosuj kontrolowaną rotację R_{d+1} z kubitu q' na kubit q (dodaje fazę 2π / 2^(d+1) warunkowaną na to, że q' wynosi 1) na koniec: odwróć kolejność kubitów za pomocą bramidła SWAP Każde bramidło Hadamarda umieszcza go w superpozycji; kontrolowane rotacje fazowe następujące po nim korygują fazę tej superpozycji, wykorzystując stan wszystkich pozostałych kubitów, dokładnie kodując rozwinięcie binarne wejściowego j w kaskadowy wzór kątów fazowych. Liczba bramidła: kubit 0 potrzebuje jednego Hadamarda i n-1 rotacji kontrolowanych, kubit 1 potrzebuje jednego Hadamarda i n-2 rotacji kontrolowanych, i tak dalej aż do ostatniego kubitu, który potrzebuje tylko jednego Hadamarda - suma trójkątna która wynosi O(n²) bramidła, plus ⌊n/2⌋ operacji wymiany na końcu, aby przywrócić kubity w standardowej kolejności.

for qubit q = 0 .. n-1:
    apply H to qubit q
    for each qubit q' after q (distance d = q'-q):
        apply controlled-R_{d+1} from qubit q' onto qubit q
            (adds a phase of 2π / 2^(d+1) conditioned on q' being 1)
finally: reverse the qubit order with SWAP gates

Skąd bierze się prędkość i gdzie się zatrzymuje

Wygląda na darmowe śniadanie, ale ogromna dysproporcja między O(n²) a O(n·2ⁿ) wynika z dwóch warunków, które przywracają równowagę dla typowych zastosowań. Po pierwsze, potrzebujesz już załadowanych do stanu kwantowego amplitud N wejścia - jeśli musisz zakodować N klasycznych liczb qubit po qubitie, sam ten proces ładowania kosztuje O(N), niszcząc przewagę zanim nawet uruchomi się QFT. Druga i bardziej subtelna sprawa to brak możliwości odczytania N amplitud wyjściowych – pomiar powoduje kolaps superpozycji do jednego wyniku, próbkowanego z prawdopodobieństwem równym kwadratowi amplitudy tego wyniku. QFT jest zatem korzystny tylko wtedy, gdy problem jest tak skonstruowany, aby pojedynczy lub kilka pomiarów stanu po transformacji ujawniły dokładnie potrzebną odpowiedź – zwykle okresowość lub własną fazę – bez potrzeby odczytania całego spektrum do pamięci klasycznej.

Wewnątrz algorytmu Shora i oszacowania fazy

Typowym przykładem jest algorytm rozkładu na czynniki Shora. Trudnym krokiem jest znajdowanie okresu r funkcji wykładniczej modularnej a^x mod N; rejestr kwantowy jest ładowany superpozycją wyników tej funkcji dla każdego x, a następnie stosuje się QFT do rejestru wykładniczego. Ponieważ wzór amplitudy stanu powtarza się z okresem r, QFT koncentruje prawdopodobieństwo wynikowe na wartościach bliskich wielokrotnościom rozmiaru rejestru podzielonym przez r – zmierz raz, a następnie uruchom algorytm ciągłego ułamka o stałej wartości na wyniku i okres r z wysoką prawdopodobieństwem znika. Ten sam mechanizm, ogólny, nazywany jest oszacowaniem fazy kwantowej: danej operatorem jednostkowym i jednym ze swoich stanów własnych, oszacowanie fazy wykorzystuje QFT do odczytania odpowiadającej fazy stanu o dokładności n bitów, a leży u podstaw nie tylko algorytmu Shora, ale także symulacji chemii kwantowej i wielu innych algorytmów liniowych kwantowych.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Quantum Fourier Transform i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.