Quadratic Unconstrained Binary Optimization (QUBO)
We used six (6) backends/algorithms, four (4) that utilized classical hardware:
- Qubovert Bruteforce
- IBM Aer State Vector Simulator
- IBMQ QASM Simulator
- Qubovert Simulated Annealing
The two (2) quantum devices used for optimization are:
- IBMQ 16 Melbourne – A 15 Qubit universal gate quantum computer
- D-Wave Advantage 1.1 Solver – An adiabatic quantum computer
We compared the algorithms on two equations:
−5a^2 − 3b^2 − 8c^2 − 6d^2 + 4ab + 8ac + 2bc + 10cd — Eq. 1.1 14a^2 + 32b^2 + 23c^2 + 48d^2 + 11e^2 − 24f^2 − g^2 + 3h^2 − 72i^2 + 71ab + 36ac + 42ad − 90fg − 120bc − Eq. 1.2
Eq. 1.1 has four (4) terms, and it was solved using bruteforce in approximately 125ms. State vector
simulator and QASM simulator took approximately 176ms and 228ms respectively. Qubovert
Simulated Annealing took 203ms. IBMQ 16 Melbourne, which is a 15-qubit universal gate
quantum computer, solved it in approximately 121ms, whereas D-Wave completed it in 55ms.
Since, quantum simulators perform several steps to transpile the program to run them on classical
hardware, and in essence – simulate quantum hardware, hence – the time taken is more than the
actual calculation time (*).
Eq. 1.2 has nine (9), and as the number of combinations go up, the time taken by bruteforce
algorithm also increases. Bruteforce consumes 5066ms. State Vector Simulator and QASM
Simulator perform the worst, taking 7422ms and 8709ms respectively. Qubovert Simulated
Annealing performs comparatively better, consuming 265ms.
IBMQ 16 Melbourne shows that optimization on universal gate quantum computers cannot run as well as AQC, taking 4891ms. D-
Wave Solver performs the best, taking just 48ms.
For Eq. 1.1, D-Wave Solver is 2.20 times faster than IBMQ 16 Melbourne, 4.14 times faster than
QASM Simulator, 2.27 times faster than Bruteforce, 3.2 times faster than State Vector Simulator,
and 3.69 times faster than Qubovert Simulated Annealing.
For Eq. 1.2, D-Wave Solver is 101.90 times faster than IBMQ 16 Melbourne, 181.44 times faster
than QASM Simulator, 105.54 times faster than Bruteforce, 154.62 times faster than State Vector
Simulator, and 5.52 times faster than simulated annealing.
Comparison of classical backends - bruteforce, simulated annealing, state vector simulator, QASM simulator, with quantum backends - IBMQ 16 Melbourne and DWave Advantage Annealer.