All the references on Grover / Amplitude Amplification (AA) (Mike&Ike, wiki, Lin Lin lecture notes, etc.) give a recipe for preparing the desired state (or amplifying the state) with probability $\gamma=O(1)$. Can one improve this result by provably making the success probability exponentially close to 1? (At the cost of the polynomial increase of the algorithm cost.)

My question is motivated by the following construction (see the circuit below). Imagine that one needs to do Grover / AA on $K$ parallel registers. If the success probability is $\gamma$ for each register, the total success probability is $\gamma^K$, which is not scalable with $K$ (assuming that the number of qubits $m+n$ in each register is fixed), unless there is a way to make $\gamma$ itself exponentially close to $1$.

enter image description here

Note that if $A$ is unitary (as in the case of using QSP for simulating time evolution), then one can indeed make $\gamma$ exponentially small at a cost polylogarithmic in problem parameters. However, for $A$ being non-unitary one would need to first somehow amplify each $\gamma$.

  • $\begingroup$ It looks like knowing $\gamma$ with high probability may allow one to make the success probability exactly $1$: journals.aps.org/pra/abstract/10.1103/PhysRevA.62.052304 $\endgroup$
    – mavzolej
    Commented Sep 25, 2023 at 21:50
  • $\begingroup$ Yes, if you know your number of solutions $M$, in a search space of size $M/N$, you can get a success probability of at least $1-\frac{M}{N}$ (and equivalent statements for AA). It only takes about twice the number of steps of getting probability 1/2 which is where some texts choose to stop. $\endgroup$
    – DaftWullie
    Commented Sep 26, 2023 at 7:56
  • $\begingroup$ So for a fixed $N=2^n$ (I'm assuming that's what you mean in terms of qubit number), can I get arbitrary close to $1$? How do I do better than $1-M/N$? $\endgroup$
    – mavzolej
    Commented Sep 26, 2023 at 15:03
  • $\begingroup$ Generally, since $M$ is small, $M/N$ is vanishingly small, and nobody really worries about getting arbitrarily close. You can do it, but it's extra effort that isn't worth it. $\endgroup$
    – DaftWullie
    Commented Sep 27, 2023 at 7:40
  • $\begingroup$ It is small in the limit of a large number of qubits but the number of qubits may stay fixed. There are instances when it is important that the success probability is exponentially close to 1. The situation described in the second paragraph of my question is encountered, for example, in HHKL algorithm where circuits based on block encoding are applied to a large number of parallel registers. What saves us there is that block encodings are used to implement unitary transformations $e^{-iHt}$. But what if we wanted to implement non-unitary transformations on parallel registers? $\endgroup$
    – mavzolej
    Commented Sep 27, 2023 at 19:13


Your Answer

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