Challenges in Quantum Computing

Abstract

In this thesis, we define the problem of finding feed-through trees in a repeated and symmetric floorplan in a VLSI layout. We first use a classical computation method to solve the same. We then use a quantum computation method employing Grover s search algorithm on an entangled database to show that the searching for all solutions which would take runtime O(2n) on a classical computer takes O (sqrt (2n-m /k)) on a quantum computer in the best case, where n is the number of possible edges, n is the number of symmetries, and k the number of possible solutions. In general, the reduction will be quadratic and not exponential unless the entire floorplan is made of repeated symmetries. newline