Quantum circuits: universal gates and cost

1 / 13 · Learn

Before you start

Part 2 is about building quantum programs and pricing them, and then about the algorithms that run on them. This lesson treats a circuit as a program: a list of instructions, each with a cost. You will rewrite circuits into equivalent ones, build controlled gates and the Toffoli gate from smaller pieces, find out what a small gate set can and cannot do, and count what a circuit costs.

By the end of this lesson you can:

turn a circuit into a matrix product in the right order, and use four standard rewrites;
build controlled- $Z$ and other controlled gates from CNOT and single-qubit gates;
check the 15-gate Toffoli circuit and say why it needs seven $T$ ⁠-type gates;
say what it means that $\{H, T, \text{CNOT}\}$ is universal, and why it can’t mean exact;
count a circuit’s gates, depth, two-qubit gates and $T$ gates, and cut its depth;
build a NOT with many controls from Toffolis and work qubits.

Check yourself

A warm-up: make a guess before reading on. The lesson comes back to it.

A quantum computer offers only the gates $H$ , $T$ and CNOT and you may use as many gates as you need. Can circuits made from them build every single-qubit gate exactly?

AYes: with enough gates, each of them is built exactly
BNo, but each one can be approximated as closely as you like
CNo: the circuits reach only a few gates, such as $X$ , $Z$ and $S$
DNot even approximately: most gates are out of reach

Show the answer

Answer: B. No, but each one can be approximated as closely as you like

Circuits from $H$ , $T$ and CNOT can be listed by length, so there are only countably many, while every single-qubit gate form a continuum. So the answer is no, but the set is universal: every gate can be approximated to any accuracy, at a cost that grows slowly with the accuracy.

Why not the others

A. Universal means approximately. Circuits from a finite gate set can be listed, first those with one gate, then those with two, and so on: there are countably many. The gates you want form a continuum, which no list can cover. So most of them can be approached as closely as you like, but never reached.
C. They reach infinitely many. One product of $H$ and $T$ is a rotation by an angle that is an irrational fraction of a full turn, so its powers never repeat and come close to every rotation about its axis.
D. Every gate can be approximated to any accuracy you name. What fails is exactness: there are only countably many circuits, so most gates are approached, never reached.

Check yourself

A warm-up: make a guess before reading on. The lesson comes back to it.

Two circuits compute the same thing. Circuit A has 2,000 gates, 300 of them $T$ gates. Circuit B has 1,200 gates, 900 of them $T$ gates. All the other gates are $H$ , $S$ or CNOT. Both will run on an error-corrected quantum computer. Which is likely to be cheaper to run?

ACircuit A
BCircuit B
CAbout the same, since they compute the same thing
DThere is no way to tell without running both

Show the answer

Answer: A. Circuit A

On an error-corrected machine $H$ , $S$ and CNOT are cheap and $T$ gates are expensive, so the $T$ ⁠-count decides. Circuit A has 300 $T$ gates against 900. Even at a modest ten to one, it costs about 4,700 units against 9,300, despite having more gates.

Why not the others

B. Circuit B has fewer gates, but 900 of them are $T$ gates, and on an error-corrected machine the $T$ gates dominate the cost. Even if a $T$ gate cost only ten times as much as each other gate, B would come to about 9,300 units against 4,700.
C. Cost belongs to the circuit, not to the job it does: two circuits for the same unitary can differ a lot. Here they differ in the gate that dominates the cost on an error-corrected machine, the $T$ gate.
D. The counts are enough for a good estimate. On an error-corrected machine $H$ , $S$ and CNOT are cheap and each $T$ gate costs many times more, so compare the $T$ ⁠-counts.

2 / 13 · Learn

A circuit is a program

A quantum circuit is a program. Each gate is an instruction, and the instructions run from left to right. Each gate is also a unitary matrix, so the whole program is a single matrix: the product of its gates. The order needs care. If a circuit applies $A$ , then $B$ , then $C$ to $\ket\psi$ , the state becomes

C\big(B(A\ket\psi)\big) = CBA\ket\psi.

The first gate in time is the factor next to the ket, at the right end of the product, and each later gate multiplies from the left. You met this in Lesson 4. It matters more now, because long circuits are compiled, rewritten and costed as products, and most pairs of gates don’t commute.

Time runs left to right along the wire, but the operator is written right to left: the first gate, $A$ , is the factor next to the ket.

Check yourself

A circuit applies $H$ , then $T$ , then $X$ to one qubit in the state $\ket\psi$ . Which product of matrices equals the whole circuit?

A $HTX$
B $H + T + X$
C $XTH$
D $H\otimes T\otimes X$

Hint

Which gate acts on $\ket\psi$ first, and where must it stand in the product?

Show the answer

Answer: C. $XTH$

$H$ acts first, so it sits next to the ket: $X\big(T(H\ket\psi)\big) = XTH\ket\psi$ . Time runs left to right in the circuit and right to left in the product.

Why not the others

A. That lists the gates in circuit order. The first gate acts on $\ket\psi$ first, so it stands next to the ket: $X\big(T(H\ket\psi)\big) = XTH\ket\psi$ . And the order matters here, since $HTX \ne XTH$ .
B. Gates in sequence compose: each acts on the output of the one before, which makes a product, not a sum. A sum of unitary matrices is usually not even unitary.
D. A tensor product describes gates side by side on different qubits, and this one would be an $8\times8$ matrix. Gates one after another on the same qubit multiply.

Two more gates join $X$ , $Y$ , $Z$ and $H$ . They are phase gates: each leaves $\ket0$ alone and multiplies $\ket1$ by a phase.

S = \begin{bmatrix}1&0\\0&i\end{bmatrix},\qquad T = \begin{bmatrix}1&0\\0&e^{i\pi/4}\end{bmatrix}

On the Bloch sphere, $S$ is a quarter turn about the $z$ axis and $T$ an eighth of a turn. Phases multiply, so two $T$ gates make an $S$ , since $e^{i\pi/4}\cdot e^{i\pi/4} = i$ , and two $S$ gates make a $Z$ . The inverses $S^\dagger$ and $T^\dagger$ carry the phases $-i$ and $e^{-i\pi/4}$ . $T$ matters twice in this lesson: it is the gate that makes small gate sets universal, and on an error-corrected machine it is the expensive one.

Check yourself

$T = \begin{bmatrix}1&0\\0&e^{i\pi/4}\end{bmatrix}$ . What is the smallest number of $T$ gates in a row (at least one) whose product equals $Z$ exactly?

Hints

$T$ leaves $\ket0$ alone and multiplies $\ket1$ by $e^{i\pi/4}$ . What does a row of $k$ of them do to $\ket1$ ?
$T^k$ multiplies $\ket1$ by $e^{ik\pi/4}$ . Which phase does $Z$ put on $\ket1$ ?

Show the answer

Answer: $4$

$T^k$ leaves $\ket0$ alone and multiplies $\ket1$ by $e^{ik\pi/4}$ . $Z$ puts the phase $-1 = e^{i\pi}$ on $\ket1$ , so $k\pi/4 = 4\pi/4$ and $k = 4$ .

Common slips

