Strangely Different

Conventional digital logic has plenty of well-optimized approaches for performing arithmetical operations—why can’t we just replace bits with qubits and use those in our QPU?

The problem, of course, is that conventional operations are expected to operate on a single set of inputs at a time, whereas we will often have input registers that are in superposition, for which we want quantum arithmetic operations to affect all values in the superposition.

Let’s start with a simple example demonstrating how we want logic to work on a superposition. Suppose we have three single-qubit QPU registers, a, b, and c, and we want to implement the following logic: if (a and b) then invert c. So if a is ∣1⟩ and b is ∣1⟩, then the value of c will be flipped. We saw in Figure 3-20 that we can implement this logic directly with a single Toffoli operation. Visualizing this in circle notation, the Toffoli operation swaps the ∣3⟩ and ∣7⟩ values, regardless of what’s in them. If b is ∣0⟩ and a is ∣1⟩, as in Figure 5-1, the exchanged circles are both empty, so the gate has no effect on c.

Figure 5-1. When b=0, this operation has no effect

Now suppose that we use a HAD operation (introduced in Chapter 2) to prepare b in a superposition of ∣0⟩ and ∣1⟩—what do we want c to do? Properly implemented, this operation should both invert and not invert c in superposition, as in Figure 5-2. Toffoli gates also exist for conventional computation, but they certainly couldn’t pull off this trick. We need a definitively quantum implementation of the Toffoli gate acting on quantum registers to make this work. The circle notation in Figure 5-2 helps us see what a properly quantum Toffoli gate should do to our superposition input.

Figure 5-2. A single gate performs two operations at the same time

There are also a few other requirements we will have of operations in order for them to be able to properly operate on qubits within a QPU. Although some of these might not be as obviously necessary as our preceding example, they are worth bearing in mind as we construct a variety of arithmetic and logical operations for QPUs:

Moving and copying data

As we have already learned, qubits cannot be copied. This is a huge difference between quantum and conventional logic. Moving or copying bits is the most common operation a conventional CPU performs. A QPU can move qubits using exchange instructions to swap them with other qubits, but no QPU will ever implement a COPY instruction. As a result, the = operator, so common for manipulating digital values, cannot be used to assign one qubit-based value to another.

Reversibility and data loss

Unlike many conventional logic operations, our basic non-READ QPU operations are reversible (due to details of the laws of quantum mechanics). This imposes significant constraints on the logic and arithmetic we can perform with a QPU, and often drives us to think creatively when trying to reproduce conventional arithmetic operations. READ is the only irreversible operation, and you might be tempted to make heavy use of it to build nonreversible operations. Beware! This will make your computation so conventional that it will most likely rob you of any quantum advantage. The simplest way of implementing any conventional circuit in our QPU is to replace it with an equivalent conventional circuit only using reversible operations, such as Toffoli. We can then implement it virtually as is on a quantum register.²

Arithmetic on a QPU

In conventional programming, we rarely use individual logic gates to write programs. Instead, we trust the compiler and CPU to convert our program into the gates needed to perform our desired operations.

Quantum computation is no different. In order to write serious QPU software, we primarily need to learn how to work with qubytes and quantum integers rather than qubits. In this section we’ll lay out the intricacies of performing arithmetical operations on a QPU. Just as classical digital logic can be built up from NAND gates (a single gate which performs NOT(b AND b)), the quantum integer operations we need can be built from the elementary QPU operations we covered in Chapters 2 and 3.

For simplicity, we will diagram and demonstrate the arithmetic operations that follow using four-qubit integers (quantum nibbles, or qunibbles, for those who remember the early microcomputer days). However, all of these examples can be extended to larger QPU registers. The size of integers that our arithmetic can handle will depend on the number of qubits available in our QPU or simulator.

Hands-on: Building Increment and Decrement Operators

Two of the simplest useful integer arithmetic operations we can perform are those for incrementing and decrementing a number. Try running Example 5-1, and stepping through the gates one by one to observe the operation shown in Figure 5-3.

Figure 5-3. Operations performing increment-by-1 and decrement-by-1

Note

