I am actually a newbie in quantum computing. I do have some doubts regarding quantum query complexity.

From what I understood is that we can't explicitly give the input and use oracle for this purpose. Let's say $O_x|i,b\rangle$ to $|i,b \operatorname{xor} x_i\rangle$ where $x_i$ is the $i$-th bit input and $i$ is the index.

The algorithm just consists of oracles and unitary operators. I wanted to know how do you really access the element? I mean we can't really give this 'i' Don't we? I didn't really found that intuitive.

Also, will the oracle of the algorithm be the same for whatever input we wanted to give?

  • $\begingroup$ Just to see if I get the example right, you are talking about a oracle $O(x)$ that has as input a string $x$ and acts on two qubits $|i, b\rangle$. And the effect on the qubit register is $O(x)|i,b\rangle=|i,b \oplus x_i\rangle$ where $x_i$ is the $i$th character of the string. Is this correct? If so, I don't get if the XOR operation is applied to $i$ and $b$ or only to one. Please correct me if I'm misunderstanding your question. Also let me know if you just want a clarification on what oracles are and how do they work. $\endgroup$ – epelaaez Jun 10 at 22:17
  • $\begingroup$ Also, remember that you can use Latex here (as I did on my other comment). Enclose the equation within $'s and write normal Latex code. This will make your question look better and be more understandable. $\endgroup$ – epelaaez Jun 10 at 22:18
  • $\begingroup$ Yes, I was talking the same oracle. I wanted to know how I would really access the inputs using this oracle. Please tell me more about oracles and their working. @epelaaez $\endgroup$ – Noob Jun 11 at 4:55
  • $\begingroup$ I just added an answer talking about this. And I just noticed I was misinterpreting the notation hahaha, but I get what the Oracle is supposed to do now and I’ve answered your questions. $\endgroup$ – epelaaez Jun 11 at 6:30

Oracles in quantum computing are "black boxes" that usually serve as input or help to another larger algorithm. They usually are defined by a function $f: \{0,1\}^n \rightarrow \{0,1\}^m$, which takes an $n$-bit input and produces an $m$-bit output. An important thing to note about oracles is that usually you don't know what is going on inside the black box, you just know that you can enter some input and you will get some output determined by $f$.

This last sentence has some controversy attached to it. Some algorithms heavily rely on oracles to achieve a speedup over their classical counterparts. However, if the function that needs to be performed by the oracle is too complex and there is no way of implementing efficiently, the speed up may be lost. That's why efficient oracle implementation is important.

From this paper:

Query complexity is a model of computation in which we have to compute a function $f(x1, \dots, x_N)$ of variables $x_i$ which can be accessed via queries. The complexity of an algorithm is measured by the number of queries that it makes. Query complexity is widely used for studying quantum algorithms, for two reasons. First, it includes many of the known quantum algorithms (including Grover’s quantum search and a key subroutine of Shor’s factoring algorithm). Second, one can prove lower bounds on the query complexity, bounding the possible quantum advantage

As you can see in the two points raised by the author, many quantum algorithms rely on oracles and their performance depend in the way we implement these oracles.

Now regarding your example. From what I understood, you have an oracle $O(x)$ acting on the register $|i,b\rangle$, which I'll write as $|i\rangle|b\rangle$. The action of the oralce on the register is given as follows $O(x)|i\rangle|b\rangle=|i\rangle|b\oplus x_i\rangle$.

I wanted to know how do you really access the element?

I guess you are referring to how the oracle is able to access $x_i$. Well, this isn't a concern when you are designing the algorithm, as you can just create oracles that perform some function $f$. However, this will be a concern when actually implementing the oracle. I'm not sure how an implementation of this would work, but I'd guess a lot of ancilla qubits to store the value of $x$ and get its $i$-th character.

Also, will the oracle be the same for whatever input we wanted to give it?

No, that's why we write the oracle as $O(x)$. This serves to represent that it depends on the string $x$. Another example of this is Grover's algorithm. You need an oracle that will mark the phase of a state that satisfies some conditions you give. Therefore, the oracle will depend on these conditions and you will get a different oracle for different desired states. More on Grover's algorithm oracle here.

  • $\begingroup$ Let's take an example of Grover Search, we need at most square root of n queries right ? Does this mean the same that we have accessed to only square root of n indexes of input and got the required element ? $\endgroup$ – Noob Jun 11 at 6:43
  • $\begingroup$ Also, how do you really input the list using oracle if let's say we want to search a element from a list of strings? $\endgroup$ – Noob Jun 11 at 6:44
  • $\begingroup$ Grover’s algorithm doesn’t access the elements of the array one by one like normal linear search would do, therefore it doesn’t access the square root of the length of the array. And for inputing the list, that’s actually given in the initial state, not the oracle. I recommend you read more about Grovers algorithm for these specific questions. $\endgroup$ – epelaaez Jun 11 at 7:07
  • $\begingroup$ Got it, Thanks mate! $\endgroup$ – Noob Jun 11 at 7:12
  • $\begingroup$ remember that you can edit the question's title to more closely reflect what is actually being asked (both epelaez and @Noob). That will enhance the reusability of both question and answer $\endgroup$ – glS Jun 11 at 7:52

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.