See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/342131364

Grover's Algorithm

Experiment Findings · July 2018

DOI: 10.13140/RG.2.2.30860.95366

CITATIONS READS
0 3,513

2 authors:

Akanksha Singhal Arko Chatterjee

Manipal University Jaipur Shiv Nadar University
1 PUBLICATION 0 CITATIONS 1 PUBLICATION 0 CITATIONS

SEE PROFILE SEE PROFILE

All content following this page was uploaded by Akanksha Singhal on 12 June 2020.

The user has requested enhancement of the downloaded file.

 Grover’s Algorithm

1
Akanksha Singhal, Arko Chatterjee

July 27, 2018

1 Internship Report on Grover’s Algorithm

Contents

Contents 1
0.1 Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
0.2 Quantum Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
0.2.1 Quantum Gates[7] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
0.2.1.1 Hadamard gate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
0.2.1.2 Pauli-X gate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
0.2.1.3 Pauli-Z gate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
0.2.1.4 S gate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
0.2.1.5 T gate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
0.2.1.6 S † gate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
0.2.1.7 T † gate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
0.2.1.8 Contolled Not gate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
0.2.2 Implementaion of classical gates in quantum . . . . . . . . . . . . . . . . . . . . . . 7
0.3 Introduction to Grover’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
0.3.1 Stages of Grover’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
0.3.2 Potential of Grover’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
0.3.2.1 Threat to AES symmetric block cipher . . . . . . . . . . . . . . . . . . . . 11
0.3.3 Optimal No. of Iterations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
0.3.4 Gate Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
0.3.5 Applicability and Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
0.4 Literature Survey . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
0.5 Our Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
0.6 IBM Platforms and Simulators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
0.7 Other Simulators and their Pros and Cons . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
0.8 Implementation of Grover’s Algorithm on IBM Simulator . . . . . . . . . . . . . . . . . . . 18
0.8.1 2 Qubit Implementation (IBM QX Simulator) . . . . . . . . . . . . . . . . . . . . . 18
0.8.2 3 Qubit Implementation (IBM QX Simulator) . . . . . . . . . . . . . . . . . . . . . 18
0.8.3 5 Qubit Implementation (IBM QX Simulator) . . . . . . . . . . . . . . . . . . . . . 18
0.8.4 Basic Information about the 3 Qubit Grover’s Search . . . . . . . . . . . . . . . . . 18
0.8.4.1 Device: Simulator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
0.9 3 Qubit Grover’s Search on IBM QX4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
0.9.1 3 Qubit Grover’s Search Implemented For IBM QX4 architecture . . . . . . . . . . 20
0.9.1.1 Normal Implementation of the 2nd Tofolli Gate . . . . . . . . . . . . . 20
0.9.1.2 Implementation of 2nd Tofolli gate for IBM QX4 . . . . . . . . . . . . 20
0.9.1.3 Device: Simulator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
0.9.1.4 Device: IBM QX4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
0.9.2 Optimized Approach for 3 Qubit Grover’s Search
Implemented for IBM QX4 Architecture . . . . . . . . . . . . . . . . . . . . . . . . 22
0.9.3 Working of C-Nots in IBM QX4 Architecture (IBM Q5 Tenerife)[20] . . . . . . . . . 22

1
 0.9.3.1 Direction of 2 Qubit gates . . . . . . . . . . . . . . . . . . . . . . . . 23
0.9.3.2 Exceptions to the rule of high frequency control/low frequency target 24
0.10 Results obtained for 3 Qubit Grover’s Search on
IBM Platform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
0.11 Back of Envelope Error Analysis of IBM QX4 Device for the 3 Qubit Grover’s Search Circuit 25
0.12 Implementing 16 Qubits Grover’s Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
0.12.1 Circuit diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
0.12.2 Creating larger CNOTs using toffoli gates [15] . . . . . . . . . . . . . . . . . . . . . . 29
0.12.3 The Oracle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
0.12.4 The Diffusion Operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
0.12.5 Implementation of 16 Qubits Grover’s search on Microsoft’s LIQUi |i simulator . . 35
0.12.5.1 Result on compiling and rendering the circuit . . . . . . . . . . . . . . . . 35
0.12.5.2 Result on optimizing the circuit . . . . . . . . . . . . . . . . . . . . . . . 38
0.12.6 Implementation of 16 Qubits Grover’s search on Microsoft’s Quantum Development
Kit (QDK) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
0.12.7 Implementation on Quirk quantum simulator . . . . . . . . . . . . . . . . . . . . . . 41
0.12.7.1 Grover gate : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
0.12.7.2 Circuit diagram : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
0.12.7.3 Result : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
0.13 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
0.14 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
.1 Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
.1.1 Proof of Optimal No. of Iterations . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
.1.2 Derivation of angle θ between uniform superposition |si and component of uniform
superposition |s0 i normal to |x∗ i . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
.1.3 Proof of Gate Complexity [22] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
.1.4 QASM Code for 3 qubit Grover’s Algortitm . . . . . . . . . . . . . . . . . . . . . . 51
.1.4.1 QASM Code for Basic 3 Qubit Grover’s Algorithm in IBM Simulator . . . 51
.1.4.2 QASM Code for Optimized 3 Qubit Grover’s Algorithm in IBM Simulator 52
.1.5 Code for implementing 16 qubit Grover’s search in Microsoft’s LIQUi |i simulator . 53
.1.5.1 Oracle function: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
.1.5.2 Diffusion function: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
.1.5.3 Function to optimize and compile the circuit: . . . . . . . . . . . . . . . . 58
.1.6 Code for implementing 16 qubits Grover’s search in Microsoft’s Quantum Develop-
ment Kit (QDK) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
.1.6.1 Oracle operation: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
.1.6.2 Diffusion operation: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
.1.6.3 Set operation: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
.1.6.4 Search operation: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
.1.6.5 C# Driver class: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

2
0.1 Abstract
Limited connectivity of qubits and hardware fidelity poses a challenge to implement large quantum algo-
rithms on actual devices .This paper is targeted to run 3 qubit Grover’s search on IBM QX4 platform and
compare its results by implementing the same circuit sequence on the simulator offered on IBM Quantum
experience i.e. IBM Q QASM Simulator. In this paper we have studied the IBM Q 5 Tenerife [ibmqx4] ar-
chitecture i.e. arrangement and connectivity of qubits and modified the circuit for 3 Qubit Grover’s Search
so as to successfully run it on the hardware. In this paper we have first discussed the naı̈ve approach to
design a circuit similar to the theoretical one to implement the algorithm by employing few swap gates.
Later we try to design modified circuits implementing the same logic with minimum number of swap gates
by reducing the number of gate stages as much as possible to reduce the errors due to hardware and en-
tanglement of qubits. We have also implemented 16 qubit Grover’s Search on well known simulators such
as Microsoft’s LIQUID, Microsoft’s Quantum Development Kit and Quirk: Quantum Circuit Simulator
presented the approach to implement the search and shared the experience along with the comparision of
the final results on these simulators in terms of accuracy and time required to execute them.

3
0.2 Quantum Computing
Quantum computing is computing using quantum-mechanical phenomena, such as superposition and en-
tanglement.

Superposition : Superposition is essentially the ability of a quantum system to be in multiple

states at the same time

Entanglement : Entanglement is an extremely strong correlation that exists between quantum

particles, such that observing one of two entangled qubits causes it to behave randomly, but tells the
observer exactly how the other qubit would act if observed in a similar manner, even if separated by great
distances.

0.2.1 Quantum Gates[7]

0.2.1.1 Hadamard gate

Figure 1: Hadamard gate

The hadamard gate is used to create an uniform superposition of the input states. The Hadamard gate
|0i + |1i |0i − |1i
acts on a single qubit. It maps the basis state |0i to √ and |1i to √ , which means that a
2 2
measurement will have equal probabilities to become 1 or 0. It is represented by the matrix:
 
1 1 1
H=√
2 1 −1

0.2.1.2 Pauli-X gate

Figure 2: X gate

X gate is known as a “bit-flip”, since it flips the 0 to 1 and vice versa. This is similar to a classical NOT
gate. It is also known as an Xrotation, since it rotates the state by π radians around the Xaxis. It is
represented by the Pauli matrix:  
0 1
X=
1 0

0.2.1.3 Pauli-Z gate

Figure 3: Z gate

4
The Pauli-Z gate acts on a single qubit. It equates to a rotation around the Z-axis of the Bloch sphere π
radians. It leaves the basis state |0i unchanged and maps |1i to −|1i. Due to this nature, it is sometimes
called phase-flip. It is represented by the Pauli Z matrix:
 
1 0
Z=
0 −1

0.2.1.4 S gate

Figure 4: S gate

S gate is a rotation of π/2 around Z. It is represented by the matrix:

 
1 0
S=
0 i

0.2.1.5 T gate

Figure 5: T gate

S gate is a rotation of π/4 around Z. It is represented by the matrix:

 
1 0
S=
0 eiπ/4

0.2.1.6 S † gate

Figure 6: S † gate

S † gate is the inverse of S and is a rotation of −π/2 around Z.

0.2.1.7 T † gate

Figure 7: T † gate

T † is the inverse of T and is a rotation of −π/4 around Z.

5
0.2.1.8 Contolled Not gate

Figure 8: CNOT gate

[24]

The CNOT gate’s action on classical basis states is to flip (apply a NOT or X gate to) the target qubit
only if the control qubit is |1i; otherwise it does nothing.

6
0.2.2 Implementaion of classical gates in quantum
1. Classical AND Gate
In digital electronics, the AND gate outputs true only when both the inputs are true. In quantum
computing, AND gate can be implemented using toffoli gate.

Figure 9: Quantum implementation of classical AND

An uniform superposition of all the four states { 00, 01, 10, 11} is prepared. The result shows that
the output (most significant bit) is true only if both the inputs are true.

Figure 10: Output

2. Classical OR Gate
The OR gate outputs true if at least one of the inputs is true.

Figure 11: Quantum implementation of classical OR

It is implemented using toffoli gate based on De Morgan’s law ( x.y = x + y ). The result shows
that the output bit (most significant bit) is true if at least one of the inputs is true.

7
 Figure 12: Output

3. Classical XOR Gate

The XOR gate (Exclusive-OR gate) is a digital logic gate that gives a true output when the number
of true inputs is odd.

Figure 13: Quantum implementation of classical XOR

The result shows that, the output bit (most significant bit) is true only for the inputs { 01, 10 }.

Figure 14: Output

8
0.3 Introduction to Grover’s Algorithm
• Grover’s algorithm is a quantum algorithm that solves the problem of unstructured search.

• It finds with high probability the unique input to a black box function that produces a particular
output value, using just
√
• O ( N ) evaluations of the function, where N is the size of the function’ domain.

• By comparison, a classical search algorithm will get the correct answer after an average of N/2 queries
of the oracle.

• It was devised by Lov Grover in 1996.

0.3.1 Stages of Grover’s Algorithm

Figure 15: Initialization, oracle, amplification, and measurement

Step I: Initialization
PN −1
Uniform Superposition |si = √1 |xi
N x=0

Figure 16: Initialization

Step II: Oracle

The oracle stage marks the solution(s) by flipping the sign of that state’s amplitude.

Black Box Function

f (x∗ ) = 1
f (x) = 0

9
 Oracle Function
Uf |xi = (−1)f (x) |xi

Figure 17: Oracle

