The current hard limits on computational power would be shattered by the realization of a large-scale, coherent quantum computer. Quantum algorithms such as Shor’s and Grover’s are able to crack RSA encryption or search an unsorted array in O($\sqrt{N}$) time. While this field may appear difficult and unintuitive (which, at times, it most certainly is), gaining a surface level understanding of the conventions and fundamentals requires only reading this article! Similar to studying standard computing, abstractions are key. By abstracting away the mathematics, physics, and implementation of quantum circuits (analogous to the transistor level), quantum circuits become a new and accessible tool to analyze and develop quantum algorithms.

While quantum mechanics is a major field of study in physics, only a small portion is necessary to understand quantum circuits. Quantum computing is, at its core, simply computers with qubits. A regular bit may take the values of 0 or 1 only, whereas a qubit may take a superposition of |0> and |1>. All this means is that the bit may be in both states with some probability. Qubits can be represented via numerous means, but the actual implementation is unimportant for the layer of abstraction we are concerned with.

A brief aside on notation: |0> and |1> are called “kets”. There are also “bras”, denoted <0| and <1|. Together this comprises “bra-ket notation” (also called Dirac notation). In quantum mechanics, kets denote wavefunctions in a general Hilbert space. For quantum computing, they may be considered as two dimensional vectors.

$$|0> = \begin{pmatrix} 1 \\ 0 \end{pmatrix}\text{, and}$$ $$|1> = \begin{pmatrix} 0 \\ 1 \end{pmatrix}\text{.}$$

These are the two basis states that comprise a qubit. A general qubit may be in a superposition of these two basis states, so it may be denoted as

$$|\psi> = \alpha|0> \text{+ $\beta$|1>, or}$$ $$|\psi> = \begin{pmatrix} \alpha \\ \beta \end{pmatrix}.$$

Recall that a ket (wavefunction) is related to the probability of a qubit being in a state. In general, $\alpha$ and $\beta$ are complex numbers. The probability is given by the magnitude squared of the coefficients of each basis state. Since probabilities must sum to 1, then $|\alpha|^2 + |\beta|^2 = 1$. This is called normalizing the wavefunction. After all, if there is a 50% chance to find the qubit in state |0>, then there must be a 50% chance to find the state in |1>.

A great visualization tool for qubits is the Bloch sphere. You can think of a qubit as a vector on a sphere, of constant radius 1 (this comes from the normalization requirement). The |1> state points in the +z direction (straight up), and the |0> state points in the -z direction (straight down). Another important region is the equator, which is an equal superposition of |0> and |1>. The different directions the state may point in is simply a difference in relative phase between $\alpha$ and $\beta$. Since the probabilities are unaffected by a phase (they are related to the magnitudes of $\alpha$ and $\beta$), the entire equator is the equal superposition. In the next section, we will cover quantum gates. These are operators, which can be envisioned as rotations on the Bloch sphere. They simply move a qubit from one state to another.

Measurement is the final step in a quantum circuit. When measuring a qubit, there is a $|\alpha|^2$ chance that |0> will be measured, and a $|\beta|^2$ chance that |1> will be measured. While there is some debate, the majority of leading physicists believe that this measurement is truly random. Once a state is measured, it collapses into the resulting basis state. That is, if a 1 is measured, then the state must be in |1> immediately after measurement.

Quantum circuit diagrams may appear intimidating at first, but they are an incredible tool for visualizing quantum circuits. Here is an example diagram (we will break down the components, so don't try to grasp it all immediately):

A circuit for a full program is more complex; even just 4 bits may seem overwhelming:

In quantum circuit diagrams, time is the x axis, and moves from left to right. Quantum circuits have 3 components: initialization, quantum gates, and measurement. So, initialization involves the left inputs, and measurement occurs at the right outputs. Only experimentalists are concerned with the initialization, but in brief, an ensemble (i.e. MANY copies of identical initial qubits) must be prepared, and the quantum circuit run MANY times in succession to determine the statistical averages of the system. Measurement occurs as the very final step in a quantum circuit, as it destroys the qubits (destroys is not to be taken literally, it just collapses the state in 0 and 1 qubits, but the previous states are completely lost).

Quantum gates are the core building blocks of quantum circuits. They are analogous to typical logic gates, such as AND and OR. Mathematically, quantum gates are transformation matrices. For a 1-qubit system, they are 2x2 (complex) matrices. Technically, any 2x2 matrix transformation could be modelled as a quantum gates. The only requirement is that they are unitary.

As a brief aside, the Hermitian conjugate of a matrix is the transposed complex conjugate of a matrix. A unitary matrix is defined such that its inverse is equal to its Hermitian conjugate (denoted by $\dagger$). Unitary matrices represent length-preserving transformtaions. This boils down to the conservation of probability. Since the magnitude squared of wavefunctions are akin to probability distributions, transformations on wavefunctions in the real world must preserve length.

Let U be a unitary matrix. Then:

$$U \equiv \begin{pmatrix} a & b \\ c & d \end{pmatrix}$$ $$\\ U^{-1} = U^{\dagger} = \begin{pmatrix} a^* & c^*\\ b^* & d^* \end{pmatrix}$$

While an arbitrary transformation is a possible quantum gate, those used in practice are limited to a handfull. These gates include H (Hadamard gate), and the X, Y, and Z gates (the Pauli matrices, and are related to the spin of a particle in the corresponding directions). They are defined as follows:

$$H \equiv \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$$ $$X \equiv \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$$ $$Y \equiv \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}$$ $$Z \equiv \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}$$

