We’re rewarding the question askers & reputations are being recalculated! Read more.

# Return to Answer

 2 added 1741 characters in body edited Mar 28 at 12:09 Mark S 2,57144 silver badges2828 bronze badges Let $$f$$ be your favorite $$\mathrm{SAT}$$ problem. For example, one that I like is: Are there integers $$x_1, x_2, x_3$$, each $$-2^{50}\le x_1,x_2,x_3 \le 2^{50}$$, with $$x_1^3+x_2^3+x_3^3=42?$$ Write $$f$$ as a sequence of irreversible $$\mathsf{NAND}$$ gates, etc., and convert them to a sequence of reversible $$\mathsf{CCNOT}$$ gates, etc. to determine a unitary $$U_f$$. In the example problem, this unitary will take the $$103$$ bits of $$x_i$$ to a single output $$y$$. Here $$y$$ is $$1$$ if and only if the $$\mathrm{SAT}$$ problem is solved. Take a first register initially at $$\vert 0\rangle$$, and apply a Hadamard to put it in the uniform superposition of all states. In the example problem, the first register is $$153$$ qubits ($$50$$ plus $$1$$ sign bit each.) Apply $$U_f$$ to the second register conditioned on the first register. Thus, in the sample problem, the system is in the state $$\vert x_1,x_2,x_3\rangle \vert f(x_1,x_2,x_3\rangle$$$$\vert x_1,x_2,x_3\rangle \vert f(x_1,x_2,x_3)\rangle$$, where $$x_1,x_2,x_3$$ are between $$-2^{50}$$ and $$2^{50}$$ and $$f$$ is $$1$$ if and only if $$x_1^3+x_2^3+x_3^3=42$$ Apply a phase shift to the first register conditioned on the value of the second register Apply the Grover diffusion operator to the first register Repeat steps 5 and 6 $$O(\sqrt N)$$ times. (With the sample problem, apply this $$O(\sqrt {2^{153}})$$ times.) If there's only one solution, the first register should be in the state that satisfies $$f(x)=1$$. With the sample problem, it should be in the state $$\vert x_1,x_2,x_3\rangle$$ solving $$x_1^3+x_2^3+x_3^3=42$$. The heart of Grover is steps 5, 6, and 7. Steps 1-4 can be fiddled with. EDIT $$f$$ is applied to the second register based on the values of the first register. The first register is left unchanged upon the application of $$f$$ to the second register. If the first register is in a uniform superposition over all states initially, then after application of $$U_f$$, acting on both the first register and the second register, the first register will still be in a uniform superposition. $$U_f$$ relies on the contents of $$x$$ to determine the contents of $$y$$ but it leaves the contents of $$x$$ unchanged. For example, from the questions in your comments, I can tell that you understand that $$f$$ can be written classically as a set of irreversible $$\mathsf{NAND},\mathsf{NOR},\mathsf{AND}$$, etc. gates. Classically if we were to apply $$f$$, then we may lose the value of $$x$$. But remember quantum-mechanically the states must be reversible. Thus from your questions I think you also recognize that $$\mathsf{NAND}$$ gates etc. need to be converted to $$\mathsf{CCNOT}$$ gates etc. It's no surprise that these gates tend to leave some inputs unchanged - the qubits that are left unchanged would correspond to $$x$$, and the qubits that are changed would correspond to $$f(x)$$. After application of $$U_f$$, for each possible value of the first register, a different value is stored in the second register, but the first register is unchanged. Shor's algorithm is a little different - initially a uniform superposition is applied to a first register, then a value of some function is calculated in the second register. In Shor, we can throw away the second register; in Grover, we need to save the second register for the repeated conditional rotations (this part I think you understand). Let $$f$$ be your favorite $$\mathrm{SAT}$$ problem. For example, one that I like is: Are there integers $$x_1, x_2, x_3$$, each $$-2^{50}\le x_1,x_2,x_3 \le 2^{50}$$, with $$x_1^3+x_2^3+x_3^3=42?$$ Write $$f$$ as a sequence of irreversible $$\mathsf{NAND}$$ gates, etc., and convert them to a sequence of reversible $$\mathsf{CCNOT}$$ gates, etc. to determine a unitary $$U_f$$. In the example problem, this unitary will take the $$103$$ bits of $$x_i$$ to a single output $$y$$. Here $$y$$ is $$1$$ if and only if the $$\mathrm{SAT}$$ problem is solved. Take a first register initially at $$\vert 0\rangle$$, and apply a Hadamard to put it in the uniform superposition of all states. In the example problem, the first register is $$153$$ qubits ($$50$$ plus $$1$$ sign bit each.) Apply $$U_f$$ to the second register conditioned on the first register. Thus, in the sample problem, the system is in the state $$\vert x_1,x_2,x_3\rangle \vert f(x_1,x_2,x_3\rangle$$, where $$x_1,x_2,x_3$$ are between $$-2^{50}$$ and $$2^{50}$$ and $$f$$ is $$1$$ if and only if $$x_1^3+x_2^3+x_3^3=42$$ Apply a phase shift to the first register conditioned on the value of the second register Apply the Grover diffusion operator to the first register Repeat steps 5 and 6 $$O(\sqrt N)$$ times. (With the sample problem, apply this $$O(\sqrt {2^{153}})$$ times.) If there's only one solution, the first register should be in the state that satisfies $$f(x)=1$$. With the sample problem, it should be in the state $$\vert x_1,x_2,x_3\rangle$$ solving $$x_1^3+x_2^3+x_3^3=42$$. The heart of Grover is steps 5, 6, and 7. Steps 1-4 can be fiddled with. Let $$f$$ be your favorite $$\mathrm{SAT}$$ problem. For example, one that I like is: Are there integers $$x_1, x_2, x_3$$, each $$-2^{50}\le x_1,x_2,x_3 \le 2^{50}$$, with $$x_1^3+x_2^3+x_3^3=42?$$ Write $$f$$ as a sequence of irreversible $$\mathsf{NAND}$$ gates, etc., and convert them to a sequence of reversible $$\mathsf{CCNOT}$$ gates, etc. to determine a unitary $$U_f$$. In the example problem, this unitary will take the $$103$$ bits of $$x_i$$ to a single output $$y$$. Here $$y$$ is $$1$$ if and only if the $$\mathrm{SAT}$$ problem is solved. Take a first register initially at $$\vert 0\rangle$$, and apply a Hadamard to put it in the uniform superposition of all states. In the example problem, the first register is $$153$$ qubits ($$50$$ plus $$1$$ sign bit each.) Apply $$U_f$$ to the second register conditioned on the first register. Thus, in the sample problem, the system is in the state $$\vert x_1,x_2,x_3\rangle \vert f(x_1,x_2,x_3)\rangle$$, where $$x_1,x_2,x_3$$ are between $$-2^{50}$$ and $$2^{50}$$ and $$f$$ is $$1$$ if and only if $$x_1^3+x_2^3+x_3^3=42$$ Apply a phase shift to the first register conditioned on the value of the second register Apply the Grover diffusion operator to the first register Repeat steps 5 and 6 $$O(\sqrt N)$$ times. (With the sample problem, apply this $$O(\sqrt {2^{153}})$$ times.) If there's only one solution, the first register should be in the state that satisfies $$f(x)=1$$. With the sample problem, it should be in the state $$\vert x_1,x_2,x_3\rangle$$ solving $$x_1^3+x_2^3+x_3^3=42$$. The heart of Grover is steps 5, 6, and 7. Steps 1-4 can be fiddled with. EDIT $$f$$ is applied to the second register based on the values of the first register. The first register is left unchanged upon the application of $$f$$ to the second register. If the first register is in a uniform superposition over all states initially, then after application of $$U_f$$, acting on both the first register and the second register, the first register will still be in a uniform superposition. $$U_f$$ relies on the contents of $$x$$ to determine the contents of $$y$$ but it leaves the contents of $$x$$ unchanged. For example, from the questions in your comments, I can tell that you understand that $$f$$ can be written classically as a set of irreversible $$\mathsf{NAND},\mathsf{NOR},\mathsf{AND}$$, etc. gates. Classically if we were to apply $$f$$, then we may lose the value of $$x$$. But remember quantum-mechanically the states must be reversible. Thus from your questions I think you also recognize that $$\mathsf{NAND}$$ gates etc. need to be converted to $$\mathsf{CCNOT}$$ gates etc. It's no surprise that these gates tend to leave some inputs unchanged - the qubits that are left unchanged would correspond to $$x$$, and the qubits that are changed would correspond to $$f(x)$$. After application of $$U_f$$, for each possible value of the first register, a different value is stored in the second register, but the first register is unchanged. Shor's algorithm is a little different - initially a uniform superposition is applied to a first register, then a value of some function is calculated in the second register. In Shor, we can throw away the second register; in Grover, we need to save the second register for the repeated conditional rotations (this part I think you understand). 1 answered Mar 28 at 2:26 Mark S 2,57144 silver badges2828 bronze badges Let $$f$$ be your favorite $$\mathrm{SAT}$$ problem. For example, one that I like is: Are there integers $$x_1, x_2, x_3$$, each $$-2^{50}\le x_1,x_2,x_3 \le 2^{50}$$, with $$x_1^3+x_2^3+x_3^3=42?$$ Write $$f$$ as a sequence of irreversible $$\mathsf{NAND}$$ gates, etc., and convert them to a sequence of reversible $$\mathsf{CCNOT}$$ gates, etc. to determine a unitary $$U_f$$. In the example problem, this unitary will take the $$103$$ bits of $$x_i$$ to a single output $$y$$. Here $$y$$ is $$1$$ if and only if the $$\mathrm{SAT}$$ problem is solved. Take a first register initially at $$\vert 0\rangle$$, and apply a Hadamard to put it in the uniform superposition of all states. In the example problem, the first register is $$153$$ qubits ($$50$$ plus $$1$$ sign bit each.) Apply $$U_f$$ to the second register conditioned on the first register. Thus, in the sample problem, the system is in the state $$\vert x_1,x_2,x_3\rangle \vert f(x_1,x_2,x_3\rangle$$, where $$x_1,x_2,x_3$$ are between $$-2^{50}$$ and $$2^{50}$$ and $$f$$ is $$1$$ if and only if $$x_1^3+x_2^3+x_3^3=42$$ Apply a phase shift to the first register conditioned on the value of the second register Apply the Grover diffusion operator to the first register Repeat steps 5 and 6 $$O(\sqrt N)$$ times. (With the sample problem, apply this $$O(\sqrt {2^{153}})$$ times.) If there's only one solution, the first register should be in the state that satisfies $$f(x)=1$$. With the sample problem, it should be in the state $$\vert x_1,x_2,x_3\rangle$$ solving $$x_1^3+x_2^3+x_3^3=42$$. The heart of Grover is steps 5, 6, and 7. Steps 1-4 can be fiddled with.