Please use this identifier to cite or link to this item: http://drsr.daiict.ac.in//handle/123456789/1141
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorSunitha, V.-
dc.contributor.advisorMulherkar, Jaideep-
dc.contributor.authorRajdeepak, Rishikant-
dc.date.accessioned2024-08-22T05:21:09Z-
dc.date.available2024-08-22T05:21:09Z-
dc.date.issued2022-
dc.identifier.citationRajdeepak, Rishikant (2022). Study of Cubelike Graphs for Parallel and Quantum Computation. Dhirubhai Ambani Institute of Information and Communication Technology. xii, 128 p. (Acc. # T01071).-
dc.identifier.urihttp://drsr.daiict.ac.in//handle/123456789/1141-
dc.description.abstractIn this thesis, we study Cayley graphs over Znr for their utility in multiprocessorcomputing and quantum computing. For multiprocessor computing, we investigateproblems of graph embedding on cubelike interconnection networks suchas hypercubes and augmented cubes. These embeddings are required for efficientsimulation of divide-and-conquer based algorithms on multiprocessor systemsbuilt on such interconnection networks. In particular, we discuss Havel�sconjecture which states that an equibipartite binary tree on 2n vertices spans then-dimensional hypercube. We develop an efficient embedding technique to provethe conjecture for a subfamily of equibipartite binary tree. We also worked ona related conjecture which states that a binary tree on 2n vertices spans the ndimensionalaugmented cube. For this, we propose a recursive technique to embedand a method to count the spanning binary trees of the augmented cube. Forexploring the utility of cubelike graphs for quantum computation, we study quantumwalks that can be used to develop quantum algorithms for searching andcommunication. We study both theoretical and experimental aspects of quantumwalks on cubelike graphs as well as Cayley graphs over Znr . For discrete-timequantum walk, our work gives a closed form for the quantum state of the systemassociated with cubelike graphs, after finitely many time steps; this work is thekey to studying hitting times on the graphs which is a measure of how quickly thewalker reaches a specific target node. We also decompose the quantum circuits ofthe corresponding evolution operators that were run on IBM�s quantum computingplatform. We conjecture that there is a linear relation between the quantumhitting times and dimension of cubelike graphs. For continuous-time quantumwalk, we investigate weighted Cayley graphs over Znr in order to classify them into three categories of graphs - those that admit PST, those that do not admit PSTbut are periodic, and those that are not periodic. In continuation to this work, weconstructed quantum circuits of the evolution operators for CTQW on weightedcubelike graphs.-
dc.publisherDhirubhai Ambani Institute of Information and Communication Technology-
dc.subjectCubelike Graphs-
dc.subjectQuantum Computation-
dc.subjectquantum computing-
dc.subjectconquer based algorithms-
dc.classification.ddc511.5 RAJ-
dc.titleStudy of Cubelike Graphs for Parallel and Quantum Computation-
dc.typeThesis-
dc.degreePhD-
dc.student.id201521006-
dc.accession.numberT01071-
Appears in Collections:PhD Theses

Files in This Item:
File SizeFormat 
201521006.pdf1.46 MBAdobe PDFView/Open


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