Understanding how to solve problems with a quantum computer
Quantum computers can lead to breakthroughs in a wide variety of subject areas because they offer a computational strength we’ve never seen before. However, not all problems are favorable for a quantum computer. In order to identify which problems make good candidates, it’s important to have an understanding of how a quantum computer solves problems.
While quantum computers can offer an exponential boost in computational power, they can’t be programmed in the same way as a classical computer. The instruction set and algorithms change, and the resulting output is different as well. On a classical computer, the solution is found by checking possibilities one at a time. Depending upon the problem, this can take too long. A quantum computer can explore all possibilities at the same time, but there are a few challenges. Getting the right answer out of the computer isn’t easy, and because the answers are probabilistic, you may need to do extra work to uncover the desired answer.
For example, assume you wanted to page-rank the internet. To do so, the process would require loading every single page as input data. On a classical machine you would create a computation that gives you the page rank of each page, but this takes time and a significant amount of hardware. With a quantum computer, computation is exponentially faster than on classical hardware. But the caveat is that with quantum, your result will typically be the page rank of one page. And then you’d have to load the whole web again to get another, and do it again to get another, and continue until you eventually have the page rank for the entire internet. Because you have to load everything each time, the exponential speedup is lost. This example would not be favorable for quantum computing.
To solve any problem, you’ll have input, computation, and output.
- Input – The data required to run the computation
- Computation – The instructions given to the computer to process the data
- Output – The useful result received from the computation
Instead of returning the entire quantum state, a quantum computer returns one state as the result of a computation. This unique characteristic is why we write the algorithm in such a way that produces the desired answer with the highest probability. For this reason, problems that require a limited number of values are more applicable.
The amount of input data is also a consideration. As input data increases, either the number of qubits or the amount of work to ‘prepare’ the data grows quickly. Problems with highly compressed input data are more much more favorable.
What types of problems are ideal challenges for a quantum computer? Quantum computers are best-suited for solving problems with a limited volume of output, and—ideally—those with a limited amount of input. These restrictions might lead you to assume that the scope of what quantum computers can do is narrow, but the exact opposite is true. Quantum computers provide a level of computational power that allows us to tackle some of the biggest challenges we face. The nuance is in framing problems in a way that makes them solvable. Here are some great examples of how a quantum computer can be used to address some of today’s biggest challenges.
Chemistry
Modelling molecules is a perfect application for quantum computing. In Richard Feynman’s own words, “Nature isn’t classical, dammit, and if you want to make a simulation of nature, you’d better make it quantum mechanical, and by golly it’s a wonderful problem, because it doesn’t look so easy.”
While we have an accurate understanding of organic molecules—those with S and P orbitals—molecules whose orbitals interact with each other are currently beyond our ability to model accurately. Many of the answers we need to address significant issues, such as world hunger and global warming, come by way of understanding these more difficult molecules. Current technology doesn’t allow us to analyze some of the more complex molecules, however, this is an excellent problem for a quantum computer because input and output are small. There’s a unique approach in quantum computing where, instead of loading the input data, you’re able to encode it into the quantum circuit itself. Modelling molecules are an example of this; the initial positions of the electrons would be the input—also referred to as ‘preparation’—and the final positions of the electron would be the output.
Materials science
Modelling materials is essentially in the same problem class as modelling molecules, which means quantum computers are also helpful in identifying new possibilities in material science. The ability to develop high-temperature superconductors is a great example. We currently lose around 15% of the power in the energy grid every year due to the resistance in the wires transporting the electricity. Finding a material that can transmit energy without heating up the wires requires modelling properties of materials, a process very similar to modelling molecules. Again, this precise focus has a minimal amount of input and a highly focused output—both great candidates for quantum computing. In addition, materials have a regular structure with (mostly) local interactions making them generally easier to model than chemicals on a quantum computer.
Cryptography
Many cryptosystems are built using math problems more difficult than a classical computer is able to solve. However, a quantum computer has the computational ability to find solutions to the cryptographic algorithms in use today. Cryptographic problems that use factoring are excellent examples of problems that can be solved with a quantum computer because both the input and output are each a single number. Note that the numbers used in the key are huge, so a significant amount of qubits are needed to calculate the result. A quantum computer’s ability to solve cryptographic algorithms is an issue we take extremely seriously at Microsoft, and we are already working on quantum-safe cryptography protocols to replace those which will be vulnerable to quantum attacks.
Machine learning and optimization
In general, quantum computers aren’t challenged by the amount of computation needed. Instead, the challenge is getting a limited number of answers and restricting the size of the inputs. Because of this, machine learning problems often don’t make for a perfect fit because of the large amount of input data. However, optimization problems are a type of machine learning problem that can be a good fit for a quantum computer.
Imagine you have a large factory and the goal is to maximize output. To do so, each individual process would need to be optimized on its own, as well as compared against the whole. Here the possible configurations of all the processes that need to be considered are exponentially larger than the size of the input data. With a search space exponentially bigger than the input data, optimization problems are feasible for a quantum computer.
Additionally, due to the unique requirements of quantum programming, one of the unexpected benefits of developing quantum algorithms is identifying new methods to solve problems. In many cases, these new methods can be brought back to classical computing, yielding significant improvements. Implementing these new techniques in the cloud is what we refer to as quantum-inspired algorithms.
Quantum computing brings about a paradigm shift in multiple ways: Not only will quantum computing provide access to new levels of computational ability, but it will also inspire new ways of thinking. For a quantum computer to solve some of our biggest challenges, we have to understand how to frame the problem. As we look at problems in new ways, this shift can, in turn, bring new ideas to how we approach classical computation as well. With more and more individuals considering problems from different angles, more and more ideas and solutions will result. Luckily, you don’t have to wait until quantum computers are readily available to begin considering problems in new ways—you can start today by learning quantum development.
As you dive into the world of quantum development, you’ll practice your ability to think about problems in new ways, get familiar with programming a quantum computer, and even simulate your work so that you’ll be ready once quantum computers are made available.
Get started today with the Microsoft Quantum Development Kit.
