Skip to content

Phase Kickback

Phase kickback [1,2,3] is an important and highly used primitive in quantum computing, and it deals with kicking the result of a function to the phase of a quantum state so it can be smartly manipulated with constructive and destructive interferences in order to achieve the desired result. Every quantum algortihm can be decomposed into 3 steps: 1)Encoding the data; 2) Manipulating the data; and 3) Extracting the result. The phase kickback primitive is a key step in the manipulaiton of the data that enables the extraction of the result. See the Deutch-Jozsa and Simon's algortihms for concrete examples of the applications of it.

The standard way [4] of applying a classical function \(f:\{0,1\}^n \rightarrow \{0,1\}\) on quantum states is with the oracle model: \(\begin{equation} O_f (|x \rangle_n|y \rangle_1) = |x \rangle_n|y \oplus f(x) \rangle_1 \end{equation}\) with \(|x \rangle\) and \(|y \rangle\) being the argument and target quantum states respectively, and \(\oplus\) being affition modolu \(2\), or the XOR operation. The phase kickback primitive takes the oracle \(O_f\) as an input, and performs the follwoing operation: \(\begin{equation} |x \rangle\rightarrow (-1)^{f(x)}|x \rangle \end{equation}\) This can obviously be applied on a superposition of states such that: \(\begin{equation} \sum_{i=0}^{2^n-1}\alpha_i|x_i \rangle\rightarrow (-1)^{f(x_i)}\alpha_i|x_i \rangle \end{equation}\) with \(\alpha_i\) being the amplitude of the \(|x_i \rangle\) state.

How this is happening? It's quite simple actually (hence the beuty of it), all needed is to apply the oracle \(O_f\) on the state target quantum state \(|- \rangle=\frac{1}{\sqrt{2}}|0 \rangle-\frac{1}{\sqrt{2}}|1 \rangle\) such that: \(\begin{equation} O_f|x \rangle |- \rangle = (-1)^{f(x)}|x \rangle |- \rangle \end{equation}\) and then effectively the desired transformation \(|x \rangle\rightarrow (-1)^{f(x)}|x \rangle\) is achieved.

Phase Kickback High Level

Let's see how this actually works! (Go to the Mathemtaical Description for full mathematical description)

Classiq Concepts * Within-Apply * In-Place XOR

Related Algorithms * Deutch-Jozsa Algorithm * Simon's Algorithm

NOTE

Sometimes another trick is refered as phase kickback (video 1, video 2). This is when applying a unitary \(U\) with eigensystem \(U| phi \rangle=e^{i\phi}|phi\rangle\) which is controlled by a qubit in the \(| + \rangle=\frac{1}{\sqrt{2}}|0\rangle+\frac{1}{\sqrt{2}}|1\rangle\), the phase of the eigenvalue of \(U\) is kicked-back to a relative phase in the controlled qubit: \(\begin{equation} CU| + \rangle| \phi \rangle=\frac{1}{\sqrt2}(|0\rangle| \phi \rangle + e^{i\phi}|1\rangle| \phi \rangle) = \frac{1}{\sqrt{2}}(|0\rangle+e^{i\phi}|1\rangle)| \phi \rangle \end{equation}\)

This is a good trick to know as well, but it is not what is commonly referred to Phase Kickback in the literature [1,2,3]

Guided Implementation

In Classiq as in any proper devleoping platform, it is recomended to think and design your code on the functional level in terms of functions. The above figure directs us to what functional building blocks we need to have so now we will implement them one function at a time and then connect them.

First we start with the Prepare \(| - \rangle\) building block implemented with the prepare_minus function. It is implemented by sequentially apllying the X (NOT) gate that transforms \(|0\rangle\) into \(X|0\rangle=|1\rangle\), and then applying the Hadmard H gate that takes the \(|1\rangle\) state into the desired \(H|1\rangle=| - \rangle\) state:

Phase Kickback High Level
from classiq import H, Output, QBit, X, allocate, qfunc


