Quantum Computing

“Nature isn’t classical, dammit, and if you want to make a simulation of nature,you’d better make it quantum mechanical.”

Richard Feynman

How tough do you think is it to simulate a single molecule of caffeine?

Around 10⁴⁸ bits are required to represent it accounting for protons, neutrons, electrons, energy configurations, and all of its bonds. Using classical computers and traditional storage, it is next to impossible. The inevitable question is:

Can a quantum computer make it possible?

Qubit, the analogue of classical bit, has a game-changing feature called superposition.

A classical bit can be either 0 or 1 at a time but a qubit can exist in superposition i.e., it can be both 0 and 1 at the same time.

Analogy of qubit with Schrodinger’s cat

You can think of qubit as Schrodinger’s cat both alive and dead when box is not opened. But once the box is opened, the cat can be either alive or dead but not both. Opening the box breaks the superposition state of the cat into one definite state. Similarly, measurement breaks the superposition state of the qubit. Once the qubit is measured, it is forced to turn into either 0 or 1.

A single qubit holds two(2¹) bits of information. First is the probability of turning out to be 0 and second is the probability of turning out to be 1 on measurement. Two qubits hold 4(2²) bits of information, with probabilities of turning out to be 00, 01, 10, and 11. Similarly, n qubits hold 2^n equivalent classical bits of information.

Just with 160 qubits, we could store 2¹⁶⁰ bits, approx. 1.46*10⁴⁸ bits. It gives us the possibility that we might be able to simulate a molecule of caffeine in the future.

Problems that quantum computer solves faster

The first problem that revealed the beauty of quantum computers was the Deutsch-Jozsa (DJ) problem.

Suppose a black-box function which can be either a constant function or a balanced function. This black box takes in n-bit input and outputs

A. 1 for all the input combinations if it is constant-1 function or

B. 0 for all the input combinations if it is constant-0 function or

C. 1 exactly half of the time and 0 for the other half of the time if it is balanced.

For a 2-bit input black box, there are 4 possible inputs 00, 01, 10, 11 with which we can test the function. For an n-bit input black box, there are N=2^n possible inputs with which we can test the function.

Best case:

If for the first input, the output is 1 and for the second input, the output is contrasting(0), the black box function is a balanced function.

Worst case:

If we get the same output for N/2 different inputs, we need to try with just 1 more input and if the output is still the same, it means the function is balanced or else constant. e.g., if there are 64 possible inputs, we need to test at least 33 inputs.

Thus, this problem has (2^N/2 + 1 ) time complexity. In big-O notation, O(2^N) i.e., exponential time complexity.

To your surprise, this problem can be solved in constant time in a quantum computer, running a single test.

To prolong the awe, you can dive into Shor’s algorithm, a quantum algorithm for factorization problems that has time complexity of logn beating all classical algorithms.

Tip of the iceberg

Applications of quantum computing are ever-growing with rigorous research being done at the cross-junction of different domains. Recently, using google quantum computer physicists created a holographic wormhole. Security experts are finding ways to exploit quantum cryptography. Pharmaceutical engineers are willing to leverage it for drug design and discovery as well as to speed up biological research by simulating biological molecules. Quantum computers show some possibility to serve individual specialized drugs and vitamins one day. Not to miss, simulating the physics and chemistry of nature with high fidelity lies at the heart of it.

As of now, IBM Osprey is the largest quantum computer with 433 qubits. Before we realize the above endless possibilities, quantum computing still needs serious improvements in error correction as these systems are so sensitive to noise even a spare cosmic ray can wreck your entire computation.

Pause and Ponder

Nature at its core follows quantum mechanics i.e., it shows behavior like superposition, interference, and entanglement. Classical computers, which are built out of capacitors and transistors, cannot simulate it cause they do not model these quantum behaviors while qubits do. Qubits, in hardware of quantum computer, are modeled by the polarization of photons, spins of electrons etc.

Much like how Feynman said quantum computers are best at simulating nature whether it’s energy harnessing during photosynthesis or just a single caffeine molecule.

For further readings you can learn shor’s algorithm or explore qiskit more. Check for DJ implementation here.