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 (\ket{x}_n\ket{y}_1) = \ket{x}_n\ket{y \oplus f(x)}_1 \end{equation}$ with $\ket{x}$ and $\ket{y}$ 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} \ket{x}\rightarrow (-1)^{f(x)}\ket{x} \end{equation}$ This can obviously be applied on a superposition of states such that: $\begin{equation} \sum_{i=0}^{2^n-1}\alpha_i\ket{x_i}\rightarrow (-1)^{f(x_i)}\alpha_i\ket{x_i} \end{equation}$ with $\alpha_i$ being the amplitude of the $\ket{x_i}$ 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 $\ket{-}=\frac{1}{\sqrt{2}}\ket{0}-\frac{1}{\sqrt{2}}\ket{1}$ such that: $\begin{equation} O_f\ket{x}\ket{-} = (-1)^{f(x)}\ket{x}\ket{-} \end{equation}$ and then effectively the desired transformation $\ket{x}\rightarrow (-1)^{f(x)}\ket{x}$ is achieved.
Let's see how this actually works! (Go to the Mathemtaical Description for full mathematical description)
Classiq Concepts
Related Algorithms
NOTE
Sometimes another trick is refered as phase kickback (video 1, video 2). This is when applying a unitary $U$ with eigensystem $U\ket{phi}=e^{i\phi}\ket{phi}$ which is controlled by a qubit in the $\ket{+}=\frac{1}{\sqrt{2}}\ket{0}+\frac{1}{\sqrt{2}}\ket{1}$, the phase of the eigenvalue of $U$ is kicked-back to a relative phase in the controlled qubit: $\begin{equation} CU\ket{+}\ket{\phi}=\frac{1}{\sqrt2}(\ket{0}\ket{\phi} + e^{i\phi}\ket{1}\ket{\phi}) = \frac{1}{\sqrt{2}}(\ket{0}+e^{i\phi}\ket{1})\ket{\phi} \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 $\ket{-}$ building block implemented with the prepare_minus
function. It is implemented by sequentially apllying the X
(NOT) gate that transforms $\ket{0}$ into $X\ket{0}=\ket{1}$, and then applying the Hadmard H
gate that takes the $\ket{1}$ state into the desired $H\ket{1}=\ket{-}$ state:
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\ket{x}\ket{target}=\ket{x}\ket{target \oplus f(x)}$. 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(\ket{x}\ket{target}) = \ket{x}\ket{target \oplus (x==0)} \end{equation}$
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 intrested in the $\ket{-}$ state and its only purpose is for the implementation of $\ket{x}\rightarrow (-1)^{f(x)}\ket{x}$. 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 intrested at in the Apply
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 $\ket{0}$ state is:
$\begin{equation}
H^{\otimes n}\ket{0}_n = \frac{1}{\sqrt{2^n}}\sum_{i=0}^{2^n-1}\ket{i}_n
\end{equation}$
Therefore our phase kickback primitive is construct of
- Initializing the
qnum
type with $4$ qubits using theallocate
function such that $\ket{x}=\ket{0}$ - Applying the Hadamrd transform on it using the
hadamard_transform
function such that $\ket{x} = \frac{1}{\sqrt{2^n}}\sum_{i=0}^{2^n-1}\ket{i}_n$ - Applying the Phase Kickback primitive with the
oracle_phase_kickback
function such that $\ket{x} = \frac{1}{\sqrt{2^n}}\sum_{i=0}^{2^n-1}(-1)^{i==0}\ket{i}_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/0f80f1fc-4f69-4a5c-8561-d410ac4c694a?version=0.38.0
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 $\ket{0}$, that is: $\begin{equation} \ket{x} = \frac{1}{\sqrt{2^4}}(\ket{1}+\ket{2}+\dots +\ket{15}-\ket{0}) \end{equation}$ In order to check this we will use the built-in Classiq state vector simulator from the IDE:
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 (\ket{x}_n\ket{y}_1) = \ket{x}_n\ket{y \oplus f(x)}_1 \end{equation}$ for $f:\{0,1\}^n \rightarrow \{0,1\}$.
Applying $O_f$ on $\ket{x}\ket{-}$ results: $\begin{equation} O_f (\ket{x}\ket{-}) = \frac{1}{\sqrt{2}}(\ket{x}\ket{0 \oplus f(x)} - \ket{x}\ket{1 \oplus f(x)}) \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 (\ket{x}\ket{-}) = \ket{x}\frac{1}{\sqrt{2}}(\ket{f(x)} - \ket{x}\ket{\overline{f(x)}}) \end{equation}$
If $f(x)=0$ the target state is $\frac{1}{\sqrt{2}}(\ket{0} - \ket{x}\ket{1}) = \ket{-} = (-1)^{f(x)}\ket{-}$.
If $f(x)=1$ the target state is $\frac{1}{\sqrt{2}}(\ket{1} - \ket{x}\ket{0}) = -\ket{-} = = (-1)^{f(x)}\ket{-}$.
Therefore:
$\begin{equation} O_f (\ket{x}\ket{-}) = (-1)^{f(x)}\ket{x}\ket{-} \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/2a392973-c7a9-4538-ad48-f6e724f9f47c?version=0.38.0
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);
}