Chisel-Q: Designing Quantum Circuits with a Scala Embedded Language Xiao Liu and John Kubiatowicz Computer Science Division University of California, Berkeley Email: {xliu, kubitron}@eecs.berkeley.edu Motivation Why Quantum Computers? Great potential to speed up certain computations, such as factorization and quantum mechanical simulation Fascinating exploration of physics Slow but constant research progress New technologies, Computer Architectures, Algorithms Still cannot quite build a large quantum computer Unfortunately, techniques for expressing quantum algorithms are limited: High-level mathematical expressions Low-level sequences of quantum gates Lets see if we can find a better form of expression! Oct 9th, 2013

International Conference on Computer Design Structure of Quantum Algorithms Enclosing Quantum Algorithm Oracle Quantum Algorithms contain two pieces: Enclosing Algorithm Quantum measurement, control structures, I/O Quantum Oracle (black-box function of quantum state) Often specified as classical function, but must handle inputs/ outputs that are superpositions of values Much of the implementation complexity in the Oracles Oct 9th, 2013 International Conference on Computer Design Example: Shors Algorithm Oracles: operate on 2048 or 4096-bit values Modular exponentiation (with embedded operations) Quantum Fourier Transform (QFT) Oct 9th, 2013 International Conference on Computer Design

Compilation Target: The Quantum Circuit Model Quantum Circuit model graphical representation of quantum computing algorithm Time Flows from left to right Single Wires: persistent qubits Double Wires: classical bits Measurement: turns quantum state into classical state Quantum gates typically operate on one or two qubits Universal gate set: Sufficient to form all unitary transformations Oct 9th, 2013 International Conference on Computer Design How to express Quantum Circuits/Algorithms? Graphically: Schematic Capture Systems Several of these have been built QASM: the quantum assembly language Primitives for defining single Qubits, Gates C-like languages Scaffold: some abstraction, modules, fixed loops

Embedded languages Use languages such as Scala or Ruby to build Domain Specific Language (DSL) for quantum circuits Can build up circuit by overriding basic operators Backend generator can add ancilla bits and erasure of information at end of computation for reversibility Oct 9th, 2013 International Conference on Computer Design Starting Point: Berkeley Chisel Scala-based language for digital circuit design High-level functional descriptions of circuits as input Many backends: for instance direct production on Verilog Used in design of new advanced RISC pipeline Features High-level abstraction: higher order functions, advanced libraries, flexible syntax Abstractions build up circuit (netlist) E.g.: Inner-Product FIR Digital Filter: Oct 9th, 2013 International Conference on Computer Design

Quantum Version: Berkeley Chisel-Q in Nutshell Augmented Chisel Syntax, New Backend Generate reversible versions of classical circuits Classical Quantum translation: Map classical gates to quantum gates Add ancilla bits when necessary for reversibility Erase ancilla state at end (decouple ancilla from answer) State machine transformations Supplemental quantum syntax for tuning output Output: Quantum Assembly (QASM) Input to other tools! Goal: Take classical circuits designed in Chisel and produce quantum equivalents Adders, Multipliers Floating-Point processors Oct 9th, 2013 International Conference on Computer Design Chisel-Q Design Flow Chisel-Q piggybacks on basic Chisel design flow Maintains basic parsing infrastructure Internal dataflow format

Output hooks for generating simulators/HDL (e.g. Verilog) Chisel-Q additions: Quantum/Classical Signal Type Analysis Parsing of Quantum Operators Reversible Circuit Generation, Ancilla Erasuree State Machine analysis Output: QASM and statistics about the resulting circuit Gate count, level of parallelism, predicted latency Oct 9th, 2013 International Conference on Computer Design Signal Type Analysis Annotations and dataflow analysis to distinguish classical and quantum signals Use isQuantum annotation on inputs or outputs to indicate quantum datapath Quantum annotations traced through rest of datapath Traced through design hierarchy, sequential loops, Combined quantum and classical signal quantum signal

