Quantum Computing Study Guide

Classical vs Quantum Bits. A classical bit is 0 or 1 (represented by e.g. high/low voltage) 1 . A qubit
(quantum bit) is a quantum state that can be in 0, 1, or a superposition of both at once 2 . We write
qubit states using Dirac notation: e.g. $|0\rangle$ or $|1\rangle$ denote the computational basis
states 3 . These kets $|\psi\rangle$ correspond to column vectors; the dual bras $\langle\psi|$ are
row vectors 4 .

• Key fact: A general one-qubit state is $|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$ with

complex amplitudes $\alpha,\beta$ and normalization $|\alpha|^2+|\beta|^2=1$ 5 6 .

Superposition and Measurement. A qubit in superposition behaves like a probabilistic mixture only
upon measurement. If $|\psi\rangle=\alpha|0\rangle+\beta|1\rangle$, measuring it in the ${|
0\rangle,|1\rangle}$ basis yields outcome $|0\rangle$ with probability $|\alpha|^2$ and $|1\rangle$
with $|\beta|^2$ 6 . After measurement the state collapses to the observed basis state. For example,
a qubit in $|+\rangle=(|0\rangle+|1\rangle)/\sqrt2$ has a 50–50 chance of yielding 0 or 1 upon
measurement. In general, the probability formula is $$P(0)=|\alpha|^2,\quad P(1)=|\beta|^2,\quad (|
\alpha|^2+|\beta|^2=1)$$ for the normalized state $|\psi\rangle=\alpha|0\rangle+\beta|
1\rangle$ 6 .

Figure: The Bloch sphere represents single-qubit states. The north/south poles are $|0\rangle$/$|1\rangle$,
and other points represent superpositions. For instance, the equatorial axes $X,Y$ correspond to the states $|
+\rangle=(|0\rangle+|1\rangle)/\sqrt2$, $|-\rangle=(|0\rangle-|1\rangle)/\sqrt2$, and $(|0\rangle\pm i|
1\rangle)/\sqrt2$ 7 .

Bloch Sphere. Any pure one-qubit state corresponds to a point on the unit Bloch sphere 7 . The $Z$-
axis poles are the computational basis $|0\rangle$ and $|1\rangle$. The $X$-axis poles are the ${|+
\rangle,|-\rangle}$ states, and the $Y$-axis poles are $(|0\rangle\pm i|1\rangle)/\sqrt2$ 7 . Rotations
on the Bloch sphere correspond to single-qubit gates: e.g. the Pauli-$X$ gate flips north↔south, the
Hadamard ($H$) rotates from $Z$ to $X$ axes, etc.

Single-Qubit Gates. Quantum gates are unitary transformations (matrices) acting on qubit states 8

9 . Important examples (with their 2×2 matrices and actions):

• Pauli $X$ (NOT) gate: $X = \begin{pmatrix}0&1\1&0\end{pmatrix}$. It flips $|

0\rangle\leftrightarrow|1\rangle$ 8 10 .
• Pauli $Y$ gate: $Y = \begin{pmatrix}0&-i\i&0\end{pmatrix}$. It flips the bit and adds a phase:
$Y|0\rangle=i|1\rangle$, $Y|1\rangle=-i|0\rangle$ 10 .
• Pauli $Z$ gate: $Z = \begin{pmatrix}1&0\0&-1\end{pmatrix}$. It does no bit-flip but flips the
phase of $|1\rangle$ (i.e.\ $Z|0\rangle=|0\rangle$, $Z|1\rangle=-|1\rangle$) 10 .
• Hadamard ($H$) gate: $H = \frac{1}{\sqrt2}\begin{pmatrix}1&1\1&-1\end{pmatrix}$ 9 . It
maps basis states to equal superpositions: $$H|0\rangle = \frac{|0\rangle+|1\rangle}{\sqrt2}=|+
\rangle,\quad H|1\rangle = \frac{|0\rangle-|1\rangle}{\sqrt2}=|-\rangle.$$ It corresponds to a
180° rotation about the $(X+Z)/\sqrt2$ axis 9 11 .
• Phase ($S$) gate: $S = \begin{pmatrix}1&0\0&i\end{pmatrix}$ 12 . This is a $Z^{1/2}$ rotation:
$S|0\rangle=|0\rangle$, $S|1\rangle=i|1\rangle$ (90° phase on $|1\rangle$).
• Identity ($I$) gate: $I = \begin{pmatrix}1&0\0&1\end{pmatrix}$ does nothing to the state.

1
These single-qubit gates can be visualized as rotations on the Bloch sphere. For example, applying $X$
is a 180° rotation about the $X$-axis, and $H$ is a 180° rotation about the $(X+Z)/\sqrt2$ axis 11 .

Multi-Qubit Gates. Multi-qubit gates act on composite systems. For two qubits we work in a 4-
dimensional space spanned by ${|00\rangle,|01\rangle,|10\rangle,|11\rangle}$. A key two-qubit gate
is:

• Controlled-NOT (CNOT): One qubit is the control, the other the target. CNOT flips the target
($X$) only if the control is $|1\rangle$ 13 . Symbolically, $\mathrm{CNOT}|c,t\rangle = |c,
\,t\oplus c\rangle$. In the computational basis, CNOT maps $|10\rangle\to|11\rangle$, $|
11\rangle\to|10\rangle$, and leaves $|00\rangle,|01\rangle$ unchanged 13 .

For three qubits:

• Toffoli (CCNOT) gate: A three-qubit gate with two controls and one target (controlled-controlled-
NOT). It flips the third qubit if both the first two are $|1\rangle$; otherwise it does nothing 14 .
In effect, Toffoli implements the classical AND in the control, then flips the target bit. It is
universal for classical reversible computation.

For two qubits:

• SWAP gate: Exchanges two qubits. In the basis ${|00\rangle,|01\rangle,|10\rangle,|11\rangle}$

its matrix is $$\mathrm{SWAP} = \begin{pmatrix}
1&0&0&0\0&0&1&0\0&1&0&0\0&0&0&1\end{pmatrix},$$ swapping $|01\rangle\leftrightarrow|
10\rangle$ 15 .

Figure: Multi-qubit gates. (Left) The Toffoli (CCNOT) gate with two control qubits (black dots) and one target
(⊕). It flips the target if both controls are 1. (Right) The SWAP gate exchanging two qubits. These are examples
of 3-qubit and 2-qubit gates respectively 16 .

Tensor Products and Multi-Qubit States. A system of $n$ qubits has a $2^n$-dimensional state space.
For example, two qubits have four basis states ${|00\rangle,|01\rangle,|10\rangle,|11\rangle}$, so a
general two-qubit state is $$|\Psi\rangle = \alpha_{00}|00\rangle + \alpha_{01}|01\rangle +
\alpha_{10}|10\rangle + \alpha_{11}|11\rangle,$$ with $\sum|\alpha_{ij}|^2=1$ 17 . The composite
state $|\psi_{AB}\rangle$ of two independent systems $A,B$ is the tensor product $|
\psi_A\rangle\otimes|\phi_B\rangle$. Tensor products build multi-qubit states and multi-qubit gate
matrices (which are $2^n\times2^n$). Measurement on multi-qubits is done similarly: the probabilities
of outcomes are the squared norms of the respective amplitudes, and the state collapses to the
observed basis vector.

