Study of cubelike graphs for parallel and quantum computation

dc.contributor.guideSunitha, V. and Mulherkar, Jaideep
dc.coverage.spatial
dc.creator.researcherRajdeepak, Rishikant
dc.date.accessioned2023-01-05T12:07:54Z
dc.date.available2023-01-05T12:07:54Z
dc.date.awarded2022
dc.date.completed2022
dc.date.registered2015
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...
dc.description.note
dc.format.accompanyingmaterialNone
dc.format.dimensions30 cm
dc.format.extentxii, 128 p.
dc.identifier.urihttp://hdl.handle.net/10603/437372
dc.languageEnglish
dc.publisher.institutionDepartment of Information and Communication Technology
dc.publisher.placeGandhinagar
dc.publisher.universityDhirubhai Ambani Institute of Information and Communication Technology (DA-IICT)
dc.relationRajdeepak, Rishikant; Study of cubelike graphs for parallel and quantum computation; xii, 128 p.; 2022 (Supervisior: V. Sunitha and Jaideep Mulherkar).
dc.rightsuniversity
dc.source.universityUniversity
dc.subject.keywordEngineering and Technology
dc.subject.keywordComputer Science
dc.subject.keywordComputer Science Software Engineering
dc.titleStudy of cubelike graphs for parallel and quantum computation
dc.title.alternative
dc.type.degreePh.D.

Files

Original bundle

Now showing 1 - 5 of 12
Loading...
Thumbnail Image
Name:
01_title.pdf
Size:
81.36 KB
Format:
Adobe Portable Document Format
Description:
Attached File
Loading...
Thumbnail Image
Name:
02_prelim pages.pdf
Size:
511.03 KB
Format:
Adobe Portable Document Format
Loading...
Thumbnail Image
Name:
03_contents.pdf
Size:
93.08 KB
Format:
Adobe Portable Document Format
Loading...
Thumbnail Image
Name:
04_abstract.pdf
Size:
85.44 KB
Format:
Adobe Portable Document Format
Loading...
Thumbnail Image
Name:
05_chapter 1.pdf
Size:
141.16 KB
Format:
Adobe Portable Document Format

License bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
license.txt
Size:
1.79 KB
Format:
Plain Text
Description: