Deutsch-Jozsa: Jedna Kwestia Kwantowa Przewyższa Każdy Klasyczny Wniosek

Obietnica problemu skonstruowana do interferencji kwantowej

David Deutsch i Richard Jozsa w swoim algorytmie z 1992 roku rozwiązują celowo wąskie zagadnienie: zostajesz wyposażony w skrzyneczkę, która jest funkcją f mapującą n bitów na pojedynczy bit, wraz z obietnicą, że f jest albo stała (identyczny wynik dla każdego możliwego wejścia) lub zbalansowana (wyjście 0 dla dokładnie połowy 2ⁿ wejść i 1 dla pozostałych). Twoim zadaniem jest stwierdzenie, która z nich, używając orakulum jak najmniej razy.

Klasycznie, jeśli wymagasz odpowiedzi pewnej, a nie tylko prawdopodobnej, nie ma skrótu: przeciwnik może f zmusić Cię do zapytania aż do 2ⁿ⁻¹ + 1 wejść, zanim będziesz mógł wykluczyć obie możliwości, ponieważ ciąg identycznych wyników jest zgodny z "stałą", dopóki nie zobaczysz więcej niż połowy domeny.

Odskok fazowy: kodowanie f(x) bez interakcji z qubitem pomocniczym

Kluczem do osiągnięcia wystarczającej liczby zapytań jest odskok fazowy. Oracle jest implementowany w sposób odwracalny jako U_f: |x⟩|y⟩ → |x⟩|y ⊕ f(x)⟩. Qubit pomocniczy jest przygotowywany nie w stanie |0⟩, lecz w superpozycji |-⟩ = (|0⟩ - |1⟩)/√2. Zastosowanie U_f do |x⟩|-⟩ powoduje, że qubit pomocniczy pozostaje w stanie |-⟩ bez zmian, a jednocześnie mnoży cały termin przez (-1)^f(x):

U_f |x⟩ (|0⟩-|1⟩)/√2 = (-1)^f(x) |x⟩ (|0⟩-|1⟩)/√2 jeśli n qubitów wejściowych znajduje się w superpozycji nad wszystkimi x, to jeden wywołany oracle zapisuje (-1)^f(x) jako fazę na każdym gałęzi tej superpozycji jednocześnie. Ponieważ rejestr wejściowy jest wprowadzony do równowartościowej superpozycji wszystkich 2ⁿ wartości przed wywołaniem oracle'a – poprzez zastosowanie bramy Hadamarda do każdego z n qubitów, która przekształca |0⟩^⊗n w (1/√2ⁿ) Σₓ |x⟩ – to jedno wywołanie odskoku fazowego skutecznie oblicza f dla każdego wejścia jednocześnie. Informacja nie pojawia się jako czytelna ciąg bitów; pojawia się zakodowana jako wzorzec faz na rozległej superpozycji o wykładniczej wielkości.

U_f |x⟩ (|0⟩-|1⟩)/√2  =  (-1)^f(x) |x⟩ (|0⟩-|1⟩)/√2

if the n input qubits hold a SUPERPOSITION over every x,
the single oracle call writes (-1)^f(x) as a phase onto
every branch of that superposition simultaneously.

Algorytm jeden zapytanie

1. Przygotuj n kubitów wejściowych w stanie |0⟩⊗n oraz jeden ancilla w stanie |-⟩. 2. Zastosuj H do wszystkich n+1 kubitów → wejście: równoważna superpozycja ancilla: |-⟩ 3. Zastosuj orakl U_f raz → przesunięcie fazowe: (-1)^f(x) na każdej gałęzi. 4. Zastosuj ponownie H do n kubitów wejściowych (transformacja Walsh-Hadamarda). 5. Zmierz n kubity wejściowe wszystkie zera → f jest STAŁE dowolny bit 1 → f jest WYKWALIFIKOWANE Krok 4 stanowi drugą połowę triku. Pojedyncze zastosowanie H zamienia |0⟩ w superpozycję; warstwa n Hadamardów na stanie, który już zawiera wzorzec faz, wykonuje transformację Walsh-Hadamarda - interferuje te 2ⁿ amplitudami fazowymi i gdzie interferencja ląduje zależy całkowicie od wzoru fazowego wpisanego przez orakl.