Entanglement and Bell States. Entanglement is a uniquely quantum correlation: entangled qubits
cannot be described separately. The simplest entangled two-qubit states are the Bell states, which are
maximally entangled. One Bell state is $$|\Phi^+\rangle = \frac{|00\rangle+|11\rangle}{\sqrt2},$$ and
the others are $|\Phi^-\rangle = (|00\rangle-|11\rangle)/\sqrt2$, $|\Psi^\pm\rangle=(|01\rangle\pm|
10\rangle)/\sqrt2$. In each Bell state the qubits are perfectly correlated: measuring one immediately
determines the other 18 19 . For example, in $|\Phi^+\rangle$ if Alice measures $0$ then Bob’s qubit is
guaranteed to be $0$ (and similarly for 1) 20 . These states form the Bell (EPR) basis of the two-qubit
space 18 21 . One way to generate a Bell state (e.g.\ $|\Phi^+\rangle$) from $|00\rangle$ is to apply
an $H$ on the first qubit and then a CNOT (first qubit controls second) 22 . This circuit yields $$|
00\rangle \xrightarrow{H_1} \frac{|0\rangle+|1\rangle}{\sqrt2}\otimes|0\rangle
\xrightarrow{\mathrm{CNOT}} \frac{|00\rangle+|11\rangle}{\sqrt2} = |\Phi^+\rangle.$$

2
Phase Kickback. Some quantum algorithms use the phase kickback trick. Normally, a controlled-$U$
gate affects only the target qubit. With phase kickback, a phase applied on the target qubit is “kicked
back” onto the control. For example, prepare an ancilla in $(|0\rangle+|1\rangle)/\sqrt2$, apply a
controlled-$Z$ or controlled-$U$ from the control to this ancilla; effectively a phase shift is added to the
control’s amplitude without directly acting on it. In words: “Phase kickback is a clever trick to add a phase
to a qubit without applying gates directly to it” 23 . Operationally one can do: start with $|0\rangle_{\rm
anc}$, apply $X$ then $H$ to make $|+\rangle$ on ancilla, then perform a controlled-$U$ with the data
qubit as control. After this sequence, a phase factor has been applied to the control’s state 24 . This is
crucial in algorithms like Deutsch-Jozsa or Grover, where the oracle’s effect appears as a phase on
superposed states.

Quantum Oracles. A quantum oracle is a “black-box” unitary encoding an unknown function $f$.
Formally, the oracle $U_f$ is a unitary that maps $$U_f: |x\rangle|y\rangle \mapsto |x\rangle|y\oplus
f(x)\rangle.$$ Thus it transforms the input register $|x\rangle$ together with a target bit $|y\rangle$
into $|f(x)\rangle$ on the target 25 . Because $U_f$ is unitary, it can also be viewed as adding a phase:
e.g.\ a phase oracle could map $|x\rangle\to (-1)^{f(x)}|x\rangle$. In any case, the oracle provides $f(x)$
without revealing it explicitly; our goal is to learn something about $f$ with as few oracle calls as
possible 25 .

Quantum Algorithms and Complexity. A quantum algorithm is a sequence of quantum gates and
measurements to solve a problem. Many quantum algorithms exploit superposition and entanglement
to evaluate many possibilities in parallel 26 . A famous example is the Deutsch–Jozsa (DJ) algorithm:
given an $n$-bit function promised either constant (all outputs equal) or balanced (half 0’s, half 1’s), DJ
determines which with one quantum query 27 , whereas any deterministic classical algorithm requires
on the order of $2^{n-1}+1$ queries in the worst case 27 . In other words, DJ achieves an exponential
query speedup. The DJ circuit starts with $n$ qubits in $|0\rangle$ and one ancilla $|1\rangle$, applies
Hadamards, the oracle $U_f$, and Hadamards again, and then measures: if all output bits are 0, $f$ is
constant; otherwise $f$ is balanced. Because of phase kickback and interference, this yields a
guaranteed answer with a single oracle use 27 .

More generally, quantum algorithms can offer polynomial or even exponential advantages. For search
problems, Grover’s algorithm finds a marked item among $N$ with $O(\sqrt{N})$ queries (quadratic
speedup over classical $O(N)$). For factoring, Shor’s algorithm factors an integer in polynomial time,
whereas the best known classical methods take sub-exponential time. In practice, “big-O” complexity
comparisons highlight these speedups: e.g. DJ goes from $O(2^n)$ classically down to $O(1)$
quantumly 27 .

Quantum computing power grows exponentially in the number of qubits 26 . A classical simulation of
$n$ qubits requires $2^n$ amplitudes. However, quantum algorithms exploit this Hilbert space
efficiently. In classical terms, algorithms often need many parallel evaluations; quantum superposition
does this in “one go” 26 . Thus quantum algorithms can handle large data sets and parallel
computations inherently. In summary, quantum complexity analysis compares the required number of
qubits and gates: an advantage is seen when a quantum algorithm has a lower big-$O$ than the best
classical counterpart 27 26 .

Quiz
1. (True/False) A qubit can be in states 0 and 1 simultaneously.
2. (MCQ) Which notation is used to denote a quantum state? A) ( ) B) ⟨ | C) |⟩ D) { }

3
 3. (Fill-in-the-blank) In Dirac notation, a ket like $|v\rangle$ represents a column vector, while its
dual $\langle v|$ is a ______.
4. (MCQ) What is the Bloch sphere? A) A way to physically build qubits; B) A representation of qubit
states as points on a sphere; C) A classical bit diagram; D) A quantum error-correction scheme.
5. (True/False) The probabilities $|\alpha|^2$ and $|\beta|^2$ of measuring $|0\rangle$ or $|
1\rangle$ from a state $\alpha|0\rangle+\beta|1\rangle$ sum to 1.
6. (MCQ) Which gate is represented by the matrix $\begin{pmatrix}0&1\1&0\end{pmatrix}$? A) $Z$
B) $H$ C) $X$ D) $S$
7. (MCQ) Which gate flips the phase of $|1\rangle$ (adds a -1 factor) but does nothing to $|
0\rangle$? A) $X$ B) $Y$ C) $Z$ D) $H$
8. (MCQ) The Hadamard gate $H$ transforms $|0\rangle$ into: A) $|0\rangle$ B) $|1\rangle$ C) $
(|0\rangle+|1\rangle)/\sqrt2$ D) $(|0\rangle-|1\rangle)/\sqrt2$.
9. (Fill-in-the-blank) Applying an $X$ gate to $|0\rangle$ yields ______.
10. (True/False) The S gate (phase gate) multiplies $|1\rangle$ by $i$ and leaves $|0\rangle$
unchanged.
11. (Match) Match each gate to its action on a single qubit:
◦ $X$ – ( ) flip bit
◦ $Z$ – ( ) add phase flip
◦ $H$ – ( ) create equal superposition
◦ $S$ – ( ) 90° phase rotation
12. (MCQ) Which of the following describes the CNOT gate? A) Swaps two qubits; B) Flips first qubit if
second is 1; C) Flips second qubit if first is 1; D) Flips both qubits always.
13. (True/False) A Toffoli (CCNOT) gate flips the third qubit if the first two qubits are |1〉.
14. (Fill-in) The SWAP gate applied to $|01\rangle$ yields _.
15. (MCQ) How many basis states does a 3-qubit system have? A) 2 B) 3 C) 6 D) 8.
16. (MCQ) Which state is entangled? A) $|00\rangle$ B) $(|01\rangle+|10\rangle)/\sqrt2$ C) $|
0\rangle|1\rangle$ D) $(|0\rangle+|1\rangle)/\sqrt2$.
17. (Fill-in) A Bell state is a maximally _ state of two qubits.
18. (True/False) Measuring one qubit of the Bell state $(|00\rangle+|11\rangle)/\sqrt2$ always
collapses the other to the same result.
19. (MCQ) In phase kickback, the phase is “kicked back” onto which qubit? A) The control qubit B)
The target qubit C) Neither D) Both equally.
20. (MCQ) A quantum oracle is best described as: A) A classical function lookup; B) An unknown
unitary that encodes a function; C) A communication protocol; D) A measurement procedure.
21. (True/False) The Deutsch–Jozsa algorithm can determine if a Boolean function is constant or
balanced with one quantum query.
22. (MCQ) Classically, determining if an unknown n-bit function is balanced or constant requires on
the order of: A) $O(1)$ B) $O(n)$ C) $O(2^n)$ D) $O(n^2)$ evaluations.
23. (Fill-in) In the Deutsch–Jozsa algorithm, after applying Hadamard gates and the oracle, the first
$n$ qubits are measured. The function is constant if the measurement yields all _.
24. (MCQ) Which algorithm demonstrates a quadratic speedup over classical search? A) Deutsch–
Jozsa B) Shor’s C) Grover’s D) Simon’s.
25. (True/False) The computational space of $n$ qubits is exponentially large (size $2^n$).
26. (Match) Match these statements:
◦ Classical computation – ( ) processes each input sequentially or in parallel as classical bits
◦ Quantum computation – ( ) can explore many inputs simultaneously via superposition.
27. (MCQ) In big-O terms, a problem that classically takes $O(2^n)$ but a quantum solution takes
$O(1)$ exhibits: A) Polynomial speedup B) Exponential speedup C) No speedup D) Quadratic
speedup.
28. (True/False) Quantum algorithms must always be faster than any classical algorithm.

