Wiring Up the Circuits

The world is all gates, all opportunities, strings of tension waiting to be struck.

Ralph Waldo Emerson

Now that we understand qubits and the operations we can apply to one or more of them, it’s time to string together the actions to do something useful. In this chapter, we build out circuits and discuss their properties. From there, we survey basic algorithms, such as those that involve oracles and searches. Through this, you’ll better understand the core programming idioms in quantum computing.

Nontrivial quantum algorithms take advantage of qubit entanglement, the graceful way qubits work together and interact until we get a result. I think of this scripted interplay among qubits as an elegant dance, and that’s how this book got its title. dancing

Topics covered in this chapter

1. 9.1. So many gates
2. 9.2. From gates to circuits
   1. 9.2.1. Constructing a circuit
   2. 9.2.2. A note on controlled gates
3. 9.3. Building blocks and universality
   1. 9.3.1. The Toffoli gate
   2. 9.3.2. Making nand reversible
   3. 9.3.3. Building more complicated circuits
   4. 9.3.4. Copying a qubit
   5. 9.3.5. Teleportation
4. 9.4. Arithmetic
5. 9.5. Welcome to Delphi
6. 9.6. Amplitude amplification and interference
   1. 9.6.1. Flipping the sign
   2. 9.6.2. Inversion about the mean
   3. 9.6.3. Interference
   4. 9.6.4. Maximizing the amplitude
7. 9.7. Searching with Grover
   1. 9.7.1. Grover’s search algorithm
   2. 9.7.2. Using the oracle
   ...

9.1 So many gates

In practice, a hardware quantum computer implements a core set of primitive gates, and we construct the others using circuits of the primitives. These core operations may be among the ones we saw in the last chapter, or they may be much stranger looking: you can consider any 2-by-2 unitary matrix a 1-qubit gate.

The primitive gates depend on the technology used to create the physical quantum computer. We construct more advanced gates from these primitive gates. For example, the Qiskit and Cirq open-source quantum computing frameworks provide a large selection of gates you can use. 42 181 Qiskit Cirq

At the hardware level, experimental physicists and engineers work to optimize the core gates. Above that, other physicists and computer scientists try to create the best-performing higher-level gates.

In the classical case, machine code is extremely low-level and directly instructs the processor. Above that is assembly code, which abstracts...

9.2 From gates to circuits

A quantum register is a collection of qubits we use for computation. We number the qubits in the register with labels such as q₀, q₁, …, q_–n or q₁, q₂, …, q_n. The quantum system initializes all qubits in a register to state |0⟩. quantum$register circuit$quantum quantum$circuit

A quantum circuit is a sequence of gates applied to one or more qubits in a quantum register.

In some algorithms, we group qubits into one or more labeled registers to better delineate their roles. It’s common to have an upper register and a lower register, for example. upper register lower register register$upper register$lower

Let’s look at some simple example circuits to see how we put them together and what we call their components.

9.2.1 Constructing a circuit

The simplest circuit is

We give qubit q₀ the initial state |0⟩, but then...

9.3 Building blocks and universality

In section 2.4, we discussed classical gates, and I illustrated how to create an or gate from nand gates. nand is universal because we can make all the other classical logic gates from it. For example, nand`gate-style gate$nand`gate-style

We could construct any software we code for classical computers from millions of nand gates, but it would be horribly inefficient. There are higher-level gates and circuits in modern processors that are tremendously faster.

The basic CNOT acts like a xor on the standard kets. xor`gate-style gate$xor`gate-style

This maps the basis kets in this way:

The xor result is the final qubit state of q₁. More than simply a logic operation, this implements addition mod 2. That is, this standard gate does a basic arithmetic operation “⊕”. For example, |1⟩ ⊕ |1⟩ = |0⟩ and |1⟩ ⊕ |0⟩ = |1⟩...

9.4 Arithmetic

In section 2.5, we looked at the rudimentary ideas of doing binary addition via logic gates. We’ll revisit that but see how to do it using quantum gates. Like most such algorithms, researchers have published many papers on optimizing the circuits using methods such as the Quantum Fourier Transform, which we cover in section 10.1. algorithm$addition

Addition

I keep to a straightforward approach to help bridge the gap between classical and quantum versions. The gates we use are simple, and we replace bits with qubits. Instead of 0 and 1, we use |0⟩ and |1⟩, respectively. We call the data input qubits |x⟩ and | y⟩, and each is in the state |0⟩ or |1⟩ at any given time. We are essentially mimicking what we would do in the classical case.

If we do not worry about carry-in and carry-out qubits, our circuit looks like

where “⊕” is addition...

9.5 Welcome to Delphi

In ancient Greece, the Oracle of Delphi was a high priestess at the Temple of Apollo who issued prophecies under the right conditions and during warm weather. oracle

In computer science, an oracle is a function that we supply with data, and it responds with a 1 for yes and a 0 for no. Our oracles cannot answer random questions; we build them to respond to specific queries. For an algorithm using an oracle, two things are significant:

• The implementation of the oracle must be as fast and efficient as possible.
• We want to call the oracle as few times as possible to minimize the algorithm’s complexity.

An oracle is a black box, meaning we understand its behavior but not how it does what it does. We use it without seeing inside it.

Since we can represent all classical data by bits, we express the inputs to the oracle function as strings of zeros and ones. If we call the function f, which is traditional...

9.6 Amplitude amplification and interference

Suppose we have three qubits, and one of their quantum state standard basis kets {|000⟩, …, |111⟩} corresponds to a solution to some problem. We want to devise an algorithm to pick the correct ket and find the answer. I’m purposely not telling you the problem or how the kets map to the data and solution. Just assume we want to identify one of them that the algorithm can determine as best. algorithm$amplitude amplification amplitude$amplification

The first question is how to see that this best ket stands out from the others. The general form for a 3-qubit quantum register state is

with

If we initialize each qubit to |0⟩ and then apply H^⊗3, we get a balanced superposition: balanced superposition superposition$balanced

All the coefficients are equal, and the square of each absolute value is 1/8. If we measure the qubits now, we have an...

9.7 Searching with Grover

We just saw how if we have one standard basis ket in mind, we flip the probability amplitude and then amplify the amplitude for that ket. When we repeat the process enough times, we are likely to measure the right ket with high probability.

In the last section, I showed that we could pick out the known ket |010⟩ from among all the kets. So I found what I knew was there, and even knew where it was beforehand. We can use these techniques more generally. In this section, we put everything together to describe the famous quantum search algorithm discovered by Lov Kumar Grover, a computer scientist. The algorithm is based on amplitude amplification. Grover, Lov Kumar

9.7.1 Grover’s search algorithm

Instead of using the magic gate matrix U_|010⟩, which flips the sign of the amplitude of the given ket, we instead employ U_f, which is related to the oracle f. Grover’s search algorithm algorithm$Grover...

9.8 The Deutsch-Jozsa algorithm

I will now walk you through another early quantum algorithm that employs oracles. It shows us another form in which we express oracles in quantum circuits. algorithm$Deutsch-Jozsa Deutsch-Jozsa algorithm

Let’s begin with an example. Suppose I buy two standard decks of 52 playing cards. In a separate room where you cannot see me, I create a single deck of 52 cards where one of the following is true:

1. All the cards are red, or all the cards are black.
2. Half the cards (26) are black, and half are red.

We call the first option “constant” and the second “balanced.”

I now go to you and give you the problem of finding out which of the two possibilities is the case for the deck I am holding. You do so by looking at and then discarding cards at the top of the deck.

In the best case, the first card is one color, and the second is the other. Therefore, the...

9.9 The Bernstein-Vazirani algorithm

Suppose I were to say to you: algorithm$Bernstein-Vazirani Bernstein-Vazirani algorithm

I’m thinking of a number from 0 to 15 inclusive.
Ask me questions to guess which one it is.

How would you go about guessing the number? How many questions would you need?

This is a search problem, but it has some structure. The numbers in the collection we are searching are consecutive and ordered. There is no reason to consider an O(n) sequence of questions such as

“Is it 0?” No.
“Is it 1?” No.
“Is it 2?” No.
⋮
“Is it 13?” Yes.

Grover could help with an O(√n) approach, but we can do better with O(log₂(n)) classically:

“Is it greater than 7?” Yes.
“Is it greater than 11?” Yes.
“Is it greater than 13?” No.
“Is it greater than 12?” Yes.
“...

9.10 Simon’s algorithm

We’ll cover one more algorithm using an oracle before leaving this chapter: Simon’s algorithm. It may seem like an odd use of an oracle, but the techniques are further used in section 10.6 when we develop function period finding before tackling Shor’s factoring algorithm. algorithm$Simon’s Simon’s algorithm

We do not study Simon’s algorithm for its wide applicability. Rather, it demonstrates how a quantum algorithm can demonstrate an exponential improvement over the classical approach. So while this particular algorithm may not have much use, it gives people confidence that future quantum computing algorithms will perform significantly better than anything we can do today on problems of societal or commercial importance.

9.10.1 The problem

Our problem is finding how a function’s values on the whole numbers W repeat themselves.

A function

...

9.11 Summary

This chapter examined how to link gates together for multiple qubits to create circuits. Circuits implement algorithms, and these are the building blocks for solutions. After all, we’re not only interested in the theory of how one might do quantum computing; we want to accomplish real work.

We looked at some well-known basic algorithms for quantum computing, including Simon’s, Bernstein-Vazirani, Deutsch-Jozsa, amplitude amplification, and Grover’s search.

Quantum computing will show its advantage when it can perform calculations that are intractable today. To be valuable, quadratic or exponential speed increases over classical methods will be required.

The next chapter considers integer factorization and Shor’s factoring algorithm. We define the Quantum Fourier Transform, phase estimation, and function period finding.