Of course, all of these matrices are unitary - you can check yourself. The X gate is commonly called the NOT gate. It inverts between the basis states, similar to a traditional NOT gate. That is, X|0> = |1>, and X|1> = |0>. The Hadamard gate is useful for "mixing" the basis states into a superposition. This is made clear by its action on the basis states:

$$H|0> = \frac{1}{\sqrt{2}}(|0> \text{+ |1>}) \equiv |+>$$ $$H|1> = \frac{1}{\sqrt{2}}(|0> \text{- |1>}) \equiv |->$$

Recall that the probability of finding the system in a basis state is the magnitude squared of the coefficients of the basis states. So, a system in either |+> or |-> has a 50/50 chance of being found in either |0> or |1> when measured.

These four gates are the most commonly used single-qubit gates. Any transformation is possible using only these gates in some combination, similar to how the traditional OR gate can be built from only NAND gates. In the example circuits above, notice the H, X, and Z gates in action. The final gate to discuss is the CNOT gate. This brings us to multi-qubit systems.

Besides a true random coin flip simulation, not much is possible with only one qubit. Most of the extension to multiple qubit systems is expected. A 2-qubit system, for instance, is represented by a vector of length 4. The basis states are |00>, |01>, |10>, and |11>. The first number corresponds to the first qubit, and the second number to the second qubit. So, measuring the |00> state means both particles were found in the |0> state. For instance,

$$|00\text{>} = \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix}$$

Transformations in higher qubit systems act on the system as a whole, and require tensor products between the gates, which falls well outside the scope of this article. Still, we can examine quantum circuits from a higher level point of view. While transformations act on the system as a whole (a 4x4 matrix), single qubit gates still behave similarly to the single qubit system.

For instance, applying a Hadamard gate to the first qubit reslts in the |+> state for the first qubit, and the second qubit is still in the |0> state.

Now that we have multiple qubits, we want to interact between them. The CNOT gate is the most common multiqubit gate. CNOT means controlled NOT - you can think of it as conditionally inverting a qubit, based on the value of a controller qubit. If the controller is in |1>, then the target is transformed as follows:

$$\alpha|0\text{>} + \beta|1\text{>} \rightarrow \beta|0\text{>} + \alpha|1\text{>}$$

On the four basis states, the CNOT gate is easy to follow.

CNOT|00> = |00>      CNOT|01> = |01>      CNOT|10> = |11>      CNOT|11> = |10>

In a quantum circuit diagram, the CNOT gate has a special notation. The controller qubit is the solid circle, and the target qubit is the open circuit. Now, you are able to decipher both of the above examples. Recall, the first example quantum circuit diagram:

This applies a Hadamard gate to the first qubit, then a CNOT gate where the first qubit is the controller and the second qubit is the target. Lets refer to the first qubit as Alice, and the second as Bob (a fun aside, these names are quite common for cryptography and physics examples). So, at $|\psi_1\text{&gt;}$, Alice is in |+> and Bob remains in |0>. This means that Alice is in an equal superposition of |0> and |1>. At the CNOT gate, the easiest way to understand is to break the situation down into the 2 possibilities. If Alice is in |0>, then Bob will not invert $\rightarrow$ both are in |0>, so the system is in |00>. If Alice is in |1>, then Bob will invert $\rightarrow$ both are in |1>, so the system is in |11>. Since Alice was equally in |0> and |1>, it stands to reason that both possibilities are equally likely; that is, the system is now in a superposition of |00> and |11>.

$$|\psi_2\text{>} = \frac{1}{\sqrt{2}}|00\text{>} + \frac{1}{\sqrt{2}}|11\text{>}$$

So, this circuit entangles the two qubits! If we were to measure Alice, and find she is in |0>, then we know the \textit{whole system} is in state |00> $\rightarrow$ Bob is also in |0>. Similarly, if Alice is measured to be in |1>, then Bob must also be in |1>. More generally, this state is the first Bell state. The Bell states are outside the scope of this article, but are quite useful in various quantum circuits.

Quantum computers promise to solve complex problems beyond classical capabilities but face significant challenges. Qubits, the fundamental units of quantum information, are highly susceptible to errors from decoherence and other noise. Quantum error correction (QEC) is crucial for reliable and scalable quantum computing. This section explores QEC principles and methods, highlighting their importance in quantum computing development.

Quantum error correction involves encoding quantum information to detect and correct errors without measuring qubits directly, which would collapse their quantum states. Unlike classical error correction, which handles bit flips (0 to 1 or vice versa), QEC addresses more complex errors, including phase flips and combinations of both.