4
29. (Fill-in) The probabilities of measuring outcomes from a quantum state are given by the squares
of the magnitudes of its ______.
30. (MCQ) In Dirac notation, the inner product $\langle \phi|\psi\rangle$ is a ______. A) Vector B)
Scalar C) Matrix D) Tensor.
31. (True/False) Applying two Hadamard gates in succession returns the qubit to its original state.
32. (MCQ) Which of these is NOT a Bell state? A) $(|00\rangle+|11\rangle)/\sqrt2$ B) $(|01\rangle-|
10\rangle)/\sqrt2$ C) $(|00\rangle-|11\rangle)/\sqrt2$ D) $(|01\rangle+|11\rangle)/\sqrt2$.
33. (MCQ) Which rotation on the Bloch sphere corresponds to the phase gate $Z$? A) 90° about Z B)
180° about X C) 180° about Z D) 90° about X.
34. (MCQ) The Pauli-Y gate has eigenvalues: A) {+1, -1} B) {+i, -i} C) {0, 1} D) {1, 1}.
35. (True/False) The SWAP gate can be implemented using three CNOT gates.
36. (MCQ) Measurement in the computational basis can give which result when applied to $|
\psi\rangle=\frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$? A) 0 with probability 1 B) 1 with probability
1 C) 0 or 1 with equal probability D) never collapses.
37. (Fill-in) The tensor product of $|0\rangle$ and $|+\rangle$ is $|0\rangle \otimes |+\rangle = |
0\rangle|+\rangle = \frac{1}{\sqrt2}(|00\rangle + |01\rangle)$. Fill in the blank: $\; |0\rangle|+
\rangle = \frac{1}{\sqrt2}(|_\,0\rangle + |_\,1\rangle).$
38. (MCQ) Which statement about entangled qubits is correct? A) Each qubit’s state can be described
independently. B) Measurement outcomes are uncorrelated. C) The overall state is a tensor
product of single-qubit states. D) Measurement of one qubit instantaneously affects the other.
39. (True/False) A constant function $f(x)$ on n bits can be either all-zeros or all-ones.
40. (Fill-in) In the Deutsch-Jozsa problem, the classical algorithm in the worst case requires about
$2^{_ -1}+1$ queries (fill in the blank).
41. (MCQ) Which gate sequence creates an entangled state from $|00\rangle$? A) X on qubit1;
CNOT B) H on qubit1; CNOT C) Z on qubit2; H on qubit1 D) H on both qubits.
42. (MCQ) What is the result of measuring one qubit of the maximally entangled pair $|\Psi^-
\rangle=(|01\rangle-|10\rangle)/\sqrt2$? A) Always 0 B) Always 1 C) Random 0 or 1, but the other
qubit is opposite D) None of the above.
43. (True/False) Oracle queries in quantum algorithms can sometimes be made in superposition to
evaluate multiple inputs at once.
44. (Fill-in) The SWAP gate swaps qubit states; it can be written as $I\otimes I + X\otimes X +
Y\otimes Y + Z\otimes Z$ all divided by ______.
45. (MCQ) Which basis states form the computational basis for two qubits? A) ${|0\rangle,|1\rangle}
$ B) ${|+\rangle,|-\rangle}$ C) ${|00\rangle,|01\rangle,|10\rangle,|11\rangle}$ D) ${|
00\rangle,|11\rangle}$.
46. (True/False) The identity matrix $I$ acting as a gate changes the qubit state to its orthogonal
complement.
47. (MCQ) Which of these statements is true about quantum gates? A) They are always 2×2 matrices.
B) They must be unitary (invertible). C) They always increase the number of qubits. D) They
collapse the wavefunction.
48. (Fill-in) After applying Hadamard to $|1\rangle$, the resulting state is $(|0\rangle _ |1\rangle)/
\sqrt2$ (fill in + or –).
49. (MCQ) The computational complexity class BQP stands for: A) Bounded-error Quantum
Polynomial time; B) Binary Quantum Protocol; C) Balanced Qubit Program; D) Base Quantum
Path.
50. (True/False) Applying a quantum algorithm cannot change the probability distribution of
measurement outcomes for any state.

5
Numerical Problems

State Vector Transformations

1. Problem. Apply the Pauli-$X$ gate to the state $|0\rangle = \begin{pmatrix}1\0\end{pmatrix}$.

What is the resulting state?

Solution. The $X$ matrix is $\begin{pmatrix}0&1\1&0\end{pmatrix}$. Acting on $|0\rangle = (1,0)^T$:

$$ X|0\rangle = \begin{pmatrix}0&1\1&0\end{pmatrix}\begin{pmatrix}1\0\end{pmatrix} =
\begin{pmatrix}0\cdot1 +1\cdot0 \ 1\cdot1 +0\cdot0\end{pmatrix} = \begin{pmatrix}0\1\end{pmatrix}. $
$
This is $|1\rangle$. So $X|0\rangle = |1\rangle$.

1. Problem. Apply the Hadamard gate $H=\frac1{\sqrt2}\begin{pmatrix}1&1\1&-1\end{pmatrix}$

to $|0\rangle$. Compute the new state.

Solution. Multiply $H$ by $|0\rangle=(1,0)^T$:

