3
$\begingroup$

One of the question while I discussed with my colleague in the math department was the construction of oracle circuit.

In computer science, specifically in algorithm, we take oracle as granted and treat it as a black box to analyze our problem.

However, he raised the question that given the oracle function, can the circuit be constructed in a reversible way; namely, unitary oracle common in well-known algorithm. He thought that the input may be subjected to phase kickback.

My question is given the oracle function. Can’t we use the reversible computation defined in classical computer to construct this oracle circuit?

Improve this question
$\endgroup$
2
  • $\begingroup$ Hi @Uriah! Are you asking about automatic quantum circuit generation from a given classical function? Or maybe your question is more "is any oracle implementable or are there any oracle that might not be implementable on a quantum computer?"? Could you rephrase a little bit your question to make it clearer? $\endgroup$
    – Adrien Suau
    Aug 10, 2021 at 13:11
  • $\begingroup$ Sure I was asking if any oracle given the oracle function and related circuit can be implemented in reversible way, just as described in algorithm such as Deutsch-Jozsa. $\endgroup$
    – Uriah
    Aug 10, 2021 at 16:53

2 Answers 2

Reset to default
2
$\begingroup$

Given any function and its corresponding circuit implementation you can build a reversible circuit implementation of the oracle by keeping track of the input. The oracle $U$ that implements a function $f$ would act as

$$ U : |x\rangle|y\rangle \xrightarrow{} |x\rangle|y\oplus f(x)\rangle. $$

This way, even if $f$ maps two or more different inputs to the same output, the oracle is still one-to-one and therefore reversible. Usually, the $|y\rangle$ register is set to $|0\rangle$ so the output is $|x\rangle|f(x)\rangle$; however, this is not a requirement.

The input of the oracle $U$ ($|x\rangle$ register) is prone to phase kickback, but this doesn’t affect its reversibility. In fact, this is good since it allows us to know more about $f$ in fewer queries than the classical case, just as in the Deutsch-Jozsa algorithm.

To read about implementing quantum oracles, I recommend Canonical Construction of Quantum Oracles and section 6 of Quantum simulation logic, oracles, and the quantum advantage.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Sorry for the rough question, but could elaborate on the clause that phase kickback does not affect the reversibility? Or offering one example to illustrate this effect. $\endgroup$
    – Uriah
    Aug 15, 2021 at 22:45
  • $\begingroup$ @Uriah phase kickback is an effect that can be seen when running the circuit, and it depends on the input to it. For example, in the Qiskit textbook chapter 2.3, phase kickback can be seen when the control is in $|-\rangle$ and the target in $|+\rangle$. This doesn't depend on the oracle itself, it's just a property you can exploit from it. To construct a reversible oracle, it is sufficient to map all basis states $|i\rangle$ to different $|j\rangle$ states. $U$ in my answer is an example of this. $\endgroup$
    – epelaez
    Aug 16, 2021 at 2:25
  • $\begingroup$ Now, even phase kickback doesn't affect the reversibility as you can see that applying $U$ two times, even if relative phase was introduced in the process, returns the registers to their original states. Following the example in the Qiskit textbook chapter I linked, the original registers are in the $|-+\rangle$ state (control at the right and target in the left) and sending this through a $CNOT$ results in $|--\rangle$ (a phase of $-1$ was added to the control qubit) thanks to phase kickback. Applyin the oracle (single $CNOT$ gate) again results in... $\endgroup$
    – epelaez
    Aug 16, 2021 at 2:29
  • $\begingroup$ $CNOT|--\rangle = CNOT(|-\rangle|0\rangle - |-\rangle|1\rangle) = |-\rangle|0\rangle - (-|-\rangle|1\rangle) = |-\rangle|0\rangle + |-\rangle|1\rangle = |-+\rangle$. As you can see, applying this simple oracle two times works as expected (it is reversible) even though phase kickback was introduced in between. $\endgroup$
    – epelaez
    Aug 16, 2021 at 2:30
0
$\begingroup$

I'm not sure I understand the question, but as far as I know, if you have Oracle function and its implementation through classical circuit, you will be able to implement the reversibile circuit using the corresponding quantum gates. I think you can do that always because with quantum gates you can rapresent every classical circuit

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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