Category: Computer Science

Balls, beams and quantum computers – performing calculations with patterns of light

by Jane Waite, Queen Mary University of London

Have you played the seaside arcade game where shiny metal balls drops down to ping, ping off little metal pegs and settle in one of a series of channels? After you have fired lots of balls, did you notice a pattern as the silver spheres collect in the channels? A smooth glistening curve of tiny balls forming a dome, a bell curve forms. High scores are harder to get than lower ones. Francis Galton pops up again*, but this time as a fellow Victorian trend setter for future computer design.

Photo credit: Galton Box by Klaus-Dieter Keller, Public Domain, via Wikimedia Commons, via the Wikipedia page for the Galton board

Francis Galton invented this special combination of row after row of offset pins and narrow receiving channels to demonstrate a statistical theory called normal distribution: the bell curve. Balls are more likely to bounce their way to the centre, distributing themselves in an elegant sweep down to the left and right edges of the board. But instead of ball bearings, Galton used beans, it was called the bean machine. The point here though is that the machine does a computation – it computes the bell curve.

Skip forward 100 years and ‘Boson Samplers’, based on Galton’s bean machine, are being used to drive forward the next big thing in computer design, quantum computers.

“Stripes beams lights” image by David from Pixabay

Instead of beans or silver balls computer scientists fire photons, particles of light through minuscule channels on optical chips. These tiny bundles of energy bounce and collide to create a unique pattern, a distribution though one that a normal digital computer would find hard to calculate. By setting it up in different ways, the patterns that result can correspond to different computations. It is computing answers to different calculations set for it.

Through developing these specialised quantum circuits scientists are bouncing beams of light forwards on the path that will hopefully lead to conventional digital technology being replaced with the next generation of supercomputers.

Watch the bell curve appear in real time.

This article was first published on the original CS4FN website and a copy is also on page 17 of issue 20 of the CS4FN magazine, Ada Lovelace: the computer scientist without a computer. You can download a free PDF copy below, along with all of our free material at our downloads site.

*Francis Galton appears earlier in Issue 20, you can read more about him on page 15 of the PDF. Although a brilliant mathematician he held views about people that are unacceptable today. In 2020 University College London (UCL) changed the name of its Galton Lecture Theatre, which had been named previously in his honour, to Lecture Theatre 115.

Related Magazine …

EPSRC supports this blog through research grant EP/W033615/1.

Watching whales well – the travelling salesman problem

by Paul Curzon, Queen Mary University of London

Photograph of a whale's tail emerging from the deep blue sea with a tree-covered cliff behind it.
Whale tail photograph by Kevin O’Leary from Pixabay

Sasha owns a new tour company and her first tours are to the Azores, a group of volcanic islands in the Atlantic Ocean, off the coast of Portugal. They are one of the best places in the world to see whales and dolphins, so lots of people are signing up to go.

Sasha’s tour as advertised is to visit all nine islands in the Azores: São Miguel, Terceira, Faial, Pico, São Jorge, Santa Maria, Graciosa, Flores and Corvo. The holidaymakers go whale watching as well as visiting the attractions on each island, like swimming in the lava pools. Sasha’s first problem, though, is to sort out the itinerary. She has to work out the best order to visit the islands so her customers spend as little time as possible travelling, leaving more for watching whales and visiting volcanos. She also doesn’t want the tour to go back to the same island twice – and she needs it to end up back at the starting island, São Miguel, for the return flight back home.

Trouble in paradise

It sounds like it should be easy, but it’s actually an example of a computer science problem that dates back at least to the 1800s. It’s known as ‘The Travelling Salesman Problem’ because it is the same problem a salesman has who wants to visit a series of cities and get back to base at the end of the trip. It is surprisingly difficult.

It’s not that hard to come up with any old answer (just join the dots!), but it’s much tougher to come up with the best answer. Of course a computer scientist doesn’t want to just solve one-off problems like Sasha’s but to come up with a way of solving any variant of the problem. Sasha, of course, agrees – once she’s sorted out the Azores itinerary, she then needs to solve similar problems, like the day trip round São Miguel. Her customers will visit the lakes, the tea factory, the hot spring-fed swimming pool in the botanic gardens and so on. Not only that, once Sasha’s done with the Azores, she then needs to plan a wildlife tour of Florida. Knowing a quick way to do it would help her a lot.

The long way round

An aerial photograph of São Miguel lighthouse in the Azores showing the surrounding tree-covered cliff and winding road.
Photo of São Miguel lighthouse Image by Vianney Dugrain from Pixabay

No one has yet come up with a good way to solve the Travelling Salesman problem though and it is generally believed to be impossible. You can find the best solution in theory of course: just try all the alternatives. Sasha could first work out how long it is if you go São Miguel, Terceira, Faial, Pico, São Jorge, Santa Maria, Graciosa, Flores, Corvo and back to São Miguel, then work out the time for a different order, swapping Corvo and Flores, say. Then she could try a different route, and keep on till she knew the length of every variation. She would then just pick the best. Trouble is, that takes forever.

Even this small problem with only 9 islands has over 20 000 solutions to check. Go up to a tour of 15 destinations and you have 43 billion calculations to do. Add a few more and it would take centuries for a fast computer running flat out to solve it. Bigger still and you find the computer would have to run for longer than the time left before the end of the universe. Hmmm. It’s a problem then.

Be greedy

