Even though the hardware side of quantum computing is still being worked out, it is interesting to consider what would constitute what I call quantum programming, which is writing algorithms or programs that run on quantum computers. Looking back at the recent history of computing, what really made a difference was programming languages. While computation can be viewed as simply manipulating a state, for example a Turning machine, a programming language is a much more expressive, and practically useful construction. In fact programming itself does not need to have anything to do with computers or the hardware. Computers let us evaluate a program and produce output, but the process of reasoning about computation, and reasoning about a problem is a higher level task. A program is a language which expresses a desired computation, but not necessarily on how to specifically implement it to produce a result. Lots of things not traditionally seen as programs are indeed programs, for example, constructions in mathematics like the real numbers are programs, or even a mathematical proof itself is a program. Using a language to formulate and reason about some idea is programming. Historically, a lot of programming languages slowly developed with connections to the underlying hardware, although as processors become more sophisticated there is a growing disconnect. Programming languages like Haskell are declarative, we state what we want, we say what the desired outcome is, and then the compiler figures out how to implement it. We do not manually manipulate the state of the memory of the computer, or the control flow, in a more traditional way, as historically done in something like C or an assembly language. However in a way, they still seem tied to their classical foundations. Even in Haskell, writing an efficient program requires you to have a little bit of an understanding of how things work under the hood. Could it be that the data structures we use in programs are just classical? lists and folds on the surface might feel very classical, but maybe that is only because we use them with classical objects. Maybe all we need to do is actually just implement proper quantum datastructures and manipulate them with the correct functions.
At the moment we seem to be at a very rudimentary stage with regards to quantum computation. A lot of quantum computing seems to be playing around with manually manipulating the state or the control flow. A lot of online tools, or current attempts at quantum programming languages, you can just chain together a bunch of quantum gates. This seems a very labourious way to develop quantum algorithms. It is tying the idea of programming with the hardware. However, maybe quantum computing is not such a big deal after all. If computation or programming is just a language, quantum computing is just a nice way to get a speedboost for certain tasks, a bit like a GPU. If programming is a higher order idea, there is no real quantum programming, it’s already just programming.
So in asking the question what is the analog of declerative programming language but for quantum computers, one answer of course is that we already have it, and its something just like Haskell. We simply need some help from the compiler that can figure out some of the details for us, and we just need some extra datastructures. It could be that quantum computers will simply be like a specialised piece of hardware, just like a GPU. Then of course we only really need some simple DSL like language, and push out tasks that we know will run efficiently on them. So Haskell is already fully compatible, we just need to implement a QState or a QIO monad and then everything is good?
On one hand this doesn’t feel quite right, quantum behaviour is not necessarily as intuitive. Are things like the quantum fourier transform and amplitude amplification hinting at something more abstract? How would a compiler necessarily produce the corresponding circuits from declaring you want the prime factors. Do we take the normal Haskell program for finding prime factors, and instead of using List plug in QState and hope it works out? Setting up your state to get you exactly what you want does seem pretty tied to the hardware, although maybe I am bad at making an efficient compiler.
Often people say quantum compiling is just taking an arbitrary unitary matrix U and then producing a series of quantum gates which approximate it. But what makes certain U more interesting? I would say its more like the output of a quantum compiler, and then what people call quantum compiling is more like quantum assembling, it’s just producing the machine code. If we used the QState approach, and implemented unitary gates U as a monoid which has a bunch of options like swap or CNOT, it seems like you would already have the assembly almost, and when would you actually come across an arbitrary unitary matrix? I feel it’s like if you had some more sophisticated quantum compiler that could actually produce U. Of course looking at assembly code and trying to reverse engineer what programming language it came from is also a hard task. Maybe there is some strange non-commutative internal language for some object that is actuallly “quantum programming”.
On the other, programming should not be tied to the hardware. Programming is just using a language to describe something. So maybe there is really nothing extra to see, and that quantum computing is just some specialised hardware. Quantum programming then probably doesn’t really exist.
Although maybe not actually Haskell, we could imagine that qubits, quantum gates and quantum states could be modelled in Haskell pretty simply. For those that haven’t seen it, in the following code, * means kind, which simply means a type. For example: Int :: *. Quantum computing makes use of the following types:
data Basis = Up | Down
newtype QBit :: *
newtype QState :: * -> *
newtype Unitary :: *Quantum gates are unitary matrices which act on qubits. There are some usual unitary gates, plus conjugation which is reversing the unitary gate.
instance Monoid Unitary
cnot :: QBit -> QBit -> Unitary
rotate :: Integral a => QBit -> a -> Unitary
invert :: Unitary -> UnitaryThe quantum state monad takes in a computational basis state, usually denoted Up or |1>, and Down or |0>. We have a special return that lifts a computational basis state into the quantum state.
instance Monad QState
mQBit :: Basis -> QState QBit
applyU :: Unitary -> QState ()
measure :: QBit -> QState BasisOf course to actually run this, we need actual quantum hardware. The alternative is to embed these into a classical Haskell state monad and them simulate them with our classical computers.