The Grover's Search quantum kata is a series of exercises designed to get you familiar with Grover's search algorithm.
It covers the following topics:
Reading material:
Each task is wrapped in one operation preceded by the description of the task.
Your goal is to fill in the blanks (marked with the // ...
comments)
with some Q# code that solves the task. To verify your answer, run the cell with Ctrl+Enter (⌘+Enter on macOS).
Within each section, tasks are given in approximate order of increasing difficulty; harder ones are marked with asterisks.
Inputs:
N qubits in an arbitrary state $|x\rangle$ (input/query register)
A qubit in an arbitrary state $|y\rangle$ (target qubit)
Goal:
Flip the state of the target qubit (i.e., apply an X gate to it) if the query register is in the $|11...1\rangle$ state, and leave it unchanged if the query register is in any other state. Leave the query register in the same state it started in.
Examples:
If the query register is in state $|00...0\rangle$, leave the target qubit unchanged.
If the query register is in state $|10...0\rangle$, leave the target qubit unchanged.
If the query register is in state $|11...1\rangle$, flip the target qubit.
If the query register is in state $\frac{1}{\sqrt{2}} \big(|00...0\rangle + |11...1\rangle \big)$, and the target is in state $|0\rangle$,
the joint state of the query register and the target qubit should be $\frac{1}{\sqrt{2}} \big(|00...00\rangle + |11...11\rangle \big)$.
%kata T11_Oracle_AllOnes
operation Oracle_AllOnes (queryRegister : Qubit[], target : Qubit) : Unit is Adj {
// ...
}
Inputs:
N qubits in an arbitrary state $|x\rangle$ (input/query register)
A qubit in an arbitrary state $|y\rangle$ (target qubit)
Goal:
Flip the state of the target qubit if the query register is in the $|1010...\rangle$ state; that is, the state with alternating 1 and 0 values, with any number of qubits in the register. Leave the state of the target qubit unchanged if the query register is in any other state. Leave the query register in the same state it started in.
Examples:
%kata T12_Oracle_AlternatingBits
operation Oracle_AlternatingBits (queryRegister : Qubit[], target : Qubit) : Unit is Adj {
// ...
}
Inputs:
N qubits in an arbitrary state $|x\rangle$ (input/query register)
A qubit in an arbitrary state $|y\rangle$ (target qubit)
A bit pattern of length N represented as Bool[]
Goal:
Flip the state of the target qubit if the query register is in the state described by the given bit pattern
(true
represents qubit state One, and false
represents Zero).
Leave the state of the target qubit unchanged if the query register is in any other state.
Leave the query register in the same state it started in.
Example:
If the bit pattern is [true, false]
, you need to flip the target qubit if and only if the qubits are in the $|10\rangle$ state.
%kata T13_Oracle_ArbitraryPattern
operation Oracle_ArbitraryPattern (queryRegister : Qubit[], target : Qubit, pattern : Bool[]) : Unit is Adj {
// ...
}
Input:
A marking oracle: an oracle that takes a register and a target qubit and flips the target qubit if the register satisfies a certain condition.
Output:
A phase-flipping oracle: an oracle that takes a register and flips the phase of the register if it satisfies this condition.
Grover's algorithm relies on the search condition implemented as a phase-flipping oracle,
but it is often easier to write a marking oracle for a given condition. This transformation allows to convert one type of oracle into the other. The transformation is described in the Wikipedia article on Grover's algorithm, in the section "Description of ${U_\omega}$".
%kata T14_OracleConverter
function OracleConverter (markingOracle : ((Qubit[], Qubit) => Unit is Adj)) : (Qubit[] => Unit is Adj) {
// ...
}
Input: A register of N qubits in an arbitrary state
Goal: Apply the Hadamard transform to each of the qubits in the register.
If the register started in the $|0...0\rangle$ state, this operation
will prepare an equal superposition of all $2^{N}$ basis states.
%kata T21_HadamardTransform
operation HadamardTransform (register : Qubit[]) : Unit is Adj {
// ...
}
Input: A register of N qubits in an arbitrary state.
Goal: Flip the sign of the state of the register if it is not in the $|0...0\rangle$ state.
Examples:
If the register is in state $|0...0\rangle$, leave it unchanged.
If the register is in any other basis state, multiply its phase by -1.
This operation implements operator $2|0...0\rangle\langle0...0| - I$ $ = \left(\begin{matrix}1&0&...&0\\0&-1&...&0\\\vdots&\vdots&\ddots&\vdots\\0&0&...&-1\end{matrix}\right) $
It doesn't matter for Grover's search algorithm itself, since the global phase is not observable, but can have side effects when used as part of other algorithms.
See the extended discussion in this Quantum Computing SE question
</details>
%kata T22_ConditionalPhaseFlip
operation ConditionalPhaseFlip (register : Qubit[]) : Unit is Adj {
// ...
}
Inputs:
N qubits in an arbitrary state $|x\rangle$ (input/query register)
A phase-flipping oracle that takes an N-qubit register and flips the phase of the state if the register is in the desired state.
Goal: Perform one Grover iteration.
%kata T23_GroverIteration
operation GroverIteration (register : Qubit[], oracle : (Qubit[] => Unit is Adj)) : Unit is Adj {
// ...
}
Inputs:
N qubits in the $|0...0\rangle$ state.
A marking oracle.
The number of Grover iterations to perform.
Goal: Use Grover's algorithm to leave the register in the state that is marked by the oracle as the answer (with high probability).
The number of iterations is passed as a parameter because it is defined by the nature of the problem
and is easier to configure/calculate outside the search algorithm itself (for example, in the classical driver).
%kata T31_GroversSearch
operation GroversSearch (register : Qubit[], oracle : ((Qubit[], Qubit) => Unit is Adj), iterations : Int) : Unit {
// ...
}
Goal: Use your implementation of Grover's Algorithm from Task 3.1 and the oracles from part 1 to find the marked elements of the search space. This task is not covered by a test and allows you to experiment with running the algorithm.
This is an open-ended task, and is not covered by a unit test. To run the code, execute the cell with the definition of the
Run_GroversSearch_Algorithm
operation first; if it compiled successfully without any errors, you can run the operation by executing the next cell (%simulate Run_GroversSearch_Algorithm
).
Note that this task relies on your implementations of the previous tasks. If you are getting the "No variable with that name exists." error, you might have to execute previous code cells before retrying this task.
operation Run_GroversSearch_Algorithm () : Unit {
// ...
}
%simulate Run_GroversSearch_Algorithm