1. prepare n input qubits in |0⟩^⊗n, one ancilla in |1⟩
2. apply H to all n+1 qubits          → input: equal superposition
                                          ancilla: |-⟩
3. apply the oracle U_f once          → phase kickback: (-1)^f(x) per branch
4. apply H to the n input qubits again  (Walsh-Hadamard transform)
5. measure the n input qubits
     all zeros  → f is CONSTANT
     any 1 bit  → f is BALANCED

Dlaczego amplitudy ulegają skurczeniu do zer lub nigdy nie występują

Amplituda pomiaru ciągu wszystkich zer daje czysty sumowanie dla każdego wejścia:

amplituda(|00...0⟩) = (1/2ⁿ) Σₓ (-1)^f(x) f stała → każdy wyraz ma ten sam znak → suma = ±2ⁿ → prawdopodobieństwo 1 f zrównoważony → dokładnie połowa wyrazów to +1, a druga połowa -1 → suma = 0 → prawdopodobieństwo 0 Jeśli f jest stałe, każdy z 2ⁿ wyrazów w tej sumie ma ten sam znak, więc dodają się konstruktywnie i wynik wszystkich zer jest pewny. Jeśli f jest zrównoważony, dokładnie połowa wyrazów to +1, a druga połowa -1, co dokładnie je anuluje, a prawdopodobieństwo wyniku wszystkich zer wynosi dokładnie zero – pomiar gwarantuje zwrócenie czegoś innego niż wszystkie zera. Nie ma przypadkowego pośredniego przypadku, co wyjaśnia, dlaczego pojedynczy pomiar daje jednoznaczna i bezbłędną odpowiedź zamiast wskazówki statystycznej.

amplitude(|00...0⟩) = (1/2ⁿ) Σₓ (-1)^f(x)

f constant  → every term has the same sign → sum = ±2ⁿ → probability 1
f balanced  → exactly half the terms are +1, half -1 → sum = 0 → probability 0

Co oznacza przyspieszenie

Ważne jest, aby precyzyjnie określić, co dowodzi algorytm Deutsch-Jozsa. Jego wykładnicza przewaga dotyczy deterministycznego, dokładnego algorytmu klasycznego, który w najgorszym przypadku musi zadawać pytania. Algorytm klasyczny, który może być losowy i prawidłowo odpowiadać z wysoką prawdopodobieństwem, może rozwiązać ten sam problem obietnicy przy użyciu niewielkiej liczby pytań – wybrać małą liczbę losowych wejść i jeśli kiedykolwiek zobaczymy dwa różne wyniki, natychmiast wiemy, że f jest zrównoważone, a biegły wynik identycznych wyników sprawia, że „stałe” staje się niezwykle prawdopodobne już po kilku sprawdzeniach. Dlatego Deutsch-Jozsa nie dowodzi, że komputery kwantowe wygrywają z najlepszej klasycznej strategii dla tego konkretnego zadania; jego prawdziwe znaczenie jest historyczne i pedagogiczne. Był to pierwszy algorytm, który rygorystycznie wykazał, że złożoność pytań komputera kwantowego w przypadku dokładnej odpowiedzi może być wykładniczo mniejsza niż złożoność pytań komputera klasycznego, a narzędzia takie jak phase-kickback i Walsh-Hadamard stały się zestawem narzędzi, z którego później, niezaprzeczalne przyspieszenia – algorytm Simona, algorytm Schora, algorytm Grovera – wszystkie zostały zbudowane.

Często zadawane pytania

Wypróbuj na żywo

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