I was wondering why till date Grover search has been implemented only till 3 qubits (corresponding to size of database = 8). Refer this paper

The reason why I ask is that we have much larger sized quantum computers today. For eg IBM has 50 qubits, Google has announced 72. Why can't we run a larger sized Grover algorithm on these computers ? Some of my guesses (based on theoretical issues) are as follows :

  1. Circuit architecture restrictions : Perhaps the gate set and the underlying architecture of the circuits provided by these computers puts a restriction.

  2. Error corrections : Additional qubits are required for correcting errors.

I would like to know if there are any additional practical/physics issues that is limiting the use of Grover search currently.


I am going to try to give guesses that can make sense:

  1. More qubits does not mean better machines. They may be less noise-tolerant and with less connectivity between qubits. That is why, when you benchmark them (with or without error-correction), you look first at the simplest implementations of state of art algorithms. Plus, you may change some calibrations parameters of the machine based on these results.
  2. Implementing a multi-controlled NOT gate (for example as the oracle) can require a lot of quantum operations like Toffolis (which has a quite deep decomposation into 2-qubit and 1-qubit set of gates), meaning you have deeper circuits, which are more difficult to apply given the (depth) limit of these quantum computers.
  3. The example circuit you refer to is a very toy example. So it is not very useful other than benchmarking so far.

    Please, bear in mind these are guesses. There may be many things going on and this is a research playground with a few people involved in the field.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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