Sponsor
Portland State University. Department of Electrical and Computer Engineering
First Advisor
Marek Perkowski
Term of Graduation
Spring 2024
Date of Publication
4-15-2024
Document Type
Dissertation
Degree Name
Doctor of Philosophy (Ph.D.) in Electrical and Computer Engineering
Department
Electrical and Computer Engineering
Language
English
DOI
10.15760/etd.3738
Physical Description
1 online resource (xxii, 301 pages)
Abstract
The field of quantum computing has emerged as a powerful tool for solving and optimizing combinatorial optimization problems. To solve many real-world problems with many variables and possible solutions for constraint satisfaction and optimization problems, the required number of qubits of scalable hardware for quantum computing is the bottleneck in the current generation of quantum computers. In this dissertation, we will demonstrate advanced, scalable building blocks for the quantum search algorithms that have been implemented in Grover's search algorithm and the quantum walk algorithm. The scalable building blocks are used to reduce the required number of qubits in the design. The proposed architecture effectively scales and optimizes the number of qubits needed to solve large problems with a limited number of qubits. Thus, scaling and optimizing the number of qubits that can be accommodated in quantum algorithm design directly reflect on performance. Also, accuracy is a key performance metric related to how accurately one can measure quantum states.
The search space of quantum search algorithms is traditionally created by using the Hadamard operator to create superposition. However, creating superpositions for problems that do not need all superposition states decreases the accuracy of the measured states. We present an efficient quantum circuit design that the user has control over to create the subspace superposition states for the search space as needed. Using only the subspace states as superposition states of the search space will increase the rate of correct solutions.
In this dissertation, we will present the implementation of practical problems for Grover's search algorithm and quantum walk algorithm in logic design, logic puzzles, and machine learning problems such as SAT, MAX-SAT, XOR-SAT, and like SAT problems in EDA, and mining frequent patterns for association rule mining.
Rights
© 2024 Abdirahman Sheikh Hassan Alasow
In Copyright. URI: http://rightsstatements.org/vocab/InC/1.0/ This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).
Persistent Identifier
https://archives.pdx.edu/ds/psu/42078
Recommended Citation
Alasow, Abdirahman Sheikh Hassan, "Quantum Search Algorithms for Constraint Satisfaction and Optimization Problems Using Grover's Search and Quantum Walk Algorithms with Advanced Oracle Design" (2024). Dissertations and Theses. Paper 6606.
https://doi.org/10.15760/etd.3738