$2$ : Two $T$ gates give the phase $e^{i\pi/2} = i$ : that is $S$ . $Z$ needs $-1 = e^{i\pi}$ , twice that phase.
$8$ : Eight $T$ gates give the phase $e^{2i\pi} = 1$ : that is the identity. $Z$ is reached halfway, after four.

3 / 13 · Explore

Rewriting circuits

A program can often be rewritten into a shorter or faster one that does the same job, and compilers for quantum circuits do this all the time. The rewrites rest on identities between small circuits. You know two of them from Lesson 4: $HXH = Z$ and $HZH = X$ . They say that $H$ swaps the $x$ and $z$ axes of the Bloch sphere, turning a bit flip into a phase flip and back.

The same idea works on two qubits, with a surprising result. Before you see the list, test your intuition on one circuit: $H$ on both qubits, then a CNOT with its control on top, then $H$ on both qubits again.

Predict, then see

The circuit is $(H\otimes H)\,\text{CNOT}\,(H\otimes H)$ , with the CNOT’s control on the top qubit. The input is $\ket{01}$ : top qubit 0, bottom qubit 1. What comes out?

A $\ket{01}$ : the control is 0, so the CNOT does nothing and the Hadamards cancel
BA random basis state: the Hadamards spread the state out
C $\ket{11}$ : the top qubit flips
D $\ket{00}$ : the bottom qubit flips

Why did the top qubit, the CNOT’s control, change? A sentence or two is enough.

Show what happens

What happens: C. $\ket{11}$ : the top qubit flips

After the first Hadamards the input is $\ket+\ket-$ . The CNOT flips the bottom qubit in the branch where the top is 1, and flipping $\ket-$ gives $-\ket-$ , so the top qubit’s $\ket1$ branch gains a minus sign: $\ket+\ket-$ becomes $\ket-\ket-$ . The last Hadamards turn that into $\ket1\ket1$ . The truth table shows the pattern: the top qubit flips exactly when the bottom one is 1. The whole circuit is a CNOT with control and target swapped.

Why not the others

A. The Hadamards don’t cancel, because the CNOT sits between them. Inside, the CNOT sees $\ket+\ket-$ , not $\ket0\ket1$ , and a flip of $\ket-$ is only a sign, which lands on the top qubit.
B. The second layer of Hadamards undoes the spreading of the first. The output is one basis state, every time.
D. The bottom qubit comes out as it went in. In the middle it is $\ket-$ , and $X\ket- = -\ket-$ : flipping $\ket-$ only changes a sign.

Here are the four rewrites to know by heart. Each one holds exactly, as an equation between matrices.

$HXH = Z$ and $HZH = X$ : a bit flip between Hadamards is a phase flip, and the other way round.
Hadamards on both qubits, before and after a CNOT, turn it upside down: control and target trade places. This is what you just saw.
An $X$ on the control before and after a CNOT makes it fire when the control is 0 instead of 1. That is an anti-control, drawn as an open circle.

You can check each one by multiplying matrices, or by following every basis state through both sides. The figure collects them.

H X H = Z

H Z H = X

Hadamards reverse a CNOT

X around a control

Four rewrites. In each panel the circuit on the left equals the one on the right exactly, with no leftover phase: $HXH = Z$ , $HZH = X$ , a CNOT turned upside down, and an anti-control.

Check yourself

Build a gate that flips the bottom qubit exactly when the top qubit is 0, using $X$ gates and one CNOT. A control dot and an $X$ in the same column make a CNOT. The truth table shows what your circuit does to each basis input.

Build it in the circuit builder (gates: X, control).

Hints

Which rewrite turns a control into an anti-control?
Put an $X$ on the top wire before the CNOT and another after it.

Show the answer

One circuit that works: X on q0, then CNOT q0→q1, then X on q0.

$X$ on the top wire turns a 0 into a 1, so the CNOT fires; the second $X$ restores the top qubit. Another answer works too: a CNOT followed by an $X$ on the bottom wire flips the bottom qubit $1\oplus a$ times, which is once exactly when $a = 0$ .

4 / 13 · Learn

Controlled gates

CNOT is one member of a family. For any single-qubit gate $U$ , controlled- $U$ applies $U$ to the target in the branch where the control is $\ket1$ and does nothing where it is $\ket0$ :

\ket0\ket\psi \mapsto \ket0\ket\psi, \qquad \ket1\ket\psi \mapsto \ket1\,U\ket\psi.

CNOT is controlled- $X$ . Controlled- $Z$ , written CZ, leaves $\ket{00}$ , $\ket{01}$ and $\ket{10}$ alone and multiplies $\ket{11}$ by $-1$ . That sign belongs to both qubits equally, so CZ has no real control and target. You can build it with a rewrite: put $H$ on the target before and after a CNOT. Where the control is 1, the target then gets $HXH = Z$ ; where it is 0, it gets $HH = I$ .

Check yourself

Build controlled- $Z$ from Hadamards and one CNOT. The truth table should show every input unchanged except $\ket{11}$ , which picks up a phase of $\pi$ (a minus sign).

Build it in the circuit builder (gates: H, control, X).

Hints

Which rewrite turns $X$ into $Z$ ?
$HXH = Z$ : put $H$ on the target wire before and after the CNOT.

Show the answer

One circuit that works: H on q1, then CNOT q0→q1, then H on q1.

$H$ on the target, then the CNOT, then $H$ on the target: where the control is 1 the target gets $HXH = Z$ , and where it is 0 it gets $HH = I$ . That is CZ. Because CZ is symmetric, the same circuit upside down (Hadamards on the top wire and a CNOT controlled from the bottom) works too.

Check yourself

What is $\text{CZ}\,\ket+\ket1$ ? (CZ multiplies $\ket{11}$ by $-1$ and leaves the other basis states alone.)

A $\ket-\ket1$
B $\ket+\ket1$ , unchanged
C $\ket+\ket0$
D $-\ket+\ket1$

Hints

Write the input as a sum of two basis states.
Only the $\ket{11}$ term changes sign.

Show the answer

Answer: A. $\ket-\ket1$

Written out, the input is $\tfrac{1}{\sqrt2}(\ket{01} + \ket{11})$ . CZ changes the sign of $\ket{11}$ only, giving $\tfrac{1}{\sqrt2}(\ket{01} - \ket{11}) = \ket-\ket1$ . The top qubit changed, so for CZ the words control and target are only labels.

Why not the others

B. The top qubit is drawn as the control, but that only means it is never flipped on basis inputs. Here it is in a superposition, and the sign on $\ket{11}$ lands on its $\ket1$ branch, which turns $\ket+$ into $\ket-$ or back.
C. CZ never flips a bit: on basis states it only changes signs. The qubit in $\ket1$ stays $\ket1$ .
D. The minus sign goes on the $\ket{11}$ term only, not on both terms. Write the input out: $\tfrac{1}{\sqrt2}(\ket{01} + \ket{11})$ , and only the second term changes sign.

Any controlled gate from two CNOTs

