TruthTableOracle producing incorrect logic for large oracles in some quantum walks

[PabloAMC]

Information

• Qiskit Aqua version: 0.8.1
• Python version: 0.16.1
• Operating system: IBM Quantum Experience

What is the current behavior?

The following code is part of a quantum walk algorithm in a two-dimensional space. We analyze the oracle that tells with what probabilities steps are accepted and determine there is an error in the output of the oracle.

Some comments:

1. Several other examples (other bitmaps) have been tested and the error happens only when we specify the coordinates with at least 5 bits, not for less.
2. We initialize the circuit in a position where the oracle should always output 1, the position (26,5).

The correct or incorrect behavior can be assessed from the printout of the following code, after the
Check of the algorithm!!! call. Correct behavior will happen when the last qubit (the output of the oracle) is always in state 1, whereas incorrect behavior happens when there is some non-negligible amplitude for the output of the oracle in state 0. The current output of the oracle circuit (when initialized to a state that should always output 1) is

Check of the algorithm!!!
1101000101001 (0.5-9.06544793068824e-14j)
1101000101010 (0.5-6.172219867702362e-14j)
1101000101101 (0.5-1.243934986233914e-13j)
1101000101110 (0.4999999999999999-6.17221986770236e-14j)

Steps to reproduce the problem

Define the bitmap of the oracle (unfortunately, this error only seems to happen for quite large oracles, so I cannot give a smaller version).

string = '1001100110011001100110111010100010111010101010101010101010101010101010101010101010101000100110011001100110011001100110011001100110011001100110011001101110101000101110101010101010101010101010101010101010101010101010001001100110011001100110011001100110011001100110011001100110011011101010001011101010101010101010101010101010101010101010101010100010011001100110011001100110111000100110011001100110011001100110111010100010111010101010101010101010001011101010101010101010101000100110011001100110011001100110011001100110011001100110011001101110101000101110101010101010101010100010111010101010101010101010001001100110011001100110011001100110011001000100010001000100010011001000000011001000100010001000100000001100100010001000100010000000010001000100010001000100010001000100010101010101010101010101110110010001110110011001100110011001000111011001100110011001100100010101010101010101010101010101010101010101010111010001010101011101100100011101100110011001100110010001110110011001100110011001000101010101010101010101010111010001010101111111101100110101010111011001000111011001100110011001100110011001100110011001101110110011011101010111011101110111011101110111011011100010011001010101111110110011111110111011101110111011101110111011101110111010101000100110011101100110011001100110011001100110011001100110011101111110101000101110101010101010101010101010101010101010101010101010001001100110011001100110011001100110011001100110011001100110011011101010001011101010101010101010101010101010101010101010101010100010011001100110011001101110101000100110011001100110011001100110111010100010111010101010101010101010101010101010101010101010101000100110011001100110011011101010001001100110011001100110011001101110101000101110101010101010101010101010101010101010101010101010001001100110011001100110011001100110011001100110011001100110011011101010001011101010101010101010101010101010101010101010101010100010011001100110011001100110011001100110010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001010101010101010101011101100100011101100110011001100110011001100110011001100110011001000101010101010101010101010101010101010101010101010101010101010111011001000101011101100110011001100100011101100110011001100110010001010101010101010101010101010101010101010101010101010101010101110110010001110110011001100110011001100110011001100110011001100100010101010101010101010101010101010101010101010101010101010111011001100100011101100110011001100110011001100110011001100110011001000101010101010101010101010101010101010101010101010101010101110110011001000111011001100110011001100110011001100110011001100110010001010101010101010101010101010101010101010101010101110110011001100110010001110110011001100110011001100110011011100110011011100100010101010101010101010101010101010101010101010101011101100100011101100100011101100110011001100110011001100110001001100110001001000101010101010101010101010111010001010101010101010111010001010111011001000111011001100110011001100110011001100110011001100110010001010101010101010101010101010101010101010101010111010101010101110110010001110110011001100110011001100110011001100110011001101100010101010101010101010101010101010101010101011101100101010101011101100100011101100110011001100110011001100110011001100110011000000101010101010101010101010101010101010101110110010001010101011111111011001111111011101110111011101110111011101110011001100110010011011101110101011101110111011101110111011001100101010101110110111010100010111010101010101010101010101010101010101110111011101100100110011001110110011001100110011001100110010001110111011001101110101000101110101010101010101010101010101010101010101010101010000001100110011001100110011001100110011001000111011001100110011011101010001011101010101010101010101010101010101010101010101010100011011001000110011001100110011001100110011101100110011001100110111010100010111010101010101010101010101010101010101010101010101000100110010101100110011001101110001001000110011001100110011001101110101000101110101010101010101010101010101010101010101010101010001001100111011001100110011001100110011101'