Step III: Amplification

The amplification stage performs a reflection about the mean, thus increasing the amplitude of the
marked state.
b = 2|sihs| − Ib
Diffusion Operation D

Figure 18: Diffusion Operation

Step IV: Measurement

Finally, the algorithm output is measured.

10
0.3.2 Potential of Grover’s Algorithm
0.3.2.1 Threat to AES symmetric block cipher
Grover’s algorithm could brute-force a 128-bit symmetric cryptographic key in roughly 264 iterations, or a
256-bit key in roughly 2128 iterations. As a result, it is sometimes suggested that symmetric key lengths
be doubled to protect against future quantum attacks. Hence Grover’s Search can be used to accelerate
brute-force attacks on symmetric block ciphers like AES. However, it does not lead to a complete break
but roughly halves the bit-security level of symmetric algorithms. Hence, the key length of algorithms with
a 128-bit key and thus 128-bit security has to be doubled (moving to AES-256).
Post-quantum cryptography (PQC) refers to new cryptographic algorithms executed on classical computers
that are expected to be efficiently secured against attackers using quantum computers. In contrast, quan-
tum cryptography (QC) or more specifically quantum key distribution (QKD) uses properties of quantum
mechanics to establish a secret key between two parties. This secret key can then be used to encrypt bulk
data using classic symmetric ciphers like AES.
Grover’s algorithm can also be used for estimating the mean and median of a set of numbers, and for
solving the collision problem.

0.3.3 Optimal No. of Iterations

√
Optimal No. of Iterations = π4 N
{ for proof refer to Appendix .1.1. } Classically one might think that applying more Grover Iterations will
better the chance of success. This is not the case.
“the probability of success does√not increase monotonically with the number of iterations.” Performing
half that number of iterations, π8 N , will give about a 50/50 chance of success. However, doing twice that
√
number of iterations, π2 N , decreases the probability to measure the correct solution to a near negligible
amount, close to 1

0.3.4 Gate Complexity

√
The number of gates applied will be in the order of O( N logN ) for large values of N.
For proof refer to Appendix .1.2.

0.3.5 Applicability and Limitations

When applications of Grover’s algorithm are considered, it should be emphasized that the database is
not represented explicitly. Instead, an oracle is invoked to evaluate an item by its index. Reading a full
database item by item and converting it into such a representation may take a lot longer than Grover’s
search. To account for such effects, Grover’s algorithm can be viewed as solving an equation or satisfying
a constraint. In such applications, the oracle is a way to check the constraint and is not related to the
search algorithm. This separation usually prevents algorithmic optimizations, whereas conventional search
algorithms often rely on such optimizations and avoid exhaustive search

11
0.4 Literature Survey
(1996) A fast quantum mechanical algorithm on the effciency of any possible quantum database
for database search searching algorithm is provided and the paper shows
Lov K. Grover, 3C-404A, Bell Labs, 600 Mountain Avenue, that Grover’s algorithm nearly comes within a factor
Murray Hill NJ 07974, lkgrover@bell-labs.com 2 of being optimal in terms of the number of probes
This is the main paper by Lov K. Grover, which required in the table.
described the Quantum search algorithm.In the pa- (1998) Experimental Implementation of
per,it is stated that, in an unsorted database of Fast Quantum Searching [3]
phone numbers, In order to find someone’s phone Chuang, Isaac L and Gershenfeld, Neil and Kubinec, Mark
number with a probability of 1/2 , any classical al- This paper first discusses the problems with
gorithm (whether deterministic or probabilistic) will Quantum computing such as coherence and provides
need to look at a minimum of N/2 names. whereas, the solutions: 1. Quantum error correction can be
using Quantum search, √ the desired phone number used with imperfect computers. 2. Computing with
can be obtained in only N steps. mixed state ensembles rather than isolated systems
(1996) Strengths and Weaknesses of Quan- in the pure state. These ideas have been applied
tum Computing [1] in the first experimental realization of a significant
Charles H. Bennett ,Ethan Bernstein, Gilles Brassard quantum search algorithm, using nuclear magnetic
This paper addresses the question of whether all of resonance (NMR) techniques to perform Grover’s
NP can be efficiently solved in quantum polynomial search algorithm. The coherence times were mea-
time by a quantum computer, proving that rela- sured to be T1 = 20 and T2 = 0.4 sec for the pro-
tive to an oracle chosen uniformly at random, with ton, and T1 = 21 sec and T2 = 0.3 sec for the carbon
probability 1, the class NP cannot be solved on a (the large ratio is due to C-Cl relaxation), and the
quantum Turing machine in time o(2n/2 ). We also coupling was measured to be J = 215 Hz. Grover
show that relative to a permutation oracle chosen search was perform to get the state x0 = 3 (out of
uniformly at random, with probability 1, the class the states 0,1,2 for N = 4) The resulting density ma-
NP ∩ co–NP cannot be solved on a quantum Turing trix of the experiment clearly revealed the |1i state
machine in time o(2n/3 ).In the end,this paper states corresponding to x0 = 3.
that the former bound is tight since recent work of (2000) Implementation of a three-
Lov K. Grover shows how to accept the class NP rel- quantum-bit search algorithm [5]
ative to any oracle on a quantum computer in time Vandersypen, Lieven MK and Steffen, Matthias and Sher-
O(2n/2 ). wood, Mark H and Yannoni, Costantino S and Breyta, Gre-
(1996) Tight bounds on quantum search- gory and Chuang, Isaac L
ing [2] This paper reports the experimental implemen-
Boyer, Michel and Brassard, Gilles and Hoyer, Peter and tation of Grover’s quantum search algorithm on a
Tapp, Alain quantum computer with three quantum bits. The
This paper provides a tight analysis of Grover’s computer consists of molecules of Clabeled CHFBr2,
recent algorithm for quantum database searching. It in which the three weakly coupled spin-1/2 nuclei be-
gives a simple closed-form formula for the probabil- have as the bits and are initialized, manipulated, and
ity of success after any given number of iterations of read out using magnetic resonance techniques. This
the algorithm. Furthermore, the paper analyses the quantum computation is made possible by the intro-
behaviour of the algorithm when the element to be duction of two techniques which significantly reduce
found appears more than once in the table and pro- the complexity of the experiment and by the surpris-
vides a new algorithm to find such an element even ing degree of cancellation of systematic errors which
when the number of solutions is not known ahead have previously limited the total possible number of
of time. Using techniques from Shor’s quantum fac- quantum gates. The first method to reduce the num-
toring algorithm in addition to Grover’s approach, ber of one- and two spin gates used to realize any
the paper introduces a new technique for approxi- given n-qubit unitary operation starts with a library
mate quantum counting, which allows to estimate of efficient implementations for often-used building
the number of solutions. Finally a lower bound blocks. The second method to reduce the complex-

12
ity concerns the initialization of the qubits to the • Set l = 0.
ground state, generally the first step in quantum al- • Repeat until there is only a single span-
gorithms. ning tree (i.e., k = 1).
(2002) Implementation of quantum search
– Increment l.
algorithm using classical Fourier optics [6]
Bhattacharya, N and van den Heuvell, HB van Linden and
– Find edges e1,e2,...,ek satisfying that
Spreeuw, RJC
ej is a minimum weight edge leaving
This paper reports on an experiment on Grover’s Tj. Interrupt when thep total number
quantum search algorithm, showing that classical of queries is (l + 2)c (km) for some
waves can search an N-item database as efficiently appropriate constant c.
as quantum mechanics can. The transverse beam – Add the edges e’ j to the trees, merg-
profile of a short laser pulse is processed iteratively ing them into larger trees.
as the pulse bounces back and forth between two • Return the spanning tree T1.
mirrors. We directly√ observe the sought item be-
ing found in ∼ N iterations, in the form of a 3. Connectivity:
growing intensity peak on this profile. The pa- A special case of Minimum Spanning Tree
per also described the problem with using classical when all edge weights are equal, is Graph Con-
waves: lack of quantum entanglement. Although the nectivity. The input is an undirected graph
lack of quantum entanglement limits the size of the and the output is a spanning tree, provided
database, the results of this paper, show that entan- the graph is connected
glement is neither necessary for the algorithm itself, (2005) Experimental One-Way Quantum
nor for its efficiency. Computing [9]
(2004) Quantum query complexity of some P.Walther, K.J.Resch, T.Rudolph, E.Schenck,*,
graph problems [10] H.Weinfurter, V.Vedral, M.Aspelmeyer and A.Zeilinger
Dürr, Christoph and Heiligman, Mark and HOyer, Peter This paper introduces a new model which re-
and Mhalla, Mehdi This paper shows the potential of quires qubits to be initialized in a highly-entangled
Quantum algorithm to speed up some of the classical cluster state. From this point, the quantum compu-
graph problems such as: tation proceeds by a sequence of single-qubit mea-
surements with classical feedforward of their out-
1. Minima Finding :
comes A cluster state can be thought of as emerg-
Suppose we are given a function f defined on a
ing from an array of equally prepared indepen-
domain of size n, and we want to find an index
dent qubits, which then interact via controlled-phase
i so that f(i) is a minimum in the image of f
(CPhase) gates with their nearest (connected) neigh-
(a) Initially let j ∈ [N] be an index chosen bours. Specifically, a cluster state can be built up by,
uniformly at random. first preparing an uniform superposition of a large
(b) Repeat forever number of Qubits (|+i = ( |0i + |1i)/2 , where 0 and
1 are the computational basis of the physical qubits).
i. Find an index i ∈ [N] such that f(i) ¡ Then, a CPhase operation |ji|ki → (−1)jk |ji|ki ,
f(j). with ( j , k ∈ 0,1) is applied between pairs of neigh-
ii. Set j := i. bouring, connected qubits and effectively generates
2. Minimum Spanning Tree: entanglement between them. According to the pa-
In this section undirected graphs with per, the probability of the quantum computer deter-
weighted edges are considered. In Minimum mining the correct outcome was about 90%.
Spanning Tree we wish to compute a cycle- (2005) Implementation of Grover’s Quan-
free edge set of maximal cardinality that has tum Search Algorithm in a Scalable System
[8]
minimum total weight
Brickman, K-A and Haljan, PC and Lee, PJ and Acton, M
• Let T1,T2,...,Tk be a spanning forest. and Deslauriers, L and Monroe, C
Initially, k = n and each tree Tj contains This paper reports the implementation of
a single vertex. Grover’s quantum search algorithm in the scalable