Every single-qubit gate can be written as $U = e^{i\alpha}AXBXC$ , for some angle $\alpha$ and single-qubit gates $A$ , $B$ , $C$ with $ABC = I$ . Then controlled- $U$ is: $C$ on the target, a CNOT, $B$ on the target, a CNOT, $A$ on the target, and the phase gate $\text{diag}(1, e^{i\alpha})$ on the control. When the control is 0, the CNOTs do nothing and the target gets $ABC = I$ . When it is 1, the target gets $AXBXC$ , and the phase gate supplies $e^{i\alpha}$ . So any controlled single-qubit gate costs at most two CNOTs.

5 / 13 · Explore

The Toffoli gate from T gates

The Toffoli gate from Lesson 6 flips its target when both controls are 1. It acts on three qubits, yet it can be built exactly from one- and two-qubit gates: two $H$ , six CNOTs and seven gates that are $T$ or $T^\dagger$ , fifteen in all. The two Hadamards play the same trick as in CZ: they turn the Toffoli’s flip of the target into a sign, $-1$ on $\ket{111}$ only. Every other gate is a CNOT or a $T$ ⁠-type gate, and together they only change phases: the CNOTs flip bits along the way but undo every flip. Step through the circuit on a few inputs, then read the truth table: it lists every basis input with its output, and it would mark any output that picked up a phase.

Check yourself

Count the gates in the circuit above that are $T$ or $T^\dagger$ . How many are there?

Hint

Look for boxes labelled $T$ or $T^\dagger$ on all three wires, not just the target.

Show the answer

Answer: $7$

Four $T$ gates and three $T^\dagger$ gates: seven in all. Four of them sit on the target wire, two on $b$ and one on $a$ .

Common slips

$4$ : That counts the $T$ gates only. The $T^\dagger$ gates are $T$ ⁠-type too, and they cost the same: there are three of them.
$3$ : That counts the $T^\dagger$ gates only. There are also four $T$ gates.
$15$ : That counts every gate. Leave out the two $H$ gates and the six CNOTs.
$6$ : Six is the number of CNOTs. Count the boxes labelled $T$ or $T^\dagger$ .

Check yourself

The truth table shows that the circuit matches the Toffoli gate on all eight basis inputs, phases included. Why is that enough to show that the two are the same gate?

AIt is enough to match the 0/1 outputs; the phases on basis outputs never matter
BIt isn’t enough: the measurement statistics must be compared as well
CIt isn’t enough: every superposition must be tested too
DBoth are linear, so agreeing on every basis state means agreeing on every superposition of them

Show the answer

Answer: D. Both are linear, so agreeing on every basis state means agreeing on every superposition of them

A gate is linear, so its action on $\sum_x\alpha_x\ket x$ is $\sum_x\alpha_x U\ket x$ . Two gates that give the same outputs on all basis states, phases included, are the same matrix.

Why not the others

A. The phases do matter. A circuit that sent $\ket{111}$ to $-\ket{110}$ would match the 0/1 outputs, yet on a superposition such as $\ket{11}\ket+$ it would give a different state. The truth table marks any row whose output picks up a phase, and here it marks none, which is why the match is exact.
B. Measurement statistics follow from the output states. If the two gates give the same state for every input, every statistic agrees too.
C. Linearity does that work. A superposition is a sum of basis states, and a linear map sends a sum to the sum of the images, so two gates that agree on the basis agree everywhere.

Why seven? Apart from the two Hadamards, the circuit must multiply $\ket{abc}$ by $(-1)^{abc} = e^{i\pi\,abc}$ . A product such as $abc$ is hard to reach with phase gates, but parities are easy. A CNOT can place a parity such as $a\oplus c$ on a wire, a $T$ on that wire then adds the phase $\pi/4$ when the parity is 1, and a $T^\dagger$ subtracts it. The bridge is an identity for bits:

\begin{aligned}4abc = {}&a + b + c - (a\oplus b) - (a\oplus c) \\ &- (b\oplus c) + (a\oplus b\oplus c)\end{aligned}

Multiply by $\pi/4$ : the phase $\pi\,abc$ is a sum of seven parity terms, four with a plus sign (a $T$ each) and three with a minus sign (a $T^\dagger$ each). The six CNOTs bring each parity onto a wire when its gate needs it, and put the wires back afterwards.

Check yourself

Check the identity for $a = b = c = 1$ : what is $a + b + c - (a\oplus b) - (a\oplus c) - (b\oplus c) + (a\oplus b\oplus c)$ ?

Hint

$1\oplus1 = 0$ , and $1\oplus1\oplus1 = 1$ .

Show the answer

Answer: $4$

$1 + 1 + 1 - 0 - 0 - 0 + 1 = 4 = 4abc$ . Times $\pi/4$ that is a phase of $\pi$ , the minus sign on $\ket{111}$ . With any bit equal to 0 the seven terms cancel to 0.

Common slips

$3$ : Look at the last term: $1\oplus1\oplus1 = 1$ , since three 1s make an odd count. So the sum is $3 - 0 + 1 = 4$ .
$1$ : That treats $1\oplus1$ as 1, like OR. XOR is addition mod 2, so $1\oplus1 = 0$ , and the three pair terms vanish.
$0$ : Zero is what the sum gives when at least one bit is 0. With all three bits equal to 1 it is $1 + 1 + 1 - 0 - 0 - 0 + 1 = 4$ .

6 / 13 · Learn

Universal gate sets

Which gates does a quantum computer need? A gate set is universal if circuits made from it can approximate every unitary, on any number of qubits, as closely as you like. Two facts give a small universal set. First, CNOT together with all single-qubit gates builds every unitary exactly. Second, $H$ and $T$ alone approximate every single-qubit gate: one product of them is a rotation by an angle that is an irrational fraction of a full turn, so its powers never repeat and come as close as you like to any rotation about its axis, and a second such rotation about another axis does the rest. So $\{H, T, \text{CNOT}\}$ is universal.

Approximation errors are easy to control, because they add up. If each of $m$ gates is replaced by one within $\epsilon$ of it (on every input the two outputs differ by at most $\epsilon$ ), the whole circuit is within $m\epsilon$ of the original.

Check yourself

A circuit has 500 gates. A compiler replaces each one by an approximation within $\epsilon = 0.0001$ . At most how far can the new circuit’s output be from the original’s?

Hint

Errors of approximated gates add up.

Show the answer

Answer: $\frac{1}{20}$

The errors add: $500\times0.0001 = 0.05$ . To keep the whole circuit within $\epsilon_{\text{total}}$ , approximate each gate to within $\epsilon_{\text{total}}/m$ .

Common slips

$0$ : That is the error of one gate. Each of the 500 gates adds its own, and in the worst case they add up: $500\times0.0001$ .

Universal does not mean exact. Imagine listing every circuit that can be built from $H$ , $T$ and CNOT: first all circuits with one gate, then all with two gates, and so on. There are only finitely many of each length, so every circuit gets a place in the list: the circuits are countable. The gates they are meant to build are not. The rotations $R_z(\theta)$ about the $z$ axis alone form a continuum, one for every real angle $\theta$ , and no list contains every real number. So most rotations are missing from the list. They can be approached as closely as you like, but never reached. The same argument works for any finite gate set, with or without extra work qubits.

