microsoft/qdk
Publicmirrored fromhttps://github.com/microsoft/qdkAvailable
katas/content/marking_oracles/contains_substring/solution.md
14lines · modecode
| 1 | This task is very similar to the task in which we checked whether the string is periodic. |
| 2 | Same as there, we have a building block that checks our condition (whether the bit string contains a given pattern at the specific position), and our function is an OR of conditions that apply with different parameters (the given pattern can start with position $0$, $1$, $2$, and so on). |
| 3 | |
| 4 | The solution is similar as well: |
| 5 | |
| 6 | 1. Allocate $N - K + 1$ auxiliary qubits, one for each position that can be the beginning of the pattern. |
| 7 | 2. Evaluate the condition with each possible position as the beginning of the pattern, and store the results in these qubits. |
| 8 | 3. Evaluate the overall function as an OR of the values of the auxiliary qubits. |
| 9 | 4. Uncompute the changes done to the states of the auxiliary qubits before releasing them. |
| 10 | |
| 11 | @[solution]({ |
| 12 | "id": "marking_oracles__contains_substring_solution", |
| 13 | "codePath": "./Solution.qs" |
| 14 | }) |
| 15 | |