presentation.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Introduction to Q#\n",
    "### Unitary Fund Group meeting\n",
    "\n",
    "Dr. Sarah Kaiser |  [@crazy4pi314](twitter.com/crazy4pi314) |  22 Oct 2020\n",
    "\n",
    "---\n",
    "    \n",
    "  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## 📃Agenda\n",
    " \n",
    "1. Give you a tour of Q# and why I am using it for research, \n",
    "2. show you a case study of using Q# to do research on qRAM, and\n",
    "3. take a look at QIR (quantum intermediate representation) proposal!\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# 📊 What do you know about Q#?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Q\\# : Microsoft's quantum programming language\n",
    "\n",
    "- Open source language domain-specific to quantum computing\n",
    "    - Strongly Typed\n",
    "    - Immutable by default\n",
    "- Used with the [_Quantum Development Kit_](https://www.microsoft.com/en-us/quantum/development-kit) which provides lots of tools for writing and running your programs.\n",
    "- Designed to be integrated with a number of languages/platforms like Python and .NET"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<center>\n",
    "    <img src=\"media/stack.png\" width=\"80%\">\n",
    "</center>\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Design goals:\n",
    "\n",
    "**tl;dr:** Because we want to write algorithms, not circuits."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "### Q\\# Design Requirements:\n",
    "1. Algorithms must be expressed in terms of abstract qubits, rather than physical qubits. \n",
    "2. Algorithms need to allow integrated quantum and classical computation. \n",
    "3. Higher-order protocols such as phase estimation and oblivious amplitude amplification must be expressible.\n",
    "4. Higher-order transformations such as taking the adjoint of an operation must be natively expressible.\n",
    "6. Tasks such as gate synthesis, gate sequence optimization, and ancilla management should be delegated to the compiler. \n",
    "7. Algorithms should be required to respect the laws of physics."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Design Principles:\n",
    "1. Start minimal and evolve carefully based on user experience.\n",
    "2. Be quantum first, familiar second.\n",
    "3. Use libraries wherever possible, rather than language features.\n",
    "4. Keep clear, well-defined semantics to enable rich optimizations and transformations in the compiler back-end."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## What do I write in a Q# program?\n",
    "\n",
    "- **Functions**: `Sin`, `ln`, reversing arrays, etc.\n",
    "    - Deterministic actions, similar to mathematical definition for functions\n",
    "- **Operations**: Everything else 😁 \n",
    "    - Working with qubits is always an operation\n",
    "- _User defined Types_"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Q# Hello World"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "- The `:` here shows you what type an variable or return of a function or operation is\n",
    "- Everything in Q# is `()` in, `()` out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "function Greeting(name : String) : Unit {\n",
    "    Message($\"Hello World! Nice to meet you {name} 💖\");\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "%simulate Greeting name=\"Sarah\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Q# Hello _Quantum_ world"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "open Microsoft.Quantum.Measurement;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "operation Qrng() : Result {\n",
    "    using (qubit = Qubit()) {   // Preparing the qubit\n",
    "        H(qubit);               // Do operation H\n",
    "        return MResetZ(qubit);  // Measure and reset qubit\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "%simulate Qrng"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "## Functions + Types in Q#\n",
    "\n",
    "- Functions are ways to define deterministic, classical calculations.\n",
    "- Q# is a strongly typed language, with a variety of built-in types and ways for you to define your own!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "// Library has the definition of the Complex type we use below.\n",
    "open Microsoft.Quantum.Math;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "// A user defined type for an array of complex numbers.\n",
    "newtype ComplexArray = (Count : Int, Values : Complex[]);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "// Converts an array of real numbers to a ComplexArray\n",
    "function AsComplexArray(data : Double[]) : ComplexArray {\n",
    "\n",
    "    // Start with a new ComplexArray to put your results in\n",
    "    mutable results = ComplexArray(0, new Complex[0]);\n",
    "\n",
    "    for (item in data) {\n",
    "        // update-and-reassign statement\n",
    "        set results w/= Values <- results::Values + [Complex(item, 0.)]; \n",
    "    }\n",
    "    \n",
    "    // Return the results with the Count named item filled out\n",
    "    return results w/ Count <- Length(results::Values); \n",
    "}\n",
    "\n",
    "function ConvertedData() : ComplexArray {\n",
    "    let data = [1.0, 2.0, 3.0];\n",
    "    return AsComplexArray(data);\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "%simulate ConvertedData"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## `using` Qubits in Q#\n",
    "\n",
    "- Qubits are a resource that are requested from the runtime when you need them and returned when you are done.\n",
    "- No distinction on physical/logical\n",
    "- Can also `borrow` qubits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "operation Qrng() : Result {\n",
    "    using (qubit = Qubit()) {   // Preparing the qubit\n",
    "        H(qubit);               // Do operation H\n",
    "        return MResetZ(qubit);  // Measure and reset qubit\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Operations are First Class 🥂\n",
    "- Operations and functions in Q# are first-class entities; they can be passed to other operations, assigned to variables, and used like any other value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "operation ApplyTwice(op : (Qubit => Unit), target : Qubit) : Unit {\n",
    "    op(target);\n",
    "    op(target);\n",
    "}\n",
    "\n",
    "function SquareOperation(op : (Qubit => Unit)) : (Qubit => Unit) {\n",
    "    return ApplyTwice(op, _);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Generating new operations in Q# ##"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "The _functors_ `Adjoint` and `Controlled` allow you to generate new operations without changes to your code to implement those versions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "operation ApplyMultiControlledNOT(control: Qubit[], target : Qubit) : Unit {\n",
    "    // Apply X normally:\n",
    "    // X(target);\n",
    "    \n",
    "    Controlled X(control, target);\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "open Microsoft.Quantum.Diagnostics;\n",
    "\n",
    "operation UseCtlFunctor() : Unit {\n",
    "    using ((controls, target) = (Qubit[2], Qubit())) {\n",
    "    \n",
    "        // Preparing uniform superposition\n",
    "        ApplyToEach(H, controls);\n",
    "        \n",
    "        // Apply our controlledNOT\n",
    "        ApplyMultiControlledNOT(controls, target);\n",
    "        \n",
    "        // Print simulator diagnostics\n",
    "        DumpMachine();\n",
    "        ResetAll(controls + [target]);\n",
    "    }  \n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Q# programs can be run from:\n",
    "\n",
    "- the [command line](https://docs.microsoft.com/en-us/quantum/user-guide/host-programs?tabs=tabid-python#q-from-the-command-prompt), if built as stand-alone applications\n",
    "- [Python](https://docs.microsoft.com/quantum/quickstarts/install-python?tabs=tabid-conda) or [.NET](https://docs.microsoft.com/quantum/quickstarts/install-cs?tabs=tabid-cmdline%2Ctabid-csharp) language programs (C#, F#, etc.) for easy data processing and visualization\n",
    "- [Jupyter notebooks](https://docs.microsoft.com/quantum/quickstarts/install-jupyter?tabs=tabid-conda) with either Q# or Python kernels\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "%simulate UseCtlFunctor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## More than just simulation..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "%lsmagic"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Example target machine: Execution tracing!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "%trace Qrng"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Example target machine: Resource estimation!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "%estimate UseCtlFunctor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Unit testing in Q#\n",
    "\n",
    "- Great way to check that what we have typed matches paper results 😊"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "open Microsoft.Quantum.Arrays;\n",
    "\n",
    "operation AllocateQubitRegister(numQubits : Int) : Unit {\n",
    "\n",
    "    Fact(numQubits > 0, \"Expected a positive number.\");\n",
    "    \n",
    "    using (register = Qubit[numQubits]) {\n",
    "        ApplyToEach(AssertQubit(Zero, _), register);\n",
    "    }\n",
    "    Message(\"Test passed!\");\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "%simulate AllocateQubitRegister numQubits=5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Unit testing in Q# cont.\n",
    "\n",
    "- Helpful to test if qRAM optimizations still do the same thing\n",
    "- Q# uses the _Choi–Jamiłkowski isomorphism_ to make an assertion of operation equivalence to one about preparing states\n",
    "    <!--- We know that if you apply an operation and then it's adjoint, that should be an Identity operation\n",
    "    - Make a channel that applies your operation under test, and then the adjoint of your reference operation.\n",
    "    - If you start with a maximally entangled state, then apply the channel to one half of a maximally entangled state, then you can use state assertions to verify that you still have that same maximally entangled state.-->\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "open Microsoft.Quantum.Diagnostics; \n",
    "\n",
    "operation ApplyCNOT(register : Qubit[])\n",
    ": Unit is Adj + Ctl {\n",
    "    CNOT(register[0], register[1]);\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "operation ApplyCNOTTheOtherWay(register : Qubit[])\n",
    ": Unit is Adj + Ctl {\n",
    "    within {\n",
    "        ApplyToEachCA(H, register);\n",
    "    } \n",
    "    apply {\n",
    "        CNOT(register[1], register[0]);\n",
    "    }\n",
    "}\n",
    "\n",
    "operation CheckThatThisWorks() : Unit {\n",
    "    AssertOperationsEqualReferenced(2, ApplyCNOT, ApplyCNOTTheOtherWay);\n",
    "    Message(\"It works!\");\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%trace CheckThatThisWorks --depth=4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Our plan for qRAM:\n",
    "\n",
    "🧰 **Step 1:** Use functions and operations to implement the qRAM proposals\n",
    "\n",
    "📚 **Step 2:** Use libraries, functors, and other features to reduce how much code we need to write\n",
    "\n",
    "🧪 **Step 3:** Use testing features to make sure our implementations are correct\n",
    "\n",
    "💰 **Step 4:** Profit! (also publish 📃)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Part 2: A case study of Q# driven research: The qRAM library"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Quantum applications _might_ need memory\n",
    "\n",
    "- We need ways to transfer **classical data** to a **quantum system**\n",
    "- _Some_ quantum algorithms, particularly quantum machine learning, assume access to a quantum RAM to load and store data during calculations.\n",
    "- Queries at address $x$ can take many forms: \n",
    "    - Bit value as a phase (Grover's Algorithm): $\\left|x\\right\\rangle\\mapsto(-1)^{b_x}\\left|x\\right\\rangle$\n",
    "    - Bit value as a qubit (Element distinctness): $\\left|x\\right\\rangle\\left|0\\right\\rangle\\mapsto\\left|x\\right\\rangle\\left|b_x\\right\\rangle$\n",
    "    - Bit value as a complex vector of amplitudes (HHL Algorithm): $(b_0...b_n)\\mapsto\\sum\\limits_{j} b_j\\left|j\\right\\rangle$\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Quantum Memories (aka qRAM)\n",
    "\n",
    "**Problem:** It is not clear if we will be able to do this eﬃciently at all, let alone in a fault-tolerant setting. \n",
    "\n",
    " ❗ _An algorithmic speedup **may not** translate to an actual speedup in an application if it is not eﬃcient to use data in the ﬁrst place!_\n",
    "\n",
    "😓 Physical limitations like coherence time, error rates, hardware supported gates, etc. contribute to the difficulty.\n",
    "\n",
    "💡 There are many different approaches, each optimizing for a particular resource. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Deep Dive: qRAM approaches and tradeoffs:\n",
    "\n",
    "#### http://bit.ly/between-the-bitlines\n",
    "\n",
    "<center>\n",
    "    <img src=\"media/olivia-talk-title.png\" width=\"48%\">\n",
    "\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## We need:\n",
    "\n",
    "- A way to implement many different algorithms representing qRAM proposals,\n",
    "- count the resources needed for each proposal, and\n",
    "- do it in an open and reproducible way.\n",
    "\n",
    "<center>\n",
    "    <img src=\"media/wanted.png\" width=\"25%\">\n",
    "</center>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### https://github.com/qsharp-community/qram\n",
    "\n",
    "\n",
    "<center>\n",
    "    <img src=\"media/github-screencap.png\" width=\"50%\">\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Basic layout:\n",
    "\n",
    "```\n",
    "├───📃 docs 📃\n",
    "├───🔮 samples 🔮\n",
    "│   ├───BucketBrigade\n",
    "│   ├───Grover\n",
    "│   ├───Qrom\n",
    "│   ├───ResourceEstimation\n",
    "│   └───SelectSwap\n",
    "├───✨ src ✨\n",
    "└───🧪 tests 🧪\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# `src`: where qRAMs are implemented\n",
    "<center>\n",
    "    <img src=\"media/src-screenshot.png\" width=\"60%\">\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Currently implemented proposals:\n",
    "**qRAM**\n",
    "- Bucket Brigade (bit and phase queries) [0708.1879](https://arxiv.org/abs/0708.1879)\n",
    "\n",
    "**qROM**\n",
    "- Simple [0807.4994](https://arxiv.org/abs/0807.4994)\n",
    "- SELECTSWAP [1812.00954](https://arxiv.org/abs/1812.00954)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Using a qROM"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "%package QSharpCommunity.Libraries.Qram::0.1.35"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Libraries help us bootstrap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "open Microsoft.Quantum.Arrays;\n",
    "open Microsoft.Quantum.Arithmetic;\n",
    "open Microsoft.Quantum.Canon;\n",
    "open Microsoft.Quantum.Convert;\n",
    "open Microsoft.Quantum.Intrinsic;\n",
    "open Microsoft.Quantum.Measurement;\n",
    "open Qram;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Custom Types for quantum memories"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "```\n",
    "newtype QRAM = (\n",
    "    QueryPhase : ((AddressRegister, MemoryRegister, Qubit[]) => Unit is Adj + Ctl),\n",
    "    QueryBit : ((AddressRegister, MemoryRegister, Qubit[]) => Unit is Adj + Ctl), \n",
    "    Write : ((MemoryRegister, MemoryCell) => Unit), \n",
    "    AddressSize : Int,\n",
    "    DataSize : Int\n",
    ");\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## We can use function and custom types to handle classical data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "function ExampleMemoryData() : MemoryBank {\n",
    "    let numDataBits = 3;\n",
    "    let data =  [\n",
    "        (0, IntAsBoolArray(0, numDataBits)), \n",
    "        (2, IntAsBoolArray(5, numDataBits)),\n",
    "        (4, IntAsBoolArray(2, numDataBits)),\n",
    "        (5, IntAsBoolArray(3, numDataBits))\n",
    "    ];\n",
    "    return GeneratedMemoryBank(Mapped(MemoryCell, data));\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Using a qROM (Read Only Memory)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "operation QueryQrom(queryAddress : Int) : Int {\n",
    "    // Generate a (Int, Bool[]) array of data.\n",
    "    let data = ExampleMemoryData();\n",
    "    // Create the QRAM.\n",
    "    let memory = QromOracle(data::DataSet);\n",
    "    using ((addressRegister, targetRegister) = (Qubit[memory::AddressSize], Qubit[memory::DataSize])) {\n",
    "        // Encode our query address\n",
    "        ApplyPauliFromBitString (PauliX, true, IntAsBoolArray(queryAddress, memory::AddressSize), addressRegister);\n",
    "        \n",
    "        // Read from the memory\n",
    "        memory::Read(LittleEndian(addressRegister), targetRegister);\n",
    "        ResetAll(addressRegister);\n",
    "        \n",
    "        // Measure the target register as an integer\n",
    "        return MeasureInteger(LittleEndian(targetRegister));\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Using a qROM"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "```\n",
    "// data: {(0, 0), (2, 5), (4, 2), (5, 3)}\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "%simulate QueryQrom queryAddress=4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "%estimate QueryQrom queryAddress=2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# `tests`: ✔ our work\n",
    "- Can run small instances on simulators\n",
    "- Can verify resource counts on larger instances\n",
    "\n",
    "<center>\n",
    "    <img src=\"media/tests-screenshot.png\" width=\"40%\">\n",
    "</center>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# What's next for the qRAM library?\n",
    "\n",
    "📓 More documentation in an interactive browser\n",
    "\n",
    "📄 Research paper compiling our results\n",
    "\n",
    "❓ More qRAM/qROM proposals "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Part 3: Quantum Intermediate Representation (QIR)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<center>\n",
    "    <img src=\"media/qir.png\" width=\"90%\">\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## QIR Spec\n",
    "\n",
    "#### https://github.com/microsoft/qsharp-language/tree/main/Specifications/QIR\n",
    "- **DRAFT** specification defines an intermediate representation for compiled quantum computations.\n",
    "- Fork of LLVM, so it is easy for users to easily write code analyzers and code transformers that operate at this level, before the final target-specific code generation.\n",
    "    - Cross language circuit optimization as a part of LLVM \"pass\" infrastructure\n",
    "- It is neither required nor expected that any particular execution target actually implement every runtime function specified\n",
    "    - Not limited to gate model QC\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## QIR Projects ##\n",
    "\n",
    "| Project Name | Description | Team | Link |\n",
    "|--------------|-------------|------|------|\n",
    "| DM-Sim       | DM-Sim is a density matrix quantum circuit simulator for multi-GPU accelerated HPC clusters. DIM-Sim is able to scale out to more than a thousand GPUs on ORNL Summit supercomputer, and is able to quickly simulate deep circuit with more than 1 million gates. DM-Sim supports Microsoft Q# through QIR, and IBM Qiskit & Google Cirq through OpenQASM. DIM-Sim provide easy-to-use Python API and C++ API. | Sriram Krishnamoorthy, Ang Li, Bo Fang | https://github.com/pnnl/DM-Sim/blob/master/doc/paper_sc20.pdf |\n",
    "| QCOR         | QCOR is a C++ language extension and associated compiler implementation for heterogeneous quantum-classical computing. QCOR builds off the XACC framework and extends plugin interfaces from Clang to enable quantum kernel expression, compilation, and execution on currently available physical (and virtual) quantum backends. | Alex McCaskey, Thien Nguyen, Daniel Claudino, Anthony Santana, Hal Finkel, Tyler Kharazi, Dmitry Liakh | https://github.com/ornl-qci/qcor |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Example syntax"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "// Assumes that qb1 and qb2 are already in the |0> state\n",
    "operation BellPair(qb1 : Qubit, qb2 : Qubit) : Unit\n",
    "{\n",
    "    H(qb1);\n",
    "    CNOT(qb1, qb2);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "```\n",
    "define void @BellPair__body(%Qubit* %qb1, %Qubit* %qb2) {\n",
    "entry:\n",
    "  call void @__quantum__qis__h(%Qubit* %qb1)\n",
    "  call void @__quantum__qis__cnot(%Qubit* %qb1, %Qubit* %qb2)\n",
    "  ret void\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Demo: Q\\# complier plugin that outputs QIR\n",
    "\n",
    "https://github.com/microsoft/qsharp-compiler/blob/feature/qir/QIR-README.md"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# 📝 Review 📝\n",
    "\n",
    "- Q# is a high level, open-source language for writing _quantum algorithms_ in a portable and reproducable way ✔\n",
    "- We have implemented a number of proposals for qRAMs in a Q# library and are working on resource estimation ✔\n",
    "- QIR is a LLVM forked proposal for an intermediate representation of quantum programs ✔"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Want to start using Q#?\n",
    "\n",
    "📑 [docs.microsoft.com/quantum](https://docs.microsoft.com/quantum)\n",
    "\n",
    "📗 _Learn Quantum Computing with Python and Q#_: [bit.ly/qsharp-book](https://bit.ly/qsharp-book)\n",
    "\n",
    "📺 Live quantum development on Twitch: [twitch.tv/crazy4pi314](https://twitch.tv/crazy4pi314)\n",
    "\n",
    "🤝 Q# community group: [qsharp.community](https://qsharp.community)\n",
    "\n",
    "🧩 Template repo for Q# projects complete with LaTeX paper setup [github.com/cgranade/quantum-research-template](https://github.com/cgranade/quantum-research-template)\n"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Q#",
   "language": "qsharp",
   "name": "iqsharp"
  },
  "language_info": {
   "file_extension": ".qs",
   "mimetype": "text/x-qsharp",
   "name": "qsharp",
   "version": "0.12"
  },
  "livereveal": {
   "autolaunch": true,
   "scroll": true
  },
  "rise": {
   "controls": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}