Quantum Computing for Dummies

Introduction

Well, quantum computing for programmers anyway. I was curious as to how quantum computers worked and why they are so much better than classical computers for some problems. I turned to the fountain of all knowledge, the internet, and found only high level overviews, misinformation or very technical stuff. In the end, the most accessible thing I found was Quantum Computing for the Determined. It’s very good, but heavy going for a programmer like me. It didn’t seem like the basic concepts were all that difficult, and I still don’t think they are, so I figured the best way to try and understand this was to build a quantum computer simulator. If I could get it to run an algorithm that was exponentially faster on a quantum computer than a classical one, I might be some way to understanding quantum computing. The simulator ended up at less than a hundred (non blank) lines of python even though it’s written in a fairly verbose style. As a bonus, those hundred lines contain the implementation of a quantum algorithm that runs exponentially faster than a classical computer. Unfortunately it’s not possible to run quantum algorithms at full speed on a classical computer, so don’t be expecting to use it to break any encryption algorithms. I’m not really qualified to write this as my background is programming, so constructive criticism is most welcome. I’m not all sure how correct all this information is, but I have a reasonable degree of confidence in the simulator, as it runs a quantum algorithm and gives the expected result.

Quantum Computing

You’ve probably heard of a Qubit. It’s the quantum equivalent of a classical bit. A classical bit can be either 1 or 0. A quantum Qubit can only ever be observed to be 1 or 0, but internally it looks quite different. Think of a clock face with only 8 hours on it, with 8 o’clock at the top. Imagine an hour hand on that clock. If the hour hand is at 4 or 8 o’clock (straight down or straight up), you’ll always observe a one on the Qubit. If the hour hand is at 2 or 6 o’clock (horizontal), you’ll always observe a zero. If the hour hand is at an odd numbered hour, it’ll be 50/50 whether you observe a 0 or a 1. This is known as a superposition of 1 and 0. Once you’ve observed a 1 or a 0 on the Qubit, you’ll always observe a 1 or 0 unless you do something to change it. In fact, it’s as if the act of looking at it moves the hour hand to 8 o’clock or 2 o’clock. We can’t ever see the internal state of a Qubit. That seems to be a fundamental part of quantum mechanics. We’ll only ever see 8 o’clock or 2 o’clock.

Clocks representing all the states of a Qubit

Qubit clocks

 

We can represent a single Qubit with a line pointing in a certain direction, like the hour hand on our clock.

Qubit represented as a vector

Qubit vector

 

The length of the line must always be 1 (corresponding to a probability of 1), so, from Pythagoras, the sum of the squares of x and y must be 1. The probability of a Qubit being in the 1 state is y squared, and the probability of it being in the 0 state is x squared.

More Qubits

We’re going to represent the internal state of our quantum computer simulator as an array of numbers. We’re going to have 1 element for each possible state of the system, and it’s value will be the square root of the probability that the system is in this state. A single Qubit system has 2 possible states, 0 and 1, so it’ll be represented by a 2 element array. One element will correspond to x in the diagram, and the other will correspond to y.

Adding another Qubit doubles the number of possible states the system can be in. Think of it like this: The computer can be in all the states it was before, with the new Qubit set to 0. It can also be in all the states it was before with the new Qubit set to 1. So for a 2 Qubit system, we’d have a 4 element array, and for a 3 Qubit system, we’d have an 8 element array. For a N Qubit system we’d have a pow(2, N) element array.

A quantum computer can act on all of these states in parallel. This is where the power of quantum computers comes from, and makes simulating a quantum computer an NP complete problem. Note that it doesn’t mean quantum computers can solve NP complete problems, because we can only ever observe one of these states. Quantum algorithms can still employ some clever trickery to exploit some of this parallelism. We’ll see one of them in action in our simulator later.

The index to our state array will be the state of our computer. The square of the value of each element will be the probability that the computer is in that state. The initial state of our quantum computer must be known with certainty. This means one element of the state array will have a probability of 1, and all the other elements will have a probability of 0. The element with probability 1 represents the initial known state of the machine.

Our state array is private. This is the same in the real world. We have no way to determine the quantum state until we observe something, at which point a Qubit becomes 0 or 1 with complete certainty. For simplicity, we’re only going to allow observation of Qubits that are in a known state in our simulator. In a real quantum computer you can look at any Qubit, but if it is not in a known state, other Qubits may be affected. Consider for example:

State           sqrt(probability)
 00                        0
 01                        0.5
 10                        0.5
 11                        sqrt(2)/2

State 00 and 10 are the only states with a 0 in the least significant bit. Since state 00 has 0 probability, if you happen to observe a 0 in the least significant Qubit, your computer will definitely be in state 10. So we now know that the most significant Qubit is 1. This is quantum decoherence, and the 2 qubits are said to be entangled with one another.

Quantum Logic Gates

We’re only going to simulate one quantum logic gate in our system, as that’s all that’s required to implement a basic quantum algorithm that is exponentially faster than a classic computer. The gate is called a Hadamard gate. On a single Qubit, all it does is advance the clock by one hour and flip the hour hand. On a 2 Qubit system, our state array is already a 4 dimensional vector, so it’s not possible to visualise. A Hadamard gate applied to a Qubit in the 1 state will result in a Qubit in a state that is equally likely to be 1 or 0. This is called a superposition of 1 and 0 if you remember. I’m not sure why it flips the line. Maybe it’s so that applying it twice gets you back to your starting point, or maybe it’s just easier to implement them with this behaviour.

Hadamard Gate

Hadamard Gate

To apply a Hadamard gate to a single Qubit system with it’s state represented by x and y for 0 and 1 respectively, we transform x and y like this:

x = (x + y) / squareRoot(2)
y = (x - y) / squareRoot(2)

To apply a Hadamard gate to a Qubit in a multi Qubit system, we need to find all the pairs of states that differ by only that Qubit, and apply the transformation above to each pair. The pairs correspond to the 0, or x, axis of the Qubit and the 1, or y, axis of the Qubit.

State       Binary
  0          000
  1          001
  2          010
  3          011
  4          100
  5          101
  6          110
  7          111

For example, the pairs for the least significant bit are:

0, 1 (000, 001)
2, 3 (010, 011)
4, 5 (100, 101)
6, 7 (110, 111)

For the middle Qubit:

0, 2 (000, 010)
1, 3 (001, 011)
4, 6 (100, 110)
5, 7 (101, 111)

And for the most significant qubit:

0, 4 (000, 100)
1, 5 (001, 101)
2, 6 (010, 110)
3, 7 (011, 111)

A Quantum Algorithm

Now all we need is a quantum algorithm to run on our simulator. We’re going to implement the Deutsch-Jozsa algorithm as it’s pretty simple (to implement, if not to understand). It’s not a very useful algorithm, but it is the basis of other quantum algorithms, such as Shor’s for prime factoring. RSA encryption relies on prime factoring being a hard problem, so Shor’s algorithm could be used to break RSA.

The Deutsch-Jozsa algorithm will take a function as it’s input. The function must take a number and map it to either 0 or 1. For every input, we’ll promise that the function will either:

  • Always return 0
  • Always return 1
  • Return 1 or 0, but the same number of inputs will map to 0 as map to 1. For example, a function that returns 1 if the number is even, or 0 if it’s odd.

Deutsch-Jozsa will tell us if the function is constant or not. If you were to solve this problem on a classical computer, worst case you’d have to call the function for half the inputs + 1 to be sure which type of function you had. Deutsch-Jozsa will only call the function once (or rather, it will ask a quantum oracle to transform a carefully crafted superposition of possible states).

Our algorithm requires enough Qubits to represent the number passed to the function, and one extra. So if the input to our function was an 8 bit number, we’d need 9 bits for our algorithm. The extra Qubit will be the first Qubit, just for ease of implementation. This means that the even numbered indexes of the state array correspond to states where the extra bit is 0.

The Quantum Oracle

For each state, the Quantum Oracle will call the function with all the bits of that state, except the extra bit, as input. If the function returns one, the Quantum Oracle will negate the probability root of that state.
Even though the Quantum Oracle and the Hadamard gate are implemented as a loop in our simulator, a quantum computer does all this in parallel. We have to be a bit clever to exploit this parallelism due to the restrictions on observing Qubits.

Implementing The Quantum Algorithm

