The Map of Quantum Computing – Quantum Computing Explained

**Sanitized Transcript:**

This video is sponsored by Qiskit; more details later in the video.

From the first idea of a quantum computer in 1980 to today, there has been significant growth in the quantum computing industry, especially in the last decade. With numerous companies and startups investing hundreds of millions of dollars, there is a race to build the world’s best quantum computers. For many, understanding quantum computing can be challenging, and much of the available information tends to overlook important details. This video aims to clarify these concepts, and by the end, you will have a solid overview of the different types of quantum computing, how they function, and the reasons behind the substantial investments in this field.

Quantum computers solve problems differently than classical computers. Quantum computers have certain advantages for specific problems due to their ability to exist in many states simultaneously, while classical computers can only be in one state at a time. To grasp how quantum computers work, you need to understand three key concepts: superposition, entanglement, and interference.

The basic units of classical computers are called bits, while those of quantum computers are called quantum bits, or qubits. They operate in fundamentally different ways. A classical bit functions like a switch that can be either a 0 or a 1, which is the binary information you may already know. When we measure a bit, we simply obtain its current state. However, qubits are more complex. You can visualize them as arrows in 3D space. If an arrow points up, it represents the 0 state; if it points down, it represents the 1 state. Qubits can also exist in a superposition state, where the arrow points in any other direction, representing a combination of 0 and 1.

When measuring a qubit, the output will still be either a 0 or a 1, but which one you get depends on a probability determined by the direction of the arrow. If the arrow points more upwards, you are more likely to get a 0; if it points downwards, you are more likely to get a 1. If it is exactly on the equator, you have a 50% chance of getting either state.

Next, let’s discuss entanglement. In classical computers, bits are independent of one another; the state of one bit does not affect the state of another. In quantum computers, qubits can become entangled, meaning they form a single quantum state. For example, consider two qubits in different superposition states that are not yet entangled. Their probabilities are independent. However, once entangled, the probabilities must be recalculated based on the combined states. If you change the direction of one qubit’s arrow, it alters the probability distribution for the entire system, indicating that the qubits are no longer independent.

For one qubit, you have a probability distribution over 2 states; for two qubits, over 4 states; for three qubits, over 8 states. In general, a quantum computer with n qubits can exist in a combination of 2^n states. This is a core difference between classical and quantum computers: classical computers can be in any state but only one at a time, while quantum computers can be in a superposition of all states simultaneously.

You might wonder how this superposition can be useful. This leads us to the final component: interference. To explain interference, we refer back to the Bloch sphere representation of a qubit. While this is a useful visualization, the actual state of a qubit is described by a quantum wavefunction, which is the fundamental mathematical description in quantum mechanics. When multiple qubits are entangled, their wavefunctions combine into an overall wavefunction that describes the quantum computer’s state. This combination can lead to constructive interference, where waves add together, or destructive interference, where they cancel each other out.

The overall wavefunction sets the probabilities of different states, and by manipulating the states of various qubits, we can influence the probabilities of the outcomes when measuring the quantum computer. Even though a quantum computer can exist in a superposition of many states, measuring it yields only a single state. Therefore, when solving computational problems with a quantum computer, one must use constructive interference to enhance the probability of the correct answer and destructive interference to reduce the probabilities of incorrect answers.

The motivation behind quantum computing is that there are problems believed to be intractable for classical computers but solvable on quantum computers. One of the most famous quantum algorithms is Shor’s algorithm, which efficiently finds the factors of large integers. This is significant because while multiplying two large numbers is straightforward, determining the original numbers from their product (factorization) is much more challenging. This difficulty underpins the security of many internet encryption methods.

In 1994, Peter Shor published his algorithm, which demonstrated that quantum computers could factor large integers efficiently, raising interest in quantum computing due to its potential real-world security implications.

To understand how much faster Shor’s algorithm is compared to classical methods, we delve into quantum complexity theory, which categorizes algorithms based on their efficiency. Problems solvable in polynomial time are considered easy for classical computers, while those outside this category, like integer factorization, are not efficiently solvable. Quantum computers can tackle problems in the BQP category, which are efficiently solvable by quantum but not classical computers.

The complexity of a problem, such as factorization, increases exponentially as the size of the number grows. Shor’s algorithm, which operates in polynomial time, represents a significant advancement in complexity theory, transforming an intractable problem into a solvable one, provided a functioning quantum computer is available. However, current quantum computers lack the capability to run Shor’s algorithm on large numbers, as they would require approximately a million qubits, while the most advanced systems today have around 100.

Researchers are also exploring post-quantum encryption schemes that do not rely on integer factorization, along with quantum cryptography. While Shor’s algorithm is a notable example, there are many other quantum algorithms, such as Grover’s algorithm, which can search unstructured data faster than classical algorithms.

