If we don't know the number of solutions, then we can test in pairs and tally up the number of times we detect one. This tally will have the same parity (i.e., odd or even) as the total number of solutions since we can only miss solutions in pairs of two. Thus, we can learn a global property about the function that we didn't know beforehand! Let us now use the same circuit as before to test for many solutions and learn the parity of the number of solutions.

Implement the circuit above, but now for how_many solutions instead of one. You will first need to implement the multi-solution version of the oracle matrix, multisol_oracle_matrix(combos), which takes a list of bit strings (representing different solutions) and returns the associated oracle in matrix form.

n_bits = 4
dev = qml.device("default.qubit", wires=n_bits)

def multisol_oracle_matrix(combos):
"""Return the oracle matrix for a set of solutions.

Args:
combos (list[list[int]]): A list of secret bit strings.

Returns:
array[float]: The matrix representation of the oracle.
"""
indices = [np.ravel_multi_index(combo, [2]*len(combo)) for combo in combos]
##################
# YOUR CODE HERE #
##################
pass

@qml.qnode(dev)
def multisol_pair_circuit(x_tilde, combos):
"""Implements the circuit for testing a pair of combinations labelled by x_tilde.
Args:
x_tilde (list[int]): An (n_bits - 1)-bit string labelling the pair to test.
combos (list[list[int]]): A list of secret bit strings.

Returns:
array[float]: Probabilities on the last qubit.
"""
for i in range(n_bits-1): # Initialize x_tilde part of state
if x_tilde[i] == 1:
qml.PauliX(wires=i)

##################
# YOUR CODE HERE #
##################

or to submit your code

To interact with codercises, please switch to a larger screen size.

Learning Objectives:

  • Explain how global information and promises can be useful for algorithm design.