The All-Seeing Oracle

• This blog post is written as part of the Q# Advent Calendar - December 2020

Background on Quantum Computation

December 19, 1947 revolutionized our world as we know it. On this day, Bell Labs successfully demonstrated the transistor for the first time. These pieces of hardware have evolved over the last decades to create the computers and phones that we use today. Over the last seven decades transistors have grown massively more powerful while physically shrinking to be incredibly tiny. However, transistors will soon become so small that they will be on the same distance scale as electron tunneling - a quantum mechanical phenomena allowing the electron to tunnel through the transistor, even when it ‘physically’ shouldn’t be able to. As we’ve approached this limit, the field of quantum computation has simultaneously grown and gained traction. Quantum computers utilize quantum mechanical properties to perform their computations and are built upon qubits, rather than transistors, which emulate classical bits. In the quantum regime, electron tunneling is not an issue. 

Qubits can be thought of as a classical bit put into a superposition state. Quantum superposition, along with other quantum mechanical phenomena, are the key to the amazing results of quantum computation, such as Grover’s algorithm which provides a quadratic speed up to its classical counterpart. Grover’s search algorithm, along with many other quantum algorithms, require quantum oracles as input to perform their computations. Quantum oracles implement an arbitrary classical function and deterministically convert input to some output. A simple example is a quantum oracle that produces a one if the input is the number seven and a zero otherwise. Such oracles are assumed to be provided in quantum algorithms - a strong assumption! Generally, in quantum computation courses, oracles are assumed to simplify the details of an algorithm but someone must implement these oracles for the algorithms to work.

My Quantum Journey

Quantum computation has long been a land of legends to me. I am a computer science and physics double major and I’ve had the chance to take three amazing courses on quantum mechanics at my university, however I had yet to work in the space of quantum computation. This past quarter the University of Washington’s computer science department offered CSE 490Q, a graduate quantum computation course. I jumped on the opportunity to take CSE 490Q to bridge the gap between my understanding of quantum mechanics and computation. As if luck had not graced me enough already, I found myself armed with a mentorship in Microsoft’s Quantum program under the guidance of Mariia Mykhailova.

During my mentorship I designed and implemented a tutorial on quantum oracles for Microsoft’s open source project The Quantum Katas to address and resolve common misconceptions and confusion regarding quantum oracles. I created an interactive Q# Jupyter Notebook to explain the theory of quantum oracles and offer ample opportunities for the learner to practice implementing quantum oracles. Throughout the tutorial the learner is presented with demos, mathematical derivations, and tasks to provide different learning mediums to round out their knowledge. The demonstrations show what a quantum oracle does to its input, the mathematical derivations target why the quantum oracle acts the way it does on its input, and finally the tasks teach how to produce the output distribution provided the inputs. Engaging with quantum oracles more meaningfully while creating this tutorial gave me a newfound appreciation of the hidden complexity behind them. Following my initial implementation of the oracles for the tasks, Mariia pointed me towards the great library functions provided in Q# in order to simplify my solutions. Specifically, the most beneficial functions for my purposes were found in Microsoft’s Canon namespace and their Convert namespace, functions such as BoolArrayAsInt and ControlledOnInt abstracted away my previous computations to create a concise and modularized solution. 

Q#’s library of functions is expanding constantly as quantum computation becomes more understood. Microsoft’s current learning materials and programming tools are a great springboard to begin your journey into the world of quantum computation. Alongside these standard libraries, Mariia created the QuantumKatas open source repository (the repository I’ve created this tutorial for) to establish a streamline learning path for software enthusiasts who want to learn more about quantum computation. Creating the tutorial on quantum oracles, under Mariia’s guidance, I became more familiar with the tools that Q# has provided for developers and I’m incredibly excited to see what tools will be available to developers in the future!