5.1.3 Sign oracles

Since the bit oracle UfU_{f} is a quantum operation, we can not only apply it to basis states |x1,…,xn,y⟩\left|x_{1},\dots,x_{n},y\right\rangle but also to general quantum states. Why would we like to do such a thing? Well, if we only ever ask the oracle ‘classical’ questions then there is little hope of achieving a quantum speedup! Given this motivation, let us investigate how the bit oracle UfU_{f} for an arbitrary function f:{0,1}n→{0,1}f:\{0,1\}^{n}\to\{0,1\} acts when the last register is set to |−⟩=(|0⟩−|1⟩)/2\left|-\right\rangle=(\left|0\right\rangle-\left|1\right\rangle)/\sqrt{2}. First, notice the following interesting fact:

NOT⁢|−⟩=12⁢(NOT⁢|0⟩−NOT⁢|1⟩)=12⁢(|1⟩−|0⟩)=−|−⟩.\displaystyle\mathrm{NOT}\left|-\right\rangle=\frac{1}{\sqrt{2}}\left\lparen% \mathrm{NOT}\left|0\right\rangle-\mathrm{NOT}\left|1\right\rangle\right\rparen% =\frac{1}{\sqrt{2}}\left\lparen\left|1\right\rangle-\left|0\right\rangle\right% \rparen=-\left|-\right\rangle.

That is, if we invert a qubit in state |−⟩\left|-\right\rangle then we pick up a sign. We can similarly compute how the bit oracle acts on a state of the form |x1,…,xn⟩⊗|−⟩\left|x_{1},\dots,x_{n}\right\rangle\otimes\left|-\right\rangle. By linearity, Eq. 5.5 gives us

Uf⁢(|x1,…,xn⟩⊗|−⟩)\displaystyle\quad U_{f}\left(\left|x_{1},\dots,x_{n}\right\rangle\otimes\left% |-\right\rangle\right)
=Uf⁢(12⁢|x1,…,xn,0⟩−12⁢|x1,…,xn,1⟩)\displaystyle=U_{f}\bigl{(}\frac{1}{\sqrt{2}}\left|x_{1},\dots,x_{n},0\right% \rangle-\frac{1}{\sqrt{2}}\left|x_{1},\dots,x_{n},1\right\rangle\bigr{)}
=12⁢|x1,…,xn,f⁢(x1,…,xn)⟩−12⁢|x1,…,xn,f⁢(x1,…,xn)⊕1⟩\displaystyle=\frac{1}{\sqrt{2}}\left|x_{1},\dots,x_{n},f(x_{1},\dots,x_{n})% \right\rangle-\frac{1}{\sqrt{2}}\left|x_{1},\dots,x_{n},f(x_{1},\dots,x_{n})% \oplus 1\right\rangle
=|x1,…,xn⟩⊗12⁢(|f⁢(x1,…,xn)⟩−|f⁢(x1,…,xn)⊕1⟩)\displaystyle=\left|x_{1},\dots,x_{n}\right\rangle\otimes\frac{1}{\sqrt{2}}% \bigl{(}\left|f(x_{1},\dots,x_{n})\right\rangle-\left|f(x_{1},\dots,x_{n})% \oplus 1\right\rangle\bigr{)}
=(−1)f⁢(x1,…,xn)⁢|x1,…,xn⟩⊗|−⟩.\displaystyle=(-1)^{f(x_{1},\dots,x_{n})}\left|x_{1},\dots,x_{n}\right\rangle% \otimes\left|-\right\rangle.

In other words, we end up returning the last qubit back in the state |−⟩\left|-\right\rangle, but we pick up an overall minus sign when f⁢(x1,…,xn)=1f(x_{1},\dots,x_{n})=1. Effectively, we have implemented the following quantum operation on the first nn qubits:

Of⁢|x1,…,xn⟩=(−1)f⁢(x1,…,xn)⁢|x1,…,xn⟩,O_{f}\left|x_{1},\dots,x_{n}\right\rangle=(-1)^{f(x_{1},\dots,x_{n})}\left|x_{% 1},\dots,x_{n}\right\rangle, (5.6)

for all bitstrings x1,…,xn∈{0,1}x_{1},\dots,x_{n}\in\{0,1\}. We call OfO_{f} the sign oracle for ff.

Interestingly, for a function f:{0,1}n→{0,1}f\colon\{0,1\}^{n}\to\{0,1\}, the sign oracle OfO_{f} operates on nn qubits since it stores the output in the amplitude. This is different from the bit oracle UfU_{f}, which stores the output in an additional qubit and therefore operates on n+1n+1 qubits.

