Grant: Discovery Grants Program - Individual

The goal of my research program is to devise practical applications for computing devices known as quantum computers. Quantum computers can harness quantum mechanical phenomena. This allows them to efficiently solve certain problems for which no efficient classical methods are known. In 1994, Peter Shor provided the most famous example of such a quantum speedup by proving that quantum computers can factor integers in polynomial time. This running time is in striking contrast with the exponential running time of the best known classical algorithms. In the time since Shor's discovery, many algorithms leveraging the power of quantum computers have been introduced with applications ranging from cryptography to materials science. This promised increase in efficiency has provided great incentive to solve the challenges associated with building quantum computers and the resulting research efforts recently culminated in the development of small but fully programmable quantum computers. Despite this great experimental progress, applications of quantum computers remain distant. According to the current estimates, the cost of running quantum algorithms exceeds by far the most optimistic previsions for hardware growth. As a result, quantum computers are unlikely to solve problems of practical interests using available techniques. One of the main obstacles to the practical application of quantum computers is the overhead incurred when expressing a quantum algorithm as a logical quantum circuit. This process, which maps the abstract description of an algorithm to the explicit description of a quantum circuit, is often carried out using techniques developed more than a decade ago. At the time, these methods were considered sufficient because the challenges associated with building reliable quantum computers were so far from being met. In light of recent experimental progress, however, these methods appear inadequate. My research program aims at reducing the overhead associated with the construction of logical circuits and their decomposition into basic operations. I plan to develop new methods for the construction of quantum circuits and reliable tools for their optimization. I expect that the contributions stemming from my program will have significant effects on the field of quantum computation and will assist in turning quantum computers into instruments of scientific discovery.