Will We Need A New Breed of Computers? This 18 Year-Old Proved It Might Take Longer Than We Thought.

Earlier this summer, a teenager named Ewin Tang reached a breakthrough in computing, proving that classical computers are still society’s best bet for most tasks, even when compared to quantum computers. As one of the most revolutionary advancements in computing since, well, the computer, quantum computing has the potential to turn technology on its head, specifically when solving “brute force problems”, or problems that require massive amounts of calculations to be solved, such as training artificial intelligence with massive amounts of data. In classical computers, which are our everyday laptops, developers have reached a huge roadblock that happens to be really tiny: engineers are creating computer parts to be more efficient and smaller, however, some essential parts are reaching a subatomic level in which electrons no longer behave the same way. While it is exciting that scientists are able to develop hardware this small, their size limits the maximum speed that a computer can be. This is where quantum computing enters, as a completely new branch of computing with redefined limits.

In traditional computers, bits are the most basic units of information, with a value set to either zero or one. These bits are the data that this computer processes, but are replaced with units called qubits in quantum computers. Because physical rules are different at this level, qubits are able to exist in multiple states at once but collapse to a definite state right when they are measured, making their actions impossible to predict. We can think of bits in terms of two coins being flipped. Because of basic math, we know there are four possible combinations, but only one of them will be the combination we end up with. In quantum computing, qubit representation of these coins would mean that we will have all four combinations at the same time, instead of just one.

The fundamental nature of this new breed of computers combines with special properties specific to qubits to exponentially outperform traditional computers….well, at least theoretically. There are quantum computers in existence under the wing of companies like Google, IBM, and Microsoft. Their set up allows for the qubits to behave in their unpredictable manner; however, they use a very small number of qubits and thus cannot solve many useful problems. Quantum computing is still very young, so we haven’t reached the point of quantum supremacy, where these computers will actually be able to solve these problems fast. There is a solitary problem that quantum computers completed the quickest, but recently it has been disproved by the aforementioned Ewin Tang, an 18-year-old computer science student who in turn disrupted (or perhaps helped) the progress of this field.

The enigma is referred to as the recommendation problem and concerns generating suggestions for users on Amazon and Netflix. It examines data produced by both the user themselves and by similar users, which ends up being a lot of information. These movies or online products are then arranged in a matrix-like grid and each item is assigned a certain value to represent the likelihood of the target user liking that selection.

The difficulty in solving this problem lies within the sheer size of it. It expands exponentially as more users are compared against the target user. Quantum computers have the potential to solve problems like this in reasonable amounts of time, while traditional models take years or even lifetimes to do so. In 2016, Anupam Prakash and Iordanis Kerenidis, two experts in the field, created and published a theoretical quantum algorithm that beat all other algorithms, including those for classical computers, and seemed to take a huge step in the name of the new computers.

Their model essentially reduced the size of the problem by examining a reduced version of it, like for example, the genre of movies that a particular user liked to watch. The algorithm was very exciting and revolutionary, as it was believed to be the only example of a quantum computer outperforming a traditional computer.

A year later, in 2017, UT Austin’s Ewin Tang, set out to disprove the theorem by finding a faster classical recommendation algorithm. This July, Tang, now 18 years old, did just that. He found inspiration in the quantum setup and sought to replicate the same techniques that Prakash and Kerenidis used, only with a classical computer. Specifically, Tang produced his algorithm so that it ran in a unique computational time called polylogarithmic time. This feature of the algorithm is shared by the quantum algorithm and enables the system that is using it to manage the scale of movies or products. Tang produced a proof that was much faster than previously suggested classical algorithms, but more importantly, was faster than the quantum approach.

Although the breakthrough has exposed weaknesses in the development of quantum computing, Tang’s study will tremendously help the field. A revision such as this is a means for further growth through study and trial and error. Now, perhaps scientists behind these new supercomputers will take inspiration from their own MacBooks. A world that utilizes quantum computing might be a lot closer than we thought.