The Oracle of the Exact Distance | PennyLane Challenges

To attempt this challenge, please switch to a larger screen size.

Challenge statement

This challenge was part of the Canadian Quantum Cup 2023 coding competition.

A common concept associated with search algorithms is that of an oracle—an operator that changes the sign of the inputs that we are looking for. For example, let us label the possible inputs via the computational basis of the three-qubit states: $|0\rangle, |1\rangle, \ldots, |7\rangle.$ Suppose that the sought-after element is $|3\rangle$ . Then the action of the oracle $U$ is as follows:

$U|x\rangle = |x\rangle \quad \text{if}\ x \not = 3$

and

$U|3\rangle = -|3\rangle.$

However, oracles do not have to accept only one input, sometimes they accept more and will change sign to those that meet a certain property. We'll encounter an example of this in this challenge! Our goal will be to build an oracle capable of changing the sign of two three-qubit states only when these two states are separated by a distance $d$ , as shown in the figure below.

Although it may seem like a simple task, you may need some auxiliary qubits, so don't worry, you will be able to use them 😉

We will leave room at the top of the challenge template so that you can create as many helper functions as you want. However, the use of qml.QubitUnitary is not allowed. You must build this oracle without access to the circuit matrix, as would be done in a real quantum computer.

Challenge code

The only function that must be completed is the quantum function oracle_distance, which takes as input the distance d (int), $d \in \{ 0, 1, 2, \dots, 7\}.$ You can create as many helper functions as you want at the top of the challenge template. You can use up to 5 auxiliary qubits. Remember that the output state of the auxiliary qubits must be reset to $|0\rangle$ after use. Otherwise, this could cause problems when implementing the operator in different algorithms.

Input

As input to this problem, you are given:

d (int): the distance with which we will check that the oracle is working properly.

Output

As an output, we will use your oracle to print a list containing the values $1$ and $-1$ . The elements of such list are indexed by the ordered pairs $(0,0), (0,1), (0,2), \ldots, (6,7), (7,7)$ . If the index $(i,j)$ satisfies $|i-j| = d$ , then the corresponding element of the list is $-1$ . Otherwise, it is equal to $1$ .

Test cases

We will test that your oracle generates the correct matrix by using all the possible values of the distance d, $d \in \lbrace 0,\ldots, 7\rbrace.$ As an example, here is what you should get for $d=2$ and $d=7$

test_input: 2
expected_output: [1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, -1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1]

test_input: 7
expected_output: [1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, 1]