- \n",
"
- Two $n$-qubit input registers are initialized to the zero state: \n", " \n", "\n", "$$\\lvert \\psi_1 \\rangle = \\lvert 0 \\rangle^{\\otimes n} \\lvert 0 \\rangle^{\\otimes n} $$\n", "\n", " \n", " \n", "
- Apply a Hadamard transform to the first register:\n", " \n", "\n", "$$\\lvert \\psi_2 \\rangle = \\frac{1}{\\sqrt{2^n}} \\sum_{x \\in \\{0,1\\}^{n} } \\lvert x \\rangle\\lvert 0 \\rangle^{\\otimes n} $$\n", "\n", " \n", " \n", " \n", "
- Apply the query function $\\text{Q}_f$: \n", " \n", "\n", "$$ \\lvert \\psi_3 \\rangle = \\frac{1}{\\sqrt{2^n}} \\sum_{x \\in \\{0,1\\}^{n} } \\lvert x \\rangle \\lvert f(x) \\rangle $$\n", "\n", " \n", " \n", " \n", "
- Measure the second register. A certain value of $f(x)$ will be observed. Because of the setting of the problem, the observed value $f(x)$ could correspond to two possible inputs: $x$ and $y = x \\oplus b $. Therefore the first register becomes:\n", " \n", "\n", "$$\\lvert \\psi_4 \\rangle = \\frac{1}{\\sqrt{2}} \\left( \\lvert x \\rangle + \\lvert y \\rangle \\right)$$\n", "\n", "\n", " where we omitted the second register since it has been measured. \n", " \n", " \n", "
- Apply Hadamard on the first register:\n", " \n", "\n", "$$ \\lvert \\psi_5 \\rangle = \\frac{1}{\\sqrt{2^{n+1}}} \\sum_{z \\in \\{0,1\\}^{n} } \\left[ (-1)^{x \\cdot z} + (-1)^{y \\cdot z} \\right] \\lvert z \\rangle $$\n", "\n", "\n", " \n", " \n", "
- Measuring the first register will give an output only if:\n", " \n", "\n", "$$ (-1)^{x \\cdot z} = (-1)^{y \\cdot z} $$\n", "\n", "\n", " which means:\n", " $$ x \\cdot z = y \\cdot z \\\\\n", " x \\cdot z = \\left( x \\oplus b \\right) \\cdot z \\\\\n", " x \\cdot z = x \\cdot z \\oplus b \\cdot z \\\\\n", " b \\cdot z = 0 \\text{ (mod 2)} $$\n", " \n", " A string $z$ will be measured, whose inner product with $b = 0$. Thus, repeating the algorithm $\\approx n$ times, we will be able to obtain $n$ different values of $z$ and the following system of equation can be written:\n", " \n", " \n", "\n", "$$ \\begin{cases} b \\cdot z_1 = 0 \\\\ b \\cdot z_2 = 0 \\\\ \\quad \\vdots \\\\ b \\cdot z_n = 0 \\end{cases}$$\n", "\n", "\n", " \n", " From which $b$ can be determined, for example by Gaussian elimination.\n", " \n", "

