Test algorithms in real machines #44

BrunoRosendo · 2024-03-23T03:22:54Z

Things to do

DWave:

Test more samplers, I only used the hybrid for CQM
Increase the input and record the execution times to understand the possible problem size (after Value error with more than 32 variables #76 and Check if DWave can use BQM in variants that don't use int vars #74)
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)
Understanding the charge times (related to Get metrics, such as execution time #12)

Qiskit:

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
Investigate why multiple jobs are being created. A session might be needed
Increase the input and record the execution times to understand the possible problem size
Try to re-submit the extra credits form? I'm not getting a response...
Create a way to read an env var or a configuration file instead of pasting the hard coded token

BrunoRosendo · 2024-04-12T00:15:59Z

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 · 2024-04-12T00:32:00Z

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 · 2024-04-12T13:59:43Z

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

BrunoRosendo · 2024-04-12T14:14:29Z

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 · 2024-04-12T15:15:29Z

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 · 2024-04-12T15:28:33Z

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

BrunoRosendo · 2024-04-12T16:30:40Z

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 · 2024-04-12T16:33:06Z

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 · 2024-04-15T16:45:47Z

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 · 2024-04-16T19:02:17Z

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 · 2024-04-16T19:14:26Z

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 · 2024-04-16T19:26:36Z

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 · 2024-04-17T01:54:13Z

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	✅	5s
Multi CVRP	544	2	[10, 8]	16	NA	✅	5s
RPP	30	2	None	4	2	✅	5s
RPP	510	2	None	16	8	✅	5s
RPP	1020	4	10	16	8	❌	5s
RPP	1020	4	10	16	8	✅	10s
RPP	5010	6	15	26	15	❌	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	✅	3s
Multi CVRP	544	2	[10, 8]	16	NA	❌	3s
Multi CVRP	544	2	[10, 8]	16	NA	❌	5s
Multi CVRP	544	2	[10, 8]	16	NA	❌	10s
Multi CVRP	544	2	[10, 8]	16	NA	❌	20s
RPP	30	2	None	4	2	✅	3s
RPP	126	2	None	8	4	✅	3s
RPP	286	2	20	12	6	❌	3s
RPP	286	2	20	12	6	❌	10s
RPP	510	2	None	16	8	❌	3s
RPP	510	2	None	16	8	❌	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	✅	✅	500	67ms
CVRP	63	2	None	8	NA	✅	❌	500	137ms
CVRP	63	2	None	8	NA	✅	❌	3000	710ms
Multi CVRP	112	2	[10, 8]	8	NA	✅	❌	500	137ms
Multi CVRP	544	2	[10, 8]	16	NA	❌	NA	NA	NA
RPP	30	2	None	4	2	✅	✅	1000	115ms
RPP	126	2	None	8	4	✅	❌	1000	224ms
RPP	126	2	None	8	4	✅	❌	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 · 2024-04-17T02:50:17Z

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 · 2024-04-17T15:53:53Z

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 qiskit-community/qiskit-algorithms#164

also machine learning qiskit-community/qiskit-machine-learning#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 · 2024-04-17T20:49:17Z

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

BrunoRosendo · 2024-04-18T01:22:56Z

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 · 2024-04-18T02:03:35Z

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

BrunoRosendo · 2024-05-16T01:02:50Z

Qiskit Results

No Warm Start

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

Warm Start

Algorithm	Vars	Vehicles	Capacity	Locations	Trips	Feasible	Time
RPP	4	1	None	2	1	❌	21 p/ iter
CVRP	36	2	None	4	NA	❌	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.

BrunoRosendo added P1 cplex P0 and removed P1 labels Mar 23, 2024

BrunoRosendo mentioned this issue Apr 12, 2024

Check if DWave can use BQM in variants that don't use int vars #74

Closed

BrunoRosendo mentioned this issue Apr 17, 2024

Pre and post processing for dwave #58

Open

BrunoRosendo linked a pull request Apr 17, 2024 that will close this issue

Feature/ibm sessions #80

Merged

BrunoRosendo mentioned this issue Apr 18, 2024

QAOA algorithms not working with IBM's latest update #81

Closed

BrunoRosendo added blocked and removed P0 labels Apr 18, 2024

BrunoRosendo mentioned this issue Apr 18, 2024

Try different params with QUBO #11

Closed

BrunoRosendo added the P0 label Apr 18, 2024

BrunoRosendo removed the blocked label May 16, 2024

BrunoRosendo mentioned this issue May 16, 2024

Get timing information from IBM #85

Closed

BrunoRosendo closed this as completed May 16, 2024

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Test algorithms in real machines #44

Test algorithms in real machines #44

BrunoRosendo commented Mar 23, 2024 •

edited

Loading

BrunoRosendo commented Apr 12, 2024

BrunoRosendo commented Apr 12, 2024 •

edited

Loading

BrunoRosendo commented Apr 12, 2024

BrunoRosendo commented Apr 12, 2024

BrunoRosendo commented Apr 12, 2024

BrunoRosendo commented Apr 12, 2024

BrunoRosendo commented Apr 12, 2024 •

edited

Loading

BrunoRosendo commented Apr 12, 2024 •

edited

Loading

BrunoRosendo commented Apr 15, 2024 •

edited

Loading

BrunoRosendo commented Apr 16, 2024

BrunoRosendo commented Apr 16, 2024

BrunoRosendo commented Apr 16, 2024 •

edited

Loading

BrunoRosendo commented Apr 17, 2024

BrunoRosendo commented Apr 17, 2024

BrunoRosendo commented Apr 17, 2024 •

edited

Loading

BrunoRosendo commented Apr 17, 2024

BrunoRosendo commented Apr 18, 2024

BrunoRosendo commented Apr 18, 2024

BrunoRosendo commented May 16, 2024

Test algorithms in real machines #44

Test algorithms in real machines #44

Comments

BrunoRosendo commented Mar 23, 2024 • edited Loading

Things to do

DWave:

Qiskit:

BrunoRosendo commented Apr 12, 2024

BrunoRosendo commented Apr 12, 2024 • edited Loading

BrunoRosendo commented Apr 12, 2024

BrunoRosendo commented Apr 12, 2024

BrunoRosendo commented Apr 12, 2024

BrunoRosendo commented Apr 12, 2024

BrunoRosendo commented Apr 12, 2024 • edited Loading

BrunoRosendo commented Apr 12, 2024 • edited Loading

BrunoRosendo commented Apr 15, 2024 • edited Loading

BrunoRosendo commented Apr 16, 2024

BrunoRosendo commented Apr 16, 2024

BrunoRosendo commented Apr 16, 2024 • edited Loading

BrunoRosendo commented Apr 17, 2024

DWave Results

LeapHybridCQMSampler

LeapHybridSampler

DWaveSampler

BrunoRosendo commented Apr 17, 2024

BrunoRosendo commented Apr 17, 2024 • edited Loading

BrunoRosendo commented Apr 17, 2024

BrunoRosendo commented Apr 18, 2024

BrunoRosendo commented Apr 18, 2024

BrunoRosendo commented May 16, 2024

Qiskit Results

No Warm Start

Warm Start

BrunoRosendo commented Mar 23, 2024 •

edited

Loading

BrunoRosendo commented Apr 12, 2024 •

edited

Loading

BrunoRosendo commented Apr 12, 2024 •

edited

Loading

BrunoRosendo commented Apr 12, 2024 •

edited

Loading

BrunoRosendo commented Apr 15, 2024 •

edited

Loading

BrunoRosendo commented Apr 16, 2024 •

edited

Loading

BrunoRosendo commented Apr 17, 2024 •

edited

Loading