Transcription
Medicine, farming, alternative energy, energy storage, finance, banking, and communication are all industries that stand to be revolutionized by quantum computing. While quantum computers are currently in their infancy, a fully functional fault tolerant quantum computer has the potential to be absolutely revolutionary.
In this video, I want to take an optimistic look at the future of quantum computing as well as other adjacent quantum tech. If we're able to achieve a fault tolerant quantum computer, what kind of results could we see? One of the most notable cases where quantum computing will change things is all due to a single quantum algorithm that solves a seemingly innocuous problem. Given a large odd number n, find its two factors, which we'll label P and Q. P and Q must be prime integers, and they must multiply together to make N. For example, 15 factors into 5 * 3 and 21 factors into 7 * 3, etc.
For small numbers, this is incredibly easy to do by hand. Just try all of the primes you can think of and you'll come out with an answer very quickly. For larger numbers on the other hand, this is incredibly difficult. It turns out that for the fastest classical algorithm, factoring these numbers scales super polomially. This means every time we increase the number of bits n in our large number, the amount of time that it takes to find P and Q doesn't just go up linearly, but rather it goes up very quickly. For example, the jump between a 2-bit and a 4-bit number is much smaller than the jump between a 4-bit and a six-bit number. You can see that as our input size increases the time that it takes to complete the algorithm scales very quickly.
Shor's algorithm on the other hand runs in polomial time in the number of bits n. While the exact runtime depends on the implementation details, the key point is that it scales dramatically better than the best known classical algorithms making factoring efficiently solvable on a fault tolerant quantum computer. But why does this matter for the real world? Well, it turns out that factoring numbers on a classical computer is so hard that we decided to base almost our entire cyber security system off of it. This means all financial transactions, banking details, account credentials, and more are secured using large prime numbers. The actual technique is known as RSA encryption, and the quantum algorithm that breaks it is known as Shor's algorithm after Peter Shore, the Bell Lab scientist turned MIT professor who discovered it.
That said, all hope for data security is not lost. While RSA can be broken by quantum computers efficiently, there are methods of encoding our data that should be robust to even quantum computing attacks. Although, it's always possible that down the line another algorithm could come out and break those. Quantum computing isn't all bad for security. Though, quantum technologies also provide a secure method of transmitting data between two parties, which would allow both listeners to stop any type of third party interference. This is done through protocols known as quantum key distribution. I'll save the detailed description of how this works for another video, but the basics are that we can use three properties of quantum particles to ensure that our message isn't read without us wanting it to be. First, quantum particles can be put into a superp osition of multiple states at once. Second, the state of a superp osition collapses to one of the states in the superp osition probabilistically upon measurement. And third, a quantum state cannot be cloned without destroying the original state entirely.
Imagine we have two people, Alice and Bob, who want to send a secure message, and a third person, Eve, who wants to listen in on the conversation. If Alice sends Bob a quantum state in superp osition, he will receive that superposition state, measure it, and get zero or one 50% of the time. However, if Eve intercepts the message and measures the cubits before sending them onto Bob, she inevitably disturbs their quantum states. As a result, Bob may receive measurement outcomes that are inconsistent with Alice's original state preparation. In the BB-84 protocol, Bob randomly chooses how to measure each cubit at the time of measurement without knowing Alice's choice. After the transmission is complete, Alice and Bob publicly compare which measurement bases they used. If an eavesdropper like Eve was present, her measurements introduce errors that Alice and Bob can detect after comparing a subset of their results, at which point they can abort the transmission. Because any information Eve gains necessarily introduces the detectable disturbances, Alice and Bob can ensure that the final shared key is secure and that any partial information Eve may have obtained is removed during the final decoding step.
Medicine, farming, and energy storage are another industry which stands to be revolutionized by quantum computing. In all three cases, the common link is chemistry. When electrons and atomic orbitals interact to minimize their energy and find the most stable orbit, they form new molecular orbitals that we call chemical bonds. While you don't need quantum mechanics to understand what happens in a lot of basic chemistry, you definitely need quantum mechanics to understand why things happen, especially as molecules get more and more complex. Once you get to more complicated reactions and materials, the cookie cutter basic rules of substitution, elimination, and addition reactions go out the window. Complex multi-step biological pathways with proteins more complex than most factory machines combined to make us who we are. Crystal lattises with complicated electronic structures are carefully engineering the energy landscape to help create things like batteries. Industrial fertilizers, pesticides, and other agricultural chemicals rely on the intricate reactions to optimize yield and efficiency from nitrogen fixation to targeted pest control shaping the farming industry.
In all of these cases, quantum chemistry simulations through algorithms like quantum phase estimation could revolutionize the field. In general, these simulations would allow a sufficiently large quantum computer to simulate chemical structures at the level of an individual or group of molecules. While current quantum mechanic simulations are limited to small molecules and scale poorly as the number of atoms increases, even on powerful supercomputers, quantum computers have the potential to do these types of simulations systematically and with controllable accuracy for molecules with thousands of atoms. This would open up the possibility of directly simulating many things that we currently use less accurate approximate methods for.
Machine learning and AI is another industry which could greatly benefit from quantum computing. While AI is going through an absolute revolution right now in its own right, there is a sub field of quantum computing known as quantum machine learning which aims to combine the benefits of quantum computing to boost the already awesome payoffs of AI. This is applicable for example in nearest neighbor search which sits at the heart of algorithms like hey nearest neighbor classifiers. These systems make predictions by comparing a target data point to other examples in a data set, something used in areas like image recognition, recommendation systems, and medical diagnosis. In the classical world, finding the nearest neighbor normally requires checking every data point, which scales linearly with the size of the data set. But on a fault tolerant quantum computer, this kind of search can be sped up using quantum search techniques like Grover's algorithm, which provide a quadratic speed up. This means that a task that would normally take n steps could be done in roughly the square root of n steps. It's important to note though that this would be a technique most applicable to physics-based AI systems closer to quantum simulation. This will not speed up chatgbt or other LLMs.
Graph problems and physics simulators are another potential candidate for quantum speedups. Quantum computers may be able to speed up certain structured computational tasks that arise in physics and graph-based problems. The math that describes quantum computing under the hood is linear algebra, which is actually the same math that we often leverage in AI and many other things too. Linear algebra mainly concerns itself with the study of vectors, which are just arrows in space with a magnitude and direction, and matrices, which usually operate on vectors and are like a grid of numbers. It turns out that some matrix math operations which commonly come up in physics and graph problems are quite slow to implement on classical computers but may be significantly faster on quantum computers. For example, matrix inversion on a classical computer is a common technique used. The details of how it works isn't really important for this discussion. However, what is important is that for a matrix of size n, meaning the length of a row or column in the matrix, classical algorithms can perform a matrix inversion in a time proportional to around n cubed. Although really it's more like n^2.3 if we do some smart algorithmic tricks.
Quantum algorithms on the other hand can solve some specific matrix inversions poly logarithmically in n. The class of algorithms which do this are known as HHL algorithms after the three scientists who discovered the methods. It's important to note that this algorithm does have some restrictive conditions on it. So it's not a completely generalpurpose solution, but it is the type of idea that we would consider here. Another issue with this is that even in a theoretically perfect quantum computer, the loading of the data to even be able to solve the HHL algorithm may be so computationally expensive that it wipes out the advantage we pick up by using the quantum computer in the first place. So to really win with this algorithm, it should be applied to problems where the matrix can be stored algorithmically instead of being loaded as a large data set. This tends to be the case in physics-based and some graph problems, which is why I say it's applicable here.
At the end of the day, quantum computing has the potential to be a revolutionary technology. The new classes of algorithms and techniques that it gives us may allow us to do extraordinary things. However, most importantly, I would argue, is that the real impact of quantum computers will be realized once the hardware has matured to be in the hands of more researchers. As quantum computing gets more concrete, in the same way that has happened with classical computers, more people will get involved, bringing in fresh ideas, novel algorithms, and creative applications of the hardware.
While optimistic videos like this are certainly fun to make, I don't want to give anyone the wrong idea or oversell where the technology currently is today. To run most of these algorithms discussed over the course of the video, you would need a quantum computer with at the very minimum tens of thousands of logical cubits. However, even the best quantum computers today have only a few hundred physical cubits and still fewer logical cubits. Even these so-called logical cubits of today are not perfectly error corrected and still decoheree very rapidly. That's all to say, while we can run proof ofconcept tests to show that these algorithms are possible, basically small test cases, quantum computers are still a very long ways away from being industrially useful, let alone a household technology. Currently, the hardware limitations of the bottleneck. That being said, people at top universities and companies are working hard and making steady progress in chip and cubit design.
The future of computing in general is not something that's easy to predict. While we come up with ad hoc rules like Moore's law, at the end of the day, there is no law that describes the human capacity to innovate. And that's not something that we should underestimate unless Chachi BT gains sentience and takes us all out for them. With that, I've been Lucas. This has been Lucas's Lab. And thanks for watching.