Notes - Quantum Information HT24, Quantum circuit model
Flashcards
Give the 5 actions that can be performed in the “standard model of quantum computation” (define each gate in the standard gate set seperately).
- Preparing qubits in the state $ \vert 0\rangle$
- Transforming qubits with the Hadamard gate $H = \vert +\rangle\langle 0 \vert + \vert -\rangle\langle 1 \vert $
- Transforming qubits with the gate $T = \vert 0\rangle\langle 0 \vert + e^{i\pi/4} \vert 1\rangle\langle1 \vert $
- Transforming pairs of qubits with the gate $\mathtt{CNOT} = \vert 0\rangle\langle 0 \vert \otimes I + \vert 1\rangle\langle 1 \vert \otimes X$
- Measuring qubits in the computational basis
What are the three gates in the standard gate set used in the quantum model of computation?
- The Hadamard gate: $H = \vert +\rangle\langle 0 \vert + \vert -\rangle\langle 1 \vert $
- The $\pi/8$ gate (unfortunate name, because of global phase): $T = \vert 0\rangle\langle 0 \vert + e^{i\pi/4} \vert 1\rangle\langle1 \vert $
- The Controlled-Not gate: $\mathtt{CNOT} = \vert 0\rangle\langle 0 \vert \otimes I + \vert 1\rangle\langle 1 \vert \otimes X$
What does it mean for a unitary gate $U$ to be generated by a set of unitary gates $\mathsf F$?
$U$ can be written as a composition of tensor products of gates in $\mathsf F$.
What is the initial state and output of a quantum computation, and how do we prepare states other than the initial state?
- Initial state: all qubits in state $ \vert 0\rangle$.
- Output: measure all qubits against computational basis.
- Preparing states other than initial state: apply gates to transform $ \vert 0\rangle^{\otimes n}$ into desired state
Suppose:
- $ \vert \psi\rangle, \vert \psi’\rangle \in \mathbb C^d$ are two unit vectors
What does it mean for the corresponding pure states to be $\epsilon$-close?
There exists a global phase $e^{i\gamma}$ such that
\[\Big|\Big||\psi'\rangle - e^{i\gamma} |\psi\rangle\Big|\Big| < \epsilon\]Suppose:
- $ \vert \psi\rangle, \vert \psi’\rangle \in \mathbb C^d$ are two unit vectors
- They are $\epsilon$-close, i.e. $\exists$ global phase $e^{i\gamma}$ such that $\Big \vert \Big \vert \vert \psi’\rangle - e^{i\gamma} \vert \psi\rangle\Big \vert \Big \vert < \epsilon$
- $\{ \vert \alpha _ n \rangle\}^{d-1} _ {n = 0}$ is an arbitrary orthonormal basis
Then why does being $\epsilon$-close imply they are approximately the same, i.e. what can you say about the probability distributions
\[\begin{aligned}
p(n) &:= |\langle\alpha_n | \psi\rangle|^2 \\\\
p'(n) &:= |\langle\alpha_n | \psi'\rangle|^2
\end{aligned}\]
We have the bound
\[|p'(n) - p(n)| < 2\epsilon + \epsilon^2\]for every $n$ in $\{0, \cdots, d-1\}$.
Suppose
- $ \vert \psi\rangle, \vert \psi’\rangle \in \mathbb C^d$ are two unit vectors
- They are $\epsilon$-close, i.e. $\exists$ global phase $e^{i\gamma}$ such that $\Big \vert \Big \vert \vert \psi’\rangle - e^{i\gamma} \vert \psi\rangle\Big \vert \Big \vert < \epsilon$
- $\{ \vert \alpha _ n \rangle\}^{d-1} _ {n = 0}$ is an arbitrary orthonormal basis
and we have the probability distributions
\[\begin{aligned}
p(n) &:= |\langle\alpha_n | \psi\rangle|^2 \\\\
p'(n) &:= |\langle\alpha_n | \psi'\rangle|^2
\end{aligned}\]
Quickly prove that we have the bound
\[|p'(n) - p(n)| < 2\epsilon + \epsilon^2\]
for every $n$ in $\{0, \cdots, d-1\}$.
where
\[|\delta\rangle := |\psi'\rangle - e^{i\gamma} |\psi\rangle\]Then using the relation that $ \vert a + b \vert ^2 = \vert a \vert ^2 + \vert b \vert ^2 + 2\text{Re}(\bar a b)$,
\[\begin{aligned} p'(n) &= |\langle \alpha_n | \delta\rangle|^2 + |\langle \alpha_n | \psi\rangle|^2 + 2\text{Re}(e^{-i\gamma} \langle \psi|\alpha_n \rangle\langle \alpha_n | \delta\rangle) \\\\ &\le |\langle \alpha_n|\delta\rangle|^2 + p(n) + 2|e^{-i\gamma}\langle \psi|\alpha_n \rangle\langle\alpha_n|\delta\rangle| \\\\ &\le \epsilon^2 + p(n) + 2\epsilon \end{aligned}\]where we used the Cauchy-Schwarz inequality on $ \vert \langle \alpha _ n \vert \delta\rangle \vert ^2$ and the fact that $ \vert \vert \alpha\rangle \vert ^2 < \epsilon^2$ by assumption. Also $ \vert \langle \psi \vert \alpha _ n \rangle \vert \le 1$ since this is just a probability.
Since the property of being $\epsilon$-close is symmetric, we have the other bound
\[p(n) \le \epsilon^2 + p'(n) + 2\epsilon\]Sticking these together,
\[|p'(n) - p(n)| \le \epsilon^2 + 2\epsilon\]Suppose:
- $U$, $U’$ are two unitary $d \times d$ matrices.
What does it mean for the corresponding reversible processes to be $\epsilon$-close?
Suppose:
- $\mathsf F$ is a finite set of unitary matrices
What does it mean for $\mathsf F$ to be universal for quantum computation?
For every possible $n$-qubit gate $U$ and $\epsilon > 0$, $U$ can be approximated by a gate $\tilde U$ built from gates in $\mathsf F$ which is $\epsilon$-close to $U$.
In the standard model of quantum computation, the output is the measurement of all $n$ qubits on the computational basis. Suppose we want to measure in a different basis, say $\{\alpha _ n\}^{d-1} _ {n = 0}$. Quickly show how can this be achieved using a universal gate set $\mathsf F$?
Consider the unitary gate that transforms $\{\alpha _ n\}^{d-1} _ {n = 0}$ into the computational basis. This is given by
\[U = \sum_ {m = 0}^{d-1} |m\rangle \langle \alpha_ m |\]Then $\forall \vert m\rangle$ in the computational basis, we have $\langle m \vert U = \langle \alpha _ m \vert $. Approximate $U$ with $U _ \epsilon$ using gates from $\mathsf F$, which is $\epsilon$-close. Then
\[p_\epsilon(m) := \Big|\langle m | U_\epsilon | \psi_m \rangle\Big|^2 \approx |\langle \alpha_m| \psi\rangle|^2\]Can you state a theorem which simplifies the process of finding a universal gate set for quantum computation, so that we can consider only single-qubit gates in our search?
Suppose:
- $U _ 2$ is a two-qubit entangling gate (i.e. transforms at least some product state into an entangled state)
Then:
- Every $n$-qubit unitary gate can be decomposed into a circuit consisting only of single-qubit gates and the gate $U _ 2$.
We have a theorem that states that if
- $U _ 2$ is a two-qubit entangling gate (i.e. transforms at least some product state into an entangled state)
Then:
- Every $n$-qubit unitary gate can be decomposed into a circuit consisting only of single-qubit gates and the gate $U _ 2$.
This simplifies our life considerably in searching for a universal gate set, since we only need to find single-qubit gates that can approximate any other single-qubit gate.
State a theorem that gives an infinite class of such gates, and explain the intuitive idea behind it using the Bloch sphere.
Suppose:
- $t \in \mathbb R \setminus (\pi \mathbb Q)$
- $n \in \mathbb R^3$ direction in space
Then every rotation around the axis $n$ can be $\epsilon$-approximated by applying the rotation $\alpha = t\pi$ around $n$ a finite number of times.
Since every unitary gate on a single qubit corresponds to a rotation of the Bloch sphere, and every rotation can be considered is generated by two rotations on distinct axes, this means any two unitary gates that rotate by an irrational angle on two different axes can give a universal gate set.
Suppose:
- $U$ is an $n$-qubit gate
- $\epsilon > 0$
Can you define the complexity $C(U, \epsilon)$ of the gate $U$?
The minimum number of elementary gates needed to $\epsilon$-approximate $U$.
How is the classical $\mathtt{NOT}$ gate realised on a quantum computer?
Using the Pauli gate $X$, which flips states in the computational basis.
Why can’t you find a unitary gate that realises the classical gate $\mathtt{AND}$ on a quantum computer?
$\mathtt{AND}$ is irreversible, but all unitary matrices are invertible.
How is the $\mathtt{TOFFOLI}$ gate defined, and how can you remember this?
where $\oplus$ denotes $\mathtt{XOR}$, or equivalently, addition modulo $2$.
One way to make it easier to remember is that this can be viewed as a simple way of making the $\mathtt{AND}$ gate reversible, by remembering the inputs.
How the complexity of a quantum state defined?
The minimum number of elementary operations needed to prepare that state, where an elementary operation is an initialisation of a state like $ \vert 0\rangle$ or a non-identity unitary matrix applied to that state.
In the context of the complexity of quantum states and measurements, what is an elementary operation?
- An initialisation of a state like $ \vert 0\rangle$
- Application of a non-identity unitary matrix
(For reference, the complexity of a quantum state is then the minimum number of elementary operations needed to prepare that state, and the complexity of a quantum measurement is the minimum number of elemntary operations needed to implement the measurement).
How is the complexity of a quantum measurement defined?
The minimum number of elemenatary operations needed to implement that measurement, where an elementary operation is an initialisation of a state like $ \vert 0\rangle$ or an application of a non-identity unitary matrix.
Show how to construct the Bell state
\[|\Phi^+\rangle = \frac{|0\rangle \otimes |0\rangle + |1\rangle \otimes |1\rangle}{\sqrt 2}\]
using a quantum circuit, and hence give an upper bound on the complexity of the state.
Complexity is at most $4$.
Show how to construct the state
\[|\mathtt{GHZ}\rangle = \frac{|0\rangle \otimes |0\rangle \otimes |0\rangle + |1\rangle \otimes |1\rangle \otimes |1\rangle}{\sqrt 2}\]
using a quantum circuit and hence give an upper bound on the complexity of the GHZ state.
Complexity is at most $6$.
How could you quickly deduce that
\[\\{\texttt{CNOT}, X\\}\]
is not a universal gate set?
They both take computational basis states to computational basis states, so there’s no way of using them to approximate a gate that maps computational basis states to non-computational basis states.
What is
\[\mathtt{CNOT}(|+\rangle \otimes |0\rangle)\]
and how can you remember this?
$\mathtt{CNOT}(H \otimes I)( \vert 0\rangle \otimes \vert 0\rangle)$ is the standard way of preparing the Bell state from the computational basis states.
How can you implement the Pauli gate $Z$ using $\{\mathtt{CNOT}, H, T\}$? Hence give an upper bound on its complexity.
So the complexity of $Z$ is at most $4$.
How can you implement the gate $T^{-1}$ using the standard gate set $\{\mathtt{CNOT}, H, T\}$? Hence give an upper bound on its complexity.
Hence
\[T^{-1} = T^\dagger = -T^7\]so the complexity of $T^{-1}$ is at most $7$.
What is the complexity of the $n$-bit Fourier gate on a quantum computer, and how is this different from the classical case?
$O(n^2)$. In the classical case, computing the Fourier transform of a vector with $2^n$ components requires at least $2^n$ elementary operations.
Suppose we have the $n$-qubit Fourier state
\[|e_0\rangle = \frac{1}{\sqrt{2^n}
} \sum^{2^n_
1}_
{x = 0} |x\rangle\]
where
\[|x\rangle = |x_1\rangle \otimes |x_2\rangle \otimes \cdots \otimes |x_n\rangle\]
and $(x _ 1, \cdots x _ n)$ are the digits in the binary expansion of $x$. Quickly derive an expression for how to prepare the Fourier state using gates from $\{\mathtt{CNOT}, H, T\}$ and hence give an upper bound on the complexity of the Fourier state.
Hence
\[|e_0\rangle = (H \otimes H \otimes \cdots \otimes H) (|0\rangle \otimes |0\rangle \otimes\cdots\otimes|0\rangle)\]So the complexity of the Fourier state $ \vert e _ 0\rangle$ is at most $2n$.
Given that $\{\mathtt{CNOT}, H, T\}$ is a universal gate set, how could you show $\{\mathtt{CNOT}, U, T\}$ is a universal gate set where
\[U = \frac 1 {\sqrt 2} (I - iH)\]
is also a universal gate set?
Note that
\[U^2 = \frac 1 2 (I - 2iH - H^2) = -iH\]which is equal to $H$ up to global phase.
How could you show that
\[\\{\mathtt{CNOT}, H, T^2\\}\]
is not a universal gate set?
Ignore the $\mathtt{CNOT}$ and consider just single-qubit gates. You can show that any combination of these gates can only map $ \vert 0\rangle$ to finitely many states.