13
system of trapped atomic ion quantum bits for two tant step in quantum computing with integrated cir-
qubits. Any one of four possible states of a two-qubit cuits, continuing efforts to increase qubit coherence
memory is marked, and following a single query of times, gate performance and register size will be re-
the search space, the marked element is successfully quired to fulfill the promise of a scalable technology.
recovered with an average probability of 60(2)%. (2011) Efficient Grover search with Ryd-
This exceeds the performance of any possible classi- berg blockade [13]
cal search algorithm, which can only succeed with a Mølmer, Klaus and Isenhower, Larry and Saffman, Mark
maximum average probability of 50%. This paper presents effcient methods to implement
(2008) On the Research of BDD Based the quantum computing Grover search algorithm
Simulation of Grover’s Algorithm [11] using the Rydberg blockade interaction. It shows
Xue, Xiling and Chen, Hanwu and Chen, Kaizhong and Li, that simple π -pulse excitation sequences between
Zhiqiang ground and Rydberg excited states readily produce
In this paper, they adopt an efficient data struc- the key conditional phase shift and inversion-about-
ture called the Binary Decision Diagram (BDD) that the mean unitary operations for the Grover search.
exploits the structure displayed in quantum comput- Multi-qubit implementation schemes suitable for dif-
ing to simulate Grover’s quantum search algorithm. ferent properties of the atomic interactions were
First they adapt the original BDD and implement identifed and the error scaling of the protocols with
a series of algorithms to represent and manipulate system size was found to be promising for experi-
matrices and vectors. Then instances of Grover’s al- mental investigation.
gorithm are simulated using our programme written (2016) On the advantages of using relative
in C++. A schematic diagram plotting the prob- phase Toffolis with an application to multiple
ability of successfully finding the item against the control Toffoli optimization
number of Grover iterations. It can be seen that the Dmitri Maslov, * 1National Science Foundation, Arlington,
probabilities of successful search as a function of the Virginia, USA In this paper an approach for system-
number of iterations follow a sinusoidal curve, after atic optimization of quantum circuits via replacing
a certain point the probability of successful measure- suitable pairs of the multiple control Toffoli gates
ment starts fading. with their relative phase implementations was re-
(2009) Demonstration of Two-Qubit Al- ported.This operation preserves the functional cor-
gorithms with a Superconducting Quantum rectness. The advantage can be witnessed through
Processor [12] the optimized resource counts. Our demonstrated
DiCarlo, L and Chow, JM and Gambetta, JM and Bishop, optimizations include a simultaneous optimization
Lev S and Johnson, BR and Schuster, DI and Majer, J and of the T count by a factor of 4/3 in the leading con-
Blais, A and Frunzio, L and Girvin, SM and others stant, the CNOT count by a factor 2 in the leading
Simultaneously meeting the conflicting require- constant, and the number of ancillary qubits by a
ments of long coherence, state preparation, universal factor of 2 in the leading constant.
gate operations, and qubit readout makes building (2016) Demonstration of a small pro-
quantum processors challenging. Few-qubit proces- grammable quantum computer with atomic
sors have already been shown in nuclear magnetic qubits [16]
resonance, cold ion trap and optical systems, but a Debnath, Shantanu and Linke, Norbert M and Figgatt, Caro-
solid-state realization has remained an outstanding line and Landsman, Kevin A and Wright, Kevin and Monroe,
challenge. This research paper demonstrates a two- Christopher
qubit superconducting processor and the implemen- It demonstrates a five-qubit trappedion quantum
tation of the Grover search and Deutsch–Jozsa quan- computer that can be programmed in software to
tum algorithms. It employs a novel two-qubit inter- implement arbitrary quantum algorithms by execut-
action, tunable in strength by two orders of magni- ing any sequence of universal quantum logic gates.
tude on nanosecond time scales, which is mediated It compiles algorithms into a fully-connected set of
by a cavity bus in a circuit quantum electrodynamics gate operations that are native to the hardware and
(cQED) architecture. This interaction allows gener- have a mean fidelity of 98 %. Unlike solid-state im-
ation of highly-entangled states with concurrence up plementations , the quantum circuitry is determined
to 94Although this processor constitutes an impor- by external fields, and hence can be programmed and

14
reconfigured without altering the structure of the process fidelities of 70.5% and 89.6%, respectively.
qubits themselves. As examples, it implements the
(2017) Experimental comparison of two
Deutsch-Jozsa (DJ)h and Bernstein-Vazirani (BV)
quantum computing architectures
algorithms with average success rates of 95 % and
Norbert M. Linke, Dmitri Maslov, Martin Roetteler, Shan-
90 %, respectively. We also perform a coherent
tanu Debnath, Caroline Figgatt, Kevin A. Landsman, Ken-
quantum Fourier transform (QFT) on five trappe-
neth Wright, and Christopher Monroe
dion qubits for phase estimation and period finding
with average fidelities of 62 % and 84 %, respec- This paper focuses on runnnig a selection of algo-
tively. This small quantum computer can be scaled rithms on two state-of-the-art 5-qubit quantum com-
to larger numbers of qubits within a single regis- puters that are based on different technology plat-
ter, and can be further expanded by connecting sev- forms. One is a publicly accessible superconducting
eral such modules through ion shuttling or photonic transmon device www.research.ibm.com/ibm-q with
quantum channels . limited connectivity, and the other is a fully con-
(2017)Complete 3-Qubit Grover search on nected trapped-ion system. Even though the two
a programmable quantum computer systems have different native quantum interactions,
C. Figgatt 1, D. Maslov1,2, K.A. Landsman1, N.M.Linke1, both can be programed in a way that is blind to
S.Debnath1 and C. Monroe1,3 the underlying hardware, thus allowing a compari-
It reports results for a complete three-qubit son of identical quantum algorithms between differ-
Grover search algorithm using the scalable quantum ent physical systems. The research paper shows that
computing technology of trapped atomic ions, with quantum algorithms and circuits that use more con-
better-than-classical performance. Two methods of nectivity clearly benefit from a better-connected sys-
state marking are used for the oracles: a phase-flip tem of qubits. Although the quantum systems here
method employed by other experimental demonstra- are not yet large enough to eclipse classical comput-
tions, and a Boolean method requiring an ancilla ers, this experiment exposes critical factors of scal-
qubit that is directly equivalent to the state mark- ing quantum computers, such as qubit connectivity
ing scheme required to perform a classical search. and gate expressivity. In addition, the results sug-
It also reports the deterministic implementation of gest that codesigning particular quantum applica-
a Toffoli-4 gate, which is used along with Toffoli-3 tions with the hardware itself will be paramount in
gates to construct the algorithms; these gates have successfully using quantum computers in the future.

15
0.5 Our Contribution

• Modified the circuit for 3 Qubit Grover’s Search according to IBM Q 5 Tenerife’s [ibmqx4] architecture
i.e. arrangement and connectivity of qubits.

• We finally executed 3 qubit Grover’s search on IBM QX4 platform IBM Q QASM Simulator.

• Multiple approaches for circuit designs are discussed with optimization by reducing the number of
gate stages and the number of swap gates (basically the cnots) as much as possible to reduce the
errors.

• We have also done an error analysis of the back of the envelope propagation of the number of involved
gates and used the posted errors on the ibmqx4 device to estimate what final state fidelity we should
have expected for our circuit.

• We have also implemented 16 qubit Grover’s Search on well known simulators such as Microsoft’s
LIQUID, Microsoft’s Quantum Development Kit and Quirk: Quantum Circuit Simulator presented
the approach to implement the search and shared the experience along with the comparision of the
final results on these simulators in terms of accuracy and time required to execute them.

0.6 IBM Platforms and Simulators

The Quantum Information Science Kit (Qiskit for short) is a software development kit (SDK)
for working with OpenQASM and the IBM Q Experience (QX). Qiskit can be used to create quantum
computing programs, compile them, and execute them on one of several backends (online Real quantum
processors, online simulators, and local simulators). For the online backends, Qiskit uses our python API
client to connect to the IBM Q Experience.
Quantum Information Science Kit (QISKit) is available to anyone interested in learning how to encode
and simulate algorithms designed for a quantum computer.

QISKit is the software that sits between quantum algorithms from one side, and the physical quantum
device from the other. It translates common programming languages like Python into quantum machine
language. This means anyone outside of the IBM Q lab can program a quantum computer.

IBM Q QASM Simulator [ibmq qasm simulator] we can use max 32 qubits and and the device is
available on QISKit.
Limitations : QASM Simulator allows the if conditions for less than 20 qubits. Fixed stages in composer
makes it difficult to implement large algorithms. It is not possible to do a stage by stage analysis of the
output. It lacks features to view the bloch sphere changes.

IBM Q 5 Yorktown [ibmqx2] and IBM Q 5 Tenerife [ibmqx4] are the 5 qubit devices available
to users on QISKit
The connectivity is provided by two coplanar waveguide (CPW) resonators with resonances around 6.6
GHz (coupling Q2, Q3 and Q4) and 7.0 GHz (coupling Q0, Q1 and Q2). Each qubit has a dedicated CPW
for control and readout. Currently ibmqx2 is under maintenance.

16
 IBM Q 16 Rueschlikon [ibmqx5] is the 16 qubit device and is available on QiSKit
The connectivity on the device is provided by total 22 coplanar waveguide (CPW) ”bus” resonators, each
of which connects two qubits. Three different resonant frequencies are used for the bus resonators. The
resonant frequencies are 6.25 GHz, 6.45 GHz, 6.65 GHz.
IBM Q 20 Austin [QS1 1] and IBM Q 20 Tokyo [ibmq 20 tokyo] are 20 qubit devices which are
available to hubs, partners, and members of the ibm network.
Limitations for Real Devices : Fixed stages in composer makes it difficult to implement large
algorithms. Limited connectivity among the gates increases the need to rely on swap gates. Large errors
are incorporated in the final answer due to cnots. Difference in frequency of qubits limits the direction of
cnots. It is difficult to maintain coherence and prevent loss of state. Its difficult to avoid errors due to
changes in device environment.

0.7 Other Simulators and their Pros and Cons

• Quantum Kit (Q-KIT)[19]
Pros: It is a graphical quantum circuit simulator and works efficiently for less no.of qubits. Easy to
add qubits while working and select gates. Allows stage by stage analysis of state of qubit. Allows
adding custom gates. Shows the probability distributions and amplitude of the possible quantum
states. Allows the bloch sphere analysis.
Cons: Although it states to undertake operations for algorithms involving 20 qubits, it often hangs
up and slows down around 16 qubits and the simulate feature does not work efficiently on laptop
devices. The graphs generated for a large number of qubits are fuzzy and unreadable.

• Quirk: Quantum Circuit Simulator[23]

Pros: Quirk offers a user – friendly environment to study quantum algorithms.It allows upto 16
qubits with an efficient toolbox to manage qubits efficiently with rotation gates and see their block
sphere representation , the chance and amplitude of a particular quantum state, make custom gates
and has an easy implementation of tofollis and swap gates. Results were obtained almost instantly
and with a very high accuracy . Implementing 16 qubit grover’s search was easy and comfortable
experience .
Cons: Has a maximum qubit limitation of 16 qubits.

• Microsoft’s Liqui|i[14]
Pros: LIQUi|i’s simulators are highly optimized, taking advantage of many available techniques
including custom memory management, cache coherence analysis, parallelization, “gate growing”,
and virtualization (running in the cloud). LIQUi|i’s highly optimized simulation environment allows
thorough investigation of quantum algorithms under noise, physical device constraints, and simula-
tion. LIQUi|i is also a full optimizing compiler. A user’s input circuit definition may be massively
rewritten (under user control) to generate compact, highly-optimized versions for simulation. We
can compile any given unitary circuit with varying levels of optimization and can mathematically
prove that the pre- and post-optimized unitary are identical even though the resulting circuits may
appear very different. [18]
Cons: Long simulation time.

• Microsoft’s Quantum Development Kit[21]

Pros: Microsoft’s Quantum Development Kit (QDK) uses Q#, which is a brand-new quantum-
focused programming language with native type, operators, and other abstraction. Q# features rich
integration with Visual Studio and VS Code and interoperability with the Python programming
language. QDK allows us to simulate quantum solutions requiring up to 30 qubits with a local

