Home Algorithms Commercialization Data Science Information Theories Quantum Theories Lab Linear Algebra
<< Grovers Algorithm 4-item Trial PDF Shors Algorithm >>

$\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}$

Grover's Algorithm 8-item Trial

First created in August 2018

With reference to Grover's Algorithm 4-item Trial, let us try the method on an 8-item list, so we can extend circuit to arbitrary lists.

Ref:

  1. A fast quantum mechanical algorithm for database search

  2. Quantum Circuit Implementing Grover's Search Algorithm

Flip Bits

Both $U_f$ and $U_s$ involve flipping a basis state. Let us spend some time to illustrate all 8 combinations in the 3-qubit case.

$X\otimes X\otimes X=\begin{bmatrix}0&0&0&X\\0&0&X&0\\0&X&0&0\\X&0&0&0\end{bmatrix},~~$ $X\otimes X\otimes I=\begin{bmatrix}0&0&0&I\\0&0&I&0\\0&I&0&0\\I&0&0&0\end{bmatrix},~~$ $X\otimes I\otimes X=\begin{bmatrix}0&0&X&0\\0&0&0&X\\X&0&0&0\\0&X&0&0\end{bmatrix},~~$ $X\otimes I\otimes I=\begin{bmatrix}0&0&I&0\\0&0&0&I\\I&0&0&0\\0&I&0&0\end{bmatrix},$

$I\otimes X\otimes X=\begin{bmatrix}0&X&0&0\\X&0&0&0\\0&0&0&X\\0&0&X&0\end{bmatrix},~~$ $I\otimes X\otimes I=\begin{bmatrix}0&I&0&0\\I&0&0&0\\0&0&0&I\\0&0&I&0\end{bmatrix},~~$ $I\otimes I\otimes X=\begin{bmatrix}X&0&0&0\\0&X&0&0\\0&0&X&0\\0&0&0&X\end{bmatrix},~~$ $I\otimes I\otimes I=\begin{bmatrix}I&0&0&0\\0&I&0&0\\0&0&I&0\\0&0&0&I\end{bmatrix}.$

All things covered, given $XIX=I,~~XZX=-Z,~~ ccZ=\begin{bmatrix}I&0&0&0\\0&I&0&0\\0&0&I&0\\0&0&0&Z\end{bmatrix} ~~$:

$\begin{array}{lllr} U_f & \text{ Step 1 } & \text{ Step 2 } & \text{ Encoding } \\\hline (X\otimes X\otimes X)ccZ(X\otimes X\otimes X) & \begin{bmatrix}0&0&0&X\\0&0&X&0\\0&X&0&0\\X&0&0&0\end{bmatrix} \begin{bmatrix}I&0&0&0\\0&I&0&0\\0&0&I&0\\0&0&0&Z\end{bmatrix} \begin{bmatrix}0&0&0&X\\0&0&X&0\\0&X&0&0\\X&0&0&0\end{bmatrix} & \begin{bmatrix}-Z&0&0&0\\0&I&0&0\\0&0&I&0\\0&0&0&I\end{bmatrix} & \Ket{000} \\ (X\otimes X\otimes I)ccZ(X\otimes X\otimes I) & \begin{bmatrix}0&0&0&I\\0&0&I&0\\0&I&0&0\\I&0&0&0\end{bmatrix} \begin{bmatrix}I&0&0&0\\0&I&0&0\\0&0&I&0\\0&0&0&Z\end{bmatrix} \begin{bmatrix}0&0&0&I\\0&0&I&0\\0&I&0&0\\I&0&0&0\end{bmatrix} & \begin{bmatrix}Z&0&0&0\\0&I&0&0\\0&0&I&0\\0&0&0&I\end{bmatrix} & \Ket{001} \\ (X\otimes I\otimes X)ccZ(X\otimes I\otimes X) & \begin{bmatrix}0&0&X&0\\0&0&0&X\\X&0&0&0\\0&X&0&0\end{bmatrix} \begin{bmatrix}I&0&0&0\\0&I&0&0\\0&0&I&0\\0&0&0&Z\end{bmatrix} \begin{bmatrix}0&0&X&0\\0&0&0&X\\X&0&0&0\\0&X&0&0\end{bmatrix} & \begin{bmatrix}I&0&0&0\\0&-Z&0&0\\0&0&I&0\\0&0&0&I\end{bmatrix} & \Ket{010}\\ (X\otimes I\otimes I)ccZ(X\otimes I\otimes I) & \begin{bmatrix}0&0&I&0\\0&0&0&I\\I&0&0&0\\0&I&0&0\end{bmatrix} \begin{bmatrix}I&0&0&0\\0&I&0&0\\0&0&I&0\\0&0&0&Z\end{bmatrix} \begin{bmatrix}0&0&I&0\\0&0&0&I\\I&0&0&0\\0&I&0&0\end{bmatrix} & \begin{bmatrix}I&0&0&0\\0&Z&0&0\\0&0&I&0\\0&0&0&I\end{bmatrix} & \Ket{011} \\ (I\otimes X\otimes X)ccZ(I\otimes X\otimes X) & \begin{bmatrix}0&X&0&0\\X&0&0&0\\0&0&0&X\\0&0&X&0\end{bmatrix} \begin{bmatrix}I&0&0&0\\0&I&0&0\\0&0&I&0\\0&0&0&Z\end{bmatrix} \begin{bmatrix}0&X&0&0\\X&0&0&0\\0&0&0&X\\0&0&X&0\end{bmatrix} & \begin{bmatrix}I&0&0&0\\0&I&0&0\\0&0&-Z&0\\0&0&0&I\end{bmatrix} & \Ket{100} \\ (I\otimes X\otimes I)ccZ(I\otimes X\otimes I) & \begin{bmatrix}0&I&0&0\\I&0&0&0\\0&0&0&I\\0&0&I&0\end{bmatrix} \begin{bmatrix}I&0&0&0\\0&I&0&0\\0&0&I&0\\0&0&0&Z\end{bmatrix} \begin{bmatrix}0&I&0&0\\I&0&0&0\\0&0&0&I\\0&0&I&0\end{bmatrix} & \begin{bmatrix}I&0&0&0\\0&I&0&0\\0&0&Z&0\\0&0&0&I\end{bmatrix} & \Ket{101} \\ (I\otimes I\otimes X)ccZ(I\otimes I\otimes X) & \begin{bmatrix}X&0&0&0\\0&X&0&0\\0&0&X&0\\0&0&0&X\end{bmatrix} \begin{bmatrix}I&0&0&0\\0&I&0&0\\0&0&I&0\\0&0&0&Z\end{bmatrix} \begin{bmatrix}X&0&0&0\\0&X&0&0\\0&0&X&0\\0&0&0&X\end{bmatrix} & \begin{bmatrix}I&0&0&0\\0&I&0&0\\0&0&I&0\\0&0&0&-Z\end{bmatrix} & \Ket{110} \\ (I\otimes I\otimes I)ccZ(I\otimes I\otimes I) & \begin{bmatrix}I&0&0&0\\0&I&0&0\\0&0&I&0\\0&0&0&I\end{bmatrix} \begin{bmatrix}I&0&0&0\\0&I&0&0\\0&0&I&0\\0&0&0&Z\end{bmatrix} \begin{bmatrix}I&0&0&0\\0&I&0&0\\0&0&I&0\\0&0&0&I\end{bmatrix} & \begin{bmatrix}I&0&0&0\\0&I&0&0\\0&0&I&0\\0&0&0&Z\end{bmatrix} & \Ket{111} \end{array}$

