Layout-Aware Quantum Circuitry and Algorithmic Extensions to Grover's Algorithm

Lov K. Grover introduced, in 1996, Grover's algorithm as a quantum search algorithm to find all solutions for quantum oracles representing classical problems. My research observed that the Grover diffusion operator of Grover's algorithm gives wrong solutions when Boolean oracles are designed in some logical structures. Therefore, I invented the new "controlled-diffusion operator" for Boolean oracles as a new approach for Grover's algorithm that always correctly solves the problem of Grover's algorithm. Another important problem in quantum computing is designing reliable and cost-effective quantum gates using reversible binary logic. In classical logic design, the stage of logic design can be separated from the stage of mapping topological circuits to geometrical architecture. In contrast to classical logic design, the stages of quantum circuit design are not separable. For practical quantum applications, a quantum circuit is realized (transpiled) into the layout of a real quantum device. For a real quantum device, two factors affect the cost-effective transpilation: the utilization of supported (native) gates and the geometrical connectivity pattern of n neighboring physical qubits, where native gates ensure cost-effective transpilation and n ≥ 2. In this dissertation, I introduced two new approaches to leverage these two factors for real IBM quantum devices. The first approach initializes the uniform distribution for all qubits using IBM native √X gates, instead of using the conventional Hadamard gates, which are IBM non-native gates producing cost-expensive transpilation. The second approach geometrically constructs generic and cost-effective quantum gates using IBM native gates. In literature the Bloch sphere is used as a visualization tool for a quantum gate, which is initially designed using unitary matrices computations. In contrast, I introduced the Bloch sphere approach (BSA) as a "geometrical design tool" to design a quantum gate using the Bloch sphere, which leads to fewer unitary matrices computations. I employed the BSA to design various generic and cost-effective quantum gates and libraries based on the layouts of IBM quantum devices. Using the BSA, I invented two quantum libraries to investigate the trade-off between scalability and reliability, for the purpose of how the input qubits of a quantum gate are routed into the layout of an IBM quantum device and how many ancilla qubits are utilized. Experimentally, for the same layout of an IBM quantum device, I prove that the transpiled quantum circuits of oracles utilizing my two approaches always have lower quantum costs and shorter depths than those of the transpiled quantum circuits of the same oracles utilizing IBM non-native gates. In conclusion, my dissertation helps to design correct and more efficient Grover's algorithm and other algorithms (especially oracular search algorithms), using my invented controlled-diffusion operator and my introduced two gate-design approaches.