$$ H|0\rangle = \frac{1}{\sqrt2}\begin{pmatrix}1&1\1&-1\end{pmatrix}\begin{pmatrix}
1\0\end{pmatrix} = \frac{1}{\sqrt2}\begin{pmatrix}1\cdot1 +1\cdot0 \ 1\cdot1 +(-1)\cdot0\end{pmatrix}
= \frac{1}{\sqrt2}\begin{pmatrix}1\1\end{pmatrix} = \frac{|0\rangle+|1\rangle}{\sqrt2}. $$
So the result is $|+\rangle=(|0\rangle+|1\rangle)/\sqrt2$.

1. Problem. Let $|\psi\rangle = \frac{1}{\sqrt{3}}|0\rangle + \sqrt{\frac{2}{3}}|1\rangle$. What is

$Z|\psi\rangle$? (Pauli-$Z$ gate flips sign of $|1\rangle$.)

Solution. The $Z$ matrix is $\mathrm{diag}(1,-1)$. Acting on $|\psi\rangle = \begin{pmatrix}1/\sqrt3\

\sqrt{2/3}\end{pmatrix}$ yields:
$$ Z|\psi\rangle = \begin{pmatrix}1&0\0&-1\end{pmatrix}\begin{pmatrix}1/\sqrt3\
\sqrt{2/3}\end{pmatrix} = \begin{pmatrix}1/\sqrt3\ -\sqrt{2/3}\end{pmatrix} = \frac{1}{\sqrt3}|0\rangle -
\sqrt{\frac{2}{3}}|1\rangle. $$
Thus $Z|\psi\rangle = \frac{1}{\sqrt3}|0\rangle - \sqrt{\frac{2}{3}}|1\rangle$.

1. Problem. Compute $H|1\rangle$ where $H$ is Hadamard.

Solution. $|1\rangle=(0,1)^T$. Apply $H$:

$$ H|1\rangle = \frac{1}{\sqrt2}\begin{pmatrix}1&1\1&-1\end{pmatrix}\begin{pmatrix}
0\1\end{pmatrix} = \frac{1}{\sqrt2}\begin{pmatrix}0+1\0+(-1)\end{pmatrix} = \frac{1}
{\sqrt2}\begin{pmatrix}1\-1\end{pmatrix} = \frac{|0\rangle - |1\rangle}{\sqrt2} = |-\rangle. $$

1. Problem. Apply the phase ($S$) gate to $|\psi\rangle = |1\rangle$. Recall $S|1\rangle = i|
1\rangle$.

Solution. By definition, $S = \mathrm{diag}(1,i)$. So $S|1\rangle = i|1\rangle$. In vector form, $|

1\rangle=(0,1)^T$, so
$$ S|1\rangle = \begin{pmatrix}1&0\0&i\end{pmatrix}\begin{pmatrix}0\1\end{pmatrix} =
\begin{pmatrix}0\i\end{pmatrix} = i\begin{pmatrix}0\1\end{pmatrix} = i|1\rangle. $$

1. Problem. If $|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$, find the state after applying the
two-qubit gate $X \otimes Z$ to $|\psi\rangle\otimes|+\rangle$.

Solution. First write $|\psi\rangle\otimes|+\rangle = \alpha|0\rangle|+\rangle + \beta|1\rangle|+

\rangle$. The gate $X\otimes Z$ applies $X$ to the first qubit and $Z$ to the second. Thus:

6
$$ (X\otimes Z)(|\psi\rangle\otimes|+\rangle) = \alpha\,X|0\rangle \otimes Z|+\rangle \;+\; \beta\,X|
1\rangle \otimes Z|+\rangle. $$
Compute each piece: $X|0\rangle = |1\rangle$, $X|1\rangle = |0\rangle$. Also $|+\rangle=(|0\rangle+|
1\rangle)/\sqrt2$. Then $Z|+\rangle = \frac{1}{\sqrt2}(Z|0\rangle + Z|1\rangle) = \frac{1}{\sqrt2}(|
0\rangle - |1\rangle) = |-\rangle$. So:
$$ = \alpha\,|1\rangle|-\rangle \;+\; \beta\,|0\rangle|-\rangle = (\beta\,|0\rangle + \alpha\,|1\rangle)
\otimes |-\rangle. $$
Explicitly, $(\beta|0\rangle + \alpha|1\rangle)\otimes (|0\rangle-|1\rangle)/\sqrt2$.

1. Problem. Apply the 2-qubit CNOT gate (control=first qubit) to the state $|10\rangle$.

Solution. CNOT flips the second (target) qubit only if the first (control) qubit is 1 13 . Here the input is $|
1\rangle\otimes|0\rangle$. Since the control is $|1\rangle$, we flip the target: $|1,0\rangle \to |
1,1\rangle$. In vector form, if we label $|10\rangle$ (binary 2) and $|11\rangle$ (binary 3), CNOT maps
basis state 2 to basis state 3. Thus the output is $|11\rangle$.

1. Problem. Compute the result of the SWAP gate on $|01\rangle$.

Solution. SWAP exchanges the two qubits. So $|0\rangle|1\rangle$ becomes $|1\rangle|0\rangle = |

10\rangle$. In vector basis ($|01\rangle$ is the second basis vector, $|10\rangle$ is the third), the
matrix sends that vector to $|10\rangle$. Hence SWAP$|01\rangle = |10\rangle$.

1. Problem. Given $|\psi\rangle=\frac{1}{\sqrt5}(2|0\rangle + |1\rangle)$, apply the unitary $U =

\begin{pmatrix}0&-i\i&0\end{pmatrix}$ (which is the Pauli-$Y$ gate). Find $U|\psi\rangle$.

Solution. Write $|\psi\rangle = \begin{pmatrix}2/\sqrt5\1/\sqrt5\end{pmatrix}$. The matrix $U$ acts as:

$$ U|\psi\rangle = \begin{pmatrix}0&-i\i&0\end{pmatrix}\begin{pmatrix}2/\sqrt5\1/\sqrt5\end{pmatrix}
= \begin{pmatrix}0\cdot\frac{2}{\sqrt5} + (-i)\cdot\frac{1}{\sqrt5} \ i\cdot\frac{2}{\sqrt5} + 0\cdot\frac{1}
{\sqrt5}\end{pmatrix} = \begin{pmatrix}-\frac{i}{\sqrt5}\ \frac{2i}{\sqrt5}\end{pmatrix} = -\frac{i}
{\sqrt5}|0\rangle + \frac{2i}{\sqrt5}|1\rangle. $$
We can factor out $i$ if desired: $= i\big(-\frac{1}{\sqrt5}|0\rangle + \frac{2}{\sqrt5}|1\rangle\big)$.
Either expression is correct.

1. Problem. Apply $H\otimes H$ (Hadamard on both qubits) to the two-qubit state $|\phi\rangle =
|+\rangle|0\rangle$, where $|+\rangle=(|0\rangle+|1\rangle)/\sqrt2$.

Solution. First express $|\phi\rangle$: $$|\phi\rangle = \frac{1}{\sqrt2}(|0\rangle+|1\rangle)\otimes|

