3
$\begingroup$

One of the most famous quantum algorithms is the quantum search, which is given an oracle, $U$ with elements along the diagonal. One element in $U$ is $-1$, and the rest are $1$ (along the diagonal) and $0$ (everywhere else).

However, many papers I find are referring to "fixed-point" quantum search. What is this in reference to? There exist fixed points, such as Brouwer fixed points, in a continuous finite mapping; is this related? This problem is hard classically, do these papers imply that it is solvable classically? An example paper is here

Sorry if this question seems trivial, I'm just confused at what the "fixed-point" means in this case, and haven't really seen anywhere else address it.

The abstract of the mentioned paper says this:

it lacks the fixed-point property — the fraction of target items must be known precisely to know when to terminate the algorithm.

But i'm not sure how this relates to what I'm asking, if at all.

$\endgroup$

1 Answer 1

4
$\begingroup$
  1. "Fixed-point quantum search" refers to variants of the quantum amplitude amplification algorithm (i.e., the generalization of the Grover algorithm) where the more iterations one does, the greater the probability of measuring a target state.
  2. This contrasts with the original search algorithms, where one needs to perform just about the right number of iterations. This is often referred to as the "soufflé problem": Iterating too few times undercooks the state, but iterating too many overcooks it.
  3. The original fixed-point quantum search algorithm was devised by Lov Grover himself. It came to be known as the "phase-$\frac{\pi}{3}$ method". As its name suggests, a single step is identical to an iteration of the Grover algorithm, except that a phase shift of $e^{i \pi/3}$ is applied instead of the original $e^{i \pi} = -1$. If the weight carried in the initial state by the states we wish to get rid of is $\epsilon$, then after such a step the weight carried by these undesired states is reduced to $\epsilon^3$. By implementing this process recursively, one can reduce the weight of the undesired states to $\epsilon^{3^n}$ after $n$ recursions.
  4. The problem with the phase-$\frac{\pi}{3}$ method is that it loses the quadratic speed-up expected for quantum search. Yoder, Low, and Chuang devised an alternative method that has the best of both worlds: It is fixed-point and preserves the quadratic speed-up. This is essentially the state-of-the-art quantum search method.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.