Buckle up for the Quantum Speedup

By faculty from the Department of Physics and the IAS Center for Quantum Technologies, HKUST

Math is hard. Take factorization as an example. We have learnt that, for instance, 21 = 3x7. The number 23 cannot be decomposed as such and is known as a prime number. You may think you have mastered such problems back in elementary school. If so, here is a challenge for you: what are the prime factors (if any) for 32,813,795,536,241?

Even if factorizing a 14-digit number does not pose a real challenge to you, you will likely admit that factorizing a 1000-digit number is beyond the limits of our brains. In fact, such problems are hard in a very sharp sense: even the best supercomputers today cannot factorize a 1000-digit number before our civilization ends. Yet, if we are provided with a possible answer, it is very easy to verify its validity: try multiplying 3441707 × 9534163 on your cellphone! Such math problems, which are very difficult to solve but are easy to verify, work like a combination lock: it takes forever to try out all the possible combinations, but if you know the passcode you can unlock it instantly. This is much more than a metaphor: the digital “locks” we frequently encounter in our everyday life can be understood in the same way. Similar principle extends even to, e.g., the basic ideas of cryptocurrency, for which the scarcity of the currency is ultimately tied to the difficulty in solving certain math problems.

The quantum hack—how quantum mechanics breaks the locks

The extreme hardness of guessing the right answer for such math problems forms the basics of digital security in our everyday life. What if someone can magically solve such math puzzles in an instant? They can then readily hack into our password-protected information! Alarming as it may sound, such hacking algorithms are known to exist. They emerge from the quantum world, where cats can be both dead and alive—at the same time—as in the Schrödinger’s cat thought experiment¹. Pictorially, a quantum hacker can sample all the possible combinations in one shot and tease out the correct answer by observing the interference pattern, similar to how radar detects the locations of nearby objects (Figure 1). Such quantum mechanical problem-solving approach is exemplified by the Shor’s algorithm, which offers an exponential speedup over the best classical algorithm in performing prime factorization. Correspondingly, a powerful quantum computer, once materializes, could become a major threat to our digital security.

Figure 1 Quantum mechanics enables parallel computing at a fundamental scale. By sampling all possibilities in one shot, it could offer an exponentially speed up on solving certain problems compared to a classical computer searching for the solution sequentially.

Quantum basics

To understand how such exponential speedup comes about, we have to introduce the idea of “quantum superposition.” We are used to a picture in which digital information is represented by a series of 0’s and 1’s, like 01000110 01101111 01110101 01101110 01100100 00100001 00111010 00101001… Each digit is called a “bit,” which can be in one of the two states 0 or 1. When we have a string of some number of bits, let us say four, there will be 2⁴=2x2x2x2 = 16 different possible states 0000, 0001, 0010, 0011,…, 1110, 1111. On a computer, we use these different possibilities to encode information. The number of possible states grow very rapidly (in fact, exponentially) with the number of bits. For instance, with 8 bits there will only be 2⁸=256 different states, but with 32 bits there will already be 2³²=4,294,967,296 (more than four trillions) possibilities! A quantum bit, or simply “qubit,” represents information based on the same principle. Yet, the quantum state of a qubit does not have to commit to being either 0 or 1—it can be simultaneously both. In physics, we refer to such non-commitment as a state of “superposition,” which is mathematically denoted as a sum of the two states: |0⟩+|1⟩. This is similar to comparing an adventurer trapped at either the north or south poles (classical) vs one who is free to explore the entire globe (quantum). Furthermore, the true quantum advantage emerges when we consider a string of qubits. By the same principle, a single state of the collection of qubits can simultaneously explore all the possibilities. This works in the same way as we expand brackets in elementary math: (├|0⟩+├|1⟩)⊗(├|0⟩+├|1⟩)=|00⟩+|01⟩+|10⟩+|11⟩. While this is only a single quantum state, it is simultaneously superposed between all the four possibilities in this two-bit system. Unlike a classical computer which can only access the possible states sequentially, a quantum computer can sample all the exponentially many possibilities using a single quantum state (Figure 2), and with 32 qubits a single quantum state could already be exploring all the four trillion possible states. This could lead to an exponential speedup in information processing, and correspondingly greatly reducing the time it takes to crack the most secure digital locks we have created.

Figure 2 A classical bit admits only two states, 0 and 1. These two states can be viewed as the two poles on a sphere. A qubit, or quantum bit, can instead take any value on the sphere, and as such it enables much more efficient information processing.

Into the quantum future

While it may be scary to imagine a world in which the most secure digital locks can still be easily cracked, it is comforting to know that building a powerful quantum computer imposes a tremendous technical challenge, and it will be a long way before we get there. In addition, the laws of quantum mechanics provide not only hacking capability, but also innate encryption schemes which are fundamentally unhackable. The field of quantum computing is a fascinating emerging area. From a software perspective, quantum algorithms can be designed and analyzed even before we succeed in engineering a quantum computer powerful enough to execute them. It should also be noted that a quantum algorithm does not always perform better than its classical counterpart, and it is an interesting active research area analyzing what classes of problems could be efficiently attacked using a quantum computer. From a hardware point of view, a near-term quantum device is really at its core a physics experiment tapping into the intricacy of the quantum rules governing our world at the smallest scale known to humans (Figure 3).

Figure 3 Development of quantum hardware and software is one of the hottest interdisciplinary research areas in the 21st century. On the one hand, quantum algorithms could be designed and analyzed before the advent of powerful quantum computers; on the other hand, the manufacturing and perfecting of quantum hardware probes into the fundamental laws of nature governing the microscopic world.

At HKUST, we conduct research at the quantum frontier using a variety of platforms like diamond color centers, ultracold atoms, complex materials, etc. Funded by the Education Bureau of the HKSAR Government and in partnership with the The Hong Kong Academy of Gifted Education, the Physics Department is also launching a new outreach program aiming at providing quantum training to interested secondary school students. The program will provide an in-depth introduction to the basics of quantum information processing and quantum algorithms, as well as hands-on experience for participants to program a quantum computer will be included. The quantum speedup may be closer to us than we thought—buckle up and join us!

¹ In this thought experiment, Schrödinger imagined what happened if we kept a cat in a room with a small device. The device releases some lethal poisonous gas dependent on the state of some microscopic particles, which, according to quantum mechanics, can be viewed as an on-off switch that is simultaneously both on and off. Correspondingly, the cat becomes simultaneously dead and alive. It should be emphasized that one should not take this absurd conclusion seriously—rather, this thought experiment aims to highlight the conceptual difficulty in reconciling the quantum mechanical with our daily-life experiences.