From the above, one can tell that the "flipped bit" is moving around depending on where the $X$s are, and there are 8 combinations.

By mathematical induction, one can prove that this applies to all $n$-qubit cases.

Code Section

In [2]:
# Initialisation

import sys
sys.path.append('../')
from qtol import *
In [3]:
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
In [8]:
# Oracle 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, c)
prep.h(q[2])
prep.h(q[1])
prep.iden(q[0])

# CCX begin
ccx = QuantumCircuit(q, c)
ccx.h(q[0])

ccx.cx(q[1], q[0])
ccx.tdg(q[0])
ccx.cx(q[2], q[0])
ccx.t(q[0])

ccx.cx(q[1], q[0])
ccx.tdg(q[0])
ccx.cx(q[2], q[0])
ccx.t(q[0])

ccx.h(q[0])

# Finalisation
ccx.t(q[1])
ccx.cx(q[2], q[1])
ccx.tdg(q[1])
ccx.t(q[2])
ccx.cx(q[2], q[1])
# CCX end


# CCZ
ccz = QuantumCircuit(q, c)
ccz.h(q[0])
ccz += ccx
ccz.h(q[0])


# Dump point
#inp_ccz = QuantumCircuit(q, c)
#inp_ccz.h(q[2])
#inp_ccz.h(q[1])
#inp_ccz.h(q[0])
#qc = inp_ccz + ccz
#show_me(qc, q, c, show_latex=True, show_histogram=True)
#circuit_drawer(qc)

# U_s and Iteration

u_s = QuantumCircuit(q, c)
u_s.h(q)
u_s.x(q)
u_s += ccz
u_s.x(q)
u_s.h(q)

# Equivalent u_s design with less gates (but not as neat)
#u_s.h(q[1])
#u_s.x(q[1])
#u_s.z(q[0])
#u_s.cx(q[1], q[0])
#u_s.z(q[0])
#u_s.x(q[1])
#u_s.h(q[1])

iters = 2
winning = "011"

encode = QuantumCircuit(q, c)
mark(encode, winning)
u_f = encode + ccz + encode
# Dump point
#show_me(prep + u_f, q, c, show_latex=True)
#circuit_drawer(prep + u_f)

qc = prep
# Iteration
for i in range(iters):
    qc += u_f + u_s

show_me(qc, q, c, show_latex=True, show_histogram=True)
circuit_drawer(qc)

Raw vector:   [ 0.25-0.j -0.25+0.j  0.25-0.j  0.75-0.j  0.25-0.j -0.25+0.j  0.25-0.j
 -0.25+0.j]
Normalised:   [ 0.25+0.j -0.25+0.j  0.25+0.j  0.75+0.j  0.25+0.j -0.25+0.j  0.25+0.j
 -0.25+0.j]
Text form:    +0.25|000>-0.25|001>+0.25|010>+0.75|011>+0.25|100>-0.25|101>+0.25|110>-0.25|111>
$$0.25\Ket{000}-0.25\Ket{001}+0.25\Ket{010}+0.75\Ket{011}+0.25\Ket{100}-0.25\Ket{101}+0.25\Ket{110}-0.25\Ket{111}$$ 




























Out[8]:





















    

  

  
 

  

    

      

        << Grovers Algorithm 4-item Trial
        Top
        Shors Algorithm >>