Check yourself

A compiler must turn $R_z(1)$ , a rotation by 1 radian about the $z$ axis, into $H$ , $T$ and CNOT gates. What can it deliver?

AA circuit within any error you name, say $10^{-10}$ , but never an exact one
BNothing useful: a rotation by 1 radian is not one of the reachable gates
CAn exact circuit, provided it may use extra work qubits
DAn exact circuit, if it searches long enough

Show the answer

Answer: A. A circuit within any error you name, say $10^{-10}$ , but never an exact one

The gate set is universal, so some circuit comes within any $\epsilon$ you name. None is exact: the circuits are countable, and the entries of their matrices are built from $1/\sqrt2$ and $i$ in a way that can never produce $e^{i}$ .

Why not the others

B. Not reachable exactly, but reachable as closely as you like. That is what universal means, and an error of $10^{-10}$ is as good as exact for any real computation.
C. Work qubits make the list of circuits longer but not uncountable, so almost every gate is still missing from it, and $R_z(1)$ is one of them.
D. No search can find it, because it doesn’t exist. Circuits from these gates form a countable list, and almost no rotation angle appears in it; 1 radian is one of the missing ones. The search can only get closer.

How many gates does a good approximation take? The Solovay–Kitaev theorem gives a general answer. Take any finite set of single-qubit gates that is universal for one qubit and contains each gate’s inverse. Then every single-qubit gate can be approximated to within $\epsilon$ by about $\log^c(1/\epsilon)$ gates from the set, where $c$ is a fixed constant. The first proofs give $c$ close to 4, later ones less. You need only the statement: the cost grows like a power of $\log(1/\epsilon)$ , so doubling the number of correct digits multiplies the cost by a fixed factor rather than squaring it.

For $H$ and $T$ , methods found since then do better still. A rotation about the $z$ axis needs about $3\log_2(1/\epsilon)$ $T$ gates, plus cheaper gates such as $H$ and $S$ . Each extra decimal digit costs about $3\log_2 10 \approx 10$ more $T$ gates.

The rule of thumb $3\log_2(1/\epsilon)$ for one rotation: each factor of 100 in accuracy adds about 20 $T$ gates, a straight line in the number of digits.

Check yourself

Use the rule of thumb from this lesson: about how many $T$ gates does it take to approximate a rotation about the $z$ axis to within $\epsilon = 10^{-9}$ ?

Hints

The rule of thumb is $3\log_2(1/\epsilon)$ .
$\log_2(10^{9}) = 9\log_2 10 \approx 9\times3.32$ .

Show the answer

Answer: $90$

$3\log_2(10^{9}) = 3\times9\times\log_2 10 \approx 90$ : about ten $T$ gates for each decimal digit of accuracy. Any answer within a few of 90 is fine, since the rule is approximate.

Common slips

$30$ : That is $\log_2(1/\epsilon)$ itself, about 30. The rule of thumb is three times that: $3\log_2(1/\epsilon) \approx 90$ .
$9$ : That is the number of decimal digits. Each digit is a factor of 10, and $\log_2 10 \approx 3.32$ , so the count is about $3\times3.32\times9 \approx 90$ .

Refresher: Big-O and repeated trials How $\log n$ , $\sqrt n$ , $n^2$ and $2^n$ compare, what big-O notation hides, and why repeating a test makes failure unlikely so fast.

Why no method can do much better

A counting argument gives a floor. With $k$ gate types there are at most $k^L$ circuits of $L$ gates. To come within $\epsilon$ of every rotation $R_z(\theta)$ , the circuits must be spread around the whole circle of angles with gaps of order $\epsilon$ , so you need on the order of $1/\epsilon$ of them. That forces $k^L$ to be at least of order $1/\epsilon$ , so $L$ grows at least like $\log(1/\epsilon)$ . So the logarithmic growth of $3\log_2(1/\epsilon)$ is the best kind possible, and the only question left is the constant in front. See the refresher for how slowly logarithms grow.

7 / 13 · Learn

What a circuit costs

Two circuits can do the same job at very different prices, and the price can mean several things.

Gate count: the total number of gates.
Depth: the number of layers, when gates on different qubits run at the same time. It sets the running time.
Two-qubit gate count: on today’s machines a CNOT fails roughly ten times as often as a one-qubit gate, so this count often decides whether a run gives usable results.
$T$ ⁠-count: on a future error-corrected machine, $H$ , $S$ and CNOT are cheap and each $T$ gate costs many times more. The reason lies in how error-correcting codes work, which is beyond these lessons.

The Toffoli circuit scores 15 gates, 6 two-qubit gates, $T$ ⁠-count 7 and depth 11. Which number matters depends on the machine. The mistake is to think that the gate count alone tells you.

Check yourself

On a noisy machine each CNOT fails with probability about 1% and each one-qubit gate with probability about 0.1%. Circuit A has 60 gates, 8 of them CNOTs. Circuit B has 45 gates, 30 of them CNOTs. Both compute the same thing. Which is more likely to run without any gate failing?

ACircuit A
BCircuit B, because it has fewer gates
CAbout equally likely, since they compute the same thing
DYou can’t tell without the depth of each circuit

Show the answer

Answer: A. Circuit A

Add up the chances of failure: A about $52\times0.1\% + 8\times1\% \approx 13\%$ , B about $15\times0.1\% + 30\times1\% \approx 32\%$ . A runs cleanly about 88% of the time and B about 73%.

Why not the others

B. B has fewer gates but far more CNOTs, and the CNOTs carry most of the risk. Expected failures: A about $52\times0.001 + 8\times0.01 \approx 0.13$ , B about $15\times0.001 + 30\times0.01 \approx 0.32$ .
C. What the circuit computes doesn’t set its error rate; its gates do. B uses 22 more CNOTs, each ten times riskier than a one-qubit gate.
D. Depth matters for how long the qubits must hold their state, but here every gate has its own chance to fail, and the gate counts already settle it: B’s 30 CNOTs dominate.

Depth needs a little care. Put each gate in the earliest layer that comes after every earlier gate on its own wires; the number of layers is the depth. A CNOT ties its two wires together, so a gate after it on either wire must wait for it.

Depth can often be cut without changing what the circuit does, by moving a gate past gates it commutes with. Three rules cover most cases. Gates on different wires always commute. A gate that is diagonal in the 0/1 basis, such as $Z$ , $S$ or $T$ , commutes with a CNOT when it sits on the control, because the CNOT only reads the control’s 0/1 value. An $X$ commutes with a CNOT when it sits on the target, because the CNOT applies either nothing or $X$ there.

As written

T on q0 moved first

The same five gates, twice. As written, the $T$ on $q_0$ waits for the CNOT and needs a fourth layer. A $T$ on a control commutes with the CNOT, so it can move to the front and share layer 1: depth 3.

Check yourself

The circuit above has depth 5. Which single change lowers the depth without changing what the circuit does?

AMove the $X$ on $q_1$ to the very start
BMove the $T$ on $q_0$ to just after the CNOT
CMove the first $H$ on $q_0$ to the end of its wire
DNothing: five gates take five layers

Show the answer

