Deutschs kvantealgoritme

David Deutsch offentliggjorde i 1985 en vigtig artikel, som for første gang viste, at kvanteberegninger kan være hurtigere end de tilsvarende klassiske beregninger for det samme problem. Richard Feynman havde kort før foreslået, at man kunne anvende kvanteberegninger til til at finde makromolekylers struktur og energiniveauer. Kvanteberegninger skal derfor betragtes i et større perspektiv end blot at forøge hastigheden af klassiske beregninger. Brydning af krypteringskoder er en ubetydelig anvendelse i det store perspektiv.

Deutschs problem vedrører funktioner af kun én variabel, som kan være enten 0 eller 1. Funktionerne antager således kun værdierne 0 eller 1. Deutsch anvender fire funktioner, som han benævner: f0, f1, f2, f3, som defineres ved
f0(0) = 0 og f0(1) = 0.
f1(0) = 0 og f1(1) = 1.
f2(0) = 1 og f2(1) = 0.
f3(0) = 1 og f3(1) = 1.
f0 og f3 er konstante funktioner.
f1 og f2 kaldes ligevægtige, idet funktionerne har lige stor sandsynlighed for at antage værdierne 0 og 1.

Deutschs problem: Givet en tilfældigt valgt funktion f ud af disse 4 funktioner. Hvor mange funktionskald er nødvendig for, at vi kan afgøre, om f er konstant eller ligevægtig? Vi er kun interesserede i at afgøre, om f er konstant eller ej.
Den klassiske analyse forløber på følgende måde: Antag, at vi finder f(0)=0. Funktionen er derfor enten f0 eller f1. Vi kan kun afgøre sagen ved at finde f(1). En klassisk beregning kræver derfor 2 funktionskald.

Deutsch betragter dernæst kvanteversionen af det samme spørgsmål. Vi får brug for 4 kvante-gates svarende til hver af de 4 funktioner, f0, f1, f2, f3:
Fi(|x>⊗|y>) = |x>⊗|fi(x)⊕y>.

Vi har de 4 kombinationer af |x>⊗|y>:
Fi(|0>⊗|0>) = |0>⊗|fi(0)>.
Fi(|0>⊗|1>) = |0>⊗|fi(0)⊕1>.
Fi(|1>⊗|0>) = |1>⊗|fi(1)>.
Fi(|1>⊗|1>) = |1>⊗|fi(1)⊕1>.
Bemærk: For alle værdier af “i” gælder, at én af f(0) og f(0)⊕1 er lig 0 og den anden er lig 1, samt at én af f(1) og f(1)⊕1 er lig 0 og den anden er lig 1. Dette viser, at alle 4 gates returnerer vektorer i den ordnede standardbase (|0>,|1>). De 4 gates er ortogonale og derfor reversible.

(fortsættes)