- \n",
"
- Two $2$-qubit input registers are initialized to the zero state:\n", " \n", "\n", "$$\\lvert \\psi_1 \\rangle = \\lvert 0 0 \\rangle_1 \\lvert 0 0 \\rangle_2 $$\n", "\n", " \n", " \n", "
- Apply Hadamard gates to the qubits in the first register:\n", " \n", "\n", "$$\\lvert \\psi_2 \\rangle = \\frac{1}{2} \\left( \\lvert 0 0 \\rangle_1 + \\lvert 0 1 \\rangle_1 + \\lvert 1 0 \\rangle_1 + \\lvert 1 1 \\rangle_1 \\right) \\lvert 0 0 \\rangle_2 $$\n", "\n", " \n", " \n", "
- For the string $b=11$, the query function can be implemented as $\\text{Q}_f = CX_{1_a 2_a}CX_{1_a 2_b}CX_{1_b 2_a}CX_{1_b 2_b}$ (as seen in the circuit diagram above):\n", " \n", "$$\n", "\\begin{aligned}\n", "\\lvert \\psi_3 \\rangle = \\frac{1}{2} ( \\; \n", " & \\lvert 0 0 \\rangle_1 \\; \\lvert 0\\oplus 0 \\oplus 0, & 0 \\oplus 0 \\oplus 0 \\rangle_2 &\\\\[5pt]\n", "+ & \\lvert 0 1 \\rangle_1 \\; \\lvert 0\\oplus 0 \\oplus 1, & 0 \\oplus 0 \\oplus 1 \\rangle_2 &\\\\[6pt]\n", "+ & \\lvert 1 0 \\rangle_1 \\; \\lvert 0\\oplus 1 \\oplus 0, & 0 \\oplus 1 \\oplus 0 \\rangle_2 &\\\\[6pt]\n", "+ & \\lvert 1 1 \\rangle_1 \\; \\lvert 0\\oplus 1 \\oplus 1, & 0 \\oplus 1 \\oplus 1 \\rangle_2 & \\; )\\\\\n", "\\end{aligned}\n", "$$\n", " \n", "Thus: \n", "\n", "$$ \n", "\\begin{aligned} \n", "\\lvert \\psi_3 \\rangle = \\frac{1}{2} ( \\quad\n", "& \\lvert 0 0 \\rangle_1 \\lvert 0 0 \\rangle_2 & \\\\[6pt]\n", "+ & \\lvert 0 1 \\rangle_1 \\lvert 1 1 \\rangle_2 & \\\\[6pt]\n", "+ & \\lvert 1 0 \\rangle_1 \\lvert 1 1 \\rangle_2 & \\\\[6pt]\n", "+ & \\lvert 1 1 \\rangle_1 \\lvert 0 0 \\rangle_2 & \\; )\\\\\n", "\\end{aligned}\n", "$$ \n", " \n", " \n", "
- We measure the second register. With $50\\%$ probability we will see either $\\lvert 0 0 \\rangle_2$ or $\\lvert 1 1 \\rangle_2$. For the sake of the example, let us assume that we see $\\lvert 1 1 \\rangle_2$. The state of the system is then\n", " \n", "\n", "$$ \\lvert \\psi_4 \\rangle = \\frac{1}{\\sqrt{2}} \\left( \\lvert 0 1 \\rangle_1 + \\lvert 1 0 \\rangle_1 \\right) $$\n", "\n", "\n", " \n", " where we omitted the second register since it has been measured.\n", " \n", " \n", " \n", " \n", " \n", "
- Apply Hadamard on the first register\n", " $$ \\lvert \\psi_5 \\rangle = \\frac{1}{2\\sqrt{2}} \\left[ \\left( \\lvert 0 \\rangle + \\lvert 1 \\rangle \\right) \\otimes \\left( \\lvert 0 \\rangle - \\lvert 1 \\rangle \\right) + \\left( \\lvert 0 \\rangle - \\lvert 1 \\rangle \\right) \\otimes \\left( \\lvert 0 \\rangle + \\lvert 1 \\rangle \\right) \\right] \\\\\n", " = \\frac{1}{2\\sqrt{2}} \\left[ \\lvert 0 0 \\rangle - \\lvert 0 1 \\rangle + \\lvert 1 0 \\rangle - \\lvert 1 1 \\rangle + \\lvert 0 0 \\rangle + \\lvert 0 1 \\rangle - \\lvert 1 0 \\rangle - \\lvert 1 1 \\rangle \\right] \\\\\n", " = \\frac{1}{\\sqrt{2}} \\left( \\lvert 0 0 \\rangle - \\lvert 1 1 \\rangle \\right)$$\n", " \n", " \n", " \n", "
- Measuring the first register will give either $\\lvert 0 0 \\rangle$ or $\\lvert 1 1 \\rangle$ with equal probability. \n", " \n", "
- \n", " If we see $\\lvert 1 1 \\rangle$, then: \n", " \n", "\n", "$$ b \\cdot 11 = 0 $$\n", "\n", "which tells us that $b \\neq 01$ or $10$, and the two remaining potential solutions are $b = 00$ or $b = 11$. Note that $b = 00$ will always be a trivial solution to our simultaneous equations. If we repeat steps 1-6 many times, we would only measure $|00\\rangle$ or $|11\\rangle$ as\n", "\n", "$$ b \\cdot 11 = 0 $$\n", "$$ b \\cdot 00 = 0 $$\n", " \n", "are the only equations that satisfy $b=11$. We can verify $b=11$ by picking a random input ($x_i$) and checking $f(x_i) = f(x_i \\oplus b)$. For example:\n", "\n", "$$ 01 \\oplus b = 10 $$\n", "$$ f(01) = f(10) = 11$$\n", "\n", " \n", "