@qfunc
def prepare_minus(target: Output[QBit]):
    allocate(out=target, num_qubits=1)
    X(target)
    H(target)

Then we need to define the oracle function that implements \(O_f| x \rangle| target \rangle=| x \rangle |target \oplus f(x)\rangle\). We will implement it for the function \(f(x)= (x==0)\), such that the output is \(1\) only if the input \(x\) equals \(0\). That is \(\begin{equation} O_f(| x \rangle| target \rangle) = | x \rangle |target \oplus (x==0)\rangle \end{equation}\)

Phase Kickback High Level

With Classiq the XOR operation (\(\oplus\)) is impleneted intuitively with ^= :

from classiq import QNum


@qfunc
def oracle_function(target: QBit, x: QNum):
    target ^= x == 0

Now we want to combine the two building blocks for preforming the phase kickback. Notice that the we not interested in the \(| - \rangle\) state and its only purpose is for the implementation of \(| x \rangle\rightarrow (-1)^{f(x)}| x \rangle\). For such cases (that are common in quantum computing) the QMOD language offers the Within-Apply (read more ) statment. Everything we want only for the use of another specific function we apply in the Within, and we use it for the specific thing we are interested at in the Apply

Phase Kickback High Level
from classiq import within_apply


@qfunc
def oracle_phase_kickback(x: QNum):
    target = QBit("target")
    within_apply(
        compute=lambda: prepare_minus(target), action=lambda: oracle_function(target, x)
    )
Note! In the native QMOD syntax in the IDE the following would look like:
qfunc oracle_phase_kickback(x:qnum){
  target:qbit;
  within{prepare_minus(target);} apply{oracle_function(x,target);}
}
which is a bit more intuitive.

Now we are ready to apply our oracle_phase_kickback function. Because we are dealing with quantum algortihms we want to utilize the power of quantum parallelism so we will apply the oracle_phase_kickback on a superposition of numbers. Creating a superposition is commonly done with the Hadamrd transform in quantum computing, which is just applying the Hadamrd gate H on all the qubits, and it's application on the \(|0\rangle\) state is: \(\begin{equation} H^{\otimes n}|0\rangle_n = \frac{1}{\sqrt{2^n}}\sum_{i=0}^{2^n-1}| i \rangle_n \end{equation}\)

Phase Kickback High Level

Therefore our phase kickback primitive is construct of

  1. Initializing the qnum type with \(4\) qubits using the allocate function such that \(| x \rangle=|0\rangle\)
  2. Applying the Hadamrd transform on it using the hadamard_transform function such that \(| x \rangle = \frac{1}{\sqrt{2^n}}\sum_{i=0}^{2^n-1}| i \rangle_n\)
  3. Applying the Phase Kickback primitive with the oracle_phase_kickback function such that \(| x \rangle = \frac{1}{\sqrt{2^n}}\sum_{i=0}^{2^n-1}(-1)^{i==0}| i \rangle_n\)
from classiq import create_model, hadamard_transform, show, synthesize


@qfunc
def main(x: Output[QNum]):
    allocate(num_qubits=4, out=x)
    hadamard_transform(x)
    oracle_phase_kickback(x)


qmod = create_model(main)
qprog = synthesize(qmod)
show(qprog)
Opening: https://platform.classiq.io/circuit/51cc75df-75d3-4f91-ba4c-fc48e41784bc?version=0.41.0.dev39%2B79c8fd0855
Phase Kickback High Level

Now let's varify that our quantum program actually does what we expect it to do. Remember - we expect to receive a \((-)\) phase only for the state \(|0\rangle\), that is: \(\begin{equation} | x \rangle = \frac{1}{\sqrt{2^4}}(|1\rangle+| 2 \rangle+\dots +| 15 \rangle-|0\rangle) \end{equation}\) In order to check this we will use the built-in Classiq state vector simulator from the IDE:

Phase Kickback High Level

And indeed we see that only for the zero state we receive the \((-)\) phase as expected! That's really cool isn't it? Note that in the result we see bit strings of 5 bits rather than just 4 - this includes the target qubit measurment that always result 0.

