What is this workbook? A workbook is a collection of problems, accompanied by solutions to them. The explanations focus on the logical steps required to solve a problem; they illustrate the concepts that need to be applied to come up with a solution to the problem, explaining the mathematical steps required.
Note that a workbook should not be the primary source of knowledge on the subject matter; it assumes that you've already read a tutorial or a textbook and that you are now seeking to improve your problem-solving skills. You should attempt solving the tasks of the respective kata first, and turn to the workbook only if stuck. While a textbook emphasizes knowledge acquisition, a workbook emphasizes skill acquisition.
This workbook describes the solutions to the problems offered in the UnitaryPatterns.
What you should know for this workbook
For an overview of all the gates have a look at the Q# quick reference here.
Input: N qubits in an arbitrary state.
Goal: Implement a unitary transformation on N qubits which is represented by a matrix with non-zero elements on the main diagonal and zero elements everywhere else.
Example: For N = 2, the matrix of the transformation should look as follows:
X...
.X..
..X.
...X
The required unitary transformation is a diagonal matrix in which all diagonal elements are non-zero. Since the transformation has to be unitary, i.e., it must preserve the norm of the vectors it is applied to, all diagonal elements have to have norm of $1$, i.e., be represented as complex numbers $e^{i\alpha}$ for some real $\alpha$.
The simplest such unitary is the identity matrix $I^{\otimes N}$, where $N$ is the number of qubits. For $N=2$ this would be $$\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \otimes \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}$$
For a general $N$ this can be achieved by applying the unitary $I$ to all qubits, which is equivalent to a no-op.
%kata T01_MainDiagonal
operation MainDiagonal (qs : Qubit[]) : Unit {
// We don't need to write out applying identity unitary, since it is a no-op
}
Input: N qubits in an arbitrary state.
Goal: Implement a unitary transformation on N qubits which is represented by a matrix with all elements non-zero.
Example: For N = 2, the matrix of the transformation should look as follows:
XXXX
XXXX
XXXX
XXXX
We need to construct a unitary that converts any basis state into a superposition of all basis states.
For $N=1$ the simplest such unitary is the Hadamard gate $H=\frac{1}{\sqrt2}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$. Similarly, for any $N$ such a unitary would be $U=H^{\otimes N}$ (apply $H$ to each qubit).
For $N=2$ this would be $$H^{\otimes 2} = \frac{1}{\sqrt2}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \otimes \frac{1}{\sqrt2}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} = \frac{1}{2}\begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{bmatrix} $$
Hadamard matrices are guaranteed to have all their elements either $\frac{1}{\sqrt{2^N}}$ or $-\frac{1}{\sqrt{2^N}}$. This can be easily proven via induction, as the $H$ matrix has no non-zero elements. Since each element of a tensor product is a result of multiplication of several elements of the $H$ matrix, it cannot be zero.
%kata T02_AllNonZero
operation AllNonZero (qs : Qubit[]) : Unit {
ApplyToEach(H, qs);
}
Input: N qubits in an arbitrary state.
Goal: Implement a unitary transformation on N qubits which is represented by a matrix which has $2 \times 2$ blocks of non-zero elements on the main diagonal and zero elements everywhere else.
Example: For N = 3, the matrix of the transformation should look as follows:
XX......
XX......
..XX....
..XX....
....XX..
....XX..
......XX
......XX
From the approach we took in the previous tasks, we can see a pattern: we need to break the given unitary transformation into a tensor product of smaller matrices.
The block diagonal matrix can be broken into product of two matrices.
For the illustrative $N=3$ case we can break it into $$ \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} \otimes \begin{bmatrix} x & x \\ x & x \end{bmatrix} = \begin{bmatrix} x & x & . & . & . & . & . & .\\ x & x & . & . & . & . & . & .\\ . & . & x & x & . & . & . & .\\ . & . & x & x & . & . & . & .\\ . & . & . & . & x & x & . & .\\ . & . & . & . & x & x & . & .\\ . & . & . & . & . & . & x & x\\ . & . & . & . & . & . & x & x \end{bmatrix} $$
For a general $N\gt2$ we have the required transformation $ U = I^{\otimes N-1} \otimes \begin{bmatrix} x & x \\ x & x \end{bmatrix}$, where the second matrix has all non-zero elements.
The $2 \times 2$ matrix can be chosen as the Hadamard matrix $H = \frac{1}{\sqrt2}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$.
Thus the required unitary transformation is $U = I^{\otimes N-1} \otimes H$.
Note that this is the first task in which endianness matters: the indices in the matrices use little endian, this the rightmost unitary in the tensor product (which corresponds to the least significant bit of the index) is applied to qubit with index $0$.
%kata T03_BlockDiagonal
operation BlockDiagonal (qs : Qubit[]) : Unit {
H(qs[0]);
// We don't need to write out applying identity unitary, since it is a no-op
}
Input: N qubits in an arbitrary state.
Goal: Implement a unitary transformation on N qubits which is represented by a matrix with non-zero elements in top left and bottom right quarters and zero elements everywhere else.
Example: For N = 3, the matrix of the transformation should look as follows:
XXXX....
XXXX....
XXXX....
XXXX....
....XXXX
....XXXX
....XXXX
....XXXX
We again break the given unitary transformation into a tensor product of smaller matrices.
For the illustrative $N=3$ case we can break it into $$\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \otimes \begin{bmatrix} x & x & x & x \\ x & x & x & x \\ x & x & x & x \\ x & x & x & x \end{bmatrix} = \begin{bmatrix} x & x & x & x & . & . & . & .\\ x & x & x & x & . & . & . & .\\ x & x & x & x & . & . & . & .\\ x & x & x & x & . & . & . & .\\ . & . & . & . & x & x & x & x\\ . & . & . & . & x & x & x & x\\ . & . & . & . & x & x & x & x\\ . & . & . & . & x & x & x & x \end{bmatrix} $$
We can see that the second matrix is the same as what we saw in task 2 - a matrix with all non-zero elements. Hence we reach a general solution for $N\gt2$:
$$ U = I \otimes H^{\otimes N-1}$$%kata T04_Quarters
operation Quarters (qs : Qubit[]) : Unit {
// Same as in previous task, the little endian encoding of indices means that
// the leftmost unitary (identity) is applied to the qubit with index N-1,
// so we need to apply H gates to all qubits except the last one.
ApplyToEach(H, qs[0 .. Length(qs)-2]);
}
Input: N qubits in an arbitrary state.
Goal: Implement a unitary transformation on N qubits which is represented by a matrix with non-zero elements in positions where row and column indices have the same parity and zero elements everywhere else.
Example: For N = 2, the matrix of the transformation should look as follows:
X.X.
.X.X
X.X.
.X.X
This is very similar to task 4, with just the order of matrices changed. We again break the given unitary transformation into tensor product of smaller matrices.
For the illustrative $N=2$ case we can break it into $$\begin{bmatrix} x & x \\ x & x \end{bmatrix} \otimes \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} x & . & x & . \\ . & x & . & x \\ x & . & x & . \\ . & x & . & x \end{bmatrix} $$
We again pick the non-zero block matrix as $H$. Hence we get a general solution for $N$:
$$ U = H^{\otimes N-1} \otimes I$$Q# expression
qs[1 ...]
gets a sub-array of all elements ofqs
except the first one. You can read more about array slicing and inferred start/end values in the Q# documentation.
%kata T05_EvenChessPattern
operation EvenChessPattern (qs : Qubit[]) : Unit {
// Same as in previous task, the little endian encoding of indices means that
// the rightmost unitary (identity) is applied to the qubit with index N-1,
// so we need to apply H gates to all qubits except the first one.
ApplyToEach(H, qs[1 ...]);
}
Input: N qubits in an arbitrary state.
Goal: Implement a unitary transformation on N qubits which is represented by a matrix with non-zero elements in positions where row and column indices have different parity and zero elements everywhere else.
Example: For N = 2, the matrix of the transformation should look as follows:
.X.X
X.X.
.X.X
X.X.
The solution is very similar to task 5, but we need to switch the order of $0$ and $1$ elements in the $2 \times 2$ matrix, so that X
and .
elements are swapped in the final result. To do this, we choose $X$ matrix instead of $I$.
For the illustrative case $N=2$ this becomes $$\begin{bmatrix} x & x \\ x & x \end{bmatrix} \otimes \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} . & x & . & x \\ x & . & x & . \\ . & x & . & x \\ x & . & x & . \end{bmatrix} $$
Thus the required transformation for any $N$ is
$$ U = H^{\otimes N-1} \otimes X$$%kata T06_OddChessPattern
operation OddChessPattern (qs : Qubit[]) : Unit {
X(qs[0]);
ApplyToEach(H, qs[1 ...]);
}
Input: N qubits in an arbitrary state.
Goal: Implement a unitary transformation on N qubits which is represented by a matrix with non-zero elements on the anti-diagonal and zero elements everywhere else.
Example: For N = 2, the matrix of the transformation should look as follows:
...X
..X.
.X..
X...
Similarly to task 1, since the transformation has to be unitary, i.e., it must preserve the norm of the vectors it is applied to, all anti-diagonal elements have to have norm of $1$, i.e., be represented as complex numbers $e^{i\alpha}$ for some real $\alpha$. The easiest way to achieve this is to choose all anti-diagonal elements to be $1$.
For $N=1$ the solution would be the Pauli $X$ gate.
For $N=2$ we can again represent the matrix as a tensor product of smaller matrices: $$\begin{bmatrix} 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \otimes \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$$
For a general $N$ the simplest such unitary is thus $X^{\otimes N}$ - applying the $X$ gate to each qubit.
%kata T07_Antidiagonal
operation Antidiagonal (qs : Qubit[]) : Unit {
ApplyToEach(X, qs);
}
Input: N qubits in an arbitrary state.
Goal: Implement a unitary transformation on N qubits which is represented by a matrix in which zero and non-zero elements form a chessboard pattern with 2x2 squares, with the top left square occupied by non-zero elements.
Example: For N = 3, the matrix of the transformation should look as follows:
XX..XX..
XX..XX..
..XX..XX
..XX..XX
XX..XX..
XX..XX..
..XX..XX
..XX..XX
This task is something between tasks 4 (a pattern of two large diagonal blocks) and 5 (a chessboard pattern of $1 \times 1$ squares). Both of them are formed using only Hadamard gates, so it makes sense to try and see if the pattern in this task can be expressed this way as well.
Consider the case of $N = 2$; the pattern you need to implement in this task is exactly the same as the pattern in task 4 (two large blocks), which you can obtain as $I \otimes H$:
$$I \otimes H = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \otimes \begin{bmatrix} 1 & 1 \\ 1 & -1\end{bmatrix} = \begin{bmatrix} 1 & 1 & 0 & 0 \\ 1 & -1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & -1\end{bmatrix}$$More formally, you can think about this task in terms of tensor products:
The smallest block you need to repeat in the $2 \times 2$ chessboard pattern is $I \otimes H$ we've seen earlier.
Now you can repeat it as many times as you need by multiplying H gates by it: $$H \otimes (I \otimes H) = \begin{bmatrix} I \otimes H & I \otimes H \\ I \otimes H & - I \otimes H\end{bmatrix} = \begin{bmatrix} 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & -1 & 0 & 0 & 1 & -1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & -1 & 0 & 0 & 1 & -1 \\ 1 & 1 & 0 & 0 & -1 & -1 & 0 & 0 \\ 1 & -1 & 0 & 0 & -1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & -1 & -1 \\ 0 & 0 & 1 & -1 & 0 & 0 & -1 & 1 \end{bmatrix}$$
The unitary transformation is $H^{\otimes N-2} \otimes I \otimes H$.
%kata T08_ChessPattern2x2
operation ChessPattern2x2 (qs : Qubit[]) : Unit {
H(qs[0]);
I(qs[1]); // No-op added for the sake of completeness
ApplyToEach(H, qs[2 ...]);
}
Input: N qubits in an arbitrary state.
Goal: Implement a unitary transformation on N qubits which is represented by a matrix with
Example: For N = 2, the matrix of the transformation should look as follows:
.X..
X...
..XX
..XX
This matrix can not be represented as a tensor product any longer, since the patterns in the top left block and the bottom right block are different. We need to figure out a different way to combine the patterns from task 7 and task 2.
Let's label the given unitary transformation as $U$, the unitary that implements the anti-diagonal pattern from task 7 as $U_7$, and the unitary that implements the all-non-zero pattern from task 2 as $U_2$.
The top left block of the matrix is the area where the most significant bit of both input and output indices equals $0$, and the effect of the unitary $U$ on $N$ qubits is defined as the effect of the unitary $U_7$ on the $N-1$ least significant bits. (Remember that with little endian encoding of the indices the most significant bit is stored in the last qubit.)
$$U(|\psi\rangle \otimes |0\rangle) = U_7(|\psi\rangle) \otimes |0\rangle $$The left half of the matrix can be described as follows: if the last qubit of the input is in state $|0\rangle$, leave that qubit unchanged and apply $U_7$ to the rest of the qubits. If we choose $U_7 = X^{\otimes N-1}$, like we did in task 7, we'll get:
$$U|\psi\rangle \otimes |0\rangle = \big(X^{\otimes N-1}|\psi\rangle \big) \otimes |0\rangle $$Similarly, the bottom right block is the area where the most significant bit of input and output equals $1$, $$U|\phi\rangle \otimes |1\rangle = U_2(|\phi\rangle) \otimes |1\rangle $$
The right half of the matrix can be described as follows: if the last qubit of the input is in state $|1\rangle$, leave that qubit unchanged and apply $U_2$ to the rest of the qubits. If we choose $U_2 = H^{\otimes N-1}$, like we did in task 2, we'll get
$$U|\phi\rangle \otimes |1\rangle = \big(H^{\otimes N-1}|\phi\rangle \big) \otimes |1\rangle $$Combining these descriptions, we can implement the unitary $U$ in 2 parts:
For $N=2$ we have
$$\begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ 0 & 0 & \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}}\end{bmatrix}$$and for $N=3$ we have
$$\begin{bmatrix} 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ 0 & 0 & 0 & 0 & \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} \\ 0 & 0 & 0 & 0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} \\ 0 & 0 & 0 & 0 & \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \end{bmatrix}$$We'll use Q# library operations from the
Microsoft.Quantum.Arrays
namespace: Tail which returns the last element of the array and Most which returns all elements except the last one.
%kata T09_TwoPatterns
open Microsoft.Quantum.Arrays;
operation TwoPatterns (qs : Qubit[]) : Unit {
ApplyToEach(Controlled H([Tail(qs)], _), Most(qs));
ApplyToEach((ControlledOnInt(0, X))([Tail(qs)], _), Most(qs));
}
Input: N qubits in an arbitrary state.
Goal: Implement a unitary transformation on N qubits which is represented by a matrix defined recursively:
Example: For N = 3, the matrix of the transformation should look as follows:
X.......
.X......
..XX....
..XX....
....XXXX
....XXXX
....XXXX
....XXXX
This task builds up on the task 9 in which matrices which are composed of smaller blocks but can't be represented as a tensor product. If we represent this unitary transformation for a given $N$ as $U_N$, then we see the following pattern:
The bottom right block is the area where the most significant bit of input and output equals $1$, and similarly to the task 9 we can represent it as follows:
$$U_N \big(|\phi\rangle \otimes |1\rangle\big) = \big(H^{\otimes N-1}|\phi\rangle \big) \otimes |1\rangle$$The top left block is the area where the most significant bit of both input and output indices equals $0$, and it matches the pattern of the same unitary for the smaller number of qubits. The left half of the matrix can be described as follows: if the last qubit of the input is in state $|0\rangle$, leave that qubit unchanged and apply an $U_{N-1}$ gate to remaining qubits.
(Remember that with little endian encoding of the indices this bit is stored in the last qubit.) $$U_{N}|\psi\rangle \otimes |0\rangle = \big(U_{N-1}|\psi\rangle \big) \otimes |0\rangle $$
This allows us to define the solution recursively, if we define the base of recursion as $U_1=I$:
Q# allows us to express recursion without unrolling it, if we add a definition of controlled variant to our operation. We can do it automatically if we modify the signature of the task to include
is Adj+Ctl
.
%kata T10_IncreasingBlocks
open Microsoft.Quantum.Arrays;
operation IncreasingBlocks (qs : Qubit[]) : Unit is Adj + Ctl {
let N = Length(qs);
if N == 1 {
// for N = 1, we need an identity, which is equivalent to doing nothing
} else {
// Apply H to get bottom-right quarter right
ApplyToEachCA(Controlled H([Tail(qs)], _), Most(qs));
// Apply the same operation recursively to get the top-left quarter right
(ControlledOnInt(0, IncreasingBlocks))([Tail(qs)], Most(qs));
}
}
Input: N qubits in an arbitrary state.
Goal: Implement a unitary transformation on N qubits which is represented by a matrix with non-zero elements on the main diagonal and the anti-diagonal and zero elements everywhere else.
Example: For N = 3, the matrix of the transformation should look as follows:
X......X
.X....X.
..X..X..
...XX...
...XX...
..X..X..
.X....X.
X......X
This transformation again cannot be broken into tensor product of smaller matrices.
The columns of the unitary matrix tell us how the matrix acts on the computational basis states. First, we represent the computational basis states in little endian form: $|0\rangle, |1\rangle, ..., |2^{N}-2\rangle, |2^{N}-1\rangle$ for given $N$. Now we observe that for any $0\leq i \lt 2^N$, our unitary $U$ acts on a given computational basis state $|i\rangle$ to convert it into a linear combination of $|i\rangle$ and $|2^{N}-1-i\rangle$:
$$U|i\rangle = \alpha_i |i\rangle + \beta_i |2^{N}-1-i\rangle$$Notice that both $|i\rangle$ and $|2^{N}-1-i\rangle$ will be transformed into some linear combination of $|i\rangle$ and $|2^{N}-1-i\rangle$. Hence to maintain orthogonality of these states (states which are orthogonal remain orthogonal under unitary transformations) we must pick coefficients $(\alpha_i, \beta_i)$ and $(\alpha_{2^{N}-1-i}, \beta_{2^{N}-1-i})$ such that the inner product of these states is
$$\langle i|U^\dagger U|2^N-1-i\rangle = \langle i|2^N-1-i\rangle = 0$$The simplest such coefficients are $\big(\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}}\big)$ and $\big(\frac{1}{\sqrt{2}},\frac{-1}{\sqrt{2}}\big)$. Our expression for defining the unitary becomes the following:
$$U|i\rangle = \frac{1}{\sqrt{2}} |i\rangle + \frac{1}{\sqrt{2}} (-1)^{k} |2^{N}-1-i\rangle$$Here $k$ is the most significant bit of the basis state $i$.
We can simplify this expression further by observing that $|2^{N}-1-i\rangle$ is the two's complement of $|i\rangle$, i.e., $|2^{N}-1-i\rangle= X^{\otimes N}|i\rangle$. Now we can describe the effect of the unitary on the basis states as follows:
$$U|i\rangle = \frac{1}{\sqrt{2}} |i\rangle + (-1)^{k}\frac{1}{\sqrt{2}} X^{\otimes N}|i\rangle$$The dependence on the sign of the most significant bit hints towards using the $H$ gate: at some point we'll want to apply the $H$ gate to the most significant bit.
This unitary can be constructed in 3 steps:
We use a series of CNOT gates with the most significant bit (MSB) acting as control and each of the remaining bits acting as target. The gate will leave the MSB unchanged and flip the rest of the bits when in MSB is 1.
Let us take 2 examples for $N=3$ where the input states are $i=0$ and $i=6$. The states in little endian format would be $|000\rangle$ and $|011\rangle$. After step 1 these would become $|000\rangle$ and $|101\rangle$, respectively.
The unitary for step 1 when $N=3$ would be $$\begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \end{bmatrix}$$
We apply the Hadamard gate on the MSB. This will give us the necessary coefficients: if MSB is 0 or 1, the coefficients would be $\big(\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}}\big)$ and $\big(\frac{1}{\sqrt{2}},\frac{-1}{\sqrt{2}}\big)$, respectively.
After step 2 our examples would become $|00\rangle \otimes H|0\rangle=\frac{1}{\sqrt{2}}|000\rangle + \frac{1}{\sqrt{2}}|001\rangle$ and $|10\rangle \otimes H|1\rangle=\frac{1}{\sqrt{2}}|100\rangle - \frac{1}{\sqrt{2}}|101\rangle$.
The unitary for step 2 is $$\frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & -1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & -1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & -1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & -1 \end{bmatrix}$$
Now we have the necessary coefficients, and one of the basis states in superposition matches the starting state $|i\rangle$, but the second basis state is not two's complement of $|i\rangle$. To fix this, we repeat step 1 again.
After step 3 our examples would become $\frac{1}{\sqrt{2}}|000\rangle + \frac{1}{\sqrt{2}}|111\rangle$ and $\frac{1}{\sqrt{2}}|100\rangle - \frac{1}{\sqrt{2}}|011\rangle$.
The unitary for step 3 is same as step 1.
If we multiply all 3 unitaries, we get the required unitary.
$$U = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \end{bmatrix} \times \frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & -1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & -1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & -1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & -1 \end{bmatrix} \times \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \end{bmatrix} = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & -1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & -1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & -1 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & -1 \end{bmatrix}$$%kata T11_XWing_Fighter
open Microsoft.Quantum.Arrays;
operation XWing_Fighter (qs : Qubit[]) : Unit {
ApplyToEach(CNOT(Tail(qs), _), Most(qs));
H(Tail(qs));
ApplyToEach(CNOT(Tail(qs), _), Most(qs));
}
Input: N qubits in an arbitrary state.
Goal: Implement a unitary transformation on N qubits which is represented by a matrix with non-zero elements forming a rhombus of width 1 with sides parallel to main diagonals.
Example: For N = 2, the matrix of the transformation should look as follows:
.XX.
X..X
X..X
.XX.
For N = 3, the matrix of the transformation should look as follows:
...XX...
..X..X..
.X....X.
X......X
X......X
.X....X.
..X..X..
...XX...
Task 12 is very similar to task 11: we will get this unitary transformation if we swap the left and right halves of the unitary matrix we implemented in task 11. This can be done by applying the $X$ gate on the most significant bit.
Thus for the case $N=3$, the matrix would be $$\frac{1}{\sqrt{2}}\begin{bmatrix} 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & -1 \\ 0 & 1 & 0 & 0 & 0 & 0 & -1 & 0 \\ 0 & 0 & 1 & 0 & 0 & -1 & 0 & 0 \\ 0 & 0 & 0 & 1 & -1 & 0 & 0 & 0 \end{bmatrix}$$
We can check this using the same examples as we used in task 11:
- The starting states in little endian format are $|000\rangle$ and $|011\rangle$;
- After applying the unitary transformation from task 11 we get
$\frac{1}{\sqrt{2}}|000\rangle + \frac{1}{\sqrt{2}}|111\rangle$ and $\frac{1}{\sqrt{2}}|100\rangle - \frac{1}{\sqrt{2}}|011\rangle$ respectively;
- We apply the $X$ gate on the MSB of the result to get $\frac{1}{\sqrt{2}}|001\rangle + \frac{1}{\sqrt{2}}|110\rangle$ and
$\frac{1}{\sqrt{2}}|101\rangle - \frac{1}{\sqrt{2}}|010\rangle$.
This is the exactly the same output as predicted by the unitary matrix above.
Therefore, the implementation is simply applying the steps from task 11, followed by applying the $X$ gate on the MSB.
%kata T12_Rhombus
operation Rhombus (qs : Qubit[]) : Unit {
XWing_Fighter(qs);
X(qs[Length(qs) - 1]);
}
Input: N qubits in an arbitrary state ($2 \leq N \leq 5$).
Goal: Implement a unitary transformation on N qubits which is represented by a matrix with non-zero elements in the following positions:
The central $2 \times 2$ sub-matrix;
The diagonals of the top right and bottom left sub-matrices of size $2^{N-1}-1$
that do not overlap with the central $2 \times 2$ sub-matrix;
that do not overlap with the central $2 \times 2$ sub-matrix.
Example:
For N = 3, the matrix of the transformation should look as follows:
..X..X..
.X....X.
X......X
...XX...
...XX...
X......X
.X....X.
..X..X..
For $N=3$ the top right corner of the required unitary in matrix form is $\begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{bmatrix}$.
This unitary is $\sigma_{N-1} = \sum_{i=0}^{2^{N-1}-1} |{i-1}\rangle\langle{i}|$ (indices are computed modulo $2^{N-1}$). It decrements the input state (in little endian format), i.e., maps $\sigma_{N-1}|{i}\rangle=|(i-1)$ mod $2^{N-1}\rangle$. It can be implemented using cascading series of controlled $NOT$ gates (here the top wire denotes the least significant bit):
We can arrive at one possible solution to this problem using $\sigma_{N-1}$ and $\Pi_X = X^{\otimes N-1}$:
$$U = \frac{1}{\sqrt{2}}\left(\begin{array}{cc} \sigma_{N-1} \Pi_X & \sigma_{N-1} \\ \Pi_X \sigma_{N-1} \Pi_X & -\Pi_X \sigma_{N-1} \end{array}\right)$$Using properties of tensor product $\otimes$, we can rewrite the above expression as
$$U = \frac{1}{\sqrt{2}}\left(\begin{array}{cc} \sigma_{N-1} \Pi_X & \sigma_{N-1} = \\ \Pi_X \sigma_{N-1} \Pi_X & -\Pi_X \sigma_{N-1} \end{array}\right) = \\ = \frac{1}{\sqrt{2}}\left(\begin{array}{cc} \Pi_I \sigma_{N-1} \Pi_X & \Pi_I \sigma_{N-1} \Pi_I\\ \Pi_X \sigma_{N-1} \Pi_X & -\Pi_X \sigma_{N-1} \Pi_I \end{array}\right) = \\ = \left(\begin{array}{cc} \Pi_I & 0 \\ 0 & \Pi_X \end{array}\right) \frac{1}{\sqrt{2}}\left(\begin{array}{cc} \sigma_{N-1} & \sigma_{N-1} \\ \sigma_{N-1} & -\sigma_{N-1} \end{array}\right) \left(\begin{array}{cc} \Pi_X & 0 \\ 0 & \Pi_I \end{array}\right) $$The rightmost unitary $\left(\begin{array}{cc} \Pi_X & 0 \\ 0 & \Pi_I \end{array}\right)$ is actually a zero-controlled $X^{\otimes N-1}$ gate; to make it a regular controlled $X$ gate we apply $X$ on the least significant qubit before and after transformation:
$$U = \left(\begin{array}{cc} \Pi_I & 0 \\ 0 & \Pi_X \end{array}\right) \frac{1}{\sqrt{2}}\left(\begin{array}{cc} \sigma_{N-1} & \sigma_{N-1} \\ \sigma_{N-1} & -\sigma_{N-1} \end{array}\right) (X \otimes I_{N-1}) \left(\begin{array}{cc} \Pi_I & 0 \\ 0 & \Pi_X \end{array}\right) (X \otimes I_{N-1})$$We can rewrite the middle unitary $U'$ as
$$U'=\frac{1}{\sqrt{2}}\left(\begin{array}{cc} \sigma_{N-1} & \sigma_{N-1} \\ \sigma_{N-1} & -\sigma_{N-1} \end{array}\right) = H \otimes \sigma_{N-1}$$Thus
$$U=(CX^{\otimes N-1})(H \otimes \sigma_{N-1})(X \otimes I_{N-1})(CX^{\otimes N-1})(X \otimes I_{N-1})$$%kata T13_TIE_Fighter
operation TIE_Fighter (qs : Qubit[]) : Unit {
let n = Length(qs);
// the rightmost unitary: zero-controlled X gate
X(qs[n-1]);
ApplyToEach(CNOT(qs[n-1], _), qs[0..n-2]);
X(qs[n-1]);
// decrement operation
X(qs[0]);
for i in 1..Length(qs)-2 {
Controlled X (qs[0..i-1], qs[i]);
}
H(qs[n-1]);
// the leftmost unitary: controlled X gate
ApplyToEach(CNOT(qs[n-1], _), qs[0..n-2]);
}
Input: 3 qubits in an arbitrary state.
Goal: Implement a unitary transformation on 3 qubits which is represented by a matrix with non-zero elements in the following pattern:
XX....XX
XX....XX
...XX...
...XX...
..X..X..
..X..X..
XX....XX
XX....XX
*There are shorter, more efficient methods for generating the required pattern.
However, this method assumes minimum prior knowledge except the tasks in the workbook.*
To create the "Creeper" unitary $U$, we start with $U'=\begin{bmatrix} x & x & . & . & . & . & x & x \\ x & x & . & . & . & . & x & x \\ . & . & x & . & . & x & . & . \\ . & . & . & x & x & . & . & . \\ . & . & . & x & x & . & . & . \\ . & . & x & . & . & x & . & . \\ x & x & . & . & . & . & x & x \\ x & x & . & . & . & . & x & x \end{bmatrix} $.
$U'$ has the same symmetry as task 13, which we can exploit to simplify $U'$.
We label the bottom-right quarter of $U'$ as $V = \begin{bmatrix} x & . & . & . \\ . & x & . & . \\ . & . & x & x \\ . & . & x & x \end{bmatrix} $. We can implement the $V$ gate as the controlled $H$ gate.
$$U'=\left(\begin{array}{cc} \Pi_X & 0 \\ 0 & \Pi_I \end{array}\right) \frac{1}{\sqrt{2}}\left(\begin{array}{cc} V & V \\ V & -V \end{array}\right) \left(\begin{array}{cc} \Pi_X & 0 \\ 0 & \Pi_I \end{array}\right) = (C^{-}X^{\otimes 2})(H \otimes V)(C^{-}X^{\otimes 2})$$The $C^{-}X^{\otimes 2}$ means zero-controlled $X^{\otimes 2}$ gate.
After completing construction of the $U'$ gate, we now apply a cyclic rotation to the middle $4 \times 4$ block:
$$R'= \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}$$$R'$ can be implemented using $3$ $X$ gates, $3$ $CNOT$ gates and $1$ $CCNOT$ gate. The transformation leaves outer $4$ computational states intact and shifts the inner $4$ computational states by 1. $$ R'U' = \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & \frac{-1}{2} & 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{-1}{2} \\ 0 & 0 & \frac{1}{\sqrt{2}} & 0 & 0 & \frac{1}{\sqrt{2}} & 0 & 0 \\ 0 & 0 & 0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & 0 & 0 & 0 \\ 0 & 0 & 0 & \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} & 0 & 0 & 0 \\ 0 & 0 & \frac{1}{\sqrt{2}} & 0 & 0 & \frac{-1}{\sqrt{2}} & 0 & 0 \\ \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 & 0 & \frac{-1}{2} & \frac{-1}{2} \\ \frac{1}{2} & \frac{-1}{2} & 0 & 0 & 0 & 0 & \frac{-1}{2} & \frac{1}{2} \end{bmatrix} = \begin{bmatrix} \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & \frac{-1}{2} & 0 & 0 & 0 & 0 & \frac{1}{2} & \frac{-1}{2} \\ 0 & 0 & 0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & 0 & 0 & 0 \\ 0 & 0 & 0 & \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} & 0 & 0 & 0 \\ 0 & 0 & \frac{1}{\sqrt{2}} & 0 & 0 & \frac{-1}{\sqrt{2}} & 0 & 0 \\ 0 & 0 & \frac{1}{\sqrt{2}} & 0 & 0 & \frac{0}{\sqrt{2}} & 0 & 0 \\ \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 & 0 & \frac{-1}{2} & \frac{-1}{2} \\ \frac{1}{2} & \frac{-1}{2} & 0 & 0 & 0 & 0 & \frac{-1}{2} & \frac{1}{2} \end{bmatrix}$$
We can see that $R'U'$ is the required pattern $U$: $$U= R'U' = R'(C^{-}X^{\otimes 2})(H \otimes V)(C^{-}X^{\otimes 2})$$
Now we have to implement $R'$
$$R'= \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \end{bmatrix} \begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \end{bmatrix} $$We observe that $R'$ is the product of 3 matrices, in which leftmost and rightmost are the adjoint of one-another. The matrix in the middle is a controlled "increment by 1" matrix. Let $W=\begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{bmatrix} \begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} = CNOT'(I \otimes X) $. Here the $CNOT'$ gate has least significant qubit as control and most significant qubit as target.
Finally $R'= (W \otimes I)(CW)(W \otimes I)^{\dagger}$, where $CW$ is the controlled version of the $W$ gate.
We'll need to use a separate cell to define two helper operations.
// W unitary: decrements the basis states modulo 4
operation W (qs : Qubit[]) : Unit is Adj + Ctl {
X(qs[0]);
CNOT(qs[0],qs[1]); // Control is LSB and Target is MSB
}
// R' unitary: performs rotation of the 4 middle basis vectors
operation Rotation (qs : Qubit[]) : Unit {
Adjoint W(qs[1..2]);
Controlled W([qs[2]], qs[0..1]);
W(qs[1..2]);
}
%kata T14_Creeper
operation Creeper(qs : Qubit[]) : Unit {
X(qs[2]);
Controlled ApplyToEachCA([qs[2]], (X, qs[0 .. 1])); // Negatively Controlled Not Gates
X(qs[2]);
H(qs[2]);
Controlled H([qs[1]], qs[0]); // Central Transformation
X(qs[2]);
Controlled ApplyToEachCA([qs[2]], (X, qs[0 .. 1])); // Negatively Controlled Not Gates
X(qs[2]);
Rotation(qs); // Rotation
}
Input: N qubits in an arbitrary state ($2 \leq N \leq 4$).
Goal: Implement a unitary transformation on N qubits which is represented by a matrix with non-zero elements forming an upper diagonal matrix plus the first subdiagonal. This is called a Hessenberg matrix.
Example: For N = 2, the matrix of the transformation should look as follows:
XXXX
XXXX
.XXX
..XX
For N = 3, the matrix of the transformation should look as follows:
XXXXXXXX
XXXXXXXX
.XXXXXXX
..XXXXXX
...XXXXX
....XXXX
.....XXX
......XX
Our strategy will be to implement a matrix with Hessenberg structure as a product of several unitary matrices that differ from the identity only in a $2\times 2$ subblock.
Let $i \in \{0, \ldots, 2^n-2\}$ denote an index. Consider operations of the form $T_N(i)$, where the $(i,i)$, $(i,i+1)$, $(i+1,i)$ and $(i+1,i+1)$ together form a $2 \times 2$ square submatrix of non-zero entries (denoted by $*$):
$$ T_N(i) = \begin{bmatrix} 1 & & & & & & & \\ & \ddots & & & & & & \\ & & 1 & & & & & \\ & & & * & * & & & \\ & & & * & * & & & \\ & & & & & 1 & & \\ & & & & & & \ddots & \\ & & & & & & & 1 \end{bmatrix}$$We can choose the Hadamard $H$ for creating the $2 \times 2$ submatrix.
For example, for $N=3$ and $i=0$ we have
$$ T_3(0) = \begin{bmatrix}
\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & 0 & 0 & 0 & 0 & 0 & 0 \ \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} & 0 & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}$$
Such an operation can be mapped to a multiply-controlled gate by first permuting the rows and columns of the matrix. Specifically, we can map $i$ to the bit string $1 1 \ldots 1 0$ and $i+1$ to the bit string $1 1 \ldots 1 1 $. Then the resulting operation can be implemented by a multiply controlled $H$ gate with the last qubit as target and remaining qubits acting as controls.
We now utilize the fact that a Hessenberg unitary $U_N$ can be factored as $ U_N = T_N(0) T_N(1) T_N(2) ... T_N(2^N-2)$.
For the simple case of $N=2$,
$$U_2 = T_2(0) T_2(1) T_2(2) = \\ = \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & 0 & 0 \\ \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & 0 \\ 0 & \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} & 0 \\ 0 & 0 & 0 & 1 \\\end{bmatrix} \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ 0 & 0 & \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} \\ \end{bmatrix} = \\ = \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{2} & \frac{1}{2\sqrt{2}} & \frac{1}{2\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{-1}{2} & \frac{-1}{2\sqrt{2}} & \frac{-1}{2\sqrt{2}} \\ 0 & \frac{-1}{\sqrt{2}} & \frac{-1}{2} & \frac{-1}{2} \\ 0 & 0 & \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} \end{bmatrix} $$open Microsoft.Quantum.Convert;
// Performs a rotation to move basis states i to 111...10 and i+1 to 111...11 (in big endian notation)
operation RotateToEnd (index: Int, qs : Qubit[]) : Unit is Adj{
let n = Length(qs);
let bits1 = IntAsBoolArray(index, n);
let bits2 = IntAsBoolArray(index + 1, n);
let diff = 0; // The index of the first bit at which the bit strings are different is 0 (successive indexes)
// we care only about 2 inputs: basis state of bits1 and bits2
// make sure that the state corresponding to bits1 has qs[diff] set to 0
if bits1[diff] {
X(qs[diff]);
}
// iterate through the bit strings again, setting the final state of qubits
for i in 0 .. n-1 {
if bits1[i] == bits2[i] { // if two bits are the same, set both to 1 using X or nothing
if not bits1[i] {
X(qs[i]);
}
} else { // if two bits are different, set both to 1 using CNOT
if i > diff {
if not bits1[i] {
X(qs[diff]);
CNOT(qs[diff], qs[i]);
X(qs[diff]);
}
if not bits2[i] {
CNOT(qs[diff], qs[i]);
}
}
}
}
if diff < n-1 {
SWAP(qs[n-1], qs[diff]); // move the differing bit to the last qubit
}
}
%kata T15_Hessenberg_Matrix
open Microsoft.Quantum.Arrays;
operation Hessenberg_Matrix (qs : Qubit[]) : Unit {
let n = Length(qs);
for i in 2^n - 2 .. -1 .. 0{
RotateToEnd(i, qs);
(Controlled H)(Most(qs), Tail(qs));
(Adjoint RotateToEnd)(i, qs);
}
}
These exercises show you how to prepare certain unitary patterns using single-qubit and multi-qubit gates. These tricks, from representing larger matrices as tensor products of smaller matrices to permuting the rows and columns of matrices to make implementation easier, are widely used when implementing specific matrices required by more advanced algorithms.