Classical signals automatically upgraded to quantum Advantages Combine classical control and quantum datapath in same design Classical designs easily transformed to quantum designs simply by annotating enclosing module (subject to some restrictions) Oct 9th, 2013 International Conference on Computer Design Easy Case: Combination Circuits (Ancilla Insertion and Reversal) Gate Level operator mapping: Simple, one for one substitution Addition of ancilla as necessary Reversed circuit generation Leveling the nodes in the dataflow graph Output the nodes in a reversed order In reversed circuit, each node is replaced by the reversed operation from original one Gets tricky only with rotation operators Example: transformation of carry circuit Oct 9th, 2013

International Conference on Computer Design Chisel-Q Optimization Approach Optimization on a case-by-case basis: More like peep-hole optimization than logical optimization Some examples (which get a lot of mileage): For nodes with single-level of fan-out (e.g. direct assignments or NOT operations), avoid introducing new ancillas For nodes with more than one qubit bandwidth and multiple fanouts, we avoid introducing new ancillas when the qubits from that node are disjointedly connected to other nodes For quantum operators, we avoid introducing ancillas Lots of room for improvement! Assume that Chisel-Q output will feed into QASM-compatible optimization toolset Oct 9th, 2013 International Conference on Computer Design Easy Case: Pipeline (Acyclic Dataflow Graph with State) When left alone, qubits act like registers Except for fact that state decays if left too long

Classical circuit with pipelined structure With registers Without loops (acyclic dataflow graph) Easy to identify/handle this type of structure Pipeline registers replaced by multi-input identity elements for synchronization Transformation is similar to combinational circuit Gate mapping, ancilla additions, reversal, Oct 9th, 2013 International Conference on Computer Design Hard Case: State Machine (Sequential Circuits with State) Sequential loops: Very important Widely used by classical designers Includes: state machines, iterative computations, Sequential circuits are challenging: 1. Quantum circuits achieved via classical control cannot handle iteration count based on quantum info 2. Cannot erase state information: must restore ancilla at end of computation Two options for Chisel-Q

Only handle easy cases: Combinational Logic, Pipelines Try to handle at least some sequential circuits Oct 9th, 2013 International Conference on Computer Design Handling Looped Structure Fixed (classically computable) iteration count No data-dependent looping! Use Iteration_Count_Quantum annotation Specified Quantum Completion Signal: Transformation into Fixed iteration count (first case) Use Iteration_Count_Quantum and Done annotations Loop Fixing Transformation Cannot currently handle unspecified (and/or unbounded) termination condition! th Oct 9 , 2013 International Conference on Computer Design

Reversing Ancilla State with Fixed Iterative Structure Save state values before they are overwritten, then use to erase state at end of computation Quantum Stack: LIFO physical structure for holding qubits Natural implementation in, e.g. Ion-trap quantum computer Transformation discussed in paper: State Hoarding Transformation Oct 9th, 2013 International Conference on Computer Design Designing with quantum operators Syntax of Quantum Gates in Chisel-Q Native syntax for quantum circuit design Insert just enough quantum knowledge to improve generated results Specify a complete quantum circuit without intervention from Chisel-Q backend Annotation IsReversed = false to block the

generation of reversed circuit Oct 9th, 2013 International Conference on Computer Design Parameterized Quantum Fourier Transform (QFT) Module Annotation IsReversed = false to block the generation of reversed circuit Oct 9th, 2013 International Conference on Computer Design Mathematical Benchmarks Design Name Description Adder_Ripple Ripple-carry adder designed in classical way. Adder_Ripple_Q Ripple-carry adder designed with quantum gate operators were used; Using designer intuition to recognize very specific

quantum operators. Adder_CLA Carry-lookahead adder designed in classical way. Mul_Booth Multiplier using Booth's algorithm designed in classical way; Quantum annotation are used to describe the iterative operation. Mul_WT Multiplier using Wallace tree structure. Exp_Mul_Booth Exponentiation module with multipliers using Booth's algorithm. Exp_Mul_WT Exponentiation module with multipliers using Wallace tree structure. QFT

