2
$\begingroup$

In Nielsen and Chuang (2010), section 6.1.1. it is written:

"For an N item search problem with M solutions, it turns out that we need only apply the search oracle O(sqrt(N/M)) times in order to obtain a solution on a quantum computer".

However, I'm not sure if this is a hard and fast rule, especially when M isn't known. For example, in the 2x2 binary sudoku outlined in this qiskit tutorial, possible solutions are all the possible values of 4 bits hence $N = 2^4 = 16$, we would expect therefore to run $\sqrt{16} = 4$ iterations of Grover's algorithm. I've also seen that $⌊(\pi/4) \sqrt{N}⌋$ iterations is optimal (from Kaye, Laflamme and Mosca). This would suggest 3 iterations to be optimal.

In the article, however, only 2 iterations are used. Increasing it to 3 or 4 iterations worsens the likelihood of getting good solutions significantly, and I'm not sure I understand why.

Additionally, with this in mind, how can one ever decide how many iterations are optimal for a given problem?

$\endgroup$
2
  • 1
    $\begingroup$ Slides 13-16 (numbers indicated on the bottom right) of this presentation will show you how to find the exact number of iterations required for a given instance of the Grover (or more generally the Amplitude Amplification) problem: drive.google.com/file/d/14G_0TwdxBFpI_Ylj5lb_imVtcnunrQcB/… $\endgroup$ Feb 6 at 22:14
  • $\begingroup$ Note that O notation only shows how the number of iterations scales and no constants are involved. This means that you cannot use that expression for calculation of actual number of iterations. $\endgroup$ Feb 7 at 6:55

2 Answers 2

0
$\begingroup$

Note that grover algorithm's iterations depends on the number of solutions the problem have (More than the optimal creates a really bad result).

We can know this by the Quantum Counting Algorithm.

$\endgroup$
2
  • $\begingroup$ I see, but what if we don't know the number of solutions to the problem? $\endgroup$
    – Lucas
    Feb 7 at 14:30
  • 1
    $\begingroup$ The Quantum Counting Algorithm is basically Grover + Quantum Phase Estimation (QPE). With the Grover's output and the QPE we can estimate the number of solutions. If you know something of spanish I recomend you ket.g youtube channel. He recently made a video of this $\endgroup$ Feb 7 at 14:58
0
$\begingroup$

Indeed, the adequate number of iterations over Grover's iterator depends on the number of solutions. Various methods have been proposed over the years to overcome this difficulty when the number of solutions is unknown, without giving up on the computational advantage that Grover's algorithm offers. I am going to cover 2 of those.

Method 1 - a stochastic iterative stepping process:

in section 4 of the paper "Tight bounds on quantum searching" by Boyer et al., there exists a description of the following method - given that $N$ is the dimension of the search-space and $t$ is the number of solutions, pick a step-size variable $1 < \lambda < \frac{4}{3}$, and set an upper-bound variable $m = 1$. Then initialize an iterative process consisting of the following steps:

  1. Increase $m$ by a factor of $\lambda$, i.e: $m = \lambda m$. If $\lambda m > \sqrt{N}$ then set $m = \sqrt{N}$.
  2. Pick randomly $j$ number of iterations, while $j$ is a natural number smaller than $m$, i.e $\{ j < m\ |\ j \in \mathbb{N} \}$.
  3. Execute Grover's algorithm with $j$ iterations and measure an outcome $i$.
  4. Verify that $i$ is indeed a solution (that's classically efficient and easy). If $i$ is a solution - done. If not - repeat.

Note that this process reveals one solution at a time, and should be initialized and repeated a sufficient number of times to reveal all solutions (depending on the size of $N$). It is noted in the paper that the time complexity of this process is $O\left(\sqrt{\frac{N}{t}}\right)$.


Method 2 - a dynamic circuit while loop:

This approach is kinda innovative and involves a dynamic circuit implementation (i.e non-unitary conditional operations are being used). There is a description of a proposed method in the paper - "A quantum while loop for amplitude amplification". I won't go into a detailed description but the overall idea is to exploit a weak measurements technique (recently explained in this QCSE post) to find out whether a solution is obtained in each Grover's iteration. It is done by allocating a "probe" qubit where $|1\rangle$ is written into where a solution is obtained. The probe qubit is measured in each iteration. If the outcome of the measurement is $1$, a measurement over the input qubits that spans the search-space is executed, and we're done, If the outcome of the measurement is $0$, the next iteration over Grover's iterator is executed. by measuring the probe qubit a partial collapsing of the system's quantum state occurs, as explained in the linked QCSE post. I would say that is the overall idea of this approach in a nutshell, for a detailed explanation look into the linked paper.


There is an open-source Qiskit-based package that I built, which synthesizes quantum circuits for satisfiability problems while exploiting Grover's algorithm. It uses versions of the above methods in cases where the number of solutions isn't known. It is called SAT Circuits Engine and there exists a pretty detailed demo of its proposed features in a demonstration notebook. It might help you better understand the nature of Grover's algorithm and the described methods above.

$\endgroup$

Your Answer

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

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