0\rangle = \frac{1}{\sqrt2}(|00\rangle+|10\rangle).$$ Now apply $H$ to each qubit: $H|0\rangle = |+
\rangle$, $H|1\rangle = |-\rangle$, and $H|0\rangle = |+\rangle$ as well for the second qubit. Thus:
$$ (H\otimes H)|00\rangle = H|0\rangle \otimes H|0\rangle = |+\rangle|+\rangle,\quad (H\otimes H)|
10\rangle = H|1\rangle \otimes H|0\rangle = |-\rangle|+\rangle. $$
So $$ (H\otimes H)|\phi\rangle = \frac{1}{\sqrt2}(|+\rangle|+\rangle + |-\rangle|+\rangle) = \frac{|+
\rangle\otimes|+\rangle + |-\rangle\otimes|+\rangle}{\sqrt2}. $$
We can simplify further: since $|+\rangle = (|0\rangle+|1\rangle)/\sqrt2$ and $|-\rangle = (|0\rangle-|
1\rangle)/\sqrt2$, the final state in the computational basis is $$ = \frac{1}{2}[(|0\rangle+|1\rangle)(|
0\rangle+|1\rangle) + (|0\rangle-|1\rangle)(|0\rangle+|1\rangle)]. $$ Expanding and simplifying yields
$|+\rangle|+\rangle$. (Either leaving in $|\pm\rangle$ form or expanded is acceptable.)

Probability Calculations

1. Problem. A qubit is in the state $|\psi\rangle = \sqrt{3/4}|0\rangle + \sqrt{1/4}|1\rangle$. What

is the probability of measuring $|0\rangle$ and $|1\rangle$?

7
Solution. We compare to $\alpha|0\rangle+\beta|1\rangle$. Here $\alpha=\sqrt{3/4}=\sqrt{0.75}$ and
$\beta=\sqrt{1/4}=0.5$. The probabilities are $|\alpha|^2$ and $|\beta|^2$. Compute:
$$ P(0) = |\alpha|^2 = \frac{3}{4}, \quad P(1)=|\beta|^2=\frac{1}{4}. $$
Indeed, $P(0)+P(1)=1$. So $75\%$ chance of outcome $0$, $25\%$ chance of $1$.

1. Problem. If $|\psi\rangle = \tfrac{\sqrt{2}}{2}|0\rangle + i\tfrac{\sqrt{2}}{2}|1\rangle$, what are

the measurement probabilities?

Solution. Here $\alpha=\frac{\sqrt2}{2}$ and $\beta = i\frac{\sqrt2}{2}$. Compute magnitudes: $|

\alpha|^2 = (\frac{\sqrt2}{2})^2 = \frac12$. Also $|\beta|^2 = |i\frac{\sqrt2}{2}|^2 = (\frac{\sqrt2}{2})^2
= \frac12$ (the phase $i$ doesn’t affect probability). So $P(0)=1/2$, $P(1)=1/2$.

1. Problem. State $|\phi\rangle = a|0\rangle + b|1\rangle$ satisfies $a+b=0$ and normalization.

Write $a,b$ and compute $P(0), P(1)$.

Solution. From $a+b=0$ we have $b=-a$. Normalization requires $|a|^2+|b|^2=|a|^2+|{-a}|^2=2|a|

^2=1$, so $|a|=1/\sqrt2$. Thus $a=1/\sqrt2$ (up to a global phase) and $b=-1/\sqrt2$. The state is $(|
0\rangle - |1\rangle)/\sqrt2 = |-\rangle$. Then $P(0)=|a|^2=1/2$, $P(1)=|b|^2=1/2$.

1. Problem. Given the normalized 3-qubit state $|\Psi\rangle = \frac{1}{\sqrt{8}}(2|000\rangle + 2|

011\rangle + 2|101\rangle + 2|110\rangle)$, find the probability of measuring $|011\rangle$.

Solution. First check normalization: the amplitudes are $2/\sqrt8 = \sqrt{2}/2$ for each of the listed
basis states. There are four terms each with amplitude $2/\sqrt8$. Indeed $4 \times (2/\sqrt8)^2 = 4
\times (4/8) = 2$, which indicates something is off since normalization should give 1. Let’s compute
carefully: $|\Psi\rangle = \frac{1}{\sqrt8}(2|000\rangle + 2|011\rangle + 2|101\rangle + 2|110\rangle)$.
Factor out 2: $|\Psi\rangle = \frac{2}{\sqrt8}(|000\rangle+|011\rangle+|101\rangle+|110\rangle)$ and
$\frac{2}{\sqrt8} = \sqrt{\frac{4}{8}} = \sqrt{\frac{1}{2}} = 1/\sqrt{2}$. So effectively $|\Psi\rangle =
\frac{1}{\sqrt2}(|000\rangle+|011\rangle+|101\rangle+|110\rangle)$, which is not normalized because
it has 4 terms. Actually the given expression with prefactor $1/\sqrt8$ is normalized. To avoid confusion,
use the given amplitudes directly: the coefficient of $|011\rangle$ is $2/\sqrt8 = 1/\sqrt{2}$. Probability
$P(011) = |1/\sqrt{2}|^2 = 1/2$.

1. Problem. A system is in state $|\chi\rangle = \frac{3}{5}|1\rangle + \frac{4}{5}|0\rangle$ (note:

not normalized). First normalize it, then compute the probability of $|0\rangle$.

Solution. The given state has raw amplitudes $3/5$ for $|1\rangle$ and $4/5$ for $|0\rangle$.
Compute its norm: $|3/5|^2 + |4/5|^2 = 9/25 + 16/25 = 25/25 = 1$. It is already normalized. So $P(0) = |
4/5|^2 = 16/25 = 0.64$, and $P(1) = 9/25 = 0.36$.

1. Problem. The qubit $|\theta\rangle = \cos\theta\,|0\rangle + \sin\theta\,|1\rangle$. For $

\theta=30^\circ$, what are $P(0)$ and $P(1)$?

Solution. Substitute $\theta=30^\circ$. Then $\cos30^\circ=\sqrt3/2$, $\sin30^\circ=1/2$. Thus $|

\theta\rangle = \frac{\sqrt3}{2}|0\rangle + \frac{1}{2}|1\rangle$. Then $P(0)=|\sqrt3/2|^2 = 3/4=0.75$,
and $P(1)=|1/2|^2 = 1/4=0.25$.

1. Problem. A two-qubit state is $|\Psi\rangle=\frac{1}{2}(|00\rangle+|01\rangle+|10\rangle+|

11\rangle)$. What is the probability that measuring both qubits yields $|10\rangle$?

8
Solution. The amplitude of $|10\rangle$ is $1/2$. So $P(10) = |1/2|^2 = 1/4 = 0.25$. (All four basis
states have equal amplitude $1/2$, each with probability $1/4$.)

1. Problem. Suppose a qubit has state vector $\begin{pmatrix}\frac{i}{\sqrt{2}}\ \frac{1}{\sqrt{2}}

\end{pmatrix}$. What is the probability of measuring 0?

Solution. The state is $|\psi\rangle = \frac{i}{\sqrt{2}}|0\rangle + \frac{1}{\sqrt{2}}|1\rangle$.

Probability of $|0\rangle$ is $|\frac{i}{\sqrt{2}}|^2 = \frac{1}{2}$. (Magnitude of $i/\sqrt{2}$ is
$1/\sqrt{2}$, squaring gives $1/2$.)

1. Problem. A 3-qubit state is $|\Phi\rangle = a|100\rangle + b|111\rangle$. If $a$ and $b$ are
real, normalized, and $a=b$, find the probability of $|111\rangle$.

Solution. Since only two basis states appear, normalization requires $|a|^2 + |b|^2 = 1$. With $a=b$
real, we have $2a^2=1$, so $a=b=1/\sqrt2$. Then the probability of $|111\rangle$ is $|b|^2 = 1/2$.