Quantum Fourier transform module described in a purely quantum manner; Annotation IsReversed is used to avoid reversed circuit generation. Shor_Exp_Mul Factorization module with Shors algorithm; Including submodule Exp_Mul_WT and QFT. Oct 9th, 2013 International Conference on Computer Design Resource Estimation for Simple Benchmarks Parse the generated QASM Count the required resource Ancilla qubit, different gates, Circuit Before Opt. After Opt. # of Ancilla Qubits

# of Toffoli # of CNOT # of X # of Ancilla Qubits # of Toffoli # of CNOT # of X Adder 1032 188 2094

0 778 188 1586 0 Adder-Q 1001 188 2032 0 32 188 126 0

Mul_WT 17764 6582 37478 124 11101 6582 24152 124 Mul_Booth (Seq) 3704 4860 3811

4428 3598 4860 3387 4428 Exp_MulWT 572411 229018 1174488 36994 365826 229018 761318 36994

Shors_ExpMulWT 573192 229018 1176050 36994 366417 229018 762500 36994 Oct 9th, 2013 International Conference on Computer Design Performance Evaluation for Simple Benchmarks Parallelism: How many quantum operations can be conducted concurrently? Latency: How many steps are required to complete all the operations?

Circuit Latency Parallelis m Min Adder 448 1 190 4.9 Adder-Q 268 1 32 2.2 Mul_WT

756 1 2048 46.4 Mul_Booth (Seq) 39680 1 236 10.4 Exp_MulWT 23543 1 3968

48.9 Shors_ExpMulWT 23792 1 3968 48.4 Oct 9th, 2013 Parallel Parallelis ism Max m Average International Conference on Computer Design Resource Estimation of Components of a RISC Processor Component # of Ancilla Qubits

# of Toffoli # of CNOT # of X ALU 27785 38492 15528 54056 Arbiter 132 95 35 162 Mem. Arbiter

1032 390 1714 488 Locking Arbiter 6856 10800 2776 14626 Flush Unit 357 638 546 474

FPU Decoder 9364 25948 21152 8226 FPU Comparator 271 1100 1037 329 Oct 9th, 2013 International Conference on Computer Design Conclusion Chisel-Q: a high-level quantum circuit design language Powerful Embedded DSL in Scala Classical circuit designers can construct quantum oracles

Translation of combinational logic straightforward Direct substitution of operations and introduction of ancilla bits Generation of reversed circuits to restore ancilla after end of computation Sequential circuits more challenging Must identify maximum number of iterations and completion signals Must save state for later use in restoring ancilla (and erasing information). For future work, we plan to Extend Chisel-Q to a full-blown language for constructing quantumcomputing algorithms Additional optimization heuristics Oct 9th, 2013 International Conference on Computer Design Extra Slides Oct 9th, 2013 International Conference on Computer Design Quantum Bits (Qubits) Qubits can be in a combination of 1 and 0: Written as: = C0|0> + C1|1> The Cs are complex numbers!

Important Constraint: |C0|2 + |C1|2 =1 If measure bit to see what looks like, With probability |C0|2 we will find |0> (say UP) With probability |C1|2 we will find |1> (say DOWN) An n-qubit register can have 2n values simultaneously! 3-bit example: = C000|000>+ C001|001>+ C010|010>+ C011|011>+ C100|100>+ C101|101>+ C110|110>+ C111|111> Oct 9th, 2013 International Conference on Computer Design Parameterized Ripple-carry adder Ripple-carry adder designed in classically and with quantum additions 26 Oct 9th, 2013 International Conference on Computer Design Parameterized Multiplier using Booth's algorithm Iterative operation

annotation Iteration_Count_Quantum Done_Signal_Name_Quantu m Oct 9th, 2013 International Conference on Computer Design Parameterized Factorization module with Shors algorithm Connection of EXP & DFT modules Oct 9th, 2013 International Conference on Computer Design