The "QFT (Quantum Fourier Transform)" quantum kata is a series of exercises designed to teach you the basics of quantum Fourier transform (QFT). It covers implementing QFT and using it to perform simple state transformations.
Each task is wrapped in one operation preceded by the description of the task.
Your goal is to fill in the blank (marked with the // ...
comments)
with some Q# code that solves the task. To verify your answer, run the cell using Ctrl+Enter (⌘+Enter on macOS).
Within each section, tasks are given in approximate order of increasing difficulty; harder ones are marked with asterisks.
This sequence of tasks uses the implementation of QFT described in Nielsen & Chuang. All numbers in this kata use big endian encoding: most significant bit of the number is stored in the first (leftmost) bit/qubit.
Input:
A qubit in state $|\psi\rangle = x_0 |0\rangle + x_1 |1\rangle$.
Goal:
Apply QFT to this qubit, i.e., transform it to a state $\frac{1}{\sqrt{2}} \big((x_0 + x_1) |0\rangle + (x_0 - x_1) |1\rangle\big)$.
In other words, transform a basis state $|j\rangle$ into a state $\frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \cdot \frac{j}{2}}|1\rangle\big)$ .
%kata T11_OneQubitQFT
operation OneQubitQFT (q : Qubit) : Unit is Adj+Ctl {
// ...
}
Can't come up with a solution? See the explained solution in the QFT Workbook.
Inputs:
A qubit in state $|\psi\rangle = \alpha |0\rangle + \beta |1\rangle$.
An integer k $\geq$ 0.
Goal:
Change the state of the qubit to $\alpha |0\rangle + \beta \cdot e^{\frac{2\pi i}{2^{k}}} |1\rangle$.
Be careful about not introducing an extra global phase!
This is going to be important in the later tasks.
%kata T12_Rotation
operation Rotation (q : Qubit, k : Int) : Unit is Adj+Ctl {
// ...
}
Can't come up with a solution? See the explained solution in the QFT Workbook.
Inputs:
A qubit in state $|\psi\rangle = \alpha |0\rangle + \beta |1\rangle$.
An array of $n$ bits $[j_1, j_2, ..., j_n]$, stored as Int[]
($ j_k \in \{0,1\}$).
Goal:
Change the state of the qubit to $\alpha |0\rangle + \beta \cdot e^{2\pi i \cdot 0.j_1 j_2 ... j_n} |1\rangle$, where $0.j_1 j_2 ... j_n$ is a binary fraction, similar to decimal fractions:
$$0.j_1 j_2 ... j_n = j_1 \cdot \frac{1}{2^1} + j_2 \cdot \frac{1}{2^2} + ... j_n \cdot \frac{1}{2^n}$$%kata T13_BinaryFractionClassical
operation BinaryFractionClassical (q : Qubit, j : Int[]) : Unit is Adj+Ctl {
// ...
}
Can't come up with a solution? See the explained solution in the QFT Workbook.
Inputs:
A qubit in state $|\psi\rangle = \alpha |0\rangle + \beta |1\rangle$.
A register of $n$ qubits in state $|j_1 j_2 ... j_n\rangle$.
Goal:
Change the state of the input from $(\alpha |0\rangle + \beta |1\rangle) \otimes |j_1 j_2 ... j_n\rangle$ to $(\alpha |0\rangle + \beta \cdot e^{2\pi i \cdot 0.j_1 j_2 ... j_n} |1\rangle) \otimes |j_1 j_2 ... j_n\rangle$,
where $0.j_1 j_2 ... j_n$ is a binary fraction corresponding to the basis state $j_1 j_2 ... j_n$ of the register.
The register of qubits can be in superposition as well;
the behavior in this case is defined by behavior on the basis states and the linearity of unitary transformations.
%kata T14_BinaryFractionQuantum
operation BinaryFractionQuantum (q : Qubit, jRegister : Qubit[]) : Unit is Adj+Ctl {
// ...
}
Can't come up with a solution? See the explained solution in the QFT Workbook.
Input:
A register of $n$ qubits in state $|j_1 j_2 ... j_n \rangle$.
Goal:
Change the state of the register from $|j_1\rangle \otimes |j_2 ... j_n\rangle$ to $\frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \cdot 0.j_1 j_2 ... j_n} |1\rangle \big) \otimes |j_2 ... j_n\rangle$.
The register of qubits can be in superposition as well;
the behavior in this case is defined by behavior on the basis states and the linearity of unitary transformations.
%kata T15_BinaryFractionQuantumInPlace
operation BinaryFractionQuantumInPlace (register : Qubit[]) : Unit is Adj+Ctl {
// ...
}
Can't come up with a solution? See the explained solution in the QFT Workbook.
Input:
A register of $n$ qubits in state $|x_1 x_2 ... x_n \rangle$.
Goal:
Reverse the order of qubits, i.e., convert the state of the register to $|x_n ... x_2 x_1\rangle$.
%kata T16_ReverseRegister
operation ReverseRegister (register : Qubit[]) : Unit is Adj+Ctl {
// ...
}
Can't come up with a solution? See the explained solution in the QFT Workbook.
Input:
A register of $n$ qubits in state $|j_1 j_2 ... j_n \rangle$.
Goal:
Apply quantum Fourier transform to the input register, i.e., transform it to a state
$$\frac{1}{\sqrt{2^{n}}} \sum_{k=0}^{2^n-1} e^{2\pi i \cdot \frac{jk}{2^{n}}} |k\rangle = $$$$\begin{align}= &\frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \cdot 0.j_n} |1\rangle\big) \otimes \\ \otimes &\frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \cdot 0.j_{n-1} j_n} |1\rangle\big) \otimes ... \otimes \\ \otimes &\frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \cdot 0.j_1 j_2 ... j_{n-1} j_n} |1\rangle\big)\end{align}$$The register of qubits can be in superposition as well;
the behavior in this case is defined by behavior on the basis states and the linearity of unitary transformations.
You can do this with a library call, but we recommend
implementing the algorithm yourself for learning purposes, using the previous tasks.
$\frac{1}{\sqrt{2}} \big(|0\rangle + exp(2\pi i \cdot 0.j_1 j_2 ... j_{n-1} j_n) |1\rangle\big) \otimes ... \otimes \frac{1}{\sqrt{2}} \big(|0\rangle + exp(2\pi i \cdot 0.j_{n-1} j_n) |1\rangle\big) \otimes \frac{1}{\sqrt{2}} \big(|0\rangle + exp(2\pi i \cdot 0.j_n) |1\rangle\big)$
%kata T17_QuantumFourierTransform
operation QuantumFourierTransform (register : Qubit[]) : Unit is Adj+Ctl {
// ...
}
Can't come up with a solution? See the explained solution in the QFT Workbook.
Input:
A register of $n$ qubits in state $|j_1 j_2 ... j_n \rangle$.
Goal:
Apply inverse QFT to the input register, i.e., transform it to a state $\frac{1}{\sqrt{2^{n}}} \sum_{k=0}^{2^n-1} e^{-2\pi i \cdot \frac{jk}{2^{n}}} |k\rangle$.
%kata T18_InverseQFT
operation InverseQFT (register : Qubit[]) : Unit is Adj+Ctl {
// ...
}
Can't come up with a solution? See the explained solution in the QFT Workbook.
This section offers you tasks on state preparation and state analysis that can be solved using QFT (or inverse QFT). It is possible to solve them without QFT, but we recommend that you to try and come up with a QFT-based solution.
Input:
A register of $n$ qubits in state $|0...0\rangle$.
Goal:
Prepare an equal superposition of all basis vectors from $|0...0\rangle$ to $|1...1\rangle$ (i.e., state $\frac{1}{\sqrt{2^{n}}} \big(|0...0\rangle + ... + |1...1\rangle\big)$.
%kata T21_PrepareEqualSuperposition
operation PrepareEqualSuperposition (register : Qubit[]) : Unit is Adj+Ctl {
// ...
}
Can't come up with a solution? See the explained solution in the QFT Workbook.
Inputs:
A register of $n$ qubits in state $|0...0\rangle$.
An integer frequency F ($0 \leq F \leq 2^{n}-1$).
Goal:
Prepare a periodic state with frequency F on this register:
$$\frac{1}{\sqrt{2^{n}}} \sum_k e^{2\pi i \cdot \frac{Fk}{2^{n}}} |k\rangle$$For example, for $n = 2$ and $F = 1$ the goal state is $\frac{1}{2}\big(|0\rangle + i|1\rangle - |2\rangle - i|3\rangle\big)$.
If you're using
DumpMachine
to debug your solution,
remember that this kata uses big endian encoding of states,
while DumpMachine
uses little endian encoding.
You can use %config
magic command
to reconfigure DumpMachine
to use big endian encoding or bit strings.
%kata T22_PreparePeriodicState
operation PreparePeriodicState (register : Qubit[], F : Int) : Unit is Adj+Ctl {
// ...
}
Can't come up with a solution? See the explained solution in the QFT Workbook.
Input:
A register of $n$ qubits in state $|0...0\rangle$.
Goal:
Prepare a periodic state with alternating $1$ and $-1$ amplitudes of basis states:
$$\frac{1}{\sqrt{2^{n}}} \big(|0\rangle - |1\rangle + |2\rangle - |3\rangle + ... - |2^{n}-1\rangle\big)$$For example, for $n = 2$ the goal state is $\frac{1}{2} \big(|0\rangle - |1\rangle + |2\rangle - |3\rangle\big)$.
%kata T23_PrepareAlternatingState
operation PrepareAlternatingState (register : Qubit[]) : Unit is Adj+Ctl {
// ...
}
Can't come up with a solution? See the explained solution in the QFT Workbook.
Input:
A register of $n$ qubits in state $|0...0\rangle$.
Goal:
Prepare an equal superposition of all even basis vectors: $\frac{1}{\sqrt{2^{n-1}}} \big(|0\rangle + |2\rangle + ... + |2^{n}-2\rangle\big)$.
%kata T24_PrepareEqualSuperpositionOfEvenStates
operation PrepareEqualSuperpositionOfEvenStates (register : Qubit[]) : Unit is Adj+Ctl {
// ...
}
Can't come up with a solution? See the explained solution in the QFT Workbook.
Input:
A register of $n\geq2$ qubits in state $|0...0\rangle$.
Goal:
Prepare a periodic state with alternating $1, 1, -1, -1$ amplitudes of basis states: $$\frac{1}{\sqrt{2^{n}}} \big(|0\rangle + |1\rangle - |2\rangle - |3\rangle + ... - |2^{n}-2\rangle - |2^{n}-1\rangle\big)$$
%kata T25_PrepareSquareWaveSignal
operation PrepareSquareWaveSignal (register : Qubit[]) : Unit is Adj+Ctl {
// ...
}
Can't come up with a solution? See the explained solution in the QFT Workbook.
Input:
A register of $n\geq2$ qubits in state $\frac{1}{\sqrt{2^{n}}} \sum_k e^{2\pi i \cdot \frac{Fk}{2^{n}}} |k\rangle$, $0\leq F\leq 2^{n}-1$.
Goal:
Return the frequency F of the "signal" encoded in this state.
%kata T26_Frequency
operation Frequency (register : Qubit[]) : Int {
// ...
return -1;
}
Can't come up with a solution? See the explained solution in the QFT Workbook.
Inputs:
A register of $n$ qubits in an arbitrary state.
An integer $P$ ($ 0 \leq P \leq 2^{20} - 1 $).
Goal:
Transform state $|x\rangle$ into state $ QFT^{P} |x\rangle$, where $QFT$ is the quantum Fourier transform implemented in part I.
Note:
Your solution has to run fast for any $P$ in the given range!
%kata T31_QFTPower
operation QFTPower (P : Int, inputRegister : Qubit[]) : Unit is Adj+Ctl {
// ...
}
Can't come up with a solution? See the explained solution in the QFT Workbook.
Inputs:
A register of $n$ qubits in an arbitrary state.
An integer $P$ ($ 2 \leq P \leq 8 $).
Goal:
Transform state $|x\rangle$ into state $V |x\rangle$, where $V^{P} = QFT$. In other words, implement a $P^{th}$ root of the $QFT$. You can implement the required unitary up to a global phase.
%kata T32_QFTRoot
operation QFTRoot (P : Int, inputRegister : Qubit[]) : Unit is Adj+Ctl {
// ...
}
Can't come up with a solution? See the explained solution in the QFT Workbook.