Potentiella tillämpningar av Grover-algoritmen i praktiken

Slutförd

I enhet 2 lärde du dig att det finns många problem som kan formuleras som ett sökproblem och därför kan lösas med Grovers algoritm. Nu när du är bekant med Grovers sökalgoritm och dess implementering ska vi gå tillbaka till frågan. Kan alla sökproblem dra nytta av kvanthastigheten som erbjuds av Grovers algoritm?

Svaret är tyvärr nej. I den här enheten tittar vi på de typer av problem som kan vara lämpliga för Grover-algoritmen.

Problem som inte har en specialiserad algoritm

Vi har sett att Grover-algoritmen inte förlitar sig på den interna strukturen i funktionen $f$. Men när du försöker lösa ett problem kan du försöka att använda det från olika vinklar, till exempel analysera problemstrukturen och se hur du kan använda den för att påskynda din lösning. Det gör att sökproblemen ofta har en väldefinierad problemstruktur som en klassisk algoritm kan utnyttja för att köra mycket snabbare.

Databassökningar nämns exempelvis ofta som en potentiell tillämpning av Grover-algoritmen. I praktiken utför databaser som lagrar information inte sökningar genom att testa var och en av posterna för att se om de matchar frågan. De förlitar sig i stället på index som möjliggör en mycket snabbare sökning. Stora databaser kan också dra nytta av distribuerad lagring och bearbetning.

Ett annat exempel är ett primtalsfaktoriseringsproblem. Även om ingen effektiv klassisk algoritm är känd ger Shor-algoritmen en bättre kvantmetod.

Den här observationen ger oss den första delen av svaret. De problem som drar nytta av Grover-algoritmen är de där vi enkelt kan kontrollera om det givna $x$ är svaret, men vi kan inte enkelt utnyttja problemstrukturen eller bearbeta parallellt för att hitta svaret.

Problem som möjliggör effektiv orakelimplementering

Kom ihåg att komplexitetsanalysen för Grover-algoritmen använder det antal funktionsbedömningar som krävs för att hitta svaret som ett mått, cirka $\sqrt{\frac{N}{M}}$, där $N$ är storleken på sökutrymmet och $M$ är antalet lösningar på problemet. Som jämförelse tar en fullständig klassisk sökning (att välja slumpmässiga indata, beräkna värdet för funktionen för den och kontrollera om det är 1) ungefär $\frac{N}{M}$ funktionsutvärderingar.

Den här analysen överväger dock inte komplexiteten vid utvärdering av funktionen, både i klassiska och i kvantfall. Om en funktionsutvärdering är mycket mer komplicerad på en kvantdator än på en klassisk, kommer den övergripande algoritmen att köras längre i kvantfallet, även om den tekniskt sett använder färre frågor.

Om funktionen till exempel definieras som en klassisk "täckande ruta", där implementeringen av funktionen inte är känd, kan du inte använda funktionens interna struktur för att implementera kvantakelt effektivt. Varje kvantfråga måste utvärdera den klassiska funktionen för var och en av $N$-indata. I det här scenariot är det mer effektivt att köra en fullständig klassisk sökning!

Så endast problem som gör att du snabbt kan beräkna framgångskriterier på en kvantdator kan betraktas som ett praktiskt program för Grovers algoritm.