ar X iv : c s . PL / 0 10 30 09 v 2 2 3 N ov 2 00 1 Toward an architecture for quantum programming

It is becoming increasingly clear that, if a useful device for quantum computation will ever be built, it will be embodied by a classical computing machine with control over a truly quantum subsystem, this apparatus performing a mixture of classical and quantum computation. This paper investigates a possible approach to the problem of programming such machines: a template high level quantum language is presented which complements a generic general purpose classical language with a set of quantum primitives. The underlying scheme involves a run-time environment which calculates the byte-code for the quantum operations and pipes it to a quantum device controller or to a simulator. This language can compactly express existing quantum algorithms and reduce them to sequences of elementary operations; it also easily lends itself to automatic, hardware independent , circuit simplification. A publicly available preliminary implementation of the proposed ideas has been realized using the C++ language. In the last decade the field of quantum computing has raised large interest among physicists, mathematicians and computer scientists due to the possibility of solving at least some " hard " problems exponentially faster than with the familiar classical computers . Relevant efforts have been concentrated in two directions: on one hand a (still not so large) set of quantum algorithms exploiting features inherent to the basic postulates of quantum mechanics has been developed ; on the other hand a number of experimental schemes have been proposed which could support the execution of these algorithms, moving quantum computation from the realm of speculation to reality (see a review of basic requirements in DiVincenzo ). The link between these two areas is a framework for describing feasible quantum algorithms , namely a computational model, which appears to have settled down to the quantum circuit model 1 , due to Deutsch [4], Bernstein and Vazirani  and Yao . Though this is satisfactory from the point of view of computational complexity theory, it is not enough for a practical use (programming) of quantum computers, once they will become available. 1 Different computational models, involving physical systems with continuous-variable quantum systems used as computational spaces, are far less developed and will not be considered in this paper. It should be noted however that any such quantum device will most likely require very different interface abstractions from quantum circuits.

Related papers:

title: Quantum algorithms revisited
abstract: Quantum computers use the quantum interference of different computational paths to enhance correct outcomes and suppress erroneous outcomes of computations. A common pattern underpinning quantum algorithms can be identified when quantum computation is viewed as multiparticle interference. We use this approach to review (and improve) some of the existing quantum algorithms and to show how they are related to different instances of quantum phase estimation. We provide an explicit algorithm for generating any prescribed interference pattern with an arbitrary precision.

title: The Physical Implementation of Quantum Computation
abstract: After a brief introduction to the principles and promise of quantum information processing, the requirements for the physical implementation of quantum computation are discussed. These five requirements, plus two relating to the communication of quantum information, are extensively ex- plored and related to the many schemes in atomic physics, quantum optics, nuclear and electron magnetic resonance spectroscopy, superconducting electronics, and quantum-dot physics, for achiev- ing quantum computing. I.  The advent of quantum information processing, as an abstract concept, has given birth to a great deal of new thinking, of a very concrete form, about how to create physical computing devices that operate in the hitherto unexplored quantum mechanical regime. The efforts now underway to produce working laboratory devices that perform this profoundly new form of information pro- cessing are the subject of this book. In this chapter I provide an overview of the common objectives of the investigations reported in the remain- der of this special issue. The scope of the approaches, proposed and underway, to the implementation of quan- tum hardware is remarkable, emerging from specialties in atomic physics (1), in quantum optics (2), in nuclear (3) and electron (4) magnetic resonance spectroscopy, in su- perconducting device physics (5), in electron physics (6), and in mesoscopic and quantum dot research (7). This amazing variety of approaches has arisen because, as we will see, the principles of quantum computing are posed using the most fundamental ideas of quantum mechanics, ones whose embodiment can be contemplated in virtually every branch of quantum physics. The interdisciplinary spirit which has been fostered as a result is one of the most pleasant and remarkable fea- tures of this field. The excitement and freshness that has been produced bodes well for the prospect for discovery, invention, and innovation in this endeavor.