Answer: A. Move the $X$ on $q_1$ to the very start

An $X$ on the target commutes with the CNOT, and it commutes with the gates on $q_0$ , so it can move to the start and share layer 1 with the first $H$ . The layers become $H$ and $X$ , then $T$ , then $H$ , then the CNOT: depth 4. The chain $H, T, H$ on $q_0$ can’t be reordered, since $T$ and $H$ don’t commute.

Why not the others

B. A $T$ on the control would commute with the CNOT, but to get there it must pass the $H$ after it, and $T$ doesn’t commute with $H$ . That move changes the circuit.
C. $H$ commutes neither with $T$ nor with a CNOT on its control, so moving it changes what the circuit does.
D. Gates on different wires can share a layer. The $X$ on $q_1$ sits on the CNOT’s target, where it commutes with the CNOT, so it can move to the front and run alongside the first $H$ .

Check yourself

A circuit on three qubits applies these gates, in this order:

$H$ on $q_0$
a CNOT with control $q_0$ and target $q_1$
$T$ on $q_1$
$H$ on $q_2$
a CNOT with control $q_1$ and target $q_2$
$X$ on $q_0$

Gates on different qubits can run in the same layer. What is the depth of the circuit as written, without moving any gate past another?

Hints

Put each gate in the earliest layer that comes after every earlier gate on its wires.
A CNOT uses two wires: it waits for both, and later gates on either wire wait for it.

Show the answer

Answer: $4$

The layers of gates 1 to 6 are 1, 2, 3, 1, 4, 3, so the depth is 4. The CNOTs pass the delay from one wire to another, which is why the depth exceeds the 3 gates of the busiest wire.

Place the gates one at a time, each in the first layer after every earlier gate on its wires:

$H$ on $q_0$ : layer 1 (nothing earlier on its wires)
a CNOT with control $q_0$ and target $q_1$ : layer 2 (after gate 1)
$T$ on $q_1$ : layer 3 (after gate 2)
$H$ on $q_2$ : layer 1 (nothing earlier on its wires)
a CNOT with control $q_1$ and target $q_2$ : layer 4 (after gate 3)
$X$ on $q_0$ : layer 3 (after gate 2)

The deepest layer is 4, so the depth is 4.

Common slips

$6$ : That counts the gates. Gates on different wires can share a layer, so the depth is smaller than the gate count here.
$3$ : That is the number of gates on the busiest wire. But a CNOT ties two wires together: a gate after it must wait for the gates before it on both wires. Follow the layers through the CNOTs.

8 / 13 · Learn

Many controls

Many algorithms need a NOT with $k$ controls, which flips the target only when all $k$ controls are 1; Grover search, later in this part, needs one in every round. For $k = 2$ it is the Toffoli. For larger $k$ , build it from Toffolis and $k - 1$ extra work qubits that start in $\ket0$ :

Compute. A Toffoli writes $c_1c_2$ into $w_1$ . The next writes $w_1c_3 = c_1c_2c_3$ into $w_2$ , and so on, until $w_{k-1}$ holds the AND of all $k$ controls.
Act. A CNOT from $w_{k-1}$ flips the target when that AND is 1.
Uncompute. The Toffolis of step 1 run again in reverse order. Each one is its own inverse, so every work qubit returns to $\ket0$ .

In all: $2(k-1)$ Toffolis, one CNOT and $k - 1$ work qubits.

A NOT with three controls. Two Toffolis compute $c_1c_2c_3$ into $w_2$ , by way of $w_1$ ; a CNOT flips the target when $w_2$ is 1; two more Toffolis return both work qubits to $\ket0$ .

Check yourself

Why run the Toffolis again at the end, instead of leaving the work qubits as they are?

ABecause a Toffoli gate only works when it comes in a pair
BTo undo the flip of the target, so the gate can be reversed
CThere is no real need: the work qubits can simply be ignored
DLeft alone, the work qubits would stay entangled with the controls and spoil later interference; uncomputing returns them to $\ket0$

Show the answer

Answer: D. Left alone, the work qubits would stay entangled with the controls and spoil later interference; uncomputing returns them to $\ket0$

After the compute half, $w_1$ holds $c_1c_2$ , and so on. With the controls in superposition that is entanglement between the work qubits and the controls, which ruins interference later in the algorithm. Running the Toffolis backwards resets every work qubit to $\ket0$ while the target keeps its flip. Lesson 13 is about this compute, act, uncompute pattern.

Why not the others

A. A single Toffoli is a perfectly good gate; the compute half uses them one at a time. The second copies are there to clean up, not to complete the first ones.
B. The uncompute Toffolis never touch the target: they read the controls and work qubits and write only to work qubits. The target’s flip, made by the middle CNOT, stays.
C. Ignoring them doesn’t make them go away. If the controls are in a superposition, $w_1$ ends up holding $c_1c_2$ in each branch, so branches that differ in $c_1c_2$ also differ on $w_1$ and can no longer interfere. The rest of the circuit then behaves as if the controls had been measured.

Check yourself

With this construction, how many work qubits does a NOT with 6 controls need?

Hint

How many Toffolis does the compute half use, and how many new work qubits does each one write to?

Show the answer

Answer: $5$

$w_1$ holds $c_1c_2$ , and each of the controls $c_3, \ldots, c_6$ needs one more work qubit: $k - 1 = 5$ .

Common slips

$6$ : One per control is one too many. The first Toffoli combines two controls at once, so $k - 1 = 5$ work qubits are enough.
$10$ : That is the number of Toffolis, $2(k-1)$ . The uncompute half reuses the same work qubits, so there are only $k - 1 = 5$ .

A cheaper version

The target itself can stand in for the last work qubit. Compute $c_1c_2\cdots c_{k-1}$ into $k - 2$ work qubits, let one Toffoli with controls $c_k$ and the last work qubit flip the target directly, and uncompute. That uses $2k - 3$ Toffolis and $k - 2$ work qubits: for $k = 3$ , three Toffolis and a single work qubit. Cleverer constructions need fewer work qubits still, at the price of more gates.

9 / 13 · Worked example

Worked example: pricing a many-control NOT

Each Toffoli is replaced by the 15-gate circuit: two $H$ , six CNOTs and seven $T$ ⁠-type gates.

Worked example

A NOT with three controls

Use the construction above with $k = 3$ controls. First the example is worked for you; then you do $k = 5$ .