It’s important to recognize that classical computers are versatile and may yield efficient algorithms for complex problems. While it seems unlikely, it is not impossible for someone to discover a more efficient classical algorithm for integer factorization. Additionally, some problems are provably non-computable on both classical and quantum computers, indicating that computationally, both types of computers are equivalent; their differences arise from the algorithms they can execute.

Simulating a quantum computer on a classical computer becomes exponentially more challenging as the number of qubits increases. Classical systems struggle to simulate quantum systems, while quantum computers, being quantum systems themselves, do not face this issue. This leads us to quantum simulation, which involves simulating phenomena like chemical reactions or electron behaviors in materials. Quantum computers can provide exponential speedups in these simulations, as classical computers find it difficult to model quantum systems.

While we currently lack quantum computers capable of solving real-world problems more effectively than classical computers, potential applications include optimizing materials, improving solar panels, enhancing batteries, and developing new drugs. Quantum simulation could enable rapid prototyping of materials, significantly reducing the time and cost associated with traditional lab testing.

Other potential applications of quantum computing extend to optimization problems, machine learning, financial modeling, weather forecasting, and cybersecurity. However, it’s essential to approach claims about quantum computing’s capabilities with caution, as many originate from individuals seeking funding.

Historically, the true applications of new technologies often become clearer only after their introduction. For instance, early computer inventors could not have predicted the internet’s emergence. Similarly, the potential of quantum computers may unfold in unexpected ways.

Now, let’s shift focus to the practical aspects of building quantum computers. While some physicists remain skeptical about achieving the scale necessary for real-world applications, many researchers are actively pursuing various approaches to quantum computing.

Quantum computing is not a singular concept; it encompasses a range of models and physical implementations. The models refer to the methods of manipulating qubits, while the physical implementations involve the actual quantum systems used to create qubits.

The most widely used model is the circuit model, where qubits are entangled and manipulated using quantum gates. A quantum algorithm consists of a sequence of gates applied to qubits, followed by a measurement to obtain the final state. These gates can be thought of as operations that rotate the qubits’ arrows to change their probabilities.

For those interested in learning more about quantum computing, I recommend the educational resources provided by Qiskit, which is funded by IBM. Qiskit offers a free, open-source software framework designed to facilitate entry into quantum computing. Their online textbook covers the basics, making it accessible to those without a quantum physics background. The Qiskit YouTube channel features tutorials and lectures, and users can run quantum circuits through their online tools or download the SDK to execute programs on IBM hardware.

Now, let’s explore the various models of quantum computing. In addition to the circuit model, there is measurement-based or one-way quantum computing, which involves creating an initial entangled state and measuring qubits sequentially during computation. This approach has been mathematically shown to be equivalent to the circuit model.

Adiabatic quantum computing operates differently, leveraging the principle that systems tend to move toward their minimum energy state. By framing problems so that the minimum energy state corresponds to the solution, adiabatic quantum computing can yield correct answers when measured.

Quantum annealing, closely related to adiabatic quantum computing, also seeks the minimum energy state but is not a universal quantum computing scheme. It can solve specific optimization problems and simulate certain quantum systems.

Topological quantum computing is a theoretical model that utilizes Majorana zero-mode quasi-particles, which are predicted to be more stable than traditional qubits due to their unique properties. These quasi-particles are thought to be protected from noise, a significant challenge in quantum computing.

In terms of physical implementations, there are various approaches to building quantum computers, including superconducting qubits, quantum dot quantum computers, linear optical quantum computing, trapped ion quantum computers, nitrogen vacancy quantum computers, and neutral atoms in optical lattices. Each method has its advantages and challenges.

Superconducting quantum computers are currently the most popular, utilizing superconducting wires with a Josephson junction. Quantum dot quantum computers use electrons or groups of electrons, while linear optical quantum computers employ photons of light. Trapped ion quantum computers leverage charged atoms, and nitrogen vacancy quantum computers embed atoms within materials.

Neutral atoms in optical lattices capture atoms in a crisscrossed arrangement of laser beams, allowing for control and entanglement. While these approaches are promising, they face challenges related to decoherence, noise, and scalability.

Decoherence occurs when quantum systems interact with their environment, leading to information loss. Researchers are exploring quantum error correction methods to create fault-tolerant quantum computers, which may require hundreds to thousands of physical qubits to represent a single noise-free qubit.

Scalability is another significant challenge, as the complexity of controlling and measuring qubits increases with their number. Each qubit requires additional infrastructure, making it essential to design scalable quantum computer architectures.

In summary, the landscape of quantum computing is diverse, with various models and physical implementations being explored. While the future remains uncertain, the potential applications and advancements in this field are exciting.

Stay tuned for my next video, where I will discuss companies and startups in quantum computing, their approaches, and future roadmaps. You can find the map of quantum computing available for purchase or download for educational purposes at dosmaps.com.

Thank you to all my Patreon supporters for your invaluable support. I look forward to seeing you soon!