title: Quantum computational networks
abstract: The theory of quantum computational networks is the quantum generalization of the theory of logic circuits used in classical computing machines. Quantum gates are the generalization of classical logic gates. A single type of gate, the universal quantum gate, together with quantum ‘unit wires’, is adequate for constructing networks with any possible quantum computational property.

title: Quantum complexity theory
abstract: In this dissertation we study quantum computation from a complexity theoretic viewpoint. Our first result is the existence of an efficient universal quantum Turing Machine in Deutsch's model of a quantum Turing Machine. This construction is substantially more complicated than the corresponding construction for classical Turing Machines--in fact, even simple primitives such as looping, branching and composition are not straightforward in the context of quantum Turing Machines. We establish how these familiar primitives can be implemented, and also introduce some new, purely quantum mechanical primitives, such as changing the computational basis, and carrying out an arbitrary unitary transformation of polynomially bounded dimension. 
We also consider the precision to which the transition amplitudes of a quantum Turing Machine need to be specified. We prove that O(log T) bits of precision suffice to support a T step computation. This justifies the claim that the quantum Turing Machine model should be regarded as a discrete model of computation and not an analog one. 
We give the first evidence indicating that quantum Turing Machines are more powerful than classical probabilistic Turing Machines. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing Machine, but requires super-polynomial time on a bounded-error probabilistic Turing Machine; and thus not in the class BPP. In fact, we show that this problem cannot be solved in MA relative to the same oracle, thus showing that even non-determinism together with randomness is not sufficient to solve the problem in poly-nomial time. The class BQP, of languages that are efficiently decidable (with small error-probability) on a quantum Turing Machine, satisfies: BPP $\subseteq$ BQP $\subseteq$ P$\sp{\sharp P}$. Therefore there is no possibility of giving a mathematical proof that quantum Turing Machines are more powerful than classical probabilistic Turing Machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory. 
We also give evidence suggesting that quantum Turing Machines cannot efficiently solve all of NP. Specifically, we prove that relative to an oracle chosen uniformly at random, with probability 1, the class NP cannot be solved on a quantum Turing machine in time $o(2\sp{n/2}).$

title: Quantum circuit complexity
abstract: We propose a complexity model of quantum circuits analogous to the standard (acyclic) Boolean circuit model. It is shown that any function computable in polynomial time by a quantum Turing machine has a polynomial-size quantum circuit. This result also enables us to construct a universal quantum computer which can simulate, with a polynomial factor slowdown, a broader class of quantum machines than that considered by E. Bernstein and U. Vazirani (1993), thus answering an open question raised by them. We also develop a theory of quantum communication complexity, and use it as a tool to prove that the majority function does not have a linear-size quantum formula.<<ETX>>

title: Conventions for quantum pseudocode
abstract: A few conventions for thinking about and writing quantum pseudocode are proposed. The conventions can be used for presenting any quantum algorithm down to the lowest level and are consistent with a quantum random access machine (QRAM) model for quantum computing. In principle a formal version of quantum pseudocode could be used in a future extension of a conventional language.

title: Programmable Quantum Gate Arrays
abstract: We show how to construct quantum gate arrays that can be programmed to perform different unitary operations on a data register, depending on the input to some program register. It is shown that a universal quantum gate array\char22{}a gate array which can be programmed to perform any unitary operation\char22{}exists only if one allows the gate array to operate in a probabilistic fashion. Thus it is not possible to build a fixed, general purpose quantum computer which can be programmed to perform an arbitrary quantum computation.

title: Theory of quantum computation
abstract: Short review article on quantum computation accepted for Supplement III, Encyclopaedia of Mathematics (publication expected Summer 2001). See also this http URL

title: An approximate Fourier transform useful in quantum factoring", IBM Research Report RC19642 ,; R. Cle
abstract: We define an approximate version of the Fourier transform on $2^L$ elements, which is computationally attractive in a certain setting, and which may find application to the problem of factoring integers with a quantum computer as is currently under investigation by Peter Shor. (1994 IBM Internal Report)

