Scaffold: Quantum Programming Language

Report ID: TR-934-12
Author: Suchara, Martin / Martonosi, Margaret / Abhari, Ali Javadi / Black,John / Brown, Ken / Brun, Todd / Catu, Oana / Chakrabati, Amlan / Chiang, Chen-Fu / Chong, Fred / Dousti, Mohammad Javad / Faruque, Arvin / Pedram, Massoud / Svec, Lukas / Vanderwilt, Seth
Date: 2012-07-00
Pages: 43
Download Formats: |PDF|
Abstract:

Quantum computing is of significant research interest because of its potential to radically alter the performance and asymptotic complexity of certain computations. Over the years, physicists have explored possibilities for how to implement quantum bits and logic devices in hardware. At a higher level, mathematicians and algorithmicists have explored how to express computational problems from diverse fields---such as cryptography, chemical systems simulation, and database search---in terms of mathematical equations potentially implementable in quantum hardware.

For quantum computing to become potentially viable however, research must also make inroads regarding the implementation, compilation, and architectural issues that lie between high-level mathematical algorithm expressions and low-level physical implementations. In particular, we need tools and analysis techniques that can---for a given algorithm and potential physical implementation technology---answer questions like: how much would it cost (i.e., how much resource in terms of qubits, gates, time are required?) to implement the algorithm in this technology? What is its performance potential? Is it scalable? Are there more algorithms that offer such speedups over classical computers?

Our work is building a language and toolflow to answer such questions. This document describes the Scaffold programming language, its design goals, and related tools. Scaffold is a programming language for expressing quantum algorithms. A quantum algorithm can consist of a wide variety of components (including classical and quantum routines) which will be defined using different coding techniques. As a quantum programming language (QPL), Scaffold was formulated to make it easy to express an algorithm with so many disparate components in a clean and efficient manner. It is from this notion of ``putting things together'' that Scaffold derives its name.