1. Problem. A qubit is in a mixed (ensemble) state with 70% chance of $|0\rangle$ and 30% chance
of $|1\rangle$. What is its density matrix $\rho$?

Solution. A classical probabilistic mixture is not a pure state, but its density matrix is $$ \rho = 0.7\,|
0\rangle\langle0| + 0.3\,|1\rangle\langle1| = \begin{pmatrix}0.7&0\0&0.3\end{pmatrix}. $$
This represents the mixed ensemble (70% $|0\rangle$, 30% $|1\rangle$).

Tensor Products and Multi-Qubit Operations

1. Problem. Compute the tensor product $|0\rangle \otimes |1\rangle$.

Solution. By definition $|0\rangle\otimes|1\rangle = |01\rangle$. In vector form $|0\rangle=(1,0)^T$,

$|1\rangle=(0,1)^T$, so $$ |0\rangle\otimes|1\rangle = \begin{pmatrix}1\0\end{pmatrix} \otimes
\begin{pmatrix}0\1\end{pmatrix} = \begin{pmatrix}1\cdot0\1\cdot1\0\cdot0\0\cdot1\end{pmatrix} =
\begin{pmatrix}0\1\0\0\end{pmatrix}, $$ which corresponds to $|01\rangle$.

1. Problem. Given two states $|\phi\rangle = |+\rangle$ and $|\psi\rangle = |-\rangle$ for single
qubits, write the two-qubit state $|\Phi\rangle = |\phi\rangle \otimes |\psi\rangle$ in the
computational basis.

Solution. We have $|\phi\rangle = |+\rangle = (|0\rangle+|1\rangle)/\sqrt2$, and $|\psi\rangle=|-

\rangle=(|0\rangle-|1\rangle)/\sqrt2$. Then $$ |\Phi\rangle = |+\rangle \otimes |-\rangle = \frac{1}
{\sqrt2}(|0\rangle+|1\rangle)\otimes \frac{1}{\sqrt2}(|0\rangle - |1\rangle) = \frac{1}{2}\Bigl(|0\rangle(|
0\rangle-|1\rangle)+|1\rangle(|0\rangle-|1\rangle)\Bigr). $$
Expanding: $$ = \frac{1}{2}(|00\rangle - |01\rangle + |10\rangle - |11\rangle). $$

1. Problem. Calculate $(H\otimes I)(|0\rangle \otimes |+\rangle)$, where $H$ acts on the first
qubit and $I$ is identity on the second.

Solution. First write the input: $|0\rangle\otimes|+\rangle = \frac{1}{\sqrt2}(|0\rangle|0\rangle + |

0\rangle|1\rangle)$. Apply $H$ on the first qubit (and do nothing to the second):
$$ H|0\rangle = |+\rangle = \frac{|0\rangle+|1\rangle}{\sqrt2}. $$
So $$ (H\otimes I)\bigl(|0\rangle|0\rangle\bigr) = |+\rangle|0\rangle,\quad (H\otimes I)\bigl(|0\rangle|
1\rangle\bigr) = |+\rangle|1\rangle. $$

9
Thus $$ (H\otimes I)(|0\rangle|+\rangle) = \frac{1}{\sqrt2}\bigl(|+\rangle|0\rangle + |+\rangle|
1\rangle\bigr) = |+\rangle \otimes \frac{|0\rangle + |1\rangle}{\sqrt2} = |+\rangle \otimes |+\rangle. $$

1. Problem. For three qubits, what is $|0\rangle \otimes |+\rangle \otimes |1\rangle$ expressed
as a sum of basis states?

Solution. Write each factor: $|0\rangle$, $|+\rangle = (|0\rangle+|1\rangle)/\sqrt2$, and $|1\rangle$.

Then: $$ |0\rangle\otimes|+\rangle\otimes|1\rangle = \frac{1}{\sqrt2}(|0\rangle\otimes(|0\rangle+|
1\rangle)\otimes|1\rangle) = \frac{1}{\sqrt2}(|0,0,1\rangle + |0,1,1\rangle). $$
So the state is $\frac{|001\rangle + |011\rangle}{\sqrt2}$.

1. Problem. Compute the tensor product of matrices: $(X\otimes Z)$, where $X=\begin{pmatrix}
0&1\1&0\end{pmatrix}$ and $Z=\begin{pmatrix}1&0\0&-1\end{pmatrix}$.

Solution. The tensor product $X\otimes Z$ is a 4×4 matrix. Compute blockwise:

$$ X\otimes Z = \begin{pmatrix}0\cdot Z & 1\cdot Z \ 1\cdot Z & 0\cdot Z\end{pmatrix} =
\begin{pmatrix}0&0&1&0\0&0&0&-1\1&0&0&0\0&-1&0&0\end{pmatrix}. $$
More stepwise: $X\otimes Z$ acts on basis $|00\rangle,|01\rangle,|10\rangle,|11\rangle$ as follows:
$X$ swaps 0↔1 of first qubit, $Z$ flips phase of second qubit’s $|1\rangle$. The matrix above encodes
that action.

1. Problem. Evaluate $(|+\rangle\langle+|) \otimes (|-\rangle\langle -|)$ as a 4×4 matrix (using $|+
\rangle=(|0\rangle+|1\rangle)/\sqrt2$, $|-\rangle=(|0\rangle-|1\rangle)/\sqrt2$).

Solution. First $|+\rangle\langle+| = \frac12\begin{pmatrix}1&1\1&1\end{pmatrix}$ and $|-

\rangle\langle -| = \frac12\begin{pmatrix}1&-1\-1&1\end{pmatrix}$. The tensor product is $$ (|+
\rangle\langle+|)\otimes(|-\rangle\langle-|) = \frac{1}{4}\begin{pmatrix}1&1\1&1\end{pmatrix}
\otimes\begin{pmatrix}1&-1\-1&1\end{pmatrix}. $$
Taking tensor product yields a 4×4 matrix (block by block):
$$ = \frac{1}{4}\begin{pmatrix}1\cdot\begin{pmatrix}1&-1\-1&1\end{pmatrix} & 1\cdot\begin{pmatrix}
1&-1\-1&1\end{pmatrix} \[3pt] 1\cdot\begin{pmatrix}1&-1\-1&1\end{pmatrix} & 1\cdot\begin{pmatrix}
1&-1\-1&1\end{pmatrix} \end{pmatrix}. $$
Which simplifies to $$ \frac{1}{4}\begin{pmatrix}1&-1&1&-1\ -1&1&-1&1\ 1&-1&1&-1\
-1&1&-1&1\end{pmatrix}. $$

1. Problem. Calculate the tensor product of three one-qubit gates: $H \otimes X \otimes I$, where
$H=\frac1{\sqrt2}\begin{pmatrix}1&1\1&-1\end{pmatrix}$, $X=\begin{pmatrix}
0&1\1&0\end{pmatrix}$, and $I$ is $2\times2$ identity. Write the size of the resulting matrix.

Solution. The tensor product $H\otimes X \otimes I$ acts on three qubits, so it yields an $8\times8$
matrix (since each single-qubit is $2\times2$, three of them give $2^3=8$ dimension). The explicit
matrix can be computed by $H\otimes X$ first (4×4) and then $\otimes I$ (8×8), but the question only
asks for the size. So the result is an $8\times8$ unitary.

1. Problem. If $|\alpha\rangle=(1/\sqrt2)(|00\rangle - |11\rangle)$ and $|\beta\rangle=(1/\sqrt2)(|

01\rangle + |10\rangle)$, compute $\langle \alpha|\beta\rangle$.