The solution is not to be such a perfectionist and accept that a good solution will have to be good enough even though it may not be the absolute best. One way to get a good solution is called using a ‘greedy’ algorithm. You start at São Miguel and just go from there to the nearest island, from there to the nearest island not yet visited, and so on till you have done them all. That would probably work well for the Azores as they are in groups, so visiting the close ones in each group together makes sense. It doesn’t guarantee the best answer in all cases though.

Or just go climb a hill

Another way is to use a version of ‘hill climbing’. Here you take any old route and then try and optimise it, by just making small changes – swapping pairs of legs over, say: instead of going Faial to Pico and later Corvo to Flores try substituting Pico to Flores and Faial to Corvo, with the rest the same but in the opposite order. If the change is an improvement keep it and make later changes to that. Otherwise stick with the original. Either way keep trying changes on the best solution you’ve found so far, until you run out of time.

So Sasha may want to run a great tour company but there may not be enough time in the universe for her tours to be guaranteed perfect…unless of course she keeps them very small. After all, just visiting São Miguel and Terceira makes a great holiday anyway.

This article was originally published on the CS4FN website and a copy can also be found on pages 14-15 of issue 10 of the CS4FN magazine, which you can downloads as a PDF below. All of our free material can be downloaded here.

Related Magazine …

EPSRC supports this blog through research grant EP/W033615/1.

Cyber Security at the Movies: Guardians of the Galaxy (Fail Secure security)

[Spoiler Alert]

If you are so power hungry you can’t stand the idea of any opposition; if you want to make a grab for total power, so decide to crush everyone in your way, then you might want to think about the security of your power supply first. Luckily, all would-be dictators who crush everyone who gets in their way as they march towards total domination of the galaxy, tend to be very naive about cyber-security.

Take Ronan the Accuser in the original Guardian of the Galaxy film. He’s a villain with a religious streak, whose belief that strength is virtue and weakness is sin leads to his totally corrupted morality. To cut to the guts of the story he manages to get the “Infinity Stone” that gives unimaginable power to its owner. With it he can destroy anyone who gets in his way so sets out to do so.

Luckily for the Galaxy, good-guy Peter Quill, or Star-Lord as he wants to be known, and his fellow Guardians have a plan. More to the point they have Gamora. She is an assassin originally sent to kill Quill, but who changes sides early on. She is an insider who knows how Ronan’s security system works, and it has a flaw: its big, heavy security doors into his control room.

Security Lesson 1. It should still be secure even when the other side know everything about how it works. If your security relies on no one knowing, its almost certainly bad security!

Once inside his ship, to get to Ronan the Guardians will need to get through those big heavy security doors. Now once upon a time big, heavy doors were locked and barred with big, heavy bolts. Even in Roman times you needed a battering ram to get in to a besieged city if they had shut the doors before you got there. Nowadays, how ever big and heavy the door, you may just need some cyber skills to get in if the person designing it didn’t think it through.

Electromagnetic locks are used all over the place and they give some big advantages, such as the fact that they mean you can program who is and isn’t allowed entry. Want to keep someone out – you can just cancel their keycard in the system. They are held locked by electromagnets: magnets that are switched on and off using an electric current. That means computers can control them. As the designer of an electromagnetic lock you have a choice, though. You can make them either “fail safe” or “fail secure”. With a fail safe lock, when the power goes, the doors automatically unlock. With fail secure, instead they lock. Its just a matter of whether the magnet is holding the door open or closed. Which you choose when designing the lock depends on your priorities.

Fail safe is a good idea, for example, if you want people to be able to escape in an emergency. If a fire cuts the electricity you want everyone to still be able to get out, not be locked in with no chance of escape. Fail secure on the other hand is good if you don’t want thieves to be able to get in just by cutting the power. The magnets hold the bolts open, so when the power goes, the spring shut.

Security Lesson 2. If you want the important things to stay secure, you need a fail secure system.

This is Ronan’s problem. Zamora knows that if you cut the power supply then the doors preventing attackers getting to him just open! He needed a fail secure door, but instead had a fail safe one installed. On such small things are galaxies won and lost! All Zamora has to do is cut the power and they can get to him. This of course leads to the next flaw in his security system. It wouldn’t have mattered if the power supply was on the secure side of that door, but it wasn’t. Ronan locks himself in and Zamora can cut the power from the outside … Dhurr!

There is one last thing that could have saved Ronan. It needed an uninterruptible power supply.

Security Lesson 3. If your system is reliant on the power supply, whether a door, your data, your control system or your life-support system, then it should keep going even if the power is switched off.

After all, what if the space ships cleaners (you never see them but they must be there somewhere!) unplug the door lock by mistake just because they need somewhere to plug in the hoover.

The solution is simple: use an “uninterruptible power supply”. They are just very fast electricity storage systems that immediately and automatically take over if the main power cuts out. The biggest on Earth keeps the power going for a whole city in Alaska (you do not want to lose the power running your heating mid-winter if you live in Alaska!). Had Ronan’s doors had a similar system, the doors wouldn’t have just opened as the power would not have been cut off.It’s always the small details that matter in cyber security (and in successfully destroying your enemies and so ruling the universe). As with all computational thinking, you have to think about everything in advance. If you don’t look after your power supply, then you may well lose all your power over the galaxy too (and your life)!

by Paul Curzon, Queen Mary University of London

More on …