Quantum logic gates
Or what if Schrodinger’s cat did math
Introduction
Yes, this article will involve quantum mechanics. And math. And some concepts in electronics.
But don’t panic. It will be quite simplified; going through the mathematical details of quantum mechanics is way beyond what fits in one article.
Instead, we will start by postulating some basic concepts in quantum mechanics, with state superposition being the critical one.
After that we will look at the abstract concept of a qubit and describe some practical physical implementations of this entity.
Then we will dive into some aspects of classic logic gates; we’ll show how any logic gate can be implemented using only NAND gates.
We will look at logic expressions and show how arithmetic operations can be implemented using logic gates and logic circuits (this is how computers do it).
Then we will put all this together to show how quantum logic gates, arranged in quantum circuits, can perform the same arithmetic operations as classic logic gates but in a fraction of the time needed by classic gates, by exploring state superposition.
Quantum mechanics in a nutshell
Quantum mechanics is a mathematical marvel.
The fact that a set of equations, postulated out of thin air, simply because they are analogue to their classical counterparts is incredible, and certainly justifies the suspicion that there’s some intertwined relationship between the macro and micro worlds. And the explanation is “well, they seem to work”.
Let’s take a look at the one-dimensional, time-independent Schrodinger equation for the energy of an electron.
V(x) is the electric potential of an electric field applied to the electron, m is the mass of the electron and ℏ is the reduced Planck constant.
The general Schrodinger equation was postulated to describe the interference pattern created by electrons passing through parallel slits, but it so happens to also describe the spacial distribution of one electron under certain conditions. Go figure.
It is postulated this way because it resembles the classic equation for an object’s mechanical energy as the sum of kinetic and potential energy. Yes, that is the explanation.
If we apply this equation to a potential well, we get this:
A potential well is a hypothetical space with zero electric potential, bound by two “walls” of infinite potential.
The boundary conditions for this equation are ψ(0) = 0 and ψ(L)= 0.
This is an ordinary second order differential equation with known general solutions of the form
with
Looks good, I have an infinite number of sinusoidal equations for each arbitrary value of E I choose. Nothing special about it.
However, when we apply the boundary conditions, we get this:
and
And because of that we only get valid solutions for certain values of E; the solutions form a discrete set — potentially infinite — of solutions, one for each discrete value of E.
This is the essence of quantum mechanics: the solutions for its equations form discrete sets; the possible values of energy E for our electron are discrete.
The electron cannot move continously from one energy level to another, the way we are used to see in our macroscopic world; it can only jump from one energy level to another. It is weird.
Each one of the energy levels the electron can be is called its energy state.
One more important thing to notice about the solutions for this equation is that they are orthogonal to each other; this means that linear combinations of the solutions are also solutions. This will be important very soon.
That’s good enough for now. Take a breath. It gets weirder.
A few more concepts
We need some vocabulary for the next sections, so better get over it now. Here are terms you need to know:
- Wave equation — the solutions for the differential equation we just resolved; don’t worry much about why it’s called that.
- Energy probability density — it’s the square of the wave function and represent the probability of finding an electron, at a certain energy level, at a certain location.
- Spin — besides having an energy level, electrons also have angular momentum(and pretty much all subatomic particles). It means that particles spin around an axis going through its center. The spin level and direction of the axis varies, but it can only be either clockwise or counterclockwise.
- Entanglement — we are not going to do the math for entanglement, the concept is enough. Two particles are entangled when changing the state of one particle changes the state of the other particle. This will become important later.
State superposition and state collapse
In the previous section we calculated all the possible energies an electron can be and the corresponding wave equations, which then we can use to calculate the probability of finding the electron at certain positions, at each energy level.
The question now is: which energy level will the electron be?
Remember when I said that linear combinations of the solutions for the differential equations are also solutions for the equation? Well, that is the essence of state superposition: the electron can be, simultaneously, at any of the energy states, with a certain probability for each state. The actual state is only known when it is measured. We cannot predict exactly which one it will be.
This is very different from classical mechanics. If you drop a ball from a tower in free fall, you can make exact predictions of its kinetic energy, its position and speed at any instant in time. You cannot do the same in quantum mechanics. In order to know the state of an electron, you have to measure it.
Yes, this is hard to swallow. Several scientists see this as just an artifact of the mathematics. One common analogy some use is flipping a card facing down.
Before you flip the card, it can be any of the 52 cards from the deck with equal probability; it doesn’t mean it is all cards simultaneously, just that we can’t predict which one it is. Once you flip the card — or measure the electron’s energy level — the states collapse into the current state.
Regardless, however, if it’s a mathematical artifact or a physical reality, the fact is that this property is key for quantum computation.
Think about it: you could have a circuit that solved a problem where, after you operate on the inputs, the outputs would be in all possible states, but in such a way that the correct answer is the state with highest probability. Then, when you read it, all states collapse into the correct answer for the inputs. That would be very cool.
If the problem is very hard to solve with regular computers, it would be even cooler, don’t you agree?
Classic logic gates and circuits
Let’s leave the quantum realm behind for a bit and give ourselves a break. Let’s talk normal logic.
Boolean algebra
Binary logical operations are those that can be performed between 2 variables that can only assume 2 values: 0 or 1.
There are 4 basic logical operations that can be performed with 2 variables: AND, OR, Exclusive OR (XOR) and Negation (NOT).
Below are the tables with the output for each operation, given the inputs:
These logical operations can be represented using Boolean algebra, with the symbols ., +, ⊕ and ￢ representing the AND, OR, XOR and NOT operations (there are other conventions but we will use these in this article).
One interesting aspect of logical operations is that you can achieve the same results of a basic operation using algebraic expressions. For example:
In fact, one can write any logical operation using only expressions with AND and NOT operations, as well as OR and NOT.
Logic gates
So, when realizing logical operations using physical circuits — called gates — , it made sense to implement a gate that executed either the Negation/AND or the Negation/OR combos and just arrange them in different circuits to get the other operations.
These devices are called NAND and NOR gates. NAND gates are preferred because they use 2 transistors in a configuration that allows for faster level transitions than NOR gates. They are represented in electronic circuits like this:
Interestingly, the transition speeds in a transistor are governed by — you guessed — quantum mechanics.
Here are some of the other gates implemented as combinations of NAND gates.
Logic gates are quite powerful; they can even be used to implement memory circuits, like a flip-flop.
Logic circuits
Combining logical gates for operations and memory, one can build quite sophisticated circuits, including ones that perform arithmetic operations.
Here is the circuit adding 2 bits with carry bit (called a full-adder) implemented using NAND gates:
This circuit gets 2 bits — A and B — plus the carry bit from the previous sum — C — and produces A plus B and the carry bit for the next sum.
Therefore, the sum of 2 numbers with N bits can be implemented as a chain of full-adders.
The more bits you have, the more circuits you need. Because the operations are executed sequentially, the larger the number of bits, the longer it takes to execute the operation.
Classic computers are built on top of these basic concepts, in a much larger scale. When we execute a program in a computer, the instructions are nothing more than bits that interact with the appropriate circuits in the processor to sequentially execute functions: transfer data to/from memory, execute an arithmetic operation, etc.
The key word here is sequentially; each step of the operation must be executed one at a time — for complex operations like multiplication and division, multiple times — , until we get the result. And this takes time. Moreover, the larger the entries, the longer it takes. So much so that some complex problems may take so much time to solve that they are , for all practical reasons, unsolvable.
Well, until now. Let’s see if Schrodinger’s cat can help us with that.
Qubits, quantum gates and quantum circuits
Qubits
Since we are talking about logic gates and binary bits and such, it’s not surprising that we’d prefer to work with something analogous to a bit in classic logic; hence, the qubit is born.
If you guessed qubit is short for quantum bit, you guessed right. So, how can we define such entity?
In classic logic, physical bits are defined as different electric voltage values; which values represent 0 and 1 are completely arbitrary, depending on the application, transistor technology, power requirements, etc.
As long as the voltages can only assume 2 possible values, it works.
So, back in the quantum realm, let’s say we want to use some property to represent 0 and 1.
You can use energy, as long as you create conditions where the particle can only assume 2 possible states.
If you decide to go with photons and light, photon polarization works.
Back to electrons, they have a property called spin. For the electron spin is either -1/2 or +1/2.
So here is one way to define the possible values of a qubit: 0 if the electron has spin +1/2, 1 otherwise. Or vice-versa.
What’s the main advantage of qubits?
Qubits are the key for quantum computers. Quantum computers — we hope — will be able to resolve problems that are so large that cannot be solved by classic computers.
Here is one simple example: suppose you want to store all the numbers with 300 bits. Doesn’t sound hard. All you need is 2³⁰⁰ memory locations with 300 bits each. What’s the problem?
The problem is that this number is higher than the number of atoms in the Universe. It is impossible to accomplish this task with classic computers.
With qubits, however, you only need 300 to accomplish it. Because each qubit can be — at the same time, due to state superposition — at 0 and 1 state, the 300 qubits represent — simultaneously — all possible 2³⁰⁰ numbers.
This concept also hints to the possibility of executing the complex operations of a difficult problem in parallel, as opposed to using classic computers — as we’ve seen when we looked at classic logic circuits — where some operations are necessarily sequential.
Quantum gates
Before we start looking at the various types of quantum gates, one thing must be clear: while classic logic gates can be built with transistors as small as 10 nanometers, quantum gates are complicated machines themselves.
Some involve lasers, special mirrors, polarizers and other optical devices, others deal with electrons cooled down to almost 0⁰ K, requiring sophisticated sensors and actuators to interact and read electron states. Here is just a glimpse of IBM’s 53 qubits quantum computer.
It is, of course, possible to simulate these devices using classic computers; quantum gates do follow quantum mechanics equations and their behavior can be calculated. These simulations can be used to determine if a physical quantum computer would behave as expected, but without the actual time gains expected from them.
It is also possible to design circuits that perform specialized operations, analogous to what is done using classic logic gates.
Similarly to logic gates, it can be proven that we only need a handful of quantum gates to implement any quantum circuit.
Let’s take a look at them.
Hadamard gate
The Hadamard gate acts on one qubit and it is used to “initialize” the qubit. In other words, it puts one qubit in a superposition state where 0 and 1 — however they are defined — have the same probability of being measured.
Again, the physical realization of such gate depends on the particle being used: photons will use lasers and optical devices; electrons can use spin and magnetic or electric fields, etc.
Pauli or rotation gates
Like the Hadamard gate, the Pauli gets act on 1 qubit. It rotates the qubit 180⁰ around a certain axis — X, Y or Z — , effectively flipping the state.
For example, if it’s an electron spinning clockwise around the Z axis, flipping it around the X axis turns the spin counterclockwise.
You can think of the Pauli gates as the quantum equivalent of the NOT logic operation.
C-NOT gate
The C-NOT (Controlled-NOT) gate is different from the previous ones because it acts on 2 qubits, instead of one. It takes advantage of entanglement to force the state of a qubit — the target qubit — by changing the state of another qubit — the control qubit.
It is the analogous to the XOR gate in classic logic.
There are several other types of gates — the same way that there are several different types of classic gates — but with these 3 we can construct any quantum circuit.
Quantum circuit
By now the idea of a quantum circuit should be getting clear. A quantum circuit in a quantum computer is machinery that allows one to apply a sequence of gates to a qubit.
Quantum circuits can be statically built to execute one specific operation or could — at least theoretically — be built in such a way that a program could tell the computer which gate to apply next.
One can imagine writing an app in some programming language, which runs in a classic computer but has an interface to a quantum computer.
The program would take advantage of APIs and libraries designed to send data to the quantum computer, request certain operations to be executed and get the results back.
It could look something like this:
void processInput(int data) {//do some classic stuff then: initQubits(data);
applyHadamard();
for (int i = 0; i < 3; i++) {
applyPauli(i); }
...}
And these functions would be designed to request the quantum computer to interact with the qubits, however the hardware is built to do.
One example of such algorithm is Shor’s algorithm for integer factorization, which executes in polynomial time.
Each element in this circuit can be built using Hadamard and CNOT gates, including the inverse quantum Fourier transform at the end.
Conclusion
This is obviously not an easy topic to grasp, the math is complicated and it’s all very abstract at this point, but it is looking more and more likely this will be an integral part of our future. Just a couple examples:
- IBM Quantum Experience allows researchers and developers to build quantum circuits using a graphic interface and execute them in real systems.
- IBM now has 18 quantum computers being used in research.
- Google claimed quantum supremacy on October 2019.
So hopefully this article helps shed a little light on the concepts behind quantum gates, quantum circuits and quantum computers.