A puzzle box hides a Boolean function f that takes n bits and answers 0 or 1. Its manual lists the inputs where f answers 1, the marked inputs, as bit strings of length n; every other input gives 0.
A quantum circuit asks f through a phase oracle O_f, the gate on n qubits that leaves every basis state alone except for a sign:
So O_f is a diagonal 2^n\times 2^n matrix whose entry for basis state x is -1 when x is marked and +1 otherwise. Basis state |b_0 b_1 \dots b_{n-1}\rangle has index int("b0b1...", 2): qubit 0 is the leftmost bit, the most significant one. In 3 qubits, |011\rangle is index 3.
Write phase_signs(n, marked) that returns the diagonal of O_f: a list of 2^n numbers, each 1 or -1, where entry i belongs to basis state i.
Examples
Input: n = 2, marked = ["10"]
Output: [1, 1, -1, 1]
Explanation: "10" is index 2.
Input: n = 3, marked = ["001", "110"]
Output: [1, -1, 1, 1, 1, 1, -1, 1]
Explanation: "001" is index 1 and "110" is index 6.
Input: n = 1, marked = []
Output: [1, 1]
Constraints
- the marked strings are distinct, each of length
n
Goals
- Write a phase oracle as the diagonal of a matrix of +1 and -1
- Turn a bit string into a basis index with qubit 0 as the leftmost bit