The prepare step and initialization value in Figure 5-3 are not part of the actual increment operation, but chosen simply to provide a nonzero input state, so that we can follow the action of operations.

In Example 5-1, we’ve implemented the increment and decrement operations using an argument of 1 in the QCEngine add() and subtract() functions.

These implementations satisfy all the requirements we have for them being truly quantum—in particular:

Reversibility

First, and most obviously, the decrement operation is simply the increment with its constituent operations reversed. This makes sense, but may not be obvious if you’re used to conventional logic. In conventional logic devices gates tend to have dedicated inputs and outputs, and simply running a device in reverse is likely to damage it, or at least fail to provide a useful result. As we’ve noted, for quantum operations reversibility is a critical requirement.

Superposition operation

Crucially, this implementation of increment also works on inputs in superposition. In Example 5-1, the preparation instructions write the value ∣1⟩ to a quantum integer and then call HAD and PHASE(45) on the 0x4 qubit, resulting in our register containing a superposition³ of ∣1⟩ and ∣5⟩, as shown in Figure 5-4.

Figure 5-4. The prepared superposition, before incrementing

Now let’s try running the increment operation on this input. Doing so transforms the state into a superposition of ∣2⟩ and ∣6⟩, where the phase of each value matches its pre-increment counterpart. This is shown in Figure 5-5.

Figure 5-5. The resulting superposition, after incrementing

Tip

How does incrementing work? Looking carefully at the operations involved, we can see that it starts by using a three-condition CNOT gate to apply “if all of the lower bits in the integer are 1, then flip the top bit.” This is essentially the same as a conventional arithmetic carry operation. We then repeat the process for each bit in the integer, resulting in a complete “add and carry” operation on all qubits, performed using only multicondition CNOT gates.

We can go beyond simple incrementing and decrementing. Try changing the integer values passed to add() and subtract() in Example 5-1. Any integer will work, though different choices result in different configurations of QPU operations. For example, add(12) produces the circuit in Figure 5-6.

Figure 5-6. A program to add 12 to a quantum integer

In this case, Figure 5-7 shows that the input values ∣1⟩ and ∣5⟩ will become ∣13⟩ and ∣1⟩, since this program will wrap on overflow (just like conventional integer math).

Figure 5-7. add(12) applied to a superposition of 1 and 5 states

The fact that these functions will take any integer brings up an interesting point: this program is performing arithmetic on a conventional digital and a quantum value. We’re always adding a fixed integer to a quantum register, and have to change the set of gates used to be specific to the particular integer we want to add. What about going a step further—can we perform addition between two quantum values?

Adding Two Quantum Integers

Suppose we have two QPU registers a and b (bearing in mind that each of these could potentially store a superposition of integer values), and we ask for a simple + operation that would store the result of their addition in a new register c. This is analogous to how a CPU performs addition with conventional digital registers. However, there’s a problem—this approach violates both the reversibility and the no-copying restrictions on QPU logic:

• Reversibility is violated by c = a + b because the prior contents of c are lost.

• No copying is violated because we could be sneaky and perform b = c – a to ultimately end up with two copies of whatever superposition might have been in a.

To get around this, we will instead implement the += operator, adding one number directly onto another. The code sample in Example 5-2, shown in Figure 5-8, adds two quantum integers together in a reversible manner, whatever superposition they happen to be in. Unlike the previous approach for adding a conventional digital integer to a quantum register, here the gates don’t need to be reconfigured every time the input values change.

Figure 5-8. Operations assembled to perform a += operation

As was the case in Example 5-1, the prepare step in Figure 5-8 is just there to provide test input, and is not part of the operation. Also, we can implement a -= b by simply running the a += b gates in reverse order.

Negative Integers

So far we’ve dealt only with adding and subtracting positive integers. How can we represent and manipulate negative integers in a QPU register? Fortunately, we can employ a two’s-complement binary representation, as used by all modern CPUs and programming languages. We provide a quick review of two’s complement here, with qubits specifically in mind.

For a given number of bits, we simply associate half the values with negative numbers, and half with positive numbers. For example, a three-bit register allows us to represent the integers –4, –3, –2, –1, 0, +1, +2, and +3 as shown in Table 5-1.

