Skip to content

Phase Kickback

View on GitHub Experiment in the IDE

Phase kickback [1,2,3] is an important and highly used primitive in quantum computing. 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 to achieve the desired result. Every quantum algortihm can be decomposed into these steps: 1) Encoding the data; 2) Manipulating the data; and 3) Extracting the result. The phase kickback primitive is a key step in the manipulation of the data that enables extracting the result. See the Deutsch-Jozsa and Simon's algorithms for concrete examples.

The standard way [4] to apply 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\) as the argument and target quantum states, respectively, and \(\oplus\) as the addition modolu \(2\) or the XOR operation. The phase kickback primitive takes the oracle \(O_f\) as input, and performs this operation: \(\begin{equation} |x \rangle\rightarrow (-1)^{f(x)}|x \rangle \end{equation}\) This can be applied on a superposition of state: \(\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\) as the amplitude of the \(|x_i \rangle\) state.

How does this happen? Its beauty lies in its simplicity: applying the oracle \(O_f\) to the state target quantum state \(|- \rangle=\frac{1}{\sqrt{2}}|0 \rangle-\frac{1}{\sqrt{2}}|1 \rangle\): \(\begin{equation} O_f|x \rangle |- \rangle = (-1)^{f(x)}|x \rangle |- \rangle \end{equation}\) then effectively achieving the desired transformation \(|x \rangle\rightarrow (-1)^{f(x)}|x \rangle\).

Phase Kickback High Level

See full details in the mathematical description.

Classiq Concepts * within-apply * in-place XOR

Related Algorithms * Deutsch-Jozsa algorithm * Simon's algorithm

NOTE

Another trick is phase kickback (video 1, video 2). A unitary \(U\) is applied to an 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\), and 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 useful trick is not the same as the Phase Kickback described in the literature [1,2,3]

.

Guided Implementation

When using the Classiq system (as for any development platform), it is recommended to design your code at the functional level in terms of functions. The above figure indicates which functional building blocks you need, so you can now implement them, one function at a time, and then connect them.

Start with the Prepare \(| - \rangle\) building block using the prepare_minus function. It is implemented by sequentially applying the X (NOT) gate that transforms \(|0\rangle\) into \(X|0\rangle=|1\rangle\), and then applying the Hadamard 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)

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

Now, define the oracle function that implements \(O_f| x \rangle| target \rangle=| x \rangle |target \oplus f(x)\rangle\) for the function \(f(x)= (x==0)\), such that the output is \(1\) only if the input \(x\) equals \(0\). \(\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 implemented intuitively with ^= :

from classiq import QNum


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

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

Combine the two building blocks for performing the phase kickback. You are not interested in the \(| - \rangle\) state as its only purpose is to implement \(| 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 ) statement. Apply everything intended for use by another specific function in the within, and use it for the specific thing in the apply

Phase Kickback High Level 
from classiq import within_apply


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

qfunc oracle_phase_kickback(x: qnum) {
  target: qbit;
  within {
    prepare_minus(target);
  } apply {
    oracle_function(target, x);
  }
}
Note! This is how the native Qmod syntax in the IDE looks: 
qfunc oracle_phase_kickback(x:qnum){
  target:qbit;
  within{prepare_minus(target);} apply{oracle_function(x,target);}
}
which is more intuitive.

Now you can use the oracle_phase_kickback function. To utilize the power of quantum parallelism, apply the oracle_phase_kickback on a superposition of numbers. Creating a superposition is commonly done with the Hadamard transform in quantum computing, which means applying the Hadamard gate H on all the qubits. Its application on the \(|0\rangle\) state: \(\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, the phase kickback primitive is constructed of this:

  1. Initializing the qnum type with \(4\) qubits using the allocate function such that \(| x \rangle=|0\rangle\).
  2. Applying the Hadamard transform 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

qfunc main(output x: qnum) {
  allocate(4, x);
  hadamard_transform(x);
  oracle_phase_kickback(x);
}
Phase Kickback High Level

Verify that the quantum program actually operates as expected; receiving 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}\) To check, use the built-in Classiq state vector simulator from the IDE:

Phase Kickback High Level

Indeed, see that you receive the \((-)\) phase only for the zero state, as expected. The result shows bit strings of five bits rather than just four. This includes the target qubit measurement that always results in 0.

To see how this phase kickback is actually implemented in practice see the Deutsch-Josza example and Simon's example.

Mathematical Description

The starting point is the definition \(\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 in this: \(\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 - |\overline{f(x)}\rangle). \end{equation}\)

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

If \(f(x)=1\) the target state is \(\frac{1}{\sqrt{2}}(|1\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 the 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(
        within=lambda: prepare_minus(target), apply=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

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

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

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

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

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);
}

References

[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)