Parts
$2(k-1) = 4$ Toffolis and one CNOT, with $k - 1 = 2$ work qubits. With three controls and one target, that makes $3 + 2 + 1 = 6$ qubits.
T-count
Each Toffoli brings seven $T$ ⁠-type gates and the middle CNOT none: $4\times7 = 28$ .
CNOT count
Each Toffoli brings six CNOTs, and there is one more in the middle: $4\times6 + 1 = 25$ .
Your turn: Toffolis
Now take $k = 5$ controls.
Your turn
A NOT with 5 controls is built as in this lesson: Toffolis compute the AND of the controls into work qubits, a CNOT flips the target, and the Toffolis run again to uncompute. How many Toffoli gates does it use?
Hints
1. Compute uses $k - 1$ Toffolis, act uses one CNOT, uncompute repeats the $k - 1$ Toffolis. There are $k - 1$ work qubits.
2. Each Toffoli circuit has six CNOTs and seven $T$ ⁠-type gates.
Show the answer
Answer: $8$
$k - 1 = 4$ Toffolis compute the AND and the same number uncompute it: $2(k-1) = 8$ .
Common slips
- $4$ : That is the compute half only. The work qubits must return to $\ket0$ , so the same Toffolis run again in reverse: $2(k-1) = 8$ .
- $5$ : One Toffoli per control is one too many for the compute half (the first Toffoli takes two controls at once), and the uncompute half doubles it: $2(k-1) = 8$ .
Your turn: T-count
Your turn
A NOT with 5 controls is built as in this lesson: Toffolis compute the AND of the controls into work qubits, a CNOT flips the target, and the Toffolis run again to uncompute, and each Toffoli is replaced by the 15-gate circuit. How many $T$ ⁠-type gates ( $T$ or $T^\dagger$ ) does it use?
Hints
1. Compute uses $k - 1$ Toffolis, act uses one CNOT, uncompute repeats the $k - 1$ Toffolis. There are $k - 1$ work qubits.
2. Each Toffoli circuit has six CNOTs and seven $T$ ⁠-type gates.
Show the answer
Answer: $56$
There are $2(k-1) = 8$ Toffolis with seven $T$ ⁠-type gates each, and the middle CNOT has none: $7\times8 = 56$ .
Common slips
- $28$ : That is the compute half only. The work qubits must return to $\ket0$ , so the same Toffolis run again in reverse, which doubles the count: $7\times8 = 56$ .
- $32$ : That counts only the $T$ gates. Each Toffoli also has three $T^\dagger$ gates, which cost the same: seven $T$ ⁠-type gates per Toffoli.
- $8$ : That is the number of Toffolis, 8. Each one is replaced by a circuit with seven $T$ ⁠-type gates.

One more, fully worked, with $k = 4$ .

Another worked example

Another example: four controls

Parts
$2(k-1) = 6$ Toffolis and one CNOT, with $k - 1 = 3$ work qubits: $4 + 3 + 1 = 8$ qubits in all.
T-count
$6\times7 = 42$ $T$ ⁠-type gates.
CNOT count
$6\times6 + 1 = 37$ CNOTs. Compare the cheaper version: $2k - 3 = 5$ Toffolis, so $T$ ⁠-count 35 and 30 CNOTs, with two work qubits.

Check yourself

A NOT with 8 controls is built as in this lesson: Toffolis compute the AND of the controls into work qubits, a CNOT flips the target, and the Toffolis run again to uncompute. How many qubits in all, counting the controls, the work qubits and the target does it use?

Hints

Compute uses $k - 1$ Toffolis, act uses one CNOT, uncompute repeats the $k - 1$ Toffolis. There are $k - 1$ work qubits.
Each Toffoli circuit has six CNOTs and seven $T$ ⁠-type gates.

Show the answer

Answer: $16$

8 controls, $k - 1 = 7$ work qubits and one target: $8 + 7 + 1 = 16$ .

Common slips

$9$ : That leaves out the 7 work qubits.
$15$ : Count again: 8 controls, 7 work qubits and one target.

10 / 13 · Practice

Practice

Three items. The numbered ones change when they come back. Hints are there if you need them.

Check yourself

A circuit on three qubits applies these gates, in this order:

$H$ on $q_2$
a CNOT with control $q_2$ and target $q_1$
$H$ on $q_2$
a CNOT with control $q_0$ and target $q_1$
$T$ on $q_1$
$H$ on $q_1$

Gates on different qubits can run in the same layer. What is the depth of the circuit as written, without moving any gate past another?

Hints

Put each gate in the earliest layer that comes after every earlier gate on its wires.
A CNOT uses two wires: it waits for both, and later gates on either wire wait for it.

Show the answer

Answer: $5$

The layers of gates 1 to 6 are 1, 2, 3, 3, 4, 5, so the depth is 5. The CNOTs pass the delay from one wire to another, which is why the depth exceeds the 4 gates of the busiest wire.

Place the gates one at a time, each in the first layer after every earlier gate on its wires:

$H$ on $q_2$ : layer 1 (nothing earlier on its wires)
a CNOT with control $q_2$ and target $q_1$ : layer 2 (after gate 1)
$H$ on $q_2$ : layer 3 (after gate 2)
a CNOT with control $q_0$ and target $q_1$ : layer 3 (after gate 2)
$T$ on $q_1$ : layer 4 (after gate 4)
$H$ on $q_1$ : layer 5 (after gate 5)

The deepest layer is 5, so the depth is 5.

Common slips

$6$ : That counts the gates. Gates on different wires can share a layer, so the depth is smaller than the gate count here.
$4$ : That is the number of gates on the busiest wire. But a CNOT ties two wires together: a gate after it must wait for the gates before it on both wires. Follow the layers through the CNOTs.

Check yourself

Now the other way round: build a CNOT with its control on top from Hadamards and one controlled- $Z$ . A dot and a $Z$ in the same column make a CZ.

Build it in the circuit builder (gates: H, control, Z).

Hints

Which rewrite turns $Z$ into $X$ ?
$HZH = X$ : put $H$ on the bottom wire before and after the CZ.

Show the answer

One circuit that works: H on q1, then CZ q0→q1, then H on q1.

$HZH = X$ , so Hadamards on the bottom wire around a CZ give a CNOT whose target is the bottom wire. CZ is symmetric, so it doesn’t matter which wire gets the dot and which the $Z$ .

Check yourself

A circuit contains 5 Toffoli gates and, besides them, 9 $T$ gates and 2 CNOTs. You replace every Toffoli with the 15-gate circuit from this lesson. What is the $T$ ⁠-count (the number of $T$ and $T^\dagger$ gates) of the new circuit?

Hints

How many CNOTs and how many $T$ ⁠-type gates are in the 15-gate Toffoli circuit?
It has two $H$ , six CNOTs, and seven gates that are $T$ or $T^\dagger$ .

Show the answer

Answer: $44$

Each Toffoli brings seven $T$ ⁠-type gates: $7\times5 + 9 = 44$ .

Common slips

$29$ : That counts only the $T$ gates in each Toffoli. The three $T^\dagger$ gates cost the same as $T$ gates, so each Toffoli adds seven.
$35$ : That counts the Toffolis’ $T$ ⁠-type gates but leaves out the 9 $T$ gates the circuit already had.
$84$ : That counts every gate in each Toffoli circuit. Only seven of the fifteen are $T$ or $T^\dagger$ ; the rest are two $H$ and six CNOTs.

11 / 13 · Explain

Explain it

The set $\{H, T, \text{CNOT}\}$ is called universal, yet no circuit made from it equals the rotation $R_z(1)$ exactly. Explain what universal means here, and why no finite gate set can build every gate exactly.

Show a model answer

