I'd like to be able to program simple functions into simulators such as QCL. I read that any function $f$ can be implemented, but I don't know how to get say a unitary matrix that implements $f$.
$\newcommand{\qr}[1]{|#1\rangle}$
I think first I must figure out a function that mimics $f$ in a reversible way. I think that $$U_f\qr{x}\qr{0} = \qr{x}\qr{0 \oplus f(x)}$$ does it. However, how do I implement this as a circuit? Please give a simple example, if you would.
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ If you want to find the circuit for some complicated function $f$, see if you can factor the function as $f=f_1 f_2$ or similarly smaller pieces. Then you can make circuits for the pieces $f_{1,2}$ using ancillas, combine that information and then uncompute to set the ancillas back to their old values. Recurse on this process as much as you need to. $\endgroup$– AHusainCommented Oct 18, 2018 at 21:45
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
0
For me the problem with understanding quantum oracles was figuring out how they work if the input is in superposition. The answer is: build the oracle so that it is a unitary which does the right thing for inputs in each of the computational basis states, and it will do the right thing for the superposition due to linearity of the unitary transformation. I don't want to write out the formulas here, you can look up a more detailed explanation here.
$\newcommand{\qr}[1]{|#1\rangle}$ Now, to the examples.
The simplest function to implement is the constant function $f(x) = 0$. Indeed, $U_0\qr{x}\qr{y} = \qr{x}\qr{y \oplus 0} = \qr{x}\qr{y}$ - that's just an identity matrix, which you can program as doing exactly nothing :-)
The constant function $f(x) = 1$ is the next easiest thing: $U_0\qr{x}\qr{y} = \qr{x}\qr{y \oplus 1}$, and all you need to do is to apply an X gate to the output qubit.
How about a function which actually depends on its input values, for example, $f(x) = x_k$ (if the k-th qubit of the input is in $\qr{1}$ state, flip the state of the output qubit)? You need to make sure that it works if $x_k = 0$ (doing nothing) and if $x_k = 1$ (flipping the state of y). This can be done by a CNOT with the k-th qubit of the input used as a control and the output qubit as a target.
You can find more complicated examples in the Quantum Katas and try to actually implement them. Writing the oracles are covered in Deutsch-Jozsa algorithm, Simon's algorithm and Grover's algorithm katas (each kata covers writing oracles used in the respective algorithm). My favorite one is probably the oracle which implements the majority function on 3 qubits.
answered Oct 18, 2018 at 21:55
$\begingroup$
$\endgroup$
2
Firstly, I would like to mention that it is more common to use $${\rm U}_f|x\rangle|0\rangle=|x\rangle|f(x)\rangle$$ instead of what you wrote down. (By the way, $0\oplus f(x)$ is simply $f(x)$.)
Now, what you want completely depends on $f$ and the domain of $x$. If for example $x$ is allowed only to be a computational basis state, $f(x)=x$ could be implemented easily with a CNOT gate: $${\rm C}_{\rm X}|0\rangle|0\rangle=|0\rangle|0\rangle,$$ $${\rm C}_{\rm X}|1\rangle|0\rangle=|1\rangle|1\rangle;$$ however if $|x\rangle$ is a general quantum state, $f(x)=x$ cannot be implemented in this form since that would violate the no-cloning theorem. In this case, you should simply read out the first qubit. This shows that sometimes (i.e. when $f$ can be represented as a unitary operator) you don't even need a second state.
answered Oct 18, 2018 at 21:30
Dyon J Don Kiwi van VreumingenDyon J Don Kiwi van Vreumingen
8151 gold badge5 silver badges14 bronze badges
-
1$\begingroup$ CNOT still works for general quantum states. It doesn't violate the no-cloning theorem because it makes an entangled copy, not an independent copy. $\endgroup$ Commented Oct 19, 2018 at 18:54
-
$\begingroup$ @AlanGeller Well, yes. The measurement probabilities for the second qubit would still be the same, so in some sense it is a copy – I guess I could be more explicit saying that there exists no unitary exactly copying a general $|x\rangle$ to the second register so as to end up with the state $|x\rangle|x\rangle$. $\endgroup$ Commented Oct 19, 2018 at 22:00
$\begingroup$
$\endgroup$
$\newcommand{\qr}[1]{|#1\rangle}$It would really depend on f. Say for instance you want to compute $f(x) = 3*x$ : $$U_f\qr{x}\qr{3}\qr{0} = \qr{x}\qr{3}\qr{3*x}$$
You will need a multiplier circuit like this one.
However, you can mimic simple operations with NOT, CNOT, Toffoli... For example, create a function which verify a set of clauses in your bits like it is done in SAT problems. It will output a bit 1 if it satisfy the set, 0 otherwise. The whole circuit will be represented by a unitary operation.