We’ll start off with our extra Qubit in the 1 state, and every other Qubit in the 0 state. Then we’ll apply the Hadamard gate to each Qubit to create a quantum superposition of every possible state. In other words, every state in which our quantum computer could be is equally likely. You can see this in the log line just before the Quantum Oracle is applied. Next we’ll apply the Quantum Oracle. The 1st Qubit is now irrelevant. Next we apply the Hadamard gate to each of the other Qubits, then we’ll observe them. If they’re all 0, our function was constant, otherwise it isn’t. I’m not going to offer a deeper understanding of how this algorithm works, as I don’t have one at the moment. Maybe I’ll spend more time figuring it out in the future, but for now, here’s the code. Use it at your own risk, but I’m pretty sure it won’t create a black hole or anything like that. It’s written in python and works on version 2.7.3 on fedora 17.

#!/usr/bin/python

import math

class QuantumComputerSimulator:
    SQRT_2 = math.sqrt(2)
    ONE_LOWER_TOLERANCE = 0.999
    ONE_UPPER_TOLERANCE = 1.001

    def __init__(self, numberOfQubits, initialState, verbose):
        self.__state = [0.0 for _ in range(0, pow(2, numberOfQubits))]
        self.__state[initialState] = 1.0 # Our quantum computer definitely starts in "initialState".
        self.__verbose = verbose
        self.log("Initial state")

    def applyHadamard(self, qubitIndex):
        "This is a constant time operation in a quantum computer."
        for index in range(0, len(self.__state), 2):
            zeroIndex = self.swapBits(0, qubitIndex, index)
            oneIndex = self.swapBits(0, qubitIndex, index + 1)

            zero = self.__state[zeroIndex]
            one = self.__state[oneIndex]

            self.__state[zeroIndex] = (zero + one) / self.SQRT_2
            self.__state[oneIndex] = (zero - one) / self.SQRT_2

        self.log("After Hadamard transformation on Qubit %s" % qubitIndex)

    def quantumOracle(self, function):
        "This is constant time on a quantum computer if function is constant time"
        for index in range(0, len(self.__state), 2): # We go in steps of 2 as the first qubit is not an input to our function
            result = function(index / 2)

            if result == 1:
                self.__state[index] = -self.__state[index]
                self.__state[index + 1] = -self.__state[index + 1]

        self.log("After quantum oracle")

    def readQubit(self, qubit):
        mask = 1 << qubit
        zeroProb = 0.0
        oneProb = 0.0

        for index in range(0, len(self.__state)):
            stateProb = self.__state[index]
            stateProb *= stateProb

            if index & mask:
                oneProb += stateProb
            else:
                zeroProb += stateProb

        if not self.isOne(oneProb + zeroProb):
            raise Exception("Something went wrong. Total probability for a Qubit should be 1.0. Could be a rounding error.")

        if self.isOne(oneProb):
            return True

        if self.isOne(zeroProb):
            return False

        # In reality, observing a qubit in a superposition (not definitely 1 or 0) would result in a 1 or 0,
        # and all entangled Qubits would need to be adjusted accordingly.
        raise Exception("Qubit is not in a known state.")

    def isOne(self, number):
        return number > self.ONE_LOWER_TOLERANCE and number < self.ONE_UPPER_TOLERANCE

    @staticmethod
    def swapBits(index1, index2, number):
        "Swap 2 bits in number, specified by index1 and index2"
        # mask for the required bits
        mask1 = number & (1 << index1)
        mask2 = number & (1 << index2)

        # Move them to the 1st bit
        bit1 = (mask1) >> index1
        bit2 = (mask2) >> index2

        # Zero out the bits in the number
        number ^= (mask1 | mask2)

        # Set the swapped bits
        number |= (bit1 << index2)
        number |= (bit2 << index1)

        return number

    def log(self, name):
        if self.__verbose:
            print "%s, %s" % (name, ", ".join(map(str, self.__state)))

def always0(value):
    return 0

def always1(value):
    return 1

def isOdd(value):
    return (value & 1)

def isEven(value):
    return (value ^ 1) & 1

def isConstantFunction(function, name, verbose):
    "This is the Deutsch-Jozsa algorithm"
    qubits = 3
    computer = QuantumComputerSimulator(qubits, 1, verbose)

    for qubit in range(0, qubits):
        computer.applyHadamard(qubit)

    computer.quantumOracle(function)

    for qubit in range(1, qubits):
        computer.applyHadamard(qubit)

    functionChanges = False

    for qubit in range(1, qubits):
        functionChanges |= computer.readQubit(qubit)

    if verbose:
        print

    if functionChanges:
        print "%s is balanced" % name
    else:
        print "%s is constant" % name

    if verbose:
        print

