Methodologies for Quantum Circuit and Algorithm Design at Low and High Levels

Although the concept of quantum computing has existed for decades, the technology needed to successfully implement a quantum computing system has not yet reached the level of sophistication, reliability, and scalability necessary for commercial viability until very recently. Significant progress on this front was made in the past few years, with IBM planning to create a 1000-qubit chip by the end of 2023, and Google already claiming to have achieved quantum supremacy. Other major industry players such as Intel and Microsoft have also invested significant amounts of resources into quantum computing research. Any viable computing system requires both hardware and software to work together harmoniously in order to perform useful computations. While the achievements of IBM and other companies represent a large step forward for quantum hardware, many gaps remain to be filled with respect to the corresponding software. Specifically, there is currently no clear path towards a complete process for translating quantum algorithms into physical operations that are directly executable on quantum hardware. Such a process is analogous to a compiler that translates programs written in a high-level language into executable machine instructions on a conventional digital computer, and it is necessary if quantum computers are to be harnessed to perform practically useful computations. Existing work has addressed individual components of this process, but so far no unified method for translating the whole of a quantum algorithm into executable operations has been described. I make substantial progress towards filling this gap by describing a set of high-level and low-level quantum circuit design techniques, which when taken together reduce the need of a circuit designer to be concerned with low-level details. On the high-level side, I describe an approach or strategy to designing quantum oracles for Grover\u27s algorithm that allows it to be applied to several types of problems. This approach involves designing oracles in terms of high-level blocks such as counters, multiplexers, comparators, and arbitrary Boolean functions. The implementations of these blocks in terms of lower-level quantum gates are demonstrated in a way that makes it clear that scaled-up versions of them can be generated in a completely automated fashion. For a specific class of problems, which I call state-space path planning problems, I also introduce a paradigm for quantum oracle design that involves representing the problem in terms of individual states and moves. Problems of this sort have applications in robotics and games. Low-level techniques that I introduce include methods for realizing both single-output and multiple-output Boolean functions, as well as reversible functions with multiple-valued inputs and outputs, on the quantum gate level. These realization methods can be used to translate the Boolean functions used as high-level blocks in quantum oracle design into low-level gates. The low-level gates used are two-qubit controlled gates such as controlled-NOT and controlled-V whose physical realizations have been extensively studied. In particular, I demonstrate that realizing symmetric functions, which are a subset of Boolean functions, directly using these low-level gates can give better results than the usual method of using higher-level Toffoli gates as intermediates. I also demonstrate that the problem of realizing a reversible Boolean function with many inputs and many outputs in place , that is, using the same qubits to hold the inputs and outputs of the function, can be converted into realizing a sequence of single-output Boolean functions. I describe the realization methods in sufficient detail for a skilled programmer to implement them as part of a CAD tool for quantum circuit design