Skip to main content
Improved formatting; Added punctuations
Source Link
Sanchayan Dutta
  • 18.2k
  • 9
  • 54
  • 117

Given the oracle you have provided, the search is indeed pointless. However, that oracle misses the point of Grover's algorithm because searching for a card in a deck of cards is not an unstructured search because, as you stated, you already know the order. Ergo, your search is structured. The reason this oracle is used is that it demonstrates how Grover's may be applied without having to discuss an oracle that would make Grover's useful because such an oracle would be more complicated than valuable. Therefore, a better oracle to demonstrate the usefulness of Grover's might be something like:

$$ f(x) = \begin{cases} 1, & x[0, \ldots, 3] + x[4, \ldots, 7] = 1010 \\ 0, & otherwise \end{cases} $$$$ f(x) = \begin{cases} 1, & x[0, \ldots, 3] + x[4, \ldots, 7] = 1010 \\ 0, & \text{otherwise} \end{cases} $$

What this oracle implies is that you have an 8-qubit search where you take the first four qubits and add them to the second four qubits and flip M if the addition makes 10 (1010 in binary). The difference between this oracle and the one you provided is that this oracle tests a pattern (do the operands add to 10) whereas yours tests equality (is this index 5). This oracle is much more difficult to build but it leverages the true power of Grover's, which is, in essence, a brute-force search where your oracle defines the search space.

Given the oracle you have provided, the search is indeed pointless. However, that oracle misses the point of Grover's algorithm because searching for a card in a deck of cards is not an unstructured search because, as you stated, you already know the order. Ergo, your search is structured. The reason this oracle is used is that it demonstrates how Grover's may be applied without having to discuss an oracle that would make Grover's useful because such an oracle would be more complicated than valuable. Therefore, a better oracle to demonstrate the usefulness of Grover's might be something like:

$$ f(x) = \begin{cases} 1, & x[0, \ldots, 3] + x[4, \ldots, 7] = 1010 \\ 0, & otherwise \end{cases} $$

What this oracle implies is that you have an 8-qubit search where you take the first four qubits and add them to the second four qubits and flip M if the addition makes 10 (1010 in binary). The difference between this oracle and the one you provided is that this oracle tests a pattern (do the operands add to 10) whereas yours tests equality (is this index 5). This oracle is much more difficult to build but it leverages the true power of Grover's, which is in essence a brute-force search where your oracle defines the search space.

Given the oracle you have provided, the search is indeed pointless. However, that oracle misses the point of Grover's algorithm because searching for a card in a deck of cards is not an unstructured search because, as you stated, you already know the order. Ergo, your search is structured. The reason this oracle is used is that it demonstrates how Grover's may be applied without having to discuss an oracle that would make Grover's useful because such an oracle would be more complicated than valuable. Therefore, a better oracle to demonstrate the usefulness of Grover's might be something like:

$$ f(x) = \begin{cases} 1, & x[0, \ldots, 3] + x[4, \ldots, 7] = 1010 \\ 0, & \text{otherwise} \end{cases} $$

What this oracle implies is that you have an 8-qubit search where you take the first four qubits and add them to the second four qubits and flip M if the addition makes 10 (1010 in binary). The difference between this oracle and the one you provided is that this oracle tests a pattern (do the operands add to 10) whereas yours tests equality (is this index 5). This oracle is much more difficult to build but it leverages the true power of Grover's, which is, in essence, a brute-force search where your oracle defines the search space.

added 16 characters in body
Source Link
Woody1193
  • 361
  • 1
  • 11

Given the oracle you have provided, the search is indeed pointless. However, that oracle misses the point of Grover's algorithm because searching for a card in a deck of cards is not an unstructured search because, as you stated, you already know the order. Ergo, your search is structured. The reason this oracle is used is that it demonstrates how Grover's may be applied without having to discuss an oracle that would make Grover's useful because such an oracle would be more complicated than valuable. Therefore, a better oracle to demonstrate the usefulness of Grover's might be something like:

