Test algorithms in real machines

[BrunoRosendo]

Things to do

DWave:

• [x] Test more samplers, I only used the hybrid for CQM
• [x] Increase the input and record the execution times to understand the possible problem size (after #76 and #74)
• [x] Understand why max min_time is always 5 secs, this is not representative of the input size (hard values that can be verified in the list of solvers under the dashboard)
• [x] Understanding the charge times (related to #12)

Qiskit:

• [x] Investigate why IBM-Q takes so long with so many iterations, even small problems are impossible (compare iterations with classic optimizer) -> locally there are also a lot of iterations, it's just the session problem
• [x] Investigate why multiple jobs are being created. A session might be needed
• [x] Increase the input and record the execution times to understand the possible problem size
• [x] Try to re-submit the extra credits form? I'm not getting a response...
• [x] Create a way to read an env var or a configuration file instead of pasting the hard coded token

[BrunoRosendo]

DWave ran seamlessly by simply using the LeapHybridCQMSampler instead of the exact solver. This was the input:

cvrp = DWaveSolver(
        2,
        None,
        [
            (456, 320),
            (228, 0),
            (912, 0),
            (0, 80),
            # (114, 80),
            # (570, 160),
            # (798, 160),
            # (342, 240),
            # (684, 240),
            # (570, 400),
            # (912, 400),
            # (114, 480),
            # (228, 480),
            # (342, 560),
            # (684, 560),
            # (0, 640),
            # (798, 640),
        ],
        [
            (2, 1, 6),
            (3, 0, 5),
        ],
        True,
        True,
        sampler=LeapHybridCQMSampler(),
    )

the problem ID was 53b3f708-20dd-4a6f-8313-929b5f7161d1

[BrunoRosendo]

The same problem would approximately take 7min on ibm_osaka, so I cancelled it... Idk why it would take so long, I need to investigate

Even the small problem below takes too long and I cancelled it. IBM is also creating multiple jobs to run the algorithm.

if __name__ == "__main__":
    # load account, the API key is a placeholder
    IBMQ.save_account(
        "TOKEN",
        overwrite=True,
    )
    IBMQ.load_account()
    provider = IBMQ.get_provider(hub="ibm-q")
    backend = provider.get_backend("ibm_osaka")

    cvrp = CplexSolver(
        1,
        None,
        [
            (456, 320),
            (228, 0),
            # (912, 0),
            # (0, 80),
            # (114, 80),
            # (570, 160),
            # (798, 160),
            # (342, 240),
            # (684, 240),
            # (570, 400),
            # (912, 400),
            # (114, 480),
            # (228, 480),
            # (342, 560),
            # (684, 560),
            # (0, 640),
            # (798, 640),
        ],
        [
            (0, 1, 6),
        ],
        True,
        sampler=BackendSampler(backend),
    )
    result = cvrp.solve()
    result.display()

[BrunoRosendo]

On DWave, the hybrid solver executed up to the time limit. I will try with a lower time limit and other solvers

[BrunoRosendo]

The minimum time limit is 5 seconds (the default), so we cannot lower it. The explanation is here https://dwave-systemdocs.readthedocs.io/en/latest/reference/generated/dwave.system.samplers.LeapHybridSampler.sample.html

Maximum run time, in seconds, to allow the solver to work on the problem. Must be at least the minimum required for the number of problem variables, which is calculated and set by default. The minimum time for a hybrid solver is specified as a piecewise-linear curve defined by a set of floating-point pairs, the minimum_time_limit field under properties. The first element in each pair is the number of problem variables; the second is the minimum required time. The minimum time for any particular number of variables is a linear interpolation calculated on two pairs that represent the relevant range for the given number of variables. For example, if LeapHybridSampler().properties[“minimum_time_limit”] returns [[1, 0.1], [100, 10.0], [1000, 20.0]], then the minimum time for a 50-variable problem is 5 seconds, the linear interpolation of the first two pairs that represent problems with between 1 to 100 variables.

[BrunoRosendo]

There is a way to convert CQM to BQM, just like mentioned in #74. I will now try to run with that instead of CQM hybrid solver (the problem is the same):

• Local solver: works well and gives the right solution
• Hybrid sampler: the solution is correct and the execution time was 3 instead of 5 (because of lower time_limit)
• DWave sampler: the solution is incorrect but the execution time was only the qpu access time (15ms). This is very promising if I can fix the results. SOLVED -> the problem was the num_reads parameter, the default for this sampler is 1. I set it to 5000 and got the solution for 588ms with 5000 reads (this value should probably be lowered)

My conclusion with these experiments is that I need to support BQM conversion to use samplers simpler than LeapHybridCQM, so I bumped the priority of #74. Then, I can decide which sampler to use based on the input size, by balancing best solution (hybrid) and execution time (quantum only)

[BrunoRosendo]

There was an error solving a problem with more than 32 variables so I created #76

[BrunoRosendo]

I ran this example (510 vars) with leap's hybrid cqm sampler, and the result was fantastic. It still took 5 seconds

cvrp = DWaveSolver(
        2,
        None,
        [
            (456, 320),
            (228, 0),
            (912, 0),
            (0, 80),
            (114, 80),
            (570, 160),
            (798, 160),
            (342, 240),
            (684, 240),
            (570, 400),
            (912, 400),
            (114, 480),
            (228, 480),
            (342, 560),
            (684, 560),
            (0, 640),
            (798, 640),
        ],
        [
            (1, 6, 5),
            (2, 10, 6),
            (4, 3, 4),
            (5, 9, 2),
            (7, 8, 7),
            (15, 11, 4),
            (13, 12, 6),
            (16, 14, 4),
        ],
        True,
        True,
        sampler=LeapHybridCQMSampler(),
    )

This is very promising

[BrunoRosendo]

Another input, this time with 1020 variables (still 5 secs). This solution does not satisfy all the trips, but it's likely a matter of increasing the time limit

cvrp = DWaveSolver(
        4,
        10,
        [
            (456, 320),
            (228, 0),
            (912, 0),
            (0, 80),
            (114, 80),
            (570, 160),
            (798, 160),
            (342, 240),
            (684, 240),
            (570, 400),
            (912, 400),
            (114, 480),
            (228, 480),
            (342, 560),
            (684, 560),
            (0, 640),
            (798, 640),
        ],
        [
            (1, 6, 5),
            (2, 10, 6),
            (4, 3, 4),
            (5, 9, 2),
            (7, 8, 7),
            (15, 11, 4),
            (13, 12, 6),
            (16, 14, 4),
        ],
        True,
        True,
        sampler=LeapHybridCQMSampler(),
    )

[BrunoRosendo]

dwave: the quota for the hybrid solver is not the same as the QPU quota, so the leap hybrid solver is actually not bad

Fun fact, the leap hybrid sampler (BQM) has a lower min time limit (3 seconds). This was discovered by accident xd

[BrunoRosendo]

Another input, this time with 1020 variables (still 5 secs). This solution does not satisfy all the trips, but it's likely a matter of increasing the time limit

cvrp = DWaveSolver(
        4,
        10,
        [
            (456, 320),
            (228, 0),
            (912, 0),
            (0, 80),
            (114, 80),
            (570, 160),
            (798, 160),
            (342, 240),
            (684, 240),
            (570, 400),
            (912, 400),
            (114, 480),
            (228, 480),
            (342, 560),
            (684, 560),
            (0, 640),
            (798, 640),
        ],
        [
            (1, 6, 5),
            (2, 10, 6),
            (4, 3, 4),
            (5, 9, 2),
            (7, 8, 7),
            (15, 11, 4),
            (13, 12, 6),
            (16, 14, 4),
        ],
        True,
        True,
        sampler=LeapHybridCQMSampler(),
    )

following this, I managed to solve it by increasing time limit to 10s

[BrunoRosendo]

This is an example of a very complex problem (and the solution returned by dwave hybrid 10secs)

cvrp = DWaveSolver(
        6,
        15,
        [
            (456, 320),
            (228, 0),
            (912, 0),
            (0, 80),
            (114, 80),
            (570, 160),
            (798, 160),
            (342, 240),
            (684, 240),
            (570, 400),
            (912, 400),
            (114, 480),
            (228, 480),
            (342, 560),
            (684, 560),
            (0, 640),
            (798, 640),
            (456, 720),
            (0, 800),
            (912, 800),
            (228, 880),
            (684, 880),
            (342, 960),
            (798, 960),
            (114, 1040),
            (570, 1040),
        ],
        [
            (1, 6, 5),
            (2, 10, 6),
            (4, 3, 4),
            (5, 9, 2),
            (7, 8, 7),
            (15, 11, 4),
            (13, 12, 6),
            (16, 14, 4),
            (0, 6, 10),
            (5, 15, 3),
            (16, 17, 7),
            (17, 18, 5),
            (19, 18, 4),
            (20, 21, 6),
            (22, 23, 7),
            (24, 25, 3),
        ],
        True,
        True,
        sampler=LeapHybridCQMSampler(),
    )

[BrunoRosendo]

multi cvrp example (544 vars)

cvrp = DWaveSolver(
        2,
        [10, 8],
        [
            (456, 320),
            (228, 0),
            (912, 0),
            (0, 80),
            (114, 80),
            (570, 160),
            (798, 160),
            (342, 240),
            (684, 240),
            (570, 400),
            (912, 400),
            (114, 480),
            (228, 480),
            (342, 560),
            (684, 560),
            (0, 640),
            (798, 640),
        ],
        [],
        False,
        True,
        sampler=LeapHybridCQMSampler(),
    )

[BrunoRosendo]

DWave Results

If not feasible, it's only because not all trips were satisfied, more execution time or reads should solve that

LeapHybridCQMSampler

Algorithm	Vars	Vehicles	Capacity	Locations	Trips	Feasible	Time
CVRP	15	2	None	4	NA	:white_check_mark:	5s
Multi CVRP	544	2	[10, 8]	16	NA	:white_check_mark:	5s
RPP	30	2	None	4	2	:white_check_mark:	5s
RPP	510	2	None	16	8	:white_check_mark:	5s
RPP	1020	4	10	16	8	:x:	5s
RPP	1020	4	10	16	8	:white_check_mark:	10s
RPP	5010	6	15	26	15	:x:	10s

In general, the solutions of this sampler are really good!

LeapHybridSampler

The variable count is made BEFORE converting into BQM. The real number higher due to slack variables and integer encoding

Algorithm	Vars	Vehicles	Capacity	Locations	Trips	Feasible	Time
CVRP	15	2	None	4	NA	:white_check_mark:	3s
Multi CVRP	544	2	[10, 8]	16	NA	:x:	3s
Multi CVRP	544	2	[10, 8]	16	NA	:x:	5s
Multi CVRP	544	2	[10, 8]	16	NA	:x:	10s
Multi CVRP	544	2	[10, 8]	16	NA	:x:	20s
RPP	30	2	None	4	2	:white_check_mark:	3s
RPP	126	2	None	8	4	:white_check_mark:	3s
RPP	286	2	20	12	6	:x:	3s
RPP	286	2	20	12	6	:x:	10s
RPP	510	2	None	16	8	:x:	3s
RPP	510	2	None	16	8	:x:	10s

In general, the performance of this sampler is much worse compared to hybrid CQM. This could be due to worse embedding or pre-processing that is done in the CQM sampler or simply due to converting the problem to BQM. I can check this in #58

DWaveSampler

Algorithm	Vars	Vehicles	Capacity	Locations	Trips	Embedding	Feasible	num_reads	Time
CVRP	15	2	None	4	NA	:white_check_mark:	:white_check_mark:	500	67ms
CVRP	63	2	None	8	NA	:white_check_mark:	:x:	500	137ms
CVRP	63	2	None	8	NA	:white_check_mark:	:x:	3000	710ms
Multi CVRP	112	2	[10, 8]	8	NA	:white_check_mark:	:x:	500	137ms
Multi CVRP	544	2	[10, 8]	16	NA	:x:	NA	NA	NA
RPP	30	2	None	4	2	:white_check_mark:	:white_check_mark:	1000	115ms
RPP	126	2	None	8	4	:white_check_mark:	:x:	1000	224ms
RPP	126	2	None	8	4	:white_check_mark:	:x:	3500	802ms

The pre-processing seems to take really long or never finds a solution, probably due to embedding, something to tackle in #58 Also, there is a maximum execution time of 1s, which can be reached with some inputs. Infeasible results are probably caused by not having enough reads (increasing it would result in high execution times)

[BrunoRosendo]

IBM: I tried creating sessions with qiskit runtime, but I encountered version conflicts

ImportError: Qiskit is installed in an invalid environment that has both Qiskit >=1.0 and an earlier version. You should create a new virtual environment, and ensure that you do not mix dependencies between Qiskit <1.0 and >=1.0. Any packages that depend on 'qiskit-terra' are not compatible with Qiskit 1.0 and will need to be updated. Qiskit unfortunately cannot enforce this requirement during environment resolution. See https://qisk.it/packaging-1-0 for more detail.

https://docs.quantum.ibm.com/run/run-jobs-in-session https://pypi.org/project/qiskit-ibm-runtime/

check the docs https://docs.quantum.ibm.com/api/qiskit-ibm-runtime/release-notes

[BrunoRosendo]

The IBM session logic is implemented and SHOULD work. However, due to a recent IBM change (march 2024) a lot of algorithm libraries have stopped working, see https://github.com/qiskit-community/qiskit-algorithms/issues/164

also machine learning https://github.com/qiskit-community/qiskit-machine-learning/issues/786

this is the announcement https://docs.quantum.ibm.com/run/primitives-examples

The problem is the circuit not being transpiled inside the algorithm. Something like this should be happening

ansatz = RealAmplitudes(num_qubits=5, reps=3)
transpiled_ansatz = qiskit.compiler.transpile(ansatz, backend=backend)
..
vqc = VQC(
    sampler=sampler,
    feature_map=feature_map,
    ansatz=transpiled_ansatz,
    optimizer=optimizer
)

[BrunoRosendo]

the execution works with backendsampler, but I cannot use sessions with that

[BrunoRosendo]

Based on the comment above and the thread below, I tried transpiling the ansatz and adding a padding to the operator (observable) as to match the number of qubits in the backend. However, I can't find a way to add the padding. Even if I did, I think there would be more problems.

https://quantumcomputing.stackexchange.com/questions/29332/how-to-avoid-delays-must-be-a-multiple-of-16-samples-error-with-estimator-sa

[BrunoRosendo]

I created #81 , for now I'll wait for a potential fix on qiskit's part. For now, this issue will be blocked

[BrunoRosendo]

Qiskit Results

No Warm Start

Algorithm	Vars	Vehicles	Capacity	Locations	Trips	Feasible	Time
RPP	4	1	None	2	1	:x:	21s p/ iter
CVRP	15	2	None	4	NA	:x:	23s p/ iter
Multi CVRP	544	2	[10, 8]	16	NA	:x:	39s p/ iter

Warm Start

Algorithm	Vars	Vehicles	Capacity	Locations	Trips	Feasible	Time
RPP	4	1	None	2	1	:x:	21 p/ iter
CVRP	36	2	None	4	NA	:x:	23s p/ iter

Warm start doesn't seem to matter in execution time, at least in the examples I used

Tests with IBM-Q are extremely hard for the following reasons:

• Iterations take too long to execute, with ~21secs per iteration. For a simple problem with 4 vars (example above), this would already exceed the monthly quota (~24mins)
• Even though I'm using a session, I still need to queue every time the algorithm runs an iteration. This is extremely time-consuming. I will ask around if there is a solution since QAOA needs to adjust the parameters for each iteration.

I imagine I will only be able to run 1-2 examples for the thesis, and everything else will be done with simulators.

PS: By this article, the jobs are only prioritized so I don't think I have control over this.