If you’ve never encountered two’s complement before, the association between negative and binary values may seem a bit haphazard, but this particular choice has the surprising benefit that methods for performing elementary arithmetic developed for positive integers will also work out of the box with the two’s-complement representations. We can also see from Table 5-1 that the highest-order bit conveniently functions as an indicator of an integer’s sign.

A two’s-complement encoding works just as well for a register of qubits as it does for a register of bits. Thus, all of the examples in this chapter work equally well with negative values represented using two’s complement. We must, of course, be diligent in keeping track of whether or not we’re encoding data in QPU registers with two’s complement, so that we interpret their binary values correctly.

To negate a number in two’s complement, we simply flip all of the bits, and then add 1.⁴ The quantum operations for performing this are shown in Figure 5-9, which bears a very strong resemblance to the increment operator presented back in Figure 5-3.

Figure 5-9. Two’s complement negation: flip all bits and add 1

Hands-on: More Complicated Math

Not all arithmetic operations will readily lend themselves to the requirements we demand for QPU operations, such as reversibility and no copying. For example, multiplication is hard to perform reversibly. The code in Example 5-3, shown in Figure 5-10, illustrates a related operation that can be constructed to be reversible. Specifically, we square one value and add the result to another.

Figure 5-10. Add the square of b to a

Performing a += b * b as in Figure 5-10 will add the squared value of b to a.

Reversibility is an especially interesting consideration for this example. If we try to naively implement b = b * b, we’ll quickly discover that there’s no suitable combination of reversible operations, as we always end up losing the sign bit. Implementing a += b * b, however, is fine, as reversing it simply gives us a –= b * b.

Getting Really Quantum

Now that we’re equipped with quantum versions of arithmetic circuits, there are other entirely new tricks we can play.

Quantum-Conditional Execution

On a conventional computer, conditional execution causes logic to be performed if a value is set. During execution, the CPU will read the value and decide whether to execute the logic. With a QPU, a value can be both set and not set in superposition, so an operation conditional on that value will both execute and not execute in superposition. We can use this idea at a higher level, and conditionally execute large pieces of digital logic in superposition.

For example, consider the program in Example 5-4, shown in Figure 5-11, which increments a register of three qubits labeled b—but only if another three-qubit register, a, holds an integer value in a certain range. By initializing a in a superposition of ∣1⟩ and ∣5⟩, b ends up in a superposition of being both incremented and not incremented.

Figure 5-11. Conditional execution

Note that for some values of a, subtracting 3 from a will cause its lowest-weight qubit to be set. We can use this top bit as a condition for our increment operation. After incrementing b conditional on that qubit’s value we need to add 3 back to a, in order to restore it to its original state.

Running Example 5-4, circle notation reveals that only parts of the quantum state where a is less than 3 or greater than 6 are incremented.

Only circles in columns 0, 1, 2, and 7 in Figure 5-12 are affected by the incrementing logic.

Figure 5-12. Conditional addition

Phase-Encoded Results

Our QPU versions of arithmetic operations can also be modified to encode the output of a calculation in the relative phases of the original input qubit register—something completely impossible using conventional bits. Encoding calculation results in a register’s relative phases is a crucial skill for programming a QPU, and can help us produce answers able to survive READ operations.

Example 5-5, shown in Figure 5-13, modifies Example 5-4 to flip the phase in an input register if a is less than 3 and b is equal to 1.

Figure 5-13. Phase-encoding the result

When this operation is complete, the magnitudes of the register are unchanged. The probabilities of READing each value remain just as they were, unable to show that this operation was ever performed. However, Figure 5-14 shows that we have used the phases in our input register to “mark” specific states in the superposition as a result of a calculation. We can see this effect most readily in circle notation.

Figure 5-14. The effect of phase encoding

We’ll make heavy use of this ability to compute in a register’s phases in Chapter 10.

Reversibility and Scratch Qubits

During this chapter we’ve noted again and again that QPU operations need to be reversible. Naturally, you might ask, “How can I make sure that the arithmetic operations I want to perform are reversible?” Although there’s no hard-and-fast way to convert an arithmetical operation into a form that is reversible (and therefore more likely to work on a QPU), a helpful technique is the use of scratch qubits.

