# What is a Quantum Computer? Why Quantum Computations will change our world

**Leo Webb**

**Quantum computers** are computational devices that use quantum mechanical phenomena (e.g. superposition or entanglement) in order to operate data. The idea of quantum computing is based on the ability of subatomic particles to exist in different states at the same time. This feature of these particles can be used to make computations faster than ever before, minimizing energy consumption.

Traditional computers store information in bits. Bits can only take two values — either 0 or 1. Quantum computing relies on quantum bits (qubits), which can take both these values and can also be in a superposition of these values, which allows for storing much more information. If you imagine the values 0 and 1 as two poles of a sphere, a qubit can represent not only these poles but also any point on the sphere, as well.

**Quantum computing** is a relatively new idea and new technology. Many researchers are working on concepts of quantum computers, and some experiments have already demonstrated successful results when performing quantum computational operations on a small number of qubits. Quantum computers are expected to solve many tasks exponentially faster than traditional computers. For example, quantum computers will be able to break complicated cryptographic codes which are virtually impossible to break using regular computers. Given that cryptography is used to protect all kinds of data, including emails and web pages, various government organizations and military agencies actively support quantum computing research. However, this cutting-edge technology is still far from becoming mainstream.

**Short History of Quantum Computing**

- In 1981, Richard Faynman stated that classical computers are unable to illustrate the evolution of quantum systems effectively. Thus, Faynman suggested that it would make sense to create a basic quantum computer that would be able to simulate certain quantum processes which are so important for physicists. He also noted that such computers would be much more efficient than classical computers. However, the first special algorithm was created only 13 years later.
- In 1994, Peter Shor introduced the first algorithm that allowed researchers to factorize large integers. In addition, the whole process took exponentially less time than when using classical computers. Traditional computers would take millions of years to factor 300-digit numbers, while Shor’s algorithm is theoretically capable of solving such tasks in hours. Shor’s algorithm demonstrated the opportunities for breaking existing cryptosystems and so sparked further interest in the quantum computing technology.
- The first quantum database search algorithm was invented by Lov Grover in 1996. This algorithm introduced new opportunities for solving a variety of problems that require brute-force search or random search, being able to solve such tasks four times faster.
- In 1998, a 2-qubit quantum computer was created and used to solve the Deustch-Jozsa problem. Shortly after, a quantum computer was also used to execute Grover’s algorithm. In both cases, quantum computers were based on the principle of nuclear magnetic resonance (NMR). NMR allows researchers to probe the quantum states of nuclei in molecules, using their spin states as qubits.
- In 2017, IBM presented the first quantum computer for non-laboratory use — IBM Q. The IBM Q System One is a 20-qubit system. It’s still not a perfect quantum computer but IBM emphasizes that this system is upgradable and relatively easy to maintain. After the System One was introduced, the quantum computing race has reached a completely new level.

**Real-Life Examples of Quantum Computing**

Although a proper, powerful quantum computer has yet been created, experts from many industries have already appreciated the potential of quantum computing for our everyday lives, coming up with various possible applications. Fortunately, some quantum computing operations can be successfully carried out on the already existing qubit devices.

In 2017, Volkswagen and D-Wave Systems started their collaboration aimed to solve traffic problems. Researchers collected data on 10,000 taxis in Beijing and decided to find a solution for the optimization of traffic between the airport and downtown, considering both the cost of a ride and the distance. It took more than three months to properly map the data and present it in the right way so that quantum machinery can operate with it. However, the necessary solutions were generated in a few seconds. Regular Volkswagen servers have worked on each solution for half an hour. Moreover, the engineers were able to come up with a cloud solution instead of relying on on-premise hardware. As for now, Volkswagen continues to invest in quantum computing and partners with Google to find new solutions for traffic optimization.

Toyota also got interested in quantum computing, partnering with DENSO Corporation to develop new solutions for the optimization of traffic and production processes. Toyota is also looking for new solutions for autonomous driving. The companies used cloud quantum systems to analyze data on 130,000 commercial cars in Thailand, developing solutions for traffic decongestion and the overall improvement of traffic, including emergency route optimization. Quantum computation enabled the companies to work with massive amounts of data, suggesting optimal routes in real time, while traditional computers are able to deal only with simpler tasks, such as individual optimization.

A Japanese company Recruit Communications Co. is currently working in collaboration with F-Wave and Fujitsu, developing quantum computing solutions for advertising and marketing purposes. Researches have noticed that quantum annealing allows for developing more effective solutions for ad placement on mobile phones. The company also combines its research of quantum computing with the research focused on machine learning, hoping to introduce new, more effective, recommendation systems.

