twitter facebook rss

Problems addressable by quantum computing

Posted by on September 21, 2016.

Quantum computing will probably make possible certain types of calculation and analysis that have been difficult or impossible with traditional digital computers. These new operations will, as every new development in information technology, have implications for security. New means of analysis and detection will be possible. At the same time, new vulnerabilities and methods of attack will be developed.

Digital computers are a wonder, and have allowed us to do so many things that we couldn’t before they existed. Digital computers are getting better and faster every year. Still, there are certain types of problems that classical computer architectures solve poorly, if at all. Many of these restrictions are not simply limitations that will be overcome as computers get faster, but are inherent in the way traditional computers work.

Some problems are just generally hard. There is, for example, the Traveling Salesman Problem. A salesman has a territory, and a number of cities to visit. What is the best route to take to visit them all, minimizing the distance and time to cover the circuit? If there are only two cities, the answer is obvious. Three is still obvious. Four might be harder, and you might have to calculate a couple of paths before you find the best. In fact, if the answer doesn’t jump right out at you (and, as good pattern matchers, people can generally have a good stab at creating a reasonably good itinerary without doing much calculation), there is no algorithm for finding the very best route besides creating each possible course, calculating the distance or time, and then comparing them until we find the shortest. Every city that you add doesn’t just add to the complexity of the calculation: it compounds it exponentially. Other examples of this level of difficulty are problems that are NP-complete, non-convergent problems, and the Ising model (which is, itself, related to some quantum technologies in that it has implications for materials science and possibly superconductivity).

This “least path” problem turns up surprisingly often, in all kinds of situations. It relates to staff scheduling, and to efficiency studies. (Those who have had to deal with seating plans for a wedding or other special event will have encountered it: what is the best seating plan given all the factors of who will speak to whom, which pairs cannot be seated together, and all kinds of preferences and social obligations.)

Weather forecasting and climate prediction are other applications that are extremely difficult. Simulations of all kinds require the processing of a great deal of data. With digital computers we have to break the problem up into small boxes, and then process each box, and then figure out how the change in box A affects boxes B, C, and D, and then recalculate how the change in box B caused by the change in box A affects boxes C and D. And then we have to recalculate how the change in box C caused by the change in box B caused by the change in Box A will, in fact, change box A. And so forth.

People are very good at finding and recognizing patterns. Computers do this poorly. Given an object, a computer can be taught to recognize it–if it is the same distance from the camera, if it is placed in the same orientation, and if the background hasn’t changed. It is very difficult to get computers to take all these factors into account, compare two objects, and reliably decide that they are the same, because “same,” to a computer, means identical. It is therefore even more difficult to get a digital computer to look at a number of different objects, and decide which two, of all of them, are closest to being the same. All kinds of calculations have to be done, and then redone, and then redone again, as each aspect of each item is compared against every other aspect of every other item. The more items are presented, the more work the computer has to do.

It is felt that quantum computers will be able to deal more effectively with a number of these difficult problems. Superposition will allow for the processing of vast numbers of possibilities simultaneously, so that a “best” answer, out of a number of potential answers, can be arrived at quickly. Entanglement may be able to allow us to impose additional conditions on calculations, beyond straightforward computation. Other aspects of quantum physics and mechanics may allow us to build computing devices that can perform calculations that are completely beyond our current capabilities, and those of the projected developments in digital information technologies.

Using the superposition capabilities of qubits, a sufficiently large quantum computer would be able to look at “all possible paths” in our least path class of problems, and thus give us the shortest path in one process. Similarly, with simulations, the effects of one aspect on another can be fed back into the calculation much more effectively. Pattern recognition, and finding similarity, is, in effect, a special class of the lowest energy, or least path problem, and so is anothr good candidate for quantum processing.

This is not, of course, to say that quantum computers are a magic panacea for every problem, and at some point I’ll have to look at some of the problems. But, for the meantime, we might look at aspects of security, and how quantum computing might help us out. Staring with security management.

Leave a Reply

Your email address will not be published. Required fields are marked *

Submitted in: Expert Views, Rob Slade, Security, Uncategorized |