Scratch qubits are not necessary for encoding the input or output we’re interested in, but rather play a temporary role enabling the quantum logic connecting them.

Here’s a specific example of an otherwise irreversible operation that can be made reversible with a scratch qubit. Consider trying to find a QPU implementation of abs(a), a function computing the absolute value of a signed integer, as shown in Figure 5-15.

Figure 5-15. What QPU operations can compute the absolute value?

Since we’ve already seen in Figure 5-9 how to easily negate integers in QPU registers, you might think that implementing abs(a) is simple—negate our QPU register dependent on its own sign bit. But any attempt to do this will fail to be reversible (as we might expect, since the mathematical abs(a) function itself destroys information about the input’s sign). It’s not that we’ll receive a QPU compile or runtime error; the problem is that no matter how hard we try, we won’t ever find a configuration of reversible QPU operations able to produce the desired results.

Enter our scratch qubit! This is used to stash the sign of the integer in a. We begin with it initialized to ∣0⟩, and then use a CNOT to flip the scratch qubit dependent on the highest-weight qubit in register a. We then perform the negation conditional on the scratch qubit’s value (rather than directly on the sign of the a register itself), as shown in Figure 5-16.

Figure 5-16. Scratch qubits can make an irreversible operation reversible

With the scratch qubit involved, we now can find a set of gates that will ultimately implement abs on our a register. But before we verify in detail that the circuit in Figure 5-16 achieves this, note that the CNOT operation we use between our scratch qubit and the 0x4 qubit of a (which tells us the sign of its integer value in two’s complement) does not copy the sign qubit exactly. Instead, the CNOT entangles the scratch qubit with the sign qubit. This is an important distinction to note, since we also know that QPU operations cannot copy qubits.

Figure 5-17 follows the progression of these operations using an illustrative sample state that has varying relative phases, simply so that we can easily keep track of which circle moves where during the various QPU operations.

Figure 5-17. Circle notation steps for the absolute value

Note that each value in the superposition that corresponds to a starting with a positive or zero value is left unchanged throughout. However, values for which a has a negative value are moved first into the second row of circles (corresponding to the scratch qubit having been conditionally flipped), and then into the corresponding positive values (as required by abs), while remaining in the “scratch = 1” row.⁵

Following the action of the scratch qubit in circle notation visually demonstrates how it solves our irreversibility issues. If we tried to perform abs without a scratch qubit, our circle notation in Figure 5-17 would only have a single row, and trying to move the negative-value circles into the corresponding positive values would obliterate the magnitudes and phases already held there—such that we could never later figure out what the original state was (i.e., we would have an irreversible operation). The scratch qubit gives us an extra row we can move into and then across in, leaving everything from the original state untouched and recoverable.⁶

Uncomputing

Although scratch qubits are frequently a necessity, they do tend to get tangled up with our QPU registers. More precisely, they tend to get entangled. This introduces two related problems. First, scratch qubits rarely end up back in an all-zero state. This is bad news, since we now need to reset these scratch qubits to make them usable again further down the line in our QPU.

“No problem!” you may think, “I’ll just READ and NOT them as necessary, like we learned in Chapter 1.” But this would lead you to encounter the second problem. Because using scratch qubits almost always results in them becoming entangled with the qubits in our output register (this is certainly the case in Figure 5-17), performing a READ on them can have a disastrous effect on the output state they helped us create. Recall from Chapter 3 that when qubits are entangled, any operations you perform on one have unavoidable effects on the others. In the case of Figure 5-17, attempting to reset the scratch qubit to ∣0⟩ (as we must if we ever want to use it again in our QPU) destroys half of the quantum state of a!

Fortunately, there’s a trick that solves this problem: it’s called uncomputing. The idea of uncomputing is to reverse the operations that entangled the scratch qubit, returning it to its initial, disentangled ∣0⟩ state. In our abs example, this means reversing all the abs(a) logic involving a and the scratch qubit. Brilliant! We have our scratch qubit back in a ∣0⟩ state. Unfortunately, we will, of course, also have completely undone all the hard work of our absolute-value calculation.