17
 simulator, or use the Azure simulator for large-scale quantum solutions requiring more than 40
qubits.
Cons: QDK does not have functions to visualize the circuits. It also does not have functions to
optimize the circuit.

0.8 Implementation of Grover’s Algorithm on IBM Simulator

0.8.1 2 Qubit Implementation (IBM QX Simulator)

0.8.2 3 Qubit Implementation (IBM QX Simulator)

0.8.3 5 Qubit Implementation (IBM QX Simulator)

0.8.4 Basic Information about the 3 Qubit Grover’s Search

[1]A 3 qubit grover search with n=3 bits can have N = 2n = 23 = 8 possible correct solutions or 82 C = 28
possible two result solutions The probability of measuring the correct solution after 1 interation of algo-
hh i i 2
N −2t 2(N −t)
rithm is = t · + √1 = 78.125% (for N=8 and t=1)
N N N

18
The oracle marks the state using the Boolean method requiring one ancilla bit initialized as |1i. The
ancilla bit flips only if the input to oracle is one of the marked state.[17]

Figure 19: Circuit for Single Solution Boolean Oracle with Marked State |010i [17]

0.8.4.1 Device: Simulator

Figure 20: Implementation on IBM Q QASM Simulator

Figure 21: Results with Shots=8192

19
0.9 3 Qubit Grover’s Search on IBM QX4
0.9.1 3 Qubit Grover’s Search Implemented For IBM QX4 architecture

(a) IBM QX4

(b) Circuit for implemention of 3 Qubit Grover’s Search Algorithm on IBM QX4

Figure 22: Modified circuit according to the direction of the C-nots using Swap gates

0.9.1.1 Normal Implementation of the 2nd Tofolli Gate

0.9.1.2 Implementation of 2nd Tofolli gate for IBM QX4

Since CX q[2],q[4] and CX q[2],q[3] is not allowed in IBM QX4 we use swap gates to implement them.

Figure 23: IBM QX4 Implementation of 2nd tofolli gate in Circuit given in Fig.14

20
Figure 24: Circuit for implemention of 3 Qubit Grover’s Search Algorithm on IBM QX4
on IBM Quantum Experience

0.9.1.3 Device: Simulator

Shots=8192

Figure 25: The probability of measuring the correct solution after 1 iteration of algorithm is =77.4%

0.9.1.4 Device: IBM QX4

(a) 9.2% with 1024 shots (b) 11.1% with 8192 shots

Figure 26: The probability of measuring the correct solution after 1 interation of algorithm

21
For code refer to Appendix .1.4.1

0.9.2 Optimized Approach for 3 Qubit Grover’s Search

Implemented for IBM QX4 Architecture
This approach implements the algorithm with the use 1 swap gate.

Figure 27: The probability of measuring the correct solution after 1 iteration of algorithm is =21.4% with
8192 shots. ( Marked state= |111i )

For code refer to Appendix 1.4.2

0.9.3 Working of C-Nots in IBM QX4 Architecture (IBM Q5 Tenerife)[20]

The gate directions are given by the following diagram.

22
0.9.3.1 Direction of 2 Qubit gates

(a) Date: November 12, (b) Date: September 25,

2017 (change in direction of 2017
q2 to q4)

Figure 28: The directions in which the c-nots work on IBM QX4

According to the data obtained frequencies of the qubits are given as follows (in GHz):
Q4:5.18929 Q0: 5.24228 Q1 :5.30745 Q2: 5.35162 Q3:5.41037
Therefore in terms of frequencies: q4<q0<q1<q2<q3
Two-qubit gates are possible between neighboring qubits that are connected by a superconducting bus
resonator. The IBM Q experience uses the cross-resonance interaction as the basis for the CX-gate. This
interaction is stronger when choosing the qubit with higher frequency to be the control qubit and the lower
frequency qubit to be the target, so the frequencies of the qubits determines the direction of the gate.
Since frequency of q4 is less than q2 CX q2, q4 should have been possible which is the not the case due
to some exceptions These changes are stated as follows:

23
0.9.3.2 Exceptions to the rule of high frequency control/low frequency target
• the gate direction must be reversed if the higher levels of the control qubit are degenerate with the
target qubit,

• or if either qubit is coupled to a third (spectator) qubit that has the same frequency or a higher
level with the same frequency as the target. In two cases on the QX5, no gate is possible between
neighboring qubits because of degeneracies with spectator qubits that prevent the gate from working
in either direction.

“spectator qubit”: Using spectator qubits involves placing another qubit dedicated to spotting small
deviations in the local environment close to the qubits actually carrying out the data processing.

0.10 Results obtained for 3 Qubit Grover’s Search on

IBM Platform
No of Total
Total
Grover No of Gate No. No.of Accuracy
Device Circuit Design No. of
Itera- Stages of Shots
C-Nots
tions Gates
IBM Using gates given 17 (stages are re-
Quantum in quantum experi- 1 duced due to de- 84 24 8192 79%
Simulator ence composer rived ccx gates)
Basic Design mod-
IBM
ified according to
Quantum 1 80 133 39 8192 77.4%
IBM QX4 architec-
Simulator
ture
Optimized
1 80 133 39
IBM QX4 Approach using 1 1024 9.5 %
swap gate for IBM
QX4 8192 11.1 %
Optimized
1
Approach using 1 Minimum stages
IBM QX4 90 27 8192 19.05 %
swap gate for IBM required=60
QX4
After reduc-
ing stages by
86 27 8192 21.4 %
compacting the
circuit=49
IBM Simulators work fine and show the desired accuracy of 78.125% in one iteration of 3 qubit Grover’s
algorithm.We can see from the table that by optimizing the circuit and reducing the number of cnots we
get a much higher accuracy. We have also removed consecutive hadamards wherever possible to avoid gate
errors. Due to different frequencies of the qubits in IBM QX4, we have can apply cnots only in a fixed
direction .Hence we have to use swap gates to apply cnots in the reverse direction and hence the required
no. of cnots increases to a great deal and the error due to cnots also increases.We have compacted the
gate stages as much as possible to improve the efficiency of the final result.

24
0.11 Back of Envelope Error Analysis of IBM QX4 Device for
the 3 Qubit Grover’s Search Circuit

Figure 29: Errors on IBM QX4 Device (IBM Q 5 Tenerife) as posted on 15-07-2018

Figure 30: Optimized 3 Qubit Grover’s Search Circuit after compacting the stages

No. of CX 1 0 = 2
Error due to CX 1 0= 0.0697
Accuracy in CX 1 0 = 1-0.0697 = 0.9303
Total accuracy due to CX 1 0 = (0.9303)2

No. of CX 2 0 = 2
Error due to CX 2 0= 0.0757
Accuracy in CX 2 0 = 1-0.0757 = 0.9243
Total accuracy due to CX 2 0 =(0.9243)2

No. of CX 3 2 = 6
Error due to CX 3 2= 0.0485
Accuracy in CX 3 2 = 1-0.0485 = 0.9515
Total accuracy due to CX 3 2 = (0.9515)6

No. of CX 4 2 = 6
Error due to CX 4 2= 0.0406
Accuracy in CX 4 2 = 1-0.0406 0.9594
Total accuracy due to CX 4 2 = (0.9594)6
No. of CX 2 1 = 5
Error due to CX 2 1= 0.0361
Accuracy in CX 2 1 = 1-0.0361 = 0.9639

25
Total accuracy due to CX 2 1 = (0.9639)5

No. of CX 3 4 = 6
Error due to CX 3 4= 0.0323
Accuracy in CX 3 4 = 1-0.0323 = 0.9677
Total accuracy due to CX 3 4 = (0.9677)6

Total accuracy due to cnots=

(0.9303)2 · (0.9243)2 · (0.9515)6 · (0.9594)6 · (0.9639)5 · (0.9677)6
=0.29236631651

No. of gates applied to qubit[0] (other than cnots) = 6 (8 gates are applied but only 6 contribute to
result)
Error due to q[0] gates= 0.0055
Accuracy in q[0] gates = 1-0.0055 = 0.9945
Total accuracy due to q[0] gates = (0.9945)6

No. of gates applied to qubit[1] (other than cnots) = 6 Error due to q[1] gates= 0.00223
Accuracy in q[1] gates = 1-0.00223 = 0.99777
Total accuracy due to q[1] gates = (0.99777)6

No. of gates applied to qubit[2] (other than cnots) = 25

Error due to q[2] gates= 0.00112
Accuracy in q[2] gates = 1-0.00112 = 0.99888
Total accuracy due to q[2] gates = (0.99888)25

No. of gates applied to qubit[3] (other than cnots) = 8

Error due to q[3] gates= 0.00146
Accuracy in q[3] gates = 1-0.00146 = 0.99854
Total accuracy due to q[3] gates = (0.99854)8

No. of gates applied to qubit[4] (other than cnots) = 14

Error due to q[4] gates= 0.00146
Accuracy in q[4] gates = 1-0.00146 = 0.99854
Total accuracy due to q[4] gates = (0.99854)14

Total accuracy due to all the single qubit gates

=( Total accuracy due to q[0] gates)· ( Total accuracy due to q[1] gates)· ( Total accuracy
due to q[2] gates)· ( Total accuracy due to q[3] gates)· ( Total accuracy due to q[4] gates)

=(0.9945)6 · (0.99777)6 · (0.99888)25 · (0.99854)8 · (0.99854)14

=0.89877695775
Accuracy due to all the gates = (Accuracy due to cnots)· (accuracy due to all single qubit
gates)
=0.29236631651· 0.89877695775
=0.2627721085

Considering the Readout Errors

Readout Error due to qubit[2] =0.025
Accuracy due to Measure gates applied to qubit[2] = 1-0.0250=0.975

26
Readout Error due to qubit[3] =0.0170
Accuracy due to Measure gates applied to qubit[3] = 1-0.0170 = 0.983
Readout Error due to qubit[4] =0.0510
Accuracy due to Measure gates applied to qubit[4] = 1-0.0510 = 0.949

Accuracy to all measure gates = 0.975· 0.983· 0.949

=0.909545325

Total Accuracy = Accuracy due to all the gates · Accuracy to all measure gates
= 0.2627721085 · 0.909545325
=0.239003143

Highest answer predicted by the simulator = 0.791

Least answer expected from device ibmqx4 = 0.7910 · 239003143 = 0.189051486
≈ 19%
Obtained ans=21.4%

Figure 31: Result obtained on IBM QX4 device for the optimized 3 Qubit Grover’s Search Circuit after
compacting the stages

27
0.12 Implementing 16 Qubits Grover’s Search
Simulators used:

1. Microsoft’s LIQUI |i

2. Microsoft’s Quantum Development Kit

3. Quirk: Quantum Circuit Simulator

0.12.1 Circuit diagram

• Total number of possible states = N = 2n = 216 = 65, 536
π√ π p 16
• No. of iterations = N= (2 ) = 201.06
4 4
• Required state = 1111111111111111 = 65,535

H • H X • X H
H • H X • X H
H • H X • X H
H • H X • X H
H • H X • X H
H • H X • X H
H • H X • X H
H • H X • X H
H • H X • X H
H • H X • X H
H • H X • X H
H • H X • X H
H • H X • X H
H • H X • X H
H • H X • X H
H • H X H H X H
X H

28
0.12.2 Creating larger CNOTs using toffoli gates [15]

