Please use this identifier to cite or link to this item:
Title: Problem Solving using Quantum Computing and Quantum Clique Algorithm
Authors: Kaur, Mandeep
Supervisor: Garg, Lalit
Keywords: quantum algorithm;quantum clique algorithm;quantum computation;shor’s factoring algorithm
Issue Date: 1-May-2007
Abstract: Quantum Computers are being proposed as new devices for computing. They are based on the principles of quantum mechanics. A key difference between the classical computer and a quantum computer is that a classical computer obeys the well-understood laws of classical physics whereas a quantum computer is a device that harnesses physical phenomenon unique to quantum mechanics to realize a fundamentally new mode of information processing. Quantum Computation and Quantum Information is the study of the information processing tasks that can be accomplished using quantum mechanical systems. The spectacular promise of quantum computers is to enable new algorithms (called quantum algorithms) that give solutions to problems, requiring exorbitant resources for their solution on a classical computer. A comparison of computability and complexity of a quantum computer to that of a classical computer is done. Specifically we are interested in the questions: can a quantum computer compute any problems that are incomputable classically and can a quantum computer compute problems more efficiently than a classical computer. An attempt has been made to divide the problems into three broad categories from view of quantum computing. These are as follows: · Problems that can be efficiently solved by quantum computers, i.e. they provide exponential speed-up as compared to their classical counterparts. · Problems for which quantum computers provide polynomial solutions but not exponential speedups, than those provided by their classical counterparts. · Problems that cannot be solved efficiently by either quantum computers or classical computers. The fields of quantum information theory and quantum complexity have been expanding dramatically, with a number of new interesting and important theoretical results. Meanwhile, the development of algorithms has lagged behind, with barely any significant new algorithms discovered other than Shor’s and Grover’s algorithms. We present some guidelines that give insight into designing new quantum algorithms. We choose an NP-Complete problem – Clique Problem and show that it is one of those problems that can gain speed-ups using quantum computing. The proposed quantum algorithm for clique problem reformulates it as a search problem and uses Grover’s search algorithm and quantum-counting algorithms, to search for the solutions i.e. cliques in a given graph. It first estimates the number of cliques present in a given graph using the quantum counting algorithm and then apply Grover’s search algorithm for finding those cliques. It offers a great speed-up in comparison with the classical algorithms.
Appears in Collections:Masters Theses@CSED

Files in This Item:
File Description SizeFormat 
92068.pdf449.81 kBAdobe PDFThumbnail

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.