What good is getting back our scratch qubit if we’ve also undone our answer? Thanks to the no-copying constraints faced by qubits, we can’t even copy the value stored in a to another register before uncomputing it. However, the reason uncomputing is not completely self-defeating is that we will often make use of our answer within register a before we uncompute. In most cases, functions such as abs are used as part of a larger arithmetic computation. For example, we might actually want to implement “add the absolute value of a to b.” We can make this operation reversible and save our scratch qubit with the circuit shown in Figure 5-18.

Figure 5-18. Using uncomputation to perform b += abs(a)

After these operations, a and b are likely entangled with one another; however, the scratch qubit has been returned to its disentangled ∣0⟩ state, ready to be used in some other operation. The larger operation is reversible, even though abs itself is not. In quantum computation, this trick is extremely common: use temporary scratch qubits to perform an otherwise-irreversible computation, perform other operations conditional on the result, and then uncompute.

In fact, although we cannot just simply “copy” the absolute value into another register before uncomputing its action, we can do something similar by initializing b to 0 before the addition in Figure 5-18. We can actually achieve the same result more simply using a CNOT operation instead of addition, as shown in Figure 5-19.

Figure 5-19. Using uncomputation to produce b xor abs(a)

Another extremely common application of uncomputation involves performing a computation (potentially using scratch qubits), storing the results in the relative phases of the output register, and then uncomputing the result. So long as the initial computation (and thus also the final uncomputation step) does not interfere with the relative phases of the output registers, they will survive the process intact. We make use of this trick in Chapter 6.

As an example, the circuit in Figure 5-20 performs the operation “flip the phase of any value where abs(a) equals 1.” We compute the absolute value using a scratch qubit, flip the phase of the output register only if the value is 1, and then uncompute.

Figure 5-20. Using uncomputation to perform phase(180) if abs(a)==1

In Figure 5-21 we follow this program step by step in circle notation.

Figure 5-21. Step-by-step walkthrough of using uncompute for conditional phase inversion

Mapping Boolean Logic to QPU Operations

Just as digital arithmetic is built from digital logic gates, to see in detail how the circuits for our basic QPU arithmetic work we rely on a toolbox of programmable quantum logic. In this section we’ll highlight the quantum analogs of some low-level digital logic gates.

Basic Quantum Logic

In digital logic, there are a few basic logic gates that can be used to build all of the others. For example, if you have just a NAND gate, you can use it to create AND, OR, NOT, and XOR, which can be combined into any logical function you wish.

Note that the NAND gates in Figure 5-22 can have any number of inputs. With a single input (the simplest case), NAND performs a NOT.

Figure 5-22. Digital NAND gates in different sizes

In quantum computation we can similarly start with one versatile gate, as in Figure 5-23, and build our quantum digital logic from it. To accomplish this, we’ll use a multiple-condition CNOT gate: the Toffoli gate. As with the NAND gate, we can vary the number of condition inputs to expand the logic performed, as shown in Example 5-6.

Figure 5-23. Quantum CNOT gates in different sizes

Note that this performs almost the same operation as NAND. We can express its digital-logic equivalent using AND and XOR, as shown in Figure 5-24.

Figure 5-24. The exact digital logic equivalent of our multicondition CNOT gate

Armed with this gate, we can produce QPU equivalents of a wide variety of logical functions, as shown in Figure 5-25.

Figure 5-25. Some basic digital logic gates, built from multiple conditioned CNOT gates

Notice that in some cases in order to get the desired logic function we need to add an extra scratch qubit, initialized to ∣0⟩. One substantial challenge in quantum computation is reducing the number of scratch qubits needed to perform a specific computation.

Conclusion

The ability to perform digital logic in superposition is a core part of most QPU algorithms. In this chapter, we have taken a close look at ways to manipulate quantum data and even to perform conditional operations within superpositions.

Performing digital logic in superposition is of limited use unless we can extract information from the resulting state in a useful way. Recall that if we try to READ a superposition of solutions to an arithmetic problem, we’ll randomly obtain just one of them. In the next chapter, we will explore a QPU primitive allowing us to reliably extract output from quantum superpositions, known as amplitude amplification.