Ancilla bits are extra bits, not involved in the logical operation being performed, that give circuit con-
structions ”room to move”. In addition to making constructions possible in the first place, ancilla bits can
allow for simpler or more efficient constructions.
The type of Ancilla bits used is Borrowed Bits, where the bits can be in any state beforehand, and must be
restored to that same state afterwards. The advantage of using Borrowed Bits is that they can be reused
and hence, reduce the number of Qubits required. But, this implementation increases the number of toffoli
gates required.

29
0.12.3 The Oracle
The black box function (f(x)), in this implementation, is designed such that when all the inputs are 1 i.e.
state is 1111111111111111, it returns the value 1.

f (x∗ ) = 1

where x∗ is the desired state.

Using this function, the oracle matrix Uf is designed to act on any of the simple, standard basis states |x
rangle by
Uf |xi = (−1)f (x) |xi
Implementation of C 16 NOT gate (Oracle function) :

Figure 32: Implementation of C 16 N OT using smaller CNOT gates

30
Implementation of C 8 N OT and C 9 N OT using toffoli gates:

Figure 33: Implementation of C 8 N OT using toffoli gates

Figure 34: Implementation of C 9 N OT using toffoli gates

31
0.12.4 The Diffusion Operation
Diffusion (Amplitude Amplification) is the procedure by which the quantum computer significantly en-
hances the probability of the required state

Circuit diagram:

H X • X H
H X • X H
H X • X H
H X • X H
H X • X H
H X • X H
H X • X H
H X • X H
H X • X H
H X • X H
H X • X H
H X • X H
H X • X H
H X • X H
H X • X H
H X H H X H

32
Implementation of C 15 N OT :

Figure 35: Implementation of C 15 N OT using smaller CNOT gates

33
Implementation of C 8 N OT using toffoli gates:

Figure 36: Implementation of C 8 N OT using toffoli gates

Figure 37: Implementation of C 8 N OT using toffoli gates

34
0.12.5 Implementation of 16 Qubits Grover’s search on Microsoft’s LIQUi |i
simulator
LIQUi|i[14] is a simulation platform developed by the Quantum Architectures and Computation team at
Microsoft Research to aid in the exploration of quantum computation. LIQUi |i stands for “Language
Integrated Quantum Operations”.

Programming language used : F#

0.12.5.1 Result on compiling and rendering the circuit

{For code refer to Appendix .1.5 }

Circuit diagrams :

Figure 38: Oracle circuit diagram

35
Figure 39: Diffusion circuit diagram

36
Output :

Desired result : 1111111111111111

Time taken : 72.2 minutes

Figure 40: Result on compiling and executing the circuit

37
0.12.5.2 Result on optimizing the circuit
LIQUi|i has method, GrowGates() to optimize the circuit by transforming it into more efficient unitary
matrices.
Circuit diagrams :

Figure 41: Optimized oracle circuit diagram

Figure 42: Optimized diffusion circuit diagram

38
Output :

Desired result : 1111111111111111

Time taken : 22.7 minutes

Figure 43: Result on optimizing the circuit

39
0.12.6 Implementation of 16 Qubits Grover’s search on Microsoft’s Quantum
Development Kit (QDK)
The Quantum Development Kit , developed by Microsoft, is based on Q# language coding and includes a
Q# compiler, Q# libraries, a local quantum computing simulator, a quantum trace simulator and a Visual
Studio extension for quantum computing projects.

Programming languages used: Q# and C#

{ For code refer to Appendix .1.6}

Output :

The circuit is simulated five times and based on the outputs, the probability of getting the desired state
(1111111111111111) is calculated.

Desired result : 1111111111111111

Time taken : 1.34 minutes

Figure 44: Result on executing the circuit

40
0.12.7 Implementation on Quirk quantum simulator
0.12.7.1 Grover gate :
Oracle : The 16 bit controlled Z-gate flips the amplitude of the required state (here |11111111111111011i)
Diffusion : It is implemented using 16 bit controlled-not gate 1

Figure 45: Grover gate

0.12.7.2 Circuit diagram :

Figure 46: Circuit diagram

1
Note that HXH = Z and HZH = X, and diffusion operator = HZH

41
0.12.7.3 Result :
grover 20 gate is 20 times the Grover gate applied repeatedly

Results after 400 iterations :

Figure 47: simulation output

42
0.13 Conclusions
While quantum computing has dramatically advanced through the last decade, its potential applications
have not yet been demonstrated at full scale. Such demonstrations are likely to require breakthroughs in
physics, computer science and engineering[4].The Quantum computers are prone to errors due to quantum
coherence and environmental conditions. To this end, we have analyzed the potential of Grover’s search
algorithm to provide quadratic speed up over classical search algorithm, for certain problems and have
executed it for 3 Qubits on IBMQX4 , developed by IBM. We got the desired state with a probability of
22.4% (for one iteration), which is much less than the theoretical probability of 78.125%. Thus, at the
moment, the gate errors on the public devices made available by IBM are quite high. Finally, we have
executed Grover’s search for 16 Qubits on Microsoft’s LIQUi |i, Microsoft’s Quantum Development Kit
and Quirk simulator and observed the following:

Results obtained for Implementation of

16 Qubit Grover’s Search on various Platforms
No. of Grover
Device Time Taken Accuracy
Iterations
Microsoft’s LIQUii
201 22.7 minutes 100%
Simulator
Microsoft Quantum
201 1.34 minutes 60%
Development Kit
Quirk Quantum Simu-
200 instant 99.9839%
lator

Simple compilation and execution of 16 Qubits Grover’s search took 72.2 minutes on Microsoft’s LIQUi |i
simulator. But, on optimizing the circuit using the inbuilt method GrowGates(), the simulation took
merely 22.7 minutes, that is, the circuit executes at a 31.44% faster rate. Also, the simulator provides a
very high accuracy rate of almost cent percent and returned the desired state (|1111111111111111i) as the
result at each test run. On the other hand, Microsoft’s Quantum development kit provided less accurate
results. After simulating the circuit on five consecutive trials, the desired state (|1111111111111111i) was
obtained only three times which translates accuracy to just 60%. It is, however, observed that operations
take much less time while using this simulator if one can compromise with low accuracy. Compared to
these Quirk Simulator gave almost instant results but it was restricted to a maximum of 16 qubits. Since
the Quirk toolbox provided an easy tofolli implementation we did not have to worry about its equivalent
circuit using basic quantum gates. However this implementation was close to the theoritical model of the
circuit rather than being close to actual hardware.

43
0.14 Limitations
Coherence issues where device must constantly fight against the environment which acts to degrade the
coherence of the system. And hence delicate quantum information stored in a quantum computer is
extremely susceptible to noise. Qubits must be kept cold or else they collapse easily. Error due to qubit
entanglement are high. Multiqubit gate errors were much higher than single qubit gate errors.
Limited Connectivity among the qubits is another major limitation. Hence there is a need for employing
a large no. of swap gates which increases the gate count (thus adding to gate errors) especially the cnots
which have a quite high errors and thus reducing the expected state fidelity by a great deal and also
circuits become complex and difficult to comprehend and debug. IBM Simulators already have limited
code length (comparatively LIQUi|i and Quirk Quantum Simulator have relaxed code lengths) hence it
becomes difficult to implement large circuits or enlarge the circuits to add any error correction gates or
resolve the problem of limited connectivity by adding more swap gates.
Due to difference in the frequency of qubits in IBM devices the direction of applying cnots is limited to
specific qubits which also increases our dependency on swap gates to a great deal.Also we cannot do stage
by stage analysis on IBM devices. While working on the real IBM devices sending our code to run on
actual devices , a long queue of execution generally results in a timeout error while working with QISKit.
While the composer ensures results even though if they are delayed it has limited stages due to which
quantum algorithms with large number of stages cannot be executed. Implementing the tofolli gate for 16
qubits required many extra qubits or a large number of stages both of which is not possible on the current
IBM devices and hence implementing 16 qubit Grover’s search on the IBM simulators and real devices was
not realistic.

44
References

[1] Charles H Bennett et al. “Strengths and weaknesses of quantum computing”. In: SIAM journal on
Computing 26.5 (1997), pp. 1510–1523.
[2] Michel Boyer et al. “Tight bounds on quantum searching”. In: Fortschritte der Physik: Progress of
Physics 46.4-5 (1998), pp. 493–505.
[3] Isaac L Chuang, Neil Gershenfeld, and Mark Kubinec. “Experimental implementation of fast quan-
tum searching”. In: Physical review letters 80.15 (1998), p. 3408.
[4] John Preskill. “Quantum computing: pro and con”. In: Proceedings of the Royal Society of London A:
Mathematical, Physical and Engineering Sciences. Vol. 454. 1969. The Royal Society. 1998, pp. 469–
486.
[5] Lieven MK Vandersypen et al. “Implementation of a three-quantum-bit search algorithm”. In: Applied
Physics Letters 76.5 (2000), pp. 646–648.
[6] N Bhattacharya, HB van Linden van den Heuvell, and RJC Spreeuw. “Implementation of quantum
search algorithm using classical Fourier optics”. In: Physical review letters 88.13 (2002), p. 137901.
[7] Quantum logic gate. Quantum logic gate — Wikipedia, The Free Encyclopedia. Accessed: 2018-07-20.
2004. url: https://en.wikipedia.org/wiki/Quantum_logic_gate.
[8] K-A Brickman et al. “Implementation of Grover’s quantum search algorithm in a scalable system”.
In: Physical Review A 72.5 (2005), p. 050306.
[9] Philip Walther et al. “Experimental one-way quantum computing”. In: Nature 434.7030 (2005),
p. 169.
[10] Christoph Dürr et al. “Quantum query complexity of some graph problems”. In: SIAM Journal on
Computing 35.6 (2006), pp. 1310–1328.
[11] Xiling Xue et al. “On the Research of BDD Based Simulation of Grover’s Algorithm”. In: Genetic
and Evolutionary Computing, 2008. WGEC’08. Second International Conference on. IEEE. 2008,
pp. 459–462.
[12] L DiCarlo et al. “Demonstration of two-qubit algorithms with a superconducting quantum processor”.
In: Nature 460.7252 (2009), p. 240.
[13] Klaus Mølmer, Larry Isenhower, and Mark Saffman. “Efficient Grover search with Rydberg blockade”.
In: Journal of Physics B: Atomic, Molecular and Optical Physics 44.18 (2011), p. 184016.
[14] Dave Wecker and Krysta M. Svore. LIQUi—¿: A Software Design Architecture and Domain-Specific
Language for Quantum Computing. 2014. eprint: 1402.4467. url: arXiv:1402.4467v1.
[15] Craig Gidney. Constructing Large Controlled Nots. http://algassert.com/circuits/2015/06/
05/Constructing-Large-Controlled-Nots.html. Blog. 2015.
[16] Shantanu Debnath et al. “Demonstration of a small programmable quantum computer with atomic
qubits”. In: Nature 536.7614 (2016), p. 63.

