Bilkent University
Department of Computer Engineering
PhD THESIS PRESENTATION
FROM QUANTUM MODELS TO QUANTUM PROGRAMS: PETRI NETS, ALGORITHMS, AND COMPILATION
Syed Asad Shah
PhD Student
(Supervisor: Prof. Dr.İbrahim Körpeoğlu & Prof. Dr. Yavuz Oruç )
Computer Engineering Department
Bilkent University
Abstract: This thesis introduces a simplified quantum Petri net (QPN) model and uses this model to generalize classical SISO, SIMO, MISO, MIMO, and Priority buffers to their quantum counterparts. It provides a primitive storage element, namely a quantum S-R flip-flop and describes two different such flip-flop designs using quantum NOT, CNOT, CCNOT, and SWAP gates. Each of the quantum S-R flip-flops can be replicated to obtain a quantum register for any given number of qubits. The aforementioned quantum buffers are then obtained using the simpli- fied QPN model and quantum registers. The quantum S-R flip-flop and quantum buffer designs have been tested using OpenQASM 2.0 and Qiskit programs on IBM quantum computers and simulators and the results validate their expected operations. The thesis also addresses the problem of reachability in bounded quantum Petri nets (QPNs). The proposed approach exploits quantum parallelism to construct a superposition over all reachable markings from the initial marking. Grover’s amplitude amplification algorithm is then applied to efficiently identify a desired target marking, while ancillary q-tokens used solely for transition control are ex- cluded from the search space, significantly reducing its size. Theoretical analysis shows that our approach achieves a quadratic speed-up over classical exhaustive algorithms. Experimental results also confirm the correctness and feasibility of the proposed quantum algorithm for solving the bounded reachability problem in Quantum Petri Nets. A quantum algorithm for the Subset Sum Problem is also developed. The proposed approach exploits quantum superposition to represent all candidate subsets simultaneously and uses reversible controlled addition to compute their corresponding subset sums. Grover’s amplitude amplification algorithm is then applied to increase the probability of measuring subsets whose sum matches the desired target. Theoretical analysis shows that our approach achieves a quadratic speed-up over classical exhaustive algorithms. The algorithm is implemented in Q# and evaluated using both valid and invalid target sums. Experimental results obtained using a Q# implementation confirm that the algorithm can correctly identify valid subsets for both single-solution and multiple-solution cases. Finally, the thesis introduces AQASM, an Abstract Quantum Assembly Lan- guage, together with a compiler framework for translating Quantum Intermediate Representation (QIR) programs into a backend-independent assembly represen- tation. AQASM explicitly represents quantum and classical operations, synchro- nization, timing information, and parallel execution. The compiler performs preprocessing, instruction lowering, gate decomposition, dependency analysis, parallel-region generation, synchronization, and abstract scheduling. An abstract backend model with all-to-all qubit connectivity and representative operation du- rations is used to evaluate the compilation and scheduling process without target- ing a specific quantum processor. Experimental evaluation using the Bernstein- Vazirani and quantum Subset Sum programs shows that the compiler correctly translates supported QIR operations, preserves instruction dependencies, identi- fies opportunities for parallel execution, and generates scheduled AQASM pro- grams according to the assumptions of the abstract backend model.
DATE: September 11, Friday @ 13:45
PLACE: Zoom
https://zoom.us/j/2837443344?pwd=NnZJaEpwQklJdUlxNGZtcFhRY0Rjdz09&omn=91451742176
ID: 283 744 3344
Password: 2354290