Overview Of Quantum Computing
I think I can safely say that nobody understands quantum physics. — Richard Feynman.
After 50 years of extraordinary growth, we now find ourselves at the
twilight of Moore’s law where we need to reinvent the core technologies to sustain the computational needs of the world. As data continues to double, we need new computing platforms and a reversal of IT ideologies to process such a massive amount of data.
Breakthroughs such as specialized chips for machine learning
and distributed computing as opposed to server farms are already making headways in the computing arena. The next big advancement in computing is supposed to come from our ability to build infrastructure that can probe the quantum nature of fundamental particles as opposed to the classical paradigm of computing that we rely on currently.
Present-day computers work based on the principles of classical physics mechanics, imagine a coin in a classical regime, when we toss it, it can take up the ‘head’ (H) of the ‘tail’ (T). But in the quantum world, a coin can exist in both ‘head’ & ‘tail’ simultaneously and this property of quantum mechanics — existing in simultaneous states- is known as superposition.
In this article, we will talk about :
- What’s quantum theory?
- First Quantum Computer.
- Qubits & Multiple Qubits.
- Bell State.
- Quantum properties.
- Quantum gates.
- Quantum algorithms.
- References.
What’s quantum theory?
The figure above shows a brief historical overview of quantum theory, we can see that it starts in 1900 when Max Planck introduced the idea that energy can only take discrete values as if existing as quanta or small energetic portions. With this assumption, he was able to resolve a heated debate regarding the spectrum of black-body radiation. Almost at the same time (1905), Albert Einstein made a similar discovery derived from the statistical
mechanics of gases and derived the concept of a photon — a portion or energy quantum of light.
In the following years, these ideas of a “theory of energy quanta” were
applied to atomic spectroscopy (especially by Niels Bohr), and in the light (by Louis de Broglie) but still based on rather ad-hoc methods.
Werner Heisenberg followed by Jordan, Born, and independently, Paul Dirac made the first mathematic formula of quantum theory referred to as matrix mechanics in 1925.
In 1926, following a slightly different and less abstract route, Erwin Schrödinger proposed his famous equation of motion for the ‘wave
function’ that describes the state of a quantum system. These two approaches were shown to be equivalent in the 1930s, and a more general version was finally proposed by Dirac and Jordan.
In the following years, quantum theory branched out into many
sub-disciplines such as quantum many-body systems, quantum thermodynamics, quantum optics, and, last but not least, quantum information processing and quantum computing.
First Quantum Computer
In 1998 Isaac Chuang of the Los Alamos National Laboratory, Neil Gershenfeld of the Massachusetts Institute of Technology (MIT), and Mark Kubinec of the University of California at Berkeley created the first quantum computer (2-qubit) that could be loaded with data and output a solution.
But their system didn’t perform well, it was coherent for only a few nanoseconds and trivial from the perspective of solving meaningful problems.
In March 2000 Emanuel Knill, Raymond Laflamme, Rudy Martinez of Los Alamos, and Ching-Hua Tseng of MIT announced that they had created a 7-qubit quantum computer using trans-crotonic acid.
And many quantum computers were created after that using different techniques. Recently IBM announced the newest quantum-computing chip, revealed on 15 November, establishing a milestone of sorts: it packs in 127 quantum bits (qubits).
Qubits & Multiple Qubits
Qubit: A qubit or quantum bit is the smallest unit of quantum computing, unlike the classical bit which can only take the value 0 or 1, the qubit can exist on a superposition of states (take 0 and 1 at the same time). Each qubit has a more complex structure than the classical bit, and its multi-state attributes allow it to store more information and process it simultaneously, increasing its speed.
The qubit is subjected to new properties called superposition and entanglement.
And according to Dirac notation, the state of qubit |ψ⟩ can be expressed as a linear combination of the basis states |0⟩ and |1⟩, as shown below :
where α and β are complex numbers, i.e., α, β ∈ ℂ. And they represent the amplitude of |0⟩ and |1⟩ respectively.
Now to understand more about α and β represent, let’s interpret the state of qubit |ψ⟩, if we analyze its algebraic formula we will find that it has a probability of |α|2 of appearing in state |0⟩ and a probability of |β|2 of
appearing in state |1⟩, where the sum of probability of appearing in either one of the computational basis states should sum to 1 since the states are mutually exclusive and exhaustive (see the figure below).
Bloch Sphere Representation of a Qubit
We have already discussed that, unlike the classical bit, the quantum bit can exist in a continuous infinity of states from |0〉 to | 1〉.
It’s really important to take a look at a geometric representation of a qubit in terms of what is called a Bloch sphere representation of a qubit (see the figure below ).
So as the figure shows every single point in the block sphere represents a qubit state, and the generalized state of the qubit |ψ⟩ can be represented by the three parameters: γ, θ, and φ and by the following formula :
Where α and β both are complex numbers, and each one of them has two degrees of freedom.
Multiple Qubits :
With two classical bits, we can have four states: 00, 01, 10, and 11. But in a quantum system with 2 qubits A and B can be in the superposition of the 4 states corresponding to the computational basis states 00, 01, 10, and 11, which we represent like follow :
α_00, α_01, α_10 and α_11 are complex numbers and the components of a unit norm vector, where the square of these amplitude magnitudes should sum to 1 (just like in the state of a single qubit) :
Bell State
One of the most interesting two-qubit states is the state represented by the following:
The Bell state is the superposition of the states ∣00⟩ and ∣11⟩ in equal proportion. If we observe qubit A and measure its state to be ∣0⟩, then the two-qubits state collapses to the state ∣00⟩.
now If we measure the state of qubit B, then there is only one form we can find for qubit B, the state ∣0⟩. And the same thing if we measure qubit A to be in state 1, so the two-qubit state collapses to state ∣11⟩, in this case, we are certainly sure that we will find qubit B in state 1.
So in the bell state, the state of the two qubits are perfectly correlated and this quantum phenomenon is known as ‘quantum entanglement’.
Quantum properties
so far we have seen that quantum computing is very different from classical computing and has very particular properties that we have presented in this section.
Superposition :
The principle of superposition is fundamental to quantum physics. And it represents the ability of a quantum system to be in multiple quantum states at the same time.
To understand this principle we will take the example of an atomic qubit based on an electron exhibiting its UP or DOWN spin and affected by a magnetic field. The electron is not spinning in a traditional sense, the word spin describes its angular momentum, which can be quantized to mean UP or DOWN (1 or 0). So it is in a superposition state, which means it can be in a fraction of a 0 or a 1.
In other words, weighted combinations like 0–37%, 1–63% (the α and β parameters of the qubit’s state (|ψ⟩ = α|0⟩ + β|1⟩)).
Physicists have not yet developed a way to visualize the reality that underlies spin. But they can describe spin mathematically and predict its behavior in lab experiments.
The figure below describes this phenomenon of superposition :
collapses when measured to give a discrete state
Entanglement :
Entanglement Is a phenomenon based on Einstein’s ‘Spooky Action at a distance’ principle, where two qubits forming a linked system, their quantum states are dependent on each other whatever the distance between them. And in classical computing, it comes down to having a logic gate that connects each bit in memory with another bit.
According to the figure above, this phenomenon let us to deduce the state of the other entangled qubit(s) no matter how far the physical distance between them is. So entangled qubits become a system with a single quantum state.
Interference :
It is the quantum phenomenon that causes logical computational paths to interfere with each other constructively or destructively.
To understand this principle we have taken an example of noise cancellation, as found in headphones, so to cancel it we will apply the principle of superposition and the principle of interference in order to reduce the amplitude of the noise while using a tone of the same frequency and amplitude, but with a phase shift of a value of π or another odd value of π.
Quantum parallelism :
Quantum parallelism refers to the fact that by the principle of superposition and linearity of quantum mechanics, it is possible to calculate in parallel the values of a function on several inputs.
For example for a Boolean function that takes as input a string of n bits, we can calculate at once the results on a superposition of the 2^n possible inputs unlike in the classic case where we can’t do this calcul at the same time, we therefore have a potential gain.
Quantically, a quantum circuit (figure below) that calculates a function can be represented by a unit transformation U which takes in |x⟩ and an ancillary qubit.
Quantum Gates
1) Single-Qubit Gates :
Quantum NOT Gate :
The classical NOT gate changes the state of a bit from the state 0 to 1 and vice versa, the quantum gate does something similar, but in terms of the amplitudes of the base states of qubit computation. It assigns the probability amplitude from state |0〉 to state |1〉, and vice versa. The NOT quantum gate works as an X operator, as shown here :
Hadamard Gate :
The Hadamard gate acts on a qubit in the state |0⟩ and takes it to the equal superposition state of :
It also transforms the state |1⟩ to the state :
The unitary matrix corresponding to the Hadamard Gate is as follows :
In terms of the Bloch sphere representation, the Hadamard gate takes the state |0⟩ aligned along the z-axis to the state :
and this state-aligned along the positive x-axis (see the figure below ).
Quantum Z Gate :
The quantum Z gate leaves the state ∣0⟩ unchanged while it changes the state ∣1⟩ to -|1⟩. The transformation of the quantum Z gate is represented as follows:
So, given any qubit state |ψ⟩ = α|0⟩ + β∣1⟩, the Z gate changes and transforms it to α|0⟩ — β∣1⟩.
2) Multiple-Qubit Gates :
When we think about 2-bit classical gates, we think about the AND, XOR, NAND, and NOR gates. In fact, the NAND gate in the classical computing paradigm is called the universal gate since any other bit gate can be constructed by combining NAND gates.
One of the two-qubit gates that helped us build universal quantum gates is the NOT conditional gate, or CNOT, shown in the next section.
CNOT Gate :
The CNOT gate works on two qubits: qubit A, which is referred to as the control qubit, and qubit B, which is the target qubit, so when we apply a CNOT gate, the control qubit state remains unchanged. The target qubit state is flipped only when the control qubit is in state ∣1⟩.
The following table represents how the qubit computation basis state changes after applying the CNOT gate.
the CNOT operation on the two qubits can be represented as follows :
Controlled-U Gate :
Another multiqubit gate that deserves special mention is the U-controlled gate. Suppose we have a unit operator U which acts on a quantum system of n qubits. We can think of a controlled U-gate as a gate that applies the unitary operator U to the system of n target qubits depending on the state of a control qubit.
When the control qubit is in state ∣1⟩, the unit operator is applied on n target qubits, on the other hand, the control qubit is in state ∣0⟩ no transformation is applied to the n target qubits.
In fact, the CNOT gate is a special case of a Controlled-U gate, where the unit operator is the single qubit X gate.
The following figure represents a quantum circuit of the controlled U-gate :
Quantum circuits
The quantum circuit is a repetitive compute consisting of homogeneous quantum operations with quantum data, such as those stored in qubits.
Each horizontal line or wire represents a qubit with a left end that contains the initial data, and to the right find the final quantum data generated by the calculation of this circuit. The operations on the qubits are placed on these wires and we represent them by boxes.
Here’s an example of a Quantum circuit :
Quantum algorithms
The main goal of quantum logic is to perform calculations faster than conventional computers do.
In general, we classify the computational problems by distinguishing those which are ‘easy’, whose solution requires a time that increases in a polynomial way, and those which are ‘difficult’, for which the time increases exponentially with n (number of bits). ‘difficult’ problems become practically insolvent for n bigger enough in conventional computers.
For example, the factorial of a big number by a classical algorithm is impossible and if we estimate it theoretically it can take up to 100,000 years to complete the execution, but with a quantum computer this task is done in a few seconds and thanks to the properties of superimpositions of qubits and their entanglement, so the classically difficult problems are transformed into quantically easy problems.
In this section, we will discuss some quantum algorithms which show the advantages of quantum logic for certain types of computation.
1) Deutsch Algorithm :
Deutsch’s algorithm exploits what we have learned so far to obtain information about a global property of a function f (x). It is often difficult to know if a function is indeed constant or balanced! To answer this question, David Deutsch in 1985 provided an excellent proof of concept that in some contexts quantum computers are strictly more powerful than classical computers.
The main objective of Deutsch’s algorithm is to find the final state | ψ_3〉 by obtaining information on the global states. The algorithm achieves this by using the superposition state reached by the system thanks to the properties of quantum parallelism. The final state is calculated as follows:
The quantum circuit of the Deutsch algorithm is represented in the following figure :
To sum up, Deutsch’s algorithm gives 0 at the output if f is constant and 1 at the output if f is balanced. Therefore, the algorithm only uses a single query to determine whether f is balanced or constant.
This calculation of the global properties of a function without explicitly evaluating the values of the same function is made possible by quantum parallelism.
2) Deutsch–Jozsa Algorithm :
The 1992 Deutsch-Jozsa algorithm inspired the work of Shor and Grover, possibly the best-known quantum algorithms based on the Deutsch algorithm.
These ideas have in common that they illustrate the potential of quantum information processing to provide solutions to problems defined in purely classical terms and perceived as incapable of being effectively solved by classical information processing.
The Deutsch-Jozsa algorithm is a generalization of the Deutsch algorithm with multiple input values, which means that we generalize the input register from one qubit to n qubits, for example, if we take n=3 qubits it can be represented in the notation |x⟩, as follow :
|000⟩ , |001⟩, |010⟩, |011⟩, |100⟩, |101⟩, |110⟩, |111⟩.
And the following figure represents the Feynman path diagram of the Deutsch algorithm
We can also represent this algorithm with the following quantum circuit
3) Grover Algorithm :
Grover’s algorithm is one of the most famous algorithms in quantum computing, it was introduced by Lov Grover in 1996 for unstructured search problems, i.e. to find an item in an unstructured database. It provides quadratic acceleration in finding items in a database.
Grover’s algorithm uses superimposed qubits in a parallel universe to do the calculations.
To understand this algorithm, we will take the example of an array of N elements, where we will look for any element that we denote by “K” in this array. In a classic computer, we are going to have a complexity of O (N) in the worst case (i.e. the element we are looking for exists in the last position of the array). But with Grover’s algorithm, we solve it with a complexity of O (√N).
And we can represent the N items in computational basis states ∣x⟩ as n input qubits, we will have also an oracle function that takes each of the computational basis states |x⟩ ∈ {0, 1}^n and returns a function output f(x)=1 for the winner item (i.e. the element we’re looking for) and f(x)=0 for the other elements of the database.
In the quantum computing paradigm, we can think of this oracle function as a unitary operator that works on the computational basis state ∣x⟩, as shown here :
The computational basis state ∣k⟩ refers to the winner item and the effect of the oracle transformation on this item is as shown here :
The following figure represents the Geometrical interpretation of Grover’s algorithm, we notice that the oracle transformation inverse only the amplitude of the winner item ‘k’ (negative value for k).
And after that, we apply an equal superposition state for the n qubits, and the amplitude of |k⟩ given by the sin will increase while the amplitude of the remaining states given by ∣c⟩ will decrease.
Then we will apply the unitary transformation U_f followed by U_ψ eq in
succession iteratively allowing us to converge to the winner state ∣k⟩ by amplifying the amplitude toward it.
And the combination of the two transforms U_ψ eq*U_f represents Grover’s transform G.
Now that we see all the details of Grove’s algorithm we can put all this together in a high-level diagram (see the following figure).
4) Shor Algorithm :
Shor’s algorithm has played a fundamental role in demonstrating the power and importance of quantum computing. It can be used to factorize prime numbers, which means it can crack the encryption code on a convenient quantum computer.
Shor’s efficient factorization algorithm consists of a quantum part and a classic part. The first is a quantum solution to the so-called order-finding problem. Because this algorithm hides the seminal idea, which makes it possible to factor a large number N in O(log_2 (N))^3 steps or gates instead of the best-known classical method asymptotically requiring :
O[k * log_2 (N) ^(1 / 3) * log2 ( log2 (N))^( 2/3)] where k is a constant often taken to be 0.9. This means that the best-known algorithm for factoring prime numbers on a classical computer requires fundamentally exponential time with the size of N.
This is why Shor’s algorithm is considered important, a quantum computer running it would only take polynomial time. Since the security of the popular RSA cryptosystem is based on the difficulty of the primary factorization. Shor’s algorithm has attracted a lot of interest from the privacy and data
security communities.
The order-finding part is the only quantum part of Shor’s algorithm; the rest involves classical calculations.
The following figure shows the period finding quantum circuit to solve the integer factorization problem.
