Will Quantum Computers be Able to Solve Any Problem in Seconds?
In 1957 I began studying physics during my freshman year at Columbia University. This inspired my best friend, the editor of the college literary magazine, to write a short story about a first-year physics student (me) who planned as an extra credit activity to assemble an infinite group of monkeys, each with a typewriter. He wanted to test the idea that given enough time, the monkeys would produce all of Shakespeare’s works. When he told his physics professor about this project, the professor pointed out that he would need an infinite space to house them. “Imagine all the bananas you would have to buy for them. Why not create an infinite monkey instead? It could live in your bathroom.” The student thought this was a great idea. He created an infinite monkey, set it up with a typewriter and a few bananas. In a few days, the monkey reproduced all of Shakespeare’s sonnets and plays, although one contained the line “To banana or not to banana; that is the question.”
In a certain sense this story anticipates the quantum computer.
Quantum Mechanics: A fuzzy world of probabilities
To understand how a quantum computer works, you must first understand quantum mechanics. QM explains the physics of the microworld as well as how computer scientists are applying it to the macroworld we inhabit.
At the scale of atoms, the equations of classical physics, such as Newton’s laws, no longer work. This happens because in the world of quantum mechanics, objects exist in a haze of probability: sometimes here, sometimes there, sometimes in the present, sometimes in the future. In the macroworld where we live, objects exist in a specific place at a specific time.
Quantum mechanics (QM) describes a world where probability replaces certainty. Scientists believe that it is the most accurate theory ever devised in physics. Its predictions of the universal constants that control our universe agree to with a precision of ten or more decimal places. It is this precision that has recently led to the development of the quantum supercomputer, a machine that will enable us to do calculations that digital computers would requires centuries to complete.
The “Many Worlds” Interpretation of QM
QM’s “many worlds” view proposes that at every moment, we face infinite possibilities: whether to turn our car left or right, go to work or stay home, speak or remain silent. When we choose from these possibilities, all the other possibilities collapse into the one we select. Following this logic, the many worlds theory posits that there are myriads of worlds in the universe, only one of which are we aware. All these possibilities coexist in parallel universes.
In this world view, our lives are a never-ending succession of the choices we make at every moment. Throughout our lifetimes, we walk on a path that branches at every instant. The choices we make coexist simultaneously. In quantum physics, this means that every time an experiment with different possible outcomes is performed, all the possible outcomes are obtained, each in a different world, even though we are only aware of the outcome obtained in our world. This phenomenon is what gives a quantum supercomputer its unbelievable power.
Bits and qubits
In a digital computer, a number is represented by zeros and ones. Suppose for example you want to store a number and you have 4 bits (a bit is either 0 or 1). Here are the 16 possible arrangements you can construct:
0000 0001 0010 0100
0100 0101 0110 0111
1000 1001 1010 1100
1100 1101 1110 1111
Let’s say that one of these numbers is the password to unlocking a safe. To find the correct number, a digital computer would have to examine the 16 possibilities, one at a time.
A quantum computer does not have this limitation. Quantum bits or “cubits” can be either 0 or 1 like ordinary bits, but they can also be 0 and 1 at the same time. This seems quite strange, until you think about flipping a coin. While it is in the air, it is both heads and tails. One might even argue that it’s heads and tails at the same time. When it lands, it has “chosen” a side — either heads or tails.
If we construct numbers with quantum bits, which can be zero and one at the same time, the bits are all of the possibilities at the same time. A technique called the “Grover Operator” named for a Sesame Street character, sweeps away the wrong numbers and leaves you with the correct password. Modern cybersecurity employs encryption so complex that would take a digital computer millions of years to work through all the possibilities. A quantum computer can do this in a few minutes.
Applications of quantum computing
Virtually any problem that takes too long for an ordinary computer to solve is fair game for a quantum computer. Google announced in 2019 that its Sycamore quantum computer solved a problem in three minutes that would take the fastest digital computers thousands of years. Similarly, problems that were previously thought to be unsolvable, may now yield discoveries in many fields due to quantum computing.
Quantum computers are difficult to build. They require near absolute zero temperature to operate. They are error-prone at this stage in their development. There are types of calculations that will still be better handled by conventional computers even when powerful quantum computers begin to emerge. But the potential is so great that already scientists are creating working models for a broad range of applications. Here are just a few of the fields which will benefit from quantum computing.
Artificial Intelligence
AI is based on the principle of learning from experience, becoming more accurate as feedback is given, until the computer program appears to exhibit “intelligence.” Quantum computers will provide access to trillions more data points than digital computers can handle, increasing the power and accuracy of AI machines.
Drug Design
Creating a vaccine is costly and time-consuming. Conventional computers require years to come up with solutions to the molecular pathways that drugs could take to kill a virus. Quantum computers can solve the pathway problem in a trillionth of the time. The ability to accelerate drug design through quantum computing could reduce the high costs and long timeframe for bringing a life-saving drug to market.
Quantum computers could also accelerate the development of vaccines for COVID-19-like viruses. Vaccine design requires complex computing. During the design phase, scientists create molecular simulations to understand the protein structure of the virus. The development of a vaccine for COVID-19 has an expected timeline of 12 to 18 months. Quantum computing has the potential to reduce these timelines dramatically.
Cryptography
Most online security is impacted by the difficulty of factoring large numbers into primes. Primes are numbers such as 7, 11 that have no factors. While digital computers can accomplish this, the immense time required makes “cracking the code” expensive and impractical. Quantum computers can factor large numbers into primes exponentially more efficiently than digital computers, making many of today’s security methods obsolete.
Banking and Investment
Because of the complexity of the financial world on a global scale, most banks rely on financial models designed by digital computers. Banks assess a range of potential outcome by using algorithms and models that calculate statistical probabilities. Quantum computing can crunch vast amounts of data at speeds that digital computers cannot. The increased speed of computation that quantum computers offer could help banks make better financial decisions with far lower risk.
Molecular Modeling
“Quantum chemistry” is so complex that only the simplest molecules can be analyzed by today’s digital computers. Chemical reactions are quantum in nature as they form highly entangled quantum superposition states. Precision modeling of molecular interactions, such as finding the optimum configurations for chemical reactions, are within the capability of quantum computers.
Want to produce and sell fertilizer? Fertilizer is made from nitrogen and hydrogen, which combine to form ammonia. The complexities of this chemical is hampered by the mazelike electrostatics involved in combining the two elements. The fastest digital computers will take 800,000 years to find all the possible solutions. A quantum supercomputer can produce the same results in a day.
Weather Forecasting and Climate Change
Nearly 30% of the US GDP ($6 trillion) is directly or indirectly affected by weather, impacting areas such as food production, transportation, and retail trade. The ability to better predict the weather would have enormous benefit to many fields. The mathematical models that describe weather behavior requires quantum computing to solve. Quantum computing also has the potential to deal with carbon storage and energy production issues that can help nations meet the Paris Agreement’s goal of limiting global temperature rise to under 2 degrees Celsius.
Particle Physics
Models of particle physics are often extraordinarily complex and require vast amounts of computing time for numerical simulation. For example, quantum computers could analyze the vast amount of data produced by experiments on the Large Hadron Collider (LHC) at CERN. The LHC produces a million gigabytes of data from a billion particle collisions per second. Researchers anticipate that a “quantum support vector machine” will help them easily dissect and evaluate the data. This could lead to breakthroughs in our understanding many particle physics phenomena.
FROM THEN TO NOW …
If you still question the possibility of a device as powerful as a quantum computer, simply look back a few decades to see how far we’ve come in such a short amount of time.
While a graduate student at Yale in 1965, my friend and I took a course at a new IBM computer center on campus. Our professors ridiculed our belief that computers could help solve research problems and told us we were wasting valuable time. We ignored their derision.
In about a week we were able to write a computer program in the now obsolete language of Fortran. Our department had a very primitive computer, an IBM 1040. I programmed an equation that described the movement and arrangement of gold and copper atoms under very high pressures. The IBM 1040 took 19 hours to solve the equation and produce a graph, which closely agreed with my experimental results. This supported my research findings and made them more credible.
During my PhD thesis defense, I explained to our professors why I needed the computer and showed them my results. This was new territory for them.
After receiving my PhD, I went to the University of California campus at Riverside as a postdoctoral physics researcher. UC Riverside had an IBM 360, a much more powerful machine than the IBM 1040. I programmed the 360 to solve my PhD thesis equation. It took the machine about one minute to produce a solution.
My current Apple laptop can solve this equation in the time it takes me to press the key.
