The Shape of Code

Q is for QCL.

Quantum computers are still so new that creators of programs languages for them are still including the word quantum in their name. I shouldn’t complain because without them today’s post would be about existing languages with the word quick tacked on the front.

Conventional modern computers contain transistors and while a knowledge of quantum mechanics is required for a detailed understand of how these work, the layman’s explanation can be given using classical terms and does not involve any apparently weird behavior (tunnelling can be skipped as a technical detail). Quantum computers make direct use of superposition and entanglement, both of which are at the very weird end of quantum mechanical effects.

Conventional computers work by toggling the state of transistors between 0/1 (a bit), Quantum computers work by performing unitary transforms on Qubits.

Unitary transforms are reversible (by the definition of the transform). This means that feeding the output value from a Quantum computer back through the output will result in the value of the original input appearing at the input. Sounds interesting until you realise that this places a couple of major restriction on the structure of a quantum program:

• the number of input bits must equal the number of output bits (its ok for some of these bits to be don’t-care bits from the point of view of interpreting them to give an external meaning),
• variables cannot be overwritten (this would destroy information and is not reversible),
• variables cannot be copied (there is no unitary transform available to do this).

Developers coding for parallel processors need to stop complaining, their life could be a lot harder. In fact figuring out how to get a quantum computer to do anything useful is so hard that people have taken to using genetic algorithms to obtain useful practical results (it was a search based software engineering workshop where I first learned about the realities of programming a Quantum computer).

These programming constraints actually make one feel relieved that the largest available Quantum computer only contains 128 Qbits that need to be used up.

It is possible to build a transistor-based reversible computer using Toffoli-gates; it has been shown that such a computer would be capable of performing any computation that a Turing machine could perform. An important theoretical result that shows that Quantum computers are at least as powerful as conventional computers.

Building a Quantum computer is very hard. The basic approach is to prepare a superposed state (perhaps using ion traps or microwaves), then apply unitary transformations in a way that takes advantage of quantum parallelism, followed by gathering up the result and making a measurement. Quantum computers are like ASICs (i.e., they need to be configured to perform one kind of calculation) and not general purpose programmable computers.

Quantum parallelism is what gives Quantum computers the potential for having a huge performance advantage over today’s computers. The poster child for this performance advantage is Shor’s algorithm (which finds the prime factors of very large numbers, such as those used in public key encryption).

Quantum computers are very delicate beasts that are destroyed by interaction with the world around them (e.g., being hit by a passing atom lurking within the near perfect vacuum in which they operate, or a stray photon bouncing around the cavity in which the computer is held).

I have a great idea for hackers wanting to stop a government agency cracking their communication keys using a Quantum computer running Shor’s algorithm. What the hackers need to do is convince the agency that some very large prime numbers are being used as keys, the agency will feed these numbers to the Quantum computer which it will be expecting a solution that contains two smaller numbers and the failure to obtain this expected result will lead the control software to think that the Quantum computer has developed a fault and shut it down (this idea has a few gaps that need filling in, not least is generating the very large prime numbers); Hollywood, I am available as a script adviser.

The commercially available Quantum computer gets around the delicate nature problem by accepting that there will be noise in the output and targeting problems whose solution has some degree of immunity to noise.

What about quantum computer languages? A variety have been created (all work by using simulators running on commodity hardware and including support for some very un-unitary transform like operations): QCL is based on a C-like syntax and supports various quantum operations, and of course the function folk know a good bandwagon when they see it.