A Design Language for Quantum Computing

"Current techniques for defining and specifying quantum algorithms are imprecise and to some degree informal, which causes a number of problems: informal descriptions can be ambiguous and difficult to understand, cannot be supported by automated tools (forcomputer algebra, simulation, etc.), and will not scale up as programming tasks become more complex. Formal notations are required, including design techniques familiar from classical programming (modularity, the ability to use different levels ofabstraction) and new techniques for dealing with {\em hybrid\/} calculations that have both classical and quantum components. Since quantum algorithms are more like circuits than like software, we propose to define such a notation and base it on thehardware description language VHDL (for which ATC-NY has developed a mathematical semantics and sophisticated automated analysis tools). We call the notation QHDL (Quantum Hardware Description Language). Phase I work will produce a preliminary design forQHDL and an informal semantics for its type system. It will implement a parser and provide a top-level design for other tools, including a typechecker. The tool set will support techniques for developing algorithms by modifying existing algorithms and bysynthesizing existing components. QHDL will provide two things that the research and engineering communities in quantum computing currently lack: a shared language of interchange (communication) and