The Shor code encodes one logical qubit into nine physical qubits and can correct both bit flip and phase flip errors. The encoding process can be represented as:

$$ |\psi\rangle_L = \alpha|0\rangle_L + \beta|1\rangle_L $$

where $|\psi\rangle_L$ is the logical qubit state encoded in nine physical qubits.

The Steane code uses seven qubits to encode one logical qubit and correct arbitrary single-qubit errors. It is based on the classical Hamming code and provides an efficient error correction scheme.

$$ |\psi\rangle_L = \alpha|0\rangle_L + \beta|1\rangle_L $$

where the logical qubit is encoded in a way that any single qubit error can be detected and corrected.

Surface codes are topological codes that arrange qubits on a 2D lattice. They are particularly promising for scalability because they require fewer physical qubits and are robust against local errors.

To implement QEC, one must follow these general steps:

1. Encoding: The logical qubit is encoded into a larger system of physical qubits. This process spreads the quantum information across multiple qubits, creating redundancy that can be used to detect and correct errors.

2. Syndrome Measurement: Special quantum gates, known as syndrome measurements, detect the presence of errors without collapsing the quantum state. These measurements extract information about the error without revealing the encoded information.

3. Error Correction: Based on the syndrome measurement results, specific quantum operations are applied to correct the errors. These operations restore the logical qubit to its intended state.

4. Decoding: Finally, the logical qubit can be decoded back into a single qubit if needed.

While QEC provides a theoretical foundation for building fault-tolerant quantum computers, practical implementation faces several challenges. The physical qubits must have sufficiently low error rates for QEC to be effective, necessitating advances in qubit technology. Additionally, QEC requires significant overhead in terms of the number of physical qubits needed to encode a single logical qubit, making it essential to reduce this overhead through ongoing research. Implementing QEC algorithms also demands precise control and manipulation of multiple qubits, which is technologically demanding. Despite these challenges, ongoing research and development in QEC are crucial for the future of quantum computing. Improved error correction methods, better qubit designs, and advanced quantum algorithms will contribute to the realization of practical and powerful quantum computers.

Now, useful algorithms involve more than two qubits. So, analyzing \textit{how} this algorithms work exactly is outside the scope of this article. We can still gain much insight from a higher level analysis. Grover's alogorithm can search an unsorted array of elements in O($\sqrt{N}$) time. There is a great geometrical view of this problem available at [1]. The algorithm initializes the system in a superposition of all basis states, where each basis state represents a single element in the array. After 2 reflections, the system points closer to the desired state. After about $\sqrt{N}$ reflections, the state maximally points towards the desired state (element).

While the above information is not technically incorrect, it is important to see the whole picture. In practice, there are many factors working against it. Namely, the overhead required for a substantially large quantum computer would likely far outweight the quadratic speedup it accomplishes over traditional computing. Additionally, maintaining the coherence of the system would be an insurmountable hurdle for modern quantum computers for any sizeable input. Still, Grover's algorithms represents a wider concept: quantum algorithms open the possibility of improvements to time complexity otherwise impossible with standard computing.

If you have heard articles claiming quantum computing will "break the internet", it is likely related to Shor's algorithm. This algorithm computes the prime factorization of an integer, in polynomial time (specifically, O((logN)^2(loglogN))). The best known algorithm for this computation on classical computers is of sub-exponential time. This means that Shor's alogirthm, if implemented on a sufficiently large and stable quantum computer, would see an exponential decrease in the time to factorize integers. In the world of cryptography, this would shatter the RSA encryption scheme, which relys on the exponential time complexity of prime factorization to transmit large integers in a public-private key arrangment. So, it is true that such a quantum computer would shatter the internet, but such a machine lies in the distant future. Modern quantum computers boast neither the size nor the coherence to factorize even relatively small integers, let alone the massive integers involved in modern telecommunications.

While quantum computing is a complex and rich, yet nascent field of study, learning the basics is straightforward. A focus on abstraction is vital for any progress in computer science to be made, and quantum computing is certainly no exception. The field is research focused, with opportunities in industry at tech companies such as Google and IBM. However, it faces difficulties which has led to a pessimistic outlook by many. Maintaining coherent states becomes exponentially more challenging with higher qubit systems, and the technology required is only available in cutting edge research labs. However, this is akin to the beginnings of computers - massive, bulky machines which have seen unimaginable reductions in size and improvements in capabilities. Thus, quantum computing maintains a hope to crush the current restrictions on common algorithms, and may find its way as a niche substitute for specific algorithms that could be exploited to launch humanity's technological capability forwards.

https://quantum.country/qcvc#part-I

https://akyrillidis.github.io/notes/quant_post_7

https://quantumcomputing.stackexchange.com/questions/1440/what-would-a-very-simple-quantum-program-look-like

https://iopscience.iop.org/article/10.1088/0034-4885/76/7/076001

https://www2.physics.ox.ac.uk/sites/default/files/ErrorCorrectionSteane06.pdf