def _compute_unitary_oracle_matrix(bitstring_map):
"""
Computes the unitary matrix that encodes the orcale function for Simon's algorithm
:param Dict[String, String] bitstring_map: truth-table of the input bitstring map in
dictionary format
:return: a dense matrix containing the permutation of the bit strings and a dictionary
containing the indices of the non-zero elements of the computed permutation matrix as
key-value-pairs
:rtype: Tuple[2darray, Dict[String, String]]
"""
n_bits = len(list(bitstring_map.keys())[0])
# We instantiate an empty matrix of size 2 * n_bits to encode the mapping from n qubits
# to n ancillas, which explains the factor 2 overhead.
# To construct the matrix we go through all possible state transitions and pad the index
# according to all possible states the ancilla-subsystem could be in
ufunc = np.zeros(shape=(2 ** (2 * n_bits), 2 ** (2 * n_bits)))
index_mapping_dct = defaultdict(dict)
for b in range(2**n_bits):
# padding according to ancilla state
pad_str = np.binary_repr(b, n_bits)
for k, v in bitstring_map.items():
# add mapping from initial state to the state in the ancilla system.
# pad_str corresponds to the initial state of the ancilla system.
index_mapping_dct[pad_str + k] = utils.bitwise_xor(pad_str, v) + k
# calculate matrix indices that correspond to the transition-matrix-element
# of the oracle unitary
i, j = int(pad_str+k, 2), int(utils.bitwise_xor(pad_str, v) + k, 2)
ufunc[i, j] = 1
return ufunc, index_mapping_dct
评论列表
文章目录
