The Marking Oracles quantum kata is a series of exercises designed to teach you to implement marking oracles for classical functions in Q#.
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).
The tasks are given in approximate order of increasing difficulty.
Inputs:
Goal: Implement a quantum oracle which checks whether the input register is a palindrome, i.e., implements the function $f(x) = 1$ if $x$ is a palindrome, and $0$ otherwise. A bit string is a palindrome if it equal its reverse, or, in other words, its first bit equals its last bit, its second bit equals its second-to-last bit, and so on.
Leave the qubits in the input register in the same state they started in. Your solution should work on inputs in superposition, and not use any measurements.
Example: For $N = 3$, the input state $|101\rangle$ is a palindrome, and $|001\rangle$ is not.
%kata T01_PalindromeOracle
operation PalindromeOracle (input : Qubit[], target : Qubit) : Unit is Adj {
// ...
}
Inputs:
Goal: Implement a quantum oracle which checks whether the input register is periodic with period $P$, i.e., for all $j$ between $0$ and $N - P - 1$, inclusive, $x_j = x_{j+P}$.
Leave the qubits in the input register in the same state they started in. Your solution should work on inputs in superposition, and not use any measurements.
Example: For $N = 3$, a bit string [false, true, false]
is periodic with period 2.
%kata T02_PeriodicGivenPeriodOracle
operation PeriodicGivenPeriodOracle (input : Qubit[], target : Qubit, P : Int) : Unit is Adj {
// ...
}
Inputs:
Goal: Implement a quantum oracle which checks whether the input register is periodic with any period, i.e., whether there exists a value $P < N$ such that for all $j$ between $0$ and $N - P - 1$, inclusive, $x_j = x_{j+P}$.
Leave the qubits in the input register in the same state they started in. Your solution should work on inputs in superposition, and not use any measurements.
Example: For $N = 3$, a bit string [false, true, false]
is periodic with period 2, so the bit string is periodic.
%kata T03_PeriodicOracle
operation PeriodicOracle (input : Qubit[], target : Qubit) : Unit is Adj {
// ...
}
Inputs:
Bool[]
($1 \le K \le N$).Goal: Implement a quantum oracle which checks whether the input register contains the given pattern starting at the given position, i.e., for all $j$ between $0$ and $K - 1$, inclusive, $pattern_j = x_{j+P}$ (false
and true
values represent states $|0\rangle$ and $|1\rangle$, respectively).
Leave the qubits in the input register in the same state they started in. Your solution should work on inputs in superposition, and not use any measurements.
Example: For $N = 3$, a bit string [false, true, false]
contains a pattern [true, false]
starting at index 1.
%kata T04_ContainsSubstringAtPositionOracle
operation ContainsSubstringAtPositionOracle (input : Qubit[], target : Qubit, pattern : Bool[], P : Int) : Unit is Adj {
// ...
}
Inputs:
Bool[]
($1 \le K \le N$).Goal: Implement a quantum oracle which checks whether the input register matches the given pattern, i.e., the bits at the given indices match the corresponding bits in the pattern (false
and true
values represent states $|0\rangle$ and $|1\rangle$, respectively).
Leave the qubits in the input register in the same state they started in. Your solution should work on inputs in superposition, and not use any measurements.
Example: For $N = 3$, a pattern [false, true]
at indices [0, 2]
would match two basis states: $|001\rangle$ and $|011\rangle$.
%kata T05_PatternMatchingOracle
operation PatternMatchingOracle (input : Qubit[], target : Qubit, indices : Int[], pattern : Bool[]) : Unit is Adj {
// ...
}
Inputs:
Bool[]
($1 \le K \le N$).Goal: Implement a quantum oracle which checks whether the input register contains the given pattern, i.e., whether there exists a position $P$ such that for all $j$ between $0$ and $K - 1$, inclusive, $pattern_j = x_{j+P}$.
Leave the qubits in the input register in the same state they started in. Your solution should work on inputs in superposition, and not use any measurements.
Example: For $N = 3$, a bit string [false, true, false]
contains a pattern [true, false]
(starting at index 1).
%kata T06_ContainsSubstringOracle
operation ContainsSubstringOracle (input : Qubit[], target : Qubit, pattern : Bool[]) : Unit is Adj {
// ...
}
Inputs:
Goal: Implement a quantum oracle which checks whether the input register is a balanced bit string, i.e., whether it contains exactly $N/2$ 0s and $N/2$ 1s.
Leave the qubits in the input register in the same state they started in. Your solution should work on inputs in superposition, and not use any measurements.
Example: For $N = 4$, basis states $|0011\rangle$ and $|0101\rangle$ are balanced, and $|0010\rangle$ and $|1111\rangle$ are not.
%kata T07_BalancedOracle
operation BalancedOracle (input : Qubit[], target : Qubit) : Unit is Adj {
// ...
}
Inputs:
Goal: Implement a quantum oracle which calculates the majority function, i.e., $f(x) = 1$ if most of the bits in the bit string are 1s, and $0$ otherwise.
Leave the qubits in the input register in the same state they started in. Your solution should work on inputs in superposition, and not use any measurements.
Example: For $N = 3$, majority function for basis states $|001\rangle$ and $|000\rangle$ is 0, and for $|101\rangle$ and $|111\rangle$ - 1.
%kata T08_MajorityOracle
operation MajorityOracle (input : Qubit[], target : Qubit) : Unit is Adj {
// ...
}
Inputs:
Goal: Implement a quantum oracle which checks whether the sum of bits in the bit string is divisible by 3.
Leave the qubits in the input register in the same state they started in. Your solution should work on inputs in superposition, and not use any measurements.
Example: For $N = 3$, the only basis states that should be marked are $|000\rangle$ and |111\rangle$.
%kata T09_BitSumDivisibleBy3Oracle
operation BitSumDivisibleBy3Oracle (input : Qubit[], target : Qubit) : Unit is Adj {
// ...
}
Inputs:
Goal: Implement a quantum oracle which checks whether the number represented by the bit string is divisible by 3.
Use little endian notation to convert the bit string to an integer, i.e., the least significant bit is stored in input[0]
.
Leave the qubits in the input register in the same state they started in. Your solution should work on inputs in superposition, and not use any measurements.
Example: For $N = 3$, the basis states that should be marked are $|000\rangle$, $|110\rangle$, and |011\rangle$.
%kata T10_DivisibleBy3Oracle
operation DivisibleBy3Oracle (input : Qubit[], target : Qubit) : Unit is Adj {
// ...
}