From the X gate to Amplitude Encoding in Ten steps

Quantum MNIST

Quantum computing has a reputation for being challenging, and there are many reasons for this. But, you can get started quite simply. In this article, we are going to progress from the simplest single-qubit operation to one of the most challenging quantum algorithms in just ten (not necessarily) easy steps.

X gate

Pauli-X

The Pauli-X gate, aka X, aka NOT, is almost the simplest operation in quantum computing. You could make an argument that the ID gate is simpler, but you could also argue that the ID gate does nothing so it doesn’t count. I’ll argue that X is the simplest gate that actually does something.

In oversimplified classical computing, a small voltage is applied to a transistor. Depending on this voltage, the transistor acts like an open switch and the current does not flow through it. We say that the switch is “off” and we represent it numerically with a zero. At other voltages, the transistor acts like a closed switch and current flows through it. We say that the switch is “on” and we represent it numerically with a one. That number, zero or one, is a “bit” of information, and as a switch, we can keep adjusting the voltage to “flip” the bit from zero to one and vice versa.

The X gate is the quantum “bit flip,” but it’s not an exact analogue. A qubit has a probability of measuring zero and a probability of measuring one, and an X gate swaps those probabilities. This is normally shown as flipping |0> to |1> and vice versa, but that’s just swapping a 100% probability of measuring zero and a 0% probability of measuring one to a 0% probability of measuring zero and a 100% probability of measuring one. Those probabilities, however, can be any two numbers that add up to 100%, and they just swap.

H gate

Hadamard

The H gate (“Hadamard”) is usually the first one shown because this is your introduction to quantum superposition. After applying one to your freshly initialized qubit, the quantum state of that qubit changes from its ground state (lowest energy state) |0> to the |+> state, which gives it a 50% probability of measuring zero and a 50% probability of measuring one.

But, the Hadamard doesn’t rotate a quarter-turn around the y axis from |0> to |+>. It actually rotates a quarter-turn around the x-axis and a quarter-turn around the z-axis. Consequently, it can be used in conjunction with T gates to create somewhat arbitrary quantum states. It can also be used in conjunction with measurements to perform x basis measurements, the uses of which are beyond the scope of this article.

CX gate

CX

The CX gate, aka controlled-x, aka controlled-NOT, is usually the second one shown because this is your introduction to quantum entanglement. It does more than just entangle qubits, though, as if that wouldn’t have been enough. The right side of the target qubit, assuming your circuit is oriented horizontally from left to right, is the XOR, aka exclusive-OR, of the control and target qubits. In addition to controlled bit flips, the CX can be used in conjunction with Hadamards to control phase flips. Furthermore, you can sandwich a z rotation between two CX gates to induce phase kickback. Ultimately, all quantum computing operations get transpiled down into CX gates and just a few single-qubit operations.

U

U gate

The U gate is your “one-stop-shop” for single-qubit rotations. It takes three out-of-order parameters: theta, phi, and lambda. The rotation would be more intuitive, however, if the parameters were ordered lambda, theta, phi. The target state rotates lambda radians around the z-axis, then theta radians around the y axis, and then phi radians around the z-axis. For most rotations, the difference between lambda and phi is not obvious; they are interchangeable. However, imagine you want to rotate from |0> to |i>; lambda then theta would rotate from |0> to |+> instead. Therefore, you do want to take your greek letters into proper consideration.

CU3 gate

CU3

The CU3 gate can be thought of as the offspring of a CX gate and a U gate. The control is borrowed from the CX gate, of course, but instead of being limited to a bit flip on the target qubit, you can rotate the target qubit as if you were applying the aforementioned U gate. Apply the same logic regarding lambda, theta, and phi rotations here.

CCX gate

CCX

The CCX gate, aka Toffoli gate, aka AND gate, is important for implementing logic. After all, you can construct all logic operations out of NAND gates, which are just an AND, or CCX, followed by a NOT, or X.

More importantly, the CCX gate allows you to construct gates for more than three qubits. This is not a tutorial for the CCCCZ gate, but you would construct one out of multiple CCX gates. This means that the CCX is also important for constructing useful oracles for Grover’s Algorithm. The only limit to how large of a custom gate you can make is the number of qubits you have available.

Quantum Fourier Transform (QFT)

Quantum Fourier Transform (QFT)

