We’re rewarding the question askers & reputations are being recalculated! Read more.
2 added 1741 characters in body
source | link
  1. 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?$

  1. 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.

  2. 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.)

  3. 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$

  4. Apply a phase shift to the first register conditioned on the value of the second register

  5. Apply the Grover diffusion operator to the first register

  6. Repeat steps 5 and 6 $O(\sqrt N)$ times. (With the sample problem, apply this $O(\sqrt {2^{153}})$ times.)

  7. 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. 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?$

  1. 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.

  2. 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.)

  3. 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$

  4. Apply a phase shift to the first register conditioned on the value of the second register

  5. Apply the Grover diffusion operator to the first register

  6. Repeat steps 5 and 6 $O(\sqrt N)$ times. (With the sample problem, apply this $O(\sqrt {2^{153}})$ times.)

  7. 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.

  1. 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?$

  1. 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.

  2. 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.)

  3. 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$

  4. Apply a phase shift to the first register conditioned on the value of the second register

  5. Apply the Grover diffusion operator to the first register

  6. Repeat steps 5 and 6 $O(\sqrt N)$ times. (With the sample problem, apply this $O(\sqrt {2^{153}})$ times.)

  7. 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
source | link

  1. 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?$

  1. 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.

  2. 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.)

  3. 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$

  4. Apply a phase shift to the first register conditioned on the value of the second register

  5. Apply the Grover diffusion operator to the first register

  6. Repeat steps 5 and 6 $O(\sqrt N)$ times. (With the sample problem, apply this $O(\sqrt {2^{153}})$ times.)

  7. 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.