Optimizing Santa’s Route … Quantum Computing?
Author(s): Peter Bye, Posted on December 14th, 2015
Now that the year end is approaching, I decided to contact Elf Tietokone who, readers may recall, is the CIO of SantaSystems, the IT arm of SantaPrise in Lapland. Once again he would be very busy so I expected that he would invite me to SantaSystem’s offices, to minimise any loss of his time. So I was surprised when he said that he would be visiting the UK and could we meet in London. He added that there have been some very interesting technical developments, which he was keen to discuss with me.
I was very happy with this arrangement as it provided me with an opportunity to introduce him to something not common in Lapland. With that idea in mind, I arranged to meet him at Lord’s cricket ground, home of the Marylebone Cricket Club (MCC), of which I am member. Although cricket is only played in the summer, Lord’s is open to visitors all year round, so I took him on a tour of the ground. I explained the laws of cricket, which he thought displayed a level of complexity greater than his IT environment.
We then adjourned to the Lord’s Tavern for lunch. Elf began our discussion by bringing me up to date on the state of their IT systems. The fabric-based architecture already installed is proving very effective. Elf said that he was planning to consolidate on ClearPath Forward for MCP and OS 2200 environments, as well as for pure Linux and Windows.
In common with just about every large (and small!) organisation, Elf remains concerned about security. The efforts of the Trollhackers under bridges across the border continue but have been frustrated by the security of the ClearPath Forward systems and all the other defences the CSO has put in place. As an indication of the emphasis placed on security, the CSO has now joined Elf on the board of SantaPrise.
Elf then explained an idea that he and the CSO were investigating. They’ve developed a trial application component, to run under MCP or OS 2200 – the decision is still open – to act as a front-end to Windows or Linux applications. The goal is to exploit the high levels of security of the ClearPath Forward environments to prevent intrusion. The fabric architecture provides the ideal infrastructure. Elf said he would be keen to share the results.
We then got to the point of why Elf was in the UK and not back in Lapland. The one area where IT is struggling is the planning of Santa’s Christmas Eve route. Even with the aid of the supercomputers now installed, the problem remains intractable. SantaSystems is therefore investigating alternative approaches.
Working out the route is the Travelling Salesman Problem (TSP): how to compute the shortest route between all the destinations going through each only once. Using a brute force approach, going through all the options, the time to complete the calculation is of the order of n-factorial (O(n!)), where n is the number of destinations. If n = 1000, n! = 4.023872601×102567. For Santa’s route, the problem is the TSP to end all TSPs: n is about one billion! Even using dynamic programming, which breaks the problem down into a collection of simpler sub-problems, the solution is still in exponential time (2O(n)).
It’s clear that using classical computing is a non-starter. Elf has decided to take time out to look at quantum computing, to see if it could solve the problem. He’s decided to start by investigating optical technology, using photon polarisation as the basis of the qubit, the quantum equivalent of the bit. He’s in the UK is because he wants to visit the University of Bristol to see the work done in the Centre for Quantum Photonics.
Apart from the route calculations, there’s another aspect of quantum information of importance to Elf and his team: security. In the foreseeable future, quantum computers may be able factorise large numbers, thereby breaking public key encryption such as RSA. An algorithm for factorisation on a quantum computer was described over 20 years ago but a suitable computer is yet to be built. However, the CSO has decided now is the time to look at what can be done if RSA is compromised, rather than waiting until it happens. He’s also interested in quantum encryption to avoid undetected attempts to eavesdrop.
Elf and his team should be pretty busy for the coming years!
That’s all for 2015!
Hyvää Joulua ja Onnelista Uutta Vuotta from Santa, Elf Tietokone and all at SantaPrise!