To see how this phase kickback is actually implemented in practice see the Deutch-Josza example and Simon's example (TODO links)

Mathematical Description

Our starting point is the defintion \(\begin{equation} O_f (| x \rangle_n| y \rangle_1) = | x \rangle_n|y \oplus f(x)\rangle_1 \end{equation}\) for \(f:\{0,1\}^n \rightarrow \{0,1\}\).

Applying \(O_f\) on \(| x \rangle| - \rangle\) results: \(\begin{equation} O_f (| x \rangle| - \rangle) = \frac{1}{\sqrt{2}}(| x \rangle |0 \oplus f(x)\rangle - | x \rangle |1 \oplus f(x)\rangle) \end{equation}\)

The expression \(0 \oplus f(x)\) equals \(f(x)\) because \(0\oplus0=0\) and \(0\oplus1=1\).

The expression \(1\oplus f(x)\) equals \(\overline{f(x)}\) i.e. NOT \(f(x)\) since \(1\oplus1=0\) and \(1\oplus0=1\).

Therefore:

\(\begin{equation} O_f (| x \rangle| - \rangle) = | x \rangle\frac{1}{\sqrt{2}}(|f(x)\rangle - | x \rangle |\overline{f(x)}\rangle) \end{equation}\)

If \(f(x)=0\) the target state is \(\frac{1}{\sqrt{2}}(|0\rangle - | x \rangle|1\rangle) = | - \rangle = (-1)^{f(x)}| - \rangle\).

If \(f(x)=1\) the target state is \(\frac{1}{\sqrt{2}}(|1\rangle - | x \rangle|0\rangle) = -| - \rangle = = (-1)^{f(x)}| - \rangle\).

Therefore:

\(\begin{equation} O_f (| x \rangle| - \rangle) = (-1)^{f(x)}| x \rangle| - \rangle \end{equation}\)

All Code Together

Python version:

from classiq import (
    H,
    Output,
    QBit,
    QNum,
    X,
    allocate,
    create_model,
    hadamard_transform,
    qfunc,
    show,
    synthesize,
    within_apply,
    write_qmod,
)


@qfunc
def prepare_minus(target: Output[QBit]):
    allocate(out=target, num_qubits=1)
    X(target)
    H(target)


@qfunc
def oracle_function(target: QBit, x: QNum):
    target ^= x == 0


@qfunc
def oracle_phase_kickback(x: QNum):
    target = QBit("target")
    within_apply(
        compute=lambda: prepare_minus(target), action=lambda: oracle_function(target, x)
    )


@qfunc
def main(x: Output[QNum]):
    allocate(num_qubits=4, out=x)
    hadamard_transform(x)
    oracle_phase_kickback(x)


qmod = create_model(main)
qprog = synthesize(qmod)
show(qprog)

write_qmod(qmod, "phase_kickback")
Opening: https://platform.classiq.io/circuit/4915ffcd-0613-479c-b93e-14bdaa8c5d27?version=0.41.0.dev39%2B79c8fd0855

Native QMOD version:

// Phase Kickback

qfunc prepare_minus(output target:qbit){
  allocate<1>(target);
  X(target);
  H(target);
}

qfunc oracle_function(x: qnum, target: qbit){
  target ^= x==0;
}

qfunc oracle_phase_kickback(x:qnum){
  target:qbit;
  within{prepare_minus(target);} apply{oracle_function(x,target);}
}

qfunc main(output x:qnum){
  allocate<4>(x);
  hadamard_transform(x);
  oracle_phase_kickback(x);
}

Refernces

[1]: Lecture Notes on Quantum Algorithms (Andrew M. Childs)

[2]: Lecture Notes on Quantum Algorithms for Scientific Computations (Lin Lin)

[3]: Quantum Computing: Lecture Notes (Ronald de Wolf)

[4]: Quantum Computation and Quantum Information (Michael Nielsen and Isaac Chuang)