Skip to main content
Quantum Computing

Return to Answer

added 68 characters in body
Source Link
Joseph Geipel
Joseph Geipel
  • 1.2k
  • 1
  • 6
  • 6

If there are more than $N/2$ solutions then there are more solutions than non-solutions. This actually has the essential effect of making the states that are marked by the algorithm unmarked and the states that are unmarked marked during the flipping around the mean that occurs with the diffusion operator, meaning if there are $N/2 + k$ solutions for $0 < k < N/2$ then it will function as a search to amplify the probabilities of the $N/2 - k$ non-solutions, and will be equivalent in the number of iterations required to optimize this probability. In terms of what Grover's algorithm is used for, this idiosyncrasy is not normally a big deal since Grover's algorithm assumes by the requirements of its design one has a tractable method to determine whether a specific given input is a solution or not, meaning if there are more solutions than otherwise just classically picking a few random inputs and trying the check on them should find you a solution.

If one makes a 2-dimensional real plane with the two axes being associated with the orthogonal vectors of a uniform superposition of all the unmarked states (denoted $|s\rangle$) and a uniform superposition of all marked states (denoted $|\omega\rangle$), then the opening uniform superposition of all states will be rotated counterclockwise from $|s\rangle$ at an angle of $\sin^{-1}(\sqrt{\frac{m}{N}})$ towards $|\omega\rangle$ where $m$ is the number of solutions, and each iteration will do a further counterclockwise rotation of twice that value. The closer it is rotated to either side of the $|\omega\rangle$ axis, the better the probability. Under this paradigm, the nature of all these statements of what happens with a certain solution density can be shown: if exactly $N/2$ solutions then the starting angle is $\sin^{-1}(\frac{1}{\sqrt{2}}) = \frac{\pi}{4}$ and each iteration will rotate by $\pi/2$, meaning it will just switch between the diagonals of each quadrant and never reach the axes themselves. At $N/4$ then the angle is $\pi/6$ and after adding twice that one gets $\pi/2$ which lands you right on the axis, hence why that requires a single iteration. Between the two, a single iteration will overshoot the axis and provide a weaker and weaker improved probability as the number of solutions gets closer and closer to $N/2$. In the end though, if one is dealing with this sort of ratio of solutions to non-solution there's not really a quantum advantage to be gained by a search here, it's finding a needle in a haystack that is more than a quarter needles. Though, the related quantum counting algorithm can, from the Grover operator, determine the number of solutions, which may be classically harder.

If there are more than $N/2$ solutions then there are more solutions than non-solutions. This actually has the essential effect of making the states that are marked by the algorithm unmarked and the states that are unmarked marked during the flipping around the mean that occurs with the diffusion operator, meaning if there are $N/2 + k$ solutions for $0 < k < N/2$ then it will function as a search to amplify the probabilities of the $N/2 - k$ non-solutions, and will be equivalent in the number of iterations required to optimize this probability. In terms of what Grover's algorithm is used for, this idiosyncrasy is not normally a big deal since Grover's algorithm assumes by the requirements of its design one has a tractable method to determine whether a specific given input is a solution or not, meaning if there are more solutions than otherwise just classically picking a few random inputs and trying the check on them should find you a solution.

If one makes a 2-dimensional real plane with the two axes being associated with the orthogonal vectors of a uniform superposition of all the unmarked states (denoted $|s\rangle$) and a uniform superposition of all marked states (denoted $|\omega\rangle$), then the opening uniform superposition of all states will be rotated counterclockwise from $|s\rangle$ at an angle of $\sin^{-1}(\sqrt{\frac{m}{N}})$ towards $|\omega\rangle$ where $m$ is the number of solutions, and each iteration will do a further counterclockwise rotation of twice that value. The closer it is rotated to either side of the $|\omega\rangle$ axis, the better the probability. Under this paradigm, all statements can be shown: if exactly $N/2$ solutions then the starting angle is $\sin^{-1}(\frac{1}{\sqrt{2}}) = \frac{\pi}{4}$ and each iteration will rotate by $\pi/2$, meaning it will just switch between the diagonals of each quadrant and never reach the axes themselves. At $N/4$ then the angle is $\pi/6$ and after adding twice that one gets $\pi/2$ which lands you right on the axis, hence why that requires a single iteration. Between the two, a single iteration will overshoot the axis and provide a weaker and weaker probability as the number of solutions gets closer and closer to $N/2$. In the end though, if one is dealing with this sort of ratio of solutions to non-solution there's not really a quantum advantage to be gained by a search here, it's finding a needle in a haystack that is more than a quarter needles. Though, the related quantum counting algorithm can, from the Grover operator, determine the number of solutions, which may be classically harder.