for function, name in [(always0, "Always0"), (always1, "Always1"), (isOdd, "isOdd"), (isEven, "isEven")]:
    isConstantFunction(function, name, True)

Monty Hall In Scheduling Language

We thought it would be an interesting exercise to rewrite the Monty Hall example in our scheduling language. The compiler/Eclipse plugin aren’t quite ready to run this, but it’s not all that far off. There’s a few things to note.
This is an early example of the language, and a few things will probably change.
It’s fully type checked. All you have to specify are the types of parameters and non-local variables.
Strings can have expressions embedded in them surrounded in back-ticks.

from
    Sys use print
    Math use Random

class MontyHall
    def runTrials(me, swapChosenDoor Bool, iterations Int)
        wins = 0
        i = 0

        while i < iterations
            i++
            if me.runSingleTrial(swapChosenDoor): wins++

        strategy = "swap the initially chosen door"

        if swapChosenDoor
            print("Always `strategy`")
        else
            print("Never `strategy`")

        print("    Number of wins `wins`")
        print("    Number of number of losses `iterations - wins`")
        print("")

private
    def runSingleTrial(me, swapChosenDoor Bool)
        initialChosenDoor = me.getDoorNumber
        correctDoor = me.getDoorNumber

        if swapChosenDoor
            if initialChosenDoor == correctDoor
                # We're swapping from the correct door, so we loose
                return False
            else
                # We're swapping from the incorrect door, so we win
                return True
        else
            if initialChosenDoor == correctDoor
                # We're not swapping from the correct door, so we win
                return True
            else
                return False

    def getDoorNumber(me) = me.randomNumberGenerator.next

    def main
        numTrials = 1000000

        monty3 = MontyHall.new(3)
        monty3.runTrials(True, numTrials)
        monty3.runTrials(False, numTrials)

        monty1m = MontyHall.new(1000)
        monty1m.runTrials(True, numTrials)
        monty1m.runTrials(False, numTrials)

    randomNumberGenerator Random
 

Monty Hall on Manlab – The Answer

This is a follow up to this post about the Monty Hall problem on Man Lab. The correct answer is that you should always switch. Did you get it? Without cheating and looking on wikipedia I mean. They got this correct on Manlab, but they got the odds wrong. You’d actually win the car 2/3rds of the time by switching.

Did you think that should be 50/50 and that whether you switched didn’t matter? Me too, and in fact if you change the puzzle slightly, we’d have been right. The thing that changed the odds was that you actually had more information than you thought. The key piece of information is that Monty told you he knew there was a goat behind the door he opened. If he’d opened that door and revealed a goat by chance, the odds would be 50/50. If you forgot which door you’d chosen and picked one of the 2 remaining doors at random, your odds would be 50/50. So what did he tell you and what do you know that changes the odds for the door you didn’t choose?

2 Groups

When you picked a door, you divided the doors into 2 groups, Monty’s and yours. The one you picked is your door and the 2 you didn’t are Monty’s doors. You know that the car is behind your door with probability 1/3, and behind one of Monty’s doors with probability 2/3rds. If you were allowed to pick a group of doors, and open all the doors in that group, you’d pick Monty’s doors, since there’s a 2/3rds chance of winning the car. Well, you effectively can open all of Monty’s doors because Monty has opened one of them for you.

Still Don’t Believe Me?

Try this python script (I was using version 2.7.3).

#!/usr/bin/python
from random import Random

