Recently, I have paid attention to some oracle algorithms, such as Grover. Generally speaking, an oracle is a kind of black box, and Grover's algorithm constructs an oracle through quantum circuits. From a higher level, ask the question, which oracles are difficult to design, which ones can be designed, and which ones cannot be designed? What are the laws or mathematical laws that design oracles? What metric is the quantum advantage of oracles measured by?


1 Answer 1


From my experience in building oracles, this question is answered by the following statement:

The complexity of constructing a specific quantum oracle is inversely proportional to the amount of information you have to use to describe fully the value of each entry of the unitary matrix representing this oracle.

The above statement is not rigorous, might have "holes", and I might have used imprecise words so let me illustrate what I mean with examples.

If your oracle should implement the identity operation, you can fully describe it with a very limited amount of information:

  • It is the identity operation.
  • It is the matrix with ones on the main diagonal and zeros everywhere else.
  • It is the matrix $M$ such that $\forall i, M_{i,i} = 1$ and $\forall i, \forall j \neq i, M_{i, j} = 0$. [1]
  • It is the operation $M$ such that $M\vert \psi \rangle = \vert \psi \rangle$, for any quantum state $\vert\psi\rangle$.

Another "efficient" oracle example might be the following:

  • It is the matrix with ones on the entries above the main diagonal and zeros everywhere else.
  • It is the matrix $M$ such that $\forall i, M_{i,i+1} = 1$ and $\forall i, \forall j \neq i+1, M_{i, j} = 0$. [1]
  • It is the operation $M$ such that $M\vert \psi \rangle = \vert \psi + 1 \rangle$, for any quantum state $\vert\psi\rangle$ written in the canonical basis.
  • It is the operation that increments by $1$.

All the above points are different ways of describing the oracle considered, and they are all:

  1. Complete in the sense that they completely describe the oracle, there is no need for more information.
  2. Efficient because I can write them down and you can read them in seconds.

Now, an example of an oracle that is not easy to build would be an oracle that associates a random quantum state to any input state.

As you can see, I just described the oracle in only a few words, but I cannot describe fully the value of each of its entry without actually writing them down:

  • $M\vert 0 \rangle = 0.0007635 \vert 0 \rangle + 0.073647 \vert 1 \rangle + ... - 0.000003846 \vert 2^n - 1 \rangle$
  • $M\vert 1 \rangle = -0.0096327 \vert 0 \rangle - 0.000259 \vert 1 \rangle + ... - 0.005963214 \vert 2^n - 1 \rangle$
  • ...
  • $M\vert 2^n - 1 \rangle = 0.8563 \vert 0 \rangle + 0.0000056 \vert 1 \rangle + ... - 0.06595 \vert 2^n - 1 \rangle$

which is a lot of information.

[1]: the range of $i$ and $j$ are not written down for simplicity, but writing them down would not change the point.

  • 1
    $\begingroup$ Your comments are very valuable. Grateful! Although in idea, like the case you gave, it can be described in words. But how to be sure that your statement is complete? In other words, how do we rigorously prove this completeness using mathematical theory. Second, should efficiency be supplemented, ie, realized efficiency? Describing things with linguistic logic is efficient, but translating that logic into quantum circuit implementations may be difficult. $\endgroup$ Jul 28, 2022 at 22:37
  • 1
    $\begingroup$ As I said in the first paragraph, there is nothing rigorous here, only the feeling of someone that ended up implementing complex oracles for a few months. The track I would follow to prove this would be to prove that the actual "non-efficient" bit of oracle construction is "data transfer from classical to quantum" (for the moment, QRAM is not efficient). If you need a lot of data (i.e., information) to describe your oracle, you also need to "send" a lot of data to the quantum chip to implement the oracle, which is yet not efficient. $\endgroup$ Jul 29, 2022 at 11:41
  • $\begingroup$ Whether there are related papers or reference materials on the design of Oracle, at present I want to thoroughly understand the underlying logic of Oracle $\endgroup$ Jul 30, 2022 at 4:43

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.