5.3.1 Hoekvergroting

Het laatste quantumalgoritme dat we zullen bespreken is een belangrijke subroutine die in veel andere quantumalgoritmes wordt gebruikt (het is bijvoorbeeld de kern van Grovers algoritme voor functies met meer dan $n=2$ invoerbits).

Het probleem dat deze subroutine oplost lijkt op het eerste gezicht een beetje apart. Het is namelijk een puur quantumprobleem dat niet een heel zinvolle klassieke formulering heeft. Toch komt het op natuurlijke wijze voor in verschillende andere algoritmes, waardoor de subroutine erg nuttig is. Dit laat zien hoe verschillend de ideeën achter quantumalgoritmes zijn en dat er nieuwe manieren van denken nodig zijn voor het uitvinden van nieuwe quantumalgoritmes!

Bovendien is dit een voorbeeld van een probleem waarbij het orakel meer dan één keer geraadpleegd moet worden. Dit is anders dan alle quantumalgoritmes die we eerder in deze quest hebben bekeken, waarbij het orakel maar één keer geraadpleegd hoefde te worden.

Huiswerkopdracht 5.6 (Wat is de hoek? (uitdagend)).

Alice en Bob zijn overstuur. "Het spijt ons voor de overlast,"vertellen ze. "We hebben deze prachtige reflectie $V(\theta)$ met hoek

\theta=+\frac{\pi}{4k}\quad\text{en}\quad\theta=-\frac{\pi}{4k},

gemaakt, maar we kunnen ons niet herinneren welke het was – we herinneren ons alleen het gehele getal $k\geq 1$ !"¹⁶¹⁶ 16 Als je wilt, kun je deze reflectie zien als een orakel dat één van de twee hoeken op een vreemde manier verbergt. Wat hun probleem nog erger maakt is dat de gate zichzelf vernietigt als het meer dan $k$ keer gebruikt wordt.

Kan jij ze helpen? Jouw taak, als je die aanvaardt, is om te bepalen welke van de twee hoeken de juiste is door de gate $V(\theta)$ maximaal $k$ keer te gebruiken.

Hint: Twee opeenvolgende spiegelingen geven een rotatie. Wat krijg je als je $\mathrm{NOT}$ en $V(\theta)$ combineert? (Je hebt de algemene formule van 4.6 niet nodig om deze vraag te beantwoorden).

Hack.

We volgen de hint, dus we bekijken $R=\mathrm{NOT}\,V(\theta)$ . We zien dat

\displaystyle\mathrm{NOT}\,V(\theta)=\mathrm{NOT}\,\mathrm{NOT}\,U(\theta)=U(\theta)

een rotatie is met hoek $\theta$ . In de tweede stap hebben we gebruikt dat $V(\theta)=\mathrm{NOT}\,U(\theta)$ , dit is precies hoe we $V(\theta)$ hebben gedefinieerd in Vgl. 2.33.

In Paragraaf 4.1.4 hebben we besproken dat twee opeenvolgende rotaties een rotatie maken waarvan de hoek de som is van de twee oorspronkelijke hoeken. Aangezien $R$ een rotatie is met een hoek $\theta$ , betekent dit dat als we dit $k$ keer herhalen, we een rotatie krijgen met een hoek van $k\theta=\pm\frac{\pi}{4}$ . Dat wil zeggen:

\displaystyle\underbrace{R\dotsb R}_{k\text{ keer}}=U(\pm\pi/4)

Als we als begintoestand $\left|+\right\rangle=\left|\psi(\pi/4)\right\rangle$ nemen, dan krijgen we

\underbrace{R\dotsb R}_{k\text{ keer}}\left|+\right\rangle=U(\pm\pi/4)\left|% \psi(\pi/4)\right\rangle=\left|\psi(\pi/4\pm\pi/4)\right\rangle.

Dus de eindtoestand is of $\left|\psi(\pi/2)\right\rangle=\left|1\right\rangle$ (als het teken een ’ $+$ ’ was) of $\left|\psi(0)\right\rangle=\left|0\right\rangle$ (als het teken een ’ $-$ ’ was). We kunnen deze twee gevallen onderscheiden door de eindtoestand te meten.