Max Henderson, a senior data scientist at QxBranch, used quantum computing for modeling the 2016 US presidential election. His main goal was to solve problems associated with correlations between different states. Henderson applied machine learning, using quantum-trained models to make a forecast based on a simulation. The team of researchers took into account polls, historical data on election results, and other sorts of publicly available data, mapping it to a Boltzman machine. After this, the Boltzman machine was mapped to a quantum computer. Thanks to this approach, the researchers could train the system for every possible configuration of the model. The experiment resulted in 25,000 solutions, demonstrating less certainty and greater uncertainty of winning for Clinton. Henderson’s team even managed to point out several “tipping-point” states.

**Advantages of Quantum Computers**

Although completely logical in the context of math and physics, the advantages of quantum computing over traditional computing had remained just a theory for quite a bit of time. In 2018, the scientific community finally obtained proofs. The Technical University of Munich (TUM), the University of Waterloo, and IBM published results of their experiment that has proven the ability of quantum computers to solve tasks impossible for classical computers.

The main difference between quantum and classical computers is that the latter follow the rules of standard physics. At any given moment, every bit of memory may only be in one or another state, which are 0 and 1. In contrast, quantum computers are based on the rules of quantum physics. Just as electrons are able to exist in different places at the same time, being in numerous overlapping states, qubits also exist in multiple states. This feature of qubits allows quantum computers to perform multiple operations on values at once, while traditional computers are limited to one operation at a time.

However, if we run traditional algorithms on a quantum computer, we won’t be able to see any advantages. Thus, the researchers needed algorithms that also use quantum principles, and such algorithms are not easy to formulate. Shor’s algorithm is a good example of what quantum factorization algorithms look like. Instead of relying on complex theories, Robert König from TUM has chosen an algebraic problem that takes a lot of time to solve when using traditional computers. König’s team used a quantum circuit – a simple quantum computing model. Quantum circuits have a “constant depth,” which means that each qubit performs only a certain number of operations. The chosen problem was impossible to solve on classical constant-depth circuits. The quantum circuit has found a solution using the principle of non-locality in the quantum algorithm, therefore proving the efficiency of quantum computing.

**Threats of Quantum Computing**

Information security is crucially important for many spheres, from military to banking and to healthcare. As we’ve already mentioned above, quantum computers are expected to break the existing mechanisms of encryption, even those that would take millions of years to decrypt using traditional computers. According to a report by the US National Academies of Science, Engineering, and Medicine, there is an urgent need for new cryptographic approaches that could withstand quantum computers. At the same time, the experts emphasize that effective adoption of quantum-resistant cryptographic technologies is a very difficult and long process. Therefore, there is a possibility that hackers will get access to quantum computers with the necessary capabilities before we will have any mechanisms of protection.

The most common method of encryption involves the use of digital keys. Two parties use these keys to decrypt secure messages. This approach is based on the idea that decryption without the key would be virtually impossible for the most powerful supercomputers, as the process would take too much time. One of the most popular cryptosystems of this kind is RSA-1024, and a powerful quantum computer could break it in less than 24 hours.

On the other hand, existing quantum computers are still incapable of solving complex cryptographical tasks. For example, the existing quantum processors from IBM or Google have 50-72 qubits, while a quantum computer powerful enough to use it in hacking would need to have thousands of “logical” qubits. Another problem with qubit processors is that they are almost impossible to use outside of the lab. They immediately react to changes in temperature and even sounds. Even the slightest vibrations cause mistakes in calculations, which is a reason why we need to link thousands of qubits to obtain reliable results.

**Where to Learn More About Quantum Computing**

To learn quantum computing, you should have a strong background in math, especially when it comes to linear algebra. Quantum computing requires you to perfectly understand matrix operations, vector representations, unitary operators, etc. Quantum computing also relies heavily on classical probability and probability amplitudes. If you have the necessary background, you can learn more about quantum computing using sources below.

*Courses*

Quantum Computing Online Courses for Professionals (MIT)

Quantum Information Science I (MIT, edX)

Quantum Information Science II (MIT, edX)

The Building Blocks of a Quantum Computer (Delft University of Technology, edX)

Understanding Quantum Computers (Keio University, Futurelearn)

Quantum Information and Computing (NPTEL)

- Books

Scott Aaronson, Quantum Computing Since Democritus

N. David Mermin, Quantum Computer Science: An Introduction

Michael A. Nielsen, Isaac L. Chuang, Computation and Quantum Information

Kenneth M. Hoffman, Ray Kunze, Linear Algebra

David J. Griffiths, Introduction to Quantum Mechanics

- Other Sources

Quantum Information Software Kit

Quantum Computing Playground

ProjectQ

Quirk: Quantum Circuit Simulator