Logic gates are the building blocks of digital circuits. The basic logic gates include AND, OR, NOT, NAND, NOR, XOR, and XNOR. They can be implemented in digital hardware using transistors and/or diodes. In a few applications, they are implemented using electromechanical relays, fluidics, pneumatics, or optical elements. A series of logic gates can be used to implement complex Boolean functions.
This FAQ begins with a review of the seven basic logic gate types, reviews the concepts of the compound and universal gates, and closes with a brief look at quantum gates that will provide the basis for future generations of quantum computers.
The seven basic logic gates are:
- AND produces a 0 output unless both the X and Y inputs are both 1, when the output is 1.
- NAND is the negation of AND, it produces a 1 output unless both the X and Y inputs are both 1, when the output is 0.
- OR produces a 0 output only when both the X and Y inputs are 0, otherwise the output is 1.
- NOR is the negation of OR and produces a 1 output when both inputs are 0, otherwise the output is 0.
- XOR is an exclusive OR and outputs 1 if there is only a single 1 input between X and Y, inputs of two 0s or two 1s produce an output of 0.
- XNOR is the inverse of XOR and inputs of two 0s and two 1s will produce an output of 1, it produces an output of 0 if there is a single 1 input between X and Y.
- NOT is also called an inverter; if the input is 1, the output is 0, and if the input is a 0 the output is 1.
The most common symbols for logic gates in the U.S. are from the American National Standards Institute (ANSI). The same symbols are called the Mil-standard symbols since they are also recognized by the U.S. Department of Defense (Figure 1). A circle on a symbol is called a bubble and indicates a logic negation between external and internal logic states (1 to 0, or vice versa). Variations of these symbols have been developed by the National Electrical Manufacturers Association (NEMA), the International Electrotechnical Commission (IEC), and other standards bodies.
These basic logic gates are used to build logic circuits, including multiplexers, arithmetic logic units (ALUs), registers, computer memories, and other structures (Figure 2). While logic gates can be made using various devices and structures, MOSFET-based gates are the most common type found in digital electronic devices. In addition, compound logic gates such as AND-OR-Invert (AOI) and OR-AND-Invert (OAI) are often employed in actual circuit designs since they tend to be simpler to use in complex structures and are more energy efficient compared with an equivalent function implemented with simple logic gates.
Universal gates
NAND and NOR gates are called universal gates since they can be used to implement any Boolean function using any other type of gate (Figure 3). Both NAND and NOR gates are the basic gates used in all digital logic integrated circuits. In practical designs, an AND gate is generally fabricated as a NAND gate followed by an inverter, and an OR gate is fabricated as a NOR gate followed by an inverter.
Quantum gates
Quantum gates operate on quantum bits (qubits) that can simultaneously exist in two states, unlike classical bits that are either a ‘1’ or a ‘0’. The two basic qubit states can be expressed as |0⟩ and |1⟩ in Dirac notation. |0⟩ is the quantum state that will always give the result 0 when converted to classical logic by a measurement, and |1⟩ will always convert to 1: However, a qubit can also exist as a linear combination of both states.
There are numerous ways to implement quantum gates, but all quantum gates leverage the concepts of superposition and entanglement that do not exist for classical gates. In addition, quantum gates (as well as some types of classical gates) are reversible. Reversibility means that, in theory, quantum gates never lose information. Pauli gates and Hadamard gates are examples of two types of logic gates used in quantum computing.
The Pauli gates are based on Pauli spin matrices and are similar to classic logic gates. Pauli spin matrices are useful for calculating changes to the spin of a single electron. Electron spin is a common property to form a qubit in today’s quantum gates. There is one Pauli gate/matrix for each axis in space (X, Y, and Z).
A Hadamard gate, or H-gate, is a strictly quantum structure that does not map into classic logic gates. An H-gate can be used to transform a defined quantum state, such as spin-down, into a complex quantum state, such as a superposition of both spin-up and spin-down at the same time. For example, if a spin-up or spin-down electron passes through an H-gate, it’s transformed into a more complex structure that combines spin-up and spin-down. An H-gate is sometimes used as the first computation in a quantum program because it transforms pre-set, or initialized, qubits back into their natural complex state to leverage the full capabilities of quantum computing.
For more information on quantum computing, see; “What are the basics of quantum computing?”
Summary
Logic gates form the basis of modern digital computing and are used to implement complex logic circuits such as multiplexers, arithmetic logic units (ALUs), registers, and computer memories. Many digital ICs are composed mostly of NAND and NOR gates called universal gates and can be used to implement any Boolean function using any other type of gate. To develop practical quantum computers, new logic gate approaches, and structures will be needed to handle the concepts of superposition and entanglement that do not exist for classical gates.
References
Demystifying Quantum Gates, Towards Data Science
Logic gate, Wikipedia
Logic gates, Digilent
Multiplexer, Wikipedia
Universal gates, University of Peshawar
VHDL Tutorial – 7 NAND gate as universal gate using VHDL, Engineers Garage
VHDL Tutorial – 8: NOR gate as a universal gate, Engineers Garage