Universal means approximately: for any unitary and any accuracy $\epsilon > 0$ there is a circuit from the set within $\epsilon$ of it, and for one qubit the number of gates grows only like a power of $\log(1/\epsilon)$ ; modern methods need about $3\log_2(1/\epsilon)$ $T$ gates per rotation. Exactness is impossible by counting. With finitely many gate types there are finitely many circuits of each length, so all circuits together form a countable list. The gates form a continuum, already the rotations $R_z(\theta)$ with one for every real $\theta$ , and no countable list covers a continuum. So almost every gate, $R_z(1)$ among them, can be approached but never reached.

A good answer covers

Universal means every unitary can be approximated to any accuracy, not built exactly
Circuits from a finite gate set can be listed by length, so there are countably many
Gates form a continuum (for example $R_z(\theta)$ for every real $\theta$ ), so most are missing from the list
The cost of accuracy grows slowly, like a power of $\log(1/\epsilon)$

12 / 13 · Mastery check

Mastery check

Check yourself

A quantum computer offers only the gates $H$ , $T$ and CNOT, with as many extra work qubits as you like, and you may use as many gates as you need. Can circuits made from them build every single-qubit gate exactly?

AYes: with enough gates, each of them is built exactly
BNo, but each one can be approximated as closely as you like
CNo: the circuits reach only a few gates, such as $X$ , $Z$ and $S$
DNot even approximately: most gates are out of reach

Show the answer

Answer: B. No, but each one can be approximated as closely as you like

Circuits from $H$ , $T$ and CNOT, with as many extra work qubits as you like, can be listed by length, so there are only countably many, while every single-qubit gate form a continuum. So the answer is no, but the set is universal: every gate can be approximated to any accuracy, at a cost that grows slowly with the accuracy.

Why not the others

A. Universal means approximately. Circuits from a finite gate set can be listed, first those with one gate, then those with two, and so on: there are countably many. The gates you want form a continuum, which no list can cover. So most of them can be approached as closely as you like, but never reached.
C. They reach infinitely many. One product of $H$ and $T$ is a rotation by an angle that is an irrational fraction of a full turn, so its powers never repeat and come close to every rotation about its axis.
D. Every gate can be approximated to any accuracy you name. What fails is exactness: there are only countably many circuits, so most gates are approached, never reached.

Check yourself

A circuit applies $H$ , then $T$ , then $X$ to one qubit in the state $\ket\psi$ . Which product of matrices equals the whole circuit?

A $XTH$
B $H\otimes T\otimes X$
C $H + T + X$
D $HTX$

Hint

Which gate acts on $\ket\psi$ first, and where must it stand in the product?

Show the answer

Answer: A. $XTH$

$H$ acts first, so it sits next to the ket: $X\big(T(H\ket\psi)\big) = XTH\ket\psi$ . Time runs left to right in the circuit and right to left in the product.

Why not the others

B. A tensor product describes gates side by side on different qubits, and this one would be an $8\times8$ matrix. Gates one after another on the same qubit multiply.
C. Gates in sequence compose: each acts on the output of the one before, which makes a product, not a sum. A sum of unitary matrices is usually not even unitary.
D. That lists the gates in circuit order. The first gate acts on $\ket\psi$ first, so it stands next to the ket: $X\big(T(H\ket\psi)\big) = XTH\ket\psi$ . And the order matters here, since $HTX \ne XTH$ .

Check yourself

Which single gate equals the matrix product $SYS^\dagger$ , up to an overall phase?

A $X$
B $Y$
C $Z$
D $I$ , the identity

Hint

Apply the product to $\ket0$ and to $\ket1$ , one gate at a time, starting from the right.

Show the answer

Answer: A. $X$

On basis states: $SYS^\dagger\ket0 = S(i\ket1) = -\ket1$ and $SYS^\dagger\ket1 = SY(-i\ket1) = -iS(-i\ket0) = -\ket0$ . That is $-X$ , which is $X$ up to an overall sign.

Why not the others

B. $S$ and $S^\dagger$ don’t cancel: $Y$ sits between them, and $S$ doesn’t commute with $Y$ . $S$ turns the Bloch sphere a quarter turn about the $z$ axis, which carries the $y$ axis onto the $-x$ axis.
C. The product flips bits, which $Z$ never does: $SYS^\dagger\ket0 = SY\ket0 = S(i\ket1) = -\ket1$ .
D. Only adjacent $S$ and $S^\dagger$ cancel. Follow $\ket0$ : $SYS^\dagger\ket0 = SY\ket0 = S(i\ket1) = -\ket1$ . The product flips bits.

Check yourself

Two circuits compute the same thing. Circuit A has 5,000 gates, 400 of them $T$ gates. Circuit B has 3,000 gates, 1,500 of them $T$ gates. All the other gates are $H$ , $S$ or CNOT. Both will run on an error-corrected quantum computer. Which is likely to be cheaper to run?

ACircuit A
BCircuit B
CAbout the same, since they compute the same thing
DThere is no way to tell without running both

Show the answer

Answer: A. Circuit A

On an error-corrected machine $H$ , $S$ and CNOT are cheap and $T$ gates are expensive, so the $T$ ⁠-count decides. Circuit A has 400 $T$ gates against 1,500. Even at a modest ten to one, it costs about 8,600 units against 16,500, despite having more gates.

Why not the others

B. Circuit B has fewer gates, but 1,500 of them are $T$ gates, and on an error-corrected machine the $T$ gates dominate the cost. Even if a $T$ gate cost only ten times as much as each other gate, B would come to about 16,500 units against 8,600.
C. Cost belongs to the circuit, not to the job it does: two circuits for the same unitary can differ a lot. Here they differ in the gate that dominates the cost on an error-corrected machine, the $T$ gate.
D. The counts are enough for a good estimate. On an error-corrected machine $H$ , $S$ and CNOT are cheap and each $T$ gate costs many times more, so compare the $T$ ⁠-counts.

Check yourself

What is $\text{CZ}\,\ket-\ket1$ ? (CZ multiplies $\ket{11}$ by $-1$ and leaves the other basis states alone.)

A $\ket+\ket1$
B $\ket-\ket1$ , unchanged
C $\ket-\ket0$
D $-\ket-\ket1$

Hints

Write the input as a sum of two basis states.
Only the $\ket{11}$ term changes sign.

Show the answer

Answer: A. $\ket+\ket1$

Written out, the input is $\tfrac{1}{\sqrt2}(\ket{01} - \ket{11})$ . CZ changes the sign of $\ket{11}$ only, giving $\tfrac{1}{\sqrt2}(\ket{01} + \ket{11}) = \ket+\ket1$ . The top qubit changed, so for CZ the words control and target are only labels.

Why not the others

B. The top qubit is drawn as the control, but that only means it is never flipped on basis inputs. Here it is in a superposition, and the sign on $\ket{11}$ lands on its $\ket1$ branch, which turns $\ket+$ into $\ket-$ or back.
C. CZ never flips a bit: on basis states it only changes signs. The qubit in $\ket1$ stays $\ket1$ .
D. The minus sign goes on the $\ket{11}$ term only, not on both terms. Write the input out: $\tfrac{1}{\sqrt2}(\ket{01} - \ket{11})$ , and only the second term changes sign.

Check yourself

A circuit contains 3 Toffoli gates and, besides them, 10 $T$ gates and 11 CNOTs. You replace every Toffoli with the 15-gate circuit from this lesson. What is the $T$ ⁠-count (the number of $T$ and $T^\dagger$ gates) of the new circuit?

Hints

How many CNOTs and how many $T$ ⁠-type gates are in the 15-gate Toffoli circuit?
It has two $H$ , six CNOTs, and seven gates that are $T$ or $T^\dagger$ .

Show the answer

Answer: $31$

Each Toffoli brings seven $T$ ⁠-type gates: $7\times3 + 10 = 31$ .

Common slips

$22$ : That counts only the $T$ gates in each Toffoli. The three $T^\dagger$ gates cost the same as $T$ gates, so each Toffoli adds seven.
$21$ : That counts the Toffolis’ $T$ ⁠-type gates but leaves out the 10 $T$ gates the circuit already had.
$55$ : That counts every gate in each Toffoli circuit. Only seven of the fifteen are $T$ or $T^\dagger$ ; the rest are two $H$ and six CNOTs.

Check yourself

A circuit on three qubits applies these gates, in this order:

$T$ on $q_1$
$T$ on $q_1$
a CNOT with control $q_2$ and target $q_0$
a CNOT with control $q_1$ and target $q_0$
a CNOT with control $q_2$ and target $q_1$
$H$ on $q_2$

Gates on different qubits can run in the same layer. What is the depth of the circuit as written, without moving any gate past another?

Hints

Put each gate in the earliest layer that comes after every earlier gate on its wires.
A CNOT uses two wires: it waits for both, and later gates on either wire wait for it.

Show the answer

Answer: $5$

The layers of gates 1 to 6 are 1, 2, 1, 3, 4, 5, so the depth is 5. The CNOTs pass the delay from one wire to another, which is why the depth exceeds the 4 gates of the busiest wire.

Place the gates one at a time, each in the first layer after every earlier gate on its wires:

$T$ on $q_1$ : layer 1 (nothing earlier on its wires)
$T$ on $q_1$ : layer 2 (after gate 1)
a CNOT with control $q_2$ and target $q_0$ : layer 1 (nothing earlier on its wires)
a CNOT with control $q_1$ and target $q_0$ : layer 3 (after gate 2)
a CNOT with control $q_2$ and target $q_1$ : layer 4 (after gate 4)
$H$ on $q_2$ : layer 5 (after gate 5)

The deepest layer is 5, so the depth is 5.

Common slips

$6$ : That counts the gates. Gates on different wires can share a layer, so the depth is smaller than the gate count here.
$4$ : That is the number of gates on the busiest wire. But a CNOT ties two wires together: a gate after it must wait for the gates before it on both wires. Follow the layers through the CNOTs.

Check yourself

A NOT with 6 controls is built as in this lesson: Toffolis compute the AND of the controls into work qubits, a CNOT flips the target, and the Toffolis run again to uncompute, and each Toffoli is replaced by the 15-gate circuit. How many $T$ ⁠-type gates ( $T$ or $T^\dagger$ ) does it use?

Hints

Compute uses $k - 1$ Toffolis, act uses one CNOT, uncompute repeats the $k - 1$ Toffolis. There are $k - 1$ work qubits.
Each Toffoli circuit has six CNOTs and seven $T$ ⁠-type gates.

Show the answer

Answer: $70$

There are $2(k-1) = 10$ Toffolis with seven $T$ ⁠-type gates each, and the middle CNOT has none: $7\times10 = 70$ .

Common slips

$35$ : That is the compute half only. The work qubits must return to $\ket0$ , so the same Toffolis run again in reverse, which doubles the count: $7\times10 = 70$ .
$40$ : That counts only the $T$ gates. Each Toffoli also has three $T^\dagger$ gates, which cost the same: seven $T$ ⁠-type gates per Toffoli.
$10$ : That is the number of Toffolis, 10. Each one is replaced by a circuit with seven $T$ ⁠-type gates.

13 / 13 · Recap

Recap

From memory

Before reading the summary, write down what you remember. Pulling it back from memory is what makes it last.

A circuit applies $A$ , then $B$ , then $C$ . Write it as a matrix product, and state the four rewrites from this lesson.
Show the key points
- $CBA$ : the first gate stands next to the ket
- $HXH = Z$ and $HZH = X$
- Hadamards on both qubits turn a CNOT upside down
- $X$ before and after the control makes an anti-control
How is the Toffoli gate built from one- and two-qubit gates, and why does it need seven $T$ ⁠-type gates?
Show the key points
- $H$ on the target turns the flip into the sign $(-1)^{abc}$
- $4abc$ is a signed sum of seven parities, each a phase of $\pm\pi/4$ : four $T$ , three $T^\dagger$
- Six CNOTs place the parities; 15 gates in all
What does it mean that $\{H, T, \text{CNOT}\}$ is universal, and how do you price a circuit?
Show the key points
- Any unitary to any accuracy, but not exactly: countably many circuits, a continuum of gates
- About $3\log_2(1/\epsilon)$ $T$ gates per rotation; Solovay–Kitaev: a power of $\log(1/\epsilon)$
- Gate count, depth, two-qubit count, $T$ ⁠-count; move commuting gates to cut depth
- A $k$ ⁠-control NOT: $2(k-1)$ Toffolis and $k - 1$ work qubits, compute, act, uncompute

Key ideas

A circuit is a program whose matrix is the product of its gates in reverse order: $A$ , then $B$ , then $C$ is $CBA$ .
$HXH = Z$ , $HZH = X$ ; Hadamards on both qubits reverse a CNOT; $X$ around a control gives an anti-control. CZ is a CNOT with $H$ on the target, and it is symmetric.
The Toffoli gate is exactly two $H$ , six CNOTs and seven $T$ ⁠-type gates.
$\{H, T, \text{CNOT}\}$ is universal: it approximates any unitary to any accuracy, never all of them exactly. A rotation costs about $3\log_2(1/\epsilon)$ $T$ gates.
Gate count, depth, two-qubit count and $T$ ⁠-count measure different costs. Moving gates that commute can cut the depth.
A NOT with $k$ controls takes $2(k-1)$ Toffolis and $k - 1$ work qubits: compute, act, uncompute.

Go further

Free resources for when you want more than this lesson covers.

Fundamentals of quantum algorithms: Quantum algorithmic foundationsJohn Watrous, IBM Quantum · Course
Measures what a computation costs and how that grows with the input, with arithmetic, GCDs and factoring as the examples.
Quantum Computing: Lecture NotesRonald de Wolf · Lecture notes
Compact, free lecture notes that set up the circuit model and universal gate sets, then work through the main algorithms.
Solovay–Kitaev theoremWikipedia · Article
The exact statement, and how later proofs pushed the exponent c in the gate count down from 3.97 to below 1.5.
Clifford gatesWikipedia · Article
Why circuits of H, S and CNOT alone are easy to simulate classically, and why the T gate lies outside that set.

Math refreshers

The toolkit topics this lesson leans on.

Big-O and repeated trialsHow log n, √N, n, n² and 2ⁿ grow, and how repeating a test drives its failure chance down