# Quantum Computing Series, Part 11: Quantum Computation Speed

A quantum computer can harness quantum states to simultaneously represent bits to offer exponential growth in computation speed and power. Enormous, complex problems traditionally estimated to have taken eons to complete could instead be done in a reasonable amount of time using quantum computers. This makes quantum computing relevant for IoT data and other such potentially complex problems that involve permutation and combination optimization.

At the quantum level, atoms could be programmed to represent all possible input combinations, all at once and therefore test all the combinations simultaneously.

#### Exponential Increase in Computation Speed

In addition to factorization problems and discrete logarithms, quantum algorithms have far superior speeds than the best-known classical algorithms. These include algorithms used for simulating quantum physical processes in solid state physics and chemistry, approximating Jones polynomials, and solving Pell’s equation.

There isn’t yet any mathematical proof to establish to show that an equally fast classical algorithm isn’t possible. It is, however, widely believed, on a solid mathematical basis, that it is unlikely.

Quantum computers perfectly suit some problems that are computationally intensive. This is because quantum computers can offer exponential increase in speed of calculations when compared to traditional digital computing. One such problem is database search, which could potentially take up a lot of time using today’s digital computers.

The basic premise that quantum computer uses for polynomial speedup is to harness quantum states to represent bits simultaneously. On the quantum level, atoms can be programmed to simultaneously represent all possible input combinations. This means running the quantum algorithm just once tests all possible combinations together. Contrast this with a classical computer where you can process only one possible input combination in one run of the algorithm. You need to cycle through all the combinations one by one to solve the problem. For some problems, such as those involving complex factorization, this requires time that exceeds the age of the Universe.

#### Using Quantum Computing to Solve Computation-Intensive Problems

So, with quantum computing, institutions and businesses can solve immensely complex problems quickly and involving much lesser costs and resources.

Quantum computing works best for complex computational problems. For example, in drug discovery, where to find a single protein, trillions of combinations of amino acids have to be cycled through.

The travelling salesman problem is considered one of the most difficult. It involves finding the shortest route between a list of cities. It might sound ridiculously simple, but involves some pretty intense computation. To solve this problems, engineers typically use shortcuts; for example, Monte Carlo method or genetic algorithms.

The traveling salesperson problem, which involves testing various combinations, is applicable to a number of areas. Any problem that requires making a complex process more efficient such combinatorial optimization is required. For example, logistics companies need route optimizations all the time to minimize their delivery time. Semiconductor companies use such optimizations to design and manufacture chips. Going forward, this will perfectly suit the Internet of Things and smart cities (and the combination of all the smart things the cities comprise).

How Quantum Computers make leveraging the quantum phenomena of superposition and entanglement, a quantum computer can process a mind-boggling number of calculations simultaneously to achieve phenomenal computation speed. A classical computer can only work with ones and zeros; in contrast, a quantum computer uses ones, zeros, and superpositions of ones and zeros. Tasks considered too difficult or even impossible for classical digital computers would be a mundane job for a quantum computer.

While classical computers can easily multiply very large numbers, factoring a very large number is too challenging for it. Using Shor’s algorithm—the first quantum computing algorithm that was proposed in 1994 by Peter Shor — a quantum computer could efficiently solve this problem of finding factors.

#### Modeling and Searching Data Using Quantum Computers

Quantum computers would open doors for scientists to conduct virtual experiments and model quantum systems. For example, behavior of atoms and particles at unusual conditions (say, very high energies that can be only created in the Large Hadron Collider) could be modeled without investing enormous amounts of money to actually create such unusual conditions. Further, chemical processes could be modeled showing how atoms interact in a chemical reaction, which essentially is a quantum process.

Another very important application of quantum computers is searching and sifting through enormous amounts of data. Consider a large phone book with one million entries and sorted by individual names. Now, you need to find the name of the person with the phone number 866-692-8781, you need to go through each and every entry serially till you find that entry. The worst case could be that you need to go through all the one million entries, or in other words, one million steps. In 1996, Lov Grover, a scientist at Bell Labs, discovered that a quantum computer significantly reduces the number of steps from one million to just one thousand.

So, generalizing, quantum computers would find immense use wherever we have finding-a-needle-in-the-haystack kind of problem.

#### Other Major Applications of Quantum Computers

Other areas that can immensely benefit from quantum computing are the conventional fields of biology, medicine, and chemistry. This is because all these fields exhibit changes at molecular level, which could be efficiently modeled using a quantum computer. Molecules are composed of particles working per the laws of quantum mechanics. Traditional computers are way too weak to represent the exact quantum states of such molecules and systems. With increasing complexity of molecules, the problem aggravates further. Quantum computing offer efficiency and ease with which such simulations can be created to accurately represent the quantum dynamics involved.

#### Where do Classical Computers Fall Short

Let’s take another example: the Human Genome Project. The project showed that treatments could be designed suited for the genetic make up of individuals rather than a generic treatment for everyone. It has since been found very effective in administering targeted cancer therapies.