Solution. Compute the inner product term by term. We have $$ \langle \alpha|\beta\rangle = \frac{1}
{2}(\langle00| - \langle11|)(|01\rangle + |10\rangle). $$

10
Expand: $\langle00|01\rangle=0$, $\langle00|10\rangle=0$, $\langle11|01\rangle=0$, $\langle11|
10\rangle=0$. All cross terms are orthogonal. Thus $\langle\alpha|\beta\rangle=0$.

1. Problem. A two-qubit system is in $|\Psi\rangle = (|00\rangle+|01\rangle+|10\rangle)/\sqrt3$.

Write this state as a tensor product of qubit states (if possible).

Solution. Attempt to factor: $|\Psi\rangle = \frac{1}{\sqrt3}(|00\rangle+|01\rangle+|10\rangle)$. Check

if it factors as $(a|0\rangle + b|1\rangle)\otimes(c|0\rangle + d|1\rangle)$. If it were separable,
amplitudes would factor: $ac|00\rangle + ad|01\rangle + bc|10\rangle + bd|11\rangle$. But here the
coefficient of $|11\rangle$ is 0, which would force either $a=0$ or $d=0$. That would also force one of
the other amplitudes to 0, which does not match this state. Therefore it cannot be written as a tensor
product of single-qubit states (the state is entangled).

1. Problem. Given $|\phi_1\rangle = |0\rangle + |1\rangle$ (unnormalized) and $|\phi_2\rangle =

2|0\rangle - |1\rangle$, compute $|\phi_1\rangle \otimes |\phi_2\rangle$.

Solution. First note $|\phi_1\rangle = (1,1)^T$ and $|\phi_2\rangle = (2,-1)^T$. The tensor product is $$
(|0\rangle+|1\rangle)\otimes (2|0\rangle - |1\rangle) = 1\cdot2\,|00\rangle + 1\cdot(-1)\,|01\rangle +
1\cdot2\,|10\rangle + 1\cdot(-1)\,|11\rangle. $$
In expanded vector form: $\begin{pmatrix}2\-1\2\-1\end{pmatrix}$ corresponding to $2|00\rangle -|
01\rangle +2|10\rangle -|11\rangle$. (We did not normalize anything since states were unnormalized.)

Gate Matrix Multiplication

1. Problem. Calculate the product of the single-qubit gates $HX$ (apply $X$ then $H$).

Solution. Compute $H\cdot X$, where $$H=\frac1{\sqrt2}\begin{pmatrix}1&1\1&-1\end{pmatrix},\;

X=\begin{pmatrix}0&1\1&0\end{pmatrix}.$$
Multiply:
$$ H X = \frac1{\sqrt2}\begin{pmatrix}1&1\1&-1\end{pmatrix}\begin{pmatrix}0&1\1&0\end{pmatrix} =
\frac1{\sqrt2}\begin{pmatrix}1\cdot0 + 1\cdot1 & 1\cdot1 + 1\cdot0\ 1\cdot0 + (-1)\cdot1 & 1\cdot1 +
(-1)\cdot0\end{pmatrix} = \frac1{\sqrt2}\begin{pmatrix}1 & 1\ -1 & 1\end{pmatrix}. $$
This matrix equals $\begin{pmatrix}1&1\-1&1\end{pmatrix}/\sqrt2$. For interpretation, note $HX =
(H\otimes I)(X \otimes I)$ etc.

1. Problem. Find the matrix for the gate sequence $Z H$ (apply $H$ then $Z$).

Solution. Compute $Z H$, with $Z=\begin{pmatrix}1&0\0&-1\end{pmatrix}$, $H$ as above. Then:

$$ ZH = \begin{pmatrix}1&0\0&-1\end{pmatrix}\frac{1}{\sqrt2}\begin{pmatrix}1&1\1&-1\end{pmatrix} =
\frac{1}{\sqrt2}\begin{pmatrix}1&1\ -1 & 1\end{pmatrix}. $$
Interestingly, $ZH$ gives the same matrix as $HX$ found above (because $ZH = -HX$ up to a global
phase of $-1$).

1. Problem. Compute the product $(H \otimes H)(H \otimes H)$.

Solution. Since $H$ is Hermitian and unitary ($H^2 = I$), we have $(H\otimes H)(H\otimes H) =
(H^2)\otimes(H^2) = I\otimes I$. Thus the result is the $4\times4$ identity.

1. Problem. Verify that $X^2 = I$ and compute $Y^2$, where $Y=\begin{pmatrix}0&-

i\i&0\end{pmatrix}$.

Solution. For $X=\begin{pmatrix}0&1\1&0\end{pmatrix}$, $X^2 = \begin{pmatrix}

0&1\1&0\end{pmatrix}^2 = I$. For $Y$:

11
$$ Y^2 = \begin{pmatrix}0&-i\i&0\end{pmatrix}^2 = \begin{pmatrix}-i\cdot i & 0\ 0 & i\cdot(-i)
\end{pmatrix} = \begin{pmatrix}(-i i)&0\0&(-i i)\end{pmatrix} = \begin{pmatrix}-i^2 &0\0&-
i^2\end{pmatrix} = \begin{pmatrix}-(-1)&0\0&-(-1)\end{pmatrix} = \begin{pmatrix}
1&0\0&1\end{pmatrix} = I. $$
So $X^2=I$ and $Y^2=I$.

1. Problem. If $S = \begin{pmatrix}1&0\0&i\end{pmatrix}$ and $T=\begin{pmatrix}1&0\0&e^{i\pi/

4}\end{pmatrix}$, compute $S^2$ and check it equals $Z$.

Solution. $S^2 = \begin{pmatrix}1&0\0&i\end{pmatrix}^2 = \begin{pmatrix}1^2&0\0&i^2\end{pmatrix}

= \begin{pmatrix}1&0\0&-1\end{pmatrix} = Z$. So indeed $S^2 = Z$. Also $T^2 = \begin{pmatrix}
1&0\0&e^{i\pi/4}\end{pmatrix}^2 = \begin{pmatrix}1&0\0&e^{i\pi/2}\end{pmatrix} = \begin{pmatrix}
1&0\0&i\end{pmatrix} = S$.

1. Problem. Multiply the 2-qubit CNOT (control=first, target=second) with itself. What is
$U_{\text{CNOT}}^2$?

Solution. The CNOT gate is its own inverse (applying it twice returns to the original state). Algebraically,
for all basis states $|c,t\rangle$, applying CNOT twice flips the target qubit if control is 1 twice, which
has no net effect. So $U_{\text{CNOT}}^2 = I_{4\times4}$ (the 4×4 identity).

1. Problem. Let $A = \frac{1}{\sqrt2}(X+Z)$ (a rotation) and $B = H$. Compute $AB$ and $BA$. Are
they the same?

Solution. First write $A = \frac{1}{\sqrt2}(\begin{pmatrix}0&1\1&0\end{pmatrix} + \begin{pmatrix}

1&0\0&-1\end{pmatrix}) = \frac{1}{\sqrt2}\begin{pmatrix}1&1\1&-1\end{pmatrix} = H$. Thus $A = H$. So
$AB = HH = H^2 = I$ and $BA = HH = I$. They are the same because here $A=B=H$.

