4
$\begingroup$

The working of a quantum oracle is still not completely clear to me and I have a few questions: As I understand it, an oracle is a unitary quantum gate and must somehow differentiate between the eigenstates of the quantum register (the current state of which is a superposition of its eigenstates which are composites of the eigenstates of the cubits that make up the register) so that the amplitudes of some eigenstates can be increased or decreased. The differentiating criterion is given by some function $f(x)$ and $f(x)$ is mostly given to be two-valued.

My first question is: what is the domain of $x$? Is this just the set of eigenstates of the quantum register? If so, then for the quantum algorithm to work, all data must somehow be in the register state. This encoding of external data (the haystack) into the states of the quantum register would seem to be a major challenge. How can this be done?

Or is it possible that $f(x)$ somehow calls a classical function... but how, when?

It is said that in e.g. Grover's algorithm the function $f(x)$ is called just once. But what does this mean if it somehow has to filter all the $2^N$ eigenstates.

Improve this question
$\endgroup$
3
  • $\begingroup$ It seems like you have gotten hung up on the generalizations of oracles, over a specific use of an oracle for, say, a $\mathsf{3SAT}$ problem. Have you seen this? $\endgroup$
    – Mark Spinelli
    Commented Jun 19, 2019 at 12:13
  • $\begingroup$ I know about SAT problems indeed. How is the SAT logical expression implemented in an oracle? This must also be some sort of quantum thing; I suppose it cannot call a digital computer.... $\endgroup$
    – michiel perdeck
    Commented Jun 19, 2019 at 13:06
  • $\begingroup$ If you have a first register as $n$ qubits in a uniform superposition over all $2^n$ states, and you have, as your oracle, your $\mathsf{3SAT}$ instance $f(x)$, you cam instantiate your oracle into a second register (plus some ancilla bits) that evaluates $f(x)$ for each of the $2^n$ bits in the first register. $\endgroup$
    – Mark Spinelli
    Commented Jun 19, 2019 at 16:19

2 Answers 2

Reset to default
4
$\begingroup$

The domain of $x$ is all bitstrings of certain length, which corresponds to eigenstates of the register. The exact meaning of $x$ might vary - it could be a set of boolean values, like in SAT problem, or a set of colors assigned to vertices, like in graph coloring problem, or integers.

The oracle has to encode the condition you're searching for as a quantum circuit - and yes, this is a challenge indeed. It is worth checking out other questions on Grover on this site, since a lot of them will consider oracle implementations (here are two that look the closest to your question at a glance: 1, 2).

Speaking of a SAT problem specifically, since it was mentioned in the comments, the oracle has to encode the logical constraints on the boolean values that the variables can take based on the specific formula you're given. Each AND clause is expressed as a controlled X gate; each OR clause is expressed as a 0-controlled X gate, followed by an X gate on the target (De Morgan's laws), and so on. You can find an example of implementing an oracle for an instance of SAT problem in my tutorial.

Improve this answer
$\endgroup$
1
$\begingroup$

Assuming you have n qubits then the domain of $x$ is all bit-strings $n$. ($2^n$ values)

To encode the data, in many cases, we start with the maximum superposition state. Which means each qubit is in an equal superposition of |0> and |1> so the entire system of $n$ qubits is in a massive superposition of all possible states (the entire domain of $x$).

Then in the case of Grover's algorithm in each iteration we call the oracle $f(x)$ and for the sub-states in which $f(x) = 1$ the amplitudes are enhanced. The amplitudes are diminished for the states where $f(x) = 0$. By doing this over a number of iterations we are left a superposition that contains mostly states that satisfy $f(x) =1$

The oracle does not call a classical function. It has to do computation in the quantum space.

Improve this answer
$\endgroup$

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.