Written by Raiyan Rizwan, Alexa Ramirez, and Elias Lehman
In Partnership with Quantum Computing at Berkeley
“The key distinction between classical and quantum computing, beyond the physics governing their units of information, is how they process information”
SECTION 1
Headlines about the fascinating problems that quantum computers are capable of solving hint at the fundamental difference between these computers and their classical counterparts. Quantum and classical computing are two different approaches to processing and manipulating information–they are intended to do the same things, like simulations, arithmetic, and analysis. The difference is in the unit of information that is processed on said computer. Classical computing refers to the traditional approach to computing that relies on classical physics and the manipulation of bits. Quantum computing, on the other hand, is a newer field that involves the use of quantum-mechanical phenomena, such as superposition and entanglement, to perform computing.
The key distinction between classical and quantum computing, beyond the physics governing their units of information, is how they process information.
In classical computing, bits are represented by one of two values: 0 or 1. These are then manipulated using logical operations, such as AND, OR, and NOT, to perform various tasks. Quantum computing, on the other hand, uses quantum bits, or qubits, which can represent both 0 and 1 with some probability of each through the principle of superposition, as we will explore in section 2.2. But, the probabilistic character of qubits alone is not at the root of quantum computing applications – it’s the ability to create dependencies, formally known as entanglement, between quantum states which allows for the elimination of possible outcomes faster. We call the elimination of a state’s probability interference. The advantage of quantum computers is leveraged strongest when these principles of quantum mechanics are working their hardest.
Another difference between classical and quantum computing is how they handle errors.
Transistors, the physical objects representing classical bits, are resilient to errors such as environmental interference which could incorrectly flip one from 0 to 1. Classical computers use error-correction techniques, which have been tested over many years, to detect and correct errors that may occur during computing. Quantum computers are more susceptible to errors because quantum-mechanical systems can be disturbed by external forces such as light radiation and temperature. As a result, quantum computers require specialized techniques, referred to as quantum error correction, to handle errors and maintain the integrity of the computing.
In summary, classical and quantum computing are two different approaches to processing information, with classical computing relying on classical physics and the manipulation of bits, and quantum computing using quantum-mechanical phenomena and the manipulation of qubits. While both approaches have their strengths and limitations, quantum computing has the potential to revolutionize the field of computing by allowing for faster and more efficient computing in certain cases, once their chronic errors have been mitigated.
KEY IDEAS:
Quantum procedures are not a wildly different concept than classical forms; meaning is extracted from and superimposed onto the physical universe to solve (often computationally heavy) problems. Thus, representation is of key importance. While electrical signals are deterministic (repeatable, set outcome), the study of quantum mechanics tends to be centered around probability. This implies a natural randomness to every measurement of a quantum circuit.
The physical property of quantum bits, qubits, (of any form) that most interests us is superposition; the nature of quantum particles to be in a distinct but unknown state. To clarify, it is not quite the case that a particle is physically in two states at once (as often misconstrued in the media), but rather that we simply don’t know which of two states it is in. We thus portray qubits as existing in a kind of transient, pre-measurement middle ground.
The two fundamental, stable quantum states are written as |0> and |1>. To an algorithms researcher, these basis kets (|>) have an arbitrary meaning that is directly dependent on the physical implementation of the computer. |0> and |1> could refer to electron spins or to the direction of current in a superconducting qubit; either way, they are well-defined, physical, and mathematical bases for the system. There are infinite other states that relate to particles in superposition. These “in-between” states exist mathematically in a Hilbert, or complex, vector space and are further conveniently depicted along the surface of a geometry known as the Bloch sphere.
The Bloch Sphere is a mathematical construct that exists in one complex and two real dimensions. Consider the unit circle in a
flat plane; if we were to pull a vector along the span of its perimeter in or out of the page without changing its magnitude, we would have a sphere. This pulling corresponds to a rotation in the complex plane and adds a dimensionality that allows us to describe any point along the surface of this pseudo-sphere using only two coordinates, each complex. The Bloch Sphere is an example of a Hilbert Space that accommodates stable and superposition states, phases, and other single-qubit characteristics. We use these tools to visually understand how a qubit leans toward one or the other basis, and they can be mathematically manipulated to mirror physical processes.
Superposition is a unique property of qubits, and linear algebra is a choice of mathematical representation. An in-depth discussion of the choice of complex numbers to architect quantum mathematics is beyond the scope of this paper, though fascinating. The power of these choices and properties will become apparent in section 2.3.
Quantum data is single-use. As soon as we make a measurement, all probabilities relating to superposition or entanglement (often denoted via the wave function ψ) “collapse” into a possible state. Notably, this makes copying quantum states through purely quantum methods (for individual qubits and larger systems) impossible, because any copies will have identical probability mappings rather than the same measured random outcome.
Read section 3 before this. An important distinction must be made concerning the measurement of entangled quantum particles. A thought experiment by John Bell in 1964 proved that an entangled quantum particle is not bound to a definite value until it or its counterpart is measured. The 2022 Nobel Laureates in Physics experimentally confirmed this. Thus, entangled particles do exist in a true ambiguity of states until one or both are measured.
“I would not call [entanglement] one but rather the characteristic trait of quantum mechanics, the one that
enforces its entire departure from classical lines of thought.”
– Erwin Schrödinger
To the sci-fi-inspired reader, entanglement may ignite visions of instantaneous communication at a potentially boundless distance but unwavering, nature does not allow faster than light (FTL) communications. The inability to force an entangled quantum particle into a particular state ruins our chances of building a transmitter. Moreover, there is no known method of simply observing changes to a particle’s state without measuring it and consequently, collapsing its entanglement, ruining our chances of building an unbiased receiver.
The upshot of entanglement is its utility in quantum algorithms and potentially, cybersecurity since tampering is unavoidably easy to detect in entangled quantum particles (due to the fused nature of observation and measurement). Another useful process, quantum teleportation, uses the phenomena in tandem with classical information transfer to indirectly “copy” an unknown quantum state without directly needing to transplant that particle, and over long distances (though not FTL).
Much of the baseline quantum computing ideas we study today hover around what
The X-gate functions as a classical NOT which flips a classical bit: X|0> → |1>. The Hadamard (H) gate was designed to create an even superposition, wherein the output qubit has a 50-50 chance of being in the |0> or |1> basis. The |+> state is an example of one such output qubit.
Most quantum states are nothing more than a linear combination of the basis states, along the lines of α|0> + ß|1>, where the weights α and ß are called probability amplitudes, designed to depict the probability of our qubit being in the |0> or |1> state. For the |+> state, α = ß = √½. Taking associated amplitude to the power of 2 gives the probability of being in that state. Thus, the |+> state depicts a ½ probability of the qubit being |0> or |1>.
A mathematical operation called a tensor product is used to represent joint qubit states. For example, the two-qubit system |+0>, is the tensor product of |+> and |0>. The beauty (and utility) of tensors is that the |+0> state mathematically decomposes into √½|00> + √½|10>, characterizing a system that has a ½ probability of being in the |00> or |10> states (notice that the right qubit, which was never in superposition, is always in the |0> state; whereas the left qubit, the |+>, exists evenly between |0> and |1>).
This notation visually clarifies probability analysis for multi-qubit systems.
As a final example, the controlled-NOT, or CNOT gate is a useful application for entanglement wherein two qubits are joined such that if the control qubit is in the |1> state, the state of the target qubit is flipped. As an example, let’s pass a |+> control and a |0> target qubit through a CNOT gate, entangling them. The control qubit has a 50-50 probability of being |0> or |1>. Thus, there is a 50-50 probability of the target qubit being flipped. When we measure the target qubit we will know with 100% certainty the state of the unknown control qubit: |0> if the target hasn’t changed and |1> if the target has, all without interacting with the control, and even at a physical separation of thousands of lightyears!
As a final example, the controlled-NOT, or CNOT gate is a useful application for entanglement wherein two qubits are joined such that if the control qubit is in the |1⟩ state, the state of the target qubit is flipped. As an example, let’s pass a |+⟩ control and a |0⟩ target qubit through a CNOT gate, entangling them. The control qubit has a 50-50 probability of being |0⟩ or |1⟩. Thus, there is a 50-50 probability of the target qubit being flipped. When we measure the target qubit we will know with 100% certainty the state of the unknown control qubit: |0⟩ if the target hasn’t changed and |1⟩ if the target has, all without interacting with the control, and even at a physical separation of thousands of lightyears!
SECTION 3
Specific problems in the topic of quantum computation include the understanding of finding a step-by-step solution that can be later on performed by a quantum computer. This chapter will demonstrate how an algorithm is an introduction to a range of fields that involve the basics of physics, chemistry, and machine learning.
Quantum algorithms are designed to take advantage of the unique capabilities of quantum computers to solve problems more efficiently than classical computers. One well-known quantum algorithm is Shor’s algorithm for integer factorization, which can be used to find the prime factors of a given integer. This specific algorithm is an important development in the field of cryptography to break widely used public key cryptographic systems. Another notable quantum algorithm would be Grover’s algorithm, which can be used to search an unsorted database more quickly than other algorithms — including the quantum Fourier Transform — due to how mathematical operations are being performed more efficiently.
Shor’s algorithm is a quantum algorithm for integer factorization, which can be used to find the prime factors of a given integer. The algorithm works by using a quantum computer to find the period of a particular function. The function used in the algorithm is the modular exponentiation function, which takes two inputs, a base and an exponent, and returns the remainder when the base is raised to the exponent and divided by a given number.
The key insight of Shor’s algorithm is that the period of this function is related to the factors of the number being factored. By finding the period using a quantum computer, the algorithm can then use classical methods to determine the factors of the number in question.
This algorithm has the potential to solve problems that are believed to be intractable on classical computers. For instance, the problem of integer factorization is believed to be difficult for classical computers, as the time required to find the prime factors of a large integer grows exponentially with the size of the integer, meanwhile, this specific algorithm can solve this problem in polynomial time. Overall, Shor’s algorithm is an important development that has the potential to significantly impact many different fields.
Grover’s algorithm — which was developed in 1996 by physicist Lov Grover — is a quantum algorithm that can be used to search an unsorted database more quickly than other known algorithms. This algorithm works by using a quantum computer to search a database of N items in ON time, which is significantly faster than the O(N) time required by classical algorithms. Leveraging the ability to put qubits into a superposition of states, and operations that combine or interfere with probabilities of these states, Grover’s algorithm highlights the correct state quicker than classical means. In a real system, this correct state can be associated with a single item hidden in an unsorted list, like a marble under a cup for example. Unraveling the apparent mysteries of Grover’s algorithm requires deep mathematical analysis, but it can become much more intuitive if one understands amplitude amplification, as is explained below.
To perform a search using Grover’s algorithm, the quantum computer must be initialized with a quantum state that encodes the search criteria. The algorithm then iteratively applies a series of quantum operations to this state, each of which performs a step in the search process. These operations are designed to amplify the amplitude of the quantum state corresponding to the search result, while this will simultaneously decrease the amplitude of other states. After a sufficient number of iterations, the quantum state will be highly concentrated around the search result, and the result will be able to be determined by the measuring state, as the number of iterations required depends on the size of the database and the accuracy of the search result desired.
Grover’s algorithm is an important theoretical development in the field of quantum computing, as it demonstrates that quantum computers can perform certain tasks more efficiently than classical computers, which has stimulated further research into the development of many applications, with the inclusion of database search, optimization, and machine learning.
The Hamiltonian Simulation is a task of approximating the time evolution of a given quantum system according to its mathematical representation of the system’s energy, known as its Hamiltonian. This task is essential because it can be used to simulate the behavior of quantum systems, which can help researchers understand and predict the properties of these systems.
Several algorithms can be used to perform a Hamiltonian simulation by using quantum-mechanical phenomena, as they will include the quantum phase estimation algorithm and the quantum approximate optimization algorithm. These algorithms usually work by preparing a quantum state that represents the initial state of the system and then applying a series of quantum operations to this state to simulate the time evolution of the system. As the Hamiltonian simulation has many potential applications, the result of this simulation can be determined by measuring the final quantum state, which will exhibit complex and counterintuitive behaviors that are difficult to understand in a classical computer. This is an important theoretical development in quantum computing, as it can stimulate the behavior of quantum systems more efficiently to impact different fields.
On December 22, 2022, the financial institution Kutxabank collaborated with the company Quantum Mads and the open innovation platform INNOLAB Bilbao to develop the improvement of allocation assets of Kutxabank’s investment portfolio by a digital annealer — a Fujitsu quantum-inspired solution. This project is based on two phases, which will be concluded by December 2023, as it will aim to optimize functionalities by interacting quantitatively with the model in a real and current environment. This project is mainly to create a prototype capable of detecting needs and opportunities that are covered by Kutxabank’s financial institution, which will include a technological solution in a real environment.
Quantum algorithms have the potential to revolutionize topics involving materials science, machine learning, and drug discovery, due to the potential to significantly improve the performance of learning systems by leveraging the power of quantum computers to perform computation more efficiently. However, quantum computers are still being improved and developed, making them not widely available; as such, the development and implementation of quantum algorithms is currently an active area of research.