class MontyHall:
    def __init__(self, doorCount):
        if doorCount < 3:
            raise Exception("doorCount must be >= 3")

        self.__doorCount = doorCount
        self.__randomNumberGenerator = Random()

    def __runTrial(self, swapChosenDoor):
        initialChosenDoor = self.__getDoorNumber()
        correctDoor = self.__getDoorNumber()

        if swapChosenDoor:
            if initialChosenDoor == correctDoor:
                # We're swapping from the correct door, so we loose
                return False
            else:
                # We're swapping from the incorrect door, so we win
                return True
        else:
            if initialChosenDoor == correctDoor:
                # We're not swapping from the correct door, so we win
                return True
            else:
                return False

        assert False    

    def __getDoorNumber(self):
        return self.__randomNumberGenerator.randint(0, self.__doorCount - 1)

    def runTrials(self, swapChosenDoor, iterations):
        wins = 0
        i = 0

        while i < iterations:
            i += 1

            if self.__runTrial(swapChosenDoor):
                wins += 1            

        strategy = " swap the initially chosen door"

        if swapChosenDoor:
            print "Always " + strategy
        else:
            print "Never " + strategy

        print "    Number of wins %s" % wins
        print "    Number of number of losses %s" % (iterations - wins)
        print

numTrials = 1000000

monty3 = MontyHall(3)
monty3.runTrials(True, numTrials)
monty3.runTrials(False, numTrials)

monty1m = MontyHall(1000)
monty1m.runTrials(True, numTrials)
monty1m.runTrials(False, numTrials)

The output should be:

Always  swap the initially chosen door
Number of wins 665493
Number of number of losses 334507

Never  swap the initially chosen door
Number of wins 333010
Number of number of losses 666990

Always  swap the initially chosen door
Number of wins 999014
Number of number of losses 986

Never  swap the initially chosen door
Number of wins 998
Number of number of losses 999002

Monty Hall on Manlab

After watching Manlab on the BBC a few days ago featuring the Monty Hall puzzle, I remembered a slightly drunken conversation with a friend in which I’d vehemently argued for the incorrect answer. The puzzle goes like this:

You’re in a game show, hosted by Monty Hall.
You’re presented with 3 doors, and asked to choose one.
Behind one door is a car. Behind the other 2 are silent, odour free goats.
When you’ve chosen, Monty opens one of the other two doors to reveal a goat.
He tells you he knew this door had a goat behind it and asks if you’d like to change your decision.

The question is, should you stick with your original decision or change to the other door?

I’ll leave the answer for the next post. Suffice to say, it’s not obvious. In fact they got the answer slightly wrong on Manlab.

Job Scheduling

Having recently looked at job scheduling and batch processing for a client, it struck us that there isn’t really anything on the market that deals well with complex work-flows. Simple work-flows are well catered for. The basic idea tends to be that you design your work-flow by joining boxes together in various ways and then specify start conditions. In essence, they’re simple visual programming languages, and they’re great for getting up and running very quickly with simple work-flows.

The Cracks in Current Job Scheduling Software

Once your program gets beyond a certain size however, you start needing a few things in place to keep it manageable:

  • Version control.
  • Auditing of releases.
  • Security.
  • Roll-back of releases.
  • Encapsulation.
  • Modules.
  • Testability.
  • Search function.

To do all of these things well, you’d have to implement your own version of, say:

  • git
  • cron
  • sudo
  • python
  • Your favourite text editor (we’re not even going there).

And add all the features specific to job scheduling/work-flow automation that are missing from this tool chain.
Where it gets even worse is that, even if your job scheduler were up there with the best in class of all these tools, you’d still be forced to use multiple tools for the same job. For example, everyone now has to use one version control system for job scheduling, and one for everything else.

In reality, you tend to end up with a job scheduling tool that’s distinctly lacklustre, compared to established tools, in areas such as:

  • Searching for something in your program.
  • Releasing changes to your code. Especially if you have jobs in progress.
  • Finding out who and what broke everything.
  • Reading through and understanding the code.
  • Parameter passing.

You also tend to do a whole heap of clicking to perform tasks that would be trivial in a text editor.

What If There Was Some Kind of Text Based Programming Language?

That would immediately take care of your version control, auditing of releases, roll-back, search etc. In fact, if you can come up with a good language, all these problems go away and you’re left to solve just the job scheduling/workload automation problems, such as:

  • Auditing of what function was called and when.
  • Logging of return codes/exceptions.
  • Re running failed jobs.
  • Starting arbitrary jobs.
  • Introspection and control of running functions.
  • Transitioning between old and new versions of a running program.

Some of these problems are tied inextricably to the runtime of the language, which means you really need a custom language runtime. Rather than take an existing language that isn’t specifically designed for job scheduling, we, at Enhedron, are working on a simple scripting language that’s specifically suited to job scheduling. We’ll keep you posted on progress.