We can check that the output at the positions starting by '1101000101' (26,5 is the minimum energy state) is 1using

print(string.count('1'))
print(len(string))
# We have to that in the target positions we should be getting a 1
for i in range(len(string)):
    n = np.binary_repr(i, width = int(np.log2(len(string))))
    if n[:10] == '1101000101':
        print(n, string[i])

which will output

2016
4096
110100010100 1
110100010101 1
110100010110 1
110100010111 1

We can try to see if we can actually get the output, which will be in register ancilla. We first create the circuit

coord_1 = QuantumRegister(5)
coord_2 = QuantumRegister(5)
move_id = QuantumRegister(1)
move_value = QuantumRegister(1)
ancilla = QuantumRegister(1)
# We order the registers from least to most significant, so that the output of qiskit is from most to least significant is correct:
qc = QuantumCircuit(ancilla,move_value,move_id,coord_2,coord_1)

# encoding the value of (26,5) = 11010 00101
qc.x(coord_1[1])
qc.x(coord_1[3])
qc.x(coord_1[4])

qc.x(coord_2[0])
qc.x(coord_2[2])

# We set the two final registers in a superposition to be able to see what happens in all possibilities
qc.h(move_id)
qc.h(move_value)

Then we create the oracle

# Construct an instruction for the oracle
oracle = TruthTableOracle(string, mct_mode='noancilla')
oracle.construct_circuit()
oracle_circuit = oracle.circuit
print()

oracle_gate = oracle_circuit.to_instruction()

qc.append(oracle_gate, [move_value[0]]+[move_id[0]] 
                        + [coord_2[j] for j in range(5)]
                        + [coord_1[j] for j in range(5)]
                        + [ancilla[0]])

And finally, we execute the circuit

experiment = execute(qc,backend=Aer.get_backend('statevector_simulator'))
state_vector = Statevector(experiment.result().get_statevector(qc))

state_vec = state_vector.data
print('Check of the algorithm!!!')
for i in range(len(state_vec)):
    if abs(state_vec[i])>1e-7:
        print(np.binary_repr(i, width = 13),state_vec[i])

Which outputs

Check of the algorithm!!!
1101000101001 (0.5-9.06544793068824e-14j)
1101000101010 (0.5-6.172219867702362e-14j)
1101000101101 (0.5-1.243934986233914e-13j)
1101000101110 (0.4999999999999999-6.17221986770236e-14j)

We can see that the ancilla (the least significant register) is not always in state 1, which represents a logic failure.

What is the expected behavior?

Something similar to

Check of the algorithm!!!
1101000101001 (0.5-9.06544793068824e-14j)
1101000101011 (0.5-6.172219867702362e-14j)
1101000101101 (0.5-1.243934986233914e-13j)
1101000101111 (0.4999999999999999-6.17221986770236e-14j)

where all the non-zero amplitudes correspond to bitstrings ending in 1.

Suggested solutions

It is unclear to me what could be failing in the logic of the oracle, so I cannot really say.