The Quantum Fourier Transform (QFT) functions as a digital-to-analogue converter, while the inverse QFT functions like an analogue-to-digital converter. Think of digital as binary numbers: there are some bitstrings (eg., 101010) encoded as inputs, and at the end, we have measurements giving us bitstrings as outputs. In between, the QFT converts amplitude information into phase information, and that makes this article no longer readable.

So, instead, think about your smartphone for a moment. It’s digital, right? The operating system and the apps, everything’s bits to gigabytes, right? That’s all binary and digital. But, the power coming from the wall outlet is analogue and needs to be converted by your phone. The cellular signals are analogue and need to be converted by your phone. Furthermore, Wi-Fi is analogue and needs to be converted by your phone.

Radio is probably the easiest way to explain this. AM radio is amplitude modulation. You can visualize it as a wave with which the heights of the peaks vary. Information is encoded in those variations. FM radio, on the other hand, is frequency modulation. You can visualize it as a wave with which the distances between the peaks vary; some are closer together and some are farther apart. Information is encoded in those variations. Your radio receiver converts analogue to digital, like the inverse QFT, and the information is rendered as sound.

The QFT converts digital bits to analogue waves so that algorithms can work with wavelike data. Why would you need to do such a thing? Well, it’s used by Shor’s Factoring Algorithm; you might have heard of that one. And, the inverse is used for phase estimation, which is used for quantum chemistry, which is probably going to be the most important application of quantum computing.

Amplitude amplification construction in IBM Quantum Experience

Amplitude Amplification

Quantum computing is probabilistic. Amplitude amplification is the part of Grover’s Algorithm during which outcomes with higher probabilities have their probabilities become even higher at the expense of outcomes with lower probabilities, which see their probabilities become even lower. This creates a separation through which it’s usually easier to visualize the solutions you’re looking for.

For a visual explanation of amplitude amplification [link to Grover’s Algorithm article]

Canonical SWAP Test

SWAP Test

The canonical SWAP Test is just a Fredkin gate, aka controlled-SWAP, with a control qubit sandwiched between two Hadamards. You may see it referred to as inner products, kernel methods, and distance measures, but these are all the same thing. The simplest implementation might be to just compare two quantum states to see if they are identical, but it can do so much more.

The SWAP Test can perform clustering and classification tasks. Despite its implementation being so simple, it has been proposed to offer a quantum computational advantage for these Quantum Machine Learning (QML) tasks when working with high-dimensional data. Specifically, if you’re working with a dataset with more than 50-55 features, and if you had sufficient qubits at your disposal, you could perform a computation that might be impossible to do classically.

Amplitude Encoding

Amplitude encoding, one method

Amplitude encoding is unique in the sense that I’ve never seen a clear explanation of it. In books and papers and articles that mention it, it’s usually just referred to as “hard,” and authors then go on to explain other encoding options. To be honest, I probably can’t explain how to do it in just a few paragraphs either. With code and circuit diagrams it would take at least a dedicated chapter in a book.

So, what is it? When you measure a circuit, there are a number of possible outcomes. Each outcome has a probability of occurring. The amplitudes that result in those probabilities can encode information. And, like all things “quantum,” amplitude encoding can be done in different ways.

The QFT is probably the simplest approach, but you can’t encode a number higher than the number of bits allows. For example, the highest number you can encode in three qubits is the same as the highest number you can encode in three bits: seven. There is another method vaguely described in a paper that requires even numbers of qubits and does not seem to use every amplitude. There is also an approach to encoding polynomials. Furthermore, you can encode binary strings: zero amplitudes are zeroes and non-zero amplitudes are ones. The advantage of this last approach is that three qubits normally allow you to encode only three bits, but three qubits have eight amplitudes or eight bits. Three bits is 0 through 7, while 8 bits is 0 through 255. Three bits is less than a nibble, while eight bits is an entire byte.

Conclusions

Quantum computing starts very simply, with zeroes and ones. Not that you should, you can emulate classical circuits with quantum circuits. Even as we add complexity, we discover that we can do everything we need with just a few gates. Not that there are many standard gates anyway, but the U and CU3 can replace many of them. And then things start to get challenging.

You can obviously do a lot more with quantum computers than what’s in this article, but my goal was simply to cover a range from the simplest to arguably the most complex.

Disclaimer: This article obviously doesn’t include every possible quantum operation and algorithm. It’s just a sampling.

Image credit: all images are from or were created in IBM Quantum Experience.