Such major advances have also revealed our limitations. Unlocking the secrets of DNA revealed lack of depth of our knowledge regarding the proteins it codes. Targeted therapies have clearly shown we can achieve much more by working with complete genomes in place of just isolated markers in our chromosomes.

Conventional classical computers are woefully short of being able to perform these tasks well. And quantum computers can very well fill that void. Harvard researchers have found that quantum computers could well enable us to map proteins similar to the way we do genes today. Quantum computer will enable creation of more effective therapies by analyzing entire genomes.

Mapping the human genome was a technological triumph. At its core, it were the computers much more powerful than the ones previously used that allowed analysis of human DNA on a massive scale. In future, however, as the problems become more complex and the computations more massive, quantum computers seem the most likely way forward.

All such possible achievements of quantum computing listed above and thousands still not conceived are based on the phenomena of quantum parallelism and quantum interference.

#### Some Potential Applications of Quantum Computers

Some other potential applications of quantum computers are as follows:

• Make airplanes safer: The leading aerospace company, Lockheed Martin, plans to use its D-Wave to test jet software. It is considered too complex for classical computers.
• Boost GDP: Consumer spending could be stimulated by employing a targeted, personalized advertising, based on results obtained using quantum computation.
• Detect life-threatening diseases early: Using complex genetic models, it could be much accurately estimated as to how genes could manifest in future, thereby catching the disease right in its tracks.
• Reduce travel time: Traffic could be analyzed much better using quantum computing. It involves data being continuously collected from every individual vehicle in the traffic and other entities en-route. The exhaustive real-time analysis offers the most efficient route.
• Offer autonomous automobiles: Google is working on a quantum computer to develop a software for distinguishing cars from landmarks.
• Make better weather forecasts: Currently, weather forecast is an approximate science that is not always correct. Quantum computers could much better model complex weather patterns and offer predictions that help reduce weather-related damage and deaths. This is because with accurate and earlier predictions, people get more time to take cover.
• Discover distant planets: Finding distant planets that exhibit Earth-like atmosphere for life to flourish involves crunching vast amounts of data collected by telescopes. Quantum computers perfectly fit he bill.
• Ace elections: Elections already have become largely an exercise of collecting, categorizing, compiling, and crunching the vast amount of data and deriving actionable based on that. Quantum computers could offer solutions to problems from every possible angle and help design campaigns that best exploit individual voter preferences.
• Develop more effective drugs: Analyzing DNA-sequencing data or mapping amino acids doctors could offer superior drug-based treatments.

#### Measuring Quantum Speedup

Quantum computers could potentially perform certain computations much faster than traditional classical computers we use today. However, defining and measuring quantum speedup is something debatable. One obvious factor is difference in computational powers of classical and quantum processors. Researchers define various types of quantum speedup and consider quantum processors designed to solve a specific class of problems.

#### Ramsey Numbers

New quantum computer prototypes are presented with two-color Ramsey numbers. Essentially, these two-color Ramsey numbers are two exclusive sets of exotic mathematical entities intimately connected with the emergence of order in a disordered system to test for quantum speedup.

Ramsey numbers can be explained using the famous party problem. It goes as follows: You need to determine how many people you need to invite to a party so that you have two subsets of people—the first subset denoted by ‘m,’ where everyone knows each other in this subset, and the second subset ‘n,’ where no one knows each other and so be forced to mingle. The required number, R(m,n), is a two color Ramsey number.

These numbers are notoriously difficult to calculate. The mathematician Paul Erdos once said that if an alien species threatened to destroy the human race unless we could tell them the R(5,5) Ramsey number, our best bet would be to put humankind’s best minds to work on the problem, since we should have a chance of getting it.

But if the aliens asked for R(6,6), our best bet would be to launch an immediate all-out strike against the aliens since the calculation would be too difficult to contemplate.

It is essentially a counting problem. Consider the guests at the party as nodes on a graph and their connections as edges. Therefore, calculating Ramsey numbers is really counting the connection permutations for a given number of guests.

However, permutations could be huge even for a small number of guests. For example, R(5,5) is still unknown; mathematicians think it lies between 43 and 49.

Researchers have calculated R(3,3) and R(m,2) where m = 4, 5, 6, 7 and 8.

#### Using Quantum Computers for Ramsey Numbers

Their quantum computer uses qubits in the form of superconducting circuits. Here, 1s and 0s are represented by the currents travelling in opposite directions and quantum mechanics laws allow both states to exist simultaneously. Therefore, a single circuit represents both 0 and 1 at the same time.

What’s useful in this calculation is that whenever a solution occurs, it is the result of increasing the number of guests by one. So in R(3,3), parties with 1, 2, 3, 4, and 5 guests produce a null result. The dynamics, however, undergo dramatic change when the number of guests go up to 6; an appropriate quantum algorithm makes it easy to spot.

Till date, the R(8, 2) computation is the largest experimental implementation of a scientifically meaningful quantum algorithm.

The computation for R(8,2) used 84 qubits. Out of these 84 qubits, 28 were used in the computation and the remaining 56 were used for error correction. It took just 270 milliseconds using the D-Wave Systems to arrive at the solution, which is 8. This result indeed matches with the solution, which has been known for many years by the conventional methods.