At first glance, the sign oracle does not seem to do much since it only introduces an overall sign when acting on a basis state, which we know from 2.7 cannot be observed. However, when we apply it to a superposition then the sign oracle can introduce relative signs, so we can get an interesting result. For example, for n=2n=2 qubits, if we apply a sign oracle OfO_{f} to a general two-qubit state

|ψ⟩=ψ00⁢|00⟩+ψ01⁢|01⟩+ψ10⁢|10⟩+ψ11⁢|11⟩\displaystyle\left|\psi\right\rangle=\psi_{00}\left|00\right\rangle+\psi_{01}% \left|01\right\rangle+\psi_{10}\left|10\right\rangle+\psi_{11}\left|11\right\rangle

then we obtain

Of⁢|ψ⟩=(−1)f⁢(0,0)⁢ψ00⁢|00⟩+(−1)f⁢(0,1)⁢ψ01⁢|01⟩+(−1)f⁢(1,0)⁢ψ10⁢|10⟩+(−1)f⁢(1,1)⁢ψ11⁢|11⟩\displaystyle O_{f}\left|\psi\right\rangle=(-1)^{f(0,0)}\psi_{00}\left|00% \right\rangle+(-1)^{f(0,1)}\psi_{01}\left|01\right\rangle+(-1)^{f(1,0)}\psi_{1% 0}\left|10\right\rangle+(-1)^{f(1,1)}\psi_{11}\left|11\right\rangle

As it turns out, the sign oracle OfO_{f} is indeed useful and often much easier to apply in quantum algorithms than the bit oracle UfU_{f}, so from now on we will not use the bit oracle anymore.

Exercise 5.2 (Sign oracle for a one-bit function).

Recall from 5.1 that there are four functions f:{0,1}→{0,1}f:\{0,1\}\to\{0,1\} with a single input and output bit. Can you implement the sign oracle OfO_{f} for each of them in Quirky?

Solution. There are four functions: the ‘identity’ function f⁢(x)=xf(x)=x, the NOT function, the all-zeros function, and the all-ones function.
  • •
    ​

    For the identity function f⁢(x)=xf(x)=x, Eq. 5.6 reads

    Of⁢|x⟩=(−1)x⁢|x⟩,\displaystyle O_{f}\left|x\right\rangle=(-1)^{x}\left|x\right\rangle,

    so this is precisely the Z gate:

    [Uncaptioned image]

  • •
    ​

    For the NOT function f⁢(x)=NOT⁢(x)f(x)=\mathrm{NOT}(x), we want

    Of⁢|x⟩=(−1)NOT⁢(x)⁢|x⟩=NOT⁢Z⁢NOT⁢|x⟩,\displaystyle O_{f}\left|x\right\rangle=(-1)^{\mathrm{NOT}(x)}\left|x\right% \rangle=\mathrm{NOT}\,Z\,\mathrm{NOT}\left|x\right\rangle,

    which corresponds to the following sequence:

    [Uncaptioned image]

  • •
    ​

    For the all-zeros function with f⁢(0)=f⁢(1)=0f(0)=f(1)=0:

    Of⁢|x⟩=|x⟩,\displaystyle O_{f}\left|x\right\rangle=\left|x\right\rangle,

    so we do not have to do anything at all:

    [Uncaptioned image]

  • •
    ​

    For the all-ones function with f⁢(0)=f⁢(1)=1f(0)=f(1)=1:

    Of⁢|x⟩=−|x⟩,\displaystyle O_{f}\left|x\right\rangle=-\left|x\right\rangle,

    which we can achieve by combining the first two oracles in sequence:

    [Uncaptioned image]

    Indeed, the first oracle adds a minus sign if x=1x=1, while the second oracle adds a minus sign if x=0x=0, so we get a minus sign in either case:

    NOT⁢Z⁢NOT⁢Z⁢|0⟩\displaystyle\mathrm{NOT}\,Z\,\mathrm{NOT}\,Z\left|0\right\rangle =NOT⁢Z⁢NOT⁢|0⟩=−|0⟩,\displaystyle=\mathrm{NOT}\,Z\,\mathrm{NOT}\left|0\right\rangle=-\left|0\right\rangle,
    NOT⁢Z⁢NOT⁢Z⁢|1⟩\displaystyle\mathrm{NOT}\,Z\,\mathrm{NOT}\,Z\left|1\right\rangle =NOT⁢Z⁢NOT⁢(−|1⟩)=−NOT⁢Z⁢NOT⁢|1⟩=−|1⟩.\displaystyle=\mathrm{NOT}\,Z\,\mathrm{NOT}(-\left|1\right\rangle)=-\mathrm{% NOT}\,Z\,\mathrm{NOT}\left|1\right\rangle=-\left|1\right\rangle.

    In the second to last step, we used linearity to move the minus sign to the front.

