Cannot construct large Grover circuit

[weiT1993]

Information

• Qiskit Aqua version: 0.7.5
• Python version: 3.7.7
• Operating system: Springdale Linux 7.8 (Verona)

What is the current behavior?

Program fails when trying to construct large Grover circuit.

Steps to reproduce the problem

from qiskit.aqua.algorithms import Grover
from qiskit.aqua.components import oracles

full_circ_size = 59
width=int((full_circ_size+1)/2)
truthtable = '0'*(2**width-1)+'1'
oracle = oracles.TruthTableOracle(truthtable,optimization=True,mct_mode='basic')
grover = Grover(oracle,num_iterations=1,mct_mode='basic')
full_circuit = grover.construct_circuit(measurement=False)

Program returns killed.

What is the expected behavior?

Should produce a 59-qubit Grover circuit.

Suggested solutions

[jlapeyre]

Did the same construction succeed on an earlier version of qiskit?

[weiT1993]

Also tested on Aqua 0.6.5. It also fails.

[jlapeyre]

You may be allocating all of your RAM. Does the following also abort with killed ?

from qiskit.aqua.algorithms import Grover
from qiskit.aqua.components import oracles

full_circ_size = 59
width=int((full_circ_size+1)/2)
truthtable = '0'*(2**width-1)+'1'
oracle = oracles.TruthTableOracle(truthtable,optimization=True,mct_mode='basic')

[woodsp-ibm]

When I tried the code the other day it was killed when building the oracle. Looking at the system log showed it was killed due to lack of memory. Changing optimization=False allows it to build the oracle but it then fails later during the custom initial state creation, again due to memory for me

    grover = Grover(oracle,num_iterations=1,mct_mode='basic')
  File "qiskit/aqua/algorithms/amplitude_amplifiers/grover.py", line 139, in __init__
    init_state if init_state else Custom(len(oracle.variable_register), state='uniform')
  File "qiskit/aqua/components/initial_states/custom.py", line 104, in __init__
    self._state_vector = np.array([1.0 / np.sqrt(size)] * size)
MemoryError

[deeplokhande]

I ran the code for varying values of full_circ_size and found a threshold at 48. So any value above 48 gives this error "Killed" And the Error is a proponent of the oracles.TruthTableOracle( ) function. Yes and as @woodsp-ibm mentioned the same issue occurs in case of optimization=False for me too. I wonder if this oracle issue is related to "timeout" OR "memory overflow". Need to investigate it more.

[jlapeyre]

I'm pretty sure the algorithm is attempting to consume all your RAM (memory) and your OS is killing the process. As @woodsp-ibm notes, there is more than one part of the algorithm that can do this.

[weiT1993]

Will there be a fix to this? I agree it was because part of the algorithm requires too much RAM.

[woodsp-ibm]

Will there be a fix to this?

It needs investigating as to what appears to be consuming the memory and then, as we understand that, it can be determined how to proceed with this.

[Hirmay]

I faced similar issue while running it on IBM-Q Experience.

[gonzaarcr]

Can confirm, the memory usage went to +10 GB after the line oracle = oracles.TruthTableOracle()

[gonzaarcr]

The usage is in truth_table_oracle.get_exact_covers():352 in ec = DLX([(c, 0 if c in cols else 1) for c in range(num_cols)]). num_cols - 1 = cols = 2^full_circ_size/2. So, for full_circ_size = 59 we got cols = 1073741823.

I tried doing a map so the DLX algorithm uses a generator instead but I got TypeError: object of type 'map' has no len().