\documentclass[pra,notitlepage]{revtex4-1} \usepackage[utf8]{inputenc} \usepackage{tikz} \usepackage[strict,uselistings]{revquantum} \newaffil{MSRQuArC}{ Quantum Architectures and Computation Group, Microsoft Research, Redmond, WA, United States } \theoremstyle{definition} \newtheorem{task}{Task} \newtheoremstyle{solution}% {\topsep}{\topsep}{\normalfont}{}% {\itshape}{.}{5pt}{} \theoremstyle{solution} \newtheorem*{solution}{Solution} \usepackage[bold]{hhtensor} \usepackage{qsharp} % Provide shorthand for verbatim Q# snippets. % We'll do similar for nwchem after we're done using the @ sign. \lstMakeShortInline[style=QSharp]" % Technique from https://tex.stackexchange.com/a/378606/615. \usepackage{listingsutf8} \lstset{ language = QSharp, inputencoding = utf8, extendedchars = true, numbers = none, columns = fullflexible, basicstyle = \ttfamily, keepspaces = true, literate = {⟩}{{\lstrangle}}1 {*}{{\char42}}1 {-}{{\char45}}1 } \protected\def\lstrangle{\ensuremath{\rangle}} \DeclareUnicodeCharacter{27E9}{\lstrangle} \usepackage{verbatimbox} \newcommand{\onemat}{\mathbf{1}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} \title{Microsoft Q\# Coding Contest - Winter 2019 - Main Contest\\ March 1-4, 2019} \author{Mariia Mykhailova} \affilMSRQuArC \author{Martin Roetteler} \affilMSRQuArC \maketitle %============================================================================= \section*{Tasks and Solutions} %============================================================================= %============================================================================= \subsection*{A1. Generate state 00 + 01 + 10 } %============================================================================= You are given two qubits in state $|00 \rangle$. Your task is to create the following state on them: $$\frac{1}{\sqrt{3}} \big( |00 \rangle + |01 \rangle + |10 \rangle)$$ You have to implement an operation which takes an array of 2 qubits as an input and has no output. The "output" of your solution is the state in which it left the input qubits. \begin{solution} This was one of the easier problems in the contest, and allowed plenty of different solutions. The straightforward solution is based on rotations and is described nicely in \href{https://quantumcomputing.stackexchange.com/a/2313/}{this StackExchange answer}: start with the state $|00\rangle$, rotate the first qubit to get $\big( \frac{\sqrt{2}}{\sqrt{3}} |0\rangle + \frac{1}{\sqrt{3}} |1\rangle \big) \otimes |0\rangle$, and end with a controlled operation which applies a Hadamard gate to the second qubit if the first qubit is in $|0\rangle$ state. \lstinputlisting[ style=QSharp, caption={Generate state $|00\rangle + |01\rangle + |10\rangle$ - rotation solution} ]{solutions/A1_1.qs} Another solution doesn't require calculating rotation angles, and uses post-selection instead. You start by generating an equal superposition of all basis states $\frac{1}{2} \big( |00\rangle + |01\rangle + |10\rangle + |11\rangle \big)$ using two Hadamard gates. After that you allocate an extra qubit and do a controlled X gate with that qubit as target and the original qubits as controls to get a state $\frac{1}{2} \big( |00\rangle + |01\rangle + |10\rangle \big) \otimes |0\rangle + \frac{1}{2} |11\rangle \otimes |1\rangle$. Now, consider what happens if you measure the last qubit? If the measurement result is 1, the first two qubits collapse to the state $|11\rangle$, which is not useful. However, if the measurement result is 0, the first two qubits collapse to the state $\frac{1}{\sqrt{3}} \big( |00\rangle + |01\rangle + |10\rangle \big)$, which is exactly the state we need! The probability of getting the right state on the first try is 75\%. You can use repeat-until-success loop to repeat the process until you get the necessary state. \lstinputlisting[ style=QSharp, caption={Generate state $|00\rangle + |01\rangle + |10\rangle$ - post-selection solution} ]{solutions/A1_2.qs} Finally, you can use a library operation to prepare the necessary state. \href{https://docs.microsoft.com/en-us/qsharp/api/canon/microsoft.quantum.canon.prepareuniformsuperposition}{PrepareUniformSuperposition} prepares a uniform superposition of the basis states that encode numbers 0 through $M - 1$, which is exactly the required state for $M = 3$. \lstinputlisting[ style=QSharp, caption={Generate state $|00\rangle + |01\rangle + |10\rangle$ - library operation} ]{solutions/A1_3.qs} \end{solution} %============================================================================= \subsection*{A2. Generate equal superposition of four basis states } %============================================================================= You are given $N$ qubits in the zero state $|0...0 \rangle$. You are also given four distinct bit vectors which describe four different basis states on $N$ qubits $|\psi_i \rangle$. Your task is to generate a state which is an equal superposition of the given basis states: $$|S \rangle = \frac{1}{2} \big( |\psi_0 \rangle + |\psi_1 \rangle + |\psi_2 \rangle + |\psi_3 \rangle \big)$$ You have to implement an operation which takes the following inputs: \begin{itemize} \item an array of $N$ ($2 \le N \le 16$) qubits, \item a two-dimensional array of Boolean values $bits$ representing the basis states $|\psi_i \rangle$. $bits$ will have exactly 4 elements, each of $bits[i]$ describing the basis state $|\psi_i \rangle$. Each of $bits[i]$ will have $N$ elements, $bits[i][j]$ giving the state of qubit $j$ in the basis state $|\psi_i \rangle$. Bit values true and false corresponding to $|1 \rangle$ and $|0 \rangle$ states, respectively; for example, for $N = 2$ an array \texttt{[false, true]} will represent the basis state $|01\rangle$. Each pair of $bits[i]$ and $bits[j]$ will differ in at least one position for $i \neq j$. \end{itemize} The operation doesn't have an output; its "output" is the state in which it leaves the qubits. \begin{solution} This problem builds up on the \href{https://codeforces.com/contest/1002/problem/A3}{problem A3 from Q\# Coding Contest - Summer 2018}. In it you had to generate an equal superposition of two basis states; in this task you have to generate an equal superposition of four basis states. However, the approach remains similar: you can allocate extra qubits (one qubit if you need a superposition of two states, two qubits if you need a superposition of four states), use them to put the main qubits into the required superposition, and then uncompute the extra qubits to return them to 0 state before releasing them (you can not just measure them, since that would destroy the superposition you worked so carefully to build, and leave you with just one of the states instead). \lstinputlisting[ style=QSharp, caption={Generate equal superposition of four basis states} ]{solutions/A2.qs} \end{solution} %============================================================================= \subsection*{B1. Distinguish three-qubit states} %============================================================================= You are given 3 qubits which are guaranteed to be in one of the two states: \begin{itemize} \item $|\psi_0\rangle = \frac{1}{\sqrt{3}} \big( |100\rangle + \omega |010\rangle + \omega^2|001\rangle \big)$, or \item $|\psi_1\rangle = \frac{1}{\sqrt{3}} \big( |100\rangle + \omega^2 |010\rangle + \omega|001\rangle \big)$, where $\omega = e^{2i\pi/3}$. \end{itemize} Your task is to perform necessary operations and measurements to figure out which state it was and to return 0 if it was $|\psi_0\rangle$ state or 1 if it was $|\psi_1\rangle$ state. The state of the qubits after the operations does not matter. \begin{solution} Let's start by considering how we would prepare one of these states, starting with the $|000\rangle$ state. You can start by preparing the W state on 3 qubits (\href{https://codeforces.com/contest/1002/problem/A4}{problem A4 from Q\# Coding Contest - Summer 2018}), and then adjust their phases using appropriate rotations on some of the qubits (\href{https://docs.microsoft.com/en-us/qsharp/api/prelude/microsoft.quantum.primitive.r1}{R1} gate is really indispensable for this - it is vastly more convenient than the more standard Rz rotations). Now, back to the task at hand: how to distinguish the given states? They look very similar, and it might take some effort even to convince yourself that they are indeed orthogonal (they are). We need to find an operation which will transform them into a pair of states which can be distinguished more obviously. It would be nice, for example, to transform one of the states into the $|000\rangle$ state, and the second one into... Actually, it doesn't matter what exactly the second state is transformed into - we know that the states $|\psi_0\rangle$ and $|\psi_1\rangle$ started orthogonal, and if the transformation we use is a unitary transformation $U$, it preserves inner products, so the states $U |\psi_0\rangle$ and $U |\psi_1\rangle$ are guaranteed to be orthogonal! If we choose $U$ in such a way that $U |\psi_0\rangle = |000\rangle$, we know that $U |\psi_1\rangle$ will be some superposition of basis states, neither of which will be $|000\rangle$. Then we'll need to distinguish the $|000\rangle$ state from such superposition, which is really easy - you can measure each qubit and check if all of the measurement results are 0 or if one or more of them are 1s. As for the transformation $U$, we can use an adjoint of the preparation routine we described in the first paragraph: if a routine transforms $|000\rangle$ into $|\psi_0\rangle$, its adjoint will transform $|\psi_0\rangle$ into $|000\rangle$. \lstinputlisting[ style=QSharp, caption={Distinguish three-qubit states} ]{solutions/B1.qs} \end{solution} %============================================================================= \subsection*{B2. Not A, not B or not C?} %============================================================================= You are given a qubit which is guaranteed to be in one of the following states: \begin{itemize} \item $|A\rangle = \frac{1}{\sqrt{2}} \big( |0\rangle + |1\rangle \big)$, \item $|B\rangle = \frac{1}{\sqrt{2}} \big( |0\rangle + \omega |1\rangle \big)$, or \item $|C\rangle = \frac{1}{\sqrt{2}} \big( |0\rangle + \omega^2 |1\rangle \big)$, where $\omega = e^{2i\pi/3}$. \end{itemize} These states are not orthogonal, and thus can not be distinguished perfectly. Your task is to figure out in which state the qubit is \textit{not}. More formally: \begin{itemize} \item If the qubit was in state $|A\rangle$, you have to return 1 or 2. \item If the qubit was in state $|B\rangle$, you have to return 0 or 2. \item If the qubit was in state $|C\rangle$, you have to return 0 or 1. \item In other words, return 0 if you're sure the qubit was \textit{not} in state $|A\rangle$, return 1 if you're sure the qubit was \textit{not} in state $|B\rangle$, and return 2 if you're sure the qubit was \textit{not} in state $|C\rangle$. \end{itemize} Your solution will be called 1000 times, each time the state of the qubit will be chosen as $|A\rangle$, $|B\rangle$ or $|C\rangle$ with equal probability. The state of the qubit after the operations does not matter. \begin{solution} The task is a simple game inspired by a quantum detection problem due to Holevo \cite{Holevo:1973} and Peres/Wootters \cite{PW:1991}. In the game, a player A thinks of a number (0,1 or 2) and the opponent, player B, tries to guess any number but the one chosen by player A. Classically, if you just made a guess, you'd have to ask two questions to be right $100\%$ of the time. If instead, player A prepares a qubit with 0, 1, or 2 encoded into three single qubit states that are at an angle of 120 degrees with respect to each other and then hands the state to the opponent, then player B can apply a Positive Operator Valued Measure (POVM) consisting of 3 states that are perpendicular to the states chosen by player A. It can be shown that this allows B to be right $100\%$ of the time with only 1 measurement, which is something that is not achievable with a von Neumann measurement on 1 qubit. See also Peres' book \cite[Chapter 9.6]{Peres:2002} for a nice description of the optimal POVM. Next, we address how we can implement the mentioned POVM by way of a von Neumann measurement, and then how to implement said von Neumann measurement in Q\#. First, we arrange the given vectors into columns of a matrix: \[ M = \frac{1}{\sqrt{2}}\left(\begin{array}{rrr} 1 & 1 & 1 \\ 1 & \omega & \omega^2 \end{array} \right), \] where $\omega = \exp(2 \pi i/3)$ denotes a primitive $3$rd root of unity. Our task will be to implement the rank 1 POVM given by vectors $v_1$, $v_2$, $v_3$ that live in the space of $2$ qubits and are perpendicular to the columns of $M$. How can a vector with $4$ components (such as the $v_i$) be orthogonal to a vector with only two components (such as the columns of $M$)? The answer is that we will have to ``pad'' the vectors in $M$ with two additional components, both being $0$. In one final (minor) complication, we need to add a fourth vector $v_4$ and make sure that together, $v_1 \ldots, v_4$ form an orthonormal basis so that we can implement them using a von Neumann measurement. We can for instance pick the following choice for $v_1, \ldots, v_4$, arranged into the rows of a unitary matrix: \[ U = \frac{1}{\sqrt{3}}\left(\begin{array}{cccc} 1 & -1 & 1 & 0 \\ 1 & -\omega^2 & \omega & 0 \\ 1 & -\omega & \omega^2 & 0 \\ 0 & 0 & 0 & -i \sqrt{3} \end{array} \right). \] Notice that indeed applying $U$ to input states given by column $i$ of $M$ (padded with two zeros to make it a vector of length $4$), where $i=0, 1, 2$ will never return the label $i$ as the corresponding vectors are perpendicular. We are therefore left with the problem of implementing $U$ as a sequence of elementary quantum gates. Notice that $U \cdot {\rm diag}(1,-1,1,-1)$ is equal to \[ U \cdot (\onemat_2 \otimes Z) = \frac{1}{\sqrt{2}}\left(\begin{array}{cccc} 1 & 1 & 1 & 0 \\ 1 & \omega^2 & \omega & 0 \\ 1 & \omega & \omega^2 & 0 \\ 0 & 0 & 0 & i \sqrt{3} \end{array} \right). \] Using a technique used in the Rader (also sometimes called Rader-Winograd) decomposition of the discrete Fourier transform \cite{Rader:1968}, which reduces it to a cyclic convolution, we apply a $2\times 2$ Fourier transform on the indices $i,j=1,2$ of this matrix (i.e. a block matrix which consists of a direct sum of blocks $\onemat_1$, $H$, and $\onemat_1$ which we abbreviate in short as ${\rm diag}(1,H,1)$). This yields \[ {\rm diag}(1, H, 1) \cdot U \cdot (\onemat_2 \otimes Z) \cdot {\rm diag}(1, H, 1) = \left(\begin{array}{rrrr} 1/\sqrt{3} & \sqrt{2/3} & 0 & 0 \\ \sqrt{2/3} & -1/\sqrt{3}& 0 & 0 \\ 0 & 0 & i & 0 \\ 0 & 0 & 0 & i \end{array} \right). \] This implies that after multiplication with the diagonal operator $(S^\dagger \otimes \onemat_2)$, we are left with \[ {\rm diag}(1, H, 1) \cdot U \cdot (\onemat_2 \otimes Z) \cdot {\rm diag}(1, H, 1)\cdot (S^\dagger \otimes \onemat_2) = \left(\begin{array}{rrrr} 1/\sqrt{3} & \sqrt{2/3} & 0 & 0 \\ \sqrt{2/3} & -1/\sqrt{3}& 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{array} \right), \] which is a (zero-)controlled rotation $R$ around the $Y$-axis by an angle given by $\arccos(\sqrt{2/3})$. Putting everything together, i.e., by applying the inverses of gates so that we find that \[ U = {\rm diag}(1,H,1) \cdot R \cdot (S \otimes \onemat_2) \cdot {\rm diag}(1,H,1) \cdot (\onemat_2 \otimes Z). \] Noting finally, that to apply this sequence of unitaries to a column vector, we have to apply it in reverse when writing it as a program (as actions on vectors are left-associative). After applying a circuit identity that simplifies the resulting circuit after implementing ${\rm diag}(1,H,1)$ via controlled $H$, we arrive at the listing shown below. \lstinputlisting[ style=QSharp, caption={Not A, not B or not C?} ]{solutions/B2.qs} \end{solution} %============================================================================= \subsection*{C1. Alternating bits oracle} %============================================================================= Implement a quantum oracle on $N$ qubits which checks whether the bits in the input vector $\vec{x}$ alternate (i.e., implements the function $f(\vec{x}) = 1$ if $\vec{x}$ does not have a pair of adjacent bits in state 00 or 11). You have to implement an operation which takes the following inputs: \begin{itemize} \item an array of $N$ ($1 \le N \le 7$) qubits $x$ in an arbitrary state (input register), \item a qubit $y$ in an arbitrary state (output qubit), \end{itemize} and performs a transformation $|x\rangle|y\rangle \rightarrow |x\rangle|y \oplus f(x)\rangle$. The operation doesn't have an output; its "output" is the state in which it leaves the qubits. Note that the input register $x$ has to remain unchanged after applying the operation. You are not allowed to use measurements in your operation. \begin{solution} This was another one of the easiest problems in the contest, and it could have been solved in multiple way. The easiest way was to follow the approach used in the task 1.2 of the \href{https://github.com/Microsoft/QuantumKatas/blob/master/GroversAlgorithm/ReferenceImplementation.qs#L34}{GroversAlgorithm kata}: find the states which are marked by the oracle and mark them using controlled X gates. This oracle marks only two states - the state 01010... and the state 10101..., so arranging the states of the qubits into these patterns and marking them is very straightforward. \lstinputlisting[ style=QSharp, caption={Alternating bits oracle} ]{solutions/C1.qs} \end{solution} %============================================================================= \subsection*{C2. ``Is the bit string periodic?'' oracle} %============================================================================= Implement a quantum oracle on $N$ qubits which checks whether the bits in the input vector $\vec{x}$ form a periodic bit string (i.e., implements the function $f(\vec{x}) = 1$ if $\vec{x}$ is periodic, and 0 otherwise). A bit string of length $N$ is considered periodic with period $P$ ($1 \le P \le N - 1$) if for all $i \in [0, N - P - 1]$ $x_i = x_{i + P}$. Note that $P$ does not have to divide $N$ evenly; for example, bit string "01010" is periodic with period $P = 2$. You have to implement an operation which takes the following inputs: \begin{itemize} \item an array of $N$ ($2 \le N \le 7$) qubits $x$ in an arbitrary state (input register), \item a qubit $y$ in an arbitrary state (output qubit), \end{itemize} and performs a transformation $|x\rangle|y\rangle \rightarrow |x\rangle|y \oplus f(x)\rangle$. The operation doesn't have an output; its output is the state in which it leaves the qubits. Note that the input register $x$ has to remain unchanged after applying the operation. \begin{solution} Let's start by considering a simpler problem: is the bit string periodic with period $P$? This problem is similar to the \href{https://codeforces.com/contest/1115/problem/G3}{problem G3 of the warmup round}: in that problem you had to compare the states of the qubits in symmetrical positions, and in this one you have to compare the states of the qubits at a distance $P$ from each other. If you can solve this sub-task, you can express the required oracle as ``the bit string periodic with period 1'' OR ``the bit string periodic with period 2'' OR ... OR ``the bit string periodic with period $N-1$''. Constructing this kind of expressions has been covered in the \href{https://codeforces.com/contest/1115/problem/G2}{problem G2 of the warmup round}. Conceptually the solution is not very elaborate, if somewhat bulky: you have to allocate extra qubits to store the evaluation results for each period, and you need to get those results in the first place. One had to be rather careful when implementing it, though - some straightforward approaches like allocating qubits for comparing individual qubits could quickly become too slow to run in time for the larger values of $N$. To fit the execution within the time limit, you had to do qubit comparison for evaluating the period in-place, using CNOTs: you would iterate over the qubits and store XOR of the states of qubits $i$ and $i + P$ in qubit $i$. After that, the bit string would be periodic if all pairs of states were equal, qubits $0$ through $N-P-1$ would all be in state 0. You can extract this information into the ancilla allocated for period $P$ and uncompute the qubit states. This approach would pass the tests, but it would take more than half of the time limit on the largest test. It can be optimized further to speed it up by another factor of 2: you don't need to consider period 1, since any string periodic with period 1 will also be periodic with period 2 (unless $N = 2$, in which case period of 2 is not valid). You don't need to consider period 2, unless $N \le 4$, and so on. \lstinputlisting[ style=QSharp, caption={``Is the bit string periodic?'' oracle} ]{solutions/C2.qs} \end{solution} %============================================================================= \subsection*{C3. ``Is the number of ones divisible by 3?'' oracle} %============================================================================= Implement a quantum oracle on $N$ qubits which checks whether the number of bits equal to 1 in the input vector $\vec{x}$ is divisible by 3 (i.e., implements the function $f(\vec{x}) = 1$ if the number of $x_i = 1$ in $\vec{x}$ is divisible by 3, and 0 otherwise). You have to implement an operation which takes the following inputs: \begin{itemize} \item an array of $N$ ($1 \le N \le 9$) qubits $x$ in an arbitrary state (input register), \item a qubit $y$ in an arbitrary state (output qubit), \end{itemize} and performs a transformation $|x\rangle|y\rangle \rightarrow |x\rangle|y \oplus f(x)\rangle$. The operation doesn't have an output; its output is the state in which it leaves the qubits. Note that the input register $x$ has to remain unchanged after applying the operation. \begin{solution} As usual, start by considering simpler versions of the problem. To check whether the number of bits equal to 1 is divisible by 2, you can just iterate over the input qubits and do a sequence of CNOTs with each of them as controls and the output qubit as the target. The fact that CNOT does a controlled flip of the state makes sure that this is the same as taking sum of the bits modulo 2, so in the end you just flip it again to become 1 if the sum modulo 2 was 0. You can use the same approach here, but you need to implement addition modulo 3 as an elementary operation. To do this, you allocate two extra qubits (``sum'' and ``carry'') and figure out the rules of updating them in a way which allows to go from $|00\rangle$ to $|10\rangle$ to $|01\rangle$ to $|00\rangle$ upon each addition. You can see one possible set of rules below. If both extra qubits end up in 0 state, the number of 1s is divisible by 3. \lstinputlisting[ style=QSharp, caption={``Is the number of ones divisible by 3?'' oracle} ]{solutions/C3.qs} \end{solution} %============================================================================= \subsection*{D1. Block diagonal matrix} %============================================================================= Implement a unitary operation on $N$ qubits which is represented by a square matrix of size $2^N$ which has 2x2 blocks of non-zero elements on the main diagonal and zero elements everywhere else. For example, for $N = 3$ the matrix of the operation should have the following shape: \begin{verbbox} XX...... XX...... ..XX.... ..XX.... ....XX.. ....XX.. ......XX ......XX \end{verbbox} \begin{figure}[ht] \centering \theverbbox \end{figure} Here and in the rest of D problems \texttt{X} denotes a "non-zero" element of the matrix (a complex number which has the square of the absolute value greater than or equal to $10^{-5}$), and \texttt{.} denotes a "zero" element of the matrix (a complex number which has the square of the absolute value less than $10^{-5}$). \begin{solution} This was the easiest problem of the contest. The \href{https://assets.codeforces.com/rounds/1115/warmup-editorial.pdf}{editorial} for \href{https://codeforces.com/contest/1115/problem/U2}{problem U2 of the warmup round} covered creating simple matrices which can be represented as tensor product of other matrices, so this pattern should be immediately recognizable as a tensor product $I_{N-1} \otimes H$. Remember that the indices are given in little endian, so the Hadamard gate has to be applied to the first qubit of the array. \lstinputlisting[ style=QSharp, caption={Block diagonal matrix} ]{solutions/D1.qs} \end{solution} %============================================================================= \subsection*{D2. Pattern of increasing blocks} %============================================================================= Implement a unitary operation on $N$ qubits which is represented by a square matrix of size $2^N$ defined as follows: \begin{itemize} \item top right and bottom left quarters are filled with zero elements, \item the top left quarter is the same pattern of size $2^{N-1}$ (for $N = 1$, the top left quarter is a non-zero element), \item the bottom right quarter is filled with non-zero elements. \end{itemize} For example, for $N = 3$ the matrix of the operation should have the following shape: \begin{verbbox} X....... .X...... ..XX.... ..XX.... ....XXXX ....XXXX ....XXXX ....XXXX \end{verbbox} \begin{figure}[ht] \centering \theverbbox \end{figure} \begin{solution} This task builds up on the \href{https://codeforces.com/contest/1115/problem/U3}{problem U3 of the warmup round}, which introduced constructing matrices which are composed of smaller quarters but can not be represented as a tensor product. It follows a very similar pattern. The bottom right block is the area where the most significant bit equals 1, and its effect on the qubits can be described as follows: if the last qubit of the input is in state $|1\rangle$, leave that qubit unchanged and apply a Hadamard gate to each of the rest of the qubits. The top left block is the area where the most significant bit equals 0, and its effect on the qubits can be described as follows: if the last qubit of the input is in state $|1\rangle$, leave that qubit unchanged and apply the same pattern to the rest of the qubits. You can use recursion without unrolling it if you add a definition of controlled variant to your operation. \lstinputlisting[ style=QSharp, caption={Pattern of increasing blocks} ]{solutions/D2.qs} \end{solution} %============================================================================= \subsection*{D3. X-wing fighter} %============================================================================= Implement a unitary operation on $N$ qubits which is represented by a square matrix of size $2^N$ which has non-zero elements on both main diagonal and anti-diagonal and zero elements everywhere else. For example, for $N = 3$ the matrix of the operation should have the following shape: \begin{verbbox} X......X .X....X. ..X..X.. ...XX... ...XX... ..X..X.. .X....X. X......X \end{verbbox} \begin{figure}[ht] \centering \theverbbox \end{figure} \begin{solution} \lstinputlisting[ style=QSharp, caption={X-wing fighter} ]{solutions/D3.qs} \end{solution} %============================================================================= \subsection*{D4. TIE fighter} %============================================================================= Implement a unitary operation on $N$ qubits which is represented by a square matrix of size $2^N$ which has non-zero elements in the following positions: \begin{itemize} \item the central 2x2 sub-matrix, \item the diagonals of the top right and bottom left square sub-matrices of size $2^{N-1}-1$ that do not overlap with the central 2x2 sub-matrix, \item the anti-diagonals of the top left and bottom right square sub-matrices of size $2^{N-1}-1$ that do not overlap with the central 2x2 sub-matrix. \end{itemize} For example, for $N = 3$ the matrix of the operation should have the following shape: \begin{verbbox} ..X..X.. .X....X. X......X ...XX... ...XX... X......X .X....X. ..X..X.. \end{verbbox} \begin{figure}[ht] \centering \theverbbox \end{figure} \begin{solution} We note first that one possible solution to this problem consists of a matrix \[ M = \frac{1}{\sqrt{2}}\left(\begin{array}{cc} \sigma \Pi_X & \sigma \\ \Pi_X \sigma \Pi_X & -\Pi_X \sigma \end{array}\right), \] where $\sigma = \sum_{i=0}^{2^n-1} \ket{i-1}\bra{i}$ is a decrementer by $1$ (indices are computed modulo $2^n$), and $\Pi_X = X^{\otimes n}$. This gives us everything we need in order to find a unitary matrix with the target pattern: We build our matrix $M$ as a Hadamard transform $(H \otimes {\onemat_2}^{\otimes {n-1}})$ on the most significant qubit, followed by a right multiplication of $\onemat_2 \otimes \sigma$. Next, notice that an incrementer can for instance be implemented via the following circuit, see \cite{RB:2011}: \bigskip \centerline{\unitlength0.8pt \thicklines \begin{picture}(30,120)(0,-10) \multiput(0,0)(0,20){2}{\line(1,0){30}} \multiput(0,60)(0,20){3}{\line(1,0){30}} \put(15,0){\circle*{4}} \put(15,20){\circle*{4}} \put(15,0){\line(0,1){30}} \put(15,60){\circle*{4}} \put(15,80){\circle*{4}} \put(15,100){\circle{10}} \put(15,105){\line(0,-1){55}} \multiput(15,35)(0,4){3}{\line(0,1){2}} \end{picture}% \begin{picture}(30,120)(0,-10) \multiput(0,0)(0,20){2}{\line(1,0){30}} \multiput(0,60)(0,20){3}{\line(1,0){30}} \put(15,0){\circle*{4}} \put(15,20){\circle*{4}} \put(15,0){\line(0,1){30}} \put(15,60){\circle*{4}} \put(15,80){\circle{10}} \put(15,85){\line(0,-1){35}} \multiput(15,35)(0,4){3}{\line(0,1){2}} \end{picture}% \begin{picture}(30,120)(0,-10) \multiput(0,0)(0,20){2}{\line(1,0){30}} \multiput(0,60)(0,20){3}{\line(1,0){30}} \put(15,0){\circle*{4}} \put(15,20){\circle*{4}} \put(15,0){\line(0,1){30}} \put(15,60){\circle{10}} \put(15,65){\line(0,-1){15}} \multiput(15,35)(0,4){3}{\line(0,1){2}} \end{picture}% \begin{picture}(37,120)(0,-10) \multiput(20,0)(0,20){2}{\makebox(0,0){$\cdots$}} \put(20,40){\makebox(0,0){$\ddots$}} \multiput(20,60)(0,20){3}{\makebox(0,0){$\cdots$}} \end{picture}% \begin{picture}(30,120)(0,-10) \multiput(0,0)(0,20){2}{\line(1,0){30}} \multiput(0,60)(0,20){3}{\line(1,0){30}} \put(15,0){\circle*{4}} \put(15,0){\line(0,1){25}} \put(15,20){\circle{10}} \end{picture}% \begin{picture}(30,120)(0,-10) \multiput(0,0)(0,20){2}{\line(1,0){30}} \multiput(0,60)(0,20){3}{\line(1,0){30}} \put(15,0){\circle{10}} \put(15,-5){\line(0,1){10}} \end{picture}% } \bigskip Finally, note that fixing the circuit so that we get the pattern of $M$ can be accomplished by applying controlled $X^{\otimes {n-1}}$ operators, which can be done by a cascade of CNOT gates. Overall, we obtain the listing shown below. \lstinputlisting[ style=QSharp, caption={TIE fighter} ]{solutions/D4.qs} \end{solution} %============================================================================= \subsection*{D5. Creeper} %============================================================================= Implement a unitary operation on 3 qubits which is represented by a square matrix of size 8 with the following pattern: \begin{verbbox} XX....XX XX....XX ...XX... ...XX... ..X..X.. ..X..X.. XX....XX XX....XX \end{verbbox} \begin{figure}[ht] \centering \theverbbox \end{figure} \begin{solution} To find a unitary matrix with this pattern, we first note that a matrix with the block structure \begin{verbbox} XXXX.... XXXX.... XXXX.... XXXX.... ....XX.. ....XX.. ......XX ......XX \end{verbbox} \begin{figure}[ht] \centering \theverbbox \end{figure} can easily be obtained from applying a Hadamard gate on the least significant qubit, followed by $H_0$ which is a (negatively) controlled $H \otimes H$ gate on the most significant qubit. The remaining task is to find a suitable permutation that permutes the blocks into the right positions. Noting that a controlled NOT from the middle qubit to the most significant qubit corresponds to a matrix with pattern \begin{verbbox} X... ...X ..X. .X.. \end{verbbox} we almost get the right pattern by simply applying ${\rm CNOT}(1,0) H_0 (\onemat_2 \otimes \onemat_2 \otimes H) {\rm CNOT}(1,0)$. The remaining issue is to re-map the entries in the middle block, which can be accomplished using a cyclic rotation of the corresponding block. The cyclic rotation in turn is implemented like the incrementer in Problem D4 and is applied conditionally on the most significant qubit being $1$. Overall, we get the following solution: \lstinputlisting[ style=QSharp, caption={Creeper} ]{solutions/D5.qs} \end{solution} %============================================================================= \subsection*{D6. Hessenberg matrix} %============================================================================= Implement a unitary operation on $N$ qubits which is represented by an upper Hessenberg matrix (a square matrix of size $2^N$ which has all zero elements below the first subdiagonal and all non-zero elements on the first subdiagonal and above it). For example, for $N = 2$ the matrix of the operation should have the following shape: \begin{verbbox} XXXX XXXX .XXX ..XX \end{verbbox} \begin{figure}[ht] \centering \theverbbox \end{figure} \begin{solution} 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 $s_1, s_2 \in \{0, \ldots, 2^n-1\}$ denote a pair of indices and consider operations of the form \bigskip \[ \renewcommand{\arraystretch}{0.1}% \setlength{\arraycolsep}{0.2em}% T(s_1, s_2) \quad = \quad \left( \begin{array}{*{11}{c}} \\ 1\\ & \ddots\\ && 1\\ &&& * \begin{picture}(0,0)% \put(-3,35){\vector(0,-1){24}}% \put(-3,40){\makebox(0,0)[b]{$ s_1$}}% \end{picture} &&&& *\begin{picture}(0,0)% \put(75,3){\vector(-1,0){70}}% \put(80,3){\makebox(0,0)[l]{$ s_1$}}% \put(-3,35){\vector(0,-1){24}}% \put(-3,40){\makebox(0,0)[b]{$ s_2$}}% \end{picture}\\ &&&& 1\\ &&&&& \ddots\\ &&&&&& 1\\ &&& * &&&& *\begin{picture}(0,0)% \put(75,3){\vector(-1,0){70}}% \put(80,3){\makebox(0,0)[l]{$ s_2$}}% \end{picture}\\ &&&&&&&& 1\\ &&&&&&&&& \ddots\\ &&&&&&&&&& 1\\ \ \end{array} \right), \] \bigskip where the ``$*$'' stand for non-zero entries. Any such operation can be mapped to a multiply-controlled gate by first permuting the rows and columns of the matrix. Specifically, we can map $s_1$ to the bit string $1 1 \ldots 1 0$ and $s_2$ to the bit string $1 1 \ldots 1 1 $, after which the resulting operation can be implemented by a multiply controlled gate of the submatrix given by the ``$*$'' entries. This strategy has been described also in \cite{Barenco:1995}. After implementing $T(s_1, s_2)$ in this fashion, we now utilize the fact that a unitary that has the form \begin{equation}\label{eq:givens} T(0,1) \cdot T(1,2) \cdot T(2,3) \cdot \ldots \cdot T(2^n-2, 2^n-1) \end{equation} will have Hessenberg form, provided that all ``$*$'' in the original $2\times 2$ submatrix are non-zero. We therefore arrive at the solution shown below which instantiates this idea where the submatrix is given by the $2 \times 2$ Hadamard gate. Note that as usual, when traversing products such as the one in eq.~(\ref{eq:givens}), the order in the corresponding program has to be reversed as we are acting on {\em column} vectors (on which the action is left-associative). \lstinputlisting[ style=QSharp, caption={Hessenberg matrix} ]{solutions/D6.qs} \end{solution} \begin{thebibliography}{9} \bibitem{Holevo:1973} A. Holevo. \newblock Information-theoretical aspects of quantum measurement. \newblock Problems of Information Transmission, vol. 9, no. 2, pp. 110–118 (1973) \bibitem{PW:1991} A. Peres and W. K. Wootters. \newblock Optimal detection of quantum information. \newblock Phys. Rev. Lett., vol. 66, pp. 1119-1122, Mar. 1991. \bibitem{Peres:2002} A. Peres. \newblock Quantum Theory: Concepts and Methods. \newblock Kluwer Academic Publishers, 2002. \bibitem{Rader:1968} C. M. Rader. \newblock Discrete Fourier transforms when the number of data samples is prime. \newblock Proc. IEEE 56, 1107–1108 (1968). \bibitem{RB:2011} G.~Alber, Th. Beth, M.~Horodecki, P.~Horodecki, R.~Horodecki, M.~Roetteler, H.~Weinfurter, and A.~Zeilinger. \newblock {\em Quantum Information: An Introduction to Basic Theoretical Concepts and Experiments}, volume 173 of {\em Springer Texts in Modern Physics}, Chapter {\em Quantum algorithms: Applicable Algebra and Quantum Physics}. \newblock Springer, 2001. \bibitem{Barenco:1995} A.~Barenco, et al. \newblock Elementary gates for quantum computation. \newblock Physical Review~A, 52(5):3457--3467, 1995. \end{thebibliography} \end{document}