Homework 5.1 (Determine the function from its sign oracle).

Consider the following two-qubit circuit (as usual, the bottom wire is the first qubit):

[Uncaptioned image]

What function f:{0,1}2→{0,1}f\colon\{0,1\}^{2}\to\{0,1\} is it the sign oracle for?

Hint: Use that H⁢NOT⁢H=ZH\,\mathrm{NOT}\,H=Z, which follows from 4.5.

Hack.

The circuit corresponds to the following two-qubit operation:

U=(I⊗H)⁢CNOT1→2⁢(I⊗H)\displaystyle U=(I\otimes H)\mathrm{CNOT}_{1\to 2}(I\otimes H)

How does this act on a two-qubit basis state?

U⁢|a,b⟩=(I⊗H)⁢CNOT1→2⁢(I⊗H)⁢|a,b⟩=(I⊗H)⁢CNOT1→2⁢(|a⟩⊗H⁢|b⟩).\displaystyle U\left|a,b\right\rangle=(I\otimes H)\mathrm{CNOT}_{1\to 2}(I% \otimes H)\left|a,b\right\rangle=(I\otimes H)\mathrm{CNOT}_{1\to 2}(\left|a% \right\rangle\otimes H\left|b\right\rangle).

If a=0a=0, the controlled-NOT operation does not invert the second qubit, so:

U⁢|0,b⟩\displaystyle U\left|0,b\right\rangle =(I⊗H)⁢CNOT1→2⁢(|0⟩⊗H⁢|b⟩)\displaystyle=(I\otimes H)\mathrm{CNOT}_{1\to 2}(\left|0\right\rangle\otimes H% \left|b\right\rangle)
=(I⊗H)⁢(|0⟩⊗H⁢|b⟩)\displaystyle=(I\otimes H)(\left|0\right\rangle\otimes H\left|b\right\rangle)
=|0⟩⊗H⁢H⁢|b⟩\displaystyle=\left|0\right\rangle\otimes H\,H\left|b\right\rangle
=|0,b⟩,\displaystyle=\left|0,b\right\rangle,

since H⁢H=IHH=I. But if a=1a=1, then the controlled-NOT operation inverts the second qubit, so:

U⁢|1,b⟩\displaystyle U\left|1,b\right\rangle =(I⊗H)⁢CNOT1→2⁢(|1⟩⊗H⁢|b⟩)\displaystyle=(I\otimes H)\mathrm{CNOT}_{1\to 2}(\left|1\right\rangle\otimes H% \left|b\right\rangle)
=(I⊗H)⁢(|1⟩⊗NOT⁢H⁢|b⟩)\displaystyle=(I\otimes H)(\left|1\right\rangle\otimes\mathrm{NOT}\,H\left|b% \right\rangle)
=|1⟩⊗H⁢NOT⁢H⁢|b⟩\displaystyle=\left|1\right\rangle\otimes H\,\mathrm{NOT}\,H\left|b\right\rangle
=|1⟩⊗Z⁢|b⟩\displaystyle=\left|1\right\rangle\otimes Z\left|b\right\rangle
=(−1)b⁢|1,b⟩\displaystyle=(-1)^{b}\left|1,b\right\rangle

(in the second to last step we used the hint). Thus:

U⁢|00⟩\displaystyle U\left|00\right\rangle =|00⟩\displaystyle=\left|00\right\rangle
U⁢|01⟩\displaystyle U\left|01\right\rangle =|01⟩\displaystyle=\left|01\right\rangle
U⁢|10⟩\displaystyle U\left|10\right\rangle =|10⟩\displaystyle=\left|10\right\rangle
U⁢|11⟩\displaystyle U\left|11\right\rangle =−|11⟩,\displaystyle=-\left|11\right\rangle,

and now we recognize that UU implements precisely the sign oracle for the AND\operatorname{AND} function.

Let us briefly summarize what we have achieved so far: Using bit oracles, we can ask a quantum computer to evaluate a function f:{0,1}n→{0,1}f\colon\{0,1\}^{n}\to\{0,1\} in exactly the same way as we would ask an ordinary computer that operates reversibly (compare Eqs. 5.4 and 5.5). This is important, because it means that we are not comparing apples and oranges when we ask how many questions to the bit oracle UfU_{f} are required to learn something about ff versus how many times one would have to evaluate ff on an ordinary computer to learn the same thing. And since we just showed that the sign oracle OfO_{f} can always be implemented using the bit oracle UfU_{f}, it makes no difference if we ask questions to the sign oracle OfO_{f} instead.