If there are more than $N/2$ solutions then there are more solutions than non-solutions. This actually has the essential effect of making the states that are marked by the algorithm unmarked and the states that are unmarked marked during the flipping around the mean that occurs with the diffusion operator, meaning if there are $N/2 + k$ solutions for $0 < k < N/2$ then it will function as a search to amplify the probabilities of the $N/2 - k$ non-solutions, and will be equivalent in the number of iterations required to optimize this probability. In terms of what Grover's algorithm is used for, this idiosyncrasy is not normally a big deal since Grover's algorithm assumes by the requirements of its design one has a tractable method to determine whether a specific given input is a solution or not, meaning if there are more solutions than otherwise just classically picking a few random inputs and trying the check on them should find you a solution.

If one makes a 2-dimensional real plane with the two axes being associated with the orthogonal vectors of a uniform superposition of all the unmarked states (denoted $|s\rangle$) and a uniform superposition of all marked states (denoted $|\omega\rangle$), then the opening uniform superposition of all states will be rotated counterclockwise from $|s\rangle$ at an angle of $\sin^{-1}(\sqrt{\frac{m}{N}})$ towards $|\omega\rangle$ where $m$ is the number of solutions, and each iteration will do a further counterclockwise rotation of twice that value. The closer it is rotated to either side of the $|\omega\rangle$ axis, the better the probability. Under this paradigm, the nature of all these statements of what happens with a certain solution density can be shown: if exactly $N/2$ solutions then the starting angle is $\sin^{-1}(\frac{1}{\sqrt{2}}) = \frac{\pi}{4}$ and each iteration will rotate by $\pi/2$, meaning it will just switch between the diagonals of each quadrant and never reach the axes themselves. At $N/4$ then the angle is $\pi/6$ and after adding twice that one gets $\pi/2$ which lands you right on the axis, hence why that requires a single iteration. Between the two, a single iteration will overshoot the axis and provide a weaker and weaker improved probability as the number of solutions gets closer and closer to $N/2$. In the end though, if one is dealing with this sort of ratio of solutions to non-solution there's not really a quantum advantage to be gained by a search here, it's finding a needle in a haystack that is more than a quarter needles. Though, the related quantum counting algorithm can, from the Grover operator, determine the number of solutions, which may be classically harder.

Source Link
Joseph Geipel
Joseph Geipel
  • 1.2k
  • 1
  • 6
  • 6

If there are more than $N/2$ solutions then there are more solutions than non-solutions. This actually has the essential effect of making the states that are marked by the algorithm unmarked and the states that are unmarked marked during the flipping around the mean that occurs with the diffusion operator, meaning if there are $N/2 + k$ solutions for $0 < k < N/2$ then it will function as a search to amplify the probabilities of the $N/2 - k$ non-solutions, and will be equivalent in the number of iterations required to optimize this probability. In terms of what Grover's algorithm is used for, this idiosyncrasy is not normally a big deal since Grover's algorithm assumes by the requirements of its design one has a tractable method to determine whether a specific given input is a solution or not, meaning if there are more solutions than otherwise just classically picking a few random inputs and trying the check on them should find you a solution.

If one makes a 2-dimensional real plane with the two axes being associated with the orthogonal vectors of a uniform superposition of all the unmarked states (denoted $|s\rangle$) and a uniform superposition of all marked states (denoted $|\omega\rangle$), then the opening uniform superposition of all states will be rotated counterclockwise from $|s\rangle$ at an angle of $\sin^{-1}(\sqrt{\frac{m}{N}})$ towards $|\omega\rangle$ where $m$ is the number of solutions, and each iteration will do a further counterclockwise rotation of twice that value. The closer it is rotated to either side of the $|\omega\rangle$ axis, the better the probability. Under this paradigm, all statements can be shown: if exactly $N/2$ solutions then the starting angle is $\sin^{-1}(\frac{1}{\sqrt{2}}) = \frac{\pi}{4}$ and each iteration will rotate by $\pi/2$, meaning it will just switch between the diagonals of each quadrant and never reach the axes themselves. At $N/4$ then the angle is $\pi/6$ and after adding twice that one gets $\pi/2$ which lands you right on the axis, hence why that requires a single iteration. Between the two, a single iteration will overshoot the axis and provide a weaker and weaker probability as the number of solutions gets closer and closer to $N/2$. In the end though, if one is dealing with this sort of ratio of solutions to non-solution there's not really a quantum advantage to be gained by a search here, it's finding a needle in a haystack that is more than a quarter needles. Though, the related quantum counting algorithm can, from the Grover operator, determine the number of solutions, which may be classically harder.