The effect of a quantum circuit on a quantum state can be expressed by specifying the unitary complex matrix that the circuit denotes. This notion of denotation can be expressed compositionally by inductively defining the denotation of sub-circuits and by relating the denotation of a composed circuit by composing the denotation of sub-circuits. Concretely, the state of an n-qubit quantum computer can be represented by a 2ⁿ complex vector and the denotation of an n-qubit quantum circuit can be expressed by a 2ⁿ × 2ⁿ unitary complex matrix. Based on the denotational semantics of a quantum circuit, it is straightforward, on a classical computer, to simulate the effect of the quantum circuit, simply by applying the unitary matrix, denoted by the circuit, on the incoming state vector. For small n, this strategy works well whereas for larger n (e.g., n > 8), the size of the unitary matrix becomes a limiting factor. A question emerges. Can we do better?

In this paper we derive a purely functional interpreter for quantum circuits that operates directly on a circuit without first constructing the unitary matrix that the circuit denotes. The interpreter takes as input an n-qubit quantum circuit and a complex state vector of size 2ⁿ and outputs a resulting state vector also of size 2ⁿ. We demonstrate the performance benefits of the approach and highlight some of its promises.

Professor in the Programming Languages and Theory of Computation (PLTC) section at Department of Computer Science, University of Copenhagen (DIKU). Conducts research in the design and implementation of programming languages, including compilation techniques for functional languages, parallelism, memory management, and program optimisation.