title: C++ Programming Language
abstract: From the Publisher: 
Written by Bjarne Stroustrup, the creator of C, this is the world's most trusted and widely read book on C. 
 
For this special hardcover edition, two new appendixes on locales and standard library exception safety have been added. The result is complete, authoritative coverage of the C language, its standard library, and key design techniques. Based on the ANSI/ISO C standard, The C Programming Language provides current and comprehensive coverage of all C language features and standard library components. 
 
For example: 
abstract classes as interfaces class hierarchies for object-oriented programming templates as the basis for type-safe generic software exceptions for regular error handling namespaces for modularity in large-scale software run-time type identification for loosely coupled systems the C subset of C for C compatibility and system-level work standard containers and algorithms standard strings, I/O streams, and numerics C compatibility, internationalization, and exception safety 
Bjarne Stroustrup makes C even more accessible to those new to the language, while adding advanced information and techniques that even expert C programmers will find invaluable.

title: Addition on a Quantum Computer
abstract: A new method for computing sums on a quantum computer is introduced. This technique uses the quantum Fourier transform and reduces the number of qubits necessary for addition by removing the need for temporary carry bits. This approach also allows the addition of a classical number to a quantum superposition without encoding the classical number in the quantum register. This method also allows for massive parallelization in its execution.

title: Logical reversibility of computation
abstract: The usual general-purpose computing automaton (e.g.. a Turing machine) is logically irreversible- its transition function lacks a single-valued inverse. Here it is shown that such machines may he made logically reversible at every step, while retainillg their simplicity and their ability to do general computations. This result is of great physical interest because it makes plausible the existence of thermodynamically reversible computers which could perform useful computations at useful speed while dissipating considerably less than kT of energy per logical step. In the first stage of its computation the logically reversible automaton parallels the corresponding irreversible automaton, except that it saves all intermediate results, there by avoiding the irreversible operation of erasure. The second stage consists of printing out the desired output. The third stage then reversibly disposes of all the undesired intermediate results by retracing the steps of the first stage in backward order (a process which is only possible because the first stage has been carried out reversibly), there by restoring the machine (except for the now-written output tape) to its original condition. The final machine configuration thus contains the desired output and a reconstructed copy of the input, but no other undesired data. The foregoing results are demonstrated explicitly using a type of three-tape Turing machine. The biosynthesis of messenger RNA is discussed as a physical example of reversible computation.

title: Elementary gates for quantum computation.
abstract: We show that a set of gates that consists of all one-bit quantum gates (U(2)) and the two-bit exclusive-or gate (that maps Boolean values (x,y) to (x,x ⊕y)) is universal in the sense that all unitary operations on arbitrarily many bits n (U(2 n )) can be expressed as compositions of these gates. We investigate the number of the above gates required to implement other gates, such as generalized Deutsch-Toffoli gates, that apply a specific U(2) transformation to one input bit if and only if the logical AND of all remaining input bits is satisfied. These gates play a central role in many proposed constructions of quantum computational networks. We derive upper and lower bounds on the exact number of elementary gates required to build up a variety of two- and three-bit quantum gates, the asymptotic number required for n-bit Deutsch-Toffoli gates, and make some observations about the number required for arbitrary n-bit unitary operations.

title: A fast quantum mechanical algorithm for database search
abstract: were proposed in the early 1980’s [Benioff80] and shown to be at least as powerful as classical computers an important but not surprising result, since classical computers, at the deepest level, ultimately follow the laws of quantum mechanics. The description of quantum mechanical computers was formalized in the late 80’s and early 90’s [Deutsch85][BB92] [BV93] [Yao93] and they were shown to be more powerful than classical computers on various specialized problems. In early 1994, [Shor94] demonstrated that a quantum mechanical computer could efficiently solve a well-known problem for which there was no known efficient algorithm using classical computers. This is the problem of integer factorization, i.e. testing whether or not a given integer, N, is prime, in a time which is a finite power of o (logN) .