45
[17] C Figgatt et al. “Complete 3-qubit Grover search on a programmable quantum computer”. In: Nature
communications 8.1 (2017), p. 1918.
[18] Norbert M Linke et al. “Experimental comparison of two quantum computing architectures”. In:
Proceedings of the National Academy of Sciences 114.13 (2017), pp. 3305–3310.
[19] Archana Tankasala, Hesameddin Ilatikhameneh. Q-Kit. https : / / sites . google . com / view /
quantum-kit/.
[20] IBM Q 5 Tenerife V1.x.x Version Log. https : / / quantumexperience . ng . bluemix . net / qx /
tutorial?sectionId=beginners- guide&page=005- Single- Qubit_Gates~2F006- Summary_of_
quantum_gates. Accessed: 2018-21-07.
[21] Microsoft. Quantum Development Kit. https://www.microsoft.com/en-in/quantum/development-
kit. Accessed: 2018-06-23.
[22] Proof of Gate Complexity. https://www.cs.cmu.edu/~odonnell/quantum15/lecture04.pdf.
[23] Quirk Quantum Simulator. https://algassert.com/quirk.
[24] Summary of Quantum Gates IBM Q Experience. https : / / quantumexperience . ng . bluemix .
net / qx / tutorial ? sectionId = beginners - guide & page = 005 - Single - Qubit _ Gates~2F006 -
Summary_of_quantum_gates. Accessed: 2018-19-07.

46
.1 Appendix
.1.1 Proof of Optimal No. of Iterations

Figure 48: Geometric representation of Grover’s search

After r iterations of Oracle and Diffusion subroutines, we get the relation ( Figure: 48)

φ(r) = (2r + 1)θ (1)

0
Now, for any vector |vi spanned by the orthonormal bases |x∗ i and |s i, can be represented by,
0
|vi = cos φ(r) |s i + sin φ(r) |x∗ i

So, the probability of |x∗ i after r iterations of the Oracle and diffusion subroutines is given by,

P (|x∗ i) = sin2 φ(r)

Or, we need to maximize sin φ(r) . We get the maximum value

sin φ(r) = 1

at
φ(r) = π/2 (2)

Using equations (1) and (2),

(2r + 1)θ = π/2 (3)

47
we get, p
θ = sin−1 ( 1/2n )2 (4)

Using (4) in (1), we get p

φ(r) = (2r + 1) sin−1 ( 1/2n ) = π/2 (5)
For very large n, (n → ∞),
p p
sin−1 ( 1/2n ) ≈ 1/2n (6)

Using (6) we get, p

(2r + 1) 1/2n = π/2
or,
π√ n
2 − 1)
(
r= 2
2
for large n,
π√ n
r= 2
4
π√ n
Thus, 2 iterations of oracle and diffusion operations are required to achieve maximum probability of
4
desired result.

.1.2 Derivation of angle θ between uniform superposition |si and component

of uniform superposition |s0 i normal to |x∗ i

Calculating the projection of |si onto |s0 i,

= (|s0 ihs|0 )|si

= hs0 |si|s0 i
Now, from the figure, the inner product hs0 |si is given by,

cos θ = hs0 |si (7)

2
Proof in Appendix .1.2

48
The inner product hs0 |si can be calculated as,
1 1
hs0 |si = (2n − 1)( √ n )( √ ) (8)
2 −1 2n
using equations (7) and (8), we get r
2n − 1
cos θ =
2n
or, r
1
sin θ =
2n
or,
r
−1 1
θ = sin (9)
2n

.1.3 Proof of Gate Complexity [22]

√
We also promised an O( N logN ) bound on the number of gates used in the algorithm. To prove this
bound, it suffices to construct the Grover diffusion gate. To do so, we first define the Z0 defned by
 
|xi if |xi = |0n i
Z0 |xi =
−|xi otherwise

In unitary matrix form, Z0 = 2|0n ih0n | − I where I is the n x n identity matrix.

Now we can construct the Grover diffusion gate, D, with a Z0 gate and O(n) = O(logN) Hadamard gates.
In matrix form, knowing that the Hadamard gate is its own inverse, we can write the diffusion gate as
N N
n n
D =H Z0 H
N N
=H n (2|0n ih0n | − I) H n
 N  N †

n n
N N
n n
=2 (H|0 i) (H|0 i) − H nH n

=2|+n ih+n | − I

It is the same as Z0 but with |+i instead of |0i. In diagram form, it is

P
Let us try giving the matrix an arbitrary input |ψi = x∈{0,1}n αx |xi to make sure it works. We get

D|ψi = (2|+n ih+n | − I) |ψi

= (2|+n ih+n |ψi − |ψi)

49
Notice that we can rewrite |+i to get

 N n
h0| + h1|
h+n | = √
2
X 1
= √ hx|,
x∈{0,1}n
N

X α
h+n |ψi = √ x hx|xi
x∈{0,1}n
N
X α
= √x
x∈{0,1}n
N
√
=µ N

That means that we can continue simplifying D |ψi to get

D|ψi =2|+n ih+n |ψi − |ψi

√
=2|+n iµ N − |ψi
√
 
h0| + h1|
=2 √ µ N − |ψi
2
 
X 1 √
=2  √ |xi µ N − |ψi
x∈{0,1}n
N
 
X
=2  µ|xi − |ψi
x∈{0,1}n
X
= (2µ − αx ) |xi
n
x∈{0,1}

which is precisely what we expect from the diffusion operator. Lastly, we need to show that we actually
can construct the Z0 gate. What does Z0 do? It negates |xi if and only if the logical OR of {x1 , x2 , .....xn }
is 1, where xi is the i-th qubit that makes up |xi. These kinds of logical operations are easy to compute. In
particular,there is a classical circuit that computes the logical OR of n bits with O(n) = O(logN ) Toffoli or
CNOT gates. This circuit is not reversible, but of course we can fix that. Given a circuit C that computes
the logical OR of n bits, we can construct a circuit C’ with m ∈ N ancillary bits that does the following:

50
 Now if we send |xi  |−i  |0m i into C’, we get (−1)OR(x) (|xi  |−i  |0m i) out, which is exactly what
Z0 does. There are some extra garbage bits, but those can be ignored. Ultimately, what this all means is
that the √
Grover diffusion gate can be constructed with O(logN) gates. That means that Grover’s algorithm
takes O( N logN ) gates to implement.

.1.4 QASM Code for 3 qubit Grover’s Algortitm

.1.4.1 QASM Code for Basic 3 Qubit Grover’s Algorithm in IBM Simulator

1. include ”qelib1.inc”; 42. cx q[3],q[4]; 83. tdg q[1];

2. qreg q[5]; 43. tdg q[4]; 84. t q[2];
3. creg c[5]; 44. h q[2]; 85. cx q[2],q[1];
4. h q[0]; 45. h q[4]; 86. x q[3];
5. h q[1]; 46. cx q[4],q[2]; 87. x q[2];
6. h q[2]; 47. h q[2]; 88. h q[3];
7. h q[3]; 48. t q[3]; 89. h q[1];
8. x q[4]; 49. h q[4]; 90. h q[2];
9. cx q[1],q[0]; 50. h q[2]; 91. x q[3];
10. x q[2]; 51. h q[3]; 92. x q[1];
11. x q[3]; 52. t q[4]; 93. x q[2];
12. h q[4]; 53. cx q[3],q[2]; 94. h q[3];
13. tdg q[0]; 54. h q[4]; 95. cx q[3],q[2];
14. cx q[2],q[0]; 55. h q[2]; 96. h q[2];
15. t q[0]; 56. h q[3]; 97. h q[3];
16. cx q[1],q[0]; 57. t q[2]; 98. cx q[3],q[2];
17. tdg q[0]; 58. tdg q[3]; 99. h q[2];
18. t q[1]; 59. h q[2]; 100. h q[3];
19. cx q[2],q[0]; 60. h q[3]; 101. cx q[3],q[2];
20. t q[0]; 61. cx q[3],q[2]; 102. cx q[2],q[0];
21. cx q[2],q[1]; 62. h q[2]; 103. h q[0];
22. h q[0]; 63. h q[3]; 104. h q[2];
23. tdg q[1]; 64. cx q[2],q[0]; 105. cx q[2],q[0];
24. t q[2]; 65. h q[0]; 106. h q[0];
25. cx q[2],q[1]; 66. h q[2]; 107. h q[2];
26. cx q[2],q[0]; 67. cx q[2],q[0]; 108. cx q[2],q[0];
27. h q[0]; 68. h q[0]; 109. cx q[3],q[2];
28. h q[2]; 69. h q[2]; 110. h q[2];
29. cx q[2],q[0]; 70. cx q[2],q[0]; 111. h q[3];
30. h q[4]; 71. h q[0]; 112. h q[0];
31. h q[0]; 72. cx q[1],q[0]; 113. cx q[3],q[2];
32. h q[2]; 73. tdg q[0]; 114. cx q[1],q[0];
33. cx q[3],q[4]; 74. cx q[2],q[0]; 115. h q[2];
34. cx q[2],q[0]; 75. t q[0]; 116. h q[3];
35. tdg q[4]; 76. cx q[1],q[0]; 117. tdg q[0];
36. h q[2]; 77. tdg q[0]; 118. cx q[3],q[2];
37. h q[4]; 78. t q[1]; 119. cx q[2],q[0];
38. cx q[4],q[2]; 79. cx q[2],q[0]; 120. t q[0];
39. h q[2]; 80. t q[0]; 121. cx q[1],q[0];
40. h q[4]; 81. cx q[2],q[1]; 122. tdg q[0];
41. t q[4]; 82. h q[0]; 123. cx q[2],q[0];

51
124. t q[0]; 130. h q[0]; 136. h q[1];
125. t q[1]; 131. cx q[2],q[1]; 137. h q[2];
126. h q[0]; 132. x q[0]; 138. measure q[0] -> c[2];
127. cx q[2],q[1]; 133. x q[1]; 139. measure q[1] -> c[1];
128. tdg q[1]; 134. x q[2]; 140. measure q[2] -> c[0];
129. t q[2]; 135. h q[0];

.1.4.2 QASM Code for Optimized 3 Qubit Grover’s Algorithm in IBM Simulator

1. include ”qelib1.inc”; 34. tdg q[1]; 67. x q[2];

2. qreg q[5]; 35. h q[0]; 68. x q[3];
3. creg c[5]; 36. cx q[2],q[1]; 69. x q[4];
4. x q[0]; 37. tdg q[1]; 70. h q[2];
5. h q[1]; 38. cx q[2],q[1]; 71. h q[2];
6. h q[3]; 39. s q[1]; 72. cx q[4],q[2];
7. h q[4]; 40. t q[2]; 73. tdg q[2];
8. h q[0]; 41. h q[2]; 74. cx q[3],q[2];
9. h q[2]; 42. cx q[4],q[2]; 75. t q[2];
10. cx q[4],q[2]; 43. tdg q[2]; 76. cx q[4],q[2];
11. tdg q[2]; 44. cx q[3],q[2]; 77. tdg q[2];
12. cx q[3],q[2]; 45. t q[2]; 78. cx q[3],q[2];
13. t q[2]; 46. cx q[4],q[2]; 79. t q[2];
14. cx q[4],q[2]; 47. tdg q[2]; 80. tdg q[4];
15. tdg q[2]; 48. cx q[3],q[2]; 81. h q[2];
16. cx q[3],q[2]; 49. t q[2]; 82. cx q[3],q[4];
17. t q[2]; 50. tdg q[4]; 83. tdg q[4];
18. tdg q[4]; 51. h q[2]; 84. cx q[3],q[4];
19. h q[2]; 52. cx q[3],q[4]; 85. h q[2];
20. cx q[3],q[4]; 53. tdg q[4]; 86. t q[3];
21. h q[0]; 54. cx q[3],q[4]; 87. s q[4];
22. tdg q[4]; 55. t q[3]; 88. x q[2];
23. cx q[1],q[0]; 56. s q[4]; 89. x q[3];
24. cx q[3],q[4]; 57. cx q[2],q[1]; 90. x q[4];
25. tdg q[0]; 58. h q[1]; 91. h q[2];
26. t q[3]; 59. h q[2]; 92. h q[3];
27. s q[4]; 60. cx q[2],q[1]; 93. h q[4];
28. cx q[2],q[0]; 61. h q[1]; 94. measure q[2] -> c[2];
29. t q[0]; 62. h q[2]; 95. measure q[3] -> c[3];
30. cx q[1],q[0]; 63. cx q[2],q[1]; 96. measure q[4] -> c[4];
31. tdg q[0]; 64. h q[2];
32. cx q[2],q[0]; 65. h q[3];
33. t q[0]; 66. h q[4];

52
.1.5 Code for implementing 16 qubit Grover’s search in Microsoft’s LIQUi |i
simulator
.1.5.1 Oracle function:

let oracle ( qs : Qubits ) =

let h i = H [ qs .[ i ]]
let m i = M [ qs .[ i ]]
let x i = X [ qs .[ i ]]
let ccx i j k = CCNOT [ qs .[ i ]; qs .[ j ]; qs .[ k ]]
let cx i j = CNOT [ qs .[ i ]; qs .[ j ]]

ccx 13 14 17
ccx 11 12 13
ccx 9 10 11
ccx 7 8 9
ccx 5 6 7
ccx 3 4 5
ccx 0 2 3
ccx 3 4 5
ccx 5 6 7
ccx 7 8 9
ccx 9 10 11
ccx 11 12 13
ccx 13 14 17
ccx 11 12 13
ccx 9 10 11
ccx 7 8 9
ccx 5 6 7
ccx 3 4 5
ccx 0 2 3
ccx 3 4 5
ccx 5 6 7
ccx 7 8 9
ccx 9 10 11
ccx 11 12 13
ccx 17 18 16
ccx 14 15 18
ccx 12 13 14
ccx 10 11 12
ccx 8 9 10
ccx 6 7 8
ccx 4 5 6
ccx 1 3 4
ccx 4 5 6
ccx 6 7 8
ccx 8 9 10
ccx 10 11 12
ccx 12 13 14
ccx 14 15 18

53
ccx 18 17 16
ccx 14 15 18
ccx 12 13 14
ccx 10 11 12
ccx 8 9 10
ccx 6 7 8
ccx 4 5 6
ccx 1 3 4
ccx 4 5 6
ccx 6 7 8
ccx 8 9 10
ccx 10 11 12
ccx 12 13 14
ccx 14 15 18
ccx 13 14 17
ccx 11 12 13
ccx 9 10 11
ccx 7 8 9
ccx 5 6 7
ccx 3 4 5
ccx 0 2 3
ccx 3 4 5
ccx 5 6 7
ccx 7 8 9
ccx 9 10 11
ccx 11 12 13
ccx 13 14 17
ccx 11 12 13
ccx 9 10 11
ccx 7 8 9
ccx 5 6 7
ccx 3 4 5
ccx 0 2 3
ccx 3 4 5
ccx 5 6 7
ccx 7 8 9
ccx 9 10 11
ccx 11 12 13
ccx 17 18 16
ccx 14 15 18
ccx 12 13 14
ccx 10 11 12
ccx 8 9 10
ccx 6 7 8
ccx 4 5 6
ccx 1 3 4
ccx 4 5 6
ccx 6 7 8
ccx 8 9 10
ccx 10 11 12

54
 ccx 12 13 14
ccx 14 15 18
ccx 18 17 16
ccx 14 15 18
ccx 12 13 14
ccx 10 11 12
ccx 8 9 10
ccx 6 7 8
ccx 4 5 6
ccx 1 3 4
ccx 4 5 6
ccx 6 7 8
ccx 8 9 10
ccx 10 11 12
ccx 12 13 14
ccx 14 15 18

.1.5.2 Diffusion function:

let diffusion ( qs : Qubits ) =

let h i = H [ qs .[ i ]]
let m i = M [ qs .[ i ]]
let x i = X [ qs .[ i ]]
let ccx i j k = CCNOT [ qs .[ i ]; qs .[ j ]; qs .[ k ]]
let cx i j = CNOT [ qs .[ i ]; qs .[ j ]]
for i in 0..15 do
h i
for i in 0..15 do
x i
h 15

ccx 13 14 17
ccx 11 12 13
ccx 9 10 11
ccx 7 8 9
ccx 5 6 7
ccx 3 4 5
ccx 0 2 3
ccx 3 4 5
ccx 5 6 7
ccx 7 8 9
ccx 9 10 11
ccx 11 12 13
ccx 13 14 17
ccx 11 12 13
ccx 9 10 11
ccx 7 8 9
ccx 5 6 7
ccx 3 4 5

55
ccx 0 2 3
ccx 3 4 5
ccx 5 6 7
ccx 7 8 9
ccx 9 10 11
ccx 11 12 13
ccx 14 17 15
ccx 12 13 14
ccx 10 11 12
ccx 8 9 10
ccx 6 7 8
ccx 4 5 6
ccx 1 3 4
ccx 4 5 6
ccx 6 7 8
ccx 8 9 10
ccx 10 11 12
ccx 12 13 14
ccx 14 17 15
ccx 12 13 14
ccx 10 11 12
ccx 8 9 10
ccx 6 7 8
ccx 4 5 6
ccx 1 3 4
ccx 4 5 6
ccx 6 7 8
ccx 8 9 10
ccx 10 11 12
ccx 12 13 14
ccx 13 14 17
ccx 11 12 13
ccx 9 10 11
ccx 7 8 9
ccx 5 6 7
ccx 3 4 5
ccx 0 2 3
ccx 3 4 5
ccx 5 6 7
ccx 7 8 9
ccx 9 10 11
ccx 11 12 13
ccx 13 14 17
ccx 11 12 13
ccx 9 10 11
ccx 7 8 9
ccx 5 6 7
ccx 3 4 5
ccx 0 2 3
ccx 3 4 5

56
ccx 5 6 7
ccx 7 8 9
ccx 9 10 11
ccx 11 12 13
ccx 14 17 15
ccx 12 13 14
ccx 10 11 12
ccx 8 9 10
ccx 6 7 8
ccx 4 5 6
ccx 1 3 4
ccx 4 5 6
ccx 6 7 8
ccx 8 9 10
ccx 10 11 12
ccx 12 13 14
ccx 14 17 15
ccx 12 13 14
ccx 10 11 12
ccx 8 9 10
ccx 6 7 8
ccx 4 5 6
ccx 1 3 4
ccx 4 5 6
ccx 6 7 8
ccx 8 9 10
ccx 10 11 12
ccx 12 13 14

h 15
for i in 0..15 do
x i
for i in 0..15 do
h i

57
.1.5.3 Function to optimize and compile the circuit:

[ < LQD >]

let __GroverSearch () =
let stats = Array . create 16 0
let k = Ket (19)
let circ1 = Circuit . Compile oracle k . Qubits
let optCirc1 = circ1 . GrowGates ( k )
show " Test1 : "
optCirc1 . Dump ()
optCirc1 . RenderHT ( " Test1 " )
let circ2 = Circuit . Compile diffusion k . Qubits
let optCirc2 = circ2 . GrowGates ( k )

show " Test2 : "

optCirc2 . Dump ()
optCirc2 . RenderHT ( " Test2 " )
let qs = k . Reset (19)
let h i = H [ qs .[ i ]]
let m i = M [ qs .[ i ]]
let x i = X [ qs .[ i ]]
for i in 0..15 do
h i
x 16
h 16
for i in 0..200 do
optCirc1 . Run qs
optCirc2 . Run qs
for i in 0..15 do
m i
for i in 0..15 do
stats .[ i ] <- qs .[ i ]. Bit . v
for i in 0..15 do
show " val [% d ]=% d " i stats .[ i ]

58
.1.6 Code for implementing 16 qubits Grover’s search in Microsoft’s Quan-
tum Development Kit (QDK)
.1.6.1 Oracle operation:

operation Oracle ( q : Qubit []) : ()

{
body
{
H ( q [16]) ;
CCNOT ( q [13] , q [14] , q [17]) ;
CCNOT ( q [11] , q [12] , q [13]) ;
CCNOT ( q [9] , q [10] , q [11]) ;
CCNOT ( q [7] , q [8] , q [9]) ;
CCNOT ( q [5] , q [6] , q [7]) ;
CCNOT ( q [3] , q [4] , q [5]) ;
CCNOT ( q [0] , q [2] , q [3]) ;
CCNOT ( q [3] , q [4] , q [5]) ;
CCNOT ( q [5] , q [6] , q [7]) ;
CCNOT ( q [7] , q [8] , q [9]) ;
CCNOT ( q [9] , q [10] , q [11]) ;
CCNOT ( q [11] , q [12] , q [13]) ;
CCNOT ( q [13] , q [14] , q [17]) ;
CCNOT ( q [11] , q [12] , q [13]) ;
CCNOT ( q [9] , q [10] , q [11]) ;
CCNOT ( q [7] , q [8] , q [9]) ;
CCNOT ( q [5] , q [6] , q [7]) ;
CCNOT ( q [3] , q [4] , q [5]) ;
CCNOT ( q [0] , q [2] , q [3]) ;
CCNOT ( q [3] , q [4] , q [5]) ;
CCNOT ( q [5] , q [6] , q [7]) ;
CCNOT ( q [7] , q [8] , q [9]) ;
CCNOT ( q [9] , q [10] , q [11]) ;
CCNOT ( q [11] , q [12] , q [13]) ;
CCNOT ( q [17] , q [18] , q [16]) ;
CCNOT ( q [14] , q [15] , q [18]) ;
CCNOT ( q [12] , q [13] , q [14]) ;
CCNOT ( q [10] , q [11] , q [12]) ;
CCNOT ( q [8] , q [9] , q [10]) ;
CCNOT ( q [6] , q [7] , q [8]) ;
CCNOT ( q [4] , q [5] , q [6]) ;
CCNOT ( q [1] , q [3] , q [4]) ;
CCNOT ( q [4] , q [5] , q [6]) ;
CCNOT ( q [6] , q [7] , q [8]) ;
CCNOT ( q [8] , q [9] , q [10]) ;
CCNOT ( q [10] , q [11] , q [12]) ;
CCNOT ( q [12] , q [13] , q [14]) ;
CCNOT ( q [14] , q [15] , q [18]) ;
CCNOT ( q [18] , q [17] , q [16]) ;
CCNOT ( q [14] , q [15] , q [18]) ;

59
CCNOT ( q [12] , q [13] , q [14]) ;
CCNOT ( q [10] , q [11] , q [12]) ;
CCNOT ( q [8] , q [9] , q [10]) ;
CCNOT ( q [6] , q [7] , q [8]) ;
CCNOT ( q [4] , q [5] , q [6]) ;
CCNOT ( q [1] , q [3] , q [4]) ;
CCNOT ( q [4] , q [5] , q [6]) ;
CCNOT ( q [6] , q [7] , q [8]) ;
CCNOT ( q [9] , q [8] , q [10]) ;
CCNOT ( q [10] , q [11] , q [12]) ;
CCNOT ( q [12] , q [13] , q [14]) ;
CCNOT ( q [14] , q [15] , q [18]) ;
CCNOT ( q [13] , q [14] , q [17]) ;
CCNOT ( q [11] , q [12] , q [13]) ;
CCNOT ( q [9] , q [10] , q [11]) ;
CCNOT ( q [7] , q [8] , q [9]) ;
CCNOT ( q [5] , q [6] , q [7]) ;
CCNOT ( q [3] , q [4] , q [5]) ;
CCNOT ( q [0] , q [2] , q [3]) ;
CCNOT ( q [3] , q [4] , q [5]) ;
CCNOT ( q [5] , q [6] , q [7]) ;
CCNOT ( q [7] , q [8] , q [9]) ;
CCNOT ( q [9] , q [10] , q [11]) ;
CCNOT ( q [11] , q [12] , q [13]) ;
CCNOT ( q [13] , q [14] , q [17]) ;
CCNOT ( q [11] , q [12] , q [13]) ;
CCNOT ( q [9] , q [10] , q [11]) ;
CCNOT ( q [7] , q [8] , q [9]) ;
CCNOT ( q [5] , q [6] , q [7]) ;
CCNOT ( q [3] , q [4] , q [5]) ;
CCNOT ( q [0] , q [2] , q [3]) ;
CCNOT ( q [3] , q [4] , q [5]) ;
CCNOT ( q [5] , q [6] , q [7]) ;
CCNOT ( q [7] , q [8] , q [9]) ;
CCNOT ( q [9] , q [10] , q [11]) ;
CCNOT ( q [11] , q [12] , q [13]) ;
CCNOT ( q [17] , q [18] , q [16]) ;
CCNOT ( q [14] , q [15] , q [18]) ;
CCNOT ( q [12] , q [13] , q [14]) ;
CCNOT ( q [10] , q [11] , q [12]) ;
CCNOT ( q [8] , q [9] , q [10]) ;
CCNOT ( q [6] , q [7] , q [8]) ;
CCNOT ( q [4] , q [5] , q [6]) ;
CCNOT ( q [1] , q [3] , q [4]) ;
CCNOT ( q [4] , q [5] , q [6]) ;
CCNOT ( q [6] , q [7] , q [8]) ;
CCNOT ( q [8] , q [9] , q [10]) ;
CCNOT ( q [10] , q [11] , q [12]) ;
CCNOT ( q [12] , q [13] , q [14]) ;
CCNOT ( q [14] , q [15] , q [18]) ;

60
 CCNOT ( q [18] , q [17] , q [16]) ;
CCNOT ( q [14] , q [15] , q [18]) ;
CCNOT ( q [12] , q [13] , q [14]) ;
CCNOT ( q [10] , q [11] , q [12]) ;
CCNOT ( q [8] , q [9] , q [10]) ;
CCNOT ( q [6] , q [7] , q [8]) ;
CCNOT ( q [4] , q [5] , q [6]) ;
CCNOT ( q [1] , q [3] , q [4]) ;
CCNOT ( q [4] , q [5] , q [6]) ;
CCNOT ( q [6] , q [7] , q [8]) ;
CCNOT ( q [9] , q [8] , q [10]) ;
CCNOT ( q [10] , q [11] , q [12]) ;
CCNOT ( q [12] , q [13] , q [14]) ;
CCNOT ( q [14] , q [15] , q [18]) ;
H ( q [16]) ;
}
}
.1.6.2 Diffusion operation:

operation Diffusion ( q : Qubit []) : ()

{
body
{
for ( i in 0..15)
{
H ( q [ i ]) ;
}
for ( i in 0..15)
{
X ( q [ i ]) ;
}

H ( q [15]) ;
CCNOT ( q [13] , q [14] , q [17]) ;
CCNOT ( q [11] , q [12] , q [13]) ;
CCNOT ( q [9] , q [10] , q [11]) ;
CCNOT ( q [7] , q [8] , q [9]) ;
CCNOT ( q [5] , q [6] , q [7]) ;
CCNOT ( q [3] , q [4] , q [5]) ;
CCNOT ( q [0] , q [2] , q [3]) ;
CCNOT ( q [3] , q [4] , q [5]) ;
CCNOT ( q [5] , q [6] , q [7]) ;
CCNOT ( q [7] , q [8] , q [9]) ;
CCNOT ( q [9] , q [10] , q [11]) ;
CCNOT ( q [11] , q [12] , q [13]) ;
CCNOT ( q [13] , q [14] , q [17]) ;
CCNOT ( q [11] , q [12] , q [13]) ;
CCNOT ( q [9] , q [10] , q [11]) ;
CCNOT ( q [7] , q [8] , q [9]) ;

61
CCNOT ( q [5] , q [6] , q [7]) ;
CCNOT ( q [3] , q [4] , q [5]) ;
CCNOT ( q [0] , q [2] , q [3]) ;
CCNOT ( q [3] , q [4] , q [5]) ;
CCNOT ( q [5] , q [6] , q [7]) ;
CCNOT ( q [7] , q [8] , q [9]) ;
CCNOT ( q [9] , q [10] , q [11]) ;
CCNOT ( q [11] , q [12] , q [13]) ;
CCNOT ( q [14] , q [17] , q [15]) ;
CCNOT ( q [12] , q [13] , q [14]) ;
CCNOT ( q [10] , q [11] , q [12]) ;
CCNOT ( q [8] , q [9] , q [10]) ;
CCNOT ( q [6] , q [7] , q [8]) ;
CCNOT ( q [4] , q [5] , q [6]) ;
CCNOT ( q [1] , q [3] , q [4]) ;
CCNOT ( q [4] , q [5] , q [6]) ;
CCNOT ( q [6] , q [7] , q [8]) ;
CCNOT ( q [8] , q [9] , q [10]) ;
CCNOT ( q [10] , q [11] , q [12]) ;
CCNOT ( q [12] , q [13] , q [14]) ;
CCNOT ( q [14] , q [17] , q [15]) ;
CCNOT ( q [12] , q [13] , q [14]) ;
CCNOT ( q [10] , q [11] , q [12]) ;
CCNOT ( q [8] , q [9] , q [10]) ;
CCNOT ( q [6] , q [7] , q [8]) ;
CCNOT ( q [4] , q [5] , q [6]) ;
CCNOT ( q [1] , q [3] , q [4]) ;
CCNOT ( q [4] , q [5] , q [6]) ;
CCNOT ( q [6] , q [7] , q [8]) ;
CCNOT ( q [8] , q [9] , q [10]) ;
CCNOT ( q [10] , q [11] , q [12]) ;
CCNOT ( q [12] , q [13] , q [14]) ;
CCNOT ( q [13] , q [14] , q [17]) ;
CCNOT ( q [11] , q [12] , q [13]) ;
CCNOT ( q [9] , q [10] , q [11]) ;
CCNOT ( q [7] , q [8] , q [9]) ;
CCNOT ( q [5] , q [6] , q [7]) ;
CCNOT ( q [3] , q [4] , q [5]) ;
CCNOT ( q [0] , q [2] , q [3]) ;
CCNOT ( q [3] , q [4] , q [5]) ;
CCNOT ( q [5] , q [6] , q [7]) ;
CCNOT ( q [7] , q [8] , q [9]) ;
CCNOT ( q [9] , q [10] , q [11]) ;
CCNOT ( q [11] , q [12] , q [13]) ;
CCNOT ( q [13] , q [14] , q [17]) ;
CCNOT ( q [11] , q [12] , q [13]) ;
CCNOT ( q [9] , q [10] , q [11]) ;
CCNOT ( q [7] , q [8] , q [9]) ;
CCNOT ( q [5] , q [6] , q [7]) ;
CCNOT ( q [3] , q [4] , q [5]) ;

62
 CCNOT ( q [0] , q [2] , q [3]) ;
CCNOT ( q [3] , q [4] , q [5]) ;
CCNOT ( q [5] , q [6] , q [7]) ;
CCNOT ( q [7] , q [8] , q [9]) ;
CCNOT ( q [9] , q [10] , q [11]) ;
CCNOT ( q [11] , q [12] , q [13]) ;
CCNOT ( q [14] , q [17] , q [15]) ;
CCNOT ( q [12] , q [13] , q [14]) ;
CCNOT ( q [10] , q [11] , q [12]) ;
CCNOT ( q [8] , q [9] , q [10]) ;
CCNOT ( q [6] , q [7] , q [8]) ;
CCNOT ( q [4] , q [5] , q [6]) ;
CCNOT ( q [1] , q [3] , q [4]) ;
CCNOT ( q [4] , q [5] , q [6]) ;
CCNOT ( q [6] , q [7] , q [8]) ;
CCNOT ( q [8] , q [9] , q [10]) ;
CCNOT ( q [10] , q [11] , q [12]) ;
CCNOT ( q [12] , q [13] , q [14]) ;
CCNOT ( q [14] , q [17] , q [15]) ;
CCNOT ( q [12] , q [13] , q [14]) ;
CCNOT ( q [10] , q [11] , q [12]) ;
CCNOT ( q [8] , q [9] , q [10]) ;
CCNOT ( q [6] , q [7] , q [8]) ;
CCNOT ( q [4] , q [5] , q [6]) ;
CCNOT ( q [1] , q [3] , q [4]) ;
CCNOT ( q [4] , q [5] , q [6]) ;
CCNOT ( q [6] , q [7] , q [8]) ;
CCNOT ( q [8] , q [9] , q [10]) ;
CCNOT ( q [10] , q [11] , q [12]) ;
CCNOT ( q [12] , q [13] , q [14]) ;

H ( q [15]) ;

for ( i in 0..15)
{
X ( q [ i ]) ;
}

for ( i in 0..15)
{
H ( q [ i ]) ;
}
}
}

63
.1.6.3 Set operation:

operation Set ( desired : Result , q1 : Qubit ) : ()

{
body
{
let current = M ( q1 ) ;
if ( desired != current )
{
X ( q1 ) ;
}
}
}
.1.6.4 Search operation:

operation Search () : ( Result [])

{
body
{
mutable resultSet = new Result [16];
using ( q = Qubit [19])
{
let databaseRegister = q [0..15];
for ( i in 0..16)
{
H ( q [ i ]) ;
}

for ( i in 0..200) {
Oracle ( q ) ;
Diffusion ( q ) ;
}
set resultSet = MultiM ( databaseRegister ) ;

for ( i in 0..18)
{
Set ( Zero , q [ i ]) ;
}
}

return ( resultSet ) ;
}
}

64
.1.6.5 C# Driver class:

class Driver
{

static void Main ( string [] args )

{
int num = 5;
int count = 0 , flag = 0;
using ( var sim = new QuantumSimulator () )
{
for ( int i =0; i < num ; i ++) {
flag = 0;
var res = Search . Run ( sim ) . Result ;
var register = res ;
System . Console . WriteLine ( $ " { register . ToString () }\ n
");
foreach ( Result r in register ) {
if ( r . Equals ( Result . Zero ) ) {
flag = 1;
break ;
}
}
if ( flag == 0) {
count ++;
}
}
}
System . Console . WriteLine ( $ " Probability = {( double ) count /
num } " ) ;
System . Console . WriteLine ( " Press any key to continue .. " ) ;
System . Console . ReadKey () ;
}
}

View publication stats 65