$$ f(x) = \begin{cases} 1, & x[0..3] + x[4..7] = 1010 \\ 0, & otherwise \end{cases} $$$$ f(x) = \begin{cases} 1, & x[0, \ldots, 3] + x[4, \ldots, 7] = 1010 \\ 0, & otherwise \end{cases} $$

What this oracle implies is that you have an 8-qubit search where you take the first four qubits and add them to the second four qubits and flip M if the addition makes 10 (1010 in binary). The difference between this oracle and the one you provided is that this oracle tests a pattern (do the operands add to 10) whereas yours tests equality (is this index 5). This oracle is much more difficult to build but it leverages the true power of Grover's, which is in essence a brute-force search where your oracle defines the search space.

Given the oracle you have provided, the search is indeed pointless. However, that oracle misses the point of Grover's algorithm because searching for a card in a deck of cards is not an unstructured search because, as you stated, you already know the order. Ergo, your search is structured. The reason this oracle is used is that it demonstrates how Grover's may be applied without having to discuss an oracle that would make Grover's useful because such an oracle would be more complicated than valuable. Therefore, a better oracle to demonstrate the usefulness of Grover's might be something like:

$$ f(x) = \begin{cases} 1, & x[0..3] + x[4..7] = 1010 \\ 0, & otherwise \end{cases} $$

What this oracle implies is that you have an 8-qubit search where you take the first four qubits and add them to the second four qubits and flip M if the addition makes 10 (1010 in binary). The difference between this oracle and the one you provided is that this oracle tests a pattern (do the operands add to 10) whereas yours tests equality (is this index 5). This oracle is much more difficult to build but it leverages the true power of Grover's, which is in essence a brute-force search where your oracle defines the search space.

Given the oracle you have provided, the search is indeed pointless. However, that oracle misses the point of Grover's algorithm because searching for a card in a deck of cards is not an unstructured search because, as you stated, you already know the order. Ergo, your search is structured. The reason this oracle is used is that it demonstrates how Grover's may be applied without having to discuss an oracle that would make Grover's useful because such an oracle would be more complicated than valuable. Therefore, a better oracle to demonstrate the usefulness of Grover's might be something like:

$$ f(x) = \begin{cases} 1, & x[0, \ldots, 3] + x[4, \ldots, 7] = 1010 \\ 0, & otherwise \end{cases} $$

What this oracle implies is that you have an 8-qubit search where you take the first four qubits and add them to the second four qubits and flip M if the addition makes 10 (1010 in binary). The difference between this oracle and the one you provided is that this oracle tests a pattern (do the operands add to 10) whereas yours tests equality (is this index 5). This oracle is much more difficult to build but it leverages the true power of Grover's, which is in essence a brute-force search where your oracle defines the search space.

Source Link
Woody1193
  • 361
  • 1
  • 11

Given the oracle you have provided, the search is indeed pointless. However, that oracle misses the point of Grover's algorithm because searching for a card in a deck of cards is not an unstructured search because, as you stated, you already know the order. Ergo, your search is structured. The reason this oracle is used is that it demonstrates how Grover's may be applied without having to discuss an oracle that would make Grover's useful because such an oracle would be more complicated than valuable. Therefore, a better oracle to demonstrate the usefulness of Grover's might be something like:

$$ f(x) = \begin{cases} 1, & x[0..3] + x[4..7] = 1010 \\ 0, & otherwise \end{cases} $$

What this oracle implies is that you have an 8-qubit search where you take the first four qubits and add them to the second four qubits and flip M if the addition makes 10 (1010 in binary). The difference between this oracle and the one you provided is that this oracle tests a pattern (do the operands add to 10) whereas yours tests equality (is this index 5). This oracle is much more difficult to build but it leverages the true power of Grover's, which is in essence a brute-force search where your oracle defines the search space.