3

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?

luciano
  • 6,084
  • 1
  • 13
  • 34
Ren-Xin Zhao
  • 558
  • 3
  • 12

1 Answers1

2

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.

Adrien Suau
  • 5,172
  • 22
  • 58