1. Problem. Consider two-qubit gates $U = H \otimes X$ and $V = X \otimes H$. Compute $UV$
(8×8 matrix) in principle and describe whether $U$ and $V$ commute.

Solution. $U$ applies $H$ to qubit 1 and $X$ to qubit 2; $V$ does $X$ on qubit 1 and $H$ on qubit 2. In
general, $U$ and $V$ do not commute because operations on different qubits do commute (indeed
$H_1 X_2$ commutes with $X_1 H_2$), but careful: $(H \otimes X)(X \otimes H) = (H X)\otimes (X H) =
I\otimes I = I$ (since $HX = -ZH$ and $XH = HX$ up to phase). Actually computing shows that $(H
\otimes X)(X \otimes H) = (HX)\otimes (XH)$ and $(X \otimes H)(H \otimes X) = (XH)\otimes (HX)$. Since
$HX = -ZH$ but $HX \neq XH$, in fact $U$ and $V$ do not necessarily commute in general. (One can
verify by applying to basis states that $UV \neq VU$.)

1. Problem. A gate $G$ has matrix $\begin{pmatrix}0&1\-1&0\end{pmatrix}$. Is this unitary?

Compute $GG^\dagger$.

Solution. First compute $G G^\dagger$. We have $G = \begin{pmatrix}0&1\-1&0\end{pmatrix}$, so

$G^\dagger = \begin{pmatrix}0&-1\1&0\end{pmatrix}$ (complex conjugate transpose, but entries are
real). Multiply: $$ G G^\dagger = \begin{pmatrix}0&1\-1&0\end{pmatrix}\begin{pmatrix}
0&-1\1&0\end{pmatrix} = \begin{pmatrix}1&0\0&1\end{pmatrix} = I. $$
Also $G^\dagger G = I$. Thus $G$ is unitary. (In fact $G = -iY$, which is unitary up to global phase.)

1. Problem. Verify that the Toffoli gate is self-inverse (i.e.\ $U_{\rm Toffoli}^2=I$) by reasoning.

Solution. The Toffoli gate flips the target qubit if the two controls are 1. Applying it twice flips the target
twice when the controls are 1, which returns it to the original bit. If either control is 0, Toffoli does

12
nothing both times. Thus in either case, two applications do nothing overall, so $U_{\rm Toffoli}^2 =
I_{8\times8}$.

Complexity and Big-O Comparisons

1. Problem. If a classical search algorithm takes $O(N)$ time on $N$ items and Grover’s quantum
algorithm takes $O(\sqrt N)$ time, compare the complexities for $N=10^6$.

Solution. For $N=10^6$, classical is $O(10^6)$ operations (on the order of a million). Grover’s is
$O(\sqrt{10^6}) = O(10^3)$ (on the order of a thousand). Thus the quantum method is about 1000 times
faster in scaling.

1. Problem. A classical algorithm scales as $O(n^2)$, and a quantum algorithm for the same
problem scales as $O(n\log n)$. For $n=1024$, approximate how many times faster the quantum
algorithm is asymptotically.

Solution. $n=1024$. Classical time $\sim 1024^2 = 1{,}048{,}576$. Quantum time $\sim 1024 \cdot
\log_2 1024 = 1024 \cdot 10 = 10{,}240$. The ratio (classical/quantum) is about $1{,}048{,}576/10{,}240
\approx 102.4$. So asymptotically, the quantum algorithm is on the order of 100 times faster for this
size.

1. Problem. The best classical algorithm for a problem is $O(2^{n})$, while a quantum algorithm
solves it in $O(n^2)$. At $n=10$, how many fewer operations does the quantum algorithm use
(big-O sense)?

Solution. For $n=10$, classical $O(2^{10}) = 1024$. Quantum $O(10^2) = 100$. So roughly the quantum
needs an order of magnitude (10×) fewer operations (1024 vs 100). In big-O terms, that’s roughly a 10×
improvement at this $n$.

1. Problem. Suppose a classical brute-force algorithm for a problem requires $\Theta(3^n)$ steps,
and a quantum heuristic solves it in $\Theta(n^2)$ steps. Compare growth for $n=5$.

Solution. For $n=5$, classical $\sim 3^5=243$ steps. Quantum $\sim 5^2=25$ steps. So the quantum
algorithm uses roughly 10× fewer steps at $n=5$. Extrapolating, classical grows exponentially (factor 3
each step), while quantum is polynomial.

1. Problem. If a quantum algorithm requires one query to an oracle (constant time), and a classical
deterministic algorithm requires $2^{n-1}+1$ queries, what is the big-O speedup (in terms of
$n$)?

Solution. Classical queries are $\Theta(2^{n})$ (exponential in $n$). Quantum queries are $\Theta(1)$
(constant). Thus the speedup is exponential: from $O(2^n)$ down to $O(1)$ 27 .

1. Problem. An $n$-qubit quantum register can represent $2^n$ states simultaneously. How does
the size of Hilbert space grow compared to $n$?

Solution. The dimension is $2^n$, which is exponential in $n$. In contrast, $n$ itself grows linearly. So
the quantum state space grows exponentially with the number of qubits 28 .

1. Problem. Compare the complexity: Classical $O(n\log n)$ versus quantum $O(\sqrt{n})$. For
$n=1024$, which is asymptotically larger?

13
Solution. $n=1024$. Classical $n\log n \approx 1024\times10 = 10{,}240$. Quantum $\sqrt{n} = 32$.
Clearly $10{,}240$ is much larger than $32$. So classical has higher complexity in this example.

1. Problem. If a quantum algorithm runs in $O(n)$ time and a classical one in $O(n^2)$, what is the
comparative growth factor as $n$ increases?

Solution. As $n$ grows, the classical $O(n^2)$ grows much faster than the quantum $O(n)$. For
example, doubling $n$ quadruples the classical time but only doubles the quantum time. Hence the
quantum algorithm scales much better (linear vs quadratic).

1. Problem. Given two algorithms: A is classical with runtime $T_A(n)=5n^2$, and B is quantum
with $T_B(n)=100n$. For which $n$ does B outperform A?

Solution. Solve $5n^2 = 100n$ for equality: $5n^2-100n=0 \implies n(5n-100)=0$. Aside from $n=0$,
$5n=100$, so $n=20$. For $n>20$, $5n^2>100n$ (classical is larger), so the quantum ($100n$) is faster
for $n>20$.

1. Problem. Compare growth: classical $O(2^{n/2})$ versus quantum $O(2^{n/4})$. Which grows
slower as $n$ increases?

Solution. $2^{n/4}$ is much smaller than $2^{n/2}$ for large $n$ (exponent is half). So the quantum
algorithm ($2^{n/4}$) grows slower asymptotically. For example, at $n=8$, classical $2^4=16$, quantum
$2^2=4$. Generally this is a quadratic speedup in the exponent.

Sources: Concepts summarized above are drawn from foundational quantum computing texts and
references 1 4 7 8 10 9 12 25 27 26 .

1 2 3 4 5 6 7 8 16 17 18 23 24 25 26 28 QC_Basics.pdf
[Link]

9 Hadamard transform - Wikipedia

[Link]

10 Pauli matrices - Wikipedia

[Link]

11 12 14 15 Quantum logic gate - Wikipedia

[Link]

13 Controlled NOT gate - Wikipedia

[Link]

19 20 21 22 Bell state - Wikipedia

[Link]

27 Deutsch–Jozsa algorithm - Wikipedia

[Link]

14