$\require{cancel} \newcommand{\Ket}[1]{\left|{#1}\right\rangle} \newcommand{\Bra}[1]{\left\langle{#1}\right|} \newcommand{\Braket}[1]{\left\langle{#1}\right\rangle} \newcommand{\Rsr}[1]{\frac{1}{\sqrt{#1}}} \newcommand{\RSR}[1]{1/\sqrt{#1}} \newcommand{\Verti}{\rvert} \newcommand{\HAT}[1]{\hat{\,#1~}} \DeclareMathOperator{\Tr}{Tr}$
Flip Bits¶
First created in August 2018
The article was motivated by the need to flip a basis state for the purpose of the Grover's Algorithm.
A circuit with no ancillary qubits are realised here with mathematical proof. (A 3-qubit version can be found in Grover's Algorithm 8-item Trial.)
Please note that the word "flip" here is loosely used to mean phase flip ($Z$), not basis state flip ($X$) as used in some other text.
Motivation¶
To "phase-flip" a basis state is to negate the sign of it. This is the core of the construction of the Grover's Algorithm.
Let $_n\Omega_w =\overbrace{ \begin{bmatrix} 1&0&\ldots&\ldots&0\\ \vdots&\ddots&\ldots&\ldots&0\\ \vdots&\vdots&-1&\ldots&0\\ \vdots&\vdots&\vdots&\ddots&0\\ 0&0&\ldots&\ldots&1\\ \end{bmatrix} }^{2^n}$ with the -1 being at position $w$, where $w\in[0,2^n-1]$.
An $n$-qubit system (representing a $2^n$ item list) will have its Grover's oracle $U_{f_w}=~_n\Omega_w$ and the diffusion operator $U_s=H^{\otimes n}~_n\Omega_0H^{\otimes n}$.
Finding $_n\Omega_w$ efficiently is crucial to the implementation of Grover's Algorithm.
The Process¶
We are trying to find $_n\Omega_w$ through mathematical induction, starting with $n=2$.
To flip one out of the 4 basis states in a 2-qubit system, there are 4 corresponding operations:
$X\otimes X=\begin{bmatrix}0&X\\X&0\end{bmatrix},~~$ $X\otimes I=\begin{bmatrix}0&I\\I&0\end{bmatrix},~~$ $I\otimes X=\begin{bmatrix}X&0\\0&X\end{bmatrix},~~$ $I\otimes I=\begin{bmatrix}I&0\\0&I\end{bmatrix}.$
Given $cZ=\begin{bmatrix}I&0\\0&Z\end{bmatrix},~~XIX=I~~\text{and}~~XZX=-Z,~~$ we have
$\begin{array}{| l | l | l | l | l | l | l | l | l | l | l | l |} \hline U_f & \text{Step 1} & \text{Step 2} & \text{Encoding}\\ \hline (X\otimes X)cZ(X\otimes X) & \begin{bmatrix}0&X\\X&0\end{bmatrix} \begin{bmatrix}I&0\\0&Z\end{bmatrix} \begin{bmatrix}0&X\\X&0\end{bmatrix} & \begin{bmatrix}XZX&0\\0&XIX\end{bmatrix} =\begin{bmatrix}-Z&0\\0&I\end{bmatrix} =\begin{bmatrix}-1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{bmatrix} & \Ket{00} \\ \hline (X\otimes I)cZ(X\otimes I) & \begin{bmatrix}0&I\\I&0\end{bmatrix} \begin{bmatrix}I&0\\0&Z\end{bmatrix} \begin{bmatrix}0&I\\I&0\end{bmatrix} & \begin{bmatrix}IZI&0\\0&III\end{bmatrix} =\begin{bmatrix}Z&0\\0&I\end{bmatrix} =\begin{bmatrix}1&0&0&0\\0&-1&0&0\\0&0&1&0\\0&0&0&1\end{bmatrix} & \Ket{01} \\ \hline (I\otimes X)cZ(I\otimes X) & \begin{bmatrix}X&0\\0&X\end{bmatrix} \begin{bmatrix}I&0\\0&Z\end{bmatrix} \begin{bmatrix}X&0\\0&X\end{bmatrix} & \begin{bmatrix}XIX&0\\0&XZX\end{bmatrix} =\begin{bmatrix}I&0\\0&-Z\end{bmatrix} =\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&-1&0\\0&0&0&1\end{bmatrix} & \Ket{10} \\ \hline (I\otimes I)cZ(I\otimes I) & \begin{bmatrix}I&0\\0&I\end{bmatrix} \begin{bmatrix}I&0\\0&Z\end{bmatrix} \begin{bmatrix}I&0\\0&I\end{bmatrix} & \begin{bmatrix}III&0\\0&IZI\end{bmatrix} =\begin{bmatrix}I&0\\0&Z\end{bmatrix} =\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&-1\end{bmatrix} & \Ket{11} \\ \hline \end{array}$
From the above, one can tell that the "flipped bit" is moving around depending on where the $X$s are. We will illustrate more in the Discussion section below.
If it is true that $_n\Omega_w=\left(^\otimes\Pi_k^n\Phi_k\right)\left(_ncZ\right)\left(^\otimes\Pi_k^n\Phi_k\right)=I-2\Ket w\Bra w= \overbrace{ \begin{bmatrix} 1&0&\ldots&\ldots&0\\ \vdots&\ddots&\ldots&\ldots&0\\ \vdots&\vdots&-1&\ldots&0\\ \vdots&\vdots&\vdots&\ddots&0\\ 0&0&\ldots&\ldots&1\\ \end{bmatrix} }^{2^n}$
with the -1 being at position $w$, where $w\in[0,2^n-1],~~\Phi_k\in[I,X]~~$ and $~_ncZ~$ is $n$-qubit-controlled-Z gate. (e.g. the Toffoli $ccZ$ is $_3cZ$.)
Let $\Psi_k^n=^\otimes\Pi_k^n\Phi_k,~~$ which "spells out" the binary representation of $w$, with $X$ corresponds to 0 and $I$ to 1.
We have $\boxed{_n\Omega_w=\Psi_k^n\left(_ncZ\right)\Psi_k^n.}$
(Note: This $X$ to 0 and $I$ to 1 convention is dictated purely by the target qubit being the LSD. If the target is the MSD, the encoding would be the reverse with $X$ to 1 and $I$ to 0. This is straight forward, as moving the target from LSD to MSD needs $X^{\otimes n}$.)
Now let us examine the $(n+1)$-qubit case, in which $w\in[0,2^{n+1}-1].$
When $w\in[0,2^n-1]~$ (the top half), we prepend $X$ as MSD and have
$_{n+1}\Omega_w =\left(X\otimes\Psi_k^n\right)\left(_{n+1}cZ\right)\left(X\otimes\Psi_k^n\right) =\begin{bmatrix}0&\Psi_k^n\\\Psi_k^n&0\end{bmatrix} \begin{bmatrix}I_{2^n}&0\\0&_ncZ\end{bmatrix} \begin{bmatrix}0&\Psi_k^n\\\Psi_k^n&0\end{bmatrix}$
$=\begin{bmatrix}\Psi_k^n\left(_ncZ\right)\Psi_k^n&0\\0&\Psi_k^nI_{2^n}\Psi_k^n\end{bmatrix} =\begin{bmatrix}_n\Omega_w&0\\0&^\otimes\Pi_k^n\left(\Phi_kI_2\Phi_k\right)\end{bmatrix} =\overbrace{\begin{bmatrix}_n\Omega_w&0\\0&I_{2^n}\end{bmatrix}}^{2^{n+1}} .$
When $w\in[2^n,2^{n+1}-1]~$ (the bottom half), we prepend $I$ as MSD and have
$_{n+1}\Omega_w =\left(I\otimes\Psi_k^n\right)\left(_{n+1}cZ\right)\left(I\otimes\Psi_k^n\right) =\begin{bmatrix}\Psi_k^n&0\\0&\Psi_k^n\end{bmatrix} \begin{bmatrix}I_{2^n}&0\\0&_ncZ\end{bmatrix} \begin{bmatrix}\Psi_k^n&0\\0&\Psi_k^n\end{bmatrix}$
$=\begin{bmatrix}\Psi_k^nI_{2^n}\Psi_k^n&0\\0&\Psi_k^n\left(_ncZ\right)\Psi_k^n\end{bmatrix} =\begin{bmatrix}^\otimes\Pi_k^n\left(\Phi_kI_2\Phi_k\right)&0\\0&_n\Omega_w\end{bmatrix} =\overbrace{\begin{bmatrix}I_{2^n}&0\\0&_n\Omega_w\end{bmatrix}}^{2^{n+1}} .$
So the "flipped bit" does fall into the proper part of the new $2^{n+1}$ dimensional matrix $_{n+1}\Omega_w$.
Therefore, $~_{n+1}\Omega_w=\Psi_k^{n+1}\left(_{n+1}cZ\right)\Psi_k^{n+1}.~~~\mathrm{QED}$
Discussion¶
As you may have rightly observed, how come the -1 is at the bottom of the $_ncZ$ matrix and by applying $X$s in the controlling qubits the -1 has moved to other places. This is straight forward mathematically but how can one visualise this "moving around"?
The puzzle arises from the misperception that the convention of diagraming the controlled qubit at the bottom has anything to do with the location of the -1.
Let us look at how multi-qubit $X$ operation works:
$X=\Ket1\Bra0+\Ket0\Bra1,$ which maps $a\Ket0$ to $a\Ket1$ and $b\Ket1$ to $b\Ket0$, or $[a,b]^T$ to $[b,a]^T$.
$X\otimes X=\Ket{00}\Bra{11}+\Ket{01}\Bra{10}+\Ket{10}\Bra{01}+\Ket{11}\Bra{00},$ which maps $[a,b,c,d]^T$ to $[d,c,b,a]^T$.
Here is the four combinations of a 2-qubit system:
| \hspace{1em}Operation\hspace{1em} | \hspace{1em}Swapping\hspace{1em} | \hspace{1em}Mapped to\hspace{1em} |
|---|---|---|
| $X\otimes X$ | $00\rightleftharpoons 11, 01\rightleftharpoons 10$ | $[d,c,b,a]^T$ |
| $X\otimes I$ | $00\rightleftharpoons 10, 01\rightleftharpoons 11$ | $[c,d,a,b]^T$ |
| $I\otimes X$ | $00\rightleftharpoons 01, 10\rightleftharpoons 11$ | $[b,a,d,c]^T$ |
| $I\otimes I$ | No swapping | $[a,b,c,d]^T$ |
So the $X$ is in fact swapping the basis states. The higher the $X$ in qubit order (closer to the MSD), the "wider" the range the swapping will get.
That effective brings that required phase shift (the -1) into the proper position. From the right, a "long range" swap to get the phase into the MSD position, followed by the second order and so on, until the last $X$ (LSD) that swaps the phase right into the even or odd position.
Code Section¶
# Initialisation
import sys
sys.path.append('../')
from qtol import *
def mark(encode, winning):
if (winning == "000"):
encode.x(q[2])
encode.x(q[1])
encode.x(q[0])
elif (winning == "001"):
encode.x(q[2])
encode.x(q[1])
encode.iden(q[0])
elif (winning == "010"):
encode.x(q[2])
encode.iden(q[1])
encode.x(q[0])
elif (winning == "011"):
encode.x(q[2])
encode.iden(q[1])
encode.iden(q[0])
elif (winning == "100"):
encode.iden(q[2])
encode.x(q[1])
encode.x(q[0])
elif (winning == "101"):
encode.iden(q[2])
encode.x(q[1])
encode.iden(q[0])
elif (winning == "110"):
encode.iden(q[2])
encode.iden(q[1])
encode.x(q[0])
elif (winning == "111"):
encode.iden(q[2])
encode.iden(q[1])
encode.iden(q[0])
return encode
# Flip-Bit-3
# To show states properly, we use the q[2]q[1]q[0] convention, having LSD on q[0].
# In other words, q[0] is controlled by all other qubits.
# X endcodes 0 and I encodes 1. e.g. xii encodes 011.
# Number of qubits
qbNum = 3
# Define the Quantum and Classical Registers
q = QuantumRegister(qbNum)
c = ClassicalRegister(qbNum)
# Preparation
prep = QuantumCircuit(q)
prep.h(q)
#prep.h(q[2])
#prep.h(q[1])
#prep.iden(q[0])
# CCX begin
ccx = QuantumCircuit(q)
ccx.ccx(q[2], q[1], q[0])
# CCZ
ccz = QuantumCircuit(q)
ccz.iden(q[2])
ccz.iden(q[1])
ccz.h(q[0])
ccz += ccx
ccz.h(q[0])
ccz.iden(q[1])
ccz.iden(q[2])
for i in range(8):
winning = str(bin(i+8))[-3:]
encode = QuantumCircuit(q)
mark(encode, winning)
qc = prep + encode + ccz + encode
show_me(qc, q, c, caption=winning + ":", normal=False, show_latex=True, show_vector=False, show_text=False)
#show_me(qc, q, c, normal=False, caption=winning + ":", show_vector=False)
encode = QuantumCircuit(q)
mark